Research On Community Detection Algorithms Based On The Node Following Relationship

The goal of community detection is to divide a network into several communi-ties,and nodes in the same community are more closely connected than those in differ-ent communities.Most traditional community detection algorithms divide each node into only one community,but in real-world networks,a node often belongs to multiple communities.Therefore,overlapping community detection is of great significance in real-world networks.Traditional community detection algorithms usually require the global information of the networks.However,it is often highly expensive,even impos-sible,to obtain the global information of large scale complex networks.Furthermore,in some practical applications,we only need the local community of the given node,rather than the community structure of the entire network.Therefore,it is relevant to study the problem of local community detection.In addition,for a given starting node,sometimes we may want to get a smaller community,and sometimes we want a larger community.Therefore,multiscale local community detection is also meaningful.This thesis studies overlapping community detection,local community detection and multiscale local community detection.The main contents include the following two aspects.(1)CDFR is an effective non-overlapping community detection algorithm that pro-poses the concept of NGC node.For any node,its NGC node refers to the nearest node with greater centrality.In this thesis,CDFR is extended for overlapping community detection,and the extended algorithm is called as OCDFR.In OCDFR,CDFR is first called to obtain a non-overlapping community partition.Then,find the kth NGC(k=1,2,3,...)node for each node,and record the fuzzy relations between them.Based on the fuzzy relation between a node and its kth NGC,five decision methods are proposed to determine whether it can join the communities to which its kth NGC belongs.We test our algorithm on ten real-world networks such as karate,dolphins and pol.books,and four LFR synthetic networks.The experimental results demonstrate that OCDFR is effective.(2)We propose a local community detection algorithm LCDNN based on NGC nodes.In the LCDNN,local community C initially consists of the given node,v.Then,the remaining nodes are added to the local community one by one,and the following conditions need to be satisfied by a node:1)its NGC node is in C,or it is the NGC node of the center node of C,2)the average fuzzy relation of the local community does not decrease if a node is added to C,and 3)the fuzzy relation between the node and its NGC node is the largest.We test our algorithm on five real-world networks such as karate,strike and five LFR synthetic networks.Experimental results show that LCDNN is effective.Concurrently,LCDNN is also extended for multiscale local community detection.The preliminary experimental results show that our algorithm can detect meaningful multiscale local communities.In this thesis,we study the community detection algorithms based on NGC nodes,and demonstrate the effectiveness of our proposed algorithms on real-world networks and LFR synthetic networks.The work of this thesis has some reference value for the re?search of overlapping community detection,local community detection and multiscale local community detection in social networks.