Research On Methods Of Community Detection And Community Search In Social Networks

In recent years,social media networks,represented by online social networks and e-commerce networks,have been developing rapidly.Community detection can reveal the organizational structure of networks,contribute to understand the function of complex networks and discover the laws contained in networks.As an important social network analysis technology,community detection has attracted a lot of attention.This dissertation focuses on the research on methods of community detection and community search in social networks.Specifically,the main research work and contributions are listed as follows.Most of the existing global community detection algorithms rely on the connection relationship between nodes to discover the community structure in networks and ignore the different influence of each node in the process of detecting communities.In view of this problem,a community detection algorithm based on central maximum clique expansion is proposed.Firstly,several cohesive and influential central maximal-cliques distributed in the network are selected as the initial communities.Then,for nodes outside the initial communities,the local modularity expansion method is used to divide them into the closest communities.The experimental results show that the proposed algorithm can better reveal the community structure in networks.Local community detection is a kind of methods that can find out the community of a given node by using the local network structure around the node,and has import research significance for the research of large social networks.Most of the existing local community detection algorithms require users to specify the parameter values manually and have low accuracy.For solving this problem,a new local community detection algorithm based on common neighbors similarity measurement with weighted neighbor nodes is proposed.Firstly,we propose a newcommon neighbors similarity measurement with weighted neighbor nodes,which is employed to estimate the similarity between two nodes in a network.Then,a new local community quality metric is given.We discover the local community of a given node by iteratively adding a shell node to the target community that has the largest embedded degree with the current local community,while ensuring the gain of the current local community quality is not negative.Extensive experimental results show that the proposed algorithm is highly effective at local community detection.Community search is a query-oriented variant of the community detection problem.Different from local community detection algorithms which rely on local network structure of the given node,community search algorithms can make use of not only the local structure around the given node but also the global network structure.Node embedding has adopted deep learning technique to learn lowdimensional real-valued vector representations of nodes from network structure directly,and offers a new approach to solve community search problem.Motivated by this,for solving the community search problem without limitation of returned nodes,a new community search algorithm based on node embedding with a CNbased random walk is proposed.Firstly,we propose a new node embedding model with a CN-based random walk and learn the low dimensional representation of nodes via this model.Then,we expand the target community by greedy addition of a shell node that has maximum similarity with the current community and implement a new community search algorithm.The experimental results show that the proposed algorithm is more effective and efficient for community search than the related algorithms.For solving the community search problem with limitation of the number of returned nodes,a new community search algorithm based on node embedding representation learning is proposed.In view of the problem that the existing node embedding algorithm has a high probability to walk back and forth between the closest neighbors,a node embedding model based on closest-neighbor biased random walk with non-immediately revisiting is proposed and the nodes are mapped to points of low dimensional space via this model.Motivated by the idea of geometric center in multi-dimensional space,the vector mean of all nodes in a community is used as the vector representation of the community,and a new community search algorithm is implemented by selecting the node closest to the current community tojoin the community.The experimental results show that the proposed algorithm has higher accuracy than the related algorithms.In summary,this work focuses on the research of community detection and community search problems in social networks,which include global community detection problem,local community detection problem,community search without limitation of returned nodes and community search with limitation of returned nodes.We hope that the research achievements of the dissertation can be helpful to research on community detection and community search in social networks.