Research On Community Detection And Application In Online Social Networks

With the rapid development of Web2.0, the OSNs (Online Social Networks), as a practical, new dating pattern, has become an indispensable part of people’s life and work. People in the OSNs are connected to each other through a variety of mutual relationships, forming many content-rich and complicated communities. For practical applications in business, current research of community is facing two major challenges. First, due to the virtual and the openness of the OSNs, how to automatically detect communities of OSNs is an urgent problem to solve. Second, the community as a new field of marketing, how to effectively evaluate the user’s social influence in the community has become a major concern.This thesis first introduces community detection algorithms, which are based on common neighbor similarity (CNS) and node attribute similarity (NAS) respectively. In order to overcome the shortcomings of the two algorithms, based on the unique characteristics of OSNs, we propose the concept of user tightness and design a community detection algorithm based on it (UTCD). UTCD computes user tightness for all edges, which are further processed with hierarchical clustering algorithm to detect communities. Finally, we validate the effectiveness of UTCD algorithm in two aspects of modularity and accuracy. Experimental results show that the communities detected by our algorithm have much higher degree of cohesion and accuracy compared with NAS and CNS.In addition, this thesis also analyses the unique structures of the community and interpersonal interaction among it, and shows that the number of friends, the quality of friends, and the community label, are three key factors to a user’s community influence which means a user’s social influence in a community. In order to more effectively evaluate the user’s community influence, we propose two new concepts of influence ability and community label and design a novel UCI (User Community Influence) model to evaluate a user’s community influence. Our initial model is established based on PageRank, then the influence ability is computed for improving the initial model. Experimental results show that our model can evaluate a user’s community influence with higher efficiency and more rationality than traditional models.In summary, this thesis solves not only the problem of automatically detecting communities of OSNs, but also the problem of community used in the marketing field to assess the problem of community used to the field of marketing. These achievements can be well applied to applications, and hope to change the "research more, while applied less" status of the community in OSNs.