×

Community detection in temporal multilayer networks, with an application to correlation networks. (English) Zbl 1328.90151

Summary: Networks are a convenient way to represent complex systems of interacting entities. Many networks contain “communities” of nodes that are more densely connected to each other than to nodes in the rest of the network. In this paper, we investigate the detection of communities in temporal networks represented as multilayer networks. As a focal example, we study time-dependent financial-asset correlation networks. We first argue that the use of the “modularity” quality function – which is defined by comparing edge weights in an observed network to expected edge weights in a “null network” – is application-dependent. We differentiate between “null networks” and “null models” in our discussion of modularity maximization, and we highlight that the same null network can correspond to different null models. We then investigate a multilayer modularity-maximization problem to identify communities in temporal networks. Our multilayer analysis depends only on the form of the maximization problem and not on the specific quality function that one chooses. We introduce a diagnostic to measure persistence of community structure in a multilayer network partition. We prove several results that describe how the multilayer maximization problem measures a trade-off between static community structure within layers and larger values of persistence across layers. We also discuss some computational issues that the popular “Louvain” heuristic faces with temporal multilayer networks and suggest ways to mitigate them.

MSC:

90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming
62H30 Classification and discrimination; cluster analysis (statistical aspects)
91D30 Social networks; opinion dynamics
94C15 Applications of graph theory to circuits and networks
91G80 Financial applications of other theories

Software:

GenLouvain
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] A. Arenas, A. Fernández, and S. Gómez, {\it Analysis of the structure of complex networks at different resolution levels}, New J. Phys., 10 (2008), 053039.
[2] T. Aynaud and J.-L. Guillaume, {\it Static community detection algorithms for evolving networks}, in Proceedings of WiOpt’10: Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, Avignon, France, 2010, pp. 508-514.
[3] I. Barnett and J.-P. Onnela, {\it Change Point Detection in Correlation Networks}, preprint, http://arxiv.org/abs/1410.0761arXiv:1410.0761v2 [stat.ME], 2015.
[4] D. S. Bassett, E. T. Owens, M. A. Porter, M. L. Manning, and K. E. Daniels, {\it Extraction of force-chain network architecture in granular materials using community detection}, Soft Matter, 11 (2015), pp. 2731-2744.
[5] D. S. Bassett, M. A. Porter, N. F. Wymbs, S. T. Grafton, J. M. Carlson, and P. J. Mucha, {\it Robust detection of dynamic community structure in networks}, Chaos, 23 (2013), 013142.
[6] D. S. Bassett, N. F. Wymbs, M. A. Porter, P. J. Mucha, J. M. Carlson, and S. T. Grafton, {\it Dynamic reconfiguration of human brain networks during learning}, Proc. Natl. Acad. Sci. USA, 108 (2011), pp. 7641-7646.
[7] S. Battiston, J. B. Glattfelder, D. Garlaschelli, F. Lillo, and G. Caldarelli, {\it The structure of financial networks}, in Network Science, Springer, London, 2010, pp. 131-163.
[8] E. T. Bell, {\it Exponential numbers}, Amer. Math. Monthly, 41 (1934), pp. 411-419. · Zbl 0010.05401
[9] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, {\it Fast unfolding of communities in large networks}, J. Stat. Mech. Theory Exp., no. 10 (2008), P10008. · Zbl 1459.91130
[10] S. Boccaletti, G. Bianconi, R. Criado, C. I. Del Genio, J. Gómez-Gardenes, M. Romance, I. Sendina-Nadal, Z. Wang, and M. Zanin, {\it The structure and dynamics of multilayer networks}, Phys. Rep., 544 (2014), pp. 1-122.
[11] B. Bollobás, S. Janson, and O. Riordan, {\it The phase transition in inhomogeneous random graphs}, Random Structures Algorithms, 31 (2007), pp. 3-122. · Zbl 1123.05083
[12] B. Bollobás and O. Riordan, {\it Random graphs and branching processes}, in Handbook of Large-Scale Random Networks, Bolyai Soc. Math. Stud. 18, Springer, Berlin, 2009, pp. 15-115.
[13] U. Brandes, D. Delling, M. Gaertler, R. Görke, M. Hoefer, Z. Nikoloski, and D. Wagner, {\it On modularity clustering}, IEEE Trans. Knowl. Data Eng., 20 (2008), pp. 172-188. · Zbl 1141.68519
[14] M. Catanzaro and M. Buchanan, {\it Network opportunity}, Nature Phys., 9 (2013), pp. 121-123.
[15] F. Chung and L. Lu, {\it The average distance in a random graph with given expected degrees}, Proc. Natl. Acad. Sci. USA, 99 (2002), pp. 15879-15882. · Zbl 1064.05137
[16] R. Cont, {\it Empirical properties of asset returns: Stylized facts and statistical issues}, Quant. Finance, 1 (2001), pp. 223-236. · Zbl 1408.62174
[17] J.-C. Delvenne, S. N. Yaliraki, and M. Barahona, {\it Stability of graph communities across time scales}, Proc. Natl. Acad. Sci. USA, 107 (2010), pp. 12755-12760.
[18] M. De Domenico, A . Lancichinetti, A. Arenas, and M. Rosvall, {\it Identifying modular flows on multilayer networks reveals highly overlapping organization in interconnected systems}, Phys. Rev. X, 5 (2015), 011027.
[19] J. Edmonds and R. M. Karp, {\it Theoretical improvements in algorithmic efficiency for network flow problems}, J. ACM, 19 (1972), pp. 248-264. · Zbl 0318.90024
[20] P. Expert, T. S. Evans, V. D. Blondel, and R. Lambiotte, {\it Uncovering space-independent communities in spatial networks}, Proc. Natl. Acad. Sci. USA, 108 (2011), pp. 7663-7668. · Zbl 1256.91043
[21] D. J. Fenn, M. A. Porter, M. McDonald, S. Williams, N. F. Johnson, and N. S. Jones, {\it Dynamic communities in multichannel data: An application to the foreign exchange market during the 2007-2008 credit crisis}, Chaos, 19 (2009), 033119.
[22] D. J. Fenn, M. A. Porter, P. J. Mucha, M. McDonald, S. Williams, N. F. Johnson, and N. S. Jones, {\it Dynamical clustering of exchange rates}, Quant. Finance, 12 (2012), pp. 1493-1520. · Zbl 1279.91130
[23] D. J. Fenn, M. A. Porter, S. Williams, M. McDonald, N. F. Johnson, and N. S. Jones, {\it Temporal evolution of financial market correlations}, Phys. Rev. E, 84 (2011), 026109.
[24] S. Fortunato, {\it Community detection in graphs}, Phys. Rep., 486 (2010), pp. 75-174.
[25] S. Fortunato and M. Barthelémy, {\it Resolution limit in community detection}, Proc. Natl. Acad. Sci. USA, 104 (2006), pp. 36-41.
[26] M. Girvan and M. E. J. Newman, {\it Community structure in social and biological networks}, Proc. Natl. Acad. Sci. USA, 99 (2002), pp. 7821-7826. · Zbl 1032.91716
[27] S. Gómez, P. Jensen, and A. Arenas, {\it Analysis of community structure in networks of correlated data}, Phys. Rev. E, 80 (2009), 016114.
[28] S. González-Bailón, J. Borge-Holthoefer, A. Rivero, and Y. Moreno, {\it The dynamics of protest recruitment through an online network}, Sci. Rep., 1 (2011), 197.
[29] B. H. Good, Y.-A. de Montjoye, and A. Clauset, {\it Performance of modularity maximization in practical contexts}, Phys. Rev. E, 81 (2010), 046106.
[30] A. A. Groppelli and E. Nikbakht, {\it Barron’s Finance}, 4th ed., Barron’s Educational Series, Inc., Hauppauge, NY, 2000.
[31] R. Guimerà, M. Sales-Pardo, and L. A. N. Amaral, {\it Functional cartography of complex metabolic networks}, Nature, 443 (2005), pp. 895-900.
[32] T. Hoffmann, M. A. Porter, and R. Lambiotte, {\it Generalized master equations for non-Poisson dynamics on networks}, Phys. Rev. E, 86 (2012), 046102.
[33] P. Holme, {\it Modern temporal network theory: A colloquium}, Eur. Phys. J. B, 88 (2015), 234.
[34] P. Holme and J. Saramäki, {\it Temporal networks}, Phys. Rep., 519 (2012), pp. 97-125.
[35] J. Hopcroft, O. Khan, B. Kulli, and B. Selman, {\it Tracking evolving communities in large linked networks}, Proc. Natl. Acad. Sci. USA, 101 (2004), pp. 5250-5253.
[36] L. G. S. Jeub, P. Balachandran, M. A. Porter, P. J. Mucha, and M. W. Mahoney, {\it Think locally, act locally: Detection of small, medium-sized, and large communities in large networks}, Phys. Rev. E, 91 (2015), 012821.
[37] I. S. Jutla, L. G. S. Jeub, and P. J. Mucha, {\it A Generalized Louvain Method for Community Detection Implemented in MATLAB, Version 2.0}, http://netwiki.amath.unc.edu/GenLouvain/GenLouvain (2011-2014).
[38] M. Kivelä, A. Arenas, M. Barthélemy, J. P. Gleeson, Y. Moreno, and M. A. Porter, {\it Multilayer networks}, J. Complex Networks, 2 (2014), pp. 203-271.
[39] H. W. Kuhn, {\it The Hungarian method for the assignment problem}, Naval Res. Logist. Quart., 2 (1955), pp. 83-97. · Zbl 0143.41905
[40] R. Lambiotte, {\it Multi-scale modularity in complex networks}, in Proceedings of WiOpt’10: Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, Avignon, France, 2010, pp. 546-553.
[41] R. Lambiotte, J.-C. Delvenne, and M. Barahona, {\it Laplacian Dynamics and Multiscale Modular Structure in Networks}, preprint, http://arxiv.org/abs/0812.1770arXiv:0812.1770 [physics.soc-ph], 2008.
[42] R. Lambiotte, J.-C. Delvenne, and M. Barahona, {\it Random walks, Markov processes and the multiscale modular organization of complex networks}, IEEE Trans. Netw. Sci. Eng., 1 (2014), pp. 76-90.
[43] A. Lancichinetti and S. Fortunato, {\it Community detection algorithms: A comparative analysis}, Phys. Rev. E, 80 (2009), 056117.
[44] A. Lancichinetti and S. Fortunato, {\it Consensus clustering in complex networks}, Sci. Rep., 2 (2012), 336.
[45] A. C. F. Lewis, N. S. Jones, M. A. Porter, and C. M. Deane, {\it The function of communities in protein interaction networks at multiple scales}, BMC Syst. Biol., 4 (2010), 100.
[46] M. MacMahon and D. Garlaschelli, {\it Community detection for correlation matrices}, Phys. Rev. X, 5 (2015), 021006.
[47] K. T. Macon, P. J. Mucha, and M. A. Porter, {\it Community structure in the United Nations General Assembly}, Phys. A, 391 (2012), pp. 343-361.
[48] R. N. Mantegna, {\it Hierarchical structure in financial markets}, Eur. Phys. J. B, 11 (1999), pp. 193-197.
[49] P. J. Mucha and M. A. Porter, {\it Communities in multislice voting networks}, Chaos, 20 (2010), 041108.
[50] P. J. Mucha, T. Richardson, K. Macon, M. A. Porter, and J.-P. Onnela, {\it Community structure in time-dependent, multiscale and multiplex networks}, Science, 328 (2010), pp. 876-878. · Zbl 1226.91056
[51] J. Munkres, {\it Algorithms for the assignment and transportation problems}, J. Soc. Indust. Appl. Math., 5 (1957), pp. 32-38. · Zbl 0083.15302
[52] M. E. J. Newman, {\it Analysis of weighted network}, Phys. Rev. E, 70 (2004), 066146.
[53] M. E. J. Newman, {\it Finding community structure in networks using the eigenvectors of matrices}, Phys. Rev. E, 74 (2006), 036104.
[54] M. E. J. Newman, {\it Networks: An Introduction}, Oxford University Press, Oxford, UK, 2010. · Zbl 1195.94003
[55] M. E. J. Newman, {\it Communities, modules and large-scale structure in networks}, Nature Phys., 8 (2012), pp. 25-31.
[56] M. E. J. Newman and M. Girvan, {\it Finding and evaluating community structure in networks}, Phys. Rev. E, 69 (2004), 026113.
[57] J.-P. Onnela, A. Chakraborti, K. Kaski, J. Kertész, and A. Kanto, {\it Dynamics of market correlations: Taxonomy and portfolio analysis}, Phys. Rev. E, 68 (2003), 056110. · Zbl 1129.91323
[58] G. Palla, A.-L. Barabási, and T. Vicsek, {\it Quantifying social group evolution}, Nature, 446 (2007), pp. 664-667.
[59] L. Peel and A. Clauset, {\it Detecting change points in the large-scale structure of evolving networks}, in Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, Association for the Advancement of Artificial Intelligence, Palo Alto, CA, 2015, pp. 2914-2920.
[60] G. Pietri and P. Expert, {\it Temporal stability of network partitions}, Phys. Rev. E, 90 (2014), 022813.
[61] M. A. Porter, J.-P. Onnela, and P. J. Mucha, {\it Communities in networks}, Notices Amer. Math. Soc., 56 (2009), pp. 1082-1097, 1164-1166. · Zbl 1188.05142
[62] M. Potters, J.-P. Bouchaud, and L. Laloux, {\it Financial applications of random matrix theory: Old laces and new pieces}, Acta Phys. Polon. B, 36 (2005), pp. 2767-2784. · Zbl 1372.91128
[63] F. Radicchi and A. Arenas, {\it Abrupt transition in the structural formation of interconnected networks}, Nature Phys., 9 (2013), pp. 717-720.
[64] J. Reichardt and S. Bornholdt, {\it Statistical mechanics of community detection}, Phys. Rev. E, 74 (2006), 016110. · Zbl 1459.91116
[65] M. Sales-Pardo, R. Guimerà, A. A. Moreira, and L. A. N. Amaral, {\it Extracting the hierarchical organization of complex systems}, Proc. Natl. Acad. Sci. USA, 39 (2007), pp. 15224-15229.
[66] M. Sarzynska, E. L. Leicht, G. Chowell, and M. A. Porter, {\it Null models for community detection in spatially embedded, temporal networks}, J. Complex Networks (2015), doi:10.1093/comnet/cnv027.
[67] R. Schafer and T. Guhr, {\it Local normalization: Uncovering correlations in non-stationary financial time series}, Phys. A, 389 (2010), pp. 3856-3865.
[68] H. A. Simon, {\it The architecture of complexity}, Proc. Amer. Phil. Soc., 106 (1962), pp. 467-482.
[69] S. M. Smith, K. L. Miller, G. Salimi-Khorshidi, M. Webster, C. F. Beckmann, T. E. Nichols, J. D. Ramsey, and M. W. Woolrich, {\it Network modelling methods for FMRI}, NeuroImage, 54 (2011), pp. 875-891.
[70] N. Stanley, S. Shai, D. Taylor, and P. J. Mucha, {\it Clustering Network Layers with the Strata Multilayer Stochastic Block Model}, preprint, http://arxiv.org/abs/1507.01826arXiv:1507.01826v2 [cs.SI], 2015.
[71] V. A. Traag and J. Bruggeman, {\it Community detection in networks with positive and negative links}, Phys. Rev. E, 80 (2009), 036115.
[72] V. A. Traag and P. Van Dooren, {\it Narrow scope for resolution-limit-free community detection}, Phys. Rev. E, 84 (2011), 016114.
[73] A. L. Traud, E. D. Kelsic, P. J. Mucha, and M. A. Porter, {\it Comparing community structure to characteristics in online collegiate social networks}, SIAM Rev., 53 (2011), pp. 526-543.
[74] S. Williams, {\it Risk trades will test investors through 2011}, Financial Times, January 5, 2011.
[75] Y. Wu, C. Zhou, J. Xiao, J. Kurths, and H. J. Schellnhuber, {\it Evidence for a bimodal distribution in human communication}, Proc. Natl. Acad. Sci. USA, 107 (2010), pp. 18803-18808.
[76] A. Zalesky, A. Fornito, and E. Bullmore, {\it On the use of correlation as a measure of network connectivity}, NeuroImage, 60 (2012), pp. 2096-2106.
[77] Q. Zhao, Y. Tian, Q. He, N. Oliver, R. Jin, and W.-C. Lee, {\it Communication motifs: A tool to characterize social communications}, in Proceedings of the 19th ACM International Conference on Information and Knowledge Management, 2010, pp. 1645-1648.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.