Key Technology Research On Personalized Ranking Based On Random Walk In Social Networks

With the rapid development of online social networks, such as instant message, Microblog, We Chat, forum, blog, and content sharing social networks, the method that people access information from the Web has changed from simple information searching to building and maintaining of social relations, and the social relation based information sharing, communicating and producing. Recently, all kinds of online social networks have become the necessary part in people’s daily life. Social network is a complex network structure that is made up of people, organizations and the relations between them.Besides online social networks, World Wide Web, paper citation network and even gene network are all considered to be social networks. In social networks, personalized ranking recognizes important nodes in the networks, and can be used in link prediction, personalized searching and recommendation.From the perspective of personalized ranking, social networks usually have the following characteristics. The scale of nodes in social networks is massive, and the attributes of nodes update dynamically. Different users have different weights considering their social relations, and personalized ranking needs to quantify them reasonably. Social networks are from different applications, and different application scenarios need different personalized ranking approaches. Based on analyzing related works, in order to deal with massive data and various applications in social networks, this paper studies several key technologies on personalized ranking based on random walk, and the main research contents and contributions are as follows:For the problem of massive data, based on theory of transition probability matrix and approach of chain of random walk, this paper proposed a binary tree random walk based parallel node personalized ranking approach in Map Reduce. Firstly, proposed a binary tree random walk model; then, generated a series of independently binary tree array for each node based on the proposed model; and finally, implemented the parallel personalized ranking algorithm for some root node in Map Reduce, and used the ratio that a node appeared in binary trees with same root node to represent the personalized ranking value of the node relative to the root node. Theoretically analysis shows that, while keeping the same ranking accuracy, the proposed algorithm has less iterations, I/O data and execution time than the chain random walk based personalized ranking. Experiments on social networks with million nodes validate the efficiency and effectiveness of the proposed algorithm.For the problem of dynamic locations of nodes in social networks, this paper proposed a chain random walk based location oriented personalized ranking approach. Firstly, in mobile social networks, filtered nodes containing the specified location, their neighbors and the relations between them, and constructed a sub-network. Secondly, introduced’authority’ that reflected the importance of node and ’hub’ that reflected the patency of node, analyzed ’authority’ and ’hub’ statistically in the sub-network based on chain random walk, and used the authority to represent the personalized ranking of the node relative to the specified location. Finally, ranked nodes relative to some import locations, saved all the ranking results, and used them to answer queries for some specified location. Experiments on real social network dataset show that, the proposed algorithm has better query hit rate and less execution time than the popular Hub Rank algorithm.This paper proposed a chain random walk based inverse influence ranking approach.The inverse influence is the influence of other nodes to the personalized node. Because of the small world phenomenon in social networks, all nodes can reach any other node in the social network with small steps, such as 6 steps. Based on this phenomenon, in directed social networks, this paper constructed a chain random walk from each of other nodes, used the sum of probabilities that a node reached the personalized node in limited steps to represent the inverse influence of the node relative to the personalized node. This paper proposed a chain random walk based inverse influence approximation algorithm.Experiments of link prediction on real social network datasets validate the effectiveness of the proposed algorithm.This paper proposed a chain random walk based recommender approach while recommending commodities to a user. In social recommender systems, it is very important to ascertain the recommender weights of other related users relative to the personalized user. Firstly, constructed a social recommender graph according to combining the user×user social network and the user commodity rating network by merging the same user nodes; then, on the social recommender graph, started form the personalized user,did the user-commodity-user chain random walk iteratively, and used the ratio of a user appearing in the chain random walk to weight the user’s recommendation relative to the recommended user; and finally, proposed a chain random walk based social user weighted recommender algorithm. Experiments on real social network datasets show that, the proposed algorithm has better commodity coverage and recommender accuracy than other simple recommender algorithms and social recommender algorithms.