基于节点拓扑属性的社团结构划分方法

Community Structure Division Method Based on Node Topology Attributes

摘要: 社团结构，作为复杂网络分析中的核心概念之一，指的是那些拥有相似特性和功能的节点所构成的子图结构。社团结构的划分不仅有助于深入挖掘网络内在的信息和特征，而且还有助于揭示复杂网络系统的演化机制。本研究提出了一种创新的社团结构划分算法，其核心围绕网络结构中节点的拓扑属性。在该算法中，我们首先通过节点的接近中心性和介质中心性构建二维决策矩阵。具体来说，接近中心性揭露了节点在网络中与其他节点的亲密程度，而介质中心性则考虑了节点在网络中的桥接作用。二维决策矩阵的构建旨在从网络的广度和深度双视角考察节点的重要性和功能。然后利用基于K-means的迭代策略找到最优的聚类中心。最后通过加权的Dijkstra算法将剩余节点依据就近的聚类中心进行分配完成社团划分。为验证所提出的算法的有效性，在多个实际存在的社会网络上进行了实验，并将其与已有的算法进行了综合比较。实验结果验证了所提算法的性能，特别是在识别具有强社交关系的Karate数据集的社团关系中，本文所提算法在NMI，ARI，Purity三个评价指标中分别达到了81.56%、83.34%、100.00%，提高了社团划分结果的准确性。

Abstract: Community structure, as a fundamental concept in the analysis of complex networks, refers to sub-graph structures composed of nodes with similar characteristics and functions. The division of community structure not only aids in the in-depth exploration of intrinsic information and features within networks but also helps uncover the evolutionary mechanisms of complex network systems. This study introduces an innovative algorithm for community structure detection, primarily focus-ing on the topological attributes of nodes within the network. In this algorithm, we initially con-struct a two-dimensional decision matrix using node closeness centrality and betweenness central-ity. Specifically, closeness centrality reveals the intimacy of nodes with respect to other nodes in the network, while betweenness centrality considers the bridging role of nodes within the network. The construction of the two-dimensional decision matrix aims to examine the importance and function-ality of nodes from both breadth and depth perspectives of the network. Subsequently, an iterative strategy based on K-means is employed to identify the optimal clustering centers. Finally, the re-maining nodes are allocated to clusters based on their proximity to the designated clustering cen-ters using a weighted Dijkstra algorithm, thus completing the community partition. To validate the effectiveness of the proposed algorithm, experiments were conducted on multiple real-world social networks, and comprehensive comparisons were made with existing algorithms. The experimental results have validated the performance of the proposed algorithm, particularly in identifying the community relationships within the Karate dataset, which is characterized by strong social ties. The proposed algorithm achieved 81.56%, 83.34% and 100.00% respectively in the three evaluation indexes of NMI, ARI and Purity. These metrics indicate an enhancement in the accuracy of the community detection results