基于符号网络的两阶段融合社区发现算法

Two-stage Fusion Community Detection Algorithm Based on Signed Social Networks

目前针对符号网络社区发现研究越来越受到重视,CRA(Clustering Re-clustering Algorithm)算法代表比较流行的一种思路,即将社区划分过程分为两个阶段:第一步先删除负边,对剩余网络用传统社区发现算法进行社区划分;第二步再用符号网络特定社区质量评价函数调整分区.此类算法由于没有充分考虑负边信息而导致了划分不正确的问题.本文通过引入网络正密度,提出一种两阶段融合算法TFCRA(Two-stage Fusion Clustering Re-clustering Algorithm),在社区划分过程中,不再删除负边,通过网络正密度和社区正密度的比较调整带负边的顶点的归属.实验证明,TFCRA能解决CRA算法存在的对某些网络无法划分和从不同顶点出发可能导致划分出错的问题.

The current study on signed social networks community detection is attracting more and more attention. CRA （ Clustering Re-clustering Algorithm） algorithm is more popular thinking, the community detection process is divided into two stages： The first stage deletes negative edges, divides the remaining network with traditional community detection algorithm. The second stage adjusts the communities by evaluation function of signed social networks. Because the negative edge information is not fully taken into account,this idea may not correctly divide the network. This paper proposes a two-stage fusion algorithm TFCRA （ Two-stage Fusion Clustering Re-clustering Algorithm） by introducing the network positive density. In the process of community division, no longer remove negative edges, the assignment of vertices with negative edges shall be determined by comparing the value of network positive density with community positive density. The experiments show that TFCRA algorithm solves the problems existing in CRA,including network division failure and wrong detection starting from different vertices.