Asymptotic resolution bounds of generalized modularity and statistically significant community detection

Xiaoyan Lu, Boleslaw K. Szymanski

The maximization of generalized modularity performs well on networks in which the members of all communities are statistically indistinguishable from each other. However, there is no theory defining the maximization performance in more realistic networks where edges are heterogeneously distributed within and between communities. We establish the asymptotic theoretical bounds on the resolution parameter of generalized modularity using the random graph properties. From this new perspective on random graph model, we find the resolution limit of modularity maximization can be explained in a surprisingly simple and straightforward way. Given a network produced by the stochastic block models, the communities for which the resolution parameter is larger than their densities are likely to be spread among multiple clusters; while communities for which the resolution parameter is smaller than their background inter-community edge density get merged into one large component. Therefore, no suitable resolution parameter exits when the intra-community edge density in a subgraph is lower than the inter-community edge density in some other subgraph. For such networks, we propose a progressive agglomerative heuristic algorithm to detect statistically significant communities at multiple scales.

Knowledge Graph



Sign up or login to leave a comment