* [63] Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, and Hao Yang.  Dynamic Graph Representation Learning via Self-Attention Networks.  arXiv preprint arXiv:1812.09430, 2018.
  * [64] Wenchao Yu, Wei Cheng, Charu C Aggarwal, Haifeng Chen, and Wei Wang.  Link Prediction with Spatial and Temporal Consistency in Dynamic Networks.  In IJCAI, pages 3343–3349, 2017.
  * [65] G. W. Stewart.  Matrix Perturbation Theory, 1990.
  * [66] Evrim Acar and Bülent Yener.  Unsupervised Multiway Data Analysis: A Literature Survey.  IEEE Trans Knowl Data Eng, 21(1):6–20, 2008.
  * [67] Dimitrios Rafailidis and Alexandros Nanopoulos.  Modeling the Dynamics of User Preferences in Coupled Tensor Factorization.  In Proceedings of the 8th ACM Conference on Recommender systems, pages 321–324. ACM, 2014.
  * [68] Xiaomin Fang, Rong Pan, Guoxiang Cao, Xiuqiang He, and Wenyuan Dai.  Personalized Tag Recommendation through Nonlinear Tensor Factorization using Gaussian Kernel.  In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015\.
  * [69] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini.  The Graph Neural Network Model.  IEEE Transactions on Neural Networks, 20(1):61–80, 2008.
  * [70] Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov.  Learning Convolutional Neural Networks for Graphs.  In International Conference on Machine Learning, pages 2014–2023, 2016.
  * [71] Daixin Wang, Peng Cui, and Wenwu Zhu.  Structural Deep Network Embedding.  In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1225–1234. ACM, 2016.
  * [72] Jinyin Chen, Xuanheng Xu, Yangyang Wu, and Haibin Zheng.  GC-LSTM: Graph Convolution Embedded LSTM for Dynamic Link Prediction.  arXiv preprint arXiv:1812.04206, 2018.
  * [73] Sepp Hochreiter and Jürgen Schmidhuber.  Long Short-Term Memory.  Neural Computation, 9(8):1735–1780, 1997.
  * [74] Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio.  Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation.  arXiv preprint arXiv:1406.1078, 2014.
  * [75] Jinyin Chen, Jian Zhang, Xuanheng Xu, Chenbo Fu, Dan Zhang, Qingpeng Zhang, and Qi Xuan.  E-LSTM-D: A Deep Learning Framework for Dynamic Network Link Prediction.  IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2019\.
  * [76] Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel.  Gated Graph Sequence Neural Networks.  arXiv preprint arXiv:1511.05493, 2015.
  * [77] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio.  Neural Machine Translation by Jointly Learning to Align and Translate.  arXiv preprint arXiv:1409.0473, 2014.
  * [78] Dongkuan Xu, Wei Cheng, Dongsheng Luo, Xiao Liu, and Xiang Zhang.  Spatio-Temporal Attentive RNN for Node Classification in Temporal Attributed Graphs.  In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 3947–3953. AAAI Press, 2019.
  * [79] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  ImageNet Classification with Deep Convolutional Neural Networks.  In Advances in Neural Information Processing Systems, pages 1097–1105, 2012.
  * [80] Thomas N Kipf and Max Welling.  Semi-Supervised Classification with Graph Convolutional Networks.  arXiv preprint arXiv:1609.02907, 2016.
  * [81] Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive Representation Learning on Large Graphs.  In Advances in Neural Information Processing Systems, pages 1024–1034, 2017.
  * [82] Yuyang Gao, Lingfei Wu, Houman Homayoun, and Liang Zhao.  DynGraph2Seq: Dynamic-Graph-to-Sequence Interpretable Learning for Health Stage Prediction in Online Health Forums.  In IEEE ICDM, pages 1042–1047, 2019.
  * [83] Stephen Bonner, John Brennan, Ibad Kureshi, Georgios Theodoropoulos, Andrew Stephen McGough, and Boguslaw Obara.  Temporal Graph Offset Reconstruction: Towards Temporally Robust Graph Representation Learning.  In 2018 IEEE International Conference on Big Data (Big Data), pages 3737–3746. IEEE, 2018.
  * [84] Ling Zhao, Yujiao Song, Chao Zhang, Yu Liu, Pu Wang, Tao Lin, Min Deng, and Haifeng Li.  T-GCN: A Temporal Graph Convolutional Network for Traffic Prediction.  IEEE Transactions on Intelligent Transportation Systems, 2019.
  * [85] Yun Xiong, Yao Zhang, Hanjie Fu, Wei Wang, Yangyong Zhu, and S Yu Philip.  DynGraphGAN: Dynamic Graph Embedding via Generative Adversarial Networks.  In International Conference on Database Systems for Advanced Applications, pages 536–552. Springer, 2019.
  * [86] Diederik P Kingma and Max Welling.  Auto-Encoding Variational Bayes.  arXiv preprint arXiv:1312.6114, 2013.
  * [87] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative Adversarial Nets.  In Advances in Neural Information Processing Systems, pages 2672–2680, 2014.
  * [88] Thomas N Kipf and Max Welling.  Variational Graph Auto-Encoders.  arXiv preprint arXiv:1611.07308, 2016.
  * [89] Hongwei Wang, Jia Wang, Jialin Wang, Miao Zhao, Weinan Zhang, Fuzheng Zhang, Xing Xie, and Minyi Guo.  GraphGAN: Graph Representation Learning with Generative Adversarial Nets.  In Thirty-Second AAAI Conference on Artificial Intelligence, 2018\.
  * [90] Stephen Bonner, Amir Atapour-Abarghouei, Philip T Jackson, John Brennan, Ibad Kureshi, Georgios Theodoropoulos, Andrew Stephen McGough, and Boguslaw Obara.  Temporal Neighbourhood Aggregation: Predicting Future Links in Temporal Graphs via Recurrent Variational Graph Convolutions.  In 2019 IEEE International Conference on Big Data (Big Data), pages 5336–5345. IEEE, 2019.
  * [91] Yifeng Zhao, Xiangwei Wang, Hongxia Yang, Le Song, and Jie Tang.  Large Scale Evolving Graphs with Burst Detection.  In 28th International Joint Conference on Artificial Intelligence (IJCAI), 2019.
  * [92] Ehsan Hajiramezanali, Arman Hasanzadeh, Krishna Narayanan, Nick Duffield, Mingyuan Zhou, and Xiaoning Qian.  Variational Graph Recurrent Neural Networks.  In Advances in Neural Information Processing Systems, pages 10700–10710, 2019.
  * [93] Yao Ma, Ziyi Guo, Zhaocun Ren, Jiliang Tang, and Dawei Yin.  Streaming Graph Neural Networks.  In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 719–728, 2020.
  * [94] Dongkuan Xu, Wei Cheng, Dongsheng Luo, Yameng Gu, Xiao Liu, Jingchao Ni, Bo Zong, Haifeng Chen, and Xiang Zhang.  Adaptive Neural Network for Node Classification in Dynamic Networks.  In 2019 IEEE International Conference on Data Mining (ICDM), pages 1402–1407. IEEE, 2019.
  * [95] Dongkuan Xu, Junjie Liang, Wei Cheng, Hua Wei, Haifeng Chen, and Xiang Zhang.  Transformer-Style Relational Reasoning with Dynamic Memory Updating for Temporal Network Modeling.  In Proceedings of the AAAI Conference on Artificial Intelligence, pages 4546–4554, 2021.
  * [96] Hogun Park and Jennifer Neville.  Exploiting Interaction Links for Node classification with deep graph neural networks.  In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 3223–3230. AAAI Press, 2019.
  * [97] Prasha Shrestha, Suraj Maharjan, Dustin Arendt, and Svitlana Volkova.  Learning from Dynamic User Interaction Graphs to Forecast Diverse Social Behavior.  In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pages 2033–2042. ACM, 2019.
  * [98] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean.  Efficient Estimation of Word Representations in Vector Space.  arXiv preprint arXiv:1301.3781, 2013.
  * [99] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean.  Distributed Representations of Words and Phrases and their Compositionality.  In Advances in Neural Information Processing Systems, pages 3111–3119, 2013.
  * [100] Sam De Winter, Tim Decuypere, Sandra Mitrović, Bart Baesens, and Jochen De Weerdt.  Combining Temporal Aspects of Dynamic Networks with Node2Vec for a More Efficient Dynamic Link Prediction.  In 2018 IEEE/ACM ASONAM, pages 1234–1241. IEEE, 2018.
  * [101] Uriel Singer, Ido Guy, and Kira Radinsky.  Node embedding over temporal graphs.  In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pages 4605–4612. International Joint Conferences on Artificial Intelligence Organization, 7 2019\.
  * [102] Sedigheh Mahdavi, Shima Khoshraftar, and Aijun An.  dynnode2vec: Scalable dynamic network embedding.  In 2018 IEEE International Conference on Big Data (Big Data), pages 3762–3765. IEEE, 2018.
  * [103] Robert Bamler and Stephan Mandt.  Dynamic Word Embeddings.  arXiv preprint arXiv:1702.08359, 2017.
  * [104] Farzaneh Heidari and Manos Papagelis.  EvoNRL: Evolving Network Representation Learning Based on Random Walks.  In International Conference on Complex Networks and their Applications, pages 457–469. Springer, 2018.
  * [105] Hooman Peiro Sajjad, Andrew Docherty, and Yuriy Tyshetskiy.  Efficient Representation Learning using Random Walks for Dynamic Graphs.  arXiv preprint arXiv:1901.01346, 2019.
  * [106] Wenchao Yu, Wei Cheng, Charu C Aggarwal, Kai Zhang, Haifeng Chen, and Wei Wang.  NetWalk: A Flexible Deep Embedding Approach for Anomaly Detection in Dynamic Networks.  In Proceedings of the 24th ACM SIGKDD Int. Conference on Knowledge Discovery & Data Mining, pages 2672–2681, 2018.
  * [107] Supriya Pandhre, Himangi Mittal, Manish Gupta, and Vineeth N Balasubramanian.  STWalk: Learning Trajectory Representations in Temporal Graphs.  In Proceedings of the ACM India Joint International Conference on Data Science and Management of Data, pages 210–219. ACM, 2018.
  * [108] Shima Khoshraftar, Sedigheh Mahdavi, Aijun An, Yonggang Hu, and Junfeng Liu.  Dynamic Graph Embedding via LSTM History Tracking.  In 2019 IEEE International Conference on Data Science and Advanced Analytics (DSAA), pages 119–127. IEEE, 2019.
  * [109] Zhitao Wang, Chengyao Chen, and Wenjie Li.  Attention network for information diffusion prediction.  In Companion Proceedings of the The Web Conference 2018, pages 65–66, 2018.
  * [110] Jia Wang, Vincent W Zheng, Zemin Liu, and Kevin Chen-Chuan Chang.  Topological Recurrent Neural Network for Diffusion Prediction.  In IEEE ICDM, pages 475–484, 2017.
  * [111] Cheng Yang, Jian Tang, Maosong Sun, Ganqu Cui, and Zhiyuan Liu.  Multi-Scale Information Diffusion Prediction with Reinforced Recurrent Networks.  In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 4033–4039. AAAI Press, 2019.
  * [112] Koya Sato, Mizuki Oka, Alain Barrat, and Ciro Cattuto.  DyANE: Dynamics-Aware Node Embedding for Temporal Networks.  arXiv preprint arXiv:1909.05976, 2019.
  * [113] Ferenc Béres, Domokos M Kelen, Róbert Pálovics, and András A Benczúr.  Node Embeddings in Dynamic Graphs.  Applied Network Science, 4(1):64, 2019.
  * [114] Zhining Liu, Dawei Zhou, and Jingrui He.  Towards Explainable Representation of Time-Evolving Graphs via Spatial-Temporal Graph Attention Networks.  In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pages 2137–2140. ACM, 2019.
  * [115] Tianxing Wu, Arijit Khan, Huan Gao, and Cheng Li.  Efficiently Embedding Dynamic Knowledge Graphs.  arXiv preprint arXiv:1910.06708, 2019.
  * [116] Tingsong Jiang, Tianyu Liu, Tao Ge, Lei Sha, Sujian Li, Baobao Chang, and Zhifang Sui.  Encoding Temporal Information for Time-Aware Link Prediction.  In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 2350–2354, 2016.
  * [117] Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko.  Translating Embeddings for Modeling Multi-Relational Data.  In Advances in Neural Information Processing Systems, pages 2787–2795, 2013.
  * [118] Omer Levy and Yoav Goldberg.  Neural Word Embedding as Implicit Matrix Factorization.  In Advances in Neural Information Processing Systems, pages 2177–2185, 2014.
  * [119] Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei.  LINE: Large-Scale Information Network Embedding.  In Proceedings of the 24th International Conference on World Wide Web, pages 1067–1077. International World Wide Web Conferences Steering Committee, 2015.
  * [120] Xin Liu, Tsuyoshi Murata, Kyoung-Sook Kim, Chatchawan Kotarasu, and Chenyi Zhuang.  A General View for Network Embedding as Matrix Factorization.  In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pages 375–383. ACM, 2019.
  * [121] Mahmudur Rahman, Tanay Kumar Saha, Mohammad Al Hasan, Kevin S Xu, and Chandan K Reddy.  DyLink2Vec: Effective Feature Representation for Link Prediction in Dynamic Networks.  arXiv preprint arXiv:1804.05755, 2018.
  * [122] Yuanfu Lu, Xiao Wang, Chuan Shi, Philip S Yu, and Yanfang Ye.  Temporal Network Embedding with Micro-and Macro-dynamics.  In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pages 469–478. ACM, 2019.
  * [123] Ying Yin, Jianpeng Zhang, Yulong Pei, Xiaotao Cheng, and Lixin Ji.  MHDNE: Network Embedding Based on Multivariate Hawkes Process.  In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 409–421. Springer, 2019.
  * [124] Ryan A Rossi.  Relational Time Series Forecasting.  The Knowledge Engineering Review, 33, 2018.
  * [125] Yulong Pei, Jianpeng Zhang, GH Fletcher, and Mykola Pechenizkiy.  Node Classification in Dynamic Social Networks.  Proceedings of AALTD, page 54, 2016.
  * [126] Ruthwik R Junuthula, Kevin S Xu, and Vijay K Devabhaktuni.  Evaluating link prediction accuracy in dynamic networks with added and removed edges.  In 2016 IEEE international conferences on big data and cloud computing (BDCloud), social computing and networking (SocialCom), sustainable computing and communications (SustainCom)(BDCloud-SocialCom-SustainCom), pages 377–384. IEEE, 2016.
  * [127] Sylvain Lamprier.  A Variational Topological Neural Model for Cascade-based Diffusion in Networks.  arXiv preprint arXiv:1812.10962, 2018.
  * [128] Yuan Zhang, Tianshu Lyu, and Yan Zhang.  COSINE: Community-Preserving Social Network Embedding from Information Diffusion Cascades.  In Thirty-Second AAAI Conference on Artificial Intelligence, 2018\.
  * [129] Laurens van der Maaten and Geoffrey Hinton.  Visualizing Data using t-sne.  Journal of Machine Learning Research, 9(Nov):2579–2605, 2008.
  * [130] Palash Goyal, Sujit Rokka Chhetri, Ninareh Mehrabi, Emilio Ferrara, and Arquimedes Canedo.  DynamicGEM: A Library for Dynamic Graph Embedding Methods.  arXiv preprint arXiv:1811.10734, 2018.
  * [131] Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao.  Hypergraph Neural Networks.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3558–3565, 2019.
  * [132] Zizhao Zhang, Haojie Lin, Yue Gao, and KLISS BNRist.  Dynamic Hypergraph Structure Learning.  In IJCAI, pages 3162–3169, 2018.
  * [133] Xiaodong Cheng, Yu Kawano, and Jacquelien MA Scherpen.  Graph Structure-Preserving Model Reduction of Linear Network Systems.  In 2016 European Control Conference (ECC), pages 1970–1975. IEEE, 2016.


