Dual domination problems in graphs Cordasco, Gennaro; Gargano, Luisa; Rescigno, Adele A.
Journal of computer and system sciences,
September 2022, 2022-09-00, Letnik:
128
Journal Article
Recenzirano
We introduce a novel domination problem, which we call Dual Domination (DD). We assume that the nodes in a network are partitioned into two categories: Positive nodes (V+) and negative nodes (V−). We ...study the Maximum Bounded Dual Domination, where, given a bound k, the problem is to find a set D⊆V+, which maximizes the number of nodes dominated in V+, dominating at most k nodes in V−. We show that such problem is hard to approximate to a factor better than (1−1/e). We give a polynomial time algorithm with approximation guaranteed (1−e−1/Δ), where Δ represents the maximum number of neighbors in V+ of any node in V−, and an O(|V|k2) time algorithm to solve the problem on trees. We also study two related problems named Maximum Dual Domination and minimum Negative Dual Domination. For both problems, we show hardness results and provide O(|V|) time algorithms on trees.
Hypergraphs have attracted increasing attention in recent years thanks to their flexibility in naturally modeling a broad range of systems where high-order relationships exist among their interacting ...parts. This survey reviews the newly born hypergraph representation learning problem, whose goal is to learn a function to project objects—most commonly nodes—of an input hyper-network into a latent space such that both the structural and relational properties of the network can be encoded and preserved. We provide a thorough overview of existing literature and offer a new taxonomy of hypergraph embedding methods by identifying three main families of techniques, i.e., spectral, proximity-preserving, and (deep) neural networks. For each family, we describe its characteristics and our insights in a single yet flexible framework and then discuss the peculiarities of individual methods, as well as their pros and cons. We then review the main tasks, datasets, and settings in which hypergraph embeddings are typically used. We finally identify and discuss open challenges that would inspire further research in this field.
The detection of negative emotions through daily activities such as writing and drawing is useful for promoting wellbeing. The spread of human-machine interfaces such as tablets makes the collection ...of handwriting and drawing samples easier. In this context, we present a first publicly available database which relates emotional states to handwriting and drawing, that we call EMOTHAW (EMOTion recognition from HAndWriting and draWing). This database includes samples of 129 participants whose emotional states, namely anxiety, depression, and stress, are assessed by the Depression-Anxiety-Stress Scales (DASS) questionnaire. Seven tasks are recorded through a digitizing tablet: pentagons and house drawing, words copied in handprint, circles and clock drawing, and one sentence copied in cursive writing. Records consist in pen positions, on-paper and in-air, time stamp, pressure, pen azimuth, and altitude. We report our analysis on this database. From collected data, we first compute measurements related to timing and ductus. We compute separate measurements according to the position of the writing device: on paper or in-air. We analyze and classify this set of measurements (referred to as features) using a random forest approach. This latter is a machine learning method, based on an ensemble of decision trees, which includes a feature ranking process. We use this ranking process to identify the features which best reveal a targeted emotional state. We then build random forest classifiers associated with each emotional state. We provide accuracy, sensitivity, and specificity evaluation measures obtained from cross-validation experiments. Our results show that anxiety and stress recognition perform better than depression recognition.
In social interactions, the reciprocity norm implies to adjust one’s behavior to that of the other agents. Conversely, behaving according to self-interest involves taking into account the reciprocity ...principle only if it does not hinder the achievement of one’s goals. However, reciprocity and self-interest may conflict with each other, as when returning a kind action involves sacrificing the possibility to achieve a personal objective. The conflict could be exacerbated by some contextual factors, such as competitive pressures. This study investigated, in a competitive interaction context, which principle prevails when the two conflict. To this end, 276 unpaid participants (M = 138) took part in a two-stage experiment entailing a simulated interaction with a fictitious opponent, which behaved selfishly, fairly or altruistically toward them during the first stage. Participants had to decide whether or not to reciprocate the opponent’s previous behavior, which in the critical experimental conditions conflicted with the goal to successfully complete the experiment. So, they were faced with a moral dilemma. Competition degree was manipulated to make the conflict between reciprocity and self-interest more or less harsh. Moreover, we tested whether the putative effect of experimental manipulation was mediated by changes in context-related affective states and personal beliefs about morality. Results showed that decision-making was principally influenced by reciprocity. Regardless of the competition degree, participants preferred to engage in reciprocal behavior even when this compromised their personal interest. Affective states and beliefs changed in response to the experimental manipulation, but they did not mediate the effect of the independent variable on decision-making.
Considered the increasing use of assistive technologies in the shape of virtual agents, it is necessary to investigate those factors which characterize and affect the interaction between the user and ...the agent, among these emerges the way in which people interpret and decode synthetic emotions, i.e., emotional expressions conveyed by virtual agents. For these reasons, an article is proposed, which involved 278 participants split in differently aged groups (young, middle-aged, and elders). Within each age group, some participants were administered a "naturalistic decoding task," a recognition task of human emotional faces, while others were administered a "synthetic decoding task" namely emotional expressions conveyed by virtual agents. Participants were required to label pictures of female and male humans or virtual agents of different ages (young, middle-aged, and old) displaying static expressions of disgust, anger, sadness, fear, happiness, surprise, and neutrality. Results showed that young participants showed better recognition performances (compared to older groups) of anger, sadness, and neutrality, while female participants showed better recognition performances (compared to males) of sadness, fear, and neutrality; sadness and fear were better recognized when conveyed by real human faces, while happiness, surprise, and neutrality were better recognized when represented by virtual agents. Young faces were better decoded when expressing anger and surprise, middle-aged faces were better decoded when expressing sadness, fear, and happiness, while old faces were better decoded in the case of disgust; on average, female faces where better decoded compared to male ones.
•Novel geometric non-uniform work partitioning approach for simulation environment.•Distributed version of MASON continuous 3D field and network field.•Fully decentralized communication strategy, ...based on the MPI standard.•Memory Consistency Mechanism to ensure memory coherence in distributed simulation.•SIMulation-as-a-Service environment on cloud computing infrastructures.
Computational Social Science (CSS) involves interdisciplinary fields and exploits computational methods, such as social network analysis as well as computer simulation with the goal of better understanding social phenomena.
Agent-Based Models (ABMs) represent an effective research tool for CSS and consist of a class of models, which, aim to emulate or predict complex phenomena through a set of simple rules (i.e., independent actions, interactions and adaptation), performed by multiple agents. The efficiency and scalability of ABMs systems are typically obtained distributing the overall computation on several machines, which interact with each other in order to simulate a specific model. Unfortunately, the design of a distributed simulation model is particularly challenging, especially for domain experts who sporadically are computer scientists and are not used to developing parallel code.
D-MASON framework is a distributed version of the MASON library for designing and executing ABMs in a distributed environment ensuring scalability and easiness. D-MASON enable the developer to exploit the computing power of distributed environment in a transparent manner; the developer has to do simple incremental modifications to existing MASON models, without re-designing them.
This paper presents several novel features and architectural improvements introduced in the D-MASON framework: an improved space partitioning strategy, a distributed 3D field, a distributed network field, a decentralized communication layer, a novel memory consistency mechanism and the integration to cloud environments.
Full documentation, additional tutorials, and other material can be found at https://github.com/isislab-unisa/dmason where the framework can be downloaded.
Summary
The cloud computing paradigm has emerged as the backbone of modern price‐aware scalable computing systems. Many cloud service models are competing to become the leading doorway to access the ...computational power of cloud providers. Recently, a novel service model, called function‐as‐a‐service (FaaS), has been proposed, which enables users to exploit the cloud computational scalability, left out the configuration and management of huge computing infrastructures. This article discloses Fly, a domain‐specific language, which aims at reconciling cloud and high‐performance computing paradigms adopting a multicloud strategy by providing a powerful, effective, and pricing‐efficient tool for developing scalable workflow‐based scientific applications by exploiting different and at the same time FaaS cloud providers as computational backends in a transparent fashion. We present several improvements of the Fly language, as well as a new enhanced version of a source‐to‐source compiler, which currently supports Symmetric Multiprocessing, Amazon AWS, and Microsoft Azure backends and translation of functions in Java, JavaScript, and Python programming languages. Furthermore, we discuss a performance evaluation of Fly on a popular benchmark for distributed computing frameworks, along with a collection of case studies with an analysis of their performance results and costs.
Whom to befriend to influence people Cordasco, Gennaro; Gargano, Luisa; Lafond, Manuel ...
Theoretical computer science,
03/2020, Letnik:
810
Journal Article
Recenzirano
Odprti dostop
Alice wants to join a new social network, and influence its members to adopt a new product or idea. Each person v in the network has a certain threshold t(v) for activation, i.e. adoption of the ...product or idea. If v has at least t(v) activated neighbors, then v will also become activated. If Alice wants to activate the entire social network, whom should she befriend? More generally, we study the problem of finding the minimum number of links that a set of external influencers should form to people in the network, in order to activate the entire social network. This Minimum Links Problem has applications in viral marketing and the study of epidemics. Its solution can be quite different from the related and widely studied Target Set Selection problem. We prove that the Minimum Links problem cannot be approximated to within a ratio of O(2log1−ϵn), for any fixed ϵ>0, unless NP⊆DTIME(npolylog(n)), where n is the number of nodes in the network. On the positive side, we give linear time algorithms to solve the problem for trees, cycles, and cliques, for any given set of external influencers, and give precise bounds on the number of links needed. For general graphs, we design a polynomial time algorithm to compute size-efficient link sets that can activate the entire graph.
HUM-CARD: A human crowded annotated real dataset Di Gennaro, Giovanni; Greco, Claudia; Buonanno, Amedeo ...
Information systems (Oxford),
September 2024, 2024-09-00, Letnik:
124
Journal Article
Recenzirano
Odprti dostop
The growth of data-driven approaches typical of Machine Learning leads to an ever-increasing need for large quantities of labeled data. Unfortunately, these attributions are often made automatically ...and/or crudely, thus destroying the very concept of “ground truth” they are supposed to represent. To address this problem, we introduce HUM-CARD, a dataset of human trajectories in crowded contexts manually annotated by nine experts in engineering and psychology, totaling approximately 5000 hours. Our multidisciplinary labeling process has enabled the creation of a well-structured ontology, accounting for both individual and contextual factors influencing human movement dynamics in shared environments. Preliminary and descriptive analyzes are presented, highlighting the potential benefits of this dataset and its methodology in various research challenges.
PDF
