005.Web Graph&Link Analysis

《005.Web Graph&Link Analysis》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、网络搜索引擎原理陈光(chenguang@bupt.edu.cn)信息与通信工程学院WebGraph&LinkAnalysis2chenguang@bupt.edu.cnWWW3chenguang@bupt.edu.cnWebGraph4chenguang@bupt.edu.cn关注的角度有向图、无向图动态，持续变化增加节点，边删除节点，边还有动态生成的节点和边（onthefly）图大小不可知，也无法定义。关注主要的连通部分时序问题变化增长率生命期(lifeexpectancy）5chenguang@bupt.edu.cn图的统计数据图的大小(Size)Totalpage

2、snumberandedgesnumberDistributionofpagespersite连通性(connectivity)NumberofconnectedcomponentsDistributionofincomingandoutgoingconnections图直径(diameter)Averageandmaximallengthoftheshortestpathbetweenanytwovertices6chenguang@bupt.edu.cnWeb的大小—网页总数图大小不可知，也无法定义估计Web图节点数的下界搜索引擎索引的网页数(crawledpages)

3、例如CNNIC中国互联网网页调查报告能更逼近真实值吗？Markandrecaptureisamethodcommonlyusedinecologytoestimatepopulationsize.Thismethodismostvaluablewhenaresearcherfailstodetectallindividualspresentwithinapopulationofinteresteverytimethatresearchervisitsthestudyarea.Othernamesforthismethod,orcloselyrelatedmethods,in

4、cludecapture-recapture,capture-mark-recapture,mark-recapture,sight-resight,mark-release-recaptureandbandrecovery.7chenguang@bupt.edu.cnCapture-RecaptureModel8chenguang@bupt.edu.cnCapture-RecaptureModelUnknownnumberoffishinalakeCatchasampleandmarkthemLetthemlooseRecaptureasampleandlookforma

5、rksEstimatepopulationsizen1=numberinfirstsample15    n2=numberinsecondsample10    n12=numberinbothsamples5    N=totalpopulationsizeassumethat    n1/N=n12/n2therefore  15/N=5/10    N=(10x15)/5=309chenguang@bupt.edu.cnWeb的大小Estimateindexedweblow-boundbyanalysisoverlapofSearchEngine(St

6、eveLawrenceandC.LeeGiles,1998*)Select6popularsearchengine,assumeindependencyoftheirindexedpagesSamplingthesearchengineswith575queries,analysisthecoverageandoverlapUseoverlaptoestimatefractionoftheindexableWeb,pa,coveredbyengineaEstimatethewholewebbythenumberofpagesindexedbyenginea10chengua

7、ng@bupt.edu.cnOverlapanalysisP(a)=na/N=n0/nbN=na*nb/n0Duringthetesttime,HotBotreportindexed110miliionpagelowerboundonthesizeoftheindexableWebof320millionpages.(1998)11chenguang@bupt.edu.cnWeb图大小——边的数目Web图十分稀疏(sparse)Averagenumberofhyperlinksperpageroughlyacons