Discovering Block Structure in Networks

Abstract

A generalization of modularity, called block modularity, is defined. This is a quality function which evaluates a label assignment against an arbitrary block pattern. Therefore, unlike standard modularity or its variants, arbitrary network structures can be compared and an optimal block matrix can be determined. Some simple algorithms for optimising block modularity are described and applied on networks with planted structure. In many cases the planted structure is recovered. Cases where it is not are analysed and it is found that strong degree-correlations explain the planted structure so that the discovered pattern is more `surprising' than the planted one under the configuration model. Some well studied networks are analysed with this new method, which is found to automatically deconstruct the network in a very useful way for creating a summary of its key features.

References in corpus (13)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• From Louvain to Leiden: guaranteeing well-connected communities
• Cooperative Game Theory Approaches for Network Partitioning
• Resolution limit in community detection
• Comparing community structure identification
• Modularity and community detection in bipartite networks
• A Review of Stochastic Block Models and Extensions for Graph Clustering
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Finding multiple core-periphery pairs in networks
• Core-periphery structure requires something else in the network
• Universality of the stochastic block model
• Modularity and Projection of Bipartite Networks