Research On The Algorithms For Community Detecting In Complex Networks

The study of complex networks has become an important area of multidislinary research involving physics, mathematics, biology, social science, informatics and other theoretical and applied science. Many complex systems in the real world can be modeled as graphs including social networks, information networks and biological networks. For instance, the topology of social networks affects the spread of information and disease, and the topology of the power grid affects the robustness and stability of power transmission.These complex networks can be divided naturally into communities. The concept of community structure was first proposed by Newman in2002. A community could be roughly described as a collection of vertices in a subgraph that are densely connected among themselves while being sparsely connected to the vertices outside the subgraph. Since many networks demonstrate such a community structure, the description and detection of such a community structure have great practical importance.Bipartite networks are an important category of complex network. In fact, many real-world networks are naturally bipartite, such as scientists-paper cooperation network, computer terminals-data networks in P2P system, investors-company network, club member-activities network. Therefore, community detection in bipartite network is very important in the research on the theory and applications of complex network analysis. Another type of community is called "disassortative mixing" or "anti-community" has also been discussed to a lesser extent. In an anti-community, vertexes have most of their connections outside their group and has no or fewer connection with the members within the same group. In addition, community detection in a social network is a complex problem when interactions among members change over time. In such dynamic network, it is very important to detect the changes of the communities structures.The main results and contributions of our research in this paper are as follows:(1) We propose an algorithm for detecting community structure in bipartite networks based on ant colony optimization.In our algorithm, each ant constructs a solution by random walk, which represents a community. Combining the solutions obtained by all the ants, we can get a community partitioning scheme. Then according to the modularity to measure the quality of the solution, the pheromone information was uptated to direct the ants’movements in the further interations. The community partitioning scheme with the highest modularity is selected as the final result. 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 partitioning.(2) We investigate the problem of anti-community detedcting in complex networks. A simple label propagation algorithm is presented. The algorithm uses the network structure alone as its guide and requires neither optimization of a predefined objective function nor prior information about the communities for anti-community detection. In our algorithm every node is initialized with a unique label and at every step each node adopts the label that most of its neighbors currently have. In this iterative process densely connected groups of nodes form a consensus on a unique label to form communities. We validate the algorithm by applying it to networks whose community structures are known. We also demonstrate that the algorithm takes an almost linear time and hence it is computationally less expensive than that of the other similar methods.(3) We propose a relatively simple, scalable, and novel artificial life-based algorithm named an ant algorithm for detecting dynamic networks. We model the nodes in the network as a swarm of artificial life, where members randomly work in a virtual two-dimensional space to form communities. Our algorithm evaluates social interactions as they occur over time so as to guide the further randomly work. The user can see the detected communities at any given time. We demonstrate empirically that our algorithm can effectively detect the changes of the community structure in dynamic networks.