Research On Detecting Community Structure Of Weighted Social Network

Social network is a kind of relation system composed of many nodes based on social relations.Community detection can help people understand the topology of the network and find some meaningful groups.The existing community detection algorithms are mainly used for detecting overlapping communities and non-overlapping communities.Overlapping community detection algorithm is a research trend in recent years.However,the algorithms based on local optimization ignore the social attributes of link,and set a relatively simple admission for nodes.It is easy to produce communities which contain large number of nodes.The emergence of this situation will make it difficult to improve the quality of overlapping community detection.A non-overlapping community detection algorithm called label propagation has near linear time complexity.However,the stability of detection result is poor because it uses a random approach when setting up the propagation queue and updating the labels.In view of the above-mentioned facts,this thesis conducts the following research:1.Aiming at the occurrence of large communities based on the local optimization,this thesis presents an improved overlapping community detection algorithm.This algorithm puts forward two suggestions for improvement.The first is to define the direct closeness and indirect closeness between nodes to generate weight.Then the new fitness function is generated by using the sum of weights which come from the internal and external community.Secondly,on the basis of node clustering coefficient,the concept of local community stability is defined in order to avoid the occurrence of large communities.When the local community chooses one node,it not only considers the contribution of the node to the community's fitness,but also considers the contribution of the node to the stability of the community.Experiments show that this algorithm can effectively detect the small community structure in the network.Meanwhile,when the network presents the characteristics of small community structure,the community detection quality of the proposed algorithm is improved compared with other algorithms.2.Aiming at the problem of low stability of community detection algorithm based on label propagation,this thesis presents an improved community detection algorithm based on label propagation.Firstly,the weight of node is defined by introducing the H index which measures the influence of researchers.Then the nodes are sorted according to the weight,and the ascending sequence is determined as the propagation queue to reduce the randomness of the algorithm.Finally,the updating strategy of node label is designed in the process of label propagation.This algorithm defined the weight of label in order to achieve the purpose of clustering.The node to be updated uses label with higher weight as its new label.Experiments show that this algorithm can obtain the unique community structure and improve the quality of community detection.