Research On Overlapping Community Detection Algorithms Based On Local Information

Many real world systems can be represented as complex networks. CommunityStructure has been found as an important property of these real-world complex networks.Detection of community structure can help us know the inner structure and characteristicsof networks, find the regular exist in the networks and then forecast the action andfunction. With the result than, more and more person pay close attention to the communitydetection of complex networks. Recent years, a number of researchers have pay a lot ofattention to the community detection and have got a variety of community detectionalgorithms.The approaches of community detection can be divided as global communitydetection and local community detection. Local community detection is based on thelocal topological information of node，which has high expansibility to lower the consumeof time and memory. At the same time，in real world the nodes of many complex networksystems have kinds of properties, and nodes can belong to many different communities, sothe research on local overlapping community detection has a big utility value.Newman invented Newman fast algorithm which is based on greedy thought andpresented the criterion in evaluating the quality of a partition----modularity. Clauset,Newman and Moore proposed CNM algorithm based on Newman fast algorithm by usinga sparse matrix store the gain in modularity for each edge. CNM algorithm has the lineartime complexity, and is appropriate for large-scale networks. For using global modularity,the algorithm exists the problem to find small community in complex networks.Weak community definition proposed by Radicchi is small communitydefinition.There are many weak communities can be found in network. But it is still auseful and approved by many people.In the research and study kinds of community detection algorithms, the paperproposes LCNM algorithm to solve the difficulty of CNM algorithm to find smallcommunity. Using the local fitness proposed by LFM algorithm finds weak communitiesin network, and then uses these weak communities as the input network of CNMalgorithm. A node may have the very big fitness to many communities，so it can belong to several communities. So LCNM algorithm no matter can solve the difficulty to find smallcommunity but also can detect overlapping community.At last, we give tests on real andartificial networks.Tests prove that LCNM algorithm can detect overlapping community,get high effectiveness and have a high value of modularity.