Font Size: a A A

A Study Of Ant Colony Optimization For Community Detection In Complex Networks

Posted on:2015-04-07Degree:MasterType:Thesis
Country:ChinaCandidate:J ZhangFull Text:PDF
GTID:2308330464967951Subject:Circuits and Systems
Abstract/Summary:PDF Full Text Request
In the 21 th century, complex networks can be found everywhere. They are used in many areas as a way to represent the patterns of connections between different components of complex system. Examples include relationship network in social system, protein network in ecosystem, World Wide Web and internet in science and technology system. Besides the two properties of small-world and scale-free in complex network, another important property is community structure. Therefore, it is of great significance and has broad application prospect to detect the topological structure and discovery the hiding law of networks. In recent years, there are many algorithms have been proposed to solve community detection problems in complex networks. In this thesis, we propose two algorithms based on ant colony optimization algorithm for solving community detection problem in complex networks. The main works are as follows:1. We have studied on the basic theory and mathematical model of ant colony algorithm. Then the ant colony optimization algorithm was applied to the community detection problem. However, there are some deficiencies in the original ant colony optimization algorithm, like the search is quite easy to trap in local optimum and the waste of computing resources. To overcome these deficiencies, we let a part of the ant colony to be intelligent. These intelligent ants can learn from those ants that found the optimal solutions and they can improve the quality of their own solutions further. With the cooperation between the original ants and intelligent ants, the ant colony can find the global optimal solution efficiently and accurately by optimizing the modularity.2. We consider the resolution limitation problem in the modularity-based single objective optimization, and propose a multi-objective ant colony optimization algorithm based on decomposition called MOACO/D-Net for community detection. In the MOACO/D-Net, we model the community detection problem as a multi-objective optimization problem which optimizes the ratio association and ratio cut of the network simultaneously. During this procedure, the ant colony is divided into several groups and the ants in each group share the same pheromone matrix. Each ant in the ant colony is responsible for a subproblem, and constructs solutions by a pseudo probability selection model. Finally, we can receive a Pareto front consists of nondominated solutions in a single run, and each of the nondorminated solutions corresponds to a partition with a different resolution of thenetwork.We also test on the important parameters in the ant colony optimization algorithm. The parameters include the pheromone factor α, the heuristic factor β, the pheromone persistence rate ρ and the population size m. By comparing the solutions obtained by algorithms with different parameters, we find out the optimal value range of each parameters.This work was supported by the National Natural Science Foundation of China(No. 61003199) and the Fundamental Research Funds for the Central Universities(Nos. JB140216 and K5051202019).
Keywords/Search Tags:Complex Network, Community Detection, Ant Colony Optimization, Multi-objective Optimization
PDF Full Text Request
Related items