欢迎来到天天文库
浏览记录
ID:41327772
大小:2.81 MB
页数:50页
时间:2019-08-22
《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
此文档下载收益归作者所有