Font Size: a A A

Research And Implementation Of Partition Algorithm For Complex Network Community

Posted on:2011-07-09Degree:MasterType:Thesis
Country:ChinaCandidate:Y YangFull Text:PDF
GTID:2120330332488373Subject:Computer software and theory
Abstract/Summary:PDF Full Text Request
It was found that networks have a feature called community structure. Partitioning those networks into rational communities correctly and efficiently is the premise of understanding and taking advantage of these networks effectively. Finding an exact solution to network community partitioning is a NP problem and there is no precise and effective solution when it comes to large network scale.Two community partitioning algorithms were proposed in this paper:The first algorithm is a complex network community partitioning algorithm based on the genetic law. In this algorithm, the genetic algorithm was applied to the implementation process of a complex network community partitioning and an isolated point repair strategy which can enhance the convergence rate was introduced. It's proved through the experiments that this algorithm is capable of searching an acceptable partitioning scheme for a complex network from a mass of partitioning schemes. The second algorithm is based on the law of gravitation and a concept of flexible algorithm was put forward. A complex network adjacency was quickly mapped to the two-dimensional space by the flexible algorithm, after that, nodes with higher association formed a relatively dense cluster, and then the community structure could quickly be identified combined with gravitational clustering method. Experiments proved that this algorithm performs well in partitioning rate and accuracy with less priori information.Furthermore, this paper presented a method of validating partitioning algorithms to assist the research. Two methods which can use real data to build a complex network were given and a random network generation algorithm was provided. We also built a scalable network community partitioning algorithm test platform and a comparison between three kinds of algorithms was achieved.
Keywords/Search Tags:Complex Network, Association Partitioning, Genetic Algorithm, Gravitational Clustering, Flexible Algorithm
PDF Full Text Request
Related items