Skip to main content
SpringerLink
Log in

Directed triadic closure and edge deletion mechanism induce asymmetry in directed edge properties

  • Regular Article
  • Published:
The European Physical Journal B Aims and scope Submit manuscript

Abstract

Many directed real world networks, such as the WWW, genetic regulation networks and economic networks exhibit significant differences between the properties of the incoming and outgoing edges, while the differences exhibited by other networks, such as Social Netw. are far more limited. This phenomenon is most evident in the differences between the distributions of incoming and outgoing degrees and direct clustering coefficients. There is currently no generic network generation model that would reproduce and tune these observed dissimilarities. We propose and empirically validate a simple and realistic model that can explain the emergence of the dissimilarities between the incoming and outgoing network degrees and clustering coefficients by combining directed triadic closure, random edge addition and directed edge removal. Surprisingly, we find that the difference between in and out degree distributions is attributed to asymmetries in the edge removal, highlighting the neglected yet crucial importance of edge removal mechanisms to the static and dynamic properties of real world networks. The model is governed by only two parameters: the first tunes the randomness of the edge addition mechanism, while the second controls the difference between the in and out degrees. The combination of these parameters reproduces the observed variety of directed degree distributions and clustering coefficients. Further comparisons of the model’s microscopic dynamics against the empirically observed evolution of real world social network confirms that while quite simple, the model properly describes both the edge addition and deletion processes in directed networks.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. A.-L. Barabási, R. Albert, Science 286, 509 (1999)

    Article  ADS  MathSciNet  Google Scholar 

  2. H. Brot et al., Physica A 391, 6645 (2012)

    Article  ADS  Google Scholar 

  3. D. Garlaschelli, M.I. Loffredo, Phys. Rev. Lett. 93, 268701 (2004)

    Article  ADS  Google Scholar 

  4. J. Jost, M.P. Joy, Phys. Rev. E 66, 036126 (2002)

    Article  ADS  MathSciNet  Google Scholar 

  5. S. Kauffman et al., Proc. Natl. Acad. Sci. 100, 14796 (2003)

    Article  ADS  Google Scholar 

  6. A. Mirshahvalad, M. Rosvall, Phys. Rev. E 84, 036102 (2011)

    Article  ADS  Google Scholar 

  7. A. Vázquez, Phys. Rev. E 67, 056104 (2003)

    Article  ADS  Google Scholar 

  8. D. Fraiman, Eur. Phys. J. B 61, 377 (2008)

    Article  ADS  MATH  Google Scholar 

  9. B. Kahng, Y. Park, H. Jeong, Phys. Rev. E 66, 046107 (2002)

    Article  ADS  Google Scholar 

  10. J. Liu et al., Physica A 371, 861 (2006)

    Article  ADS  Google Scholar 

  11. G. Rodgers, K. Darby-Dowman, Eur. Phys. J. B 23, 267 (2001)

    Article  ADS  Google Scholar 

  12. H. Ebel, L.-I. Mielsch, S. Bornholdt, Phys. Rev. E 66, 035103 (2002)

    Article  ADS  Google Scholar 

  13. M.E. Newman, S. Forrest, J. Balthrop, Phys. Rev. E 66, 035101 (2002)

    Article  ADS  Google Scholar 

  14. S. Bernhardsson, P. Minnhagen, Phys. Rev. E 74, 026104 (2006)

    Article  ADS  Google Scholar 

  15. A. Grönlund, Phys. Rev. E 70, 061908 (2004)

    Article  ADS  Google Scholar 

  16. O. Popa et al., Genome Res. 21, 599 (2011)

    Article  Google Scholar 

  17. L.G. Morelli, Phys. Rev. E 67, 066107 (2003)

    Article  ADS  Google Scholar 

  18. M. Kimura, K. Saito, N. Ueda, Neural Netw. 17, 975 (2004)

    Article  MATH  Google Scholar 

  19. E.A. Leicht et al., Eur. Phys. J. B 59, 75 (2007)

    Article  ADS  MATH  Google Scholar 

  20. S.J. Brams, H. Mutlu, S.L. Ramirez, Studies Conflict Terrorism 29, 703 (2006)

    Article  Google Scholar 

  21. B. Gonçalves, N. Perra, A. Vespignani, PLoS One 6, e22656 (2011)

    Article  ADS  Google Scholar 

  22. H. Kwak et al., What is Twitter, a Social network or a News Media? in Proceedings of the 19th international conference on World wide web (ACM, 2010)

  23. V. Satuluri, S. Parthasarathy, Symmetrizations for clustering directed graphs, in Proceedings of the 14th International Conference on Extending Database Technology (ACM, 2011)

  24. M. Moslonka-Lefebvre, M. Pautasso, M.J. Jeger, J. Theor. Biol. 260, 402 (2009)

    Article  MathSciNet  Google Scholar 

  25. M. Pautasso, M.J. Jeger, Ecol. Complexity 5, 1 (2008)

    Article  Google Scholar 

  26. A.D. Sánchez, J.M. López, M.A. Rodriguez, Phys. Rev. Lett. 88, 048701 (2002)

    Article  ADS  Google Scholar 

  27. R. Itzhack et al., Physica A 389, 5308 (2010)

    Article  ADS  Google Scholar 

  28. L. Muchnik et al., Phys. Rev. E 76, 016106 (2007)

    Article  ADS  Google Scholar 

  29. Y. Rosen, Y. Louzoun, Physica A 401, 118 (2014)

    Article  ADS  MathSciNet  Google Scholar 

  30. S. Ahnert, T. Fink, Phys. Rev. E 78, 036112 (2008)

    Article  ADS  Google Scholar 

  31. S.M. Park, B.J. Kim, Phys. Rev. E 74, 026114 (2006)

    Article  ADS  Google Scholar 

  32. A. Broder et al., Comput. Netw. 33, 309 (2000)

    Article  Google Scholar 

  33. M.E.J. Newman, SIAM Rev. 45, 167 (2003)

    Article  ADS  MATH  MathSciNet  Google Scholar 

  34. P. Krapivsky, G. Rodgers, S. Redner, Phys. Rev. Lett. 86, 5401 (2001)

    Article  ADS  Google Scholar 

  35. S.-W. Son et al., Phys. Rev. E 86, 046104 (2012)

    Article  ADS  Google Scholar 

  36. R. Itzhack, Y. Mogilevski, Y. Louzoun, Physica A 381, 482 (2007)

    Article  ADS  Google Scholar 

  37. R. Milo et al., Science 298, 824 (2002)

    Article  ADS  Google Scholar 

  38. J.-P. Onnela et al., Phys. Rev. E 71, 065103 (2005)

    Article  ADS  Google Scholar 

  39. C. Seshadhri, et al., arXiv:1302.6220 (2013)

  40. G. Fagiolo, Phys. Rev. E 76, 026107 (2007)

    Article  ADS  Google Scholar 

  41. J.G. Foster et al., Proc. Natl. Acad. Sci. 107, 10815 (2010)

    Article  ADS  Google Scholar 

  42. A. Ramezanpour, V. Karimipour, Phys. Rev. E 66, 036128 (2002)

    Article  ADS  Google Scholar 

  43. B. Georgeot, O. Giraud, D.L. Shepelyansky, Phys. Rev. E 81, 056109 (2010)

    Article  ADS  Google Scholar 

  44. S.M. Goodreau, Social Netw. 29, 231 (2007)

    Article  Google Scholar 

  45. G. Robins et al., Social Netw. 29, 173 (2007)

    Article  Google Scholar 

  46. T.A. Snijders, G.G. Van de Bunt, C.E. Steglich, Social Netw. 32, 44 (2010)

    Article  Google Scholar 

  47. Y. Louzoun, L. Muchnik, S. Solomon, Bioinformatics 22, 581 (2006)

    Article  Google Scholar 

  48. A.-X. Cui et al., PLoS One 7, e50702 (2012)

    Article  ADS  Google Scholar 

  49. N. Gondal, Social Netw. 33, 20 (2011)

    Article  Google Scholar 

  50. P.N. Krivitsky, M.S. Handcock, M. Morris, Statistical Methodology 8, 319 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  51. G. Robins, P. Pattison, P. Wang, Social Netw. 31, 105 (2009)

    Article  Google Scholar 

  52. P. Wang et al., Social Netw. 35, 96 (2013)

    Article  Google Scholar 

  53. J. Davidsen, H. Ebel, S. Bornholdt, Phys. Rev. Lett. 88, 128701 (2002)

    Article  ADS  Google Scholar 

  54. J.M. Kumpula et al., Phys. Rev. Lett. 99, 228701 (2007)

    Article  ADS  Google Scholar 

  55. M. Marsili, F. Vega-Redondo, F. Slanina, Proc. Natl. Acad. Sci. USA 101, 1439 (2004)

    Article  ADS  MATH  MathSciNet  Google Scholar 

  56. R. Toivonen et al., Social Netw. 31, 240 (2009)

    Article  Google Scholar 

  57. E. Volz, Phys. Rev. E 70, 056115 (2004)

    Article  ADS  Google Scholar 

  58. G. Csányi, B. Szendröi, Phys. Rev. E 69, 036131 (2004)

    Article  ADS  Google Scholar 

  59. J.M. Kumpula et al., Phys. Rev. Lett. 99, 228701 (2007)

    Article  ADS  Google Scholar 

  60. M. Li et al., Physica A 375, 355 (2007)

    Article  ADS  Google Scholar 

  61. K. Yuta, N. Ono, Y. Fujiwara, arXiv:physics/0701168 (2007)

  62. D.J. Watts, S.H. Strogatz, Nature 393, 440 (1998)

    Article  ADS  Google Scholar 

  63. H. Brot et al., Physica A 391, 6645 (2012)

    Article  ADS  Google Scholar 

  64. J. Cheng, A.W. Fu, J. Liu, K-isomorphism: privacy preserving network publication against structural attacks, in Proceedings of the 2010 international conference on Management of data (ACM, 2010)

  65. K. Park, Y.C. Lai, N. Ye, Phys. Rev. E 72, 026131 (2005)

    Article  ADS  Google Scholar 

  66. B. Rudolf et al., Phys. Rev. E 85, 026114 (2012)

    Article  ADS  Google Scholar 

  67. S. Gollapudi, K. Kenthapadi, R. Panigrahy, Threshold phenomena in the evolution of communities in Social Netw., in 17th International World Wide Web conference (WWW2008), Workshop on social web search and mining (swsM2008) (Citeseer, 2008)

  68. M. Cavaliere et al., J. Theor. Biol. 299, 126 (2011)

    Article  MathSciNet  Google Scholar 

  69. W. Miura, H. Takayasu, M. Takayasu, Phys. Rev. Lett. 108, 168701 (2012)

    Article  ADS  Google Scholar 

  70. M. Deijfen, M. Lindholm, Physica A 388, 4297 (2009)

    Article  ADS  Google Scholar 

  71. H. Brot et al., Phys. Rev. E 88, 042815 (2013)

    Article  ADS  Google Scholar 

  72. K.L. Morrow, T. Rowland, C.M. Danforth, Phys. Rev. E 80, 016103 (2009)

    Article  ADS  MathSciNet  Google Scholar 

  73. P. Holme, B.J. Kim, Phys. Rev. E 65, 026107 (2002)

    Article  ADS  Google Scholar 

  74. P. Klimek, S. Thurner, New J. Phys. 15, 063008 (2013)

    Article  ADS  MathSciNet  Google Scholar 

  75. R. Toivonen et al., Physica A 371, 851 (2006)

    Article  ADS  Google Scholar 

  76. A.T. Stephen, O. Toubia, Social Netw. 31, 262 (2009)

    Article  Google Scholar 

  77. M. Szell, R. Lambiotte, S. Thurner, Proc. Natl. Acad. Sci. 107, 13636 (2010)

    Article  ADS  Google Scholar 

  78. A.L. Ter Wal, R.A. Boschma, Ann. Regional Sci. 43, 739 (2009)

    Article  Google Scholar 

  79. R. Albert, A.-L. Barabási, Rev. Mod. Phys. 74, 47 (2002)

    Article  ADS  MATH  Google Scholar 

  80. M.E. Newman, SIAM Rev. 45, 167 (2003)

    Article  ADS  MATH  MathSciNet  Google Scholar 

  81. T. Squartini, D. Garlaschelli, in Triadic motifs and dyadic self-organization in the World Trade Network, in Self-Organizing Systems (Springer, 2012), pp. 24–35

  82. Q. Chen, D. Shi, Physica A 335, 240 (2004)

    Article  ADS  MathSciNet  Google Scholar 

  83. J.S. Kong, V.P. Roychowdhury, Physica A 387, 3335 (2008)

    Article  ADS  Google Scholar 

  84. S. Saavedra, F. Reed-Tsochas, B. Uzzi, Proc. Natl. Acad. Sci. 105, 16466 (2008)

    Article  ADS  Google Scholar 

  85. D. Shi et al., Europhys. Lett. 76, 731 (2006)

    Article  ADS  Google Scholar 

  86. S. Mangan, U. Alon, Proc. Natl. Acad. Sci. 100, 11980 (2003)

    Article  ADS  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Gonda Brain Research Center, Bar-Ilan University, 52900, Ramat Gan, Israel

    Hilla Brot & Yoram Louzoun

  2. Northwestern Institute on Complex Systems, Northwestern University, Evanston, Illinois, 60208, USA

    Hilla Brot

  3. School of Business Administration, Hebrew University, Jerusalem, Israel

    Lev Muchnik

  4. Department of Mathematics, Bar-Ilan University, 52900, Ramat Gan, Israel

    Yoram Louzoun

Authors
  1. Hilla Brot
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lev Muchnik
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yoram Louzoun
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Hilla Brot or Yoram Louzoun.

Electronic supplementary material

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Brot, H., Muchnik, L. & Louzoun, Y. Directed triadic closure and edge deletion mechanism induce asymmetry in directed edge properties. Eur. Phys. J. B 88, 12 (2015). https://doi.org/10.1140/epjb/e2014-50220-4

Download citation

  • Received:

  • Revised:

  • Published:

  • DOI: https://doi.org/10.1140/epjb/e2014-50220-4

Keywords

Search

Navigation