欢迎来到天天文库
浏览记录
ID:59417520
大小:579.00 KB
页数:44页
时间:2020-09-19
《Introduction to Graph Mining 图挖掘介绍ppt课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、IntroductiontoGraphMiningSangameshwarPatilSystemsResearchLabTRDDC,TCS,Pune1OutlineMotivationGraphsasamodelingtoolGraphminingGraphTheory:basicterminologyImportantproblemsingraphminingFSG:FrequentSubgraphMiningAlgorithm2MotivationGraphsareveryusefulformodelingvarietyofentitie
2、sandtheirinter-relationshipsInternet/computernetworksVertices:computers/routersEdges:communicationlinksWWWVertices:webpagesEdges:hyperlinksChemicalmoleculesVertices:atomsEdges:chem.BondsSocialnetworks(Facebook,Orkut,LinkedIn)Vertices:personsEdges:friendshipCitation/co-autho
3、rshipnetworkDiseasetransmissionTransportnetwork(airline/rail/shipping)Manymore…3Motivation:GraphMiningWhatarethedistinguishingcharacteristicsofthesegraphs?Whencanwesaytwographsaresimilar?Arethereanypatternsinthesegraphs?Howcanyoutellanabnormalsocialnetworkfromanormalone?How
4、dothesegraphevolveovertime?Canwegeneratesynthetic,butrealisticgraphs?ModelevolutionofInternet?…4Terminology-IAgraphG(V,E)ismadeoftwosetsV:setofverticesE:setofedgesAssumeundirected,labeledgraphsLv:setofvertexlabelsLE:setofedgelabelsLabelsneednotbeuniquee.g.elementnamesinamol
5、ecule5Terminology-IIAgraphissaidtobeconnectedifthereispathbetweeneverypairofverticesAgraphGs(Vs,Es)isasubgraphofanothergraphG(V,E)iffVsissubsetofVandEsissubsetofETwographsG1(V1,E1)andG2(V2,E2)areisomorphiciftheyaretopologicallyidenticalThereisamappingfromV1toV2suchthateache
6、dgeinE1ismappedtoasingleedgeinE2andvice-versa6ExampleofGraphIsomorphism7Terminology-III:SubgraphisomorphismproblemGiventwographsG1(V1,E1)andG2(V2,E2):findanisomorphismbetweenG2andasubgraphofG1ThereisamappingfromV1toV2suchthateachedgeinE1ismappedtoasingleedgeinE2andvice-ver
7、saNP-completeproblemReductionfrommax-cliqueorhamiltoniancycleproblem8NeedforgraphisomorphismChemoinformaticsdrugdiscovery(~1060molecules?)ElectronicDesignAutomation(EDA)designingandproducingelectronicsystemsrangingfromPCBstointegratedcircuitsImageProcessingDataCenters/Large
8、ITSystems9OtherapplicationsofgraphpatternsProgramcontrolflowanalysisDetectionofmal
此文档下载收益归作者所有