Key User Discovery Of Online Social Networks Based On Dual Connectivity

With the development of Internet technology, many online social networks emerge, such as, Facebook, Twitter, Weibo, etc. The online social network is an information network, which is constituted by the users and their relationships. The online social networks have important applications in information diffusion, product promotion, the recommend system, political, education and culture. Taking Weibo as an example, users can share information, discuss information and transmit information. In reality, the information shared by famous users and stars etc., can be easily discussed and transmitted by other users of their followers. We can regard these users as critical users, who can easily spread the positive information or the information of products etc. How to find these critical users is the aim of our paper.In general, the main work of this thesis are as follows:(1) We first establish the undirected graph model with weights of edges to represent users’ influence degree.In this thesis, we establish a directed online social network by the "concern" and "comments" between users. The direction of an edge is denoted from the followers to the concerned users, and the weight of the directed edge can be computed by the number of comments and fans. However, the weight of the edge cannot well reflect the users’ influence degree. We further employ the PageRank algorithm to convert the weights of the directed graph to those of the users represented by nodes in the graph model. This method can establish a weighted undirected graph model, where the weight of the node represents the influence of the corresponding user.(2) We further propose a method based on the biconnectivity property to discover critical users in online social networks.In practice, the influence of a user is not only related to the users’ influence, but also related to the user’s location in the online social network. The biconnectivity algorithm can be used to find articulation points based on the topological structure of graphs, which can well reflect the importance of a node in the network topology location. Therefore, we combine the biconnectivity algorithm and the user’s influence to find the ctirical users.(3) Experimental resultsWe use the experimental results to verify the feasibility and the effectiveness of the proposed method.