Study And Implementation On Algorithm For Friends Recommendation Based On Egocentric Network And GPS Trajectory Information

With the development of Internet technology, especially the advent of the era of Web2.0, tens of thousands of users have registered in all kinds of social networking sites. They communicate and make friends with others online through social networks platform and release, share and propagate the information, which have provided more abundant resources for various recommendation service based on social network. In addition, with the wide application of mobile devices, users' locations and trajectory information have become a new kind of information resources which will contribute to recommend service more obviously. For the current popular social networking service microblog, this thesis studies on the construction of user egocentric network and algorithms for recommending friends based on the egocentric network. Moreover, this thesis studies on the friend recommendation approach based on the egocentric network and GPS trajectory information by adding trajectory information when constructing the egocentric network.Firstly, based on the intuition that a certain user will be more inclined to make friends with those users who are in the same social circle than the other social circles, this thesis introduces the algorithm of label propagation for dividing community for accelerating the process of recommending friends.Secondly, in a community, it is observed that a certain user will be more inclined to make friends with those users who are close on the network distance than those far ones. Based on this observation, this thesis proposes an algorithm of constructing a K-degree egocentric network in the sub-community where a certain user belongs, which can lay the ground for further recommendation of friends.Thirdly, in a certain user's egocentric network, this thesis builds the model of recommending potential friends based on SimRank for the relationship of bidirectional link and the model of recommending potential friends based on Unidirectional SimPropagation for the relationship of unidirectional link. Two novel algorithms are designed for recommending friends based on the two models respectively.Fourthly, the mobile devices which support position are widely used in recent years, thus user's position information can be obtained easily. This thesis proposes a method of measuring the trajectory similarity based on distance and trend through importing the GPS information layer into the user layer. The proposed method constructs a two layer social network structure model which contains the user layer and the geographic information layer. With the help of the model, the recommendation of friends based on the GPS trajectory is implemented.Finally, the experiment results validate that the proposed algorithm for the recommendation of friends is effective. Especially, it is more meaningful to import the GPS information when recommending friends.