††thanks: These Authors equally contributed to the Manuscript††thanks: These
Authors equally contributed to the Manuscript

###### Abstract

A wealth of evidence shows that real world networks are endowed with the
small-world property i.e., that the maximal distance between any two of their
nodes scales logarithmically rather than linearly with their size. In
addition, most social networks are organized so that no individual is more
than six connections apart from any other, an empirical regularity known as
the six degrees of separation. Why social networks have this ultra-small world
organization, whereby the graph’s diameter is independent of the network size
over several orders of magnitude, is still unknown. We show that the ‘six
degrees of separation’ are the property featured by the equilibrium state of
any network where individuals weigh between their aspiration to improve their
centrality and the costs incurred in forming and maintaining connections. We
show, moreover, that the emergence of such a regularity is compatible with all
other features, such as clustering and scale-freeness, that normally
characterize the structure of social networks. Thus, our results show how
simple evolutionary rules of the kind traditionally associated with human
cooperation and altruism can also account for the emergence of one of the most
intriguing attributes of social networks.

††preprint: APS/123-QED

In the short story ”Chains” (1929), the Hungarian writer Frigyes Karinthy
described a game where a group of people was discussing how the members of the
human society were closer together than ever before. To prove this point, one
participant proposes that any person out of the entire Earth population
(around 1.8 billion at that time) could be reached using nothing except each
personal network of acquaintances, betting that the resulting chain would be
of no more than five individuals. The story coined the expression ‘six degrees
of separation’ to reflect the idea that all people of the world are six or
fewer social connections apart from each other. The concept was later
generalized to that of ‘small world’ networks, where the maximal social
distance (the diameter of the network) scales logarithmically, rather than
linearly, with the size of the population watts .

After early studies on the structure of social networks by Michael Gurevich
gure  and Manfred Kochen koch , Stanley Milgram performed his 1967 famous set
of experiments on social distancing milgram ; milgram2  where, with a limited
sample of a thousand individuals, it was shown that people in the United
States are indeed connected by a small number of acquaintances. Later on,
Duncan Watts recreated Milgram’s experiments with Internet email users dodds
by tracking 24,163 chains aimed at 18 targets from 13 countries and confirmed
that the average number of steps in the chains was around six. Furthermore,
many experiments conducted at a planetary scale on various social networks
verified the ubiquitous character of this feature: i) a 2007 study by Jure
Leskovec and Eric Horvitz (with a data set of 30 billion conversations among
240 million Microsoft Messenger users) revealed the average path length to be
6 lesko ; lesko2 , ii) the average degree of separation between two randomly
selected Twitter users was found to be 3.435 bakhsh , and iii) the Facebook’s
network in 2011 (721 million users with 69 billion friendship links) displayed
an average distance between nodes of 4.74 facebook .

Such abundant and consistent evidence points to the fact that the structure of
these networks radically differs from either that of regular networks (where
the diameter scales linearly with the size) and that of classical small-world
networks (where, instead, the scaling law is logarithmic) watts . A clear
explanation of the mechanisms through which social networks organize into
ultra-small world states (where the diameter does not depend on the system
size over several orders of magnitude) is, however, still missing. Why does
such a collective property emerge? What are its fundamental mechanisms? Why is
the common shortest path length between units of a social network six, rather
than five or seven or any other number, implying an average distance which is
also not far from six?

We here answer these questions in exact terms, by adopting a game theoretical
approach for describing the network evolution, a line of studies which started
almost five decades ago by Myerson myerson1977graphs  analyzing cooperation
structures in a wide class of games. A couple of decades later, games on
adaptive networks were introduced, for instance by Jackson and Wolinsky
jackson1996strategic , with the purpose of studying the stability and
efficiency of social and economic networks when self-interested individuals
could form or sever links with others. Further on, the influential work by
Nowak and May nowak_n92b  showed how spatial structure could provide an
evolutionary escape hatch for cooperation in social dilemmas. Co-evolutionary
networks have then been considered in a series of works where players could
improve their topological position, for example by cutting links to defectors
or rewiring their links to gain larger payoffs ebel2002coevolutionary ;
zimmermann_pre04 ; zimmermann_pre05 ; pacheco_prl06 ; gomez-gardenes_prl07 ;
gross_jrsi08 . Related research also covered game theoretical models as the
basis for cooperation on networks ohtsuki_n06 , for network formation and
growth goyal2005network ; bloch2007formation ; poncela_njp09 ; bei2011bounded
, as well as for agents to achieve a position of high centrality while
minimizing the number of contacts they have to maintain holme_prl06 .

So far, the few available studies on ultra-small world states have focused on
finding the relationship between the scaling properties of distances in a
graph and those of the node’s degree distribution. It was indeed proved that
scale-free networks with degree distribution $p(k)\sim k^{-\gamma}$ and
$2<\gamma<3$ (as it is observed in all real-world networks) display a scaling
of the diameter as $D\sim\ln\ln N$ cohen2003 , which departs from the classic
logarithmic scaling of small-world networks and yet maintains an explicit
dependence on the network size $N$. On the other hand, scale-free networks
featuring an asymptotically invariant shortest path (called Mandala networks
mandala ) may be synthesized, which however have an associated value of
$\gamma$ strictly equal to 2 and therefore do not match any case observed in
real world.

Rather than being dependent on global (i.e., degree distribution) scaling
properties, in this Article we show that the mechanism behind such observed
regularity can be found, instead, in a dynamic evolution of the network.
Precisely, we rigourously show that, when a simple compensation rule between
the cost incurred by nodes in maintaining connections and the benefit accrued
by the chosen links is governing the evolution of a network, the asymptotic
equilibrium state (a Nash equilibrium where no further actions would produce
more benefit than cost nash_pnas50 ), features a diameter which does not
depend on the system’s size, and is equal to 6. In other words, we
theorematically prove that any network where nodes strive to increase their
centrality by forming connections if and only if their cost is smaller than
the payoff tends to evolve into an ultra-small world state endowed with the
’six degree of separation’ property, irrespective of its initial structure.
Our study points out, therefore, that evolutionary rules of the kind
traditionally associated with human cooperation and altruism novak ; rand1 ;
rand2 ; fu1 ; fu2  can in fact account also for the emergence of this
attribute of social networks. Furthermore, we show that such a global network
feature can emerge even from situations where individuals have access to only
partial information on the overall structure of connections, which is indeed
the case in almost all social networks.

