Zhi Yang
Abstract
Kleinberg proposed a family of small-world networks to explain the navigability of large-scale real-world social networks. However, the underlying mechanism that drives real networks to be navigable is not yet well understood. In this article, we present a game theoretic model for the formation of navigable small-world networks. We model the network formation as a game called the Distance-Reciprocity Balanced (DRB) game in which people seek for both high reciprocity and long-distance relationships. We show that the game has only two Nash equilibria: One is the navigable small-world network, and the other is the random network in which each node connects with each other node with equal probability, and any other network state can reach the navigable small world via a sequence of best-response moves of nodes. We further show that the navigable small-world equilibrium is very stable—(a) no collusion of any size would benefit from deviating from it; and (b) after an arbitrary deviations of a large random set of nodes, the network would return to the navigable small world as soon as every node takes one best-response step. In contrast, for the random network, a small group collusion or random perturbations is guaranteed to bring the network out of the random-network equilibrium and move to the navigable network as soon as every node takes one best-response step. Moreover, we show that navigable small-world equilibrium has much better social welfare than the random network, and we provide the price-of-anarchy and price-of-stability results of the game. Our empirical evaluation further demonstrates that the system always converges to the navigable network even when limited or no information about other players’ strategies is available, and the DRB game simulated on real-world networks leads to navigability characteristic that is very close to that of the real networks, even though the real-world networks have non-uniform population distributions different from Kleinberg’s small-world model. Our theoretical and empirical analyses provide important new insight on the connection between distance, reciprocity, and navigability in social networks.
- Lada Adamic and Eytan Adar. 2005. How to search a social network. Social Netw. 27 (2005).Google Scholar
- K. Bhattacharya, G. Mukherjee, J. Saramäki, K. Kaski, and S. S. Manna. 2008. The international trade network: Weighted network analysis and modelling. J. Stat. Mech.: Theory Exp. 2 (2008), P02002.Google ScholarCross Ref
- M. Boguñá, D. Krioukov, and K. C. Claffy. 2009. Navigability of complex networks. Nature Phys. 5 (2009), 74--80.Google ScholarCross Ref
- Augustin Chaintreau, Pierre Fraigniaud, and Emmanuelle Lebhar. 2008. Networks become navigable as nodes move and forget. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP’08). Google ScholarDigital Library
- Wei Chen, Wenjie Fang, Guangda Hu, and Michael W. Mahoney. 2013. On the hyperbolicity of small-world and treelike random graphs. Internet Math. 9, 4 (2013), 434--491.Google ScholarCross Ref
- Eunjoon Cho, Seth A. Myers, and Jure Leskovec. 2011. Friendship and mobility: User movement in location-based social networks. In Proceedings of the Conference on Knowledge Discovery and Data (KDD’11). Google ScholarDigital Library
- Aaron Clauset and Cristopher Moore. 2003. How do networks become navigable. In Arxiv Preprint arXiv:0309.415v2.Google Scholar
- Ross Gittell and Avis Vidal. 1998. Community Organizing: Building Social Capital as a Development Strategy. Sage Publication.Google ScholarCross Ref
- Jacob Goldenberg and Moshe Levy. 2009. Distance is not dead: Social interaction and geographical distance in the internet era. In Arxiv preprint arXiv:0906.3202.Google Scholar
- Marta C. Gonzlez, Csar A. Hidalgo, and Albert-Lszl Barabsi. 2008. Understanding individual human mobility patterns. Nature (2008).Google Scholar
- Alvin Ward Gouldner. 1960. The norm of reciprocity: A preliminary statement. Amer. Sociol. Rev. 25, 4 (1960), 161--178.Google ScholarCross Ref
- Mark Granovetter. 1974. Getting a Job: A Study of Contacts and Careers. Harvard University Press.Google Scholar
- Mark S. Granovetter. 1973. The strength of weak ties. Amer. J. Sociol. (1973), 1360--1380.Google Scholar
- András Gulyás, József J. Bíró, Attila Korösi, Gábor Rétvári, and Dmitri Krioukov. 2015. Navigable networks as Nash equilibria of navigation games. Nature Commun. 6 (2015), 7651.Google ScholarCross Ref
- András Gulyás, Attila Korösi, Dávid Szabó, and Gergely Biczóki. 2012. On greedy network formation. SIGMETRICS Perform. Eval. Rev. (2012). Google ScholarDigital Library
- Yanqing Hu, Yougui Wang, Daqing Li, Shlomo Havlin, and Zengru Di. 2011. Possible origin of efficient navigation in small worlds. Phys. Rev. Lett. (2011).Google Scholar
- Johannes Illenberger, Kai Nagel, and Gunnar Fltterd. 2013. The role of spatial interaction in social networks. Netw. Spatial Econ. 13, 3 (2013), 255--282.Google ScholarCross Ref
- Matthew O. Jackson. 2004. A survey of models of network formation: Stability and Efficiency. In Group Formation in Economics: Networks, Clubs, and Coalitions. Cambridge University Press, Cambridge, UK, 11--57.Google Scholar
- Akshay Java, Xiaodan Song, Tim Finin, and Belle Tseng. 2007. Why we twitter: Understanding microblogging usage and communities. In Proceedings of the Workshop on Web Mining and Social Network Analyisis (WebKDD/SNA-KDD’07). Google ScholarDigital Library
- J. Jiang, C. Wilson, X. Wang, P. Huang, W. Sha, Y. Dai, and B. Y. Zhao. 2010. Understanding latent interactions in online social networks. In Proceedings of the Internet Measurement Conference (IMC’10). Google ScholarDigital Library
- Jon Kleinberg. 2002. The small-world phenomenon: An algorithmic perspective. In Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC’02). Google ScholarDigital Library
- Jon Kleinberg. 2006. Complex networks and decentralized search algorithms. In Proceedings of the International Congress of Mathematicians (ICM’06).Google Scholar
- Gautier Krings, Francesco Calabrese, Carlo Ratti, and Vincent D. Blondel. 2009. Urban gravity: A model for intercity telecommunication flows. J. Stat. Mech.-Theor. Exp. (2009).Google Scholar
- D. Krioukov, F. Papadopoulos, M. Kitsak, A. Vahdat, and M. Boguñá. 2010. Hyperbolic geometry of complex networks. Phys. Rev. E 82 (2010), 036106.Google ScholarCross Ref
- D. Krioukov, F. Papadopoulos, A. Vahdat, and M. Boguñá. 2009. Curvature and temperature of complex networks. Phys. Rev. E 80 (2009), 035101(R).Google ScholarCross Ref
- Renaud Lambiotte et al. 2008. Geographical dispersal of mobile communication networks. Physica A 387 (2008).Google Scholar
- David Liben-Nowell, Jasmine Novak, Ravi Kumar, Prabhakar Raghavan, and Andrew Tomkins. 2005. Geographic routing in social networks. Proc. Natl. Acad. Sci. U.S.A. 102 (2005).Google ScholarCross Ref
- Nisha Mathias and Venkatesh Gopal. 2001. Small worlds: How and why. Physical Review E 63, 2 (2001).Google ScholarCross Ref
- Stanley Milgram. 1967. The small world problem. Psychol. Today 2, 1 (1967), 60--67.Google Scholar
- Alan Mislove, Massimiliano Marcon, Krishna P. Gummadi, Peter Druschel, and Bobby Bhattacharjee. 2007. Measurement and analysis of online social networks. In Proceedings of the Internet Measurement Conference (IMC’07). Google ScholarDigital Library
- Fragkiskos Papadopoulos, Dmitri V. Krioukov, Marián Boguñá, and Amin Vahdat. 2010. Greedy forwarding in dynamic scale-free networks embedded in hyperbolic metric spaces. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM’10). Google ScholarDigital Library
- Oskar Sandberg and Ian Clarke. 2006. The evolution of navigable small-world networks. In Arxiv Preprint arXiv:cs/0607025.Google Scholar
- Mark Schaller and Bibb Latank. 1995. Distance matters: Physical space and social impact. Personal. Soc. Psychol. Bull. 21 (1995), 795--805.Google ScholarCross Ref
- Éva Tardos and Tom Wexler. 2007. Network formation games and the potential function method. In Algorithmic Game Theory. Cambridge University Press.Google Scholar
- Duncan J. Watts and Steven H. Strogatz. 1998. Collective dynamics of ‘small-world’ networks. Nature 393, 6684 (1998), 440--442.Google Scholar
- Zhi Yang, Christo Wilson, Xiao Wang, Tingting Gao, Ben Y. Zhao, and Yafei Dai. 2011. Uncovering social network sybils in the wild. In Proceedings of the Internet Measurement Conference (IMC’11). Google ScholarDigital Library
- Kai Zhao, Mirco Musolesi, Pan Hui, Weixiong Rao, and Sasu Tarkoma. 2015. Explaining the power-law distribution of human mobility through transportation modality decomposition. Sci. Rep. (2015).Google Scholar
Index Terms
- A Game Theoretic Model for the Formation of Navigable Small-World Networks—The Tradeoff between Distance and Reciprocity
Recommendations
A Game Theoretic Model for the Formation of Navigable Small-World Networks
WWW '15: Proceedings of the 24th International Conference on World Wide WebKleinberg proposed a family of small-world networks to explain the navigability of large-scale real-world social networks. However, the underlying mechanism that drives real networks to be navigable is not yet well understood. In this paper, we present ...
Invulnerability analysis of scale-free network and small-world network
AI2A '23: Proceedings of the 2023 3rd International Conference on Artificial Intelligence, Automation and AlgorithmsThis paper analyzes the invulnerability of two kinds of networks with different degrees of distribution. According to their topology, four attack strategies and two metrics were selected. The most effective attack strategy and the most appropriate ...
A Self-Stabilization Process for Small-World Networks
IPDPS '12: Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing SymposiumSmall-world networks have received significant attention because of their potential as models for the interaction networks of complex systems. Specifically, neither random networks nor regular lattices seem to be an adequate framework within which to ...
Comments