Community Structure In Complex Network

This paper studies the community structure of the networks, especially those withlarge scales. The thesis is organized as follows.In the first chapter, we will introduce the basic concept of the network and itsdevelopment, also the background of the community structure.The main result of thisthesis and the method we consider are stated.In the second chapter, we will study the Laplacian matrix of the network. We findthat there is a significant gap between eigenvalues of the Laplacian matrix if the net-work possesses a obvious community structure. Also the first significant gap betweeneigenvalues can be used as a criterion to determine the number of the communities.Meanwhile, based on the research of the signless laplacian matrix, we depict the sharpupper bounds for the signless Laplacian spectral radius of graphs in terms of the cliquenumber.In the third and fourth chapter, we will discuss the two problems which occurin the process of partition:1, what is a reasonable criterion that separates the inner-and inter-communities;2, for a specific criterion, like modularity, the landscape ishighly degenerate, with a huge number of partitions having large values of modularity,close to the maximum, although they may be structurally very different from eachother. For the first problem, we propose a algorithm called WNDP, which apply theNodal Domain theory to get the partition. For the second problem, the study of themodularity shows that the diversity of the local network connection densities causesthis degenerate. Our criteria are mostly defined on the whole network, but this diversityof the connection density will lead to a result that omits the local detail information.We take into account the local information about the network to make improvement. Also, we build a new algorithm in which we define a new concept’mixing rate’ todescribe the position of a single node in a network. With additional information of thelocal structure, called’similarity’, we can depict the community structure of the wholenetwork.