Community Detection And Analytical Application In Complex Networkss

In the past few decades, as the fast development of the information technology especially the Internet, the human society has entered the network era. The network science combines the graph theory and some complex systems, it is one subject which studies the vertices and the relationships between vertices. Coupled biological and chemical systems, neural networks, social interacting species, the Internet and the World Wide Web, are only a few examples of systems composed by a large number of highly interconnected dynamical units. The first approach to capture the global properties of such systems is to model them as graphs whose nodes represent the dynamical units, and whose links stand for the interactions between them. As a result, the network science can be used in many kinds of complex systems in the nature and the society. The network science provides new viewpoint and new methods to people and it can be used in complexities. Besides, the complex network becomes the physical form of the network science and it attracts the attention of many scientists.The modern science of networks has brought significant advances to our understanding of complex systems. One of the most relevant features of graphs representing real systems is community structure, or clustering, i.e. the organization of vertices in clusters, with many edges joining vertices of the same cluster and comparatively few edges joining vertices of different clus-ters. Such clusters, or communities, can be considered as fairly independent compartments of a graph, playing a similar role like, e.g., the tissues or the organs in the human body. Detecting communities is of great importance in sociology, biology and computer science, disciplines where systems are often represented as graphs. Through appropriately decomposing a network into a series of functional clusters, its structure would be better understood and the relationships between its different components will be clear. Moreover, possible functions for members of a cluster can be suggested by comparing the functions of other members. Therefore, the techniques of community detection method are very important in complex networks. The network is one very complex system, the community structure is one fast way which could help us learn the structure of networks easily. The vertex i is one unit of the subnetwork V of network G, and the degree of i can be denoted by ki(V)=kiin(V)+kiout(V), kiin(V) is the number of edges that the vertex i connects with the other vertices within V, kiout(V) is the number of edges that the vertex i connects with the other vertices out of V. Then we get two kinds of definitions about community:(1)Strong community structure. For i∈V, if kiin(V)> kiout(V),(?)i∈V, then the subnetwork V is one strong community.(2)Weak community structure. If∑kiin(V)>∑kiout(V), then the subnet-work V is one weak community.The methods of community detection can be divided into global and local methods. The global methods contain spectral method, modularity and the density of subnetwork. The local method mainly takes use of the local clustering. The existing methods are mainly based on the statistical physics and heuristic algorithms. we uncover one new method from the point of graph theory. The bipartite graph is one special graph model. Let G(V, E) be an undirected graph, if the vertices in V can be divided into two non-overlapping subsets U, K and for (?)eij∈E, there is (i∈U,j∈V), then G(V, E) is a bipartite graph. We construct the bipartite network G(V, V, E) in accordance with the network G(V, E). The solution of the maximum flow problem in the bipartite network can be regarded as the community structure. This is one community detection method which is based on the revised maximum flow problem.The equitable coloring of graph is a special vertex coloring. A graph G(V, E) is said to be equitably k-colorable, if the vertex set V can be par-titioned into k independent subsets V1, V2,…,Vk such that||Vi|-|Vj||≤1(1≤i,j≤k).Based on this, we give a definition on the equitable commu-nity structure. Two kinds of equitable community structures are taken into consideration. One is the all-equitable community structure, the difference value of the nodes number in different communities is less than1. Another is the density-uniform community structure, the partition densities of differ-ent communities are the same. The partition density is defined by the ratio between the edge number and the vertex number. We show the meaning and application value of these two kinds of communities.Identifying influential nodes that lead to faster and wider spreading in complex networks is of theoretical and practical significance. This is equiv-alent to sort the influence of vertices in network. Many methods have been proposed to identify the community structure of complex networks. These methods can be roughly classified into two categories in terms of their re-sults, i.e., to form a partition or a cover of the network. In real networks, communities are usually overlapping and hierarchical. Overlapping means that some vertices may belong to more than one community. When we in-vestigate the influences of vertices, the vertices in the overlapping region are very important. The larger the infected area of one disease in the same time, the greater the influence of the vertex. Besides, the influence of the vertices with high degree, large betweenness and the large clustering coefficient are taken into consideration. A series of contrasts between the overlapping ver-tices and the other types of vertices about their influence in the spreading process show that the overlapping vertices are more influential. As a result, the overlapping vertices should be isolated preferentially in the procedure of epidemic spreading, or we should strengthen their influence in the process of goodbehavior spreading.Network evolution model can help to learn the topological structure of complex networks. The random network, small-world network and scale-free network are constructed in accordance with some network properties. We construct a gravitation networks model according to the law of gravity. The law of universal gravitation states that any two bodies in the universe attract each other with a force that is directly proportional to the product of their masses and inversely proportional to the square of the distance between them. We think this law is also suitable for the evolution of network. The degree of vertex can be regarded as the mass, and the shortest path length between vertices can be seen as the distance. Based on this, we propose the gravitation network model. The generated network by this model posses more properties of real networks, such as the small-world, scale-free and community structure. We also detect the structures of different communities are different. There are two kinds of communities. The first is the leader community within which there are one or several nodes with higher degrees and the other nodes with lower degrees; the second is the self-organizing community within which all the nodes have similar degrees. We can also detect these two kinds of communities in the gravitation network model.We mainly discuss the methods of community detection and some prob- lems which are related to the community structure. We have constructed our works in five chapters.In Chapter1, we give brief introductions about the history and con-cepts of complex network. Then we present the community structure and its measurement. At last, we outline the main results.In Chapter2, we state the community detection method which is based on the revised maximum flow problem. The precise algorithm of community detection and its complexity are explained in detail. The application of this methods in some real networks are shown. Then we mainly discuss the equitable community structure. First we present algorithms of the two kinds of community structures. At last, one specific application example is introduced.In chapter3, we reveal the high influence of overlapping nodes. We give an introduction about the importance of vertices. Then we have a contrast between different kinds of vertices about their influence in networks and verify that the overlapping vertices are more influential.In Chapter4, we discuss the internal community structure and construc-t the gravitation network model. Firstly we introduce the existing network model. Then we present the method which distinguishes the different com-munity structure and the specific procedure of the model. At last, we analyze the characteristics of the model network.In Chapter5, we give a conclusion and the problems that need to be solved about community structure in furture.