《Random Walks on GraphsHomERNET图上的随机游动的家庭网络》由会员分享，可在线阅读，更多相关《Random Walks on GraphsHomERNET图上的随机游动的家庭网络（58页珍藏版）》请在金锄头文库上搜索。
1、Random Walks on GraphsLecture 18Monojit C吹褥雷产虽韩挑垫些稻阐守丽忘栽些捂毙茫寒惨偶建隘苛苞瑟织啤佬穴爆Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络What is a Random WalkGiven a graph and a starting point (node), we select a neighbor of it at random, and move to this neighbor; Then w
2、e select a neighbor of this node and move to it, and so on;The (random) sequence of nodes selected this way is a random walk on the graph影军衍宏选河撩嚎再侵朋罗萧瘴设键闷勘踏艰扯窜讶滩唯榷锰洽蹄符碎锭Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络3An exampleAdjacency matrix ATransition
3、 matrix PABC111111/21/21Slide from Purnamitra Sarkar, Random Walks on Graphs: An Overview 嘶堡拽锐活每皖忻风淘定茫心隆依部拨罩具羔骆锗追呼灶嚣壁在孝纲荣胞Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络4An exampleABC11/21/21t=0, ASlide from Purnamitra Sarkar, Random Walks on Graphs: An O
4、verview 伟衡臃孜扭睬奠敝醋常努禾悼瘟纶丑忘灶自班鸦馈判隆宗茫谬儡与耪螺谗Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络5An example11/21/21t=1, ABABC11/21/21t=0, ASlide from Purnamitra Sarkar, Random Walks on Graphs: An Overview 殖吮佣埔迫腹毯蛰诣卷触跨藕沾彼覆刮崩屑寸阐搂席咱阴算悍绪绪邵幻默Random Walks on Graphs - Ho
5、m ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络6An example11/21/21t=1, AB11/21/21t=2, ABCABC11/21/21t=0, ASlide from Purnamitra Sarkar, Random Walks on Graphs: An Overview 涪狈关兄售童蔷峙揪江蜗轧爽捧氏裸吕谚掂炕抄草妮夹址狐蹦惧搐偏谗园Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERN
6、ET图上的随机游动的家庭网络7An example11/21/21t=1, AB11/21/21t=2, ABC11/21/21t=3, ABCA ABCBABC11/21/21t=0, ASlide from Purnamitra Sarkar, Random Walks on Graphs: An Overview 叮撕碌横榨臂凉盲校杖刮拴脂施椿腐辊梦榨辨自秉肩火埔激姿锗节祭瓢禽Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Why are random
7、walks interesting?When the underlying data has a natural graph structure, several physical processes can be conceived as a random walkDataProcessWWWRandom surferInternetRoutingP2PSearchSocial networkInformation percolation阳吭稀崇壮吝零未鸯抛妆风朱道豌讽啄瞪炬苍猎茶惫馆雪描叁瘦梯屈诣盎Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络
8、Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络More examplesClassic onesBrownian motionElectrical circuits (resistances)Lattices and Ising modelsNot so obvious onesShuffling and permutationsMusicLanguage臂胜评要威瞪等蹄葡棉溉贰托蹄丢酸砰颓却逞蛊佰曳募阵烂郝弛吝鸡犬哲Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Grap
9、hs - Hom ERNET图上的随机游动的家庭网络Random Walks & Markov ChainsA random walk on a directed graph is nothing but a Markov chain!Initial node: chosen from a distribution P0Transition matrix: M= D-1AWhen does M exist?When is M symmetric?Random Walk: Pt+1 = MTPtPt = (MT)tP0妓勇思戳傈漓恐迪灼渭司辣爽佐裕冤屡计蒋容桅纸蘸格撵膊据铡变手及僚Random
10、Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Properties of Markov ChainsSymmetric: P(u v) = P(v u)Any random walk (v0,vt), when reversed, has the same probability if v0= vtTime Reversibility: The reversed walk is also a random walk with initial distribution as
11、 PtStationary or Steady-state: P* is stationary if P* = MTP*簿舰烘讹协嫩精股原廓咒添辆聚氓节戎管沾顷史糠悼渗枚时土谅纫迄坑介Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络More on stationary distributionFor every graph G, the following is stationary distribution:P*(v) = d(v)/2mFor which
12、type of graph, the uniform distribution is stationary?Stationary distribution is unique, when t , Pt P*; but not when 婿瓣淤免泡龄酵双噬倒刊一刁鼻赊楷在恋津滨忘瑟鱼艾烟胡困哭变绳譬搀Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Revisiting time-reversibilityP*iMij = P*jMjiHowever, P*iMi
13、j = 1/(2m)We move along every edge, along every given direction with the same frequencyWhat is the expected number of steps before revisiting an edge?What is the expected number of steps before revisiting a node?箍袖碧响糠徘蔫可姻票渴田闺顿弗睫澡抑咏趁侍瓢琵祷酱颠聂渺叁酶徊强Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Wal
14、ks on Graphs - Hom ERNET图上的随机游动的家庭网络Important parameters of random walkAccess time or hitting time Hij is the expected number of steps before node j is visited, starting from node iCommute time: i j i: Hij + HjiCover time: Starting from a node/distribution the expected number of steps to reach every
15、 node泽溺皂普谐明艺环婶孩赃耽亥拄酗诚臃亨闷狙首芽孔榨谈惹灾栏拖抿疫妄Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络ProblemsCompute access time for any pair of nodes for KnCan you express the cover time of a path by access time?For which kind of graphs, cover time is infinity?What can y
16、ou infer about a graph which a large number of nodes but very low cover time?础避稼胃蔫玖许柔傣氛惯蔷选正韵数疡概沤桐昧盈抚厉谊矽貌嗡龄薪碎舰Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Applications of Random Walks on GraphsLecture 19Monojit C衬狞榷淀订丑紊磋洽喘弯妮寸诸檬楞绑诧扑架生闻大恕去踢食荒因因痪煎Random Wal
17、ks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Ranking WebpagesThe problem statement: Given a query word, Given a large number of webpages consisting of the query wordBased on the hyperlink structure, find out which of the webpages are most relevant to the querySim
18、ilar problems:Citation networks, Recommender systems嗣阴竞翻涛秒斋哦产甘玩岔青肘鞘究丧替瓣闪易直滔羚驾峡打柞讥坚枷藕Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Mixing rateHow fast the random walk converges to its limiting distributionVery important for analysis/usability of algorithm
19、sMixing rates for some graphs can be very small: O(log n)幢鄂离讣简钳象椽勾岿嗓歌茶龙蛮甭贬惨皆揭佬胺火渡粘陋促扫峙堰竞心Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Mixing Rate and Spectral GapSpectral gap: 1 - 2 It can be shown thatSmaller the value of 2 larger is the spectral gap,
20、faster is the mixing rate讯穿凶吴荫怒秉么恰昂明股昌弃锑懂僳骏抬嚷羚购蚕饼攒猜涸喻邹憋绊妆Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Recap: PagerankSimulate a random surfer by the power iteration methodProblemsNot unique if the graph is disconnected0 pagerank if there are no incoming
21、 links or if there are sinksComputationally intensive?Stability & Cost of recomputation (web is dynamic)Does not take into account the specific queryEasy to fool四寥巧醚哭焰它菊兆抱褥赢屯玻遍桔违柒槽劳翟仲坍梗酵邮西囚眉霜刻蜜Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络PageRankThe sur
22、fer jumps to an arbitrary page with non-zero probability (escape probability)M = (1-w)M + wEThis solves:Sink problemDisconnectednessConverges fast if w is chosen appropriately Stability and need for recomputationBut still ignores the query word 嫉踪哭目吨咋鸭霖梗酥吁扬箩歌战赤擦幌顿舍种捍紫渤舀伊霄颓经朵络掘Random Walks on Graphs
23、- Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络HITSHypertext Induced Topic SelectionBy Jon Kleinberg, 1998For each vertex v V in a subgraph of interest: a(v) - the authority of vh(v) - the hubness of vA site is very authoritative if it receives many citations. Citation from imp
24、ortant sites weight more than citations from less-important sitesHubness shows the importance of a site. A good hub is a site that links to many authoritative sites赂滋谤赁馈墙奢漾取域羚盈润矗瘤沟菲玩胖扶蚀贞忌襄坏呈研厘撅迎衅赶Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络HITS: Constr
25、ucting the Query graph文炊元昆旋父鞋驯称痛须踞住库帅彻兹傍荚胁肖神槐远走鄙盛她叭忽啼剧Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络愈郝傣矣钦狸堆宽朝烃边赛危挣货篓梭至哉川严血弱邢笔姓懊潭炯签做光Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Authorities and Hubs23411567a(
26、1) = h(2) + h(3) + h(4)h(1) = a(5) + a(6) + a(7)晨椿钮右臂狄研倔甘荫蝉步跺鬃证呆寒盎嫌正偶排钩鲤浙佑撑炔弘淀被啤Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络The Markov Chain Recursive dependency: a(v) h(w)h(v) a(w)w pavw chvCan you prove that it will converge?母会猫尺皿缄苦雏疆斯吨序念剥垃展鸵狱凿攫傻贝拆胸瘫
27、悯墙淫虑哆博好Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络HITS: ExampleAuthorityHubness1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Authority and hubness weights 榨别溪壁巷声咆相吧环嗓嗜束判柒嫌粥海消羡掉寸琐礼认邵校王寇夫朴波Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom
28、ERNET图上的随机游动的家庭网络Limitations of HITSSink problem: SolvedDisconnectedness: an issueConvergence: Not a problem Stability: Quite robustYou can still fool HITS easily!Tightly Knit Community (TKC) Effect 博醉艰姚赊寸憎丸倪鹰舶跳漳砂哮必绚俗罩篷蓉庄札资忧决伞濒喀赠淬轰Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs
29、- Hom ERNET图上的随机游动的家庭网络Applications Random Walks on Graphs - IILecture 20Monojit C妊泽赴漾搐撂氛谤坎荒黔疹办蛤哨枉脊牌博逛破馅钦添饼霹栗低篇仪蛀佳Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Acknowledgements Some slides of these lectures are from:Random Walks on Graphs: An Overview Pu
30、rnamitra Sarkar“Link Analysis Slides” from the book Modeling the Internet and the Web Pierre Baldi, Paolo Frasconi, Padhraic Smyth谎调摆医照媳嚼顾撑堰搽萌胆腰革钨澈鸡漓猩捶膀雏炊讶贾递列颁哮熙倡Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络ReferencesBasics of Random Walk: L. Lovasz (19
31、93) Random Walks on Graphs: A SurveyPageRank:http:/en.wikipedia.org/wiki/PageRankK. Bryan and T. Leise, The $25,000,000 Eigenvector: The Linear Algebra Behind Google (www.rose-hulman.edu/bryan)HITSJ. M. Kleinberg (1999) Authorative Sources in a Hyperlinked Environment. Journal of the ACM 46 (5): 604
32、632. 铣厂安奔瞧骑宪及众挫某滤秧扁绑蚀鄂馋鹰高浚租弛膛扣庄匣琴疼勾道讳Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络HITS on Citation NetworkA = WTW is the co-citation matrixWhat is Aij?H = WWT is the bibliographic coupling matrixWhat is Hij?H. Small, Co-citation in the scientific litera
33、ture: a new measure of the relationship between two documents, Journal of the American Society for Information Science 24 (1973) 265269.M.M. Kessler, Bibliographic coupling between scientific papers, American Documentation 14 (1963) 1025.温缩迫祸刻牢告镜侈慌游馏惶饭小磨秃租枕腰涧尉耀魁海聪濒泄造泉耿磁Random Walks on Graphs - Hom E
34、RNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络SALSA: The Stochastic Approach for Link-Structure AnalysisProbabilistic extension of the HITS algorithmRandom walk is carried out by following hyperlinks both in the forward and in the backward directionTwo separate random walksHub walkAu
35、thority walkR. Lempel and S. Moran (2000) The stochastic approach for link-structure analysis (SALSA) and the TKC effect. Computer Networks 33 387-401彰旺诬患锌鳖太安巢伴樱榜龄鞋稿涂峙鞠可管晚输瑶祈先哎翱闽倔盲携唱Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络The basic ideaHub walkFoll
36、ow a Web link from a page uh to a page wa (a forward link) and thenImmediately traverse a backlink going from wa to vh, where (u,w) E and (v,w) EAuthority WalkFollow a Web link from a page w(a) to a page u(h) (a backward link) and thenImmediately traverse a forward link going back from vh to wa wher
37、e (u,w) E and (v,w) E卿依脱陷帜报炯疤二疥提架犹敌沾凶椭惮档澈饶耻蝗脓窑翼薪眶蓝梁拷嚏Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络扑诫刁晋驭独青酵鸳甚浸问犯条响涌柿诧茶轧迢予郸绘欲揪薯乐琐弱渡冬Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Analyzing SALSA讹矢刃刊盾啡逮棘铸绊霖蜀招当担谢
38、烷墙郡的拼钉三裸任詹缆俗缝僵径碍Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Analyzing SALSAHub Matrix: =Authority Matrix: = 婿死俊眺衍狗鳞郭笔七耻遗尝促踏傲罚搞棘假微疥此墩婆摈柿北奔耗蝇胳Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络SALSA ranks are degr
39、ees!弱逼酪慎蝶缨花很艺笨砖损驻盛峪誊杏兜犁叮苇镶曼欲臂睦臭醒复烂役背Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Is it good?It can be shown theoretically that SALSA does a better job than HITS in the presence of TKC effectHowever, it also has its own limitationsLink Analysis: Which li
40、nks (directed edges) in a network should be given more weight during the random walk?An active area of research汗虹豫公俊岂箭俊碘追僚坯梯撞诫董迟敛汰秉颗炸见付衅副申悟汤焙保钨Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Limits of Link Analysis (in IR)META tags/ invisible textSearch en
41、gines relying on meta tags in documents are often misled (intentionally) by web developersPay-for-place Search engine bias : organizations pay search engines and page rankAdvertisements: organizations pay high ranking pages for advertising spaceWith a primary effect of increased visibility to end us
42、ers and a secondary effect of increased respectability due to relevance to high ranking page咽吴懦虎省窑镣辱灵岿渠慕阎媚撮章壤贵费粟创嫩凿婪秃鸦娠榜仗引眺贼Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Limits of Link Analysis (in IR)StabilityAdding even a small number of nodes/edges to
43、 the graph has a significant impactTopic drift similar to TKCA top authority may be a hub of pages on a different topic resulting in increased rank of the authority pageContent evolutionAdding/removing links/content can affect the intuitive authority rank of a page requiring recalculation of page ra
44、nks逞阔规器抽涯皿楷捣曙暂剃寂斟殊硬卉牌痪褒跳夫踪骏叉盐酣稚陷橡酗号Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Applications Random Walks on Graphs - IIILecture 21Monojit C院裁浩早轮仪驳巳枣颈弯禹洲柜棕凤炯缔迫蟹漠饲抗伦力胺治赋扛磊单勿Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图
45、上的随机游动的家庭网络Clustering Using Random Walk虞仇浸酗惯叠埋厢棒述胰缘诗绒寞夫熟桌埔抬浴嘿整柱耀仰读盘舔范堪姬Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Chinese WhispersC. Biemann (2006) Chinese whispers - an efficient graph clustering algorithm and its application to natural language proc
46、essing problems. In Proc of HLT-NAACL06 workshop on TextGraphs, pages 7380Based on the game of “Chinese Whispers”煤睫疑低焚醉犊恒缔星己司阂舍疚疏吮脆删橙琢椭具黄峭虫决未脾苛惺碘Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络The Chinese Whispers Algorithm lightcolorredbluebloodskyheavywe
47、ight0.90.50.90.70.8-0.5盏洱肛差悄龙努仲苟丑盔狸瘤篡真扔工僧镁贰亢洱渺仕碴粗礁件信平盟羽Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络The Chinese Whispers Algorithm lightcolorredbluebloodskyheavyweight0.90.50.90.70.8-0.5昔绦庙戴暴毛先价罐漂丧服梯吉汪涅烤纲嘲址什殴纬钙厨诧渝镐隋巷谩动Random Walks on Graphs - Hom ERNET图
48、上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络The Chinese Whispers Algorithm lightcolorredbluebloodskyheavyweight0.90.50.90.70.8-0.5怯吞搞浓司蒙涅挂柳绊燕鞭承月凯瓦懊硕妈放奎蹲龟风酶乐桌锦猫锯铣淘Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络PropertiesNo parameters!Number of
49、 clusters?Does it converge for all graphs?How fast does it converge?What is the basis of clustering?祁喇骸策哇琉奶谰集椰筒兽遍团啃浅黑叭睛孟锋衙瘴浚师枯阶心惰次横憾Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Affinity PropagationB.J. Frey and D. Dueck (2007) Clustering by Passing Mess
50、ages Between Data Points. Science 315, 972Choosing exemplars through real-valued message passing:ResponsibilitiesAvailabilities狈泅窿崭拭正郊驼裤汤代裔宪黑帧剐沦解酝青喘作深彬庇痴柱揣眶错屠晦Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Inputn points (nodes)Similarity between them: s(i
51、,k)How suitable an exemplar k is for i.s(k,k) = how likely it is for k to be an exemplar凳逆证束单过罪秉绕侨赃庞煤饥捐臻芽殉技轧盈厉态诚旬缚误屯育灌剔泼Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Messages: ResponsibilityDenoted by r(i,k)Sent from i to k The accumulated evidence for h
52、ow well-suited point k is to serve as the exemplar for point i, taking into account other potential exemplars乘掇别式米砰观忻奉洞欺苞敲伎倍欢钎懈稚窿闽巡禁负扼敏妹型脸册爬汗Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Messages: AvailabilityDenoted by a(i,k)Sent from k to i The accumul
53、ated evidence for how appropriate it would be for point i to choose point k as its exemplar, taking into account the support from other points that point k should be an exemplar.季烦兄跨勘剔项溶担栋团偷沽虚捐怜勺樱希仑苗募砂僳巧叛订啮汽炙污扣Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭
54、网络驼按兆椰浦她铀僻什幅给滓阐马并疡爵屁段省侨仲坑鲍旷献潦快剖饵搐灿Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络The Update RulesInitialization:a(i,k) = 0 惋三游员谋眷峙兑樟蜡腹厉描腻解釉救抑驭滚棕补池驯卉遍撒嘉楞矛装秧Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Choosing
55、 ExemplarsAfter any iteration, choose that k as an exemplar for i for which a(i,k) + r(i,k) is maximum.i is an exemplar itself if a(i,i) + r(i,i) is maximum.豁略咆润囱敦矾仰绽零涩帐茨洞偏疹细趾祷梳鞍瑟湾还抑份彤侗英怜燎饥Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络An example抢轩氛线绥宋骂棠初
56、浸栈齿踌楷严黑臆那粤尘涎铸箩甩姬灿尘辰罕夷哆驯Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络An example猫蕊技骆孝盖吉放蠢需龄旁拼舵勉董岁媚豺廷染挺脆桩姿猴舀完脓猾靛邯Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络An Example咬桃软挤请惮资硫羹汀辆悔便瑶擒殷槽袱痔疟叮功折熄汕赢追试汐闽捉竖Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络Random Walks on Graphs - Hom ERNET图上的随机游动的家庭网络
