Influence and Correlation in Social Networks | Yahoo! Research
By Anagnostopoulos, A.; Kumar, R.; Mahdian, M.
14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) (2008)
In many social systems, social ties between users play an important role in dictating users’ behavior. One of the ways this can happen is through social influence, the phenomenon that the actions of a user can induce his/her friends to behave in a similar way. Identifying and understanding social influence is of tremendous interest from both an analysis (e.g., predicting the future of the system) and a design (e.g., designing viral marketing strategies) point of view. This is a difficult task in general, since there are many other factors that can induce statistical correlation between the actions of friends in a social network. In this paper, we propose two simple tests that can identify influence as a source of social correlation in cases where data on the time step of actions are available. (…)
TrustBets: Operating a Prediction Market on an IOU Network, 2008.
Paper by Sharad Goel, Mohammad Mahdian, David M. Pennock, and Daniel M. Reeves,
We consider the problem of operating a prediction market where players pay with IOUs instead of cash, and where in general not everyone trusts everyone else. Players declare their degree of trust in other players. The system determines what bets are acceptable according to the trust network. We show that if there are n markets, even if the markets are independent, the problem of determining whether a bet is acceptable is NP-hard. In the special case when the trust network is a tree, the problem can be solved in polynomial time using a maximum flow algorithm.