由于连接的广泛可用性和无处不在的特性,像Facebook、Twitter(现在称为X)、WhatsApp和WeChat这样的社交网络平台受到了极大的关注。用户在社交网络中利用这些平台进行互动和信息共享。通过点赞、评论、分享和消息等频繁的互动表明了用户之间的共同兴趣,从而在网络中形成了连接。这些连接在塑造网络中的模块化组织或社区方面起着重要作用。Cao等人(2025)将社交网络中的社区定义为一组具有强内部连接和弱外部连接的节点。在过去十年中,社区检测问题在网络科学中变得非常流行(Arya, Pandey, & Saxena, 2022)。它有助于分析通过社交联系相连的人们的共同兴趣和行为(Niu, Kong, Liu, Wen, & Xiao, 2023; Wu, 2024; Zhuo, Chen, Yu, & Cao, 2024)。
随着用户之间互动的增加,社交网络中社区检测的复杂性也随之增加,导致网络内部形成了相互连接的社区。同时属于多个社区的用户越来越多(Das & Biswas, 2024)。检测这种重叠社区引起了广泛关注,因为它能更好地解释网络中的复杂社会关系和互动。最近引入了许多重叠社区检测方法,反映了改进重叠社区检测的多样化努力。基于密度的模糊社区检测(DFCD)、使用局部邻域的重叠社区检测算法(OCLN)和基于DeepWalk的标签传播算法(DPLPA)通过依赖局部信息来检测重叠社区(Cheng, Wang, Zhang, & Yang, 2020; Roy & Muhuri, 2025; Yu, Ma, Chao, & Zhang, 2022)。DFCD使用随机游走来获得总体密度得分,但这个得分过于模糊,无法确定重叠节点的成员数量。在OCLN和Core Expansion中,对简单局部邻域指标(如共享邻居)的依赖会影响种子扩展过程。在高重叠区域,这种方法过于宽松;而在低重叠区域则过于严格,可能导致合法的社区结构被忽略。DPLPA算法用于标签分配的DeepWalk嵌入在低重叠场景中不足以准确确定重叠节点的成员身份。像UMST方法(UMSTMO)、加权局部聚类(WLC)和贪婪耦合种子扩展(GREESE)这样的算法主要通过关注拓扑凝聚力来识别重叠社区(Asmi & Abarda, 2022; Asmi, Lotfi, & Abarda, 2022; Asmi, Lotfi, & Marraki, 2020)。然而,这些算法采用的结构启发式方法容易受到社区边界不明确和重叠分配不一致等挑战的影响,最终导致性能不佳。因此,UMSTMO、WLC和GREESE无法在复杂网络中准确估计重叠节点的数量和成员数量。
上述讨论指出,现有的社区检测算法(如DFCD、OCLN、DPLPA、UMSTMO、GREESE和WLC)通常依赖于局部启发式方法和结构依赖性,导致它们在高重叠和低重叠场景中无法准确识别重叠社区的数量和成员数量。这一限制促使我们开发了一种有效应对这些挑战的重叠社区检测方法。最近,将信息扩散纳入重叠社区检测以提升性能受到了关注。这种方法利用了对网络扩散模式和信息交换过程中用户行为的洞察来提高社区检测的有效性(Das & Biswas, 2021b; Das, Biswas, & Saxena, 2022; Das, Devarapalli, & Biswas, 2024)。然而,由于网络的多样性,信息扩散驱动的社区检测方法也难以确保所需的质量。
在这项工作中,我们旨在设计一种能够准确识别多样化网络中重叠节点数量和成员数量的重叠社区检测算法。为此,我们关注同质性,即用户倾向于与志同道合的人建立联系的倾向,这显著影响社交互动(Saxena, Kumar, & Meena, 2025)。基于这一原则,我们提出了Sangam,这是一种基于信息扩散的社区检测算法,它采用了两个新颖的概念:成对同质性得分和基于节点的社区同质性。在信息扩散过程中应用成对同质性得分来确定社区级联。随后,通过考虑内部和外部连接以及基于节点的社区同质性来处理这些级联,以提取潜在社区。通过将信息扩散与同质性相结合,Sangam算法提供了一种稳健的社区检测方法。本文的主要贡献如下:
- •
引入了成对同质性得分和基于节点的社区同质性等新颖概念,以识别多样化网络中的微妙社区。
- •
使用LFR基准网络和真实世界数据集进行的实证分析,以及与最先进重叠社区检测算法的比较,证明了Sangam算法在高重叠和低重叠场景中的有效性。
- •
实验结果证实了Sangam算法在准确识别重叠节点数量和成员数量方面的有效性。
- •
Sangam算法的时间复杂度为O(n*k^2),其中n和k分别表示节点数量和网络的平均度。在无向连通网络中,这一时间复杂度可以进一步降低到O(m*k)
在本节中,我们从网络科学和扩散理论的既定原则出发,理论证明了信息扩散与同质性路径融合机制的新颖性。在社区级联生成步骤中,我们将成对同质性得分与扩散路径相结合,以反映相似节点更频繁参与信息扩散的倾向(Mcpherson, Smith-Lovin, & Cook, 2001)。通过将同质性融入扩散过程,节点加入级联的概率成为现有级联节点的总体成对同质性和发起者与每个非活跃节点之间的成对同质性得分的函数。这种方法扩展了传统的概率扩散模型(如独立级联模型),通过优先考虑相似节点之间的路径,从而更好地模拟现实世界的社交传染。在社区形成步骤中,我们根据内部-外部连接处理这些级联来检测重叠社区,这一策略基于模块性和传导性概念(Das & Biswas, 2021a; Zhou, Wang, & Cui, 2025)。根据共享连接合并社区,并使用基于节点的社区同质性分配空闲节点,确保捕捉到结构和属性上的相似性。因此,我们方法的每一步都是基于数学的,其新颖性可以通过其与现有网络科学理论模型的直接对齐和扩展来验证。