Reparameterized Stochastic Block Model Adaptive to Heterogeneous Degree and Block Distributions

The stochastic block model (SBM) has recently gained popularity in network-oriented structure discovery and analysis, and demonstrated great superiority in the aspects of modeling flexibility, mining accuracy, and application simplicity. However, the existing SBMs are lack of adaptability in characterizing various kinds of distributions of node degree and block size commonly existed in real-world networks, because the model itself limits the node degree and block size subject only to uniform and multinomial distributions, respectively, disabling it to capture the heterogeneities of node degree and block size following other distributions. In this paper, a reparameterized SBM, named as RSBM, is proposed with broader and generalized formulation, which is adaptable to various types of networks with heterogeneous block and degree distributions. Moreover, an efficient learning algorithm for the RSBM is proposed, enabling the model to perform the parameter estimation and model selection concurrently, which significantly reduces the time complexity from $O(n^{5})$ to $O(n^{2.5})$ . Extensive experiments on various types of synthetic and real-world networks demonstrate that our proposed method outperforms the state-of-the-art methods in terms of both accuracy and scalability.