Influence maximization plays a key role in social network viral marketing. Although the problem has been widely studied, it is still challenging to estimate influence spread in big networks with hundreds of millions of nodes. Existing heuristic algorithms and greedy algorithms incur heavy computation cost in big networks and are incapable of processing dynamic network structures. In this paper, we propose an incremental algorithm for influence spread estimation in big networks. The incremental algorithm breaks down big networks into small subgraphs ad continuously estimate influence spread on these subgraphs as data streams. The challenge of the incremental algorithm is that subgraphs derived from a big network are not independent and MC simulations on each subgraph (defined as snapshots) may conflict with each other. In this paper, we assume that different combinations of MC simulations on subgraphs on subgraphs generate independent samples. In so doing, the incremental algorithm on streaming subgraphs can estimate influence spread with fewer simulations. Experimental results demonstrates the performance of the proposed algorithm.

The rapidly growing of Location-based Social Networks (LBSNs) provides a vast amount of check-in data, which enables many services, e.g., point-of-interest (POI) recommendation. In this paper, we study the next new POI recommendation problem in which new POIs with respect to users' current location are to be recommended. The challenge lies in the difficulty in precisely learning users' sequential information and personalizing the recommendation model. To this end, we resort to the Metric Embedding method for the recommendation, which avoids drawbacks of the Matrix Factorization technique. We propose a personalized ranking metric embedding method (PRME) to model personalized check-in sequences. We further develop a PRME-G model, which integrates sequential information, individual preference, and geographical influence, to improve the recommendation performance. Experiments on two real-world LBSN datasets demonstrate that our new algorithm outperforms the state-of-the-art next POI recommendation methods.

The triad is one of the most basic human groups in social networks. Understanding factors affecting the formation of triads will help reveal the underlying mechanisms that govern the emergence and evolution of complex social networks. In this paper, we study an interesting problem of decoding triadic closure in social networks. Specifically, for a given closed triad (a group of three people who are friends with each other), which link was created first, which followed, and which link closed. The problem is challenging, as we may not have any dynamic information. Moreover, the closure processes of different triads are correlated with each other. Our technical contribution lies in the proposal of a probabilistic factor graph model (DeTriad). The model is able to recover the dynamic information in the triadic closure process. It also naturally models the correlations among closed triads. We evaluate the proposed model on a large collaboration network, and the experimental results show that our method improves the accuracy of decoding triadic closure by up to 20% over that of several alternative methods.

We introduce the study of adversarial effects on wisdom of the crowd phenomena. In particular, we examine the ability of an adversary to influence a social network so that the majority of nodes are convinced by a falsehood, using its power to influence a certain fraction, μ < 0.5 of N experts. Can a bad restaurant make a majority of the overall network believe in the quality of that restaurant by misleading a certain share of food critics into believing its food is good, and use the influence of those experts to make a majority of the overall network to believe in the quality of that restaurant? We are interested in providing an agent, which does not necessarily know the graph structure nor who the experts are, to determine the true value of a binary property using a simple majority. We prove bounds on the social graph's maximal degree, which ensure that with a high probability the adversary will fail (and the majority vote will coincide with the true value) when it can choose who the experts are, while each expert communicates the true value with probability p > 0.5. When we examine expander graphs as well as random graphs we prove such bounds even for stronger adversaries, who are able to pick and choose not only who the experts are, but also which ones of them would communicate the wrong values, as long as their proportion is 1-p. Furthermore, we study different propagation models and their effects on the feasibility of obtaining the true value for different adversary types.

We consider revenue negotiation problems in iterative settings. In our model, a group of agentshas some initial resources, used in order to generate revenue. Agents must agree on some way of dividing resources, but there’s a twist. At every time-step, the revenue shares received at time t are agent resources at time t + 1, and the game is repeated. The key issue here is that the way resources are shared has a dramatic effect on long term social welfare, so in order to maximize individual long-term revenue one must consider the welfare of others, a behavior not captured by other models of cooperation and bargaining. Our work focuses on homogeneous production functions. We identify conditions that ensure that the socially optimal outcome is an epsilon-Nash equilibrium. We apply our results to some families of utility functions, and discuss their strategic implications.

They pinpoint families of voting rules that exhibit robustness: they are accurate in the limit with respect to a wide Classic social choice theory assumes that votes are range of noise models, which govern the way noisy votes are independent (but possibly conditioned on an underlying generated, given the ground truth [Caragiannis et al., 2013; objective ground truth). This assumption 2014]. is unrealistic in settings where the voters are connected While these results are promising, they rely on a crucial via an underlying social network structure, modeling assumption: votes are independent. This assumption as social interactions lead to correlated votes. We is clearly satisfied in some settings -- when votes are establish a general framework -- based on random submitted by computer Go programs [Jiang et al., 2014], say.

Manipulation can be performed when intermediate voting results are known; voters might attempt to vote strategically and try and manipulate the results during an iterative voting process. When only partial voting preferences are available, preference elicitation is necessary. In this paper, we combine two approaches of iterative processes: iterative preference elicitation and iterative voting and study the outcome and performance of a setting where manipulative voters submit partial preferences. We provide practical algorithms for manipulation under the Borda voting rule and evaluate those using different voting centers: the Careful voting center that tries to avoid manipulation and the Naive voting center. We show that in practice, manipulation happens in a low percentage of the settings and has a low impact on the final outcome. The Careful voting center reduces manipulation even further.

Voting is commonly used as a method for aggregating information in crowdsourcing and human computation. In many settings, one would like to use voting rules which can be efficiently elicited, preserve voter privacy, and are robust to strategic manipulation. In this paper, we give algorithms which elicit approximate winners in a way which provably satisfies all three of these requirements simultaneously. Our results hold for tournament voting rules, which we define to be the voting rules which can be expressed solely as a function of the table of pairwise comparisons containing the number of voters preferring one candidate to another. Tournament voting rules include many common voting rules such as the Borda, Copeland, Maximin, Nanson, Baldwin, Kemeny-Young, Ranked Pairs, Cup, and Schulze voting rules. Our results significantly expand the set of voting rules for which efficient elicitation was known to be possible and improve the known approximation factors for epsilon-strategyproof voting in the regime where the number of candidates is large.

Many hard computational social choice problems are known to become tractable when voters' preferences belong to a restricted domain, such as those of single-peaked or single-crossing preferences. However, to date, all algorithmic results of this type have been obtained for the setting where each voter's preference list is a total order of candidates. The goal of this paper is to extend this line of research to the setting where voters' preferences are dichotomous, i.e., each voter approves a subset of candidates and disapproves the remaining candidates. We propose several analogues of the notions of single-peaked and single-crossing preferences for dichotomous profiles and investigate the relationships among them. We then demonstrate that for some of these notions the respective restricted domains admit efficient algorithms for computationally hard approval-based multi-winner rules.

One prominent way to deal with conflicting view-points among agents is to conduct an argumentative debate: by exchanging arguments, agents can seek to persuade each other. In this paper we investigate the problem, for an agent, of optimizing a sequence of moves to be put forward in a debate, against an opponent assumed to behave stochastically, and equipped with an unknown initial belief state. Despite the prohibitive number of states induced by a naive mapping to Markov models, we show that exploiting several features of such interaction settings allows for optimal resolution in practice, in particular: (1) as debates take place in a public space (or common ground), they can readily be modelled as Mixed Observability Markov Decision Processes, (2) as argumentation problems are highly structured, one can design optimization techniques to prune the initial instance. We report on the experimental evaluation of these techniques.