Search

This paper deals with the complexity of some natural graph problems parameterized by some measures that are restrictions of clique-width, such as modular-width and neighborhood diversity. We introduce a novel parameter, called iterated type partition number, that can be computed in linear time and nicely places between modular-width and neighborhood diversity. We prove that the Equitable Coloring problem is W [ 1 ] -hard when parameterized by the iterated type partition number. This result extends to modular-width, answering an open question on the complexity of Equitable Coloring when parameterized by modular-width. On the contrary, we show that the Equitable Coloring problem is FPT when parameterized by neighborhood diversity. Furthermore, we present a scheme for devising FPT algorithms parameterized by iterated type partition number, which enables us to find optimal solutions for several graph problems. As an example, in this paper, we present algorithms parameterized by the iterated type partition number of the input graph for some generalized versions of the Maximum Clique , Minimum Graph Coloring , (Total) Minimum Dominating Set , Minimum Vertex Cover and Maximum Independent Set problems. Each algorithm outputs not only the optimal value but also the optimal solution. We stress that while the considered problems are already known to be FPT with respect to modular-width, the novel algorithms are both simpler and more efficient. We finally show that the proposed scheme can be used to devise polynomial kernels, with respect to iterated type partition number, for the decisional version of most of the problems mentioned above. [ABSTRACT FROM AUTHOR]

We consider the problem of keeping under control the spread of harmful items in networks, such as the contagion proliferation of diseases or the diffusion of fake news. We assume the linear threshold model of diffusion where each node has a threshold that measures the node's resistance to the contagion. We study the parameterized complexity of the problem: Given a network, a set of initially contaminated nodes, and two integers k and ℓ , is it possible to limit the diffusion to at most k other nodes of the network by immunizing at most ℓ nodes? We consider several parameters associated with the input, including the bounds k and ℓ , the maximum node degree Δ , the number ζ of initially contaminated nodes, the treewidth, and the neighborhood diversity of the network. We first give W[1] or W[2]-hardness results for each of the considered parameters. Then we give fixed-parameter algorithms for some parameter combinations. [ABSTRACT FROM AUTHOR]

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 | k 2) 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. [ABSTRACT FROM AUTHOR]

