generating a web graph

《generating a web graph》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Generatingawebgraph-ShantanuShahscs49@cornell.eduDept.ofComputerScience,CornellUniversity17thMay2005AbstractHowdowegenerateagraphaslargeandascomplexastheWorldWideWebitself?Isitpracticaltogenerateagraphonarealmachine?Whatparametersarerequiredtogeneratesuchagraphonapracticalsystem

2、?Whatresourcesarerequiredtorunsuchanalgorithm?Whatcompromisesdowemake?Thispaperdiscussesthevariouswebgraphgenerationalgorithmsanddiscussesapracticalimplementationtogenerateawebgraph.IntroductionThewebgraphWisdefinedasadirectedgraphwithwebpagesasitsnodesandthelinksbetweenthepages

3、asitsedges.Thewebgraphisahugegraphwithmorethan8billionnodes[6].Onanaverage,consideringthateverywebpagehas7.2outgoinglinks[7],thenumberoflinksismorethan57.6billion.Ourproblemistogenerateawebgraphonrealmachineswhosepropertiescloselyresemblethoseoftheactualwebgraph.Notethatwedonott

4、rytogenerateagraphwhichisindistinguishablefromtherealwebgraph.Theactualsetofpropertiessatisfiedbythegeneratedgraphdependsonthemodel.Thechoiceofmodel,inturn,dependsontheapplication.Variousmodelsofthewebgraphhavebeenproposedin[1].Therearemanyapplicationsofsuchanartificialwebgraph.

5、TheprimaryapplicationistouseitasatestdatafortestingscalabilityofthestorageandaccessmethodsusedintheWebLaboratoryproject[9].Applicationsarealsoenvisionedincriminologyandlawenforcementtoanalyzingviruspropagationpatternsandunderstandingnetworksofregulatorygenesandinteractingprotein

6、sandsoon[2],althoughthesearenotdiscussedhere.ScopeWefocusontheproblemofgeneratingawebgraphwiththefollowingconstraintsandrequirementsinmind:1.Thegenerationofthewebgraphmustbeinrealtimeandonrealmachines.Theoutputofthisprocedurewillbeusedasaninputtosomeotherprocedure;hence,wemustbe

7、abletocompletetheprocedureforgeneratingthewebgraphinalimitedtime.Bylimitedtime,wemeanthattheremustbeapredictableupperboundtothetimerequiredforgeneratingthegraph,possiblyderivedempirically.Furthermore,itmustbepracticallypossibletorunthealgorithmonphysicalmachinesintherealworld.Th

8、ememoryandprocessingpowerrequirementsforthealgo