摘要 :
复杂网络是复杂系统的抽象表现，例如电力网络、交通网络、引文网络、生态网络等。通常网络中的节点可以分成多个组，组内节点间连接相对紧密，不同组节点间连接相对稀疏，这些节点组被称为社区。社区结构是复杂网络的重要特性之一，发现网络中的社区...
展开
复杂网络是复杂系统的抽象表现，例如电力网络、交通网络、引文网络、生态网络等。通常网络中的节点可以分成多个组，组内节点间连接相对紧密，不同组节点间连接相对稀疏，这些节点组被称为社区。社区结构是复杂网络的重要特性之一，发现网络中的社区结构有助于深入分析和理解复杂系统功能、演化机制等。
网络规模的增大导致社区组成更加复杂，节点与社区之间的关系也更多样化。对一个社区发现算法而言，如果一个节点的邻居节点属于相同社区，则该节点具有相对明确的社区归属；如果一个节点的邻居节点分别属于多个社区，则该节点的社区归属不明确，确定其社区归属有一定难度。有效的度量节点邻域的社区构成，并对社区归属确定性有差异的节点分别处理，有望提高社区发现算法的性能。本文对基于节点稳定性的社区发现算法进行研究，主要工作有：
(1)给出了一种基于标签熵的节点稳定性度量方法(Node Stability measurement method based on label entropy)，对节点社区归属的确定性进行度量。由于无法事先获取节点及其邻域的社区归属的先验信息，本文采用接近线性时间复杂度的标签传播算法LPA对网络进行预处理，根据各节点获得的社区标签情况，定义了基于标签熵的节点稳定性度量指标。若一个节点社区归属比较明确，则其邻域节点的社区标签比较单一；反之若一个节点社区归属比较模糊，则其邻域节点包含更多的社区标签。利用信息熵计算标签传播算法在不同节点上表现的稳定性，可以度量节点社区归属的确定性，称为节点的标签熵。标签熵较低的节点易于得到准确的社区划分结果，而标签熵较高的节点通常是社区发现过程中的困难节点。
(2)提出了一种基于节点稳定性的社区发现算法(Node Stability based community detection Algorithm, NSA)，包括稳定节点选择、初始社区获取、未聚类节点处理三个主要过程。首先根据节点标签熵选择稳定节点集；再利用直接邻域对稳定节点进行扩展得到子网络，并在其上运行LPA(Label Propagation Algorithm)算法得到初始社区；计算未聚类节点与初始社区的连接紧密程度，得到最终社区发现结果。先对稳定节点聚类得到初始社区，再对剩余不稳定节点进行社区划分，可以提高算法对困难节点的社区发现能力。在4个带标签网络和8个无标签网络上，与LPA，Infomap，Walktrap，BGLL，LPA-S等经典的社区发现算法进行对比实验，结果表明NSA算法在模块度以及标准互信息方面表现良好。
(3)提出了一种基于节点稳定性和邻域相似性的社区发现算法(Node Stability and Neighbor Similarity based community detection Algorithm, NSNSA)。尽可能选择与稳定节点位于同一社区的节点来对稳定节点进行扩展，可以减小子网络规模，进一步提高所获得初始社区的准确性。此处采用标签传播算法对网络进行预处理，根据各节点及其邻居节点的标签情况，进一步定义节点邻域相似性，对节点与其邻居节点的社区归属一致性进行度量。首先选择标签熵较低的节点作为稳定节点集，在其直接邻居中选择邻域相似性最高的节点对进行扩展得到初始子网络；在该子网络上运行标签传播算法得到初始社区；将未聚类节点分配至与其Katz相似性最高的节点所在社区；对小规模社区进行合并处理，得到最终的社区划分结果。在14个真实网络上，与LPA，Infomap，Walktrap，BGLL，LPA-S等经典的社区发现算法进行对比实验，结果表明NSNSA算法在模块度以及标准互信息方面表现良好。
收起
