Network community detection using higher-order structures

• 成果类型: Article
• 署名作者: Yu, X.; Zhu, J.
• 署名单位: University of Michigan System; University of Michigan
• 刊物名称: BIOMETRIKA
• ISSN/ISSBN: 0006-3444
• DOI: 10.1093/biomet/asae014
• 发表日期: 2024
• 关键词: stochastic blockmodels; models; motifs

摘要

In many real-world networks, it is often observed that subgraphs or higher-order structures of certain configurations, e.g., triangles and by-fans, are overly abundant compared to standard randomly generated networks (). However, statistical models accounting for this phenomenon are limited, especially when community structure is of interest. This limitation is coupled with a lack of community detection methods that leverage subgraphs or higher-order structures. In this paper, we propose a new community detection method that effectively uses higher-order structures in a network. Furthermore, for the community detection accuracy, under an edge-dependent network model that consists of both community and triangle structures, we develop a finite-sample error bound characterized by the expected triangle degree, which leads to the consistency of the proposed method. To the best of our knowledge, this is the first statistical error bound and consistency result for community detection of a single network considering a network model with dependent edges. We also show, in both simulation studies and a real-world data example, that our method unveils network communities that are otherwise invisible to methods that ignore higher-order structures.