Study On Overlapping Community Detection Based On Random Walk And Three-way Representation

Complex networks exist widely in the real world.As one of the most important characteristics in complex networks,community structure can reveal the topology structure of complex networks.Community structures often overlap with each other in real life,that is,a node may belong to multiple communities.In addition,complex network changes over time,and how to detect communities in the dynamic network is very important.Therefore,the algorithms based on random walk and three-way representation are proposed to detect community structures in static and dynamic complex networks.The thesis used three-way representation method to represent a community structure in a static network or a dynamic network,in order to accurately describe the uncertainty relationship between nodes and communities.It is different from the traditional community representation with adopting a single set,the three-way representation used a pair of sets to represent a community,namely,the core region and fringe region.The node in the core region and fringe region indicate that it belongs to a community certainty and uncertainty respectively.The three-way representation can intuitively reveal the relationship between a node and a community.A method was proposed based on random walk to detect the overlapping communities in the static network.Firstly,the local degree central nodes in the network were detected,and the seed communities were detected by the local degree central nodes;secondly,the communities were extended based on the idea of random walk and three-way decisions,that is,the probability that the node walks inside the community was greater than the probability outside the community;finally,the threshold of three-way representations are obtained by the idea of difference sorting,and the nodes were placed into the core or fringe regions of the corresponding community,respectively,which was beneficial to show the different importance of the nodes in the community.After that,a dynamic community detection algorithm was devised based on the previous static algorithm in order to detect the overlapping communities in the dynamic network.After obtaining the community structure of the last time snapshot,only the incremental network between the two time snapshots was calculated.Considering the different importance of nodes in the network,different strategies were used to adjust the community structure of the last time snapshot to get the communities at the current moment,it avoided the repartitioning of nodes in the network.In this thesis,the proposed algorithms,CFinder,SLPA,FacetNet and other were compared on the artificial datasets and real datasets such as Football,Yeast and CellPhone Calls.The experimental results showed that the proposed method was better in Modularity,NMI,F-score values and other evaluation index than the comparison methods,and the results also indicate that the work in this thesis was effective for solving overlapping community detection.