基于信息瓶颈的社区发现  

Information Bottleneck Based Community Detection in Network

作　　者：沈华伟[1] 程学旗[1] 陈海强[1] 刘悦[1] 

机构地区：[1]中国科学院计算技术研究所

出　　处：《计算机学报》2008年第4期677-686,共10页Chinese Journal of Computers

基　　金：国家“九七三”重点基础研究发展规划项目基金(2004CB318109,2007CB311100);微软亚洲研究院IST2007-Web20社区发现与社区演化研究课题(FY07-RES-THEME-067)资助~~

摘　　要：该文提出一种映射方法,把单部网络变换成二部图网络.针对得到的二部图网络,在信息论的框架下,提出了一种基于信息瓶颈的社区发现方法.该方法通过寻找网络的最优压缩表示来发现网络的社区结构,最优压缩表示尽可能多地保留原始网络的拓扑特征.在真实数据集和计算机产生的数据集上的实验表明,该方法能够有效地发现网络的社区结构.另外,对于有向网络的社区发现,现有方法忽略有向网络中边的方向而作为无向网络来处理,损失了有向的网络的方向信息,文中提出的社区发现方法能够很好地解决这一问题,并能从有向网络中挖掘出一些现有方法无法发现的知识,这一特点使得该文的方法比现有方法更适用于解决像WWW这样的有向网络.同时,真实世界的许多网络本身就是二部图网络,相对于现有的社区发现方法,文中的方法可以直接应用于这类网络.This paper proposes a projection method to transform a unipartite network into a bipartite network. As to the obtained bipartite network, it presents an information-bottleneckbased method for community detection under the information-theoretic framework. This method detects the community structure of networks by finding an efficient compression of the network. The efficient compression holds the regularity of the original network as many as possible. Applications on the computer-generated networks and many real-world networks demonstrate that this method is very effective at community detection of networks. As for the community detection of directed networks, existing methods neglect the direction of edges and treat them as undirected networks. The information provided by directionality is lost in this process. Using the projection method proposed in this paper, the direction of edges can be retained and thus the method is more suitable to detect the community structure in directed networks, such as the world-wide-web. And some new knowledge can be found by the method. In addition, the method can be directly applied to the detection of community structure in bipartite networks, which are common in real world.

关 键 词：社区发现 信息瓶颈 聚团性 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]