基于广义后缀树的二分网络社区挖掘算法

Detecting Community from Bipartite Network Based on Generalized Suffix Tree

近年来,二分网络的社区挖掘问题得到了极大的关注。提出了一种基于广义后缀树的二分网络社区挖掘算法。首先从二分网络的邻接矩阵中提取网络中每个节点的链接节点序列,然后构建广义后缀树。广义后缀树的每个节点表示二分网络的一个完全二分团,由此获取并调整完全二分团。通过引入二分团的紧密度得到初始的社区划分,最后再对孤立点进行处理以得到最终的社区划分。所提算法不仅能发现重叠社区,而且能得到一对多关系的社区。在人工数据集和真实数据集上的实验表明,所提算法能准确地识别二分网络中的社区个数,获得很好的划分效果。

In recent years,the problem of detecting communities from bipartite network has drawn much attention of researchers.This paper presented an algorithm based on generalized suffix tree for detecting communities from bipartite networks.The algorithm firstly extracts the adjacent node sequence for each node from the adjacency matrix of the bipartite network,and constructs a generalized suffix tree.Each node in the generalized suffix tree represents a complete bipartite clique.Then the algorithm extracts and adjusts those cliques.The closeness of two cliques is introduced to form initial communities.Finally,isolated nodes are processed to get the final community partition.The proposed algorithm can detect overlapping communities,and is able to get one-to-many correspondence between communities.Experimental results on the artificial networks and real-world networks show that,our algorithm can not only accurately identify the number of communities from bipartite networks,but also obtain high quality of community partitioning.