Research On Community Detection Algorithm In Dynamic Social Networks

Social networks are widespread in many areas of the real world such as friendshipnetworks, scientists’ co-author relationship networks, and information networks and so on.Along with the rapid development of technology, Facebook, Twitter, blog community andother new forms of social networks have appeared in recent years. Nowadays, social networkanalysis has become an important mission and hot issue in data mining.As an important property of social networks, community structure and relative researchhave attracted considerable concern of more and more experts and scholars from a lot ofdifferent areas such as sociology, bioinformatics and computer science. By now, there existmany community detection methods represented by GN, K-L and Rachicci. Some of themeven have been applied in actual practice. However, most present algorithms are staticmethods, meaning that they only analysis a single static network graph, while the dynamicnature, networks may change over time, is rarely considered. In fact, dynamic social networkanalysis has just started since2003. So it has wide research space and applications.Before this paper, the author read a lot of articles about social network analysis,clustering, classification and other data mining technology and learned the graph theory,theory of probability and mathematical statistics and other related knowledge. Based on theabove work, we do a lot of research work about detecting communities in dynamic socialnetwork and its evolution analysis.This paper first introduced the research status of social network analysis and summarizedthe advantages and shortcomings of existing community detection methods. Based on relativeresults and in order to put forward the corresponding solutions to solve problems in thesealgorithms, this paper deeply researched the task of community structure detection in dynamicsocial networks, and gave some effective solutions.The main job of this paper contains following two aspects:(1) It is found after observing many real world networks and reading relative papers that,there are often some core nodes in a social network. Each core and its followers together forma community. Based on this fact, this paper proposed the MKBCD community detectionmethod, which is based on the thought of k-means. A modified method for selecting initialcommunity cores is presented to mine initial core set whether the number of communities isknown or not. This method also contains a two-stage strategy to determine communityownership of non-core nodes. In the iteration process, the division is continuously optimizedand wrong communities are deleted. Experiments on several classic real world networks and computer-generated data sets as well as comparison with other methods proved the superiorityon finding high quality communities. Based on achievement of the above, this paper also putsforward a MKBCD based backbone node mining algorithm on dynamic networks, which isused for mining backbone nodes in communities. These nodes can be used to infer thestructure of network in the next moment.(2) Aimed at dynamic social networks which have relatively stable community structures,this paper proposed an increment-analyzing based community detection method namedCDBIA. This method focuses on those increments which may change the communityownership of some nodes, and uses existing division and current topology structure to minedivision of current network with reducing the complexity. Experiments on dynamic Zacharynetwork and virtual networks show that, the proposed method is able to find the realcommunity structures in dynamic social networks.