Community Detections In Online Social Networks

With the development of mobile networks, online social network has become an important type of network application, and has been deeply changing our lives and societies in many aspects. Users in online social networks naturally form into group(community) structures based on their social circles and interests. The dissemination of information and evolution of social networks are strongly related to these structures. And how to detect communities in online social networks has been a popular area of study. In this paper, we study the modeling of social networks and community detection algorithms, and propose a novel neighborhood vector propagation algorithm for community detection in online social networks.Our algorithm is divided into two stages, namely neighborhood vector propagation and hierarchical clustering. First, to define the similarity between two nodes in the network, we introduced the concept of neighborhood vector. A neighborhood vector is a normalized vector in multi-dimensional space, whose direction contains topology information within a certain range of the node. In the stage of neighborhood vector propagation, each node exchanges topological information with its adjacencies, mixing its vector with that of its neighbors, and eventually obtains a neighborhood vector. Node similarity is then derived from neighborhood vectors, and a larger similarity indicates a larger probability that these two nodes are in the same community. In the hierarchical clustering stage, we iteratively merge adjacent nodes with the largest similarity, and keep neighborhood valid and in a low complexity through a vector combination and dimensional reduction procedure. In the end we obtain the community structure of the network.To further evaluate the accuracy of our algorithm, we apply it to real-world networks and LFR benchmark networks. The result shows that the similarity based on neighborhood vector can accurately measure the similarity of two online network nodes. And our algorithm achieves greater accuracy than serval well known algorithms.