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


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:

Aging – Clustering coefficients – Community structure – Eigenvalues – Network analysis – Protein interaction networks – Social networks – Operator theory


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.

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ánek vyšel v časopise


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