Community Structures Detection In Complex Networks Via Objective Function Optimization

Withthedevelopmentofinformationtechnologyandtheproducingandeverydaylifepractices, modern society has entered a typical big-data era. The major challenge in thebig-data time is that we are facing increasingly big and complex systems in nature,societyandtechnologyfields. Withrapiddevelopingofdatageneratingandgatheringtechnology,the research in complex systems gradually swift from theoretical aspects to data drivingapproaches.Inthegeneralsystemtheory,complexnetworkisasimplifiedmodelforcomplexsys-tem which modeling the system as a set of its components and relations betweens them.This effective abstraction enables us to to study the complex systems by mathematics.The microscopic scale properties of complex networks are highly local clustering coeffi-cients, rich club phenomenon. While in the macroscopic scale complex network possesssmall-world and scale-free properties. Between the above two extreme scales there isa mesoscopic scale that complex networks show some significant properties, includingstructure and dynamic features. Community structure is one of the key structural proper-ties of complex networks at the mesoscopic scale.Modularity is one typical objective function for community detection which mea-sures the link density within vertexes groups. In this the thesis we study communitydetection problem, with focus on the community detection framework based on objectivefunction optimizing in the following four different ways:First,we propose a community optimizing algorithm based on least-angle merging.By treating the network as directed graph, we reformulate the modularity matrix as cross-covariance of vertex vectors taking directed edges as their basis. One main issue of themodularity matrix is that it has eigenvalues. The existing method treated community de-tection as a vector partition problem by spectral decomposition of modularity matrix, us-ing only a few leading positive eigenvalues and the corresponding vectors. The diagonalof the cross-covariance matrix is modified to make it positive defined and then factoredinto inner product of vertex vectors. Thus the above modification improves the trans-formation of the community detection problem as a vector partition problem. From thevector partition point of view, the resolution limit of modularity is reinterpreted.A greedyalgorithm based on merging vectors with least angle is designed.The proposed method is less resolution limited than modularity optimizing methods.Second,we improve the local similarity based community detection method. Sincethe existing similarities tend to underestimate the existing links, we propose new simi-larities for community detecting based on star-neighborhood and α-neighborhood to overthesedefects. Wethendesigncorrespondinghierarchicalclusteringalgorithmscoordinatewith these new metrics, greatly promoting community detection results. The similaritymatrices are stored by max-heap data structure and the algorithms run quite fast.Third,weproposerestrictedrandomnesssearchingalgorithmformodularityoptimiz-ing. It is known that pure greedy modularity optimizing tend to get trapped in one singlelocal maximal and there are many of them due to the fact that modularity is extremely de-generate. The random search algorithm based on the head-heap data structure proposedhere is designed to jump out of the local maximal and efficiently extract diverse commu-nity structures in multiple runs.Last but not least, we consider community detection methods based on clique analy-siswhichtakingcliquesasbasicbuildingblocks. ofbothdisjointandoverlappingcommu-nities. By building vertex-clique bipartite graph and evaluating weights between vertexesand cliques,we extract feature vectors for vertexes from the adjacency matrix. Spectralclustering method is carried out on the matrix of correlation coefficients of the featurevectors for disjoint community structure detection. Clique graph is built from the max-imal cliques cover of the network with edge weighted by the degree of clique overlap.This graph is further splitted by weighted modularity, forming overlapping communitystructure of the original network.