A Scalable Redefined Stochastic Blockmodel

Stochastic blockmodel (SBM) is a widely used statistical network representation model, with good interpretability, expressiveness, generalization, and flexibility, which has become prevalent and important in the field of network science over the last years. However, learning an optimal SBM for a given network is an NP-hard problem. This results in significant limitations when it comes to applications of SBMs in large-scale networks, because of the significant computational overhead of existing SBMmodels, as well as their learning methods. Reducing the cost of SBM learning and making it scalable for handling large-scale networks, while maintaining the good theoretical properties of SBM, remains an unresolved problem. In this work, we address this challenging task from a novel perspective of model redefinition. We propose a novel redefined SBM with Poisson distribution and its block-wise learning algorithm that can efficiently analyse large-scale networks. Extensive validation conducted on both artificial and real-world data shows that our proposed method significantly outperforms the state-of-the-art methods in terms of a reasonable trade-off between accuracy and scalability.(1)

Automated summary

Stochastic blockmodel (SBM) is a widely used statistical network representation model with good interpretability and flexibility. Learning an optimal SBM is an NP-hard problem, resulting in limitations for its applications in large-scale networks. A novel redefined SBM with Poisson distribution and its block-wise learning algorithm have been proposed in this work to efficiently analyze large-scale networks, outperforming state-of-the-art methods in terms of accuracy and scalability.