A network community detection method with integration of data from multiple layers and node attributes

Abstract

Multilayer networks are in the focus of the current complex network study. In such networks multiple types of links may exist as well as many attributes for nodes. To fully use multilayer -- and other types of complex networks in applications, the merging of various data with topological information renders a powerful analysis. First, we suggest a simple way of representing network data in a data matrix where rows correspond to the nodes, and columns correspond to the data items. The number of columns is allowed to be arbitrary, so that the data matrix can be easily expanded by adding columns. The data matrix can be chosen according to targets of the analysis, and may vary a lot from case to case. Next, we partition the rows of the data matrix into communities using a method which allows maximal compression of the data matrix. For compressing a data matrix, we suggest to extend so called regular decomposition method for non-square matrices. We illustrate our method for several types of data matrices, in particular, distance matrices, and matrices obtained by augmenting a distance matrix by a column of node degrees, or by concatenating several distances matrices corresponding to layers of a multilayer network. We illustrate our method with synthetic power-law graphs and two real networks: an Internet autonomous systems graph and a world airline graph. We compare the outputs of different community recovery methods on these graphs, and discuss how incorporating node degrees as a separate column to the data matrix leads our method to identify community structures well-aligned with tiered hierarchical structures commonly encountered in complex scale-free networks.

References in corpus (19)

• Emergence of scaling in random networks
• Community structure in social and biological networks
• Modularity and community structure in networks
• Community detection in graphs
• Multilayer Networks
• Stochastic blockmodels and community structure in networks
• The spatial structure of networks
• Structure and inference in annotated networks
• Consistency of spectral clustering in stochastic block models
• Consistency of community detection in networks under degree-corrected stochastic block models
• Parsimonious module inference in large networks
• Identifying modular flows on multilayer networks reveals highly overlapping organization in social systems
• Inferring the mesoscale structure of layered, edge-valued and time-varying networks
• Detecting Multiple Communities Using Quantum Annealing on the D-Wave System
• Community detection with node attributes in multilayer networks
• Network structure, metadata and the prediction of missing nodes and annotations
• Community Detection in Networks using Graph Distance
• Regular Decomposition: an information and graph theoretic approach to stochastic block models
• Community recovery in non-binary and temporal stochastic block models