传播过程中信号缺失的层次聚类社区发现算法

Community detection algorithm based on hierarchical clustering under signal missing in propagating process

社区发现是社会网络分析的一个基本任务,而社区结构探测是社区发现的一个关键问题。将社区结构中的结点看作信号源,针对信号传递过程中存在信号缺失情况,提出了一种层次聚类社区发现算法。该算法通过度中心性来度量节点接收信号的概率,用于量化节点接受信号过程中的缺失值。经过信号传递,使网络的拓扑结构转化为向量间的几何关系,在此基础上,使用层次聚类算法用于发现社区。为了验证SMHC算法的有效性,通过在三个数据集上与SHC算法、CNM算法、GN算法、Similar算法进行比较,实验结果表明,SMHC算法在一定程度上提高了社区发现的正确率。

Community identification is a basic task of social network analysis, meanwhile the community structure detec-tion is a key problem of community identification. Each node in the community structure is regarded as the signal source. A hierarchical clustering community algorithm is proposed in order to settle the problem of signal missing in the process of signal transmission. The algorithm measures the probability of receiving signals of nodes by degree centrality to quantify the signal missing values. After the signal transmission, the topology of the network is transformed into geometric relation-ships among the vectors. On the basis, the hierarchical clustering algorithm is used to find the community structure. In order to validate the proposed method, this paper compares it with SHC algorithm, CNM algorithm, GN algorithm and Similar algorithm. Under three real networks, the Zachary Club, American Football and Netscience, the experimental results indi-cate that SMHC algorithm can effectively improve precision.