Introduction to Graph Mining 图挖掘介绍ppt课件.ppt

《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