A widely studied model of influence diffusion in social networks represents the network as a graph G = (V , E) , with an integer influence threshold t (v) for each node, and the diffusion process as follows: Initially the members of a chosen set S ⊆ V are influenced and, during each subsequent round, the set of influenced nodes is augmented by including every new node v that has at least t (v) previously influenced neighbours. The general problem is to find a small initial set that influences the whole network. In this paper we extend this model by using incentives to reduce the thresholds of some nodes. The goal is to minimize the total amount of the incentive required to ensure that the information diffusion process terminates within a given number of rounds λ. The problem is hard to approximate in general networks. We present optimal polynomial-time algorithms for paths, cycles, trees, and complete networks for any λ. For the special case λ = 1 , we present a polynomial-time algorithm with a logarithmic approximation guarantee for any network. [ABSTRACT FROM AUTHOR]

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 (2 log 1 − ϵ ⁡ n) , for any fixed ϵ > 0 , unless N P ⊆ D T I M E (n p o l y l o g (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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Abstract Identifying the most influential spreaders is an important issue for the study of the dynamics of information diffusion in complex networks. In this paper we analyze the following spreading model. Initially, a few nodes know a piece of information and are active spreaders of it. At subsequent rounds, spreaders communicate the information to their neighbors. Upon receiving the information, a node becomes aware of it but does not necessarily become a spreader; it starts spreading only if it gets the information from a sufficiently large number of its neighbors. A set of initial spreaders that guarantees that all the nodes become aware of the information is called a perfect seed set. We study the problem of choosing a perfect seed set of minimum size. We provide hardness results and show that the problem becomes tractable on trees. In case of general graphs, we provide an efficient algorithm and validate its effectiveness (in terms of the solution size) on real-life networks. We also study perfect seed sets in dense graphs and derive a bound on the size of a dominating set in Ore graphs. [ABSTRACT FROM AUTHOR]

Highlights • 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. Abstract 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. [ABSTRACT FROM AUTHOR]

Given a network represented by a graph G=(V,E), we consider a dynamical process of influence diffusion in G that evolves as follows: Initially only the nodes of a given S⊆V are influenced; subsequently, at each round, the set of influenced nodes is augmented by all the nodes in the network that have a sufficiently large number of already influenced neighbors. The question is to determine a small subset of nodes S (a target set) that can influence the whole network. This is a widely studied problem that abstracts many phenomena in the social, economic, biological, and physical sciences. It is known that the above optimization problem is hard to approximate within a factor of 2log1-ϵ|V|, for any ϵ>0. In this paper, we present a fast and surprisingly simple algorithm that exhibits the following features: (1) when applied to trees, cycles, or complete graphs, it always produces an optimal solution (i.e, a minimum size target set); (2) when applied to arbitrary networks, it always produces a solution of cardinality which improves on previously known upper bounds; (3) when applied to real-life networks, it always produces solutions that substantially outperform the ones obtained by previously published algorithms (for which no proof of optimality or performance guarantee is known in any class of graphs). [ABSTRACT FROM AUTHOR]

Simulation models are becoming an increasingly popular tool for the analysis and optimization of complex real systems in different fields. Finding an optimal system design requires performing a large sweep over the parameter space in an organized way. Hence, the model optimization process is extremely demanding from a computational point of view, as it requires careful, time-consuming, complex orchestration of coordinated executions. In this paper, we present the design of SOF (Simulation Optimization and exploration Framework in the cloud), a framework which exploits the computing power of a cloud computational environment in order to carry out effective and efficient simulation optimization strategies. SOF offers several attractive features. Firstly, SOF requires “zero configuration”, as it does not require any additional software installed on the remote node; only standard Apache Hadoop and SSH access are sufficient. Secondly, SOF is transparent to the user, since the user is totally unaware that the system operates on a distributed environment. Finally, SOF is highly customizable and programmable, since it enables the running of different simulation optimization scenarios using diverse programming languages – provided that the hosting platform supports them – and different simulation toolkits, as developed by the modeler. The tool has been fully developed and is available on a public repository 1 1 SOF GitHub public repository, https://github.com/isislab-unisa/sof . under the terms of the open source Apache License. It has been tested and validated on several private platforms, such as a dedicated cluster of workstations, as well as on public platforms, including the Hortonworks Data Platform and Amazon Web Services Elastic MapReduce solution. [ABSTRACT FROM AUTHOR]

Euler diagrams are an accessible and effective visualisation of data involving simple set-theoretic relationships. Efficient algorithms to quickly compute the abstract regions of an Euler diagram upon curve addition and removal have previously been developed (the single marked point approach, SMPA), but a strict set of drawing conventions (called well-formedness conditions) were enforced, meaning that some abstract diagrams are not representable as concrete diagrams. We present a new methodology (the multiple marked point approach, MMPA) enabling online region computation for Euler diagrams under the relaxation of the drawing convention that zones must be connected regions. Furthermore, we indicate how to extend the methods to deal with the relaxation of any of the drawing conventions, with the use of concurrent line segments case being of particular importance. We provide complexity analysis and compare the MMPA with the SMPA. We show that these methods are theoretically no worse than other comparators, whilst our methods apply to any case, and are likely to be faster in practise due to their online nature. The machinery developed for the concurrency case could be of use in Euler diagram drawing techniques (in the context of the Euler Graph), and in computer graphics (e.g. the development of an advanced variation of a winged edge data structure that deals with concurrency). The algorithms are presented for generic curves; specialisations such as utilising fixed geometric shapes for curves may occur in applications which can enhance capabilities for fast computations of the algorithms' input structures. We provide an implementation of these algorithms, utilising ellipses, and provide time-based experimental data for benchmarking purposes. [ABSTRACT FROM AUTHOR]

Many modern computing platforms—notably clouds and desktop grids—exhibit dynamic heterogeneity: the availability and computing power of their constituent resources can change unexpectedly and dynamically, even in the midst of a computation. We introduce a new quality metric, AREA, for schedules that execute computations having interdependent constituent chores (jobs, tasks, etc.) on such platforms. AREA measures the average number of chores that a schedule renders eligible for execution at each step of a computation. Even though the definition of AREA does not mention any properties of host platforms (such as volatility), intuition suggests that rendering chores eligible at a faster rate will have a benign impact on the performance of volatile platforms. We report on simulation experiments that support this intuition. Earlier work has derived the basic properties of the AREA metric and has shown how to efficiently craft AREA-maximizing (A-M) schedules for several classes of significant computations. Even though A-M schedules always exist for every computation, it is not always known how to derive such schedules efficiently. In response, the current study develops an efficient algorithm that produces AREA-Oriented (A-O) schedules, which aim to efficiently approximate the AREAs of A-M schedules on arbitrary computations. The simulation experiments reported on here suggest that, in common with A-M schedules, A-O schedules complete computations on volatile heterogeneous platforms faster than a variety of heuristics that range from lightweight ones to computationally intensive ones—albeit not to the same degree as A-M schedules do. Our experiments suggest that schedules having larger AREAs have smaller completion times—but no proof of that yet exists. [ABSTRACT FROM AUTHOR]

Given a network represented by a weighted directed graph G , we consider the problem of finding a bounded cost set of nodes S such that the influence spreading from S in G , within a given time bound, is as large as possible. The dynamics that governs the spread of influence is the following: initially only elements in S are influenced; subsequently at each round, the set of influenced elements is augmented by all nodes in the network that have a sufficiently large number of already influenced neighbors. We prove that the problem is NP-hard, even in simple networks like complete graphs and trees. We also derive a series of positive results. We present exact pseudo-polynomial time algorithms for general trees, that become polynomial time in case the trees are unweighted. This last result improves on previously published results. We also design polynomial time algorithms for general weighted paths and cycles, and for unweighted complete graphs. [ABSTRACT FROM AUTHOR]

The AREA of a schedule for executing DAGs is the average number of DAG-chores that are eligible for execution at each step of the computation. AREA maximization is a new optimization goal for schedules that execute DAGs within computational environments, such as Internet-based computing, clouds, and volunteer computing projects, that are dynamically heterogeneous, in the sense that the environments' constituent computers can change their effective powers at times and in ways that are not predictable. This paper is motivated by the thesis that, within dynamically heterogeneous environments, DAG-schedules that have larger AREAs execute a computation-DAG with smaller completion time under many circumstances; this thesis is supported by preliminary simulation-based experiments. While every DAG admits an AREA-maximizing schedule, it is likely computationally difficult to find such a schedule for an arbitrary DAG. Earlier work has shown how to craft AREA-maximizing schedules efficiently for a number of families of DAGs whose structures are reminiscent of many scientific computations. The current paper extends this work by showing how to efficiently craft AREA-maximizing schedules for series-parallel DAGs, a family that models a multithreading computing paradigm. The techniques for crafting these schedules promise to apply also to other large families of recursively defined DAGs. Moreover, the ability to derive these schedules efficiently leads to an efficient AREA- oriented heuristic for scheduling arbitrary DAGs. [ABSTRACT FROM AUTHOR]

Abstract: Motivated by applications in sociology, economy and medicine, we study variants of the Target Set Selection problem, first proposed by Kempe, Kleinberg and Tardos. In our scenario one is given a graph , integer values for each vertex v (thresholds), and the objective is to determine a small set of vertices (target set) that activates a given number (or a given subset) of vertices of G within a prescribed number of rounds. The activation process in G proceeds as follows: initially, at round 0, all vertices in the target set are activated; subsequently at each round every vertex of G becomes activated if at least of its neighbors are already active by round . It is known that the problem of finding a minimum cardinality Target Set that eventually activates the whole graph G is hard to approximate to a factor better than . In this paper we give exact polynomial time algorithms to find minimum cardinality Target Sets in graphs of bounded clique-width, and exact linear time algorithms for trees. [Copyright &y& Elsevier]

Agent-based simulation models are an increasingly popular tool for research and management in many fields. In executing such simulations “speed” is one of the most general and important issues because of the size and complexity of simulations. But another important issue is the effectiveness of the solution, which consists of how easily usable and portable the solutions are for the users, i.e. the programmers of the distributed simulation. Our study, then, is aimed at efficient and effective distribute simulations by adopting a framework-level approach, with our design and implementation of a framework, D-Mason, which is a parallel version of the Mason library for writing and running simulations of agent-based simulation models. In particular, besides the efficiency due to workload distribution with small overhead, D-Mason at a framework level proves itself effective since it enables the scientists that use the framework (domain expert but with limited knowledge of distributed programming) only minimally aware of the fact that the simulation is running on a distributed environment. Then, we present tests that compare D-Mason against Mason in order to assess the improved scalability and D-Mason capability to exploit heterogeneous distributed hardware. Our tests also show that several massive simulations that are impossible to execute on Mason (e.g. because of CPU and/or memory requirements) can be easily performed using D-Mason. [ABSTRACT FROM AUTHOR]

Abstract: Many modern computing platforms—notably clouds and desktop grids—exhibit dynamic heterogeneity: the availability and computing power of their constituent resources can change unexpectedly and dynamically, even in the midst of a computation. We introduce a new quality metric, area, for schedules that execute computations having interdependent constituent chores (jobs, tasks, etc.) on such platforms. Area measures the average number of tasks that a schedule renders eligible for execution at each step of a computation. Even though the definition of area does not mention and properties of host platforms (such as volatility), intuition suggests that rendering tasks eligible at a faster rate will have a benign impact on the performance of volatile platforms—and we report on simulation experiments that support this intuition. We derive the basic properties of the area metric and show how to efficiently craft area-maximizing (A-M) schedules for several classes of significant computations. Simulations that compare A-M scheduling against heuristics ranging from lightweight ones (e.g., FIFO) to computationally intensive ones suggest that A-M schedules complete computations on volatile heterogeneous platforms faster than their competition, by percentages that vary with computation structure and platform behavior—but are often in the double digits. [Copyright &y& Elsevier]

Abstract: Euler diagrams are an accessible and effective visualisation of data involving simple set-theoretic relationships. Sets are represented by closed curves in the plane and often have wellformedness conditions placed on them in order to enhance comprehensibility. The theoretical underpinning for tool support has usually focussed on the problem of generating an Euler diagram from an abstract model. However, the problem of efficient computation of the abstract model from the concrete diagram has not been addressed before, despite this computation being a necessity for computer interpretations of user drawn diagrams. This may be used, together with automated manipulations of the abstract model, for purposes such as semantic information presentation or diagrammatic theorem proving. Furthermore, in interactive settings, the user may update diagrams “on-line” by adding and removing curves, for example, in which case a system requirement is the update of the abstract model (without the necessity of recomputation of the entire abstract model). We define the notion of marked Euler diagrams, together with a method for associating marked points on the diagram with regions in the plane. Utilising these, we provide on-line algorithms which quickly compute the abstract model of a weakly reducible wellformed Euler diagram (constructible as a sequence of additions or removals of curves, keeping a wellformed diagram at each step), and quickly updates both the set of curves in the plane as well as the abstract model according to the on-line operations. Efficiency is demonstrated by comparison with a common, naive algorithm. Furthermore, the methodology enables a straightforward implementation which has subsequently been realised as an application for the user classification domain. [ABSTRACT FROM AUTHOR]

Abstract: A key challenge when scheduling computations over the Internet is temporal unpredictability: remote “workers” arrive and depart at unpredictable times and often provide unpredictable computational resources; the time for communication over the Internet is impossible to predict accurately. In response, earlier research has developed the underpinnings of a theory of how to schedule computations having intertask dependencies in a way that renders tasks eligible for execution at the maximum possible rate. Simulation studies suggest that such scheduling: (a) utilizes resource providers’ computational resources well, by enhancing the likelihood of having work to allocate to an available client; (b) lessens the likelihood of a computation’s stalling for lack of tasks that are eligible for execution. The applicability of the current version of the theory is limited by its demands on the structure of the dag that models the computation being scheduled—namely, that the dag be decomposable into connected bipartite “building-block” dags. The current paper extends the theory by developing the Sweep Algorithm, which takes a significant step toward removing this restriction. The resulting augmented suite of scheduling algorithms allows one to craft optimal schedules for a large range of dags that the earlier framework could not handle. Most of the newly optimally scheduled dags presented here are artificial but “close” in structure to dags that arise in real computations; one of the new dags is a component of a large dag that arises in a functional Magnetic Resonance Imaging application. [Copyright &y& Elsevier]

Abstract: We study Small-World graphs in the perspective of their use in the development of efficient as well as easy to implement network infrastructures. Our analysis starts from the Small-World model proposed by Kleinberg: a grid network augmented with directed long-range random links. The choices of the long-range links are independent from one node to another. In this setting greedy routing and some of its variants have been analyzed and shown to produce paths of polylogarithmic expected length. We start from asking whether all the randomness, used in Kleinberg’s model for establishing the long-range contacts of the nodes, is indeed necessary to assure the existence of short paths. In order to deal with the above question, we impose (stringent) restrictions on the choice of long-range links and we show that such restrictions do not increase the average path length of greedy routing and its variations. We are able to decrease the number of random bits, required to establish each node’s long-range link, from to on a network of size . Diminishing the randomness in the choice of random links has several benefits; in particular, it implies an increase in the clustering of the graph, thus increasing the resilience of the network. [Copyright &y& Elsevier]

We define a family of Distributed Hash Table systems whose aim is to combine the routing efficiency of randomized networks—e.g. optimal average path length O(log 2 n/ δlog δ) with δ degree—with the programmability and startup efficiency of a uniform overlay—that is, a deterministic system in which the overlay network is transitive and greedy routing is optimal. It is known that Ω(log n) is a lower bound on the average path length for uniform overlays with O(log n) degree (Xu et al., IEEE J. Sel. Areas Commun. 22(1), 151–163, ). Our work is inspired by neighbor-of-neighbor (NoN) routing, a recently introduced variation of greedy routing that allows us to achieve optimal average path length in randomized networks. The advantage of our proposal is that of allowing the NoN technique to be implemented without adding any overhead to the corresponding deterministic network. We propose a family of networks parameterized with a positive integer c which measures the amount of randomness that is used. By varying the value c, the system goes from the deterministic case ( c=1) to an “ almost uniform” system. Increasing c to relatively low values allows for routing with asymptotically optimal average path length while retaining most of the advantages of a uniform system, such as easy programmability and quick bootstrap of the nodes entering the system. We also provide a matching lower bound for the average path length of the routing schemes for any c. [ABSTRACT FROM AUTHOR]

Earlier work has developed the underpinnings of the IC-Scheduling Theory, a framework for scheduling computations having intertask dependencies—modeled via directed acyclic graphs (DAGs)—for Internet-based computing. The goal of the schedules produced is to render tasks eligible for execution at the maximum possible rate, with the dual aim of 1) utilizing remote clients' computational resources well by always having work to allocate to an available client and 2) lessening the likelihood of a computation's stalling for lack of eligible tasks. The DAGs handled by the theory thus far are those that can be decomposed into a given collection of bipartite building block DAGs via the operation of DAG decomposition. A basic tool in constructing schedules is a relation ..., which allows one to "prioritize" the scheduling of a complex DAG's building blocks. The current paper extends the IC-Scheduling Theory in two ways: by expanding significantly the repertoire of DAGs that the Theory can schedule optimally and by allowing one sometimes to shortcut the algorithmic process required to find optimal schedules. The expanded repertoire now allows the theory to schedule optimally, among other DAGs, a large range of DAGs that are either "expansive," in the sense that they grow outward from their sources, or "reductive," in the sense that they grow inward toward their sinks. The algorithmic shortcuts allow one to "read off" an optimal schedule for a DAG from a given optimal schedule for the DAG's dual, which is obtained by reversing all arcs (thereby exchanging the roles of sources and sinks). [ABSTRACT FROM AUTHOR]

This work deals with a generalization of the minimum Target Set Selection (TSS) problem, a key algorithmic question in information diffusion research due to its potential commercial value. Firstly proposed by Kempe et al., the TSS problem is based on a linear threshold diffusion model defined on an input graph with node thresholds, quantifying the hardness to influence each node. The goal is to find the smaller set of items that can influence the whole network according to the diffusion model defined. This study generalizes the TSS problem on networks characterized by many-to-many relationships modeled via hypergraphs. Specifically, we introduce a linear threshold diffusion process on such structures, which evolves as follows. Let H = (V , E) be a hypergraph. At the beginning of the process, the nodes in a given set S ⊆ V are influenced. Then, at each iteration, (i) the influenced hyperedges set is augmented by all edges having a sufficiently large number of influenced nodes; (ii) consequently, the set of influenced nodes is enlarged by all the nodes having a sufficiently large number of already influenced hyperedges. The process ends when no new nodes can be influenced. Exploiting this diffusion model, we define the minimum Target Set Selection problem on hypergraphs (TSSH). Being the problem NP-hard (as it generalizes the TSS problem), we introduce four heuristics and provide an extensive evaluation on real-world networks. [ABSTRACT FROM AUTHOR]

This research involved 88 young adults aged between 20 years and 35 years from two different countries, Spain and Italy. This work aims to explore preferences of the two groups toward synthetic voices, created for the experiment with variations in gender and quality for each language. The Spanish group was asked to evaluate the two high-quality voices of Elena and Pablo and the two low-quality voices of Maria and Juan while the Italian group was asked to assess the high-quality voices of Giulia and Antonio and the low-quality voices of Clara and Edoardo. The shortened and digitized version of the Virtual Agent Voice Acceptance Questionnaire (VAVAQ) was administered, respectively, in the Spanish or Italian version on the basis of the referring group to collect participants' preferences. Due to the pandemic situation, participants were mainly contacted via email. Each participant was provided with a specific link. Outcomes revealed that Spanish and Italian young adults showed a greater appreciation toward the high-quality female voice compared to the other proposed voices. Regarding participants' cross-cultural differences, Italian participants seem to judge the voices as more emotionally engaging than the Spanish participants whereas Spanish participants consider the audited voices as more natural and expressive than the Italian participants. [ABSTRACT FROM AUTHOR]

This study contributes knowledge on the detection of depression through handwriting/drawing features, to identify quantitative and noninvasive indicators of the disorder for implementing algorithms for its automatic detection. For this purpose, an original online approach was adopted to provide a dynamic evaluation of handwriting/drawing performance of healthy participants with no history of any psychiatric disorders (n = 2 8), and patients with a clinical diagnosis of depression (n = 2 7). Both groups were asked to complete seven tasks requiring either the writing or drawing on a paper while five handwriting/drawing features' categories (i.e. pressure on the paper, time, ductus, space among characters, and pen inclination) were recorded by using a digitalized tablet. The collected records were statistically analyzed. Results showed that, except for pressure, all the considered features, successfully discriminate between depressed and nondepressed subjects. In addition, it was observed that depression affects different writing/drawing functionalities. These findings suggest the adoption of writing/drawing tasks in the clinical practice as tools to support the current depression detection methods. This would have important repercussions on reducing the diagnostic times and treatment formulation. [ABSTRACT FROM AUTHOR]

Based on a previous investigation, a quantitative study aimed to identify user' preferences towards four synthetic voices of two different quality levels (classified through the sophistication of the synthesizer: low vs. high) is proposed. The voices administered to participants were developed considering two main aspects: the voice quality (high/low) and their gender (male/female). 182 unpaid participants were recruited for the study, divided in four groups according to their age, and therefore classified as adolescents, young adults, middle-aged, and seniors. To collect data regarding each voice, randomly audited by participants, the shortened version of the Virtual Agent Voice Acceptance Questionnaire (VAVAQ) was exploited. Outcomes of the previous study revealed that the voices of high quality, regardless of their gender, received a higher acclaim by all participants examined rather than the corresponding two voices assessed as lower quality. Conversely, findings of the current study suggest that the four new groups of participants involved agreed in showing their strong preference towards the high-quality voice gendered as female compared to all the other considered voices. Regarding the two voices gendered as male, the high-quality one was considered as more original and capable to arouse positive emotional states than the low-quality one. Moreover, the high-quality male voice was judged as more natural than the female low-quality one. Results provide some insights for future directions in the user experience and design field. [ABSTRACT FROM AUTHOR]

This paper proposes a systematic approach to investigate the impact of factors such as the gender and age of participants and gender, and age of faces on the decoding accuracy of emotional expressions of disgust, anger, sadness, fear, happiness, and neutrality. The emotional stimuli consisted of 76 posed and 76 naturalistic faces, differently aged (young, middle-aged, and older) selected from FACES and SFEW databases. Either a posed or naturalistic faces' decoding task was administered. The posed faces' decoding task involved three differently aged groups (young, middle-aged, and older adults). The naturalistic faces' decoding task involved two groups of older adults. For the posed decoding task, older adults were found significantly less accurate than middle-aged and young participants, and middle-aged significantly less accurate than young participants. Old faces were significantly less accurately decoded than young and middle-aged faces of disgust, and anger, and young faces of fear, and neutrality. Female faces were significantly more accurately decoded than male faces of anger and sadness, significantly less accurately decoded than male faces of neutrality. For the naturalistic decoding task, older adults were significantly less accurate in decoding naturalistic rather than posed faces of disgust, fear, and neutrality, contradicting an older adults' emended support from a prior naturalistic emotional experience. Young faces were more accurately decoded than old and middle-aged faces of disgust and anger and old faces of neutrality. Female faces were significantly more accurately decoded than male faces of fear, and significantly less accurately decoded than male faces of anger. Significant effects and significant interdependencies were observed among the age of participants, emotional categories, age, and gender of faces, and type of stimuli (naturalistic vs. posed), not allowing to distinctly isolate the effects of each involved variable. Nevertheless, the data collected in this paper weakens both the assumptions on women enhanced ability to display and decode emotions and participants enhanced ability to decode faces closer to their own age ("own age bias" theory). Considerations are made on how these data would guide the development of assessment tools and preventive interventions and the design of emotionally and socially believable virtual agents and robots to assists and coach emotionally vulnerable people in their daily routines. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

In this research, we analyse data obtained from sensors when a user handwrites or draws on a tablet to detect whether the user is in a specific mood state. First, we calculated the features based on the temporal, kinematic, statistical, spectral and cepstral domains for the tablet pressure, the horizontal and vertical pen displacements and the azimuth of the pen's position. Next, we selected features using a principal component analysis (PCA) pipeline, followed by modified fast correlation–based filtering (mFCBF). PCA was used to calculate the orthogonal transformation of the features, and mFCBF was used to select the best PCA features. The EMOTHAW database was used for depression, anxiety and stress scale (DASS) assessment. The process involved the augmentation of the training data by first augmenting the mood states such that all the data were the same size. Then, 80% of the training data was randomly selected, and a small random Gaussian noise was added to the extracted features. Automated machine learning was employed to train and test more than ten plain and ensembled classifiers. For all three moods, we obtained 100% accuracy results when detecting two possible grades of mood severities using this architecture. The results obtained were superior to the results obtained by using state-of-the-art methods, which enabled us to define the three mood states and provide precise information to the clinical psychologist. The accuracy results obtained when detecting these three possible mood states using this architecture were 82.5%, 72.8% and 74.56% for depression, anxiety and stress, respectively. [ABSTRACT FROM AUTHOR]