Community Detection Algorithm Based On The Fair Expansion Model And The Targeted Local Expansion

Community detection is an important domain in complex networks.This dissertation starts from reviewing definitions of the community,nowaday methods of community detection,synthetic networks for testing and the evaluation for community detection results.First,based on Clauset's local graph model,the Fair Expansion model is proposed.In addition,we discussed the Fair Expansion Function,which is the state transition function of the Fair Expansion model,and proved that a poset can be constructed by the state transition function in the state space2~V as well as the property of the maximal elements and the comparable element sets of those elements is similar to attractors and its basins.After the Fair Expansion Function,the Fair Expansion Algorithm to expand the seed community into the fruit community is proposed,which has a number of groundbreaking characteristics:the insensitivity to noise in seed communities,the potential of learning the community feature in label networks,and the prior evaluation on expansion precision and expansion difficulty.Next,based on the Fair Expansion Algorithm,a new local community detection algorithm,the Targeted Local Expansion community detection algorithm,is proposed.The algorithm consists of two phases:the preparation phase on the label network to obtain the expansion parameters and the detection phase on the network to be mined.A node exploration sequence is also transplanted from the subgraph isomorphism problem into the community detection problem to generate seed communities from nodes.Finally,the time complexity of the Targeted Local Expansion community detection algorithm is discussed.The performance of the Targeted Local Expansion community detection algorithm is experimentally verified and compared,and the feasibility and the validity of the algorithms are also verified.