War pact model of shrinking networks

Autoři: Luka Naglić aff001;  Lovro Šubelj aff002
Působiště autorů: University of Zagreb, Faculty of Science, Zagreb, Croatia aff001;  University of Ljubljana, Faculty of Computer and Information Science, Ljubljana, Slovenia aff002
Vyšlo v časopise: PLoS ONE 14(10)
Kategorie: Research Article
doi: https://doi.org/10.1371/journal.pone.0223480


Many real systems can be described by a set of interacting entities forming a complex network. To some surprise, these have been shown to share a number of structural properties regardless of their type or origin. It is thus of vital importance to design simple and intuitive models that can explain their intrinsic structure and dynamics. These can, for instance, be used to study networks analytically or to construct networks not observed in real life. Most models proposed in the literature are of two types. A model can be either static, where edges are added between a fixed set of nodes according to some predefined rule, or evolving, where the number of nodes or edges increases over time. However, some real networks do not grow but rather shrink, meaning that the number of nodes or edges decreases over time. We here propose a simple model of shrinking networks called the war pact model. We show that networks generated in such a way exhibit common structural properties of real networks. Furthermore, compared to classical models, these resemble international trade, correlates of war, Bitcoin transactions and other networks more closely. Network shrinking may therefore represent a reasonable explanation of the evolution of some networks and greater emphasis should be put on such models in the future.

Klíčová slova:

Clustering coefficients – Community structure – International trade – Network analysis – Random graphs – Scale-free networks – Small world networks – Mesoscopic physics


1. Pastor-Satorras R, Vespignani A. Epidemic spreading in scale-free networks. Phys Rev Lett. 2001;86(14):3200–3203. doi: 10.1103/PhysRevLett.86.3200 11290142

2. Pastor-Satorras R, Vespignani A. Epidemic dynamics and endemic states in complex networks. Phys Rev E. 2001;63(6):066117. doi: 10.1103/PhysRevE.63.066117

3. Milgram S. The small world problem. Psychol Today. 1967;1(1):60–67.

4. Watts DJ, Strogatz SH. Collective dynamics of ‘small-world’ networks. Nature. 1998;393(6684):440–442. doi: 10.1038/30918 9623998

5. Kleinberg JM. Navigation in a small world. Nature. 2000;406(6798):845. doi: 10.1038/35022643 10972276

6. Simini F, González MC, Maritan A, Barabási AL. A universal model for mobility and migration patterns. Nature. 2012;484(7392):96–100. doi: 10.1038/nature10856 22367540

7. Barabási AL, Albert R. Emergence of scaling in random networks. Science. 1999;286(5439):509–512. doi: 10.1126/science.286.5439.509 10521342

8. Solé RV, Ferrer-Cancho R, Montoya JM, Valverde S. Selection, tinkering, and emergence in complex networks. J Complexity. 2003;8(1):20–33.

9. Albert R, Jeong H, Barabasi AL. Error and attack tolerance of complex networks. Nature. 2000;406(6794):378–382. doi: 10.1038/35019019 10935628

10. Liu YY, Slotine JJ, Barabasi AL. Controllability of complex networks. Nature. 2011;473(7346):167–173. doi: 10.1038/nature10011 21562557

11. Fortunato S, Bergstrom CT, Börner K, Evans JA, Helbing D, Milojević S, et al. Science of science. Science. 2018;359(6379):eaao0185. doi: 10.1126/science.aao0185 29496846

12. Barabási AL. The network takeover. Nat Phys. 2012;8(1):14–16. doi: 10.1038/nphys2188

13. Price DDS. A general theory of bibliometric and other cumulative advantage processes. J Am Soc Inf Sci. 1976;27(5):292–306. doi: 10.1002/asi.4630270505

14. Newman MEJ. Assortative mixing in networks. Phys Rev Lett. 2002;89(20):208701. doi: 10.1103/PhysRevLett.89.208701 12443515

15. Newman MEJ. Mixing patterns in networks. Phys Rev E. 2003;67(2):026126. doi: 10.1103/PhysRevE.67.026126

16. Borgatti SP, Everett MG. Models of core/periphery structures. Soc Networks. 2000;21(4):375–395.

17. Newman MEJ, Girvan M. Finding and evaluating community structure in networks. Phys Rev E. 2004;69(2):026113. doi: 10.1103/PhysRevE.69.026113

18. Milo R, Shen-Orr S, Itzkovitz S, Kashtan N, Chklovskii D, Alon U. Network motifs: Simple building blocks of complex networks. Science. 2002;298(5594):824–827. doi: 10.1126/science.298.5594.824 12399590

19. Pržulj N, Corneil DG, Jurisica I. Modeling interactome: Scale-free or geometric? Bioinformatics. 2004;20(18):3508–3515. doi: 10.1093/bioinformatics/bth436 15284103

20. Freeman LC. Centrality in social networks: Conceptual clarification. Soc Networks. 1979;1(3):215–239. doi: 10.1016/0378-8733(78)90021-7

21. Brin S, Page L. The anatomy of a large-scale hypertextual Web search engine. Comput Networks ISDN. 1998;30(1-7):107–117.

22. Erdős P, Rényi A. On random graphs I. Publ Math Debrecen. 1959;6:290–297.

23. Newman MEJ, Strogatz SH, Watts DJ. Random graphs with arbitrary degree distributions and their applications. Phys Rev E. 2001;64(2):026118. doi: 10.1103/PhysRevE.64.026118

24. Clauset A, Moore C, Newman MEJ. Hierarchical structure and the prediction of missing links in networks. Nature. 2008;453(7191):98–101. doi: 10.1038/nature06830 18451861

25. D’Souza RM, Borgs C, Chayes JT, Berger N, Kleinberg RD. Emergence of tempered preferential attachment from optimization. P Natl Acad Sci USA. 2007;104(15):6112–6117. doi: 10.1073/pnas.0606779104

26. Holland PW, Laskey KB, Leinhardt S. Stochastic blockmodels: First steps. Soc Networks. 1983;5(2):109–137. doi: 10.1016/0378-8733(83)90021-7

27. Kleinberg JM, Kumar R, Raghavan P, Rajagopalan S, Tomkins AS. The web as a graph: Measurements, models, and methods. In: Proceedings of the International Conference on Computing and Combinatorics. Tokyo, Japan; 1999. p. 1–17.

28. Kejžar N, Nikoloski Z, Batagelj V. Probabilistic inductive classes of graphs. J Math Sociol. 2008;32(2):85–109. doi: 10.1080/00222500801931586

29. Dorogovtsev SN, Mendes JFF. Evolution of networks. Adv Phys. 2002;51(4):1079–1187. doi: 10.1080/00018730110112519

30. Peixoto TP. Bayesian stochastic blockmodeling. In: Doreian P, Batagelj V, Ferligoj A, editors. Advances in Network Clustering and Blockmodeling. New York: Wiley; 2019. p. 281–324.

31. Adai AT, Date SV, Wieland S, Marcotte EM. LGL: Creating a map of protein function with an algorithm for visualizing very large biological networks. J Mol Biol. 2004;340(1):179–190. doi: 10.1016/j.jmb.2004.04.047 15184029

32. De Domenico M, Nicosia V, Arenas A, Latora V. Structural reducibility of multilayer networks. Nat Commun. 2015;6:6864. doi: 10.1038/ncomms7864 25904309

33. Doreian P, Mrvar A. Structural balance and signed international relations. J Soc Struct. 2015;16:2.

34. Kondor D, Csabai I, Szüle J, Pósfai M, Vattay G. Inferring the interplay between network structure and market effects in Bitcoin. New J Phys. 2014;16(12):125003. doi: 10.1088/1367-2630/16/12/125003

35. Leskovec J, Kleinberg J, Faloutsos C. Graph evolution: Densification and shrinking diameters. ACM Trans Knowl Discov Data. 2007;1(1):1–41. doi: 10.1145/1217299.1217301

36. Girvan M, Newman MEJ. Community structure in social and biological networks. P Natl Acad Sci USA. 2002;99(12):7821–7826. doi: 10.1073/pnas.122653799

37. Traag VA, Waltman L, Van Eck NJ. From Louvain to Leiden: Guaranteeing well-connected communities. Sci Rep. 2019;9:5233. doi: 10.1038/s41598-019-41695-z 30914743

38. Faloutsos M, Faloutsos P, Faloutsos C. On power-law relationships of the Internet topology. Comput Commun Rev. 1999;29(4):251–262. doi: 10.1145/316194.316229

39. Schieber TA, Carpi L, Díaz-Guilera A, Pardalos PM, Masoller C, Ravetti MG. Quantification of network structural dissimilarities. Nat Commun. 2017;8:13928. doi: 10.1038/ncomms13928 28067266

40. Bagrow JP, Bollt EM. An information-theoretic, all-scales approach to comparing networks. e-print arXiv:180403665v1. 2018; p. 1–18.

41. Bagrow JP, Bollt EM, Skufca JD, ben Avraham D. Portraits of complex networks. Europhys Lett. 2008;81(6):68004. doi: 10.1209/0295-5075/81/68004

42. Laurienti PJ, Joyce KE, Telesford QK, Burdette JH, Hayasaka S. Universal fractal scaling of self-organized networks. Physica A. 2011;390(20):3608–3613. doi: 10.1016/j.physa.2011.05.011 21808445

43. Clauset A, Shalizi CR, Newman MEJ. Power-law distributions in empirical data. SIAM Rev. 2009;51(4):661–703. doi: 10.1137/070710111

44. Zhou S, Mondragon RJ. The rich-club phenomenon in the Internet topology. IEEE Commun Lett. 2004;8(3):180–182. doi: 10.1109/LCOMM.2004.823426

45. Broido AD, Clauset A. Scale-free networks are rare. Nat Commun. 2019;10(1):1017. doi: 10.1038/s41467-019-08746-5 30833554

46. Voitalov I, van der Hoorn P, van der Hofstad R, Krioukov D. Scale-free networks well done. e-print arXiv:181102071v1. 2018; p. 1–31.

47. Soffer SN, Vázquez A. Network clustering coefficient without degree-correlation biases. Phys Rev E. 2005;71(5):057101. doi: 10.1103/PhysRevE.71.057101

48. Newman MEJ. Networks. 2nd ed. Oxford: Oxford University Press; 2018.

Článek vyšel v časopise


2019 Číslo 10
Nejčtenější tento týden