针对有向图的局部扩展的重叠社区发现算法

Overlapping Community Detection from Local Extension in Directed Graphs

当前社区发现算法主要是针对无向图研究社区结构,但在实际复杂网络中,链接关系时常表现出非对称性或方向性,比如Twitter的用户关注关系,文献网络的引用关系,网页之间的超链接关系等应用网络。因此,本文依据信息在复杂网络中的传播规律和流动方向性,提出了k-Path共社区邻近相似性概念及计算方法,用于衡量结点在同一社区的相似性程度,并给出了把有向图转换为带方向权值的无向图的方法。基于带权无向图提出了一种从局部扩展来探测社区的重叠社区发现算法(Local and wave-like extension algorithm of detecting overlapping community,LWS-OCD)。在真实数据集上的实验表明,共社区邻近相似性概念实现了有向到无向的合理转换,而且提高了社区结点的聚集效果,LWSOCD算法能够有效地发现带权无向图中的重叠社区。

Most of the previous research on community detection are mainly based on the undirected graph structures. However, in actual complex networks, the links relation usually shows the asymmetric char- acteristic or directionality, such as citation network of scientific papers, the one-way follow relationship on Twitter, and hyperlinks between web pages. Therefore, based on the propagation of information and the direction of information transmission, a k-Path conception and calculation method for measuring the similarity of co-community neighboring is presented to weigh possibility of nodes in the same community. Furthermore, the method of transferring directed graphs into undirected graphs with similarity of weight is presented. Then the local extension algorithm of detecting overlapping community based on weighted undirected graphs is proposed. Several experiments on the real data sets are conducted and analyzed. Ex- perimental results demonstrate that the k-Path conception can achieve the reasonable conversion for di- rected graph and improve the effectiveness of the community gathering nodes. Finally, the results show that the algorithm can detect the overlapping community effectively.