Research On Community Detection In Bipartite Networks

Both of the physical systems in nature and the engineered artifacts in human society, such as biology, economy, sociology, and other fields, could be modeled as complex networks. An important feature of the real world networks is typically the community structure:the nodes of networks can often be divided into distinct groups named community, such that nodes within the same group are similar to each other in some sense, whereas nodes from different groups are dissimilar. Communities are relatively independent in the structure, and it is believed that each of them may correspond to a fundamental functional unit. For example, a community in genetic networks often contains genes with similar functions and a community on the World Wide Web may correspond to web pages related to similar topics. Since many networks have such a community structure, community structure detection has great practical importance. Because communities are relatively independent of one another structurally, it helps to uncover unknown functional modules. Identifying and analyzing such communities from a large network provides a means for functional dissection of the network and sheds light on its organizational principles.Opposed to the general unipartite networks, bipartite network not only is universality, but also is an important category of complex networks which has become an important research topic in complex networks analysis. Many real-world networks are naturally bipartite, such as scientists-paper cooperation network, the actors-films network, investors-company network, disease-gene network, club member-activities network, audience-songs network and so on. Therefore, community detection in bipartite networks is very important in theoretical research and has practical value for the study of complex networks, such as academic detection, functional analysis, recommendation system, disease diagnosis, link prediction and other aspects.Recently, a wide range of successful algorithms for community detection in bipartite networks and bipartite modularity have been proposed. In uniparite networks, Newman introduces a qualitative measurement called modularity to evaluate the quality of a particular community division. Guimera devised a bipartite modularity which aims at nodes of one type at a time. Barber presented a bipartite modularity and proposed an algorithm called adaptive BRIM for detecting community structure by maximizing this bipartite modularity. T. Murata proposed a bipartite modularity, which gives consistent result as Newman’s modularity. Based on this modularity. X. Liu and T. Murata improved the label propagation algorithm (LPA) and propose a new algorithm to make it more suitable for bipartite networks. Their algorithm is readily parallelized for real time community analysis of large-scale bipartite networks. X Liu and T. Murata also proposed an algorithm called LP&BRIM for community detection in large-scale bipartite networks. The algorithm is based on label propagation, and employs BRIM algorithm for generating better community structure.Aimed at community detection in bipartite networks, the main contributions and results of our research are as follows:(1) We proposed an algorithm based on ant colony optimization for detecting community structures in bipartite networks. The algorithm first transforms the problem of community detection into the one of combination optimization, and establishes a model graph for the ants’ searching. Meanwhile we define heuristic information according to the topological information of the vertexes. Each ant chooses its path according to the pheromone and heuristic information on each edge to construct a solution. The quality of solution obtained by each ant is measured by its bipartite modularity. Experimental results show that our algorithm can not only accurately identify the number of communities of a network, but also obtain higher quality of community detection.(2) We proposed an algorithm for multi-facet community detection from bipartite networks. As we all know the acknowledgement that each individual in the society has more than just one aspect, so multi-facet community which is composed of one type of nodes and each of them are not connected in bipartite networks should be paid attention to. The algorithm is based on many-to-many correspondence between communities in different parts. We propose an algorithm based on ant colony optimization for multi-facet community detection in bipartite networks. Experimental results demonstrate that our algorithm can extract multi-facet communities from bipartite networks and obtain high quality of partitioning communities.(3) We proposed a quantitative measurement named density based bipartite modularity for evaluating the community partitioning in bipartite networks. Bipartite modularity is developed according to different understandings of community in bipartite networks. However, those modularity measurements suffer resolution limits which could reduce the quality of community partitioning. Those modularity measurements contain an intrinsic scale which depends on the total size of links and ignores the number of nodes in the bipartite network. We first illustrate such resolution limit of the traditional bipartite modularity using several examples of bipartite networks. Then we verify that optimization of the density based modularity proposed has no drawback of resolution limit. By optimizing such density based modularity, we can partition the network into correct communities. Experiments on synthetic and real world bipartite networks validate the accuracy and reliability of our bipartite density based modularity.