Mesoscopic structure and fragments

Network community and core-periphery structure. Graph partitioning, blockmodeling and community detection. Network motifs, graphlets and node orbits.

Lectures materials:

• Weak ties and network community structure (slides)
  
• Graph partitioning and community detection (slides)
  
• Blockmodeling and stochastic block models (slides)
• Network motifs, graphlets and node orbits (slides)
  

Book chapters:

• Ch. 9: Communities in Barabási, A.-L., Network Science (Cambridge University Press, 2016).
  
• Ch. 7.12-13: Similarity etc. & Ch. 11: Graph partitioning in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
• Ch. 21: Fragments etc. & Ch. 21: Communities etc. in Estrada, E. & Knight, P.A., A First Course in Network Theory (Oxford University Press, 2015).
• Ch. 3: Strong and weak ties in Easley, D. & Kleinberg, J., Networks, Crowds, and Markets (Cambridge University Press, 2010).

Course readings:

• Granovetter, M.S., The strength of weak ties, Am. J. Sociol. 78(6), 1360-1380 (1973).
• Girvan, M. & Newman, M.E.J., Community structure in social and biological networks, P. Natl. Acad. Sci. USA 99(12), 7821-7826 (2002).
  
• Ravasz, E., Somera, A.L. et al., Hierarchical organization of modularity in metabolic networks, Science 297(5586), 1551-1555 (2002).
  
• Newman, M.E.J. & Girvan, M., Mixing patterns and community structure in networks, Phys. Rev. E 67(2), 026126 (2003).
  
• Fortunato, S. & Barthelemy, M., Resolution limit in community detection, P. Natl. Acad. Sci. USA 104(1), 36-41 (2007).
  
• Palla, G., Derényi, I. et al., Uncovering the overlapping community structure of complex networks in nature and society, Nature 435(7043), 814-818 (2005).
• Guimera, R., Sales-Pardo, M. & Amaral, L.A.N., Classes of complex networks defined by role-to-role connectivity profiles, Nat. Phys. 3(1), 63-69 (2007).
• Lancichinetti, A., Kivela, M. et al., Characterizing the community structure of complex networks, PLoS ONE 5(8), e11976 (2010).
  
• Ahn, Y.-Y., Bagrow, J.P. & Lehmann, S., Link communities reveal multiscale complexity in networks, Nature 466(7307), 761-764 (2010).
• Onnela, J.-P., Saramäki, J. et al., Structure and tie strengths in mobile communication networks, P. Natl. Acad. Sci. USA 104(18), 7332-7336 (2007).
• Hric, D., Darst, R.K. & Fortunato, S., Community detection in networks: Structural communities versus ground truth, Phys. Rev. E 90(6), 062805 (2014).
• Schaub, M.T., Delvenne, J.-C. et al., The many facets of community detection in complex networks, Appl. Netw. Sci. 2, 4 (2017).

• Fortunato, S., Community detection in graphs, Phys. Rep. 486(3-5), 75-174 (2010).
  
• Fortunato, S. & Hric, D., Community detection in networks: A user guide, Phys. Rep. 659, 1-44 (2016).
• Xie, J., Kelley, S. & Szymanski, B.K., Overlapping community detection in networks, ACM Comput. Surv. 45(4), 43 (2013).
• Lancichinetti, A. & Fortunato, S., Community detection algorithms: A comparative analysis, Phys. Rev. E 80(5), 056117 (2009).
  
• Raghavan, U.N., Albert, R. & Kumara, S., Near linear time algorithm to detect community structures in large-scale networks, Phys. Rev. E 76(3), 036106 (2007).
  
• Rosvall, M. & Bergstrom, C.T., Maps of random walks on complex networks reveal community structure, P. Natl. Acad. Sci. USA 105(4), 1118-1123 (2008).
  
• Blondel, V.D., Guillaume, J.-L. et al., Fast unfolding of communities in large networks, J. Stat. Mech., P10008 (2008).
  
• Kumpula, J.M., Kivelä, M. et al., Sequential algorithm for fast clique percolation, Phys. Rev. E 78(2), 026109 (2008).
  
• Šubelj, L. & Bajec, M., Ubiquitousness of link-density and link-pattern communities in real-world networks, Eur. Phys. J. B 85(1), 32 (2012).
  
• Šubelj, L., Blagus, N. & Bajec, M., Group extraction for real-world networks, In: Proceedings of NetSci '13 (Copenhagen, Denmark, 2013), pp. 2.
• Zhao, Y., Levina, E. & Zhu, J., Community extraction for social networks, P. Natl. Acad. Sci. USA 108(18), 7321-7326 (2011).
• Šubelj, L., Label propagation for clustering in Doreian, P., Batagelj, V. & Ferligoj, A., Advances in Network Clustering and Blockmodeling (Wiley, 2018).

• Reichardt, J. & White, D.R., Role models for complex networks, Eur. Phys. J. B 60(2), 217-224 (2007).
• Holland, P.W., Laskey, K.B. & Leinhardt, S., Stochastic blockmodels: First steps, Soc. Networks 5(2), 109-137 (1983).
• Airoldi, E.M., Blei, D.M. et al., Mixed membership stochastic blockmodels, J. Mach. Learn. Res. 9(9), 1981-2014 (2008)
  
• Newman, M.E.J. & Leicht, E.A., Mixture models and exploratory analysis in networks, P. Natl. Acad. Sci. USA 104(23), 9564 (2007).
• Karrer, B. & Newman, M.E.J., Stochastic blockmodels and community structure in networks, Phys. Rev. E 83(1), 016107 (2011).
• Peixoto, T., Model selection and hypothesis testing for large-scale network models with overlapping groups, Phys. Rev. X 5(1), 011033 (2015).
• Guimera, R., Sales-Pardo, M. & Amaral, L.A.N., Classes of complex networks defined by role-to-role connectivity profiles, Nat. Phys. 3(1), 63-69 (2007).
  
• Clauset, A., Moore, C. & Newman, M.E.J., Hierarchical structure and the prediction of missing links in networks, Nature 453(7191), 98-101 (2008).
  
• Guimera, R. & Sales-Pardo, M., Missing and spurious interactions and the reconstruction of complex networks, P. Natl. Acad. Sci. USA 106(52), 22073-22078 (2009).
• Šubelj, L. & Bajec, M., Group detection in complex networks: An algorithm and comparison of the state of the art, Physica A 397, 144-156 (2014).
• Peixoto, T.P., Bayesian stochastic blockmodeling in Doreian, P., Batagelj, V. & Ferligoj, A., Advances in Network Clustering and Blockmodeling (Wiley, 2018).

• Seidman, S.B., Network structure and minimum degree, Soc. Networks 5(3), 269–287 (1983).
  
• Borgatti, S.P. & Everett, M.G., Models of core/periphery structures, Soc. Networks 21(4), 375–395 (2000).
• Holme, P., Core-periphery organization of complex networks, Phys. Rev. E 72(4), 46111 (2005).
• Leskovec, J., Lang, K.J. et al., Community structure in large networks, Internet Math. 6(1), 29–123 (2009).
• Batagelj, V. & Zaveršnik, M., An O(m) algorithm for cores decomposition of networks, Adv. Data Anal. Classif. 5(2), 129–145 (2011).
• Csermely, P., London, A. et al., Structure and dynamics of core/periphery networks, J. Complex Netw. 1(2), 93-123 (2013).
• Rombach, M., Porter, M. et al., Core-periphery structure in networks, SIAM J. Appl. Math. 74(1), 167–190 (2014).
• Zhang, X., Martin, T. & Newman, M.E.J., Identification of core-periphery structure in networks, Phys. Rev. E 91(3), 32803 (2015).
• Jeub, L.G.S., Balachandran, P. et al., Think locally, act locally, Phys. Rev. E 91(1), 12821 (2015).
• Ma, A. & Mondragón, R.J., Rich-cores in networks, PLoS ONE 10(3), e0119678 (2015).

• Milo, R., Shen-Orr, S. et al., Network motifs: Simple building blocks of complex networks, Science 298(5594), 824-827 (2002).
  
• Milo, R., Itzkovitz, S. et al., Superfamilies of evolved and designed networks, Science 303(5663), 1538-1542 (2004).
  
• Valverde, S. & Solé, R.V., Network motifs in computational graphs: A case study in software architecture, Phys. Rev. E 72(2), 026107 (2005).
• Davies, T. & Marchione, E., Event networks and the identification of crime pattern motifs, PLoS ONE 10(11), e0143638 (2015).
• Benson, A.R., Gleich, D.F. & Leskovec, J., Higher-order organization of complex networks, Science 353(6295), 163-166 (2016).
• Pržulj, N., Corneil, D.G. & Jurisica, I., Modeling interactome: Scale-free or geometric?, Bioinformatics 20(18), 3508-3515 (2004).
  
• Pržulj, N., Biological network comparison using graphlet degree distribution, Bioinformatics 23(2), e177-e183 (2007).
  
• Yaveroğlu, Ö.N., Malod-Dognin, N. et al., Revealing the hidden language of complex networks, Sci. Rep. 4, 4547 (2014).
  
• Hočevar, T. & Demšar, J., A combinatorial approach to graphlet counting, Bioinformatics 30(4), 559-565 (2014).
  
• Soufiani, H.A. & Airoldi, E.M., Graphlet decomposition of a weighted network, J. Mach. Learn. Res. 22, 54-63 (2012).
  
• Sarajlić, A., Malod-Dognin, N. et al., Predictive functional connectivity of real-world systems, e-print arXiv:1603.05470v1, pp. 17 (2016).
  
• Peel, L., Delvenne, J.-C., & Lambiotte, R., Multiscale mixing patterns in networks, P. Natl. Acad. Sci. USA 115(16), 4057-4062 (2018).
  
• Sanchez-Garcia, R.J., Exploiting symmetry in network analysis, e-print arXiv:1803.06915v1, pp. 7 (2018).