研究融合网络与属性信息的社区发现，给出误分率下界并提出高效算法。
Community Detection for Contextual-LSBM: Theoretical Limitations of Misclassification Rate and Efficient Algorithms
- 基于谱方法设计针对上下文随机块模型的社区检测算法。
- 理论证明任意算法的误分率至少为某下界，该下界在退化情形下恢复已有结果。
- 适用于需结合网络结构与节点属性的社交网络或生物数据挖掘场景。
近年来，将网络信息与节点属性信息结合的社区检测受到广泛关注。本文研究上下文标记随机块模型（CLSBM）下的社区检测问题，其中网络结构服从随机块模型（LSBM），节点属性服从高斯混合模型（GMM）。研究重点为误分率，即社区检测算法期望的误分类节点数。我们首先建立了任意算法都不可突破的误分率下界。当退化到仅保留网络信息的LSBM或仅保留属性信息的GMM时，该下界恢复了已有结果。此外，我们提出一种面向CLSBM的高效谱基算法，并推导其误分率的上界。尽管该算法未达到理论下界，但可作为设计更精确算法的可靠起点（因许多算法以谱方法为初始化，再通过精炼步骤提升精度）。
原文摘要 · Abstract (English)
The integration of network information and node attribute information has recently gained significant attention in the community detection literature. In this work, we consider community detection in the Contextual Labeled Stochastic Block Model (CLSBM), where the network follows an LSBM and node attributes follow a Gaussian Mixture Model (GMM). Our primary focus is the misclassification rate, which measures the expected number of nodes misclassified by community detection algorithms. We first establish a lower bound on the optimal misclassification rate that holds for any algorithm. When we specialize our setting to the LSBM (which preserves only network information) or the GMM (which preserves only node attribute information), our lower bound recovers prior results. Moreover, we present an efficient spectral-based algorithm tailored for the CLSBM and derive an upper bound on its misclassification rate. Although the algorithm does not attain the lower bound, it serves as a reliable starting point for designing more accurate community detection algorithms (as many algorithms use spectral method as an initial step, followed by refinement procedures to enhance accuracy).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。