Community detection over a heterogeneous population of non-aligned networks
This addresses a gap in clustering for partially aligned or unaligned graphs, which is incremental as it extends existing SBM methods to handle heterogeneity without node alignment.
The paper tackles the problem of community detection in heterogeneous non-aligned networks, where graphs lack node mappings, by developing a joint stochastic blockmodel (Joint SBM) and an efficient spectral clustering approach. The result shows that this joint model outperforms separate SBMs on each graph in estimating communities, as demonstrated on synthetic and real-world datasets.
Clustering and community detection with multiple graphs have typically focused on aligned graphs, where there is a mapping between nodes across the graphs (e.g., multi-view, multi-layer, temporal graphs). However, there are numerous application areas with multiple graphs that are only partially aligned, or even unaligned. These graphs are often drawn from the same population, with communities of potentially different sizes that exhibit similar structure. In this paper, we develop a joint stochastic blockmodel (Joint SBM) to estimate shared communities across sets of heterogeneous non-aligned graphs. We derive an efficient spectral clustering approach to learn the parameters of the joint SBM. We evaluate the model on both synthetic and real-world datasets and show that the joint model is able to exploit cross-graph information to better estimate the communities compared to learning separate SBMs on each individual graph.