Community Structure Detection Algorithm Research In Complex Networks

Community structure is a general and important topologies property in complexnetworks. A community structure is a densely connected subset of nodes that is onlysparsely linked to the rest of the networks. Reveal the complex network ofcommunity structure on network topology, understand its function, found hiddenpatterns and predict network behavior has important theoretical significance andwide application prospects.In recent years, a lot of community detection algorithms have been proposedaiming at different kinds of large scale complex networks. In this paper, we havesummarized some latest representative algorithms, focusing on the basic conceptsand the definition of community structure in complex networks. We have pointed outthe important progress in this research area. Based on the global information, earlyproposed algorithms detected the community structure of the whole network, whichis problematic for large-scale network. And there are many situations only payattention to the network structure of the local community in real life. So, need tofind new ways to divide the network structure.The main works of the dissertation are summarized as follows.Firstly, as the global information in large-scale networks is not easy to beaccessed, shortcomings of time complexity is higher of existing algorithm, and thelocal community division actually demand, a novel method which can detect localcommunity structure based on the link strength is proposed(LCD-LinkS). Thealgorithm used local information of the network, and take the local modularity as astandard to select nodes as a community greedy. This algorithm only requires localinformation of nodes and its time complexity in a reasonably short time. And theoutcome community has a higher modularity.Secondly, designed a measurement of the relationship between node andcommunity, which named Node Contribution. Then gave a new comparativedefinition for community. The contribution of the node consists of two parts. Thefirst is the number of the edges between them. And the second is the dense degree ofthe community. This definition is different from other comparative definitions. Ourcommunity definition is in line with the Scale-free network characteristics.Thirdly. As some algorithms based on the community attractive force have node ambiguity problem. Based on the measurement of Node Contribution, we proposed afast community detection method (FCD-NodeC). Employing the Node Contributionbased self-organize process; we can detect community structures of the wholenetwork. The time complexity of the algorithm isO (Lnd~2/2). And when d n ouralgorithm is much faster and the time complexity is near linear.Lastly, the effectiveness of the LCD-LinkS and FCD-NodeC is demonstrated byextensive experiments on lots of computer generated graphs and public availablereal-world graphs, such as College Football network, Zachary karate club and someother complex networks whose communities is unknown. The results showed thatalgorithms are fast and reasonable in detecting communities.