Assortifying Networks | New Generation Computing Skip to main content
Springer Nature Link
Log in

Assortifying Networks

  • Published:
New Generation Computing Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

Since its introduction, the concept of assortativity has proved to be a fundamental metric for understanding the structure and function of complex networks. It has been shown to have a significant impact on many processes on networks, including epidemic thresholds, spreading, and longevity, congestion relief, and information cascades. In a number of these results, the degree distribution (usually a power-law distribution) plays a critical role. We describe a simple but effective method for modifying a given network so as to either increase or decrease its assortativity while preserving the degree distribution of the network. The process is easily controlled to yield desired assortativities. A modification is given which not only preserves the degree of every vertex but also respects a given community structure on the network. Both algorithms are supported by detailed empirical results. The constructions should be of particular value to investigators seeking to measure the impact of assortativity in various applications without disturbing the overall degree distribution or community decompositions.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Albert, R., “Scale-free networks in cell biology,” Journal of cell science, 118, 21, pp. 4947–4957, 2005.

  2. Badham, J. and Stocker, R., “The impact of network clustering and assortativity on epidemic behaviour,” Theoretical population biology, 77, 1, pp. 71–75, 2010.

  3. Barabási, A.-L. and Albert, R., “Emergence of scaling in random networks,” Science, 286, 5439, pp. 509–512, 1999.

  4. Barthélemy M, Barrat A, Pastor-Satorras R, Vespignani A: “Velocity and hierarchical spread of epidemic outbreaks in scalefree networks,”. Physical Review Letters 92(17), 178701 (2004)

    Article  Google Scholar 

  5. Blondel V.D, Guillaume J.-L, Lambiotte R, Lefebvre E: “Fast unfolding of communities in large networks,” Journal of Statistical Mechanics:. Theory and Experiment 2008(10), P10008 (2008)

    Google Scholar 

  6. Brandes, U., Delling, D., Gaertler, M., Gorke, R., Hoefer, M., Nikoloski, Z. and Wagner, D., “On modularity clustering,” Knowledge and Data Engineering, IEEE Transactions on, 20, 2, pp. 172–188, 2008.

  7. Clauset A, Newman M.E.J, Moore C: “Finding community structure in very large networks,” . Physical review E 70(6), 066111 (2004)

    Article  Google Scholar 

  8. Crucitti, P., Latora, V., Marchiori, M. and Rapisarda, A., “Efficiency of scale-free networks: error and attack tolerance,” Physica A: Statistical Mechanics and its Applications, 320, pp. 622–642, 2003.

  9. D’Agostino G, Scala A, Zlatić V, Caldarelli G: “Robustness and assortativity for diffusion-like processes in scale-free networks,” EPL . (Europhysics Letters.) 97(6), 68006 (2012)

    Article  Google Scholar 

  10. Dezső Z, Barabási A.-L: “Halting viruses in scale-free networks,”. Physical Review E 65(5), 055103 (2002)

    Article  Google Scholar 

  11. Ebel, H., Mielsch, L.-I. and Bornholdt, S., “Scale-free topology of e-mail networks,” arXiv preprint cond-mat/0201476, 2002.

  12. Fortunato, S., “Community detection in graphs,” Physics Reports, 486, 3, pp. 75–174, 2010.

  13. igraph. http://igraph.sourceforge.net.

  14. Jeong, H., Tombor, B., Albert, R., Oltvai, Z. N. and Barabási, A-L., “The large-scale organization of metabolic networks,” Nature, 407, 6804, pp. 651–654, 2000.

  15. May R.M, Lloyd A.L: “Infection dynamics on scale-free networks,”. Physical Review E 64(6), 066112 (2001)

    Article  Google Scholar 

  16. Miller J.C: “Percolation and epidemics in random clustered networks,”. Physical Review E 80(2), 020901 (2009)

    Article  MathSciNet  Google Scholar 

  17. Moreno Y, Gómez J.B, Pacheco A.F: “Epidemic incidence in correlated complex networks,” . Physical Review E 68(3), 035103 (2003)

    Article  Google Scholar 

  18. Newman M.E.J: “Finding community structure in networks using the eigenvectors of matrices,”. Physical review E 74(3), 036104 (2006)

    Article  MathSciNet  Google Scholar 

  19. Newman M.E.J., Girvan M.: “Finding and evaluating community structure in networks,” . Physical review E 69(2), 026113 (2004)

    Article  Google Scholar 

  20. Newman M.E.J.: “Assortative mixing in networks,” . Physical Review Letters 89(20), 208701 (2002)

    Article  Google Scholar 

  21. Onnela, J-P, Saramäki, J., Hyvönen, J., Szabó, G., Lazer, D., Kaski, K., Kertész, J., and Barabási, A-L., “Structure and tie strengths in mobile communication networks,” Proc. of the National Academy of Sciences, 104, 18, pp. 7332–7336, 2007.

  22. Pajek. http://pajek.imfm.si.

  23. Pastor-Satorras R., Vespignani A.: “Epidemic spreading in scale-free networks,” . Physical review letters 86(14), 3200 (2001)

    Article  Google Scholar 

  24. Pastor-Satorras R., Vespignani A.: “Epidemic dynamics in finite size scale-free networks,” . Physical Review E 65(3), 035108 (2002)

    Article  Google Scholar 

  25. Payne J. L., Dodds P.S., Eppstein M.J.: “Information cascades on degree-correlated random networks.” . Physical Review E 80(2), 026125 (2009)

    Article  Google Scholar 

  26. Pons, P. and Latapy, M., “Computing communities in large networks using random walks,” in Computer and Information Sciences-ISCIS 2005, pp. 284–293, Springer, 2005.

  27. r Project. http://www.r-project.org.

  28. Raghavan U.N., Albert R., Kumara S.: “Near linear time algorithm to detect community structures in large-scale networks".. Physical Review E 76(3), 036106 (2007)

    Article  Google Scholar 

  29. Redner, S., “How popular is your paper? an empirical study of the citation distribution,” The European Physical Journal B-Condensed Matter and Complex Systems, 4, 2, pp. 131–134, 1998.

  30. Reichardt J., Bornholdt S.: “Statistical mechanics of community detection”. Physical Review E 74(1), 016110 (2006)

    Article  MathSciNet  Google Scholar 

  31. Rosvall, M., Axelsson, D. and Bergstrom, C. T., “The map equation,” The European Physical Journal Special Topics, 178, 1, pp. 13–23, 2009

  32. Rosvall, M. and Bergstrom, C. T., “Maps of random walks on complex networks reveal community structure,” Proc. of the National Academy of Sciences, 105, 4, pp. 1118–1123, 2008.

  33. Santos, F. C. and Pacheco, J. M., “Scale-free networks provide a unifying framework for the emergence of cooperation,” Physical Review Letters, 95, 9, 098104, 2005.

  34. Singh B.K., Gupte N.: “Congestion and decongestion in a communication network”. Physical Review E, 71(5), 055103 (2005)

    Article  Google Scholar 

  35. Toroczkai, Z. and Bassler, K. E., “Network dynamics: Jamming is limited in scale-free systems,” Nature, 428, 6984, p. 716, 2004.

  36. Traag V.A., Bruggeman J.: “Community detection in networks with positive and negative links”.. Physical Review E 80(3), 036115 (2009)

    Article  Google Scholar 

  37. Vazquez A.: “Spreading dynamics on small-world networks with connectivity fluctuations and correlations”.. Physical Review E 74(5), 056101 (2006)

    Article  MathSciNet  Google Scholar 

  38. Wang, X. F. and Chen, G., “Synchronization in scale-free dynamical networks: robustness and fragility,” Circuits and Systems I: Fundamental Theory and Applications, IEEE Transactions on, 49, 1, pp. 54–62, 2002.

  39. Zhao, L., Park, K. and Lai, Y.-C., “Attack vulnerability of scalefree networks due to cascading breakdown,” Physical review E, 70, 3, 035101, 2004.

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Western Kentucky University, Bowling Green, KY, 42101, USA

    Rong Yang

Authors
  1. Rong Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Rong Yang.

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Yang, R. Assortifying Networks. New Gener. Comput. 32, 297–308 (2014). https://doi.org/10.1007/s00354-014-0406-5

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00354-014-0406-5

Keywords

Search

Navigation