Research And Design Of Community Detection Algorithm

In real life,not only social networks represent the relationships between entities in the form of a network,but also the network can be used to represent the biosphere and the Internet.The nodes in the network represent an entity,while the edges in the network represent the relationships between the entities.An important property of these networks is the community structure.Community division of community structure is the basic method of mining node preferences and relationships among nodes.Therefore,community division is also attracting more and more scholars' attention.This thesis mainly studies two aspects of non-overlapping community division and overlapping community division.The main work and contributions are as follows:(1)Aiming at the problem of stochastic selection and instability in LPA and its operation without discriminating all nodes,a label propagation algorithm based on node importance and random walk matrix(NILPA)is proposed.In this algorithm,we give the definition of the importance of nodes to distinguish each node in the network,and use the importance to sort the nodes in the network.In the stage of label propagation,the algorithm constructs a new measurement function based on random walk matrix and node importance,which can effectively avoid the random selection of labels by nodes.Finally,divide the community by the node's label after the label propagation has ended.The algorithm not only guarantees the performance of community partitioning,reduces the randomness of the algorithm,but also makes some modifications to the algorithm to deal with the division of overlapping communities.(2)Aiming at the lack of reliable fireworks initialization method in fireworks algorithm,a non-overlapping community partitioning algorithm based on fireworks algorithm and local double rings(LDRFA)is proposed.In this algorithm,we first give the definition of local double rings,which can effectively improve the process of fireworks initialization,and the method of initialization is universal.Then in the generation and selection phase of fireworks,we combine the idea of label propagation algorithm to carry out fireworks variation.Finally,the method proposed in this paper can be used to solve the problem of non-overlapping community partition effectively.Compared with other comparison algorithms,the performance of this method is also greatly improved.(3)Aiming at the problem of overlapping phenomenon in initialization and ants lack of prior knowledge,an ant colony random walk algorithm(ACRWA)is proposed to deal with overlapping community partition.The algorithm can be mainly divided into three parts: non-overlapping ant colony initialization stage,ants spread label stage and post-processing stage.Firstly,a new ant colony initialization method is used to find the non-overlapping initialized ant colony in the network.A new heuristic message is given in the ants spread label stage.Using this heuristic information allows ants to make smarter decisions when pheromones have not yet precipitated.In the post-processing phase,the algorithm mainly deals with two phenomena: over-overlapping community and over-small-scale community.Finally,experimental results on datasets show that the ACRWA algorithm has better performance than other algorithms and can find more accurate overlapping communities and overlapping nodes.