Hostname: page-component-745bb68f8f-s22k5 Total loading time: 0 Render date: 2025-02-06T14:50:43.700Z Has data issue: false hasContentIssue false
  • English
  • Français

Detection of core–periphery structure in networks using spectral methods and geodesic paths

Published online by Cambridge University Press:  03 August 2016

MIHAI CUCURINGU ,
PUCK ROMBACH ,
SANG HOON LEE  and
MASON A. PORTER
MIHAI CUCURINGU
Affiliation:
Department of Mathematics, UCLA, Los Angeles, CA, USA emails: mihai@math.ucla.edu, rombach@math.ucla.edu
PUCK ROMBACH
Affiliation:
Department of Mathematics, UCLA, Los Angeles, CA, USA emails: mihai@math.ucla.edu, rombach@math.ucla.edu
SANG HOON LEE
Affiliation:
Oxford Centre for Industrial and Applied Mathematics, Mathematical Institute, University of Oxford, Oxford, UK email: porterm@maths.ox.ac.uk School of Physics, Korea Institute for Advanced Study, Seoul, Korea email: lshlj82@kias.re.kr
MASON A. PORTER
Affiliation:
Oxford Centre for Industrial and Applied Mathematics, Mathematical Institute, University of Oxford, Oxford, UK email: porterm@maths.ox.ac.uk CABDyN Complexity Centre, University of Oxford, Oxford, UK
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We introduce several novel and computationally efficient methods for detecting “core–periphery structure” in networks. Core–periphery structure is a type of mesoscale structure that consists of densely connected core vertices and sparsely connected peripheral vertices. Core vertices tend to be well-connected both among themselves and to peripheral vertices, which tend not to be well-connected to other vertices. Our first method, which is based on transportation in networks, aggregates information from many geodesic paths in a network and yields a score for each vertex that reflects the likelihood that that vertex is a core vertex. Our second method is based on a low-rank approximation of a network's adjacency matrix, which we express as a perturbation of a tensor-product matrix. Our third approach uses the bottom eigenvector of the random-walk Laplacian to infer a coreness score and a classification into core and peripheral vertices. We also design an objective function to (1) help classify vertices into core or peripheral vertices and (2) provide a goodness-of-fit criterion for classifications into core versus peripheral vertices. To examine the performance of our methods, we apply our algorithms to both synthetically generated networks and a variety of networks constructed from real-world data sets.

Keywords

Networkscore–periphery structureshortest-path algorithmslow-rank matrix approximationsgraph Laplacians
Type
Papers
Information
European Journal of Applied Mathematics , Volume 27 , Special Issue 6: Network Analysis and Modelling , December 2016 , pp. 846 - 887
Copyright
Copyright © Cambridge University Press 2016 

References

[1] Ahn, Y.-Y., Bagrow, J. P. & Lehmann, S. (2010) Link communities reveal multiscale complexity in networks. Nature 466, 761–764.CrossRefGoogle ScholarPubMed
[2] Anthonisse, J. M. (1971) The Rush in a Directed Graph, Stichting Mathematisch Centrum, Amsterdam. Available at http://oai.cwi.nl/oai/asset/9791/9791A.pdf.Google Scholar
[3] Arenas, A., Díaz-Guilera, A. & Pérez-Vicente, C. J. (2006) Synchronization reveals topological scales in complex networks. Phys. Rev. Lett. 96, 114102.Google Scholar
[4] Ball, B., Karrer, B. & Newman, M. E. J. (2011) Efficient and principled method for detecting communities in networks. Phys. Rev. E 84, 036103.Google Scholar
[5] Barranca, V. J., Zhou, D. & Cai, D. (2015) Low-rank network decomposition reveals structural characteristics of small-world networks. Phys. Rev. E 92, 062822.CrossRefGoogle ScholarPubMed
[6] Barucca, P., Tantari, D. & Lillo, F. (2016) Centrality metrics and localization in core–periphery networks. J. Stat. Mech. Theor. Exp. 2016, 023401.Google Scholar
[7] Bascompte, J., Jordano, P., Melián, C. J. & Olesen, J. M. (2003) The nested assembly of plant-animal mutualistic networks. Proc. Natl. Acad. Sci. U.S.A. 100, 9383–9387.CrossRefGoogle ScholarPubMed
[8] Bassett, D. S., Wymbs, N. F., Porter, M. A., Mucha, P. J., Carlson, J. M. & Grafton, S. T. (2011) Dynamic reconfiguration of human brain networks during learning. Proc. Natl. Acad. Sci. U.S.A. 108, 7641–7646.Google Scholar
[9] Bassett, D. S., Wymbs, N. F., Rombach, M. P., Porter, M. A., Mucha, P. J. & Grafton, S. T. (2013) Task-based core–periphery organization of human brain dynamics. PLoS Comput. Biol. 9, e1003171.CrossRefGoogle ScholarPubMed
[10] Belkin, M. & Niyogi, P. (2003) Laplacian eigenmaps for dimensionality reduction and data representation. Neural Comput. 15, 1373–1396.Google Scholar
[11] Benaych-Georges, F. & Nadakuditi, R. R. (2011) The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices. Adv. Math. 227, 494–521.Google Scholar
[12] Bhatia, R. (1997) Matrix Analysis, Graduate Texts in Mathematics, vol. 169, Springer-Verlag, Berlin, Germany.CrossRefGoogle Scholar
[13] Borgatti, S. P. & Everett, M. G. (1999) Models of core/periphery structures. Soc. Netw. 21, 375–395.Google Scholar
[14] Borgatti, S. P., Everett, M. G. & Freeman, L. C. (2011) UCINET, version 6.289. Available at http://www.analytictech.com/ucinet/.Google Scholar
[15] Boyd, J. P., Fitzgerald, W. J., Mahutga, M. C. & Smith, D. A. (2010) Computing continuous core/periphery structures for social relations data with MINRES/SVD. Soc. Netw. 32, 125–137.Google Scholar
[16] Brandes, U. (2001) A faster algorithm for betweenness centrality. J. Math. Sociol. 25, 163–177.Google Scholar
[17] Brandes, U., Delling, D., Gaertler, M., Görke, R., Hoefer, M., Nikoloski, Z. & Wagner, D. (2008) On modularity clustering. IEEE Trans. Knowl. Data Eng. 20, 172–188.Google Scholar
[18] Chase-Dunn, C. (1989) Global Formation: Structures of the World-Economy, Basil Blackwell, Oxford, UK.Google Scholar
[19] Chen, J. & Yuan, B. (2006) Detecting functional modules in the yeast protein–protein interaction network. Bioinformatics 22, 2283–2290.CrossRefGoogle ScholarPubMed
[20] Chung, F. R. K. (1997) Spectral Graph Theory, CBMS Regional Conference Series, American Mathematical Society, Providence, RI.Google Scholar
[21] Clauset, A., Arbesman, S. & Larremore, D. B. (2015) Systematic inequality and hierarchy in faculty hiring networks. Sci. Adv. 1, e1400005.Google Scholar
[22] Coifman, R. R. & Lafon, S. (2006) Diffusion maps. Appl. Comput. Harmon. Anal. 21, 5–30.CrossRefGoogle Scholar
[23] Coifman, R. R., Lafon, S., Lee, A. B., Maggioni, M., Nadler, B., Warner, F. & Zucker, S. W. (2005) Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps. Proc. Natl. Acad. Sci. U.S.A. 102, 7426–7431.Google Scholar
[24] Colizza, V., Flammini, A., Serrano, M. A. & Vespignani, A. (2006) Detecting rich-club ordering in complex networks. Nat. Phys. 2, 110–115.Google Scholar
[25] Comrey, A. L. (1962) The minimum residual method of factor analysis. Psychol. Rep. 11, 15–18.Google Scholar
[26] Csermely, P., London, A., Wu, L.-Y. & Uzzi, B. (2013) Structure and dynamics of core/periphery networks. J. Cplx. Netw. 1, 93–123.Google Scholar
[27] da Silva, M. R., Ma, H. & Zeng, A.-P. (2008) Centrality, network capacity, and modularity as parameters to analyze the core–periphery structure in metabolic networks. Proc. IEEE 96, 1411–1420.Google Scholar
[28] Darlington, R. B., Weinberg, S. L. & Walberg, H. J. (1973) Canonical variate analysis and related techniques. Rev. Educ. Res. 43, 433–454.Google Scholar
[29] Della-Rossa, F. D., Dercole, F. & Piccardi, C. (2013) Profiling core–periphery network structure by random walkers. Sci. Rep. 3, 1467.Google Scholar
[30] Doreian, P. (1985) Structural equivalence in a psychology journal network. J. Assoc. Inf. Sci. 36, 411–417.Google Scholar
[31] Edler, D. & Rosvall, M. (2010) The map generator software package (2010 network scientist coauthorship network). Accessed 12 September 2014. Available at http://mapequation.org/downloads/netscicoauthor2010.net.Google Scholar
[32] Erdős, P. & Rényi, A. (1959) On random graphs I. Publ. Math. Debrecen 6, 290–297.Google Scholar
[33] Everett, M. G. & Valente, T. W. (2016) Bridging, brokerage and betweenness. Soc. Netw. 44, 202–208.Google Scholar
[34] Féral, D. & Péché, S. (2007) The largest eigenvalue of rank one deformation of large Wigner matrices. Comm. Math. Phys. 272, 185–228.Google Scholar
[35] Fortunato, S. (2010) Community detection in graphs. Phys. Rep. 486, 75–174.Google Scholar
[36] Freeman, L. C. (1977) A set of measures of centrality based on betweenness. Sociometry 40, 35–41.Google Scholar
[37] Gilbert, E. N. (1959) Random graphs. Ann. Math. Stat. 30, 1141–1144.Google Scholar
[38] Girvan, M. & Newman, M. E. J. (2002) Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA 99, 7821–7826.Google Scholar
[39] Goemans, M. X. & Williamson, D. P. (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 1115–1145.Google Scholar
[40] González, M. C., Herrmann, H. J., Kertész, J. & Vicsek, T. (2007) Community structure and ethnic preferences in school friendship networks. Physica A 379, 307–316.Google Scholar
[41] Good, B. H., de Montjoye, Y.-A. & Clauset, A. (2010) Performance of modularity maximization in practical contexts. Phys. Rev. E 81, 046106.CrossRefGoogle ScholarPubMed
[42] Grant, M. & Boyd, S. (2008) Graph implementations for nonsmooth convex programs, In: Blondel, V., Boyd, S. & Kimura, H. (editors), Recent Advances in Learning and Control, Lecture Notes Contr. Inf. Sci., Springer-Verlag, Berlin, Germany, pp. 95–110.Google Scholar
[43] Guattery, S. & Miller, G. L. (1995) On the performance of spectral graph partitioning methods. In: Proc. 6th Ann. ACM-SIAM Symp. on Discrete Algorithms, SODA '95, January 22–24, 1995, San Francisco, CA, USA. SIAM, Philadelphia, PA, USA, pp. 233–242.Google Scholar
[44] Holme, P. (2005) Core–periphery organization of complex networks. Phys. Rev. E 72, 046111.Google Scholar
[45] Holme, P. & Saramäki, J. (2012) Temporal networks. Phys. Rep. 519, 97–125.Google Scholar
[46] Jeub, L. G. S., Balachandran, P., Porter, M. A., Mucha, P. J. & Mahoney, M. W. (2015) Think locally, act locally: Detection of small, medium-sized, and large communities in large networks. Phys. Rev. E 91, 012821.CrossRefGoogle ScholarPubMed
[47] Jeub, L. G. S., Mahoney, M. W., Mucha, P. J. & Porter, M. A. (2015) A local perspective on community structure in multilayer networks, arXiv:1510.05185.Google Scholar
[48] Kelmans, A. K. (1965) The number of trees of a graph I. Aut. Remote Contr. 26, 2118–2129.Google Scholar
[49] Kelmans, A. K. (1966) The number of trees of a graph II. Aut. Remote Contr. 27, 233–241.Google Scholar
[50] Kelmans, A. K. (1997) Transformations of a graph increasing its Laplacian polynomial and number of spanning trees. Europ. J. Comb. 18, 35–48.Google Scholar
[51] Kitsak, M., Gallos, L. K., Havlin, S., Liljeros, F., Muchnik, L., Stanley, H. E. & Makse, H. A. (2010) Identification of influential spreaders in complex networks. Nat. Phys. 6, 888–893.Google Scholar
[52] Kivelä, M., Arenas, A., Barthelemy, M., Gleeson, J. P., Moreno, Y. & Porter, M. A. (2014) Multilayer networks. J. Cplx. Netw. 2, 203–271.Google Scholar
[53] Krugman, P. (1996) The Self-Organizing Economy, Oxford University Press, Oxford, UK.Google Scholar
[54] Laumann, E. O. & Pappi, F. U. (1976) Networks of Collective Action: A Perspective on Community Influence, Academic Press, New York, NY, USA.Google Scholar
[55] Lee, S. H. (2016) Network nestedness as generalized core–periphery structures. Phys. Rev. E 93, 022306.Google Scholar
[56] Lee, S. H., Cucuringu, M. & Porter, M. A. (2014) Density-based and transport-based core–periphery structures in networks. Phys. Rev. E 89, 032810.Google Scholar
[57] Lewis, A. C. F., Jones, N. S., Porter, M. A. & Deane, C. M. (2010) The function of communities in protein interaction networks at multiple scales. BMC Syst. Biol. 4, 100.Google Scholar
[58] McLachlan, G. & Peel, D. (2000) Finite Mixture Models, Wiley-Interscience, Hoboken, NJ, USA.Google Scholar
[59] Meilǎ, M. & Shi, J. (2001) A random walks view of spectral segmentation. In: 8th International Workshop on Artificial Intelligence and Statistics (AISTATS), Key West, FL, USA.Google Scholar
[60] Morone, F. & Makse, H. A. (2015) Influence maximization in complex networks through optimal percolation. Nature 524, 65–68.CrossRefGoogle ScholarPubMed
[61] Mucha, P. J., Richardson, T., Macon, K., Porter, M. A. & Onnela, J.-P. (2010) Community structure in time-dependent, multiscale, and multiplex networks. Science 328, 876–878.Google Scholar
[62] Nesterov, Y. (2004) Introductory Lectures on Convex Optimization: A Basic Course, Applied optimization, Kluwer Academic Publ., Dordrecht, the Netherlands.Google Scholar
[63] Newman, M. E. J. (2005) A measure of betweenness centrality based on random walks. Soc. Netw. 27, 39–54.Google Scholar
[64] Newman, M. E. J. (2006) Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E 74, 036104.Google Scholar
[65] Newman, M. E. J. (2010) Networks: An Introduction, Oxford University Press, UK.Google Scholar
[66] Newman, M. E. J. & Girvan, M. (2003) Mixing patterns and community structure in networks. In: Pastor-Satorras, R., Rubi, M. & Díaz-Guilera, A. (editors), Statistical Mechanics of Complex Networks Lecture Notes in Physics, vol. 625, Springer-Verlag, Berlin, Germany, pp. 66–87.Google Scholar
[67] Newman, M. E. J. & Girvan, M. (2004) Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113.Google Scholar
[68] Onnela, J.-P., Saramäki, J., Hyvönen, J., Szabó, G., Lazer, D., Kaski, K., Kertész, J. & Barabási, A. L. (2007) Structure and tie strengths in mobile communication networks. Proc. Natl. Acad. Sci. U.S.A. 104, 7332–7336.Google Scholar
[69] Palla, G., Derenyi, I., Farkas, I. & Vicsek, T. (2005) Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 814–818.Google Scholar
[70] Peixoto, T. P. (2014) Hierarchical block structures and high-resolution model selection in large networks. Phys. Rev. X 4, 011047.Google Scholar
[71] Piccardi, C. (2011) Finding and testing network communities by lumped Markov chains. PLoS ONE 6, e27028.Google Scholar
[72] Pons, P. & Latapy, M. (2006) Computing communities in large networks using random walks. J. Graph Algorithms Appl. 10, 191–218.Google Scholar
[73] Porter, M. A., Mucha, P. J., Newman, M. E. J. & Warmbrand, C. M. (2005) A network analysis of committees in the U.S. House of Representatives. Proc. Natl. Acad. Sci. U.S.A. 102, 7057–7062.CrossRefGoogle ScholarPubMed
[74] Porter, M. A., Onnela, J.-P. & Mucha, P. J. (2009) Communities in networks. Notices Amer. Math. Soc. 56, 1082–1097, 1164–1166.Google Scholar
[75] Richardson, T., Mucha, P. J. & Porter, M. A. (2009) Spectral tripartitioning of networks. Phys. Rev. E 80, 036111.Google Scholar
[76] Rombach, M. P., Porter, M. A., Fowler, J. H. & Mucha, P. J. (2014) Core–periphery structure in networks. SIAM J. Appl. Math. 74, 167–190.Google Scholar
[77] Rossi, R. A. & Ahmed, N. K. (2015) Role discovery in networks. IEEE Trans. Knowl. Data Eng. 27, 1112–1131.Google Scholar
[78] Rosvall, M. & Bergstrom, C. T. (2008) Maps of random walks on complex networks reveal community structure. Proc. Natl. Acad. Sci. U.S.A. 105, 1118–1123.Google Scholar
[79] Roweis, S. T. & Saul, L. K. (2000) Nonlinear dimensionality reduction by locally linear embedding. Science 290, 2323–2326.Google Scholar
[80] Shi, J. & Malik, J. (2000) Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 22, 888–905.Google Scholar
[81] Singer, A. (2011) Angular synchronization by eigenvectors and semidefinite programming. Appl. Comput. Harmon. Anal. 30, 20–36.Google Scholar
[82] Smith, D. A. & White, D. R. (1992) Structure and dynamics of the global economy: Network analysis of international trade. Soc. Forces 70, 857–893.Google Scholar
[83] Spielman, D. A. & Teng, S.-H. (1996) Spectral partitioning works: Planar graphs and finite element meshes. In: Foundations Of Computer Science (FOCS), IEEE Computer Society, Washington, D.C., USA, pp. 96–105.Google Scholar
[84] Spielman, D. A. & Teng, S.-H. (2007) Spectral partitioning works: Planar graphs and finite element meshes. Linear Algebra Appl. 421, 284–305. Special Issue in honor of Miroslav Fiedler.Google Scholar
[85] Steiber, S. (1979) The world system and world trade: An empirical explanation of conceptual conflicts. Sociol. Quart. 20, 23–26.Google Scholar
[86] Traud, A. L., Kelsic, E. D., Mucha, P. J. & Porter, M. A. (2011) Comparing community structure to characteristics in online collegiate social networks. SIAM Rev. 53, 526–543.Google Scholar
[87] Traud, A. L., Mucha, P. J. & Porter, M. A. (2012) Social structure of Facebook networks. Physica A 391, 4165–4180.Google Scholar
[88] Valente, T. W. & Fujimoto, K. (2010) Bridging: Locating critical connectors in a network. Soc. Netw. 32, 212–220.Google Scholar
[89] Verma, T., Russmann, F., Araújo, N. A. M., Nagler, J. & Hermann, H. J. (2016) Emergence of core–peripheries in networks. Nat. Commun. 7, 10441.Google Scholar
[90] Wallerstein, I. (1974) The Modern World-System I: Capitalist Agriculture and the Origins of the European World-Economy in the Sixteenth Century, Academic Press, New York, NY, USA.Google Scholar
[91] Yang, J. & Leskovec, J. (2014) Structure and overlaps of ground-truth communities in networks. ACM Trans. Intell. Syst. Technol. 5, 26.Google Scholar
[92] Zhang, X., Martin, T. & Newman, M. E. J. (2015) Identification of core–periphery structure in networks. Phys. Rev. E 91, 032803.Google Scholar