MSP-N: Multiple selection procedure with ‘N’ possible growth mechanisms
Autoři:
Pradumn Kumar Pandey aff001; Mayank Singh aff002
Působiště autorů:
Computer Science and Engineering, Indian Institute of Technology Roorkee, Roorkee, Uttrakhand, India
aff001; Computer Science and Engineering, Indian Institute of Technology Gandhinagar, Gandhinagar, Gujarat, India
aff002
Vyšlo v časopise:
PLoS ONE 14(12)
Kategorie:
Research Article
prolekare.web.journal.doi_sk:
https://doi.org/10.1371/journal.pone.0224383
Souhrn
Network modeling is a challenging task due to non-trivial evolution dynamics. We introduce multiple-selection-procedure with ‘N’ possible growth mechanisms (MSP-N). In MSP-N, an incoming node chooses a single option among N available options to link to pre-existing nodes. Some of the potential options, in case of social networks, can be standard preferential or random attachment and node aging or fitness. In this paper, we discuss a specific case, MSP-2, and shows its efficacy in reconstructing several non-trivial characteristic properties of social networks, including networks with power-law degree distribution, power-law with an exponential decay (exponential cut-off), and exponential degree distributions. We evaluate the proposed evolution mechanism over two real-world networks and observe that the generated networks highly resembles the degree distribution of the real-world networks. Besides, several other network properties such as high clustering and triangle count, low spectral radius, and community structure, of the generated networks are significantly closer to the real-world networks.
Klíčová slova:
Network analysis – Community structure – Aging – Eigenvalues – Social networks – Clustering coefficients – Protein interaction networks – Operator theory
Zdroje
1. Newman M. Networks: an introduction. Oxford University Press; 2010.
2. Barabási AL, Albert R, Jeong H. Scale-free characteristics of random networks: the topology of the world-wide web. Physica A: statistical mechanics and its applications. 2000;281(1):69–77.
3. Asur S, Ucar D, Parthasarathy S. An ensemble framework for clustering protein–protein interaction networks. Bioinformatics. 2007;23(13):i29–i40. doi: 10.1093/bioinformatics/btm212 17646309
4. Wu J, Vallenius T, Ovaska K, Westermarck J, Mäkelä TP, Hautaniemi S. Integrated network analysis platform for protein-protein interactions. Nature methods. 2009;6(1):75–77. doi: 10.1038/nmeth.1282 19079255
5. Amaral LAN, Scala A, Barthelemy M, Stanley HE. Classes of small-world networks. Proceedings of the national academy of sciences. 2000;97(21):11149–11152. doi: 10.1073/pnas.200327197
6. Newman ME. The structure of scientific collaboration networks. Proceedings of the National Academy of Sciences. 2001;98(2):404–409. doi: 10.1073/pnas.98.2.404
7. Leskovec J, Mcauley JJ. Learning to discover social circles in ego networks. In: Advances in neural information processing systems; 2012. p. 539–547.
8. 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
9. Bollobás B, Riordan O. The diameter of a scale-free random graph. Combinatorica. 2004;24(1):5–34. doi: 10.1007/s00493-004-0002-2
10. Broder A, Kumar R, Maghoul F, Raghavan P, Rajagopalan S, Stata R, et al. Graph structure in the web. Computer networks. 2000;33(1):309–320. doi: 10.1016/S1389-1286(00)00083-9
11. Chung F, Lu L. The average distances in random graphs with given expected degrees. Proceedings of the National Academy of Sciences. 2002;99(25):15879–15882. doi: 10.1073/pnas.252631999
12. Kleinberg J. Small-world phenomena and the dynamics of information. Advances in neural information processing systems. 2002;1:431–438.
13. Milgram S. The small world problem. Psychology today. 1967;2(1):60–67.
14. Watts DJ, Strogatz SH. Collective dynamics of ‘small-world’networks. Nature. 1998;393(6684):440–442. doi: 10.1038/30918 9623998
15. Martinez ND. Artifacts or attributes? Effects of resolution on the Little Rock Lake food web. Ecological Monographs. 1991; p. 367–392. doi: 10.2307/2937047
16. 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
17. Huxham M, Beaney S, Raffaelli D. Do parasites reduce the chances of triangulation in a real food web? Oikos. 1996; p. 284–300. doi: 10.2307/3546201
18. Newman ME, Girvan M. Finding and evaluating community structure in networks. Physical review E. 2004;69(2):026113. doi: 10.1103/PhysRevE.69.026113
19. Barabási AL, et al. Scale-free networks: a decade and beyond. Science. 2009;325(5939):412. doi: 10.1126/science.1173299 19628854
20. Eguiluz VM, Chialvo DR, Cecchi GA, Baliki M, Apkarian AV. Scale-free brain functional networks. Physical review letters. 2005;94(1):018102. doi: 10.1103/PhysRevLett.94.018102 15698136
21. Luce RD, Perry AD. A method of matrix analysis of group structure. Psychometrika. 1949;14(2):95–116. doi: 10.1007/bf02289146 18152948
22. Li W, Schuurmans D. Modular community detection in networks. In: Twenty-Second International Joint Conference on Artificial Intelligence; 2011.
23. Pandey PK, Adhikari B. A parametric model approach for structural reconstruction of scale-free networks. IEEE Transactions on Knowledge and Data Engineering. 2017;29(10):2072–2085. doi: 10.1109/TKDE.2017.2725264
24. Dorogovtsev SN, Mendes JFF. Evolution of networks with aging of sites. Physical Review E. 2000;62(2):1842. doi: 10.1103/PhysRevE.62.1842
25. Dorogovtsev S, Mendes J, Samukhin A. Size-dependent degree distribution of a scale-free growing network. Physical Review E. 2001;63(6):062101. doi: 10.1103/PhysRevE.63.062101
26. Chakrabarti D, Faloutsos C. Graph mining: Laws, generators, and algorithms. ACM computing surveys (CSUR). 2006;38(1):2. doi: 10.1145/1132952.1132954
27. Toivonen R, Onnela JP, Saramäki J, Hyvönen J, Kaski K. A model for social networks. Physica A: Statistical Mechanics and its Applications. 2006;371(2):851–860. doi: 10.1016/j.physa.2006.03.050
28. Kossinets G, Watts DJ. Empirical analysis of an evolving social network. Science. 2006;311(5757):88–90. doi: 10.1126/science.1116869 16400149
29. Jackson MO. A survey of network formation models: stability and efficiency. Group Formation in Economics: Networks, Clubs, and Coalitions. 2005; p. 11–49.
30. Slikker M, van den Nouweland A. Network formation models with costs for establishing links. Review of Economic Design. 2000;5(3):333–362. doi: 10.1007/PL00013692
31. Bornholdt S, Rohlf T. Topological evolution of dynamical networks: Global criticality from local dynamics. Physical Review Letters. 2000;84(26):6114. doi: 10.1103/PhysRevLett.84.6114 10991137
32. Barabâsi AL, Jeong H, Néda Z, Ravasz E, Schubert A, Vicsek T. Evolution of the social network of scientific collaborations. Physica A: Statistical mechanics and its applications. 2002;311(3):590–614.
33. Pandey PK, Adhikari B. Context dependent preferential attachment model for complex networks. Physica A: Statistical Mechanics and its Applications. 2015;436:499–508. doi: 10.1016/j.physa.2015.04.038
34. Simon HA. On a class of skew distribution functions. Biometrika. 1955;42(3/4):425–440. doi: 10.2307/2333389
35. Price DdS. A general theory of bibliometric and other cumulative advantage processes. Journal of the American society for Information science. 1976;27(5):292–306. doi: 10.1002/asi.4630270505
36. Abello J, Buchsbaum AL, Westbrook JR. A functional approach to external graph algorithms. In: Algorithms—ESA’98. Springer; 1998. p. 332–343.
37. Faloutsos M, Faloutsos P, Faloutsos C. On power-law relationships of the internet topology. In: ACM SIGCOMM computer communication review. vol. 29. ACM; 1999. p. 251–262.
38. Huberman BA, Adamic LA. Internet: growth dynamics of the world-wide web. Nature. 1999;401(6749):131–131. doi: 10.1038/43604
39. Kumar R, Raghavan P, Rajagopalan S, Tomkins A. Trawling the Web for emerging cyber-communities. Computer networks. 1999;31(11):1481–1493. doi: 10.1016/S1389-1286(99)00040-7
40. Bi Z, Faloutsos C, Korn F. The DGX distribution for mining massive, skewed data. In: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining. ACM; 2001. p. 17–26.
41. Chakrabarti D, Zhan Y, Faloutsos C. R-MAT: A Recursive Model for Graph Mining. In: SDM. vol. 4. SIAM; 2004. p. 442–446.
42. Christensen K, Donangelo R, Koiller B, Sneppen K. Evolution of random networks. Physical Review Letters. 1998;81(11):2380. doi: 10.1103/PhysRevLett.81.2380
43. Krapivsky PL, Redner S, Leyvraz F. Connectivity of growing random networks. Physical review letters. 2000;85(21):4629. doi: 10.1103/PhysRevLett.85.4629 11082613
44. Ohtsuki H, Hauert C, Lieberman E, Nowak MA. A simple rule for the evolution of cooperation on graphs and social networks. Nature. 2006;441(7092):502–505. doi: 10.1038/nature04605 16724065
45. Krapivsky PL, Redner S. Organization of growing random networks. Physical Review E. 2001;63(6):066123. doi: 10.1103/PhysRevE.63.066123
46. Dorogovtsev SN, Goltsev AV, Mendes JFF. Pseudofractal scale-free web. Physical Review E. 2002;65(6):066122. doi: 10.1103/PhysRevE.65.066122
47. Dorogovtsev SN, Goltsev AV, Mendes JFF. Ising model on networks with an arbitrary distribution of connections. Physical Review E. 2002;66(1):016104. doi: 10.1103/PhysRevE.66.016104
48. Dorogovtsev SN, Mendes JFF. Effect of the accelerating growth of communications networks on their structure. Physical Review E. 2001;63(2):025101.
49. Leskovec J, Krevl A. SNAP Datasets: Stanford Large Network Dataset Collection; 2014. http://snap.stanford.edu/data.
50. Singh M, Sarkar R, Goyal P, Mukherjee A, Chakrabarti S. Relay-linking models for prominence and obsolescence in evolving networks. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM; 2017. p. 1077–1086.
51. Singh M, Sarkar R, Goyal P, Mukherjee A, Chakrabarti S. Sic Transit Gloria Manuscriptum: Two Views of the Aggregate Fate of Ancient Papers. arXiv preprint arXiv:151108310. 2015;.
52. Zhu H, Wang X, Zhu JY. Effect of aging on network structure. Phys Rev E. 2003;68:056121. doi: 10.1103/PhysRevE.68.056121
53. Kumar R, Raghavan P, Rajagopalan S, Sivakumar D, Tomkins A, Upfal E. Random graph models for the web graph. In: FOCS; 2000. p. 57–65.
54. König MD, Tessone CJ, Zenou Y. From assortative to dissortative networks: the role of capacity constraints. Advances in Complex Systems. 2010;13(04):483–499. doi: 10.1142/S0219525910002700
55. Battiston P. Constrained Network Formation. Italian Economic Journal. 2016;2(3):347–362. doi: 10.1007/s40797-016-0040-0
56. Barabási AL, Albert R, Jeong H. Mean-field theory for scale-free random networks. Physica A: Statistical Mechanics and its Applications. 1999;272(1):173–187.
57. Leskovec J, Kleinberg J, Faloutsos C. Graphs over time: densification laws, shrinking diameters and possible explanations. In: Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining. ACM; 2005. p. 177–187.
58. Girvan M, Newman ME. Community structure in social and biological networks. Proceedings of the national academy of sciences. 2002;99(12):7821–7826. doi: 10.1073/pnas.122653799
59. Blondel V, Guillaume J, Lambiotte R, Lefebvre E. Fast Unfolding of Community Hierarchies in large network. J Stat Mech P. 2008;1008.
60. Jamakovic A. Characterization of complex networks: application to robustness analysis. 2008;.
61. Chung FR, Graham FC. Spectral graph theory. 92. American Mathematical Soc.; 1997.
Článok vyšiel v časopise
PLOS One
2019 Číslo 12
- Metamizol jako analgetikum první volby: kdy, pro koho, jak a proč?
- Nejasný stín na plicích – kazuistika
- Těžké menstruační krvácení může značit poruchu krevní srážlivosti. Jaký management vyšetření a léčby je v takovém případě vhodný?
- Ne každé mimoděložní těhotenství musí končit salpingektomií
- Masturbační chování žen v ČR − dotazníková studie
Najčítanejšie v tomto čísle
- Methylsulfonylmethane increases osteogenesis and regulates the mineralization of the matrix by transglutaminase 2 in SHED cells
- Oregano powder reduces Streptococcus and increases SCFA concentration in a mixed bacterial culture assay
- Parametric CAD modeling for open source scientific hardware: Comparing OpenSCAD and FreeCAD Python scripts
- The characteristic of patulous eustachian tube patients diagnosed by the JOS diagnostic criteria
Zvýšte si kvalifikáciu online z pohodlia domova
Všetky kurzy