lecture14.ppt

InformationNetworks GraphClusteringLecture14 Clustering GivenasetofobjectsV andanotionofsimilarity ordistance betweenthem partitiontheobjectsintodisjointsetsS1 S2 Sk suchthatobjectswithintheeachsetaresimilar whileobjectsacrossdifferentsetsaredissimilar GraphClustering Input agraphG V E edge u v denotessimilaritybetweenuandvweightedgraphs weightofedgecapturesthedegreeofsimilarityClustering Partitionthenodesinthegraphsuchthatnodeswithinclustersarewellinterconnected highedgeweights andnodesacrossclustersaresparselyinterconnected lowedgeweights mostgraphpartitioningproblemsareNPhard Measuringconnectivity Whatdoesitmeanthatasetofnodesarewellinterconnected min cut theminnumberofedgessuchthatwhenremovedcausethegraphtobecomedisconnectedlargemin cutimpliesstrongconnectivity Measuringconnectivity Whatdoesitmeanthatasetofnodesarewellinterconnected min cut theminnumberofedgessuchthatwhenremovedcausethegraphtobecomedisconnectednotalwaystrue Graphexpansion NormalizethecutbythesizeofthesmallestcomponentGraphexpansion WewillnowseehowthegraphexpansionrelatestotheeigenvalueoftheadjancenymatrixA Spectralanalysis TheLaplacianmatrixL D AwhereA theadjacencymatrixD diag d1 d2 dn di degreeofnodeiThereforeL i i diL i j 1 ifthereisanedge i j LaplacianMatrixproperties ThematrixLissymmetricandpositivesemi definitealleigenvaluesofLarepositiveThematrixLhas0asaneigenvalue andcorrespondingeigenvectorw1 1 1 1 1 0isthesmallesteigenvalue Thesecondsmallesteigenvalue Thesecondsmallesteigenvalue alsoknownasFieldervalue 2satisfiesThevectorthatminimizes 2iscalledtheFieldervector Itminimizes where FielderValue Thevalue 2isagoodapproximationofthegraphexpansion Spectralordering ThevaluesofxminimizeForweightedmatricesTheorderingaccordingtothexivalueswillgroupsimilar connected nodestogetherPhysicalinterpretation Thestablestateofspringsplacedontheedgesofthegraph Spectralpartition PartitionthenodesaccordingtotheorderinginducedbytheFieldervectorIfu u1 u2 un istheFieldervector thensplitnodesaccordingtoavaluesbisection sisthemedianvalueinuratiocut sisthevaluethatmaximizes G sign separatepositiveandnegativevalues s 0 gap separateaccordingtothelargestgapinthevaluesofuThisworksprovablywellforspecialcases Conductance ThenodeswithhighdegreearemoreimportantGraphConductanceConductanceisrelatedtotheeigenvalueofthematrixM D 1A ClusteringConductance Theconductanceofaclusteringisdefinedastheminimumconductanceoverallclustersintheclustering Maximizingconductanceseemslikeanaturalchoice butitdoesnothandlewelloutliers Aclusteringbi criterion Maximizetheconductance butatthesametimeminimizetheinter clusteredgesAclusteringC C1 C2 Cn isa c e clusteringifTheconductanceofeachCiisatleastcThetotalnumberofinter clusteredgesisatmostafractioneofthetotaledges Theclusteringproblem Problem1 Givenc finda c e clusteringthatminimizeseProblem2 Givene finda c e clusteringthatmaximizescTheproblemsareNP hard Aspectralalgorithm CreatematrixM D 1 2AFindthesecondlargesteigenvectorvFindthebestratio cut minimumconductancecut withrespecttovRecurseonthepiecesinducedbythecut Thealgorithmhasprovableguarantees Discoveringcommunities Community asetofnodesS wherethenumberofedgeswithinthecommunityislargerthanthenumberofedgesoutsideofthecommunity Min cutMax flow GivenagraphG V E whereeachedgehassomecapacityc u v asourcenodes andadestinationnodet findthemaximumamountofflowthatcanbesentfromstot withoutviolatingthecapacityconstraintsThemax flowisequaltothemin cutinthegraph weightedmin cut Solvableinpolynomialtime Aseededcommunity Thecommunityofnodeswithrespecttonodet isthesetofnodesreachablefromsinthemin cutthatcontainssthissetdefinesacommunity DiscoveringWebcommunities StartwithasetofseednodesSAddavirtualsourcesFindneighborsafewlinksawayCreateavirtualsinktFindthecommunityofswithrespecttot Amorestructuredapproach Addavirtualsourcetinthegraph andconnectallnodestot withedgesofcapacity LetSbethecommunityofnodeswithrespecttot ForeverysubsetUofSwehaveSurprisingly thissimplealgorithmgivesguaranteesfortheexpansionandtheinter communitydensity Min CutTrees GivenagraphG V E themin cuttreeTforgraphGisdefinedasatreeoverthesetofverticesV wheretheedgesareweightedthemin cutbetweennodesuandvisthesmallestweightamongtheedgesinthepathfromutov removingthisedgefromTgivesthesamepartitionasremovingthemin cutinG Lemma1 u w U U2 U1 W c W U2 c U1 U2 Lemma2 LetSbethecommunityofthenodeswithrespecttotheartificialsinkt ForanysubsetUofSwehave Lemma3 LetSbethecommunityofnodeswithrespecttot Thenwehave Algorithmforfindingcommunities AddavirtualsinkttothegraphGandconnectallnodeswithcapacity graphG Createthemin cuttreeT ofgraphG RemovetfromT Returnthedisconnectedcomponentsasclusters Effectof When istoosmall thealgorithmreturnsasinglecluster theeasythingtodoistoremovethesinkt When istoolarge thealgorithmreturnssingletonsInbetweenistheinterestingarea Wecanexplorefortherightvalueof Wecanrunthealgorithmhierarchicallystartwithsmall andincreaseitgraduallytheclustersreturnedarenested References J Kleinberg LecturenotesonspectralclusteringDanielA SpielmanandShang HuaTeng SpectralPartitioningWorks Planargraphsandfiniteelementmeshes Proceedingsofthe37thAnnualIEEEConferenceonFoundationsofComputerScience 1996 andUCBerkeleyTechnicalReportnumberUCBCSD 96 898 RaviKannan SantosVempala AdrianVetta Onclusterings good badandspectral JournaloftheACM JACM 51 3 497 515