Research On Detecting Communities And Influential Spreaders In Social Networks

With the rapid development of the Web2.0 technology,people's lifestyle has undergone great changes.The relationship between people in the real world has a new extension on the Internet,people interact with each other through the Internet,thus contributing to the development of the social network.For example,in recent years,some typical social network service platforms,such as Facebook,Wikipedia,and Sina Weibo,have seen a rapid increase in the number of users.In social networks,users are the core and the main body of the networks.Users form the basic structure of the social networks through link relationships.Through this structure,users on social networks are driven by common goals or interests,carrying out various types of information transmission and sharing.In the real world,people's activities often show obvious group features,such as family groups,friends groups,and so on.Similarly,in the network world,the interaction between users also presents obvious group features,also known as the community structure characteristics of the network.That is,some users interact more closely,while others interact sparsely.These users interacting closely with some others form a community on the web.At the same time,the clustering effect of the online society raises the emergence and development of many events and activities in the real world.For example,the terrorist organizations and extremist organizations organize and launch terrorist activities through social networks,which greatly jeopardizes national security and social stability.In addition,the formation of group aggregation effect is also inseparable from some key individuals in the network for information dissemination.These individuals often have higher levels of influence in the online community,which promotes the formation of the group and the speed of aggregation.Through the identification of these key individuals,the process of information dissemination can be effectively controlled to avoid adverse events.Therefore,the research on community detection and key individuals identification method in social networks has important theoretical and practical significance for maintaining social stability,inhibiting the dissemination of harmful information,and national security and stability.At present,researchers can analyze and study the characteristics of social networks from multiple different perspectives,but the analysis of the structural characteristics is the basis of other analysis methods.Individuals conduct the interaction and transmission of information based on the link relationship between them.The change in the structural relationship directly affects the breadth and depth of information transmission.Therefore,from the perspective of the structural characteristics of the social networks,this thesis conducts related research on community detection and vital nodes identification methods.The main contribution of this thesis can be summarized as the following four aspects:(1)In the field of static community discovery,aiming at resolving the accuracy problem of the classic community detection methods,this thesis proposes a fruit fly optimization method based on group intelligence strategy for partitioning communities in the network(CDMFOA).Compared with the traditional community detection methods based on biological evolution or group intelligence strategy,the community detection method based on the fruit fly optimization algorithm has the advantages of less artificial parameters,simple calculation process and easy understanding.However,the simple fruit fly optimization algorithm for community detection is easy to fall into the local extreme value in the process of finding the optimal community divisions,and the global search ability of it is weak.In order to resolve this problem,this thesis uses the local hill-climbing search to enhance the local search ability of the algorithm,and utilizes multi-swarm strategy to improve the global search ability of the algorithm.Through the experimental research and analysis on four real networks and artificial networks,this thesis shows that the proposed method has good global and local search ability in the solution space,which makes the final community partitioning results own high accuracy.(2)In the field of static community discovery,the traditional methods usually need to obtain the global topological structure information of the network,thus own high time complexity,which are not fit for the community detection problems in the large-scale social networks.In this thesis,based on the definition of a novel node influence evaluation method(LH-index),a community detection method based on the LH-index of the nodes is proposed according to the characteristics of the core-edge structure of the network.This method determines a node's influence level by computing the LH-index value of it,and then sorts all the nodes according to their LH-index values,then carries out the label propagation process according to this order.Thus,the new proposed method overcomes the instability of the traditional label propagation method for community detection,which is caused by the two randomness problems(the randomness of the initial nodes selection and the label update strategy).Through the experimental research and analysis on the real networks and synthetic networks,this thesis demonstrates that the new proposed method not only has low time complexity,but also can find out the community structure characteristics of the network,and acquire the community partition results more stablely.(3)In the field of dynamic community discovery,for the majority of current dynamic community discovery methods,they can not detect the hierarchical and overlapping community partitions,and ignore the effects of the interaction strength variation between the nodes on the community detection problem.In this thesis,a hierarchical and overlapping community detection method for dynamic weighting networks is proposed.This method can not only reveal the community structure in the dynamic networks,but also can detect the overlapping communities.At the same time,this method can also obtain a hierarchical structure of the community by adjusting a parameter.The main idea of the proposed method is based on the weighted edge fitness and weighted partition density so as to determine whether to add a link to a community and whether to merge two communities to form a new link community.Experiments on both synthetic and real world networks demonstrate the proposed algorithm can detect hierarchical and overlapping community partitions in dynamic weighted networks effectively.(4)In the field of vital nodes identification,there is a big difference between the theoretical influence level of the node(the calculated value of the evaluation method)and the actual influence level(taking the single node as the information source,and using the information dissemination model to calculate the actual number of the infected nodes in the network)for the majority of current methods.This thesis presents a kind of vital nodes identification method based on local h-index(LH-index).H-index is a new method proposed recently for measuring the influence of the nodes in networks.In terms of assessing the actual influence level of the node,the accuracy of the h-index is higher than that of the traditional methods.Meanwhile,the h-index is not sensitive to the small variation of the degree value of the node,and only requires the local information of the network.However,the h-index has a resolution limit problem.In this thesis,we propose a local h-index centrality(LH-index)method to identify and rank vital nodes in networks in order to resolve the deficiency of the h-index method.The LH-index method simultaneously takes into account of h-index values of the node itself and its neighbors,which is based on the idea that a node connecting to more influential nodes will also be influential.According to the simulation results by utilizing the stochastic Susceptible-Infected-Recovered(SIR)model in four real world networks and several simulated networks,we demonstrate the effectivity of the LH-index method in identifying influential nodes in networks.Besides,recent researches pointed out that the characteristics of the community structure in the network can influence the information spreading ability of the nodes.On the basis of the LH-index method,this thesis also considers the influence of the community structure on vital nodes identification problem,and proposes a kind of vital nodes identification method based on the community structure of the network.Through the experimental research and analysis on the real world networks,we demonstrate that the proposed method can effectively identify vital nodes in networks with community structure.