1,720,966 research outputs found
Stable outcomes in modified fractional hedonic games
Full text linkIn coalition formation games self-organized coalitions are created as a result of the strategic interactions of independent agents. In this paper we assume that for each couple of agents (i, j), weight wi,j= wj,i reflects how much agents i and j benefit from belonging to the same coalition. We consider the (symmetric) modified fractional hedonic game, that is a coalition formation game in which agents’ utilities are such that the total benefit of agent i belonging to a coalition (given by the sum of wi,j over all other agents j belonging to the same coalition) is averaged over all the other members of that coalition, i.e., excluding herself. Modified fractional hedonic games constitute a class of succinctly representable hedonic games. We are interested in the scenario in which agents, individually or jointly, choose to form a new coalition or to join an existing one, until a stable outcome is reached. To this aim, we consider common stability notions leading to strong Nash stable outcomes, Nash stable outcomes or core stable outcomes: we study their existence, complexity and performance, both in the case of general weights and in the case of 0–1 weights. In particular, we completely characterize the existence of the considered stable outcomes and show many tight or asymptotically tight results on the performance of these natural stable outcomes for modified fractional hedonic games, also highlighting the differences with respect to the model of fractional hedonic games, in which the total benefit of an agent in a coalition is averaged over all members of that coalition, i.e., including herself
Link recommendation for social influence maximization
No full textSocial link recommendation systems, like "People-you-may-know" on Facebook, "Who-to-follow" on Twitter, and "Suggested-Accounts" on Instagram assist the users of a social network in establishing new connections with other users.While these systems are becoming more and more important in the growth of social media, they tend to increase the popularity of users that are already popular. Indeed, since link recommenders aim to predict user behavior, they accelerate the creation of links that are likely to be created in the future and, consequently, reinforce social bias by suggesting few (popular) users, giving few chances to most users to create new connections and increase their popularity. In this article, we measure the popularity of a user by means of her social influence, which is her capability to influence other users' opinions, and we propose a link recommendation algorithm that evaluates the links to suggest according to their increment in social influence instead of their likelihood of being created. In detail, we give a 1 - ∈ factor approximation algorithm for the problem of maximizing the social influence of a given set of target users by suggesting a fixed number of new connections considering the Linear Threshold model asmodel for diffusion.We experimentally showthat,with fewnewlinks and small computational time, our algorithm is able to increase by far the social influence of the target users. We compare our algorithm with several baselines and show that it is the most effective one in terms of increased influence
Generalized budgeted submodular set function maximization
No full textIn the generalized budgeted submodular set function maximization problem, we are given a ground set of elements and a set of bins. Each bin has its own cost and the cost of each element depends on its associated bin. The goal is to find a subset of elements along with an associated set of bins such that the overall costs of both is at most a given budget, and the profit is maximized. We present an algorithm that guarantees a [Formula presented](1−[Formula presented])-approximation, where α≤1 is the approximation factor of an algorithm for a sub-problem. If the costs satisfy a specific condition, we provide a polynomial-time algorithm that gives us α=1−ε, while for the general case we design an algorithm with α=1−[Formula presented]−ε. We extend our results providing a bi-criterion approximation algorithm where we can spend an extra budget up to a factor β≥1 to guarantee a [Formula presented](1−[Formula presented])-approximation
On the performance of stable outcomes in modified fractional hedonic games with egalitarian social welfare
No full textIn this paper we consider modified fractional hedonlc games, that are coalition formation games defined over an undirected edge-weighted graph G = (N, E, w), where N is the set of agents and for any edge u.v E, wu = wu-u reflects how much agents u and v benefit from belonging to the same coalition More specifically, given a coalition structure, Le., a partition of the agents into coalitions, the utility of an agent u is given by the sum of wu over all other agents v belonging to the same coalition of u averaged over all other members of that coalition, i.e., excluding herself We focus on common stability notions: We are interested in strong Nash stable, Nash stable and core stable outcomes In [18], the existence of these natural outcomes for modified fractional hedonic games is completely characterized; moreover, many tight or asymptotically tight results on their performance are shown for the classical utilitarian social welfare function, that is defined as the sum of all agents' utilities Motivated by the fact that an outcome with an high utilitarian social welfare could be extremely harsh for some agents, we pro-vide a comprehensive analysis on the performance of strong Nash stable, Nash stable and core stable outcomes for modified fractional hedonic games under the egalitarian social welfare function, that is defined as the minimum among all agents' utilities
Recommending Links to Maximize the Influence in Social Networks
No full textSocial link recommendation systems, like “People-you-may-know” on Facebook, “Who-to-follow” on Twitter, and “Suggested-Accounts” on Instagram assist the users of a social network in establishing new connections with other users. While these systems are becoming more and more important in the growth of social media, they tend to increase the popularity of users that are already popular. Indeed, since link recommenders aim at predicting users' behavior, they accelerate the creation of links that are likely to be created in the future, and, as a consequence, they reinforce social biases by suggesting few (popular) users, while giving few chances to the majority of users to build new connections and increase their popularity. In this paper we measure the popularity of a user by means of its social influence, which is its capability to influence other users' opinions, and we propose a link recommendation algorithm that evaluates the links to suggest according to their increment in social influence instead of their likelihood of being created. In detail, we give a constant factor approximation algorithm for the problem of maximizing the social influence of a given set of target users by suggesting a fixed number of new connections. We experimentally show that, with few new links and small computational time, our algorithm is able to increase by far the social influence of the target users. We compare our algorithm with several baselines and show that it is the most effective one in terms of increased influence
Recommending Links to Control Elections via Social Influence
Full text linkPolitical parties recently learned that they must use social media campaigns along with advertising on traditional media to defeat their opponents. Before the campaign starts, it is important for a political party to establish and ensure its media presence, for example by enlarging their number of connections in the social network in order to assure a larger portion of users. Indeed, adding new connections between users increases the capabilities of a social network of spreading information, which in turn can increase the retention rate and the number of new voters. In this work, we address the problem of selecting a fixed-size set of new connections to be added to a subset of voters that, with their influence, will change the opinion of the network’s users about a target candidate, maximizing its chances to win the election. We provide a constant factor approximation algorithm for this problem and we experimentally show that, with few new links and small computational time, our algorithm is able to maximize the chances to make the target candidate win the elections
Additively Separable Hedonic Games with Social Context
Full text linkIn hedonic games, coalitions are created as a result of the strategic interaction of independent players. In particular, in additively separable hedonic games, every player has valuations for all other ones, and the utility for belonging to a coalition is given by the sum of the valuations for all other players belonging to it. So far, non-cooperative hedonic games have been considered in the literature only with respect to totally selfish players. Starting from the fundamental class of additively separable hedonic games, we define and study a new model in which, given a social graph, players also care about the happiness of their friends: we call this class of games social context additively separable hedonic games (SCASHGs). We focus on the fundamental stability notion of Nash equilibrium, and study the existence, convergence and performance of stable outcomes (with respect to the classical notions of price of anarchy and price of stability) in SCASHGs. In particular, we show that SCASHGs are potential games, and therefore Nash equilibria always exist and can be reached after a sequence of Nash moves of the players. Finally, we provide tight or asymptotically tight bounds on the price of anarchy and the price of stability of SCASHGs
The Multi-budget Maximum Weighted Coverage Problem
No full textIn this paper we consider the multi-budget maximum weighted coverage problem, a generalization of the classical maximum coverage problem, where we are given k budgets, a set X of elements, and a set S of bins where any S∈ S is a subset of elements of X. Each bin S has its own cost, and each element its own weight. An outcome is a vector O= (O1, ⋯, Ok) where each budget bi, for i= 1, ⋯, k, can be used to buy a subset of bins Oi⊆ S of overall cost at most bi. The objective is to maximize the total weight which is defined as the sum of the weights of the elements bought with the budgets. We consider the classical combinatorial optimization problem of computing an outcome which maximizes the total weight and provide a (1-1e) -approximation algorithm for the case when the maximum cost of a bin is upper-bounded by the minimum budget, i.e. the case in which each budget can be used to buy any bin. Moreover, we give a randomized Monte-Carlo algorithm for the general case that runs in polynomial time, satisfies the budget constraints in expectation, and guarantees an expected 1-1e approximation factor
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
- …
