编辑推荐：
本文提出了一种基于阈值规则的共享节点识别方法，能够有效区分复杂网络重叠社区中真正的重叠节点与由噪声或内部子社区结构引起的伪重叠。该方法通过比较嵌套结构中内外层节点数量比值与预设阈值，动态筛选出具有显著连接作用的重叠节点（Overlapping Nodes）。研究应用五个真实网络数据集（包括社交网络和通信网络）进行验证，结果表明随着阈值增加，筛选出的重叠节点数量减少，但其在网络信息流动和社区连接中的影响力愈加凸显。该框架不依赖于特定社区检测算法，为分析网络结构功能（如社交网络分析、网络安全）提供了通用且可调节的工具。
引言
复杂网络中的社区检测是分析网络结构的重要方面，有助于识别复杂系统（如社交和生物网络以及信息物理系统）中的集群或模块。社区可分为非重叠（Non-overlapping）、重叠（Overlapping）或层次化（Hierarchical）类型。重叠社区允许节点同时属于多个社区，例如社交网络中的个体可能分属家庭、学校、兴趣团体等不同社交圈。重叠节点在网络结构和功能中扮演关键角色，通常作为桥梁促进不同社区间的信息或影响流动。识别和分析重叠节点对于理解复杂系统的运行机制至关重要，例如揭示基础设施网络中的关键脆弱点或改进传播过程（如意见扩散或传染）的预测。然而，现有重叠社区检测方法在区分真正的多重隶属关系与噪声或高度连接节点引起的伪影方面存在局限，且缺乏对重叠节点的统一后处理框架。
相关工作
重叠社区的研究已成为网络科学的重要课题。早期社区检测方法假设不相交的社区划分，但后续研究揭示社交、生物和信息网络经常表现出共享或模糊的节点隶属关系。重要贡献包括派系渗流方法（Clique Percolation Method, CPM）、链接社区（Link Communities）以及基于局部统计适应度优化的框架。概率模型如混合隶属随机块模型（Mixed Membership Stochastic Block Model, MMSBM）通过统计推断形式化了节点的重叠隶属。近年来，机器学习方法如BigCLAM、CESNA以及基于图神经网络（Graph Neural Networks, GNN）的方法（如图卷积网络（Graph Convolutional Networks, GCN）和图注意力网络（Graph Attention Networks, GAT））被扩展用于重叠社区检测。然而，这些方法在区分真实重叠节点与噪声或内部子社区结构方面仍存在挑战，并且缺乏统一的阈值框架来控制噪声并揭示剩余重叠节点日益增强的影响力。
模型
本研究侧重于识别和分类复杂网络结构内重叠社区的共享节点，并不详细描述特定的社区检测方法，因为识别共享或重叠节点的方法具有通用性，可结合任何能够产生重叠社区的检测方法。为进行演示，应用了作者先前提出的重叠社区检测方法。该节点识别方法包含两个主要阶段：首先，检测社区之间的所有交集，称为构建块（Building Blocks）；其次，评估每个构建块是否符合子社区的标准。不符合子社区标准的社区交集是重叠节点的候选者。随后应用选择规则来确定哪些节点应保留为重叠节点，哪些应被排除。该技术解决了模糊分配节点和噪声的问题。噪声可能源于数据错误、随机连接、不完整采样、网络生成过程中的内在随机性或社区检测方法本身的局限性。
作为算法的第一个选择标准，评估所有社区交集是否应被识别为独立的社区。这涉及检查它们是否是嵌套社区的内部部分，并满足社区的标准（例如，最大化社区检测方法中使用的目标函数）。接下来，需要为未被归类为子社区的交集定义另一个标准。这些交集内的所有节点都可被视为重叠节点，但可以根据考虑节点数量或交集内聚性值的阈值来排除其中一部分。在本研究中，使用节点数量作为选择规则的基础。
在嵌套社区结构中，比较嵌套结构外层与内层的节点数量。随着该比率的增加，规则变得更加严格，导致更多节点被排除，更少的节点被计为剩余的重叠节点。当增加此阈值时，可能仅保留少量节点甚至单个节点作为重叠节点。选择标准表明，在近乎等大的节点集嵌套系统中，这些被排除的节点可被视为内部结构，而非不同社区的重叠节点。
图2说明了社区检测将网络划分为两个部分的情况。左右两图展示了社区检测方法的两种不同解决方案。右图结合了这些部分，并描绘了各种相交和重叠区域：M1∩ K2, M2∩ K2, M1∩ K1, 和 M2∩ K1。这些区域中的节点可用于定义重叠节点的包含和排除标准。重叠的阈值由条件定义，即方程（2）中的比率r必须大于附录B中指定的阈值参数值thr。比率r定义为社区K1中的节点数量与交集M2∩ K2中的节点数量之比。需要注意的是，集合M1∩ K2（或M2∩ K1）为空，因为附录A中的程序已进行了预处理，并将构建块分类为有效的子社区和检测到的社区的其他交集。
数据与演示
本节通过将方法应用于五个真实世界的社交网络来演示其识别重叠社区中重叠节点的实际用途。所使用的网络包括Zachary空手道俱乐部网络、Les Misérables社交网络、经验移动电话呼叫网络、海豚社交网络和Facebook社交圈网络。对于每个网络，将经验观察到的社区结构与网络拓扑所暗示的理论结构进行比较。例如，Zachary空手道俱乐部和海豚社交网络已知会分成两个主要群体，这为评估方法结果提供了有用的参考点。
Zachary空手道俱乐部网络
Zachary空手道俱乐部网络说明了34名俱乐部成员之间的友谊关系。该网络因 instructor（节点1）和 administrator（节点34）之间的分歧而分裂成两个派系，这密切反映了网络的结构。两位领导者都是具有大量连接的高度中心节点，成员通常与他们联系更紧密的领导者站在一边。节点3与两位领导者都有紧密联系，最终根据Zachary的分析加入了instructor的派系。唯一选择与模型预测不一致的成员是节点9，他加入了administrator的派系而不是instructor的派系。这个案例突出了社交网络结构如何有效预测现实世界的群体分裂。
几项研究应用不同的方法来检测Zachary空手道俱乐部网络中的重叠社区，发现尽管最初的划分明显是二元的，但某些节点始终出现在社区之间的边界上。在不同的算法中，节点3、9、10、14和31最常被识别为重叠节点，表明它们与两个派系成员的联系。本研究模型的结果与其他理论模型的结果进行了比较。节点9、10和31被识别为重叠节点，与上述理论模型一致。此外，节点28也被识别为重叠节点。节点9、10、28和31始终存在于同一个子社区内。当它们改变子社区时，它们一起改变。类似地，节点25、26、29和32形成一个类似的组，但通常在现有文献中不被识别为重叠节点。这是因为本研究使用的社区检测方法识别出更多的子社区。在本模型中，即使对于较高的阈值参数值，节点3仍然被分类为重叠节点，这与文献中的其他理论发现一致。与其他理论模型相反，节点14在本模型中被认为不重叠。图3说明了重叠节点分布在网络外围部分的整体情况。
Les Misérables社交网络
几项研究使用Les Misérables社交网络作为检测重叠或混合隶属社区的基准。该网络由维克多·雨果书中的77个虚构角色组成，说明了角色的共同出现，每个节点代表一个角色，每条边连接两个在同一场景或章节中一起出现的角色。叙事中的社交网络包含几个不同的群体：Valjean的群体（节点12、24和27）、革命学生（节点54–65）和Thenardier家族（节点25、26、29和30）。这些群体总共有17个节点，占书中进行社交互动并有助于社区结构的总共77个角色的一部分。
社区结构并不严格反映这些群体，也许除了革命群体，因为故事主要围绕各种角色之间的社交互动展开。社区及其重叠节点涵盖了所有家庭和其他个体，突出了作者超越这些家庭间互动的更广泛故事情节。叙事中的一些角色充当重叠或边界节点，作为不同社区之间的桥梁，连接各种社会群体。在图4中，重叠节点以不同颜色突出显示，说明了反映作者在书中故事发展的关系。
为了研究Les Misérables社交网络的社区结构，Riolo和Newman使用了一种信息论方法。应用诸如基于信息压缩的网络分区等技术，他们识别了社区的“构建块”——经常互动并在整体网络内形成内聚子结构的角色组。在互信息峰值处的八个块的结构包括社区及其交集。将此结构与使用参数值thr=0.0的第一个图（图4）进行比较。在本模型中，白色节点被识别为子社区或其内部结构的成员，彩色节点代表不同阈值下的重叠节点。通过比较得出结论，尽管存在微小差异，但最大的构建块（图5中深蓝色表示）对应于图4中的重叠节点。其他五个较大的块（浅绿色、深绿色、浅蓝色、橙色和紫色表示）对应于本模型中的不同子社区。
经验移动电话呼叫网络
本小节分析的经验数据集基于一个大型移动电话呼叫详细记录数据库。该数据集已被用于研究人类通信模式、其社会结构和行为动力学。数据源自大规模匿名呼叫详细记录，涵盖数百万次互动，捕获了以自我为中心的社交网络，其中节点代表个体，加权边表示通信的强度或频率。基于此数据集的研究探索了各种主题，包括社交链接的强度、通信模式中性别或年龄相关的差异、社交互动中的流动性和内部迁移，以及统计验证主题和时空通信结构的演变。
在此，仅关注移动电话呼叫网络一个子集的拓扑属性。图6中显示增加模型阈值参数值效果的四幅图揭示了一种与本研究中其他案例一致的模式。观察到随着阈值参数值的增加，重叠节点的数量减少。在第四幅图中，只有三个小组作为重叠部分保留下来。与其他检查的网络相比，该网络是稀疏的：社区清晰分离，并且通常仅由一条社区间边连接。这导致即使阈值参数设置为零时，构建块也是不相交的。正如预期的那样，阈值的微小增加进一步减少了剩余的重叠。在某些应用中，甚至可以进一步分析这些少数剩余的重叠组，以确定其中最中心的焦点节点。例如，在通信网络中优化传感器放置的问题中，为每个组只设置一个传感器是可行的。
海豚社交网络
以下示例突出了1994年至2001年间新西兰Doubtful Sound的62只宽吻海豚的无向社交网络。在该网络中，节点代表个体海豚，边连接被观察到在一起的频率高于偶然预期的成对海豚，表明存在显著的社会关联。Lusseau和Newman分析的数据集揭示了一个内聚但模块化的社区结构。
在这项研究期间，一只名为SN100的海豚暂时消失，导致网络分裂成两个子组。当SN100返回时，群体重新联合，证明了一个中心个体的存在或缺席如何影响社会凝聚力。该数据集已成为社交网络分析的关键示例，特别是用于研究社区结构和个体对群体动态的影响。
几项研究已将混合隶属和重叠社区检测方法应用于海豚社交网络。尽管该网络自然地分成两个主要社会群体，但某些海豚始终出现在社区之间的边界上，表明存在重叠的社会归属。例如，研究34识别出的重叠个体包括Beak、Kringel、MN105、Oscar、PL、SN4、SN9和TR99，而研究53在混合隶属模型下发现Beak、Bumper、Fish、Oscar、PL、SN89、SN96和TR77作为边界海豚。Lusseau和Newman在51中的原始分析强调了SN100作为海豚社交网络上关键桥梁个体。总之，这些结果说明某些海豚，特别是Beak、Oscar、PL和SN100，在子群之间扮演着关键的连接者角色，强调了重叠和桥接个体在维持社会凝聚力中的重要性。接下来，将本模型的结果与先前提到的结果进行比较。
表4总结了我们的发现以及文献中一小部分选择的结果。首先，检查图7中的中间和底部面板。海豚Beak、Kringel、MN105、Oscar、PL和TR99与研究34报告的结果一致。相反，SN4和SN9在本模型中没有被识别为重叠节点，尽管它们在图7顶部面板的低阈值下显示为重叠节点。本方法识别出两个组：一个由五只海豚组成——Beak、Bumber、Fish、SN96和TR77，另一个包含两只——Oscar和PL。这种分组方式与研究53的发现相似。在本模型中，这些组即使改变子社区也保持在一起，这在图中以棕色阴影表示。此外，SN89在两种情况下都被识别出来，尽管它在研究34中没有被识别。SN100在底部面板的高阈值下仍然被识别，突出了其在网络结构中的桥接作用。Zap在所有阈值下都被识别为重叠节点，但未在讨论的两个文献模型中出现。
Facebook社交圈网络
包含4039个节点和88,234条边的Facebook自我网络是一个从用户朋友圈中提取的无向社交网络，最初作为SNAP数据集集合的一部分引入。每个节点代表一个Facebook用户，边表示单个自我中心用户的朋友之间的相互友谊。数据集包括通过手动注释得出的真实社交圈，其中自我用户根据现实生活关系和共享属性（包括学校、工作地点、位置或政治派别）将朋友分配到重叠的社交组。这使其成为重叠圈、社区检测和链接预测算法的流行基准。对这些圈的分析也提出了一个问题：圈和社区之间的区别有些模糊，并且这些术语在社交网络科学中经常互换使用。这是有问题的，因为圈虽然反映了一些结构属性（例如，三角闭合和派系），但是属性驱动的，而社区更多是一种拓扑现象。重叠社区检测算法通常针对这些圈进行基准测试，而不是社区。后续研究，包括55，已使用该数据集评估检测到的社区与已知圈隶属的质量。圈与社区之间的相关性在39中讨论。研究我们检测到的重叠节点如何与已知圈交集对齐留待未来工作。
Facebook自我中心网络作为一个大型社交网络结构的例子，说明了我们识别重叠节点和节点组的方法。在图8中，显示了在六种不同场景下重叠的节点，每种场景由递增的阈值参数值表示。当阈值较低时，几乎所有节点都被分类为重叠。这是因为在密集网络中，大多数节点参与多个交集，导致高重叠率。增加阈值会减少重叠节点的数量，最终导致网络中只有少数节点被分类为重叠。有趣的是，随着阈值的增加，保持被分类为重叠的节点不一定是自我节点本身；相反，它们可能位于网络内的任何位置。这表明有影响力的桥接节点通常位于社区内部而不是其边界，这种模式在Twitter网络分析中也观察到。最重要的是，本方法甚至可以揭示在紧密互连的子组中的此类关键桥接节点。使用传统的社区检测方法很难识别此类节点。
讨论
本研究侧重于识别和过滤检测到的重叠社区中的重叠节点。关键问题是如何区分真正的重叠节点与由噪声或高度相似的社区结构引起的看似重叠的节点。检测重叠社区的细粒度方法通常会产生许多密切相关的社区，尤其是在个体属于多个社交圈的社交网络中。在这种密集的环境中，传统方法可能难以划定有意义的边界，并且社区可能共享其大部分成员。在这些情况下，识别真正的桥接节点变得比单独分析社区结构更具信息性。
将过多节点错误分类为重叠会掩盖那些真正连接不同网络区域节点的影响力。本方法通过使用阈值控制结构噪声来解决这个问题，减少由近乎相同的社区组成引起的重叠。这突出了作为真实连接器的节点，并支持对复杂网络中的影响力、信息流和关键参与者进行更准确的分析。此外，一个迄今未涵盖的主题是阈值参数值与网络结构之间的关系。我们的实证结果表明，去除重叠节点所需的最大阈值并非
