基于信息瓶颈的社区发现F.doc

基于信息瓶颈的社区发现F 沈华伟1),2) 程学旗1) 陈海强1),2) 刘悦1) 1)（中国科学院计算技术研究所 北京 100080) 2)（中国科学院研究生院 北京 100049） 摘 要 本文提出一种映射方法，把单部网络变换成二部图网络。针对得到的二部图网络，在信息论的框架下，提出了一种基于信息瓶颈的社区发现方法。该方法通过寻找网络的最优压缩表示来发现网络的社区结构，最优压缩表示尽可能多地保留原始网络的拓扑特征。在真实数据集和计算机产生的数据集上的实验表明，该方法能够有效地发现网络的社区结构。另外，对于有向网络的社区发现，现有方法忽略有向网络中边的方向而作为无向网络来处理，损失了有向的网络的方向信息，本文提出的社区发现方法能够很好地解决这一问题，并能从有向网络中挖掘出一些现有方法无法发现的知识，这一特点使得本文的方法比现有方法更适用于解决像WWW这样的有向网络。同时，真实世界的许多网络本身就是二部图网络，相对于现有的社区发现方法，本文的方法可以直接应用于这类网络。 关键词 社区发现；信息瓶颈；聚团性 中图法分类号 Information Bottleneck based Community Detection in Network SHEN Hua-Wei1),2) CHENG Xue-Qi1) CHEN Hai-Qiang1),2) LIU Yue1) 1)（Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080） 2)（Graduate University of Chinese Academy of Sciences, Beijing 100049） Abstract This paper proposes a projection method to transform a unipartite network into a bipartite network. As to the obtained bipartite network, we present an information-bottleneck-based 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 our 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 our method. In addition, our method can be directly applied to the detection of community structure in bipartite networks, which are common in real world. Keywords co