Reasearch On Community Detection Algorithms Based On Similarity

Community structure is one of the most important topological properties of complex network.The communities always represent modules with unique function or characteristic.Therefore,extracting those modules from network can benefit researches on complex network.Such as in biology field,the community in a protein interaction network always corresponds to the protein tissue with the same structure or function and in sociology field,the community corresponds to people with the common features.Therefore,community detection is so important for theory research and practical application that researchers from various fields have pay their attention to it and lots of algorithms have been proposed.Based on study on these algorithms,this thesis proposes a bisection spectral method using the optimal eigenvectors and another one method using similarity closures.Based on the bisection spectral method,we propose a community detection algorithm using the optimal eigenvectors.During the procedure of split network,this method prefers to choose the eigenvector that produces the maximal modularity increment rather than use the particular one.So,the proposed algorithm can take the full use of spectrum information from matrix.Besides this,to make full utilization of more adjacency information,we define a similarity rule to convert the original network into a weighted one and rewrite the algorithm to adapt to the change.Finally,the algorithm can extract community structure with larger modularity.The second method this thesis proposes is based on a similarity measure.This thesis defines the functional dependency between vertices according to the similarity rule,which describes whether two vertices belong to the same community or not.Then,based on the functional dependency,we define a closure for the vertex,and all vertices in the closure belong in the same community.To get the final communities,we choose closures that are not contained by other closures as maximal closures.After solving the overlapping among maximal closures,the algorithm obtains the resulting the community structure with clear boundary.To verify the effectiveness of community detection algorithms proposed,this thesis also conducts experiments on some network datasets,with some existing community detection algorithms as a comparison.The experiments finally demonstrate the proposed algorithms can extract community structure with high quality and they can be applied on almost all kinds of networks effectively.