A Research Of Community Detection Based On Node Neighborhood Information And Similarity Matrix

Complex networks are the abstract descriptions of complex systems in reality,such as social networks,scientific cooperation networks and biological protein systems.Communities are used to describe closely connected clusters or modules of complex networks,while community detection is the use of special topologies in the network to identify clusters of closely connected nodes,also referred to as network clustering.Community detection can help people discover potential structural patterns in the network and further understand the organizational functions of the network.In recent years,researchers have designed many community detection algorithms for complex networks from different perspectives,but most of the algorithms are proposed merely for handling a single network structure,such as unsigned networks.However,the reality of complex systems often covers a variety of features.For instance,signed networks describe a variety of relationships between entities,and attribute networks can not only represent the relationship between entities,but also explicate the attributes or characteristics of the entity.Therefore,these networks provide a more realistic picture of the complexity of real systems and present even greater challenges to community detection issues.In addition,taking full advantage of the neighborhood information of nodes to design more appropriate operation steps,the detection accuracy of the algorithm will be greatly improved.In view of the ubiquitous problems existing in the existing algorithms,this dissertation conducts deep research on different types of networks.The specific solutions are as follows:1)A community detection algorithm based on node neighborhood information and three closely joint strategies is proposed.First of all,the algorithm introduces the methodology of K-nearest neighbor into label propagation algorithm(LPA)and proposes a network pre-division strategy.This strategy takes the closeness between nodes into more consideration,and overcomes the defect that the LPA cannot identify the community when the community structure is vague,so that the algorithm can accurately identify the closely connected sub-communities at the initial stage.Secondly,devise a community integration strategy based on the first stage,and effective integration of sub-communities with high closeness is achieved.Finally,a refinement strategy is used to reclassify misclassified nodes.The algorithm has little dependence on the number of initial points and the number of iterations,so it can save a lot of running time and is suitable for community detection problems of large-scale networks.2)A multi-objective network clustering algorithm based on K-nodes updating strategy and similarity matrix is proposed for identifying communities in social networks.First of all,a generalized similarity function is established to calculate the similarity matrix of unsigned or signed networks,and a preprocessing strategy is projected according to the similarity matrix of nodes.The preprocessing strategy merely considers some nodes with high similarity values,which avoids the interference of noise nodes during the label update phase.Thus,nodes with dense connections can be rapidly gathered into sub-communities.Secondly,the crossover operator is designed and used to merge the sub-communities resulting from the preprocessing strategy,and the mutation operator based on the similarity matrix is used to adjust the communities to which the boundary nodes belong.Finally,build multi-objective optimization models and use them to handle different types of networks.Therefore,the algorithm can deal with the community detection issues of unsigned or signed networks.3)A new method based on multi-objective discrete particle swarm optimization algorithm combining edge structure and node attribute.Firstly,the algorithm calculates the similarity matrix of the edge structure and the attribute similarity matrix of the nodes,and then combines the two to obtain the hybrid similarity matrix through a hybrid parameter.Based on this,an algorithm for updating the label of nodes is proposed.Secondly,considering the operability of particle swarm optimization and its high time efficiency,this algorithm originally introduces multi-objective discrete particle swarm optimization into attribute networks.Finally,the average attribute similarity function is formulated and used to construct the multi-objective optimization model.It can take into account the dense connections between nodes in the community as well as the high homogeneity of node attributes.