SupervisedRandomWalks:
PredictingandRecommendingLinksinSocialNetworks
LarsFacebook
Backstromlars@facebook.com
1ABSTRACT
0Predictingtheoccurrenceoflinksisafundamentalprobleminnet-2 works.InthelinkpredictionproblemwearegivenasnapshotofavnetworkandwouldliketoinferwhichinteractionsamongexistingomembersarelikelytooccurinthenearfutureorwhichexistingNinteractionsarewemissing.Althoughthisproblemhasbeenex- tensivelystudied,thechallengeofhowtoeffectivelycombinethe7informationfromthenetworkstructurewithrichnodeandedge1attributedataremainslargelyopen.
WedevelopanalgorithmbasedonSupervisedRandomWalks]IthatnaturallycombinestheinformationfromthenetworkstructureSwithnodeandedgelevelattributes.Weachievethisbyusingthese.sattributestoguidearandomwalkonthegraph.Weformulateacsupervisedlearningtaskwherethegoalistolearnafunctionthat[assignsstrengthstoedgesinthenetworksuchthatarandomwalker ismorelikelytovisitthenodestowhichnewlinkswillbecreated1inthefuture.Wedevelopanef cienttrainingalgorithmtodirectlyvlearntheedgestrengthestimationfunction.
17OurexperimentsontheFacebooksocialgraphandlargecollab-0orationnetworksshowthatourapproachoutperformsstate-of-the-4artunsupervisedapproachesaswellasapproachesthatarebased.onfeatureextraction.
11CategoriesandSubjectDescriptors:H.2.8[DatabaseManage-0ment]:Databaseapplications—DataminingGeneralTerms:Algorithms;Experimentation.:1vKeywords:Linkprediction,Socialnetworks
iXr1.INTRODUCTION
aLargereal-worldnetworksexhibitarangeofinterestingproper-tiesandpatterns[7,20].Oneoftherecurringthemesinthislineofresearchistodesignmodelsthatpredictandreproducetheemer-genceofsuchnetworkstructures.Researchthenseekstodevelopmodelsthatwillaccuratelypredicttheglobalstructureofthenet-work[7,20,19,6].
Manytypesofnetworksandespeciallysocialnetworksarehighlydynamic;theygrowandchangequicklythroughtheadditionsofnewedgeswhichsignifytheappearanceofnewinteractionsbe-
Permissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforpro torcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationonthe rstpage.Tocopyotherwise,torepublish,topostonserversortoredistributetolists,requirespriorspeci cpermissionand/orafee.
WSDM’11,February9–12,2011,HongKong,China.
Copyright2011ACM978-1-4503-0493-1/11/02...$10.00.
StanfordJureLeskovec
University
jure@cs.stanford.edu
tweenthenodesofthenetwork.Thus,studyingthenetworksatalevelofindividualedgecreationsisalsointerestingandinsomerespectsmoredif cultthanglobalnetworkmodeling.Identifyingthemechanismsbywhichsuchsocialnetworksevolveatthelevelofindividualedgesisafundamentalquestionthatisstillnotwellunderstood,anditformsthemotivationforourworkhere.
Weconsidertheclassicalproblemoflinkprediction[21]wherewearegivenasnapshotofasocialnetworkattimet,andweseektoaccuratelypredicttheedgesthatwillbeaddedtothenetworkduringtheintervalfromtimettoagivenfuturetimet′.Morecon-cretely,wearegivenalargenetwork,sayFacebook,attimetandforeachuserwewouldliketopredictwhatnewedges(friendships)thatuserwillcreatebetweentandsomefuturetimet′.Theprob-lemcanbealsoviewedasalinkrecommendationproblem,whereweaimtosuggesttoeachuseralistofpeoplethattheuserislikelytocreatenewconnectionsto.
Theprocessesguidinglinkcreationareofinterestfrommorethanapurelyscienti cpointofview.ThecurrentFacebooksystemforsuggestingfriendsisresponsibleforasigni cantfractionoflinkcreations,andaddsvalueforFacebookusers.Bymakingbetterpredictions,wewillbeabletoincreasetheusageofthisfeature,andmakeitmoreusefultoFacebookmembers.
Challenges.Thelinkpredictionandlinkrecommendationprob-lemsarechallengingfromatleasttwopointsofview.First,realnetworksareextremelysparse,i.e.,nodeshaveconnectionstoonlyaverysmallfractionofallnodesinthenetwork.Forexample,inthecaseofFacebookatypicaluserisconnectedtoabout100outofmorethan500millionnodesofthenetwork.Thus,averygood(butunfortunatelyuseless)waytopredictedgesistopredictnonewedgessincethisachievesnearperfectpredictiveaccuracy(i.e.,outof500millionpossiblepredictionsitmakesonly100mistakes).Thesecondchallengeismoresubtle;towhatextentcanthelinksofthesocialnetworkbemodeledusingthefeaturesintrinsictothenetworkitself?Similarly,howdocharacteristicsofusers(e.g.,age,gender,hometown)interactwiththecreationofnewedges?Con-sidertheFacebooksocialnetwork,forexample.Therecanbemanyreasonsexogenoustothenetworkfortwouserstobecomecon-nected:itcouldbethattheymetataparty,andthenconnectedonFacebook.However,sincetheymetatapartytheyarelikelytobeaboutthesameage,andtheyalsoprobablyliveinthesametown.Moreover,thislinkmightalsobehintedatbythestructureofthenetwork:twopeoplearemorelikelytomeetatthesamepartyiftheyare“close”inthenetwork.Suchapairofpeoplelikelyhasfriendsincommon,andtravelinsimilarsocialcircles.Thus,de-spitethefactthattheybecamefriendsduetotheexogenousevent(i.e.,aparty)therearecluesintheirsocialnetworkswhichsuggestahighprobabilityofafuturefriendship.
Thusthequestionishowdonetworkandnodefeaturesinteract
Leskovec, “Supervised random walks: predicting and recommending links in social networks,” Proc. Fourth ACM Intl. Conf. on Web Search and Data Mining ...
用户能量模型 Edge{f1,f2……weight} Vertex{ tScore,dScore, weights[], pScores[] } Supervised Random Walks: Predicting and Recommending Links in Social ...
热门文档