- Physical Review Journals
All JournalsPhysics Magazine

Physical Review X

Reuse & Permissions

It is not necessary to obtain permission to reuse this article or its components as it is available under the terms of the Creative Commons Attribution 3.0 License. This license permits unrestricted use, distribution, and reproduction in any medium, provided attribution to the author(s) and the published article's title, journal citation, and DOI are maintained. Please note that some figures may have been included with permission from other third parties. It is your responsibility to obtain the proper permission from the rights holder directly for these figures.

Export citation

Export citation

Choose format for download:

Download Citation
  • Open Access

Super-Resolution Community Detection for Layer-Aggregated Multilayer Networks

Dane Taylor1,2,*, Rajmonda S. Caceres3, and Peter J. Mucha1

  • 1Carolina Center for Interdisciplinary Applied Mathematics, Department of Mathematics, University of North Carolina, Chapel Hill, North Carolina 27599, USA
  • 2Department of Mathematics, University at Buffalo, State University of New York, Buffalo, New York 14260, USA
  • 3Lincoln Laboratory, Massachusetts Institute of Technology, Lexington, Massachusetts 02420, USA

  • *dane.r.taylor@gmail.com
PDF

Phys. Rev. X 7, 031056 – Published 26 September, 2017

DOI: https://doi.org/10.1103/PhysRevX.7.031056

Abstract

Applied network science often involves preprocessing network data before applying a network-analysis method, and there is typically a theoretical disconnect between these steps. For example, it is common to aggregate time-varying network data into windows prior to analysis, and the trade-offs of this preprocessing are not well understood. Focusing on the problem of detecting small communities in multilayer networks, we study the effects of layer aggregation by developing random-matrix theory for modularity matrices associated with layer-aggregated networks with N nodes and L layers, which are drawn from an ensemble of Erdős–Rényi networks with communities planted in subsets of layers. We study phase transitions in which eigenvectors localize onto communities (allowing their detection) and which occur for a given community provided its size surpasses a detectability limit K*. When layers are aggregated via a summation, we obtain K*∝O(NL/T), where T is the number of layers across which the community persists. Interestingly, if T is allowed to vary with L, then summation-based layer aggregation enhances small-community detection even if the community persists across a vanishing fraction of layers, provided that T/L decays more slowly than O(L−1/2). Moreover, we find that thresholding the summation can, in some cases, cause K* to decay exponentially, decreasing by orders of magnitude in a phenomenon we call super-resolution community detection. In other words, layer aggregation with thresholding is a nonlinear data filter enabling detection of communities that are otherwise too small to detect. Importantly, different thresholds generally enhance the detectability of communities having different properties, illustrating that community detection can be obscured if one analyzes network data using a single threshold.

View figure in article

Physics Subject Headings (PhySH)

Popular Summary

Networks can represent relationships between the online behaviors of individuals such as emailing, file sharing, and purchasing history. Small-community detection, which attempts to identify anomalous clusters within such networks, has important applications in cybersecurity for detecting attacks, intrusions, and fraud. Before analyzing the structural patterns of these networks, data are often preprocessed using a variety of techniques. While there is a wealth of theory for network analysis methodology, most preprocessing is done on an ad hoc basis, and there is significant need for an encompassing theory bridging these two steps.

Here, we focus on the task of detecting small communities in large multilayer networks, wherein “layers” encode different types of connections, such as different instances in time. Because it can be beneficial to aggregate layers that are similar, we analyze the effects of layer aggregation on the detectability of communities. We analyze a novel, important metric: the number of layers a community must persist across in order for aggregation to benefit detection. In addition, we introduce layer aggregation with thresholding as a nonlinear data filter, showing that this preprocessing step can allow super-resolution detection of communities that are otherwise too small to detect.

This work paves the way for a new class of holistic methods that simultaneously address both the data preprocessing and network analysis steps. Such an approach will lead to improved pattern analytics in cybersecurity and broadly benefit the analysis of diverse networks arising in the social, biological, and engineering sciences.

Article Text

References (59)

  1. M. E. J. Newman, The Structure and Function of Complex Networks, SIAM Rev. 45, 167 (2003).
  2. K. Lewis, J. Kaufman, M. Gonzalez, A. Wimmer, and N. Christakis, Tastes, Ties, and Time: A New Social Network Dataset Using Facebook.com, Soc. Networks 30, 330 (2008).
  3. P. Holme and J. Saramäki, Temporal Networks, Phys. Rep. 519, 97 (2012).
  4. S. Boccaletti, G. Bianconi, R. Criado, C. Del Genio, J. Gómez-Gardenes, M. Romance, I. Sendina-Nadal, Z. Wang, and M. Zanin, The Structure and Dynamics of Multilayer Networks, Phys. Rep. 544, 1 (2014).
  5. M. Kivelä, A. Arenas, M. Barthelemy, J. P. Gleeson, Y. Moreno, and M. A. Porter, Multilayer Networks, J. Complex Netw. 2, 203 (2014).
  6. G. Menichetti, D. Remondini, and G. Bianconi, Correlations Between Weights and Overlap in Ensembles of Weighted Multiplex Networks, Phys. Rev. E 90, 062817 (2014).
  7. M. De Domenico, V. Nicosia, A. Arenas, and V. Latora, Structural Reducibility of Multilayer Networks, Nat. Commun. 6, 6864 (2015).
  8. K. K. Kleineberg, M. Boguna, M. A. Serrano, and F. Papadopoulos, Hidden Geometric Correlations in Real Multiplex Networks, Nat. Phys. 12, 1076 (2016).
  9. N. Stanley, S. Shai, D. Taylor, and P. J. Mucha, Clustering Network Layers with the Strata Multilayer Stochastic Block Model, IEEE Trans. Network Sci. Eng. 3, 95 (2016).
  10. D. Taylor, S. Shai, N. Stanley, and P. J. Mucha, Enhanced Detectability of Community Structure in Multilayer Networks through Layer Aggregation, Phys. Rev. Lett. 116, 228301 (2016).
  11. H. Nayar, B. A. Miller, K. Geyer, R. S. Caceres, S. T. Smith, and R. R. Nadakuditi, Improved Hidden Clique Detection by Optimal Linear Fusion of Multiple Adjacency Matrices, 49th Asilomar Conference on Signals, Systems and Computers, 1520 (IEEE, New York, 2015).
  12. P. J. Mucha, T. Richardson, K. Macon, M. A. Porter, and J. P. Onnela, Community Structure in Time-Dependent, Multiscale, and Multiplex Networks, Science 328, 876 (2010).
  13. D. S. Bassett, N. F. Wymbs, M. A. Porter, P. J. Mucha, J. M. Carlson, and S. T. Grafton, Dynamic Reconfiguration of Human Brain Networks During Learning, Proc. Natl. Acad. Sci. U.S.A. 108, 7641 (2011).
  14. F. Chung and W. Zhao, A Sharp PageRank Algorithm with Applications to Edge Ranking and Graph Sparsification, in Proceedings of the 2010 International Workshop on Algorithms and Models for the Web-Graph (Nature Publishing, London, 2010), pp. 2–14.
  15. S. M. Hill et al., Inferring Causal Molecular Networks: Empirical Assessment through a Community-Based Effort, Nat. Methods 13, 310 (2016).
  16. A. Clauset, C. Moore, and M. E. J. Newman, Hierarchical Structure and the Prediction of Missing Links in Network, Nature (London) 453, 98 (2008).
  17. M. E. J. Newman, Measurement Errors in Network Data, arXiv:1703.07376.
  18. S. Fortunato, Community Detection in Graphs, Phys. Rep. 486, 75 (2010).
  19. M. Rosvall and C. T. Bergstrom, Maps of Random Walks on Complex Networks Reveal Community Structure, Proc. Natl. Acad. Sci. U.S.A. 105, 1118 (2008).
  20. A Lancichinetti, S. Fortunato, and F. Radicchi, Benchmark Graphs for Testing Community Detection Algorithms, Phys. Rev. E 78, 046110 (2008).
  21. M. Sales-Pardo, R. Guimera, A. A. Moreira, and L. A. N. Amaral, Extracting the Hierarchical Organization of Complex Systems, Proc. Natl. Acad. Sci. U.S.A. 104, 15224 (2007).
  22. J. Moody, Peer Influence Groups: Identifying Dense Clusters in Large Networks, Soc. Networks 23, 261 (2001).
  23. D. Mavroeidis, L. Batina, T. van Laarhoven, and E. Marchiori, PCA, Eigenvector Localization and Clustering for Side-Channel Attacks on Cryptographic Hardware Devices, in Joint European Conference on Machine Learning and Knowledge Discovery in Databases (Springer, Berlin, 2012), pp. 253–268.
  24. Q. Ding, N. Katenka, P. Barford, E. Kolaczyk, and M. Crovella, Intrusion as (Anti) Social Communication: Characterization and Detection, in Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (ACM, New York, 2012), pp. 886–894.
  25. S. Chen and A. Gangopadhyay, A Novel Approach to Uncover Health Care Frauds Through Spectral Analysis, in IEEE International Conference on Healthcare Informatics (IEEE, New York, 2013), pp. 499–504.
  26. N. Alon, M. Krivelevich, and B. Sudakov, Finding a Large Hidden Clique in a Random Graph, Random Struct. Algorithm 13, 457 (1998).
  27. R. R. Nadakuditi, On Hard Limits of Eigen-Analysis Based Planted Clique Detection, IEEE Statistical Signal Processing Workshop (IEEE, New York, 2012), p. 129.
  28. B. A. Miller, M. S. Beard, P. J. Wolfe, and N. T. Bliss, Spectral Framework for Anomalous Subgraph Detection, IEEE Trans. Signal Process. 63, 4191 (2015).
  29. A. Ghasemian, P. Zhang, A. Clauset, C. Moore, and L. Peel, Detectability Thresholds and Optimal Algorithms for Community Structure in Dynamic Networks, Phys. Rev. X 6, 031005 (2016).
  30. T. Kawamoto and Y. Kabashima, Detectability of the Spectral Method for Sparse Graph Partitioning, Europhys. Lett. 112, 40007 (2015).
  31. A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová, Inference and Phase Transitions in the Detection of Modules in Sparse Networks, Phys. Rev. Lett. 107, 065701 (2011).
  32. R. R. Nadakuditi and M. E. J. Newman, Graph Spectra and the Detectability of Community Structure in Networks, Phys. Rev. Lett. 108, 188701 (2012).
  33. F. Radicchi, Detectability of Communities in Heterogeneous Networks, Phys. Rev. E 88, 010801 (2013).
  34. T. P. Peixoto, Eigenvalue Spectra of Modular Networks, Phys. Rev. Lett. 111, 098701 (2013).
  35. P. Y. Chen and A. O. Hero, Phase Transitions in Spectral Community Detection, IEEE Trans. Signal Process. 63, 4339 (2015).
  36. S. Fortunato and M. Barthelemy, Resolution Limit in Community Detection, Proc. Natl. Acad. Sci. U.S.A. 104, 36 (2007).
  37. P. Y. Chen and A. O. Hero, Multilayer Spectral Graph Clustering via Convex Layer Aggregation: Theory and Algorithms, arXiv:1708.02620.
  38. B. D. O. Anderson and J. B. Moore, Optimal Filtering (Prentice-Hall, Englewood Cliffs, New Jersey, 1979).
  39. M. E. J. Newman and M. Girvan, Finding and Evaluating Community Structure in Networks, Phys. Rev. E 69, 026113 (2004).
  40. F. Benaych-Georges and R. R. Nadakuditi, The Eigenvalues and Eigenvectors of Finite, Low Rank Perturbations of Large Random Matrices, Adv. Math. 227, 494 (2011).
  41. Z. Bai and J. W. Silverstein, Spectral Analysis of Large Dimensional Random Matrices (Springer, New York, 2010).
  42. M. Capitaine, C. Donati-Martin, and D. Féral, The Largest Eigenvalues of Finite Rank Deformation of Large Wigner Matrices: Convergence and Nonuniversality of the Fluctuations, Ann. Prob. 37, 1 (2009).
  43. W. Hoeffding, Probability Inequalities for Sums of Bounded Random Variables, J. Am. Stat. Assoc. 58, 13 (1963).
  44. J. A. Méndez-Bermúdez, A. Alcazar-Lopez, A. J. Martinez-Mendoza, F. A. Rodrigues, and T. K. DM. Peron, Universality in the Spectral and Eigenfunction Properties of Random Networks, Phys. Rev. E 91, 032122 (2015).
  45. R. Pastor-Satorras and C. Castellano, Distinct Types of Eigenvector Localization in Networks, Sci. Rep. 6, 18847 (2016).
  46. T. Martin, X. Zhang, and M. E. J. Newman, Localization and Centrality in Networks, Phys. Rev. E 90, 052808 (2014).
  47. T. Kawamoto, Localized Eigenvectors of the Non-Backtracking Matrix, J. Stat. Mech. (2016) 023404.
  48. H. Nassar, K. Kloster, and D. F. Gleich, Strong Localization in Personalized Page Rank Vectors, Algorithms and Models for the Web Graph, in Proceedings of the 2015 Workshop on Algorithms for the Web-Graph (Springer, Cham, 2015), Vol. 9479, pp. 190–202.
  49. M. Cucuringu, V. D. Blondel, and P. Van Dooren, Extracting Spatial Information from Networks with Low-Order Eigenvectors, Phys. Rev. E 87, 032803 (2013).
  50. P. Barucca, D. Tantari, and F. Lillo, Centrality Metrics and Localization in Core-Periphery Networks, J. Stat. Mech. 2, 023401 (2016).
  51. S. Suweis, Effect of Localization on the Stability of Mutualistic Ecological Networks, Nat. Commun. 6, 10179 (2015).
  52. D. Taylor, S. A. Myers, A. Clauset, M. A. Porter, and P. J. Mucha, Eigenvector-Based Centrality Measures for Temporal Networks, Multiscale Modeling Sim. 15, 537 (2017).
  53. J. A. Méndez-Bermúdez, G. F. de Arruda, F. A. Rodrigues, and Y. Moreno, Scaling Properties of Multilayer Random Networks, Phys. Rev. E 96, 012307 (2017).
  54. N. B. Murphy, E. Cherkaev, and K. M. Golden, Anderson Transition for Classical Transport in Composite Materials, Phys. Rev. Lett. 118, 036401 (2017).
  55. P. W. Anderson, Localized Magnetic States in Metals, Phys. Rev. Lett. 124, 41 (1961).
  56. E. Abrahams, P. W. Anderson, D. C. Licciardello, and T. V. Ramakrishnan, Scaling Theory of Localization: Absence of Quantum Diffusion in Two Dimensions, Phys. Rev. Lett. 42, 673 (1979).
  57. F. Shi, S. Wang, M. G. Forest, and P. J. Mucha, Percolation-Induced Exponential Scaling in the Large Current Tails of Random Resistor Networks, Multiscale Modeling Sim. 11, 1298 (2013).
  58. F. Shi, S. Wang, M. G. Forest, P. J. Mucha, and R. Zhou, Network-Based Assessments of Percolation-Induced Current Distributions in Sheared Rod Macromolecular Dispersions, Multiscale Modeling Sim. 12, 249 (2014).
  59. V. Sekara, A. Stopczynski, and S. Lehmann, Fundamental Structures of Dynamic Social Networks, Proc. Natl. Acad. Sci. U.S.A. 113, 9977 (2016).

Outline

Information

Phys. Rev. X 7, 031056– Published 26 September, 2017
  • Received 14 September 2016
Creative Commons Logo

Published by the American Physical Society under the terms of the Creative Commons Attribution 3.0 License. Further distribution of this work must maintain attribution to the author(s) and the published article’s title, journal citation, and DOI.

Published by the American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation