您好，以上文档是发表于《journal on communications》2024年3月第45卷第3期的一篇原创性研究论文。该研究由来自广东海洋大学、燕山大学和东北石油大学的研究团队完成。论文标题为“基于多核心节点的增量式动态社区发现算法”，英文标题为“incremental dynamic community discovery algorithm based on multi-core nodes”。本文旨在向您介绍这项研究的核心内容。

一、 研究团队与发表信息 本研究的通讯作者单位为广东海洋大学和燕山大学。主要作者包括陈晶（广东海洋大学数学与计算机学院）、刘志君（燕山大学信息科学与工程学院/河北省虚拟技术与系统集成重点实验室）、杨新宇（燕山大学信息科学与工程学院/河北省虚拟技术与系统集成重点实验室）、刘洺辛（广东海洋大学电子信息工程学院）和刘苗苗（东北石油大学计算机与信息技术学院）。该研究成果于2024年3月正式发表在《journal on communications》（通信学报）上。

二、 研究背景与目标 本研究属于复杂网络分析与数据挖掘领域，具体聚焦于动态网络中的社区发现问题。社区发现旨在识别网络中联系紧密的节点群组，对于理解社交网络、信息传播、生物网络等具有重要意义。传统的社区发现方法多针对静态网络，而现实世界的网络（如社交关系、通信网络）是动态演变的，节点和连接会随时间增加或消失，导致社区结构也随之变化。

现有的动态社区发现算法，特别是增量式方法，通常基于一个关键假设：社区结构在时间片之间是平稳、渐进变化的。这类方法通过重用前一时刻的社区划分结果，仅对网络中发生变化的部分（增量）进行重新计算，以此提高效率。然而，这种假设在现实中可能不成立。动态网络的演化过程中可能出现社区突然消亡、涌现、分裂或合并等“突发事件”，导致网络结构发生剧烈而非平稳的变化。现有的增量式算法仅关注直接受增量影响的节点，忽略了其邻居节点可能随之发生的连锁反应，这会导致两个主要问题：1) 以牺牲准确性为代价换取计算效率；2) 在连续的时间片上迭代更新时，微小的错误会不断累积，产生“时间漂移”误差，最终使社区划分结果严重偏离真实情况。

为了解决上述问题，本研究团队提出了一种名为“基于多核心节点的增量式动态社区发现算法”，简称MCNIDCD（Multi-Core Nodes based Incremental Dynamic Community Discovery）。该算法的核心目标是：在保持增量式方法高效性的同时，通过更精细地识别和处理受网络变化影响的节点范围，显著提升动态社区发现的准确性、稳定性以及对突发事件（如社区剧变）的适应能力。

三、 研究方法与工作流程 MCNIDCD算法的整体框架是一个分阶段、多策略的增量处理流程，其核心思想在于区分并利用两类功能不同的“核心节点”来精准控制社区结构演化的影响范围。具体工作流程如下：

第一步：初始化与核心节点识别 * 初始化：在初始时间片（t=0），算法使用成熟的静态社区发现算法Louvain生成一个准确的初始社区结构，作为后续增量更新的基准。 * 核心节点分类与识别：这是本研究的创新关键。算法将核心节点分为两类，以应对不同类型的社区演化动力： * 扩散型核心节点：这类节点具有强大的信息或影响力传播能力。研究采用影响力最大化中的“度折扣”启发式方法，选取网络中前10%的影响力最大的节点作为扩散核心节点集合（记为dispersel_t）。这类节点的变动容易引起影响的广泛扩散，可能导致社区扩张、合并或信息跨社区传播。 * 内聚型核心节点：这类节点是维持社区内部紧密连接的关键。研究采用分解2-core子图的方法来识别：在一个社区的2-core子图（所有节点度至少为2的子图）中，迭代地移除度数最大的节点，直到子图不再连通。这些被移除的节点对于维持社区的连通性至关重要，构成了内聚核心节点集合（记为gatherl_t）。删除这类节点容易导致社区内部连接变稀疏、分裂或消亡。

第二步：增量事件的分类与局部更新策略 当网络从时刻t-1演化到时刻t时，算法接收网络增量变化（ΔGt），包括新增节点、删除节点、新增边、删除边四种类型。算法结合前一时刻的社区划分结果（C{t-1}）和当前时刻识别出的两类核心节点，设计了一套精细化的局部更新策略，以确定哪些节点的社区归属需要重新计算。 算法维护两个节点集合：finishl_t（继承历史标签，暂不处理的节点）和unfinishl_t（受增量影响，需要重新计算社区归属的节点）。核心策略是根据增量类型和所涉及节点的核心节点类型，来决定将哪些节点从finishl_t移动到unfinishl_t。具体策略包括： 1. 增加边策略：如果新增边的两个端点属于不同社区，且其中至少有一个是扩散核心节点，则影响范围较大，可能触发社区合并或重组。算法会将相关社区的更多节点（甚至整个社区）放入unfinishl_t进行重新评估。 2. 删除边策略：如果删除边的两个端点属于同一社区，且其中至少有一个是内聚核心节点，则该边的移除可能严重破坏社区的内部凝聚力，容易导致社区分裂。因此，算法会将整个社区的节点放入unfinishl_t。 3. 增加节点策略：对于新增节点，如果它是扩散核心节点，则其加入不仅影响自身，还可能扰动其邻居所在的社区，因此将其邻居所在社区的所有节点都纳入unfinishl_t。 4. 删除节点策略：对于被删除的节点，如果它是内聚核心节点，其移除可能对原社区结构造成重大破坏，因此将其原属社区的所有节点及邻居节点都放入unfinishl_t。 对于不涉及核心节点的常规增量变化，算法仅将直接受影响的邻居节点放入unfinishl_t。这套策略的核心是：通过核心节点的类型（扩散/内聚）来放大或收束由网络变化引发的“影响涟漪”，从而更准确地划定需要重新计算的节点范围，避免了错误累积。

第三步：社区归属重计算与合并优化 将所有标记为unfinishl_t的节点各自初始化为一个独立的“小社区”，与finishl_t中已确定的社区共同构成一个“中间社区结构”。然后，算法采用一种增量模块度最大化的方法对这个中间结构进行优化和合并。 * 增量模块度：论文定义了增量模块度（ΔQ）公式来衡量将一个节点（或社区）合并到另一个社区时，对整体社区结构质量（模块度）的贡献。ΔQ考虑了由于增量变化（边或节点的增删）带来的网络结构变化。 * 优化流程：这是一个迭代过程，类似于Louvain算法但作用于增量上下文：1) 尝试将unfinishl_t中的每个节点（或小社区）移动到其邻居社区，计算ΔQ；2) 将节点移动到能使ΔQ获得最大正增益的邻居社区；3) 重复此过程直到没有节点可以移动以获得正增益；4) 将网络压缩，将同一社区的节点聚合为一个超节点，然后在新网络上重复步骤1-3，直到整个网络的模块度不再增加。 这个过程的目标是找到一种社区划分，使得在融入新变化后，网络的整体模块度（社区内部连接紧密、社区之间连接稀疏的程度）最大化，从而得到当前时刻t的最优社区划分结果C_t。

四、 实验结果与分析 研究团队在人工合成网络和真实网络数据集上对MCNIDCD算法进行了全面评估，并与LabelRankT、DynMOGA、PDG、IncNSA、TMOGA等五种先进的动态社区发现算法进行了对比。评价指标主要采用模块度，其值越高表明社区划分质量越好。

1. 人工网络实验： 研究者生成了三种不同类型演化事件（社区生成与消亡、扩张与收缩、合并与分裂）的人工动态网络，每个网络包含10个时间快照。实验结果显示： * 整体性能：MCNIDCD在三种事件类型上的模块度值均表现最佳或接近最佳，且随着时间推移，其模块度值最为稳定，波动最小。这表明MCNIDCD能够很好地适应不同类型的社区演化模式。 * 算法稳定性：对比算法如PDG和IncNSA，其模块度值在不同时间片上波动较大。MCNIDCD通过引入核心节点控制影响范围和增量模块度优化，有效抑制了误差累积，展现出优异的稳定性。 * 演化相关性分析：通过计算相邻时间片社区之间的Jaccard相似度并可视化，发现MCNIDCD的结果中，对角线（表示社区保持稳定）颜色较深，符合动态社区“平滑演化”的预期。同时，在不同事件类型的网络中，相关性图谱也清晰地反映了社区生成/消亡（对角线白色区域多）、扩张/收缩（对角线黑色集中）、合并/分裂（对角线灰色集中）的模式，证明了算法划分结果的合理性。

2. 真实网络实验： 实验使用了两个真实数据集：PhoneCall（10天的手机通话记录）和AS-Oregon（9个时间片的互联网自治系统路由图）。 * 模块度提升：在PhoneCall数据集上，MCNIDCD在所有时间快照的模块度均高于对比算法。在AS-Oregon数据集上，MCNIDCD的平均模块度达到0.6204，优于其他对比算法。 * 显著性能优势：论文指出，在真实网络实验中，MCNIDCD算法在模块度性能指标上平均提升了28%。更重要的是，其模块度曲线非常平稳，而其他算法（如IncNSA和DynMOGA）的模块度值波动剧烈。这证明在面对更复杂、演化模式未知的真实网络时，MCNIDCD在保持高划分质量的同时，具有更强的鲁棒性和稳定性。

五、 研究结论与价值 本研究成功提出并验证了MCNIDCD算法。该算法通过创新性地将核心节点区分为扩散型和内聚型，并据此设计针对四种增量类型的精细化局部更新策略，精确地划定了网络变化的影响范围。随后，通过增量模块度最大化的优化过程，有效地将受影响的节点重新分配到合适的社区中。 结论表明，MCNIDCD算法能够有效克服传统增量式算法因忽略影响传播和错误累积而导致的准确率下降问题。它在人工和真实网络数据集上均表现出色，不仅模块度（社区划分质量）高，而且时间稳定性好，能够更准确地捕捉动态社区的演化过程，包括处理社区突发性剧变。这对于深入研究社交网络演化、舆情传播、蛋白质相互作用网络变化等具有重要的理论和应用价值。

六、 研究亮点 1. 核心节点分类的创新：首次在增量式动态社区发现中明确区分并利用“扩散型”和“内聚型”两类功能迥异的核心节点，分别应对社区扩张/合并和内部分裂/消亡两种演化动力，这是对核心节点理论在动态场景下的重要深化。 2. 精细化局部更新策略：基于核心节点类型和增量类型（增/删节点/边）的组合，设计了四类差异化的更新策略。这种策略不再是“一刀切”地处理所有变化，而是根据变化的性质和所处网络位置进行智能响应，极大提升了影响范围判定的准确性。 3. 显著的性能提升与稳定性：实验数据有力地证明了该算法的优越性。尤其是在真实复杂网络环境下，算法在提升模块度的同时，显著改善了结果的稳定性，解决了增量算法中长期存在的时间漂移问题。 4. 系统的算法框架：算法从核心节点识别、到增量分类处理、再到增量模块度优化合并，形成了一个完整、自洽的增量式动态社区发现框架，逻辑清晰，可复现性强。

七、 未来展望 论文在结尾处指出了未来的研究方向：探索如何将MCNIDCD算法应用于更大规模的网络环境中，并进一步优化算法的性能，例如在处理超大规模网络时的计算效率等。这为后续研究提供了明确的思路。