Research On Multi-agent Evolutionary Clustering Algorithms For Complex Networks

Cluster structure is one of the important attributes in the field of complexnetwork, which reflects the topological structure of relative intensity inside cluster,while, in the mean time, relative scattering among clusters. Using cluster analysistechnology to detect cluster in the networks, is an important method to understand thenetwork characteristics and network behavior, which have a great significance toreveal the hidden knowledge in complex networks. In recent years, a lot of clusteringalgorithms of complex network have been proposed and applied successfully to somespecific complex networks. However, with the increase of network scale, how toquickly detect the cluster structure without prior knowledge is still a highlychallenging issue.Multi-agent evolutionary mechanism evolved from the genetic algorithm, bysimulating the natural evolutionary process, gradually approaching the optimalsolution of the problem. Multi-agent evolutionary clustering algorithm whichintegrated with the local perception and reaction ability of agent and the search abilityof traditional evolutionary algorithm, has fast convergence, high accuracy androbustness charachterstics in solving complex network clustering problem. In thispaper, we present a new approach using multi-agent evolution for discoveringcommunities in social networks and detecting functional modules in PPI networks.My main work includes the following two parts:(1) We propose a multi-agent evolutionary method for discoving communities insocial network. The focus of the method lies in the evolutionary method process ofcomputational agent in a lattice enviroment, where each agent corresponds to acandidate solution to the community detection problem. First, the method utilizes aconnection-based encoding scheme to transform the clustering problem into agentencording information. The agent in the enviroment employs a random-walk behaviorto construct a solution. Next, we design three evolutionary operators, i.e. competition,crossover, and self-adaptive mutation operator, to realize information exchangeamong agents as well as solution evolution. The performance of our method has beentested using real-world networks and synthetic networks, the result of which hassuccessfully shown its capability in effectively detecting community structures.(2) On the basis of the previous work, we made some improvements onmulti-agent evolution mechanism for the detection problem of functional modules in aPPI network. First, for the problem that PPI network’s sparsity and has high nose, wepropose a new heuristic function which combines topological structure of networksand GO annotation information. The new heuristic function improves the accuracy ofsimilarity measure. Moreover, some operators have been redesigned to enhance the search capabilities of the algorithm. Finally, after evolutionary process, to improve themining quality, we adopt two post-processing strategies. Systematic experiments havebeen conduceted on three benchmark testing sets of yeast networks. By comparisonwith several other existing algorithms, experimental results show that the approachhas obvious advantage of precsion, recall and other metrics for the dectection problemof functional modules.