Research On Community Detection Based On Link Measure

In the20th century, graphs have already become extremely useful as the representation of a wide variety of systems in different areas. Biological, social, technological, and information networks can be studied as graphs, and graph analysis has become crucial to understand the features of these systems. More and more study work is being developed further from regular networks to random networks to complex networks, among which, the discovery of scale-free networks gives a fresh view to understand the complex networks. The degree distribute of vertices unevenly in it, meanwhile, it shows a high level of order and organization. The degree distribution is broad, with a tail that often follows a power law:many vertices with low degree coexist with some vertices with large degree. The feature is called community structure.Community detection plays an important part in the field of sociology, biology and computer science, such as improving quality of service of the World Wide Web, enhancing network sale, finding a group of scientists'interest in common, revealing the secret of government organization running, discovering social structure in animal world, clustering features gene and so forth.In recent years, a large number of new concept and methods has been given to study community detection. In terms of unweighted graphs, modularity makes the study go further and community detecting algorithms based on modularity optimization has been a mainstream. However, the existing modularity definition is inadequate to all situations and there are still some defects about some algorithms based on modularity optimization. In the study of weighted graphs, there are a few relative studies and the weight's significance be neglected. Lots of social networks are created on interaction activities. Meanwhile, the quantity of such activities is another influence to community structure. Based on these problems, this thesis concerns about the problem of link measure and gives a new research in aspects of modularity definition, improving algorithms based on modularity optimization, community detecting in weighed graphs so as to extend suitable range of the modularity, improve accuracy of community detection, and reveal reasonable community structure of weighted graphs.The main contributions and novelties of this thesis are summarized as follows:(1) Proposes a new modularity based on the concept of coupling coefficient. The existing modularity has shortages to compare the quality of the community structure of networks which are very different in size or have multiple communities. According to the characteristic of communities, which vertices are densely connected within the community and have much sparser connection between the communities, it defines values of the link density between communities and the link density within a community. By the ratio of two values, it defines coupling coefficient between communities. The lower the link density between communities is and the higher the link density within community is, the smaller coupling coefficient of community will be. A new modularity based on coupling coefficient is suggested to access the goodness of a network partition.. The experiment figure shows that the new modularity is suitable for both similar and very different communities in size, it also works in multiple community.(2) Propose a non-recursive and divisive algorithm of modularity optimization for community detecting. For the impact of recursive bisectioning, the divisive algorithm based on modularity optimization is inadequate for multiple communities. Based on k-means clustering idea, the writer suggests a modularity-based algorithm for community detecting. The main idea of our algorithm is setting a number as the number of communities in a network, dividing nodes according to their degree in the network to get initial communities, and optimizing communities by shifting nodes between communities so that modularity has the maximal increase; then changing the number of communities and repeat the process above until the modularity cannot be improved any more by the procedure or the number of communities is changed to k, which is the user-specified biggest number of community. For the initial partition to each number of community works on the original networks, our algorithm avoids the problem caused by recursive bisectioning. The experimental results show that our algorithm can correctly detect the communities.(3) Propose the concept of interaction degree on the interactive behavior between members of community, and applied to the hierarchical agglomerative algorithm for community detecting. In the social networks representing interactive relationships, it is intuitively realized that the measure of interactive relationships should consider two aspects, one is absolute quantity of interactive activities, and the other is reciprocity of interaction. Accordingly, we propose the concept of interaction degree between vertices and analyze the impact of topology structure of networks on the interaction degree. By introducing the reliability in the probability theory, we extend the interaction degree from between vertices to between communities. Then the interaction degree being as similarity measures, the writer proposes the hierarchical agglomerative algorithm for community detecting. The algorithm can naturally simulate the formation of community. Experiments show that it can detect the reasonable community structure in weighted graphs.(4) Develop a software tool for visualization of community detection, and propose a layered force-directed algorithm. Basing on JAVA, OpenGL graph programming interface, and force-directed method, we develop a visualization tool for showing dynamically graph structure and community detection consequence so as to make the graph be intuitive. In order to better display the results of community detecting, we propose a layered force-directed algorithm. In addition, it offers human-computer interaction mechanism in dynamic layout process, which makes artificial intervention possible and satisfies operators'observation convention as well.