Research Of Community Detection Algorithms Based On Node Similarity In Complex Networks

Complex network is an abstraction of many practical problems in the real world,which can reflect the interaction of individuals in the networks.Community structure is an important structural feature of the network,it normally corresponds to functional modules in the system,and extracting such structure can explore the internal rules of the network and the potential relationships among nodes.Therefore,community detection in complex networks is of great theoretical significance and application value,and has been widely concerned by researchers in various fields,accordingly many community detection methods have been proposed.On the basis of fully studying these algorithms,this dissertation proposes a local community detection algorithm applied to the static complex networks and an incremental community detection algorithm for extracting communities from the dynamic networks by exploring the similarity characteristics of nodes.(1)The Node Similarity Based Local Algorithm for Community Detection.This algorithm makes full use of the degree information and network topology,calculates the similarity among nodes,and constructs the community structure locally in an efficient way.Moreover,this dissertation also designs an index to measure the community sparseness and scale which can solve the problem of limited resolution.The algorithm consists of two phases.The first phase uses degree information to reflect the influence of nodes.Specifically,at each time,the node with the largest degree is selected from the nodes that have no community assignment,and then the preliminary community is constructed for this node and its most similar neighbour node.After repeating the above process,all nodes in the network will have the preliminary community assignment.Since some of preliminary communities might be too small or too sparse,the second phase uses the index mentioned above to measure the size and the sparsity of communities.If a preliminary community does not meet the community metric,it will be merged into its most similar neighbour community,so as to obtain the resulting community structure with high quality.(2)The Incremental Community Detection Method for Dynamic Network Based on Node Similarity.After obtaining the community structure of the first snapshot,this algorithm only detects the incremental part of the graph that changes in the evolution,and directly inherits the stable communities that do not change.Besides,by defining active nodes,the algorithm only considers from the perspective of node variations,so that simplifies the complex edge variations.The algorithm consists of three phases.The first phase is to inherit the community structure of the previous time step,remove the disappeared nodes in evolution,select the nodes which community affiliations may change from the previous time to the current time,and define them as active nodes together with the newborn ones.Next,constructing the initial communities for the active nodes by degree information and node similarity.At last,the final community structure on each snapshot can be obtained by merging and optimizing the result based on the modularity increment.In order to verify the performance of the proposed algorithms,experiments are fully carried out on several real network data sets and synthetic network data sets.The experimental results are compared with some related popular algorithms,the results show that the proposed algorithms can effectively extract high-quality community structures from various networks.