SCAN-A-Structural-Clustering-Algorithm-for-Network

SCAN:AStructuralClusteringAlgorithmforNetworksXiaoweiXu(徐晓伟)JointWorkwithNurcanYuruk(UALR)andThomasA.J.Schweiger(Acxiom)NetworkClusteringProblemNetworksmadeupofthemutualrelationshipsofdataelementsusuallyhaveanunderlyingstructure.Becauserelationshipsarecomplex,itisdifficulttodiscoverthesestructures.Howcanthestructurebemadeclear?Statedanotherway,givensimplyinformationofwhoassociateswithwhom,couldoneidentifyclustersofindividualswithcommoninterestsorspecialrelationships(families,cliques,terroristcells).AnExampleofNetworksHowmanyclusters?Whatsizeshouldtheybe?Whatisthebestpartitioning?Shouldsomepointsbesegregated?ASocialNetworkModelIndividualsinatightsocialgroup,orclique,knowmanyofthesamepeople,regardlessofthesizeofthegroup.Individualswhoarehubsknowmanypeopleindifferentgroupsbutbelongtonosinglegroup.Politicians,forexamplebridgemultiplegroups.Individualswhoareoutliersresideatthemarginsofsociety.Hermits,forexample,knowfewpeopleandbelongtonogroup.TheNeighborhoodofaVertexvDefine()astheimmediateneighborhoodofavertex(i.e.thesetofpeoplethatanindividualknows).StructureSimilarityThedesiredfeaturestendtobecapturedbyameasurewecallStructuralSimilarityStructuralsimilarityislargeformembersofacliqueandsmallforhubsandoutliers.|)(||)(||)()(|),(wvwvwvStructuralConnectivity[1]-Neighborhood:Core:Directstructurereachable:Structurereachable:transitiveclosureofdirectstructurereachabilityStructureconnected:}),(|)({)(wvvwvN|)(|)(,vNvCORE)()(),(,,vNwvCOREwvDirRECH),(),(:),(,,,wuRECHvuRECHVuwvCONNECT[1]M.Ester,H.P.Kriegel,J.Sander,&X.Xu(KDD'97)Structure-ConnectedClustersStructure-connectedclusterCConnectivity:Maximality:Hubs:NotbelongtoanyclusterBridgetomanyclustersOutliers:NotbelongtoanyclusterConnecttolessclusters),(:,,wvCONNECTCwvCwwvREACHCvVwv),(:,,huboutlier139101178126401523Algorithm=2=0.7139101178126401523Algorithm=2=0.70.63139101178126401523Algorithm=2=0.70.750.670.82139101178126401523Algorithm=2=0.7139101178126401523Algorithm=2=0.70.67139101178126401523Algorithm=2=0.70.730.730.73139101178126401523Algorithm=2=0.7139101178126401523Algorithm=2=0.70.51139101178126401523Algorithm=2=0.70.68139101178126401523Algorithm=2=0.70.51139101178126401523Algorithm=2=0.7139101178126401523Algorithm=2=0.70.510.510.68139101178126401523Algorithm=2=0.7RunningTimeRunningtime=O(|E|)Forsparsenetworks=O(|V|)[2]A.Clauset,M.E.J.Newman,&C.Moore,Phys.Rev.E70,066111(2004).Areyoureadyforsomefootball?Givenonlythe2006scheduleofwhatschoolseachNCAADivision1Ateammetonafootballfield,whatunderlyingstructurescouldonediscover?789Contests119Division1Aschoolwhoplay:schoolsintheirconferenceschoolsinother1Aconferencesindependent1Aschools(e.g.Army)schoolsinsub-1Aconferences(e.g.Maine)ConsiderArkansas’Schedule:USCPacific10UtahStateWesternAthleticVanderbiltSECAlabamaSECAuburnSECSoutheastMissouriStateNon1AMississippiSECLouisianaMonroeSunBeltSouthCarolinaSECTennesseeSECMississippiStateSECLSUSECFloridaSECWisconsinBig10TheNetwork:The1AConference:ResultofOurAlgorithm:ResultofFastModularityAlg.[2]:[2]A.Clauset,M.E.J.Newman,&C.Moore,Phys.Rev.E70,066111(2004).ConclusionWeproposeanovelnetworkclusteringalgorithm:ItisfastO(|E|),forscalefreenetworks:O(|V|)Itcanfindclusters,aswellashubsandoutliersFormoreinformation:Seeyouinpostersessionthiseveningatposterboard#4Email:[e-mail]URL:Thankyou!