Research On Overlapping Community Detection Algorithm And Parallel Implementation In Location-based Social Networks

With the emergence of online social network platforms, the link information between users becomes more and more abundant. As one of the most important technologies of link mining, community detection has drawn so many researchers' attention. Traditional community detection algorithms, which mainly consider links, text content and so forth, rarely take location information into account. Due to the wide applications of mobile terminals and GPS technology, there is a wealth of location information in online social networking platforms. It is importantly meaningful to find a way to combine the location information and links to detect communities. In a real society, a user usually belongs to multiple communities which are mostly overlapping. This situation is similar in social network, in which the research of overlapping community detection algorithms combined location information is meaningful.Here community is defined as a set of edges based on link communities, so as to divide groups by edges. Since a node may be shared by different edges, then this node will be divided into different groups when its edges belong to different groups respectively. In this way, the overlapping communities can be detected. A parallel overlapping community detection algorithm is proposed based on Edge-means distance in location social networks. In this article, communities are detected using edge similarity which can be calculated with the similarity of nodes linked by the same edge. The link information and the location information are comprehensively considered when calculating the similarity of nodes. In addition, the weight of different factors in the algorithm can be adjusted automatically for the sake of better performance. However, because of the increasing edges in the network, the efficiency of the algorithm will be greatly compromised. To overcome this problem, a Hadoop-based parallel overlapping community detection method proposed. With this method, the efficiency of the algorithm is improved, and the algorithm is scalable.By conducting experiments on real data sets, the result of community division is evaluated by some measurements, such as modularity. The result depicts that the algorithm has a better performance than Clique Percolation Method(CPM) and K-means algorithm. With the analysis of the speedup of both the serialized version and the parallelized version, experimental results show that the parallelized algorithm possesses an excellent scalability.