##  I Results

###  I.1 A game theoretical model for network evolution

Consider the general case which is schematically depicted in Figure 1, where
the $N$ nodes of a network $V$ are rational agents of a game. At each step $m$
of the game, each agent $v\in V$ selects (independently of the choices made by
the other agents at the same step) a potential neighborhood ${\cal N}_{v}(m)$
made of $k_{v}(m)$ other nodes of $V$. The agent then decides whether it is
more profitable to form connections with the nodes in ${\cal N}_{v}(m)$ or to
remain connected with the nodes in ${\cal N}_{v}(m-1)$. The decision is based
on a balance between the payoff and the cost functions associated with the
change of neighborhood.

As for the cost function, we assume that node $v$ pays a unitary cost $c>0$ to
maintain a connection with each node $u$ belonging to its neighborhood (and
that node $u$ cannot refuse the connection paid for by $v$). Moreover, to be
as generic as possible, we either assume the unitary cost to be a constant, or
to depend on the network size as $c=c(N)$.

Figure 1: The game theoretical framework. The structure of a social network
evolves following simple rules of a game. Panel a: At each step of the game,
the individuals forming part of the network (like the red woman in the
picture) have to decide whether to stay with the neighborhood formed by their
actual friends, or to change to another neighborhood formed by potential new
friends. The current and new neighborhoods may overlap (in our picture, the
blue man and the yellow woman are members of both sets). The decision is based
on a careful evaluation of the cost incurred and of the benefit gained with
the change. Panel b: The decision is merely utilitarian. If the benefit is not
overcoming the cost, then individuals maintain their current neighborhood
(left picture). If, on the contrary, the payoff exceeds the cost, then
individuals relinquish their current neighborhood and move to the new one
(right picture). The structure of the network then evolves until converging to
its Nash equilibrium (if it exists) i.e., to the configuration where no
changes of neighborhood are allowed, as no individual has anything to gain in
abandoning acquaintances. Figure 2: $l$-independence of nodes. Sketch of a
generic graph, with node A at the center. The first, second and third
neighbors of node A are respectively located within the yellow, pink, and gray
region. The $l$-independent set of a graph is the set of nodes such that the
distance between any two of them is larger than $l$. The black nodes (A, B, C
and D) form the 2-independent set of the graph, as all of them are at a
distance larger than 2 from each other. The black nodes together with the ones
depicted in light blue form, instead, the 1-independent set. Note that the
light blue nodes do not participate in the 2-independent set. Finally, the red
nodes belong neither to the 1-independent set nor to the 2-independent set.

As for the benefit function, if agents are rational, it is logical to assume
that their goal is to increase their importance within the network. This can
be naturally framed in terms of betweenness centrality freeman , which indeed
provides a measure of the influence exerted by a node on the information flow
within a network. This is defined as follows. First of all, if $v$ and $s$ are
two nodes of a connected network, the distance $l(v,s)$ is taken to be the
number of edges forming the shortest path between them. Then, the betweenness
centrality (or degree of mediation) $BC(v)$ is taken to be $\sum_{s\neq v\neq
t}\frac{\sigma_{st}(v)}{\sigma_{st}}$, where $s,t\in V$ are all possible pairs
of different vertices that do not match with $v$, $\sigma_{st}(v)$ is the
number of shortest paths between the vertices $s$ and $t$ passing through the
vertex $v$, and $\sigma_{st}$ is the total number of shortest paths between
the vertices $s$ and $t$.

$BC(v)$ quantifies how relevant the intermediary role played by $v$ in the
graph is. However, one immediately realizes that the contribution in $BC(v)$
of the shortest paths in which $v$ is the unique intermediary between $s$ and
$t$ is equal to that of paths in which $v$ is just one of a long chain of
intermediaries. To account for such a difference, one may adopt a generic
weighted version of the betweenness centrality, $WBC(v)$, which is defined as

$WBC(v)=\sum_{s\neq v\neq t}\frac{\sigma_{st}(v)}{\sigma_{st}}\cdot
f(l(s,t)),$ (1)

where $f$ is a strictly decreasing function of its argument (as longer paths
must contribute less). One can think of Eq. (1) as follows: each pair $s,t$ of
vertices creates some utility, which is then distributed equally among all
shortest paths from $s$ to $t$, and then each intermediary vertex in each path
obtains a fraction equal to $\frac{f(l(s,t))}{\sigma_{st}}$.

With these simple rules in mind, the $N$ agents play the game. When the game
converges to a Nash equilibrium (a configuration where no agent has anything
to gain by changing its own neighborhood, as all of them have already attained
their optimal adjacency), we can demonstrate rigorously that the obtained
structure is endowed with the six degrees of separation attribute.

###  I.2 2-independent sets and the emergence of ultra-small world states

Before we demonstrate our main results, we first need to introduce the concept
of 2-independence of network’s nodes. In traditional graph theory, a
1-independent set (or internally stable set, or anti-clique) $S$ is a set of
vertices such that any pair of them isn’t connected by a graph’s edge. This is
to say that each edge in the graph has at most one endpoint in $S$. As a
consequence, any two vertices of $S$ are at a distance which is strictly
larger than one.

One can now generalize the latter definition, and designate as a
$l$-independent set $S_{l}$ the set of network’s nodes such that the distance
between any pair of its members is larger than $l$ fink1985 . It follows that
nodes belonging to $S_{l}$ do not necessarily belong to $S_{l+1}$ (see Fig. 2
for an illustrative sketch of the comparison between a 2-independent set and a
classical 1-independent set).

Why are 2-independent sets important in our framework? This can be understood
by looking at Fig. 3. In panel a, the three vertices 1,2,7 are originally part
of a 1-independent set. Now, if vertex 7 forms the yellow edges $(7,1)$ and
$(7,2)$, it is removed from the set but it does not change the distance
between nodes 1 and 2. It only contributes to the multiplicity of shortest
paths between nodes 1 and 2. As the number of alternative shortest paths may
be very large in large sized networks, the minimum possible benefit obtained
from gluing a 1-independent set (as node 7 would do by forming edges with
nodes 1 and 2) may be very small with the growth of the network’s size. From
the latter point it follows that the presence of independent sets of large
size may be compatible with the Nash equilibrium.

A totally different situation occurs when we consider 2-independent sets, as
in panel b of Fig. 3. Indeed, when forming the yellow connections with nodes 1
and 2, vertex 7 is actually reducing their distance from at least 3 down to 2.
Therefore, regardless of which other edge exists in the network involving
vertices 1 and 2, vertex 7 receives a minimum benefit equal to $f(2)$. This is
equally valid for any other vertex of the 2-independent set which would form
edges with all other members of the set: it would receive at least the same
benefit from each pair of nodes in the set. Therefore, the minimal benefit
obtained from gluing a 2-independence set of size $x$ is ${x-1\choose 2}f(2)$,
which may be rather substantial. For this reason, sizeable 2-independent sets
cannot exist in the Nash equilibrium.

The process of gluing large size 2-independence sets is precisely what
regulates the spontaneous emergence of the six degrees of separation. Namely,
it can be proved theorematically that such a process determines that

  * i)

at the Nash equilibrium the graph necessarily contains at least a vertex $v$
whose degree $k$ scales as the cube root of the system’s size i.e.,
$k\sim\sqrt[3]{N}$, and

  * ii)

node $v$ is at the center of the network and displays the remarkable property
of being at a distance of no more than 3 from any other node of the graph.

The latter implies that the shortest path between any pair of nodes $i,j$ in
the graph will be smaller or equal than 6, as there will be maximum 3 edges
forming the shortest path from $i$ to $v$ and maximum three edges also to form
the shortest path from $v$ to $j$. Therefore, the diameter $D$ of the network
will be exactly 6.

The proofs of the Theorems and Lemmas involved are available in the
Supplementary Information Appendix (SI).

Figure 3: Independence of nodes and Nash equilibrium. Panel a: When only black
links are considered, vertices 1,2,7 form a 1-independent set. For consistency
with Fig. 2, nodes 1 and 2 are colored in light blue. As vertex 7 forms the
yellow edges (7,1) and (7,2) it is removed from the 1-independent set (this
change is depicted by coloring the lowest part of the node in yellow), but the
two new connections do not remove nodes 1 and 2 from the 1-independent set,
since they only contribute to the multiplicity of the shortest paths between 1
and 2. Panel b: When only black links are considered, vertices 1,2,7 form a
2-independent set. As the yellow connections are formed, vertex 7 reduces the
distance between nodes 1 and 2 from at least 3 down to 2. As a consequence,
nodes 1 and 2 can only be part of a 1-independent set. For this reason, the
upper half of nodes 1 and 2 is depicted in black, indicating that these nodes
initially belonged to the 2-independent set, and the lower half in light blue,
indicating that by receiving the connections from node 7, they become members
of a 1-independent set. Node 7 is half colored in black (as it initially
belonged to the 2-independent set), and half in yellow (as the two new
connections remove it from all independent sets).

###  I.3 An illustrative case

For the sake of a better illustration , let us now focus on the case described
as follows.

  * i)

The agents start the game when they are already connected by means of a
pristine graph where, in addition, there exists at least one node with
sufficiently high degree.

  * ii)

Each agent $v$ adopts as benefit function

$WBC(v)=\sum_{s\neq v\neq
t}\frac{\sigma_{st}(v)}{\sigma_{st}}\cdot\frac{1}{l(s,t)^{\alpha}},$ (2)

with $\alpha$ being a strictly positive parameter. Comparing with Eq. (1),
this means that the weighting factor is $f(l(s,t))=\frac{1}{l(s,t)^{\alpha}}$,
and that Eq. (2) coincides, for $\alpha=1$, with the classical weighted
betweenness centrality freeman .

  * iii)

Agents sequentially add new connections to their neighborhood if and only if
there is a positive balance between the extra-utility brought by the new
connections and the extra-cost.

In practice, at each step $m$ of the game, the potential neighborhood ${\cal
N}_{v}(m)$ of each agent $v\in V$ is equal to ${\cal N}_{v}(m-1)$ plus $p$
other nodes. The $p$ new edges are then added only if $\Delta WBC(v)\geq pc$
i.e., only if the extra weighted betweenness centrality is larger or equal to
the extra cost $pc$.

When no agent is able to incorporate any further edge, the network is said to
have reached its asymptotic equilibrium. It should be remarked that such a
final state cannot formally be associated to a Nash equilibrium, because the
option of removing existing links is not contemplated in the game, and
therefore there is no certainty that agents, in their asymptotic states, are
in their optimal adjacency configuration. In this respect, it is worth
highlighting that another mechanism (beyond that of link addition and
deletion) that one can consider at the basis of the emergence of the six
degrees of separation is that of link rewiring, which would actually imply the
invariance of the network density during its evolution towards the asymptotic
equilibrium. We plan to report on the effects of this latter mechanism
elsewhere.

The following Theorem can be proved:

  * i)

if $v$ is a node of the pristine graph with $k$ original connections, and

  * ii)

if $H\in\left\\{3,4,5,...\right\\}$ is some integer number strictly larger
than 2, and

  * iii)

if, for the considered values of $c$ and $\alpha$, the inequality

$\left(\frac{1}{2^{\alpha}}-\frac{1}{(H+2)^{\alpha}}\right)k\geq c,$ (3)

is satisfied,

then, in the equilibrium state of the network, the node $v$ is linked to all
other nodes of the graph by no more than $H$ links, implying that the diameter
of the equilibrium network does not exceed $2H$.

In practice, the theorem guarantees that the asymptotic state of a network
evolving from an initial condition that satisfies condition (3) is an ultra-
small world state (and, for $H=3$, also the emergence of the 6 degrees of
separation property).

Figure 4: The emergence of the ultra-small world state. Panel a: Sketch of a
hypothetical network where nodes $v$ and $u$ are separated by a distance
$H+1$. The neighbors of $v$ are then at either $H$ (the light blue node), or
$H+1$ (the green node $s$), or $H+2$ (the red nodes) edges from $u$. For a
better visualization, paths of different lengths are marked with the
corresponding colors. Panel b: A direct (yellow) link is added between $v$ and
$u$. Our study demonstrates rigorously (see Theorem 3 of the SI) that the
network configuration of panel a is incompatible with an equilibrium state.
Notice that, at variance with the case depicted in Fig. 2, here distances
between nodes depend on the value of the parameter $H$.

The proof of the Theorem (see SI for details) is given by contradiction i.e.,
by supposing that there is a node $u$ in the final state of the network whose
distance from $v$ is at least $H+1$ i.e., $l(u,v)\geq H+1$. To better
illustrate the situation, we depicted in panel a of Fig. 4 the case in which
nodes $v$ and $u$ are separated by a distance $H+1$. In that circumstance, the
nodes directly connected to $v$ (the neighbors of $v$) may be found at either
$H$ (the light blue node), or $H+1$ (the green node), or $H+2$ (the red nodes)
edges from $u$. Looking at the figure, it is easy to understand that all
network’s shortest paths which end in $u$ and start in either the green or the
light blue node cannot pass through $v$. Therefore, the only contribution to
the benefit function of $v$ from shortest paths ending in $u$ is coming from
those paths which start in the red nodes, the neighbors of $v$ that are at
distance $H+2$ from $u$.

When one, instead, includes a direct link between $v$ and $u$ [the yellow link
in panel b of Fig. 4], then the shortest path between any neighbor of $v$
(denoted by $w$) and $u$ becomes $w-v-u$, since $H\geq 3$. Calculating then
the value of $\Delta WBC(v)$ corresponding to the addition of such a link, and
recalling that the equilibrium requires $\Delta WBC(v)$ to be smaller than the
cost $c$, one easily get to an expression which is in explicit contradiction
with condition (3) (see the SI for full details).

###  I.4 A realistic case

We shall remark that our approach is valid independently on the specific
degree distribution properties of the pristine graph. However, the maximum
degree of a node in a scale-free network generated by the preferential
attachment method barabara  is known to scale as $\sqrt{N}$ BR ; FFF  and this
implies that, for these networks, condition (3) is (from a given size on)
always verified for any value of fixed cost $c$ and any value of $\alpha$,
thus making them very good candidates for initializing the formation of ultra-
small world structures.

Therefore, to illustrate power and generality of the above Theorem, we
performed a massive numerical trial by initializing our game on networks of
$N$ nodes generated with the Barabási-Albert (BA) algorithm barabara , for
$\alpha=1$ (i.e., adopting as benefit the weighted betweenness centrality),
$H=3$ and $c=0.15\sqrt{N}$ (to ensure a coherent scaling of the cost with that
of the maximum degree in the network). With these stipulations, condition (3)
becomes $0.3k\geq 0.15\sqrt{N}$. As $k\approx 2\sqrt{N}$ BR ; FFF , this means
that condition (3) is verified at each value of $N$, and one then expects that
the diameter at equilibrium would not exceed $6$.

It is important to remark here that estimating the benefit function (2)
requires the retrieval of the global structure of network’s pathways at each
step of the game. However, such information is in general not available to the
agents of real social networks. Indeed, computing Eq. (2) becomes
prohibitively costly as the size of the network increases, requiring (with the
fastest existing algorithms) ${\cal O}(NL)$ operations (being $L$ the total
number of links in the network) newma ; brand .

For this reason, it is much more realistic and much less computationally
demanding to assume that agents only use local information. We then consider a
scenario wherein at each step $m$ of the game, a (large degree) node $v$ is
chosen. $v$ incorporates an edge with another node $u$ if

  1. a)

$0.3k\geq c$, where $k$ is the degree of $v$,

  2. b)

the distance between $u$ and $v$ is larger than $3$.

In this way, it is only required to check that the subgraph formed by $v$ and
its first and second neighbors has zero overlap with the subgraph formed by
$u$ and its first neighbors, and the method is not hurting for the knowledge
of the overall shortest paths’ structure. At the same time, the adoption of
local information makes our study’s main claims even stronger, because it
proves that a global network property (the network diameter) may emerge as a
result of a game in which agents only share local information, which is what
actually happens in almost all real circumstances.

Figure 5: The emergence of the six degrees of separation. Ensemble average
$\langle D\rangle$ vs. $N$ for different sets of networks. Light blue line: BA
scale-free networks that are used as initial conditions for the evolution of
the game. Green line: Networks generated at the equilibrium state of the game.
Red line: Networks constructed by randomly adding to the initial condition of
each game the same number of links needed to reach the game equilibrium. A
horizontal black dashed line is positioned at $D=6$ to indicate that the
network’s structure obtained at the equilibrium features the ultra-small world
property, with the concurrent emergence of the six degrees of separation.
Inset: log-lin plot of $\langle D\rangle$ vs. $N$. The logarithmic scaling of
the light blue and red lines is clearly visible.

Note that, if an edge connecting $u$ and $v$ is added, the above conditions
implies that $\Delta WBC(v)\geq c$. Indeed, if the node $u$ satisfies
condition $b)$, it can easily be shown (using the same arguments that the
reader finds in the SI for the proof of the Theorem) that the maximum
contribution to $v$ of the shortest paths between $u$ and a neighbor of $v$ is
$1/5$. Adding the new edge, such a contribution raises to $1/2$, and this
means that

$\Delta WBC(v)\geq 0.3k,$

where $k$ is the number of connections of $v$. Therefore, if condition $a)$
holds, then condition $\Delta WBC(v)\geq c$ is also satisfied. This implies
that our local method is actually more restrictive when incorporating edges,
and yet sufficient to give evidence of the predictions of the Theorem for
nodes satisfying condition (3).

The results of our simulation trial are presented in Fig. 5. At each value of
the network size $N$, $10,000$ different realizations of a BA scale-free
network are generated. The ensemble average $\langle D\rangle$ of the value of
the network diameter is plotted as a light blue line in the figure, showing a
small-world behavior (a logarithmic scaling with $N$, well visible in the log-
lin plot of the inset).

Each of the generated networks is then taken as initial condition for the
evolution of our game, following the conditions a) and b) described above,
until reaching the final, equilibrium state. $\langle D\rangle$ for the
reached equilibria is reported as a green line in the figure, and it is
clearly seen that an ultra-small world state emerges with $\langle D\rangle=6$
(a value marked by an horizontal dashed line).

A legitimate objection is that adding links to a graph (and therefore
increasing the graph’s density) always results in decreasing the network’s
diameter, and therefore a proper comparison has to be offered to assess the
relevance of the obtained results. For this purpose, in all trials we took
diligent note of the total number of links added before reaching the
equilibrium. Then, we took back the initial condition of the specific trial,
and added exactly the same number of links, but this time in a fully random
way i.e., without caring about the fulfillment of the game conditions a) and
b). The obtained values of $\langle D\rangle$ are reported as a red line in
the figure. As expected, the red line is always located below the light blue
one, but the remarkable result is that the new network ensemble maintains
exactly the same logarithmic scaling with $N$ (once again well visible in the
inset), which is destined to depart more and more from the constant value
characterizing ultra-small world states and emerging at the equilibrium of our
game.

Figure 6: Scale-free distribution and hierarchical clustering. a) Ensemble
average $\langle D\rangle$ vs. $N$ for the three considered ensembles of
networks. Light blue line: networks generated by the procedure of Ref.
boccalettibravo  and that are used as initial conditions for the evolution of
the game. Green line: The equilibrium network states of the game. Red line:
Networks constructed by randomly adding to the initial condition of each game
the same number of links needed to reach the game equilibrium. A horizontal
black dashed line is positioned at $D=6$. b) The degree distribution $p(k)$
vs. $k$ for the set of initial conditions (light blue line) and the set of
reached equilibria (green line). $N=10,000$. For visibility, the green line
plotting $p(k)$ at the equilibria has been slightly vertically shifted. The
black dashed line reports the scaling $p(k)\sim k^{-3}$. c) The hierarchical
clustering coefficient $c(k)$ (see text for definition) vs. $k$ for the set of
initial conditions (light blue line) and the set of reached equilibria (green
line). $N=10,000$. For visibility, the green line plotting $c(k)$ at the
equilibria has been slightly vertically shifted. The black dashed line reports
the scaling $c(k)\sim k^{-1}$. The small inset reports the global clustering
coefficients $\langle C\rangle$ vs. $N$ for the three considered ensembles.

Finally, we move to show that the mechanism proposed by us and leading to the
emergence of the six degrees of separation is, in fact, perfectly compatible
with all major structural properties that are observed in real social
networks, and in particular with scale-freeness in the degree distribution and
with the presence of prominent and hierarchical clustering features. The
former attribute indicates that the distribution of the nodes’ degrees scale
as $p(k)\sim k^{-\gamma}$ (with $2<\gamma\leq 3$ in real social networks), the
latter implies that the clustering coefficient $c(k)$ of a connectivity class
$k$ (the average clustering coefficient of all nodes with a given degree $k$)
does depend on $k$ as $c(k)\sim k^{-\omega}$ ravasz2002 .

To that purpose, we repeat the same extensive simulations which led us to
obtain the results reported in Fig. 5, but this time we adopted as initial
conditions for each trial networks that are originated by means of the
procedure described in Ref. boccalettibravo , which indeed provides graphs
endowed with degree distributions $p(k)\sim k^{-3}$, with a very high
clustering value ($c\sim 0.5$ for an average degree of $\langle k\rangle=6$),
and with a hierarchical structure of the clustering described by $c(k)\sim
k^{-1}$.

Once again, for each value of $N$, an ensemble of $10,000$ different networks
are synthesized by the technique of Ref. boccalettibravo , and each of the
generated networks is taken as initial condition for the evolution of the
game, until reaching the equilibrium state. In each trial, moreover, note is
taken of the total number of links added before reaching the equilibrium, and
a network is constructed, for comparison, by randomly adding exactly the same
number of links to the used initial condition.

The results are reported in Fig. 6. Precisely, panel a of Fig. 6 clearly shows
that the scenario obtained is identical to that of Fig. 5: the values of
$\langle D\rangle$ averaged over the ensemble of the initial conditions (light
blue line) and over the constructed set of networks with randomly added links
(red line) are both scaling logarithmically with $N$, while the reached
equilibria (green line) are ultra-small world states with $\langle D\rangle=6$
(marked by an horizontal dashed line).

Panels b and c of Fig. 6 compare, instead, the structures of the initial
conditions and that of the reached equilibria, for $N=10,000$, and one
immediately sees a very remarkable fact: all other structural properties
imprinted in the initial conditions are conserved in the final state.
Precisely, panel b (panel c) of Fig. 6 reports the degree distribution $p(k)$
(the clustering coefficient $c(k)$) for the light blue case corresponding to
the used initial conditions and for the green case corresponding to the
reached equilibria, and one immediately sees that the scaling $p(k)\sim
k^{-3}$ ($c(k)\sim k^{-1}$), highlighted by a black dashed line, is fully
preserved within the range $10^{0}-10^{2}$ of the degree i.e., across two
orders of magnitude, and with minimal differences occurring only at larger
degrees due to the addition of the new links that create a few new hubs at the
equilibrium. For visibility, $p(k)$ ($c(k)$) of the equilibria has even been
multiplied by 2, in order to shift the line in the panel, because otherwise
there would be an almost complete overlap between the light blue and the green
curves.

In the small inset of panel b of Fig. 6, the values of the global clustering
coefficients are reported vs. $N$ for the three ensembles. One sees that the
addition of links in the process of relaxation to equilibrium leads to a
slight decrease of $\langle C\rangle$ (from $\langle C\rangle\sim 0.5$ to
$\langle C\rangle\sim 0.42$) which, however is maintained to a level pointing
to the presence of very prominent and important clustering features. However,
the most remarkable trait here is that the value of $\langle C\rangle$ at
equilibria is larger than that pertinent to the ensemble of networks
constructed by randomly adding to the initial conditions the same number of
links needed to reach the equilibria.

##  II Discussion and outlook

The compensation of costs and benefits is certainly a natural interaction
strategy through which rational agents determine their connections
eguiluz2005cooperation ; perc_bs10 ; jackson2010social ; christakis2013social
; nishi2015inequality ; alvarez2021evolutionary , and therefore our study
contributes to the understanding of why the six degrees of separation is such
a ubiquitous property across vastly different social networks. It is,
moreover, reasonable to assume that a similar evolutionary principle may also
apply to the design of man-made or technological networks holme2012temporal :
take, for instance air or sea transportation networks guimera2005worldwide ;
barbosa2018human ; lei2022forecasting , in which airports/ports may increase
their volume of trades and/or tourism industry by ‘being in between’ the main
routes of interchanges of passengers and goods, and in doing so they are keen
to incur in the relative costs of maintaining (or even enlarging) the number
of local connections.

On the other hand, the units of biological networks are in general not
rational agents, and it is not straightforward to argue that benefits in terms
of betweenness centrality shaped, for instance, the structure of metabolic,
genetic or brain networks along their million year long evolutionary path
jeong2000large ; bassett2017network ; zwir2022evolution ;
tripp2022evolutionary . However, one cannot rule out that other compensation
mechanisms could have played a pivotal role in this case too, with different
benefit functions (e.g. resilience to random perturbations or failures
albert2000error ; cohen2000resilience , or local or global efficiency
morone2015influence ) recouping for the cost to form or maintain a specific
adjacency structure. In neural structures, for instance, it is well known that
the functional gains associated with link formation must offset the associated
structural costs cajal ; bullmore ; sterling . Note that, for neural
structures, while this principle holds in general at evolutionary and
developmental time scales, it may also take place at much shorter scales,
comparable to those of social network dynamics.

Finally, our study also sheds light on the so-called strength of weak ties
phenomenon. This concept was introduced by Mark Granovetter who showed that
the most common way of finding a new job is through personal contacts with
distant acquaintances, and not via close friends, as one would instead have
expected granovetter1973strength ; granovetter1974 . Distant acquaintances
represent links connecting different groups of people, and therefore provide
each individual with a unique way to receive useful information about distant
groups.

Formally speaking, weak ties are links connecting nodes that were originally
located at rather large distances and they are therefore called bridges or
local bridges (see the discussion and references in Chapter 3 of Ref.
easley2010networks ). Their importance for social interaction and
communication is strongly supported by a wide range of studies
burt1992structural ; burt2004structural .

The formation of links connecting nodes from 2-independent sets as the key to
the emergence of the six degrees of separation describes exactly the case of a
local bridge formation, i.e. a weak tie in Granovetter’s sense. Therefore, our
model can also be viewed as the game-theoretical foundation for the strength
of weak ties phenomenon.

Authors would like to thank Gonzalo Contreras-Aso and Jorge Tredicce for many
inspiring discussions. R. Criado and M. Romance acknowledge funding from
projects PGC2018-101625-B-I00 (Spanish Ministry, AEI/FEDER, UE) and M1993
(URJC Grant). M.P. was supported by the Slovenian Research Agency (Grant Nos.
P1-0403 and J1-2457). The usage of the resources, technical expertise, and
assistance provided by the supercomputer facility CRESCO of ENEA in Portici
(Italy) is also acknowledged.

## References

  * (1) Watts, DJ. & Strogatz, SH. Collective dynamics of ‘small-world’ networks. Nature 393, 440–442 (1998).
  * (2) Gurevitch, M. Ph.D. thesis (Massachusetts Institute of Technology) (1961).
  * (3) de Sola Pool, I & Kochen, M Contacts and influence. Social Networks 1, 5–51 (1978).
  * (4) Milgram, S. The small world problem. Psychology Today 2, 60–67 (1967).
  * (5) Travers, J. & Milgram, S. An experimental study of the small world problem in Social Networks. (Elsevier), pp. 179–197 (1977).
  * (6) Dodds, PS., Muhamad, R. & Watts, DJ. An experimental study of search in global social networks. Science 301, 827–829 (2003).
  * (7) Leskovec, J. & Horvitz, E. Worldwide buzz: Planetary-scale views on an instant-messaging network, (Citeseer), Technical report (2007).
  * (8) Sanderson, K. Six degrees of messaging (2008).
  * (9) Bakhshandeh, R., Samadi, M., Azimifar, Z. & Schaeffer, J. Degrees of separation in social networks in International Symposium on Combinatorial Search. Vol. 2, (2011).
  * (10) Backstrom, L., Boldi, P., Rosa, M., Ugander, J. & Vigna, S. Four degrees of separation in Proceedings of the 4th Annual ACM Web Science Conference. pp. 33–42 (2012).
  * (11) Myerson, RB. Graphs and cooperation in games. Mathematics of Operations Research 2, 225–229, (1977).
  * (12) Jackson, MO. & Wolinsky, A. A strategic model of social and economic networks. Journal of Economic Theory 71, 44–74 (1996).
  * (13) Nowak, MA. & May, RM. Evolutionary Games and Spatial Chaos. Nature 359, 826–829 (1992).
  * (14) Ebel, H. & Bornholdt, S. Coevolutionary games on networks. Physical Review E 66, 056118 (2002).
  * (15) Zimmermann, MG., Eguíluz, V., & San Miguel, M. Coevolution of dynamical states and interactions in dynamic networks. Physical Review E 69, 065102(R) (2004).
  * (16) Zimmermann, MG. & Eguíluz, V. Cooperation, Social Networks and the Emergence of Leadership in a Prisoner’s Dilemma with Local Interactions. Physical Review E 72, 056118 (2005).
  * (17) Pacheco, JM., Traulsen, A., & Nowak, MA. Coevolution of strategy and structure in complex networks with dynamical linking. Physical Review Letters 97, 258103 (2006).
  * (18) Gómez-Gardeñes, J., Campillo, M., Moreno, Y., & Floría, LM. Dynamical Organization of Cooperation in Complex Networks. Physical Review Letters 98, 108103 (2007).
  * (19) Gross T. & Blasius, B. Adaptive coevolutionary networks: a review. Journal of the Royal Society Interface 5, 259–271 (2008).
  * (20) Ohtsuki, H., Hauert, C., Lieberman, E., & Nowak, MA. A simple rule for the evolution of cooperation on graphs and social networks. Nature 441, 502–505 (2006).
  * (21) Goyal, S. & Vega-Redondo, F. Network formation and social coordination. Games and Economic Behavior 50, 178–207 (2005).
  * (22) Bloch, F. & Jackson, MO. The formation of networks with transfers among players. Journal of Economic Theory 133, 83–110, 2007.
  * (23) Poncela, J., Gómez-Gardeñes, J., Traulsen, A., & Moreno, Y. Evolutionary game dynamics in a growing structured population. New Journal of Physics 11, 083031 (2009).
  * (24) Bei, X., Chen, W., Teng, S-H., Zhang, J., & Zhu, J. Bounded budget betweenness centrality game for strategic network formations. Theoretical Computer Science 412, 7147–7168 (2011).
  * (25) Holme, P. & Ghostal, G. Dynamics of networking agents competing for high centrality and low degree. Physical Review Letters 96, 098701 (2006).
  * (26) Cohen, R. & Havlin, S. Scale-free networks are ultrasmall. Physical Review Letters 90, 058701 (2003).
  * (27) Sampaio Filho, C.IN., Moreira, AA., Andrade, R.FS., Herrmann, HJ. & Andrade, JS. Mandala networks: ultra-small-world and highly sparse graphs. Scientific Reports 5, 1–6 (2015).
  * (28) Nash Jr, JF. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences 36, 48–49 (1950).
  * (29) Nowak, MA. Five rules for the evolution of cooperation. Science 314, 1560–1563 (2006).
  * (30) Rand, DG., Arbesman, S. & Christakis, NA. Dynamic social networks promote cooperation in experiments with humans. Proceedings of the National Academy of Sciences 108, 19193–19198 (2011).
  * (31) Rand, DG. & Nowak, MA. Human cooperation. Trends in Cognitive Sciences 17, 413–425 (2013).
  * (32) Fu, F., Tarnita, CE., Christakis, NA., Wang, L., Rand, DG. & Nowak, MA. Evolution of in-group favoritism. Nature Scientific Reports 2, 460 (2012).
  * (33) Fu, F., Nowak, MA., Christakis, NA. & Fowler, JH. The Evolution of Homophily. Nature Scientific Reports 2, 845 (2012).
  * (34) Freeman, LC. A set of measures of centrality based on betweenness. Sociometry pp. 35–41 (1977).
  * (35) Fink, JF. & Jacobson, MS. On n-domination, n-dependence and forbidden subgraphs in Graph theory with applications to algorithms and computer science. pp. 301–311 (1985).
  * (36) Barabási, AL. & Albert, R. Emergence of scaling in random networks. Science 286, 509–512 (1999).
  * (37) Bollobás, B. & Riordan, OM. Mathematical results on scale-free random graphs. Handbook of Graphs and Networks: from the genome to the internet pp. 1–34 (2003).
  * (38) Flaxman A. & Frieze, A. T Fenner, High degree vertices and eigenvalues in the preferential attachment graph. Internet Mathematics 2, 1–19 (2005).
  * (39) Newman, ME. Scientific collaboration networks. ii. shortest paths, weighted networks, and centrality. Physical Review E 64, 016132 (2001).
  * (40) Brandes, U. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology 25, 163–177 (2001).
  * (41) Ravasz, E., Somera, AL., Mongru, DA., Oltvai, ZN. & Barabási, AL. Hierarchical organization of modularity in metabolic networks, Science 297, 1551–1556 (2002).
  * (42) Boccaletti, S., Hwang & Latora, V. Growing hierarchical scale-free networks by means of nonhierarchical processes. International Journal of Bifurcation and Chaos 17, 2447–2452 (2007).
  * (43) Eguíluz, VM., Zimmermann, MG., Cela-Conde, CJ. & Miguel, MS. Cooperation and the emergence of role differentiation in the dynamics of social networks. American Journal of Sociology 110, 977–1008 (2005).
  * (44) Perc, M. & Szolnoki, A. Coevolutionary games—a mini review. BioSystems 99, 109–125 (2010).
  * (45) Jackson, MO. Social and economic networks. (Princeton University Press), (2010).
  * (46) Christakis, NA. & Fowler, JH. Social contagion theory: examining dynamic social networks and human behavior. Statistics in Medicine 32, 556–577 (2013).
  * (47) Nishi, A., Shirado, H., Rand, DG. & Christakis, NA. Inequality and visibility of wealth in experimental social networks. Nature 526, 426–429 (2015).
  * (48) Alvarez-Rodriguez, U., Battiston, F., de Arruda, GF., Moreno, Y., Perc, M. & Latora, V. Evolutionary dynamics of higher-order interactions in social networks. Nature Human Behaviour 5, 586–595 (2021).
  * (49) Holme, P. & Saramäki, J. Temporal networks. Physics Reports 519, 97–125 (2012).
  * (50) Guimera, R., Mossa, S., Turtschi, A. & Amaral, LN. The worldwide air transportation network: Anomalous centrality, community structure, and cities’ global roles. Proceedings of the National Academy of Sciences 102, 7794–7799 (2005).
  * (51) Barbosa, H., Barthelemy, M., Ghoshal, G., James, C.R., Lenormand, M., Louail, T., Menezes, R., and Ramasco, J.J., Simini, F. & Tomasini, M. Human mobility: Models and applications. Physics Reports 734, 1–74 (2018).
  * (52) Lei, W., Alves, LG. & Amaral, LAN. Forecasting the evolution of fast-changing transportation networks using machine learning. Nature Communications 13, 1–12 (2022).
  * (53) Jeong, H., Tombor, B., Albert, R., Oltvai, ZN. & Barabási, AL. The large-scale organization of metabolic networks. Nature 407, 651–654 (2000).
  * (54) Bassett, DS. & Sporns, O. Network neuroscience. Nature Neuroscience 20, 353–364 (2017).
  * (55) Zwir, I., Del-Val, C., Hintsanen, Mirka and Cloninger, KM and Romero-Zaliz, R and Mesa, A and Arnedo, J and Salas, R and Poblete, GF and Raitoharju, E., Raitakari, O., Keltikangas-Järvinen, L., de Erausquin, GA., Tattersall, I., Lehtimäki, T. & Cloninger, CR. Evolution of genetic networks for human creativity. Molecular Psychiatry 27, 354–376 (2022).
  * (56) Tripp, EA., Fu, F. & Pauls, SD. Evolutionary Kuramoto dynamics. Proc. R. Soc. B 289, 20220999 (2022).
  * (57) Albert, R., Jeong, H. & Barabási, AL. Error and attack tolerance of complex networks. Nature 406, 378–382 (2000).
  * (58) Cohen, R., Erez, K., Ben-Avraham, D. & Havlin, S. Resilience of the internet to random breakdowns. Physical Review Letters 85, 4626 (2000).
  * (59) Morone, F. & Makse, HA. Influence maximization in complex networks through percolation. Nature 524, 65–68 (2015).
  * (60) Ramón y Cajal, S. Histologie du systéme nerveux de l’homme et des vertébrés, 1909, english translation as Histology of the nervous system of man and vertebrates (N. Swanson & L. Swanson, Trans.). (Oxford University Press), (1995).
  * (61) Bullmore, E. & Sporns, O. The economy of brain network organization. Nature Reviews Neuroscience 13, 336–349 (2012).
  * (62) Sterling,P. & Laughlin, S. Principles of neural design. (MIT Press), (2015).
  * (63) Granovetter, MS. The strength of weak ties. American Journal of Sociology 78, 1360–1380 (1973).
  * (64) Granovetter, MS. Getting a job: A study of contacts and careers. (University of Chicago Press), (2018).
  * (65) Easley, D. & Kleinberg, J. Networks, crowds, and markets: Reasoning about a highly connected world. (Cambridge University Press), (2010).
  * (66) Burt, RS. Structural holes: the social structure of competition. (Harvard University Press), (1992).
  * (67) Burt, RS. Structural holes and good ideas. American Journal of Sociology 110, 349–399 (2004).

Supplementary Information:
Why are there six degrees of separation in a social network?
I. Samoylenko∗, D. Aleja∗, E. Primo, K. Alfaro-Bittner, E. Vasilyeva, K.
Kovalenko, D. Musatov, A. M. Raigorodskii, R. Criado, M. Romance, D. Papo, M.
Perc, B. Barzel, S. Boccaletti.

In this Supplementary Material (SM), the reader finds all details of the
theorematic proofs which are referred to in the main text. The SM is divided
in two main sections. The first Section contains some definition and
preliminaries that are of use in all Theorem and Lemmas and describes the
results of the game theoretical approach presented in the first part of our
Manuscript. The second Section contains, instead, the details of the
illustrative case (presented in the second part of our Manuscript) in which
nodes can only add links to their neighborhoods.

##  III The game theoretical approach

In our model, the $N$ nodes of a network $V$ are agents of a game. At each
step $m$ of the game, each node $v\in V$ selects (independently on the choices
that may be made by the other agents in the same step) a potential
neighborhood ${\cal N}_{v}(m)$ made of $k_{v}(m)$ other nodes of $V$, and
decides whether it is more profitable to form connections with all the nodes
in ${\cal N}_{v}(m)$ or to remain connected with the nodes in ${\cal
N}_{v}(m-1)$. The decision is based on compensation between the costs incurred
in the change and the payoff (or benefit).

To be more specific, at the step $m$ of the game, each agent $v$ (separately
and independently) compares the configuration defined by the adjacency matrix
$A_{m-1}$ (reflecting the state of the network after all agents have made
their choice of neighborhood at the step $m-1$) with that of the adjacency
matrix $A_{m,u}$ which is obtained from $A_{m-1}$ by eliminating all the
$k_{v}(m-1)$ edges between $v$ and the members of ${\cal N}_{v}(m-1)$ and
adding instead all the $k_{v}(m)$ edges between $v$ and the members of ${\cal
N}_{v}(m)$. If the benefit of the new configuration $A_{m,u}$ overcomes the
costs of forming such $k_{v}(m)$ edges, then the agent $v$ adopts the
neighborhood ${\cal N}_{v}(m)$, otherwise it remains linked with the members
of ${\cal N}_{v}(m-1)$. The step $m$ of the game is concluded when all the $N$
agents have made their decision and a new global network arrangement is
produced, reflected by the adjacency matrix $A_{m}$, which is then used (by
all agents) at the step $m+1$.

###  III.1 Definitions and preliminaries

Definition 1 The cost of forming a connection $(u,v)$ is taken to be equal to
some $c(N)>0$, which can be either a constant or a generic function of the
network size.

Definition 2. The distance between two vertices is the number of edges forming
the shortest path between them.

Definition 3. The benefit function is taken to be $WBC(v)=\sum_{s\neq v\neq
t}\frac{\sigma_{st}(v)}{\sigma_{st}}\cdot f(l(s,t))$ [as in Eq. (1) of the
main text], where $s,t\in V$ are all possible pairs of vertices other than
$v$, $\sigma_{st}(v)$ is the number of shortest paths between the vertices $s$
and $t$ passing through the vertex $v$, $\sigma_{st}$ is the total number of
shortest paths between vertices $s$ and $t$, $f(x)$ is an arbitrary (but
strictly decreasing) function of the argument $x$, and $l(s,t)$ is the length
of the shortest path between vertices $s$ and $t$.

Definition 4. A network satisfies the ultra-small world property if its
diameter (the maximal distance between any pair of network’s nodes) is bounded
by a given value which is independent on the network’s size.

Definition 5. A $2$-independent set $S$ is a set of network’s nodes such that
the distance between any pair of its members is larger than $2$. As a
consequence, each pair of nodes $u,v\in S$ isn’t connected directly by a
network edge, nor a vertex $w\in V$ exists having simultaneously connections
with $u$ and $v$.

It is now necessary to make a couple of preliminary observations, that are of
use in all demonstrations which are part of this SM.

A first observation is concerned with the fact that, if a node $v$ selects a
potential new neighborhood where all previous connections are maintained and
$p$ new neighbors are added and if such a new configuration is not accepted,
it actually implies

$\Delta WBC(v)<pc,$ (4)

where $\Delta WBC(v)$ is the difference between $WBC^{\prime}(v)$ (calculated
with incorporating the $p$ new edges) and $WBC(v)$. Indeed, as the new
strategy is rejected, it follows that

$WBC^{\prime}(v)<(q+p)c,$

where $q$ was the number of neighbors of $v$ before incorporating the $p$ new
edges. Moreover, as the $q$ previous neighbors were instead accepted in the
previous step of the game, one has that $WBC(v)\geq qc$. Therefore, condition
(4) comes from the fact that

$WBC^{\prime}(v)<(q+p)c\leq WBC(v)+pc.$

A second, important, observation comes from the content of the following Lemma
0, which states that the contribution to the benefit function of $v$ given by
the shortest path between any two nodes (say $s$ and $t$) never decreases when
$v$ acquires a new link. Fig. 1A illustrates the case in which node $v$
accrues an utility due to being intermediary in one of the shortest paths
connecting nodes $s$ and $t$. If a link is now added between $v$ and another
node $u$, the benefit function for $v$ changes as

$WBC^{\prime}(v)=\sum_{s\neq v\neq
t}\frac{\sigma^{\prime}_{st}(v)}{\sigma^{\prime}_{st}}\cdot
f(l^{\prime}(s,t)).$ (5)

where now all quantities are denoted by ′. Notice that the number of pairs
$(s,t)$ in Eq. (5) may change from the ones considered in $WBC(v)$ because of
the added link.

Lemma 0. If a new link is added between two nodes $u$ and $v$ then

$\frac{\sigma_{s,t}(v)}{\sigma_{s,t}}\cdot
f(l(s,t))\leq\frac{\sigma^{\prime}_{s,t}(v)}{\sigma^{\prime}_{s,t}}\cdot
f(l^{\prime}(s,t)),$ (6)

where $s$ and $t$ are any two nodes of $V\setminus\left\\{v\right\\}$.

Figure 7: Schematic illustration of the two possible cases examined in Lemma
0. In all panels red and light blue curves are used to mark, respectively, the
shortest paths between $s$ and $t$ (whose number is $\sigma_{s,t}$) and the
shortest paths between nodes $s$ and $t$ which pass through node $v$ (whose
number is $\sigma_{s,t}(v)$). Panel A) shows an hypothetical graph $V$ where
nodes $s$ and $t$ (colored in light blue) are separated by a distance
$l(s,t)=5$, $\sigma_{s,t}=5$, and $\sigma_{s,t}(v)=1$. The next two panels
illustrate the two possible cases originated by adding a link between nodes
$v$ and $u$. Panel B) Case $l(s,t)>l^{\prime}(s,t)$. In this situation, both
the distance between $s$ and $t$ and the number of shortest paths decrease. In
particular, the unique (new) shortest path between $s$ and $t$ is the one that
passes through node $v$. Panel C) Case $l(s,t)=l^{\prime}(s,t)$. In this case
three new shortest paths appear (colored in green). Note that all the shortest
paths colored in red are equal to the ones presented in panel A.

Proof of Lemma 0. When adding such a link, the distance between $s$ and $t$
can either decrease or remain the same. Then, these two cases have to be
separately examined.

  * •

Case $l(s,t)>l^{\prime}(s,t)$ (illustrated in Fig. 1B). In this case, when a
link is added between $u$ and $v$, one obtains that

$\frac{\sigma_{s,t}(v)}{\sigma_{s,t}}\cdot f(l(s,t))\leq f(l^{\prime}(s,t)),$

because $\sigma_{s,t}(v)\leq\sigma_{s,t}$, $l(s,t)>l^{\prime}(s,t)$, and $f$
is a strictly decreasing function of its argument. Therefore, as all the
shortest paths between $s$ and $t$ pass through $v$ (see again Fig.1B), one
has that $\sigma^{\prime}_{s,t}(v)=\sigma^{\prime}_{s,t}$, and condition (6)
is verified.

  * •

Case $l(s,t)=l^{\prime}(s,t)$ (illustrated in Fig. 1C). In this situation,
when a link between $u$ and $v$ is added, $x$ new shortest paths between $s$
and $t$ may arise, which however have to pass all through $v$ (as it is shown
in Fig. 7C). Therefore, one has

$\sigma^{\prime}_{s,t}=\sigma_{s,t}+x\quad\hbox{and}\quad\sigma^{\prime}_{s,t}(v)=\sigma_{s,t}(v)+x.$
(7)

Thus, as $\sigma_{s,t}(v)\leq\sigma_{s,t}$, one obtains that

$\sigma_{s,t}(v)\left(\sigma_{s,t}+x\right)\leq\sigma_{s,t}\left(\sigma_{s,t}(v)+x\right),$

and eventually

$\frac{\sigma_{s,t}(v)}{\sigma_{s,t}}\leq\frac{\sigma_{s,t}(v)+x}{\sigma_{s,t}+x}.$

Therefore, considering both $l(s,t)=l^{\prime}(s,t)$ and Eq. (7), it comes out
that condition (6) is satisfied.

###  III.2 Main results

Here, we describe the properties of the model’s Nash equilibria (when they
exist), i.e. of those settings where it is unprofitable for any agent to
unilaterally deviate from its current strategy.

First, we state a bounding condition for the cost ensuring that, when they
exist, such Nash equilibria are not empty graphs, and therefore they contain
at least a connected component.

Theorem 0. If $c(N)>\frac{f(2)(N-2)}{2}$, then the empty graph is a Nash
equilibrium configuration. Otherwise, an empty graph will never be obtained at
the Nash equilibrium.

Proof. Consider a vertex $v$ of an empty graph $V$. From each pair of other
vertices $s,t\in V,s\neq v\neq t$, the contribution to $WBC(v)$ is no more
than $f(2)$ (which would correspond to the case in which both nodes $s$ and
$t$ are directly linked to $v$). The net benefit for $v$ of making $x$
connections will be then equal to ${x\choose 2}\cdot f(2)-xc$. Obviously, the
maximum is reached at $x=N-1$. Then, if a vertex $v$ in an empty graph changes
its strategy and forms connections with the other $N-1$ nodes, it receives a
net utility equal to ${N-1\choose 2}\cdot f(2)-(N-1)c$. Such a latter quantity
will be non negative for $\frac{(N-1)(N-2)f(2)}{2}\geq(N-1)c\Rightarrow
c\leq\frac{f(2)(N-2)}{2}$, meaning that a vertex can exist which would benefit
from deviating from the strategy of not drawing any edges. If instead
$c>\frac{f(2)(N-2)}{2}$, then the maximum possible gain (after deducing costs)
will be negative, and this implies that the empty graph will be a Nash
equilibrium.

####  III.2.1 Condition for the existence of a vertex of a large degree

The next step is to prove that, in a non empty Nash equilibrium, there exists
always a vertex of large degree.

Lemma 1. Let the maximum degree of a vertex in a connected graph $V$ be $k$.
Then, the maximum 2-independent set will be of size at least
$\frac{|V|}{k^{2}+1}$.

Proof. Let’s construct iteratively a 2-independent set $S$ of the required
size.

For this purpose, we start by considering a generic node $v_{1}\in V$. Then,
we consider the set $t_{1}$ including $v_{1}$, all its neighbors (vertices of
$V$ which are at distance 1 from $v_{1}$) and all its neighbors of neighbors
(vertices of $V$ at distance 2 from $v_{1}$). Since the degree of a vertex in
$V$ does not exceed $k$, so does the maximum number of neighbors of $v_{1}$.
Consider now the vertex $u$ which is neighbor of $v_{1}$. Since its degree
does not exceed $k$ and it has a connection $(v,u)$, then the maximum number
of vertices that are at distance 2 from $v_{1}$ and are furthermore connected
to $u$ is $k-1$. It follows that the number of vertices belonging to $t_{1}$
is bounded from above as $k(k-1)+k+1=k^{2}+1$ (a situation in which $v_{1}$
has $k$ neighbors and each neighbor of $v_{1}$ provides a unique set of
vertices located at a distance of 2 from it).

The vertex $v_{1}$ is added to the set $S$ and the subgraph $V_{1}=V\setminus
t_{1}$ is considered. $V_{1}$ is the graph obtained from $V$ by removing all
members of $t_{1}$, and therefore it contains vertices that are all at a
distance of at least 3 from $v_{1}$ (in other words, any vertex $v_{2}\in
V_{1}$ will be 2-independent with $v_{1}$). The procedure can be repeated
iteratively until there are no vertices left in the resulting subgraph: at
each iteration of the procedure, a new vertex can be added to $S$, and no more
than $k^{2}+1$ vertices are removed from $V$. As a consequence, there are at
least $\frac{|V|}{k^{2}+1}$ iterations of the procedure, which means
$|S|\geq\frac{|V|}{k^{2}+1}$ (quod erat demonstrandum!)

Lemma 2. Let a 2-independent set of size $x$ be present in the network. Then,
if one vertex of such a set ”glues the set” (i.e., it forms connections with
all other members of the set), it receives an additional utility equal to at
least ${x-1\choose 2}\cdot(f(2)-f(6))$

Proof. Consider a 2-independent set $S$ and a vertex $v\in S$, and let us
estimate the minimum gain that such a vertex will get by forming edges to all
other vertices of $S$. Notice that, before forming connections in the set, the
maximum contribution to $WBC(v)$ received from a pair of other vertices
$s,t\in S$ is $f(6)$. This is because both distances $l(v,s)$ and $l(v,t)$ are
at least 3, and therefore either the shortest path between $s$ and $t$ is of
length at least 6, or it does not pass through $v$ (and, in this latter case,
the contribution to $WBC(v)$ is 0). This implies that even in the case in
which all shortest paths between $s$ and $t$ are passing through $v$, the
maximum possible contribution to $WBC(v)$ from these two vertices is $f(6)$.
Now, let the vertex $v$ form the edges $(v,s)$ and $(v,t)$. Then, there exists
a unique path from $s$ to $t$ of length 2 passing through $v$ (see the
explanatory Figure 2B in the main text), and thus such a pair of vertices will
contribute $f(2)$ to $WBC(v)$. On its turn, this implies that the minimum
increase of $WBC(v)$ from gluing any pair of vertices $s,t\in S$ is equal to
$f(2)-f(6)$, and then (summing up over all possible pairs of vertices $s,t\in
S$) the Lemma is proved.

Theorem 1. Let $c(N)>0$ be a size-dependent cost function of forming an edge,
and let $k$ be a positive integer number specifying the degree of a node in
the network. If a network size $\tilde{N}$ exists starting from which (i.e.
for all sizes $N>\tilde{N}$) the relationship

$\left[\frac{2}{f(2)-f(6)}(c(N)+f(2)-f(6))\right](k^{2}+1)<N$

is satisfied, then the Nash equilibrium will always contain at least a vertex
of degree at least $k$.

Proof. Let’s demonstrate Theorem 1 by contradiction, and assume the opposite
i.e., let us suppose that there is a $k$ such that for any $N$ there are
equilibrium states that do not contain a vertex of degree at least $k$.

Due to Lemma 1, this entails the existence of a 2-independent set $S$ of size
at least $\frac{N}{k^{2}+1}$.

Then, due to Lemma 2, any vertex of such a 2-independent set will increase the
value of the benefit function (by forming connections with all other vertices
in $S$) by at least ${\frac{N}{k^{2}+1}-1\choose 2}\cdot(f(2)-f(6))$. The
costs of forming these links will be instead equal to
$(\frac{N}{k^{2}+1}-1)\cdot c$.

Then one can examine the utility obtained by a vertex $v\in S$ from the
formation of such connections, taking into account that, in order to prevent
$v$ from connecting with every other vertex in $S$, the difference between the
additional utility received and the cost must be negative. One has

$\frac{1}{2}\cdot(\frac{N}{k^{2}+1}-1)\cdot(\frac{N}{k^{2}+1}-2)\cdot(f(2)-f(6))-(\frac{N}{k^{2}+1}-1)\cdot
c<0$ ,

and, therefore,

$(\frac{N}{k^{2}+1}-2)<\frac{2c}{f(2)-f(6)}\Leftrightarrow\frac{N}{k^{2}+1}<\frac{2c}{f(2)-f(6)}+2$
.

In order to be at the Nash equilibrium, it is necessary that the above
condition is verified, because otherwise it would be strictly advantageous for
a vertex from the maximum 2-independent set $S$ to change its strategy and
glue the set $S$. Then, one obtains:

$\frac{N}{k^{2}+1}<\frac{2c}{f(2)-f(6)}+2\Leftrightarrow
N<(\frac{2c}{f(2)-f(6)}+2)\cdot({k^{2}+1})\Longrightarrow
N<\left[\frac{2}{f(2)-f(6)}(c+f(2)-f(6))\right](k^{2}+1)$

which is in direct contradiction with the statement of Theorem 1. This implies
that our initial assumption is incorrect, and therefore that there will be
necessarily a vertex of degree at least $k$ at the equilibrium (quod erat
demonstrandum!).

####  III.2.2 The emergence of ultra-small world states and of the six degrees
of separation property

Finally, we can prove the main result of our study, related with the fact
that, if they exist, the Nash equilibria are ultra-small world states
featuring the six degrees of separation property.

Theorem 2. Let the cost $c(N)$ of forming a link in the network satisfy

$c(N)<\sqrt[3]{\frac{f(2)-f(6)}{16}}\cdot\sqrt[3]{N\cdot(f(2)-f(5))^{2}}-f(2)+f(6).$

Then, from a given network size $\tilde{N}$ on (i.e. for all networks whose
size $N$ is larger than $\tilde{N}$), the distance between two generic
vertices $v,u$ of the network does not exceed 6 at the Nash equilibrium.

Lemma 3. If

$c(N)<\sqrt[3]{\frac{f(2)-f(6)}{16}}\cdot\sqrt[3]{N\cdot(f(2)-f(5))^{2}}-f(2)+f(6),$

then all equilibria contain at least a vertex $u$ such that the distance to it
from any other vertex of the network does not exceed 3.

Proof. Once again, let us proceed by contradiction, i.e. by trying to prove
the opposite. Let us then consider a value of the degree
$k=\frac{1}{f(2)-f(5)}\cdot\left(\sqrt[3]{\frac{f(2)-f(6)}{2}}\cdot\sqrt[3]{N\cdot(f(2)-f(5))^{2}}-f(2)+f(6)\right)$.

First, one has to notice that the inequality $k^{2}+1<2k^{2}$ is always
verified, as far as $k>1$. Then, one has that

$\frac{2}{f(2)-f(6)}(c+f(2)-f(6))(k^{2}+1)<\frac{2}{f(2)-f(6)}(c+f(2)-f(6))\cdot
2k^{2}=\frac{4}{f(2)-f(6)}(c+f(2)-f(6))\cdot k^{2}=$

$=\frac{4}{f(2)-f(6)}(c+f(2)-f(6))\left(\frac{1}{f(2)-f(5)}\cdot(\sqrt[3]{\frac{f(2)-f(6)}{2}}\cdot\sqrt[3]{N\cdot(f(2)-f(5))^{2}}-f(2)+f(6))\right)^{2}<$

$<\frac{4}{f(2)-f(6)}\left(\sqrt[3]{\frac{f(2)-f(6)}{16}}\sqrt[3]{N\cdot(f(2)-f(5))^{2}}\right)(\sqrt[3]{\frac{f(2)-f(6)}{2}})^{2}\cdot$

$\cdot\frac{1}{(f(2)-f(5))^{2}}$
$\cdot\left(\sqrt[3]{N\cdot(f(2)-f(5))^{2}}\right)^{2}=N\Longrightarrow$

$\Longrightarrow\frac{2}{f(2)-f(6)}(c+f(2)-f(6))(k^{2}+1)<N.$

Due to Theorem 1, one has therefore to conclude that there must be a vertex of
degree $k$ at the Nash equilibrium.

Notice that, in the derivation of the above expression, we have made use of
the two inequalities
$c+f(2)-f(6)<\sqrt[3]{\frac{f(2)-f(6)}{16}}\cdot\sqrt[3]{N\cdot(f(2)-f(5))^{2}}$
(from the statement of Lemma 3) and $-f(2)+f(6)<0$ (from the fact that $f(x)$
is a strictly decreasing function of its argument).

Let us call such a vertex $u$. Suppose now that a vertex $v\in V$ exists such
that the distance between $u$ and $v$ is at least 4, and let us calculate the
minimum additional utility that the vertex $u$ would accrue by forming a
connection with $v$.

We now denote as $S_{u}$ the set of neighbors of the vertex $u$, and we
consider a generic vertex $s_{i}\in S_{u}$. If the shortest path from $v$ to
$s_{i}$ passes through $u$, then the distance from $v$ to $s_{i}$ must be at
least 5 (otherwise it would be possible to get to $u$ from $v$ along the edges
of the network with less than 3 moves). Notice that the pair $s_{i},v$
contributes to $WBC(u)$ no more than $f(l(s_{i},v))$, i.e. no more than $f(5)$
in the present case. After forming the edge $(u,v)$, the distance between the
vertices $s_{i}$ and $v$ will become 2, which implies that the contribution of
this pair to $WBC(u)$ will become $f(2)$, i.e. it will increase by at least
$(f(2)-f(5))$. This argument is valid for all other vertices of $S$. Then, the
total benefit from holding the edge $(u,v)$ will be at least $(f(2)-f(5))\cdot
k$. At the same time, the cost of forming the edge $(u,v)$ is equal to $c$.
Thus, in order to be at the Nash equilibrium, it is necessary that

$\left(f(2)-f(5)\right)\cdot k<c\Leftrightarrow k<\frac{c}{f(2)-f(5)}$ .

On the other hand, one has that

$\frac{c}{f(2)-f(5)}<\frac{1}{f(2)-f(5)}\cdot\left(\sqrt[3]{\frac{f(2)-f(6)}{16}}\cdot\sqrt[3]{N\cdot(f(2)-f(5))^{2}}-f(2)+f(6)\right)<$

$<\frac{1}{f(2)-f(5)}\cdot\left(\sqrt[3]{\frac{f(2)-f(6)}{2}}\cdot\sqrt[3]{N\cdot(f(2)-f(5))^{2}}-f(2)+f(6)\right)=k$.

Therefore, one has that $k>\frac{c}{f(2)-f(5)}$, which evidently leads to a
contradiction. Therefore, all equilibrium states must necessarily contain at
least a vertex $u$ of degree at least $k$ such that each vertex $v\in V$ will
necessarily be at a distance of no more than 3 from $u$. Lemma 3 is proved.

Proof of Theorem 2. According to Theorem 1, there is a vertex $u$ of degree at
least $k$ in the equilibrium state. According to Lemma 3, the distance from
any other vertex of the network to $u$ does not exceed 3. This automatically
implies that the maximal distance between any two vertices $s,t$ (the diameter
of the network) cannot exceed 6 at the equilibrium: no more than 3 steps are
needed for passing from $s$ to $u$ and no more than 3 other steps are needed
from $u$ to $t$ (quod erat demonstrandum!).

##  IV The illustrative case

In the second part of the main text, we reported on an illustrative model,
where nodes can modify their neighborhood only by adding new links to the
already existing ones. In particular, the game consisted in the following
steps.

  * 1)

The agents start the game when they are already connected by means of a
pristine graph where, in addition, there exists at least one node with
sufficiently high degree.

  * 2)

Each agent adopts as benefit function

$WBC(v)=\sum_{s\neq v\neq
t}\frac{\sigma_{st}(v)}{\sigma_{st}}\cdot\frac{1}{l(s,t)^{\alpha}},$ (8)

with $\alpha$ being a strictly positive parameter. This implies that the
weighting factor is $f(l(s,t))=\frac{1}{l(s,t)^{\alpha}}$, and that Eq. (8)
coincides, for $\alpha=1$, with the classical weighted betweenness centrality.

  * 3)

Agents add new connections to their neighborhood if and only if there is a
positive balance between the extra-utility brought by the new connections and
the extra-cost.

In practice, at each step $m$ of the game, each agent $v\in V$ considers a
neighborhood ${\cal N}_{v}(m)$ which is equal to ${\cal N}_{v}(m-1)$ plus $p$
other nodes.

When all agents become unable to incorporate further edges, the network is
said to have reached its asymptotic equilibrium state.

Under this conditions, we are able to prove the following Theorem:

Theorem 3. If in the initial graph there is a node whose degree $k$ has a
value satisfying the relationship

$\left(\frac{1}{2^{\alpha}}-\frac{1}{(H+2)^{\alpha}}\right)k>c,$ (9)

for some integer $H\in\left\\{3,4,5,...\right\\}$, then the equilibrium state
contains at least a node $v$ which is linked to all other nodes of the graph
by no more than $H$ links. This automatically implies that the diameter of the
equilibrium state of the network does not exceed $2H$ and that, therefore,
such an equilibrium state is an ultra-small world state (and, for $H=3$, also
the emergence of the 6 degrees of separation property).

Proof of Theorem 3. The proof is given again by contradiction. i.e. by
supposing that there is a node $u$ in the final state of the network whose
distance from $v$ is at least $H+1$ i.e., $H^{\prime}=l(u,v)\geq H+1$. Then,
the nodes directly connected to $v$ (the neighbors of $v$) may be found at
either $H^{\prime}-1$, or $H^{\prime}$, or $H^{\prime}+1$ edges from $u$. In
the main text, we already discussed that the only contribution to the benefit
function of $v$ from shortest paths ending in $u$ and originating in a
neighbor of $v$ is coming from those paths starting in the neighbors of $v$
that are at distance $H^{\prime}+1$ from $u$. The contribution of these paths
to Eq. (8) satisfies

$\frac{1}{l^{\;\alpha}_{s,u}}\cdot\frac{\sigma_{s,u}(v)}{\sigma_{s,u}}\leq\frac{1}{(H^{\prime}+1)^{\;\alpha}}\leq\frac{1}{(H+2)^{\;\alpha}}.$

This is because $\sigma_{s,u}(v)\leq\sigma_{s,u}$, and $H+2\leq
H^{\prime}+1\leq l_{s,u}$. Therefore, it easily follows that

$WBC(v)\leq\frac{k}{(H+2)^{\;\alpha}}+R,$

where $R$ accounts for the contribution of all other shortest paths in the
network that pass through $v$ and that have not been considered so far.

When a direct link between nodes $v$ and $u$ is added, the shortest path
between any neighbor of $v$ (denoted now generically by $w$) and $u$ becomes
$w-v-u$. Consequently,

$\Delta
WBC(v)\geq\left(\frac{1}{2^{\alpha}}-\frac{1}{(H+2)^{\alpha}}\right)\cdot k,$

because the contribution of the rest of the shortest paths (which do not start
in $w$ and end in $u$) does not decrease (compared to $R$) with the addition
of the new edge (see details of the demonstration in the above Lemma 0). Once
again, let us now recall that the definition of the equilibrium state foresees
explicitly that the gain from adding any edge must be smaller than the cost,
that is,

$c>\Delta
WBC(v)\geq\left(\frac{1}{2^{\alpha}}-\frac{1}{(H+2)^{\alpha}}\right)\cdot k,$

which is in explicit contradiction with condition (9) (quod erat
demonstrandum!).