文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > Supervised Random Walks Predicting and Recommending Links in Social Networks
侵权投诉

Supervised Random Walks Predicting and Recommending Links in Social Networks

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

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email