1-1 大规模游戏社交网络节点相似性算法及其应用.pdf

1、规模游戏社交络节点相似性算法及其应林清Large-scale game social network node similarity algorithm and its application腾讯游戏社交络算法负责CONTENTS01Introduction02Previous Work03Experiments and Deployment04Our Solution05Optimizations06Conclusions 01IntroductionGraph is EverywhereMost of data can be naturally modeled as graphs.Soci

2、al networkGraph of webProtein-protein interaction(PPI)networkGraphs can easily depict the relations or interactions of data.Some homogeneous graphs:friendships,interactions between players,etc.Some heterogenous graphs:club memberships,item interactions,etc.playersItems/clubsGraph in GamesFriendships

3、 in gamesClub memberships or item purchasing in gamesGraphs could be massive!Billions of nodesHundred-billions of edgesRecommendation on GraphsFriend recommendation on the billion-scale game social network.News recommendation on the content heterogenous graphClub recommendation for game players.Appl

4、icationsTwo kinds of problemsOrdering existing edgesPredicting non-existing edges,Link Analysis and PredictionThe problems can be solved by learning the node proximity functions.?Common NeighborsFriends friends could be friends.Personalized PageRank(PPR)The PPR of with respect to,denoted by ,is defi

5、ned as the probability of a random walk starting with and ending at.Some Classical Node Proximity PPRs are asymmetric.Its able to answer high order proximity of two nodes by considering all the possible paths between them.$+(1 )$restart/termination probabilitycontinue probabilitystarting matrixnorma

6、lized adjacent matrixPPR matrixA Formal Definition of PPR Distributed algorithms for fully PPR,instead of single machine solutions or pair-wise/single-source solutions.DriverWorkerWorkerWorkerGraph is stored as the adjacent list,such as.Our FocusMapReduce computing framework:Map phase Take as input