Research Of Community Detection Algorithm Based On Affinity Propagation And Its Paralleization

In real life, many system structures can be abstracted into network, such as Relations Network based on social applications, Metabolic Networks, E-mail Communication Networks, Mobile Phone Network, etc. These networks can show some structure characteristics according to the interaction of internal, the Community Structure, which is the most important feature of these networks. Detecting the community structure of the network is called the Community Detection. As the basic task of network analysis, Community Detection is helpful to the task computing of the other network, there are a lot of research about Community Detection in recent years and made many achievements.The continuous development of science and technology, making the scale of the network increasing, part of the existing community detection algorithms is unable competent to the community detection tasks of the large-scale network; besides, community detection problems can be converted into clustering problems. So this dissertation mainly from three aspects to study the community detection, including the similarity measure, clustering algorithm and distributed parallel computing. The main content of this dissertation is as follows:1. Existing algorithms measured the similarity of the vertices in the network, some of which have highly time complexity or not fully considered the topology structure of the network. Based on the above problems, this dissertation based on the random walk model, using Approximate Page Rank algorithm, combined with the characteristics of the existing community structure of the network, raises a fast algorithm of similarity measure, making the efficiency much higher when measure the similarity of vertices in the network under fully considering the topology of the network.2. During the detection process of the community results in the network, most of the existing clustering algorithms are unable to take advantage of the information of the network, making the community quality of detection is not high. Based on the above background, a Modified Affinity Propagation algorithm called Similarity Set based Affinity Propagation, which is suited to community detection of the network, is raised. SSAP is an improvement of the AP(Affinity Propagation), improving thespeed of the iteration. SSAP combined the APR algorithm makes the community detection problem into clustering.3. Many technologies of the distributed computing are becoming more and more mature, such as the Map Reduce parallel computing framework based on the Hadoop platform, Spark parallel computing framework based on the memory, etc. The emergence of these distributed computing technologies makes the computing task, which is not be completed in single environment, is possible. At the same time, the network scale in the community detection task is increasing; this dissertation makes the community detection algorithm parallelization under the Spark framework, using the advantage of the distributed parallel for the community detection of large-scale network is executable.