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

Detecting Community from Bipartite Network Based on Generalized Suffix Tree

作　　者：邹凌君[1] 陈崚[2,3] 戴彩艳[4] 

机构地区：[1]金陵科技学院信息化建设与管理中心,南京211169 [2]扬州大学信息工程学院,扬州225009 [3]南京大学计算机软件新技术国家重点实验室,南京210093 [4]南京航空航天大学计算机科学与技术学院,南京210016

出　　处：《计算机科学》2017年第7期221-226,共6页Computer Science

基　　金：国家自然科学基金项目(61379066);江苏省高校自然科学基金项目(15KJD520008);江苏省现代教育技术研究重点课题(2017-R-54927)资助

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

关 键 词：二分网络 社区划分 广义后缀树 重叠社区 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]