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
Souhrn
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
Zdroje
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
PLOS One
2019 Číslo 10
- S diagnostikou Parkinsonovy nemoci může nově pomoci AI nástroj pro hodnocení mrkacího reflexu
- Je libo čepici místo mozkového implantátu?
- Pomůže v budoucnu s triáží na pohotovostech umělá inteligence?
- AI může chirurgům poskytnout cenná data i zpětnou vazbu v reálném čase
- Nová metoda odlišení nádorové tkáně může zpřesnit resekci glioblastomů
Nejčtenější v tomto čísle
- Correction: Low dose naltrexone: Effects on medication in rheumatoid and seropositive arthritis. A nationwide register-based controlled quasi-experimental before-after study
- Combining CDK4/6 inhibitors ribociclib and palbociclib with cytotoxic agents does not enhance cytotoxicity
- Experimentally validated simulation of coronary stents considering different dogboning ratios and asymmetric stent positioning
- Risk factors associated with IgA vasculitis with nephritis (Henoch–Schönlein purpura nephritis) progressing to unfavorable outcomes: A meta-analysis
Zvyšte si kvalifikaci online z pohodlí domova
Všechny kurzy