Research On The Algorithm For Detecting Overlapping Communities In Complex Network

With the capacity of computer increasing in storage and computing,more and more networks with different structure were generated.The study of the network has also entered into current flourishing prosperity where number of network models and algorithms are proposed and applied from the early stage of simple graph theory. Community structure,as a kind of medio-structure of network,which can also be regarded as compression of network in some degree,is of great significance to understand structure and function of the network. However Nearly all of the traditional community detection algorithms can only be used to detect non-overlapping community,research about detecting overlapping community still stay in an early stage. there are many overlapping communities in real world,for example,one person can join in different hobby group,a paper can belongs to many fields, a word can own different part of speech etc. Knowledge of overlapping community structure can be useful to reveal functional organization in networks and to know more about feature of networks. To detect overlapping communities more effectively,this paper makes a systematic and in-depth study and forms the following research findings:(1)To the instability of those algorithms based on local expansion, the paper proposed a new method called DOCNR.The proposed algorithm firstly make improvement on the uniform distribution strategy of PageRank to form a new method NodeRank which is more useful to undirected network. We use NodeRank to calculate the importance of nodes in network, then we propose a new fitness function based on feature that the whole importance value of all nodes in network is conservation. Using the fitness function,the algorithm selects starting nodes according importance of nodes to expand to form community as same as Breadth First search. Different starting nodes will lead to different communities which usually have intersection,So the algorithm can detect overlapping communities successfully. Finally,the algorithm merge those communities who have high degree of overlapping so as to attain high-quality communities.(2)Aiming at defects of LFM that wastes much time,generates homeless nodes as well as steps into local endless loop easily, we propose a quick algorithm based on greedy strategy called QLFM and an algorithm that is expanding-firstly and cutting-lastly based on local optimization of a fitness function called ECFM. QLFM firstly select a node as seed randomly.With a local fitness function,the algorithm then will expand from inside to outside of the seed to form community according to the greedy strategy. Being the same with QLFM, The ECLFM also firstly selects a node as seed randomly.With a local fitness function,the algorithm then will expand from inside to outside of the seed according to the Breadth-First-Search in graph, When expanding-step stops, the cutting method will start to check and remove those nodes which can't satisfy the fitness function.As different seeds will expand to different communities independently,and these communities have same nodes,thus our method can detect overlapping nodes quickly and efficiently.(3)Comparing our method with current famous algorithms LFM?CPM and COPRA on real and synthetic datasets,we can find:1).DOCNR has high stability and can find high quality overlapping communities.2).Both QLFM and ECLFM give better result not only in time efficiency,but also in quality of detected overlapping community.