Automatic exploration of structural regularities in networks

Abstract

Complex networks provide a powerful mathematical representation of complex systems in nature and society. To understand complex networks, it is crucial to explore their internal structures, also called structural regularities. The task of network structure exploration is to determine how many groups in a complex network and how to group the nodes of the network. Most existing structure exploration methods need to specify either a group number or a certain type of structure when they are applied to a network. In the real world, however, not only the group number but also the certain type of structure that a network has are usually unknown in advance. To automatically explore structural regularities in complex networks, without any prior knowledge about the group number or the certain type of structure, we extend a probabilistic mixture model that can handle networks with any type of structure but needs to specify a group number using Bayesian nonparametric theory and propose a novel Bayesian nonparametric model, called the Bayesian nonparametric mixture (BNPM) model. Experiments conducted on a large number of networks with different structures show that the BNPM model is able to automatically explore structural regularities in networks with a stable and state-of-the-art performance.

18 pages, 3 figures

References in corpus (13)

• Fast unfolding of communities in large networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• The structure and dynamics of multilayer networks
• Mixture models and exploratory analysis in networks
• Narrow scope for resolution-limit-free community detection
• Degree mixing in multilayer networks impedes the evolution of cooperation
• Topology-driven instabilities: the theory of pattern formation on directed networks
• Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement
• Generalized friendship paradox in complex networks: The case of scientific collaboration
• Experience versus Talent Shapes the Structure of the Web