Research On Community Division Algorithm Of Weighted Networks

Complex networks can be seen as highly abstract of the myriad connections between things in the real world.The weighted network can reflect the closeness of the connection between the nodes,giving the network more explicit physical meaning.Community structure is one of the important characteristics of complex networks,which can reflect the internal structure and function of the network.Since communities in the real world may be independent or overlap with each other,the discovery of these two types of communities in weighted networks has its practical significance.Therefore,this thesis studies both overlapping and non-overlapping community division algorithms for weighted networks,and the main work is as follows:Aiming at the division of non-overlapping communities in weighted networks,this thesis designs a weighted network community division algorithm IMWCD based on node importance and modularity optimization to improve the accuracy of the division results.The algorithm uses the idea of degree centrality and Page Rank,the weighted network node importance calculation method WNI,which integrates the information of the node itself and its neighbors,and the idea of community division based on modularity optimization.Firstly,each node is initialized as a community,and the node importance is calculated.Then,nodes are traversed according to the ascending order of node importance,and the target node is moved into the corresponding community according to the principle of maximum modularity gain until each node does not need to move again.Then,each community is taken as a node to reconstruct the network.Repeat the process until the modularity of the network does not change.The experimental results on the LFR artificial benchmark network datasets and multiple real network datasets show that the IMWCD algorithm effectively improves the accuracy of community division,and has linear time complexity,which is suitable for large-scale weighted network community division.Aiming at the division of overlapping communities in weighted networks,this thesis first defines the similarity between nodes based on global information GNS,and then fuses it with the idea of label propagation to design an overlapping community division algorithm based on similarity and label propagation GLWOCD.In the initial stage,the algorithm takes the node number as the node label and sets the membership degree of each node to 1.In the process of label updating,the WNI method is used to calculate the importance of nodes,and the nodes are traversed according to the ascending order of node importance.The label membership degree of the current node is calculated according to the GNS similarity between the current node and its neighbors,and the neighbor node label whose membership degree is greater than the set threshold is taken as the new label of the current node.When the primary labels of all nodes do not change or the algorithm is executed to the specified round,the nodes with the same label belong to the same community,and the nodes with multiple labels belong to multiple communities at the same time.Experimental results on the LFR artificial benchmark network datasets and multiple real network datasets show that the proposed algorithm can more effectively divide overlapping communities in the network.Based on the above research results,this thesis further designs a weighted network overlapping community division algorithm GIMWOCD based on GNS and IMWCD.Firstly,the algorithm uses the IMWCD algorithm to divide the community,and then calculates the GNS similarity between each node in each community and other communities.The node can simultaneously belong to more than one community whose similarity is higher than the set threshold.Thus,the overlapping communities in the network are divided.Experimental results on the LFR artificial benchmark network datasets and multiple real network datasets show that the GIMWOCD algorithm can achieve overlapping community division more effectively,and is more stable than GLWOCD algorithm,and has higher time efficiency.