资源描述:
《WeightedGraphsandDisconnectedComponentsPatte:加权图和断开连接的组件模式》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、WeightedGraphsandDisconnectedComponentsPatternsandaGeneratorMaryMcGlohon,LemanAkoglu,ChristosFaloutsosCarnegieMellonUniversitySchoolofComputerScience2McGlohon,Akoglu,FaloutsosKDD08Ingraphsalargestconnectedcomponentemerges.Whataboutthesmaller-sizecomponents?Howdot
2、heyemerge,andjoinwiththelargeone?3McGlohon,Akoglu,FaloutsosKDD08“Disconnected”components4McGlohon,Akoglu,FaloutsosKDD08WeightededgesGraphshaveheavy-taileddegreedistribution.Whatcanwealsosayabouttheseedges?Howaretheyrepeated,orotherwiseweighted?5McGlohon,Akoglu,Fa
3、loutsosKDD08OurgoalsObserve“Next-largestconnectedcomponents”Q1.HowdoestheGCCemerge?Q2.HowdoNLCC’semergeandjoinwiththeGCC?FindpropertiesthatgovernedgeweightsQ3:Howdoesthetotalweightofthegraphrelatetothenumberofedges?Q4:Howdotheweightsofnodesrelatetodegree?Q5:Doest
4、hisrelationchangewiththegraph?Q6:Canweproduceanemergent,generativemodel66McGlohon,Akoglu,FaloutsosKDD08OutlineMotivationRelatedworkPreliminariesDataObservationsModelSummary123457McGlohon,Akoglu,FaloutsosKDD08PropertiesofnetworksSmalldiameter(“smallworld”phenomeno
5、n)[Milgram67][Leskovec,Horovitz07]Heavy-taileddegreedistribution[Barabasi,Albert99][Faloutsos,Faloutsos,Faloutsos99]Densification[Leskovec,Kleinberg,Faloutsos05]“Middleregion”componentsaswellasGCCandsingletons[Kumar,Novak,Tomkins06]8McGlohon,Akoglu,FaloutsosKDD08
6、GenerativeModelsErdos-Renyimodel[Erdos,Renyi60]PreferentialAttachment[Barabasi,Albert99]ForestFiremodel[Leskovec,Kleinberg,Faloutsos05]Kroneckermultiplication[Leskovec,Chakrabarti,Kleinberg,Faloutsos07]EdgeCopyingmodel[Kumar,Raghavan,Rajagopalan,Sivakumar,Tomkins
7、,Upfal00]“Winnersdon’ttakeall”[Pennock,Flake,Lawrence,Glover,Giles02]99McGlohon,Akoglu,FaloutsosKDD08OutlineMotivationRelatedworkPreliminariesDataObservationsModelSummary12345610McGlohon,Akoglu,FaloutsosKDD08DiameterDiameterofagraphisthe“longestshortestpath”.n1n2
8、n3n4n5n6n711McGlohon,Akoglu,FaloutsosKDD08DiameterDiameterofagraphisthe“longestshortestpath”.diameter=3n1n2n3n4n5n6n712McGlohon,Akoglu,FaloutsosKDD08DiameterDi