A Study Of Community Detection Algorithms In Complex Networks

Nowadays, as the explosion of the internet, especially the surprisingly speed of growth of SNS, we are faced with networks with larger and larger scale, as a result, it becomes more and more difficult to make a research on those networks directly with the computational resources we have at the moment. In order to mine some useful information from complex networks with acceptable computation cost, we have to manage to simplify the network, therefore, it's necessary to detect the hidden community structure in the original network, through which we won't lose too much information and at the same time research becomes more feasible.In this article, firstly we generalize and take an analytics on the common community detection algorithms. Then we propose a hierarchical community detection algorithm based on the similarity between nodes, we choose the best initial threshold of the weight of edges to make the loosest community keep as tight as possible, and then we find out the local core tree structures based on the threshold, after that we implement two diffusion steps based on the connection between those left nodes with those local structures we have, then we find out communities for all nodes in the network. As in the algorithm we utilize the local measures, we can get the result in a relatively low computation cost, and the two diffusion steps make the algorithm perform well. Therefore we can get a quite good performance in a relatively low computation cost.Thirdly we extends this algorithm to the detect communities on dynamic networks, we firstly get the initial threshold of the weight of edges based on the change of the denseness of the network, and then implement the local core detection step and two diffusion steps as Chapter 3 shows, as we eliminate the step of deciding the initial threshold, we lower the computation cost in a large scale as the test shows, and the test also shows that we can get a similar result with a much lower computation cost.