Chinese Journal of Computers   Full Text
Title	Information Bottleneck Based Community Detection in Network
Authors	SHEN Hua-Wei1),2) CHENG Xue-Qi1) CHEN Hai-Qiang1),2) LIU Yue1)
Address	1)(Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080) 2)(Graduate University of Chinese Academy of Sciences, Beijing 100049)
Year	2008
Issue	No.4(677—686)
Abstract &   Background	Abstract 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-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 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. keywords community detection; information bottleneck; modularity background Research on complex networks attracts considerable attentions from many scientific fields. The main focus is on three aspects: The statistical properties of complex networks, the model of the evolution of complex networks, the dynamics of complex networks. Community structure is a common and important property of complex networks. It forms an intermediate level between the microscopic and macroscopic description of networks. It provides the knowledge about the relation between the function and structure of complex networks. Thus, community detection plays a crucial role in the research on complex networks. Recent research on community detection devotes most efforts to unipartite undirected networks. Only few works concern the directed networks and multipartite networks. This paper aims to address the problem of community detection for bipartite networks. The method proposed in this paper is also applicable to unipartite networks through a projection used in this paper. The research is a part of "Research on Community Identification and Community Evolution on the Web 2.0", which is supported by MSRA IST 2007(FY07-RES-THEME-067). The latter aims to the sociality emerged in the Web 2.0. It is useful to help us understand the rules that govern the networks formed in rapidly emerging Web 2.0 applications. The identification of community structure is a fundamental task of this research. It is the basis of research on community evolution in Web 2.0. The authors’ recent studies mainly focus on the community detection of complex networks. The authors have made some in-depth research on the measure of community structure, the method to uncover the hierarchical and overlapping community structure in large networks, and its application on expert finding. In addition, a case study on the Douban (www.douban.com) is carried out by the research team. And the corresponding results are published in the 17th International World Wide Web Conference.