基于距离驱动质心的有影响力节点社交网络社区检测方法

《Applied Sciences》：A Distance-Driven Centroid Method for Community Detection Using Influential Nodes in Social Networks Srinivas Amedapu and R. Leela Velusamy

　　

社区检测是复杂网络分析中的关键任务，尤其是在社交网络分析中，揭示内聚且良好分离的群体对于理解组织结构与交互模式至关重要。许多现有的基于质心的社区检测方法主要依赖节点度进行质心选择，这常导致质心拥挤以及社区间空间分离不足。为解决这些限制，本文提出了基于度-距离质心与有影响力节点的社区检测（DDC-CDIN），一种距离驱动且影响力感知的社区检测框架。在所提出的方法中，研究人员首先根据增强度中心性度量对节点进行排序，该度量结合了度信息、邻居结构和局部聚类特征，以识别结构上有影响力的节点。然后通过最大化最短路径距离，从排名靠前的有影响力节点中迭代选择质心，确保所选质心在网络中既具代表性又分布良好。一旦确定质心，研究人员根据最小测地距离将剩余节点分配到社区，从而生成紧凑且边界清晰的聚类。在多个真实世界网络上的广泛实验表明，与传统基于质心及模块度驱动的方法相比，DDC-CDIN在模块度、社区内聚性和边界清晰度方面取得了具有竞争力的性能。结果表明，联合考虑影响力感知节点排序与基于距离的质心散布，有效缓解了质心拥挤问题并提升了整体社区检测质量。这些发现证明了DDC-CDIN在复杂网络中检测结构良好且拓扑连贯社区的有效性和鲁棒性。

### 论文解读：基于距离驱动质心的有影响力节点社区检测方法（DDC-CDIN）

#### 研究背景与问题

复杂网络（如社交平台、基础设施网络、生物网络）中，社区结构（内部连接密集、外部连接稀疏的节点子集）的检测是理解信息扩散、用户分组、网络弹性等任务的基础。传统模块度优化方法虽广泛应用，但存在分辨率限制（难以发现细粒度社区）和对搜索启发式的敏感性。近年来，基于质心（centroid）或种子（seed）的社区检测因可解释性和局部信号利用而受到关注，但质心选择是关键瓶颈：随机选择导致结果不稳定，而仅依赖度（degree）等单一中心性指标则易造成质心拥挤（centroid crowding）——多个高度数节点聚集在一起，吸引重叠邻居，导致社区边界模糊。尽管已有研究引入影响力感知（influence-aware）节点排序或距离驱动（distance-driven）散布，但两者往往被分开处理。为同时解决质心代表性与空间分离性问题，研究人员提出了DDC-CDIN（Degree–Distance Centroid–Community Detection with Influential Nodes）框架，旨在通过融合结构影响力筛选与测地距离最大化，生成紧凑且分离良好的社区结构。该论文发表在《Applied Sciences》。

#### 主要关键技术方法

DDC-CDIN的核心方法分为三步：首先，计算增强度中心性（Enhanced Degree Centrality, EDC），该度量综合节点度、邻居节点度之和以及局部聚类系数，对节点进行影响力排序；其次，从排名前`p = ?αn?`的候选集中，随机选择首个质心，然后迭代选择使得与已选质心最短路径距离之和最大的节点作为后续质心，确保空间散布；最后，将每个剩余节点分配到与其测地距离最近的质心，形成社区。实验采用四个真实网络数据集：Facebook（4039节点）、Power-Grid（4941节点）、Wiki-Vote（7115节点）和Gnutella（6301节点），社区数`k`由35次Louvain算法运行的中位数确定（分别为16、18、21、20）。对比方法包括随机节点头技术（RNHT）、最高度节点头技术（HDNHT）、Louvain和最大最小技术（MMT）。评估指标为平均适应度（Average Fitness）、模块度（Modularity）和运行时间（Runtime）。

#### 研究结果

**Fitness Comparison（适应度比较）**：适应度越低表示社区内连接越紧密、社区间连接越少。在Facebook、Power-Grid、Wiki-Vote和Gnutella数据集上，DDC-CDIN的适应度分别为0.240、0.280、0.210和0.320。与Louvain（0.240, 0.330, 0.210, 0.320）相比，DDC-CDIN在Power-Grid上显著更优，在其他数据集上相当或持平。RNHT、HDNHT和MMT的适应度整体较高，表明DDC-CDIN在增强社区内聚性方面具有优势。

**Modularity Comparison（模块度比较）**：模块度越高代表社区结构越清晰。DDC-CDIN在所有数据集上取得最高模块度：Facebook 0.576（第二高Louvain 0.524）、Power-Grid 0.782（Louvain 0.712）、Wiki-Vote 0.174（Louvain 0.135）、Gnutella 0.264（Louvain 0.214）。该结果证实了DDC-CDIN在生成高内聚、低耦合社区方面的有效性。

**Runtime Comparison（运行时间比较）**：DDC-CDIN的运行时间在Facebook上为3680 ms（快于Louvain 4864 ms和MMT 4438 ms，但慢于RNHT 2041 ms和HDNHT 3601 ms）；在Power-Grid上为925 ms（快于HDNHT、Louvain和MMT）；在Wiki-Vote上为5070 ms（快于Louvain和MMT）；在Gnutella上为2271 ms。整体上DDC-CDIN在计算效率与社区质量之间取得了平衡，尽管不是最快，但显著优于纯距离或纯影响力方法。

#### 讨论与结论

讨论部分指出，DDC-CDIN通过联合考虑影响力节点过滤（EDC）和距离散布，有效缓解了传统质心方法的质心拥挤问题，并在多个真实网络（包括社交、基础设施和点对点网络）上表现出稳定的高质量分区。与传统方法相比，DDC-CDIN在模块度和适应度上均具有竞争力，尤其是在Power-Grid等具有稀疏结构的数据集上优势明显。结论部分明确：DDC-CDIN是一种将结构影响力（Enhanced Degree Centrality）与测地距离散布相结合的混合方法，生成紧凑且分离良好的社区，同时保持计算效率。实验结果表明该策略在不同网络拓扑下能产生稳定、高质量的社区结构。局限性包括：需要预先指定或估计社区数`k`，当前仅适用于无向、无权、非重叠网络，且质心选择中的重复广度优先搜索（BFS）在极大规模网络上可能增加计算开销。未来工作拟扩展至动态、加权、有向和重叠网络，并探索与图神经网络及可解释人工智能技术的结合以增强可扩展性与可解释性。