How to Optimally allocate your budget of attention in social networks
Authors:
- 1 April 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2373-2381
Abstract
We consider the performance of information propagation through social networks in a scenario where each user has a budget of attention, that is, a constraint on the frequency with which he pulls content from neighbors. In this context we ask the question “when users make selfish decisions on how to allocate their limited access frequency among neighbors, does information propagate efficiently?” For the metric of average propagation delay, we provide characterizations of the optimal social cost and the social cost under selfish user optimizations for various topologies of interest. Three situations may arise: well-connected topologies where delay is small even under selfish optimization; tree-like topologies where selfish optimization performs poorly while optimal social cost is low; and “stretched” topologies where even optimal social cost is high. We propose a mechanism for incentivizing users to modify their selfish behaviour, and observe its efficiency in the family of tree-like topologies mentioned above.Keywords
This publication has 9 references indexed in Scilit:
- Fast Information Spreading in Graphs with Large Weak Conductance2011
- Flooding in Weighted Random Graphs2011
- Optimal and scalable distribution of content updates over a mobile social network2009
- Rumor Spreading in Social Networks2009
- The structure of information pathways in a social communication network2008
- Algorithmic Game Theory2007
- Randomized rumor spreading2002
- One, Two and Three Times log n/n for Paths in a Complete Graph with Random WeightsCombinatorics, Probability and Computing, 1999
- On Spreading a RumorSIAM Journal on Applied Mathematics, 1987