Research On Community Detection Algorithm For Social Information Networks

Social information networks are widespread in many areas in the real world suchas microblog network, email network, scientific cooperation network and so on. Inreality, these networks are usually organized in communities which appear as sets ofvertices with a high density of internal links, whereas links between those communitieshave a comparatively lower density. As one of the remarkable characteristics existing incomplex networks, on one hand, community structure reflects the locality of therelationship between individuals of the target networks. On the other hand, communitystructure affects or even determines the behavior of the dynamical processes takingplace on networks. Therefore, community structure is crucial to shedding light onorganizations and functions of complex information networks and has significanttheoretical and practical implications.In order to answer the fundamental questions “how to quantify the communitystructure” and “how to detect community structure in social information networks”, thisdissertation has investigated many efficient algorithms for community detection in bothstatic social information networks and dynamic ones. The main contributions are asfollows:(1) Based on the analysis of the k-means thought and other relative approaches, ak-representatives community detection method called KRRW is proposed to dividenetwork vertices into communities. It adopts a simple random model to decrease thestrong dependence on the selection of initial center vertices. In addition, a modifiedmeasure Discriminant Community Density (DCD) is applied to evaluate theperformance of the novel method. DCD takes both density of within-community andthat of between-community into account. Experimental results on several classic realworld networks confirm that the proposed algorithm outperforms the contradistinctivealgorithms at most cases according to the metrics such as modularity Q, accuracy rateAR and DCD.(2) As for dynamic social information networks, this dissertation investigatesand analyzes problems that how to mine the core vertices accurately and how to define and quantify the increments. On the basis of such investigation, a novel incrementalcommunity detection algorithm for dynamic social information networks entitledICDMC is proposed. It takes both the historical community information and the currentchanges into consideration, and just updates the affiliations of vertices whoseconnections change over time. Contrast experiments on Zachary s dynamic network andnetworks extracted from DBLP show that the novel approach is able to gain largermodularity Q, accuracy rate AR and a lower time cost, which demonstrates that thenovel method outperforms both of the comparative algorithms on the comprehensiveanalysis of efficiency and effectiveness.