网络搜索引擎原理005web graphamplink analysis

网络搜索引擎原理陈光(chenguang@)信息与通信工程学院WebGraph

&LinkAnalysis2chenguang@WWW3chenguang@WebGraph4chenguang@关注的角度有向图、无向图动态，持续变化增加节点，边删除节点，边还有动态生成的节点和边（onthefly）图大小不可知，也无法定义。关注主要的连通部分时序问题变化增长率Lifeexpectancy5chenguang@图的统计数据SizeTotalpagesnumberandedgesnumberDistributionofpagespersiteConnectivityNumberofconnectedcomponentsDistributionofincomingandoutgoingconnectionsDiameterAverageandmaximallengthoftheshortestpathbetweenanytwovertices6chenguang@Web的大小—网页总数图大小不可知，也无法定义WhatisthecurrentsizeoftheWeb?At2005,Googleclaimstoindexmorethan8billionpages,MSNclaimsabout5billionpages,Yahoo!atleast4billionandAsk/Teomamorethan2billion.Markandrecapture

isamethodcommonlyusedinecologytoestimatepopulationsize.Thismethodismostvaluablewhenaresearcherfailstodetectallindividualspresentwithinapopulationofinteresteverytimethatresearchervisitsthestudyarea.Othernamesforthismethod,orcloselyrelatedmethods,includecapture-recapture,capture-mark-recapture,mark-recapture,sight-resight,mark-release-recaptureandbandrecovery.7chenguang@Capture-RecaptureModel8chenguang@Capture-RecaptureModelUnknownnumberoffishinalakeCatchasampleandmarkthemLetthemlooseRecaptureasampleandlookformarksEstimatepopulationsize

n1=numberinfirstsample15

n2=numberinsecondsample10

n12=numberinbothsamples5

N=totalpopulationsize

assumethat

n1/N=n12/n2

therefore

15/N=5/10

N=(10x15)/5=309chenguang@Web的大小Estimateindexedweblow-boundbyanalysisoverlapofSearchEngine(SteveLawrenceandC.LeeGiles,1998*)Select6popularsearchengine,assumeindependencyoftheirindexedpagesSamplingthesearchengineswith575queries,analysisthecoverageandoverlapUseoverlaptoestimatefractionoftheindexableWeb,pa,coveredbyengineaEstimatethewholewebbythenumberofpagesindexedbyenginea10chenguang@OverlapanalysisP(a)=na/N=n0/nbN=na*nb/n0Duringthetesttime,HotBotreportindexed110miliionpagelowerboundonthesizeoftheindexableWebof320millionpages.(1998)Estimatedsizeofpublicindexablewebisupto11.5billionpages.(2005)11chenguang@Web图大小——边的数目Web图十分稀疏(sparse)Averagenumberofhyperlinksperpageroughlyaconstant12chenguang@Web的连通性Alargescalestudy(Altavistacrawls)revealsinterestingpropertiesofweb(AndreiBroder,1999)Studyof200millionnodes&1.5billionlinksSomepartsunreachable,OthershavelongpathsfoundBow-tieStructure13chenguang@Bow-tieComponentsStronglyConnectedComponent(SCC)CoreUpstream(IN)Corecan’treachINDownstream(OUT)OUTcan’treachcoreDisconnectedTendrils&Tubes14chenguang@ComponentPropertiesEachcomponentisroughlysamesize~50millionnodesDisconnectedcomponentsMaximalandaveragediameterisinfinite15chenguang@EmpiricalNumbersforBow-tieDiameter,maximalminimalpathlength28forSCC,500forentiregraphProbabilityofapathbetweenany2nodes~1quarter(0.24)Shortestdirectedpathbetween2nodesinSCC:16-20linksonaverage16chenguang@FeatureofWebGraphSitesizesandConnectivityfollowsapowerlawdistributionWebgraphisasmallworldgraph17chenguang@Distributionofnumber-of-links-in18chenguang@80/20原则Paretoprinciple:formanyphenomena,80%oftheconsequencesstemfrom20%ofthecauses.(VilfredoPareto)19chenguang@Powerlaw20chenguang@PowerlawAlineappearsonalog-logplotP(k)=Ck-λ

log[P(k)]=-λlog(Ck)rareeventsarenotsorare!Longtail21chenguang@PowerLawDistribution-ExamplesFromGraphstructureintheweb,(byaltavistacrawl,1999)22chenguang@ExampleswithPowerLawNetworksExamplesofnetworkswithPowerLawDistributionInternetattherouterandinter-domainlevelCitationnetworkCollaborationnetworkofactorsNetworksformedbyinteractinggenesandproteins23chenguang@SmallworldnetworkItisa‘smallworld’Millionsofpeople.Yet,separatedby“sixdegrees”ofacquaintancerelationshipsPopularizedbyMilgram’sfamousexperimentMathematicallyDiameterofgraphissmall(logN)ascomparedtooverallsizePropertyseemsinterestinggiven‘sparse’natureofgraphbut…Thispropertyis‘natural’in‘pure’randomgraphs

24chenguang@小世界网络米尔格伦连锁信实验1967年，美国哈佛大学社会心理学教授斯坦利·米尔格兰姆对这个问题做了一个著名的实验，他从内布拉斯加州和堪萨斯州招募到一批志愿者，随机选择出其中的三百多名，请他们邮寄一个信函。信函的最终目标是米尔格兰姆指定的一名住在波士顿的股票经纪人。由于几乎可以肯定信函不会直接寄到目标，米尔格兰姆就让志愿者把信函发送给他们认为最有可能与目标建立联系的亲友，并要求每一个转寄信函的人都回发一个信件给米尔格兰姆本人。出人意料的是，有六十多封信最终到达了目标股票经济人手中，并且这些信函经过的中间人的数目平均只有5个。

也就是说，陌生人之间建立联系的最远距离是6个人。1967年5月，米尔格兰姆在《今日心理学》杂志上发表了实验结果，并提出了著名的“六度分隔”假说25chenguang@小世界网络你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过六个人你就能够认识任何一个陌生人。这就是六度分割理论，也叫小世界理论几年前一家德国报纸接受了一项挑战，要帮法兰克福的一位土耳其烤肉店老板，找到他和他最喜欢的影星马龙·白兰度的关联。结果经过几个月，报社的员工发现，这两个人只经过不超过六个人的私交，就建立了人脉关系。原来烤肉店老板是伊拉克移民，有个朋友住在加州，刚好这个朋友的同事，是电影《这个男人有点色》的制作人的女儿在女生联谊会的结拜姐妹的男朋友，而马龙·白兰度主演了这部片子若每个人平均认识260人，其六度就是2606

＝1,188,137,600,000。消除一些节点重复，那也几乎复盖了整个地球人口若干多多倍。

——摘录自wikilab26chenguang@ThesmallworldofWWWEmpiricalstudyofWeb-graphrevealssmall-worldpropertyGraphgeneratedusingpower-lawmodelDiameterpropertiesinferredfromsamplingCalculationofmax.diametercomputationallydemandingforlargevaluesofn

Averagedistance(d)insimulatedweb:

d=0.35+2.06log(n)e.g.n=109,d~=1927chenguang@ImplicationsforWebLogarithmicscalingofdiametermakesfuturegrowthofwebmanageable10-foldincreaseofwebpagesresultsinonly2moreadditional‘clicks’,but…Usersmaynottakeshortestpath,mayusebookmarksorjustgetdistractedonthewayThereforesearchenginesplayacrucialrole28chenguang@SocialNetwork任何一种用于建立个体之间联系的自然现象、社会活动或技术机制都可能形成一张网“朋友关系”（对称，无向图）“知晓关系”（不对称，有向图）“文献引用关系”（不对称，有向图）

co-author关系（对称，无向图）通电话，通信病毒传染（生物、计算机）网页链接关系（不对称，有向图）还可以考虑不同的“尺度”：网站之间，城市之间，省份之间，国家之间，…29chenguang@研究这些“关系图”有什么意义？一阶指标（“入度”）知晓关系：社会知名度引用关系：认可程度“高阶指标”和一个著名人物“共同发表”论文的“距离”：越短似乎显得越“有荣誉”（例如，Erdosnumber，）仅仅是“结构”就可以带来丰富的“语义”PaulErdösErdosnumber:根据现代匈牙利数学家保罗·埃尔德什，这个最多产的数学家命名，是描述数学论文中一个作者与埃尔德什的“合作距离”的一种方式reputation,prestige,importance,…完全靠“入度”来评价可能显得比较粗燥（即这种评价模型不一定很准）认识甲的人可能和认识乙的人一样多，但认识乙的人都是些“重要人物”，于是通常应该认为乙比甲重要不仅是人，论文也是一样，被重要的文章引用的文章可能就比较重要些谁重要一些？30chenguang@知名度，声望，重要性，…31chenguang@图论、线性代数若干概念回顾图，有向图，邻接矩阵，两节点间的距离（d），图的半径（r），图的中心（c），图的连通性d(u,v)：从u到v的最短路径的长度r(G)：最大的距离d(u,v)c(G)：具有最短半径的节点矩阵（A），矩阵的转置（AT），行列式（|A|），特征值，特征向量，线性相关性32chenguang@应用举例：Co-citation分析给定一个文献的集合，希望表达这些文献两两被同时（同一篇文章）引用的情况coc[i,j]越大，表示这两篇文章的相关性越强形成文章之间的邻接矩阵E，使得E[i,j]=1当且仅当文章i引用了j；否则E[i,j]=0。这意味着，E的第j列反映文章j被引用的情况；同时引用文章i和文章j的文章数量等于E[*,i]和E[*,j]在相同的行出现1的个数。考虑到E元素的{0,1}特性，即coc[i,j]=∑E[k,i]E[k,j],k=1,2,…,n或者coc=ETEj1i33chenguang@i文章的引用矩阵Ej1ji1111coc[i,j]=∑E[k,i]E[k,j]coc[i,j]=ETEi11j1134chenguang@关于声望模型给定一个群体S，及其在上面的一个“知晓”关系R，于是定义了一个有向“关系图”G。用邻接矩阵E表示，E(i,j)=1当且仅当i“听说过”j（注意这里没有程度之分）。我们希望确定p(i)：所有个体i∈S的“声望”模型一：p(i)=∑E[k,i]，k=1,…,n，即i在G上的“入度”，亦即E的第i列的1的个数清楚、好计算；但是“不够好”模型二：p(i)=∑E[k,i]p(k)，k=1,…,n，即i的声望等于知晓他的人的声望之和清楚、显得要更“精确些”；但是，好计算吗？35chenguang@声望模型二（续）对于所有i，p(i)=∑E[k,i]p(k)，k=1,…,n也就是，记p=(p(1),p(2),…,p(n))T,p=ETp问题是：这个方程存在解吗？如果存在，如何得到？如果不存在，该怎么办？一般来讲：这个方程的非0解是不存在的！36chenguang@p=ETp的不存在例S={1,2,3},R={<1,2>,<1,3>,<2,3>}E=((0,1,1),(0,0,1),(0,0,0))ET=((0,0,0),(1,0,0),(1,1,0))不难看到：方程的成立p(1)=0p(2)=0p(3)=0一般来讲，p=ETp，意味着要求ET有特征值1，这是很难得的。12337chenguang@修改模型模型三：让i的声望等于知晓他的人的声望之和乘以一个常数（对所有i相同）p(i)=c*∑E[k,i]p(k)，k=1,…,n与模型二的关系效果上感觉应该差不多，因为是“共同的常数”，而对我们有意义的只是“相对声望”但并不完全等价!p=c*ETp38chenguang@对网页重要性的评价PageRank算法，HITS（HyperlinkInducedTopicSearch）算法都是为了利用HTML网页的链接特点，改善查询的效果当Spam页面淹没了searchengine的搜索结果页面时，除了页面内容与查询的相关性以外，页面本身的质量/重要性的作用就显现出来都是1997年左右完成的研究工作，PageRank促成了Google，HITS依然有学术上的意义。39chenguang@PageRank对每一篇网页，得到一个独立于查询词的相对“重要性”指标，将这个指标和查询匹配情况结合起来（以及其他因素），形成网页的排序。“重要性”入度？类似于前面讨论的“声望”？（模型三）从一个新的角度考虑一种模型（能说得更彻底些的）？40chenguang@“RandomWalker”模型设想有一个永不休止、在网上浏览网页的人,随机选择一个链出的链接继续访问。我们问，在稳态情况下（足够长时间后），他会正在看哪一篇网页呢？等价于：稳态情况下，每个网页v会有一个被访问的概率，p(v)，它可以作为网页的重要程度的度量我们可以合理地设想：此时到达v的概率，依赖于上一个时刻到达“链向”v的网页的概率，以及那些网页中超链的个数41chenguang@Randomwalkermodelpk+1(v)=∑E[u,v]*pk(u)/du,overu这里，du是网页u的“出度”，∑E[u,v]overuVu1u2u3u4u542chenguang@RandomWalkerModel(cont’)改写一下，成形式上和“声望”模型一样，只是矩阵L有行向量元素和为1的性质。有用吗？DanglingNode（出度为0的节点）对于这些节点，矩阵L对应着元素全0的行，元素和不为1修正：L[u,v]=1/Nifdu=043chenguang@Stochasticmatrix矩阵M，元素非负，每个行向量元素之和分别都等于1（亦称马尔科夫转移矩阵）L就是这种矩阵显然，随机矩阵的最大特征值为1，对应的特征向量是全1元素向量转置矩阵的行列式和原矩阵的行列式相等于是1也就是LT最大的特征值！44chenguang@问题不管初始值P0如何，下面这个式子都会收敛到有意义的结果吗？45chenguang@还有一点问题上述“随机浏览”模型有效的条件是：由网页形成的有向图允许通过链接关系访问到每一个网页但有两个情况是破坏这条件的图中形成“圈”(rankbounce)有入度或者出度为0的点(ranksink)因此该模型的表述通常要求所形成的图是irreducible（强连通）和aperiodic（不能有进去后出不来的圈）。46chenguang@修改模型让这浏览者每次以一定的概率（1-β）沿着超链走，以概率（β）重新随机选择一个新的起始节点这在物理意义上即总是有可能跳进入度为0的点，跳出那些“圈”。在模型表达上即为剩下来的迭代就可用poweriteration,β选在0.1和0.2之间迭代最后得到的稳定P就是PageRank（Page&Brin1997）47chenguang@HITS从设计思想来看，HITS和PageRank的一个基本区别是HITS针对具体查询、应用在查询时间，而PageRank是独立于查询的Rootset,R(q):和查询q相关的网页集合Baseset,V(q):除了R(q)外，还包括指向R(q)元素和被R(q)元素指向的网页Expandedset=V-R两个概念（直觉上有意义）AUTHORITY（权威型网页）：内容权威，质量高的网页HUB（目录型网页）：指向许多aut