Graph Element Analysis图形元素的分析.ppt

graphelementanalysis,woochanghwangdepartmentofcomputerscienceandengineeringstateuniversityofnewyorkatbuffalo,introductionrealworldnetworkscentralitiesmotivationbridgingcentralitybridgecutdiscussionfutureworks,introduction,manyrealworldsystemscanbedescribedasnetworks.socialrelationships:e.g.collaborationrelationshipsinacademic,entertainment,businessarea.technologicalsystems:ernettopology,www,ormobilenetworks.biologicalsystems:e.g.regulatory,metabolic,orinteractionrelationships.almostalloftheserealworldnetworksarescale-free.,realworldnetworks,yeastppinetwork,realworldnetworks,proteomsize(pdb),realworldnetworks,powerlawdegreedistribution:richgetrichersmallworld:asmallaveragepathlengthmeanshortestnode-to-nodepathcanreachanynodesinasmallnumberofhops,56hopsrobustness:resilientandhavestrongresistancetofailureonrandomattacksandvulnerabletotargetedattackshierarchicalmodularity:alargeclusteringcoefficienthowmanyofanodesneighborsareconnectedtoeachotherdisassortativeorassortativebiologicalnetworks:disassortativesocialnetworks:assortative,realworldnetworks,e.ravaszetal.,science,2002,realworldnetworks,proteinnetworks,metabolicnetworks,realworldnetworks,complexsystemsmaintaintheirbasicfunctionsevenundererrorsandfailures(cellmutations;internetrouterbreakdowns),realworldnetworks,robust.for3,removingnodesdoesnotbreaknetworkintoislands.veryresistanttorandomattacks,butattackstargetingkeynodesaremoredangerous.,maxclustersize,pathlength,centralities,degreecentrality:numberofdirectneighborsofnodevwheren(v)isthesetofdirectneighborsofnodev.stresscentrality:thesimpleaccumulationofanumberofshortestpathsbetweenallnodepairswherest(v)isthenumberofshortestpathspassingthroughnodev.,centralities,closenesscentrality:reciprocalofthetotaldistancefromanodevtoalltheothernodesinanetwork(u,v)isthedistancebetweennodeuandv.eccentricity:thegreatestdistancebetweenvandanyothervertex,centralities,shortestpathbasedbetweennesscentrality:ratioofthenumberofshortestpathspassingthroughanodevoutofallshortestpathsbetweenallnodepairsinanetworkstisthenumberofshortestpathsbetweennodesandtandst(v)isthenumberofshortestpathspassingonanodevoutstcurrentflowbasedbetweennesscentrality:theamountofcurrentthatflowsthroughvinanetworkrandomwalkbasedbetweennesscentrality,centralities,markovcentrality:valuesfornodesshowwhichnodeisclosertothecenterofmass.morecentralnodescanbereachedfromallothernodesinashorteraveragetime.wherethemeanfirstpassagetime(mfpt)msvinthemarkovchainandnis|r|,risagivenrootset.wherendenotesthenumberofstepstakenanddenotestheprobabilitythatthechainstartingatstatesandfirstreturnstostatetinexactlynsteps.,centralities,informationcentrality:incorporatesthesetofallpossiblepathsbetweentwonodesweightedbyaninformation-basedvalueforeachpath.wherewithlaplacianlandj=11t,andistheelementonthesthrowandsthcolumninci.itmeasurestheharmonicmeanlengthofpathsendingatavertexs,whichissmallerifshasmanyshortpathsconnectingittoothervertices.randomwalkbasedclosenesscentralityisequivalenttoinformationcentrality,centralities,eigenvectorcentrality:ameasureofimportanceofnodesinanetworkusingtheadjacencyandeigenvectormatrices.wherecivisaeigenvectorandisaneigenvalue.onlythelargesteigenvaluewillgeneratethedesiredcentralitymeasurement.hubbelindex,katzstatusindex,etc.,centralities,bargaincentraity:inbargainingsituations,itisadvantageoustobeconnectedtothosewhohavefewoptions;powercomesfrombeingconnectedtothosewhoarepowerless.beingconnectedtopowerfulpeoplewhohavemanycompetitivetradingpartnersweakensonesownbargainingpower.whereisascalingfactor,istheinfluenceparameter,aistheadjacencymatrix,andisthen-dimentionalvectorinwhicheveryentryis1.,centralities,pagerank:linkanalysisthatscoresrelativelyimportanceofwebpagesinawebnetwork.thepagerankofawebpageisdefinedrecursively;apagehasahighimportanceifithasalargenumberofincominglinksfromhighlyimportantwebpages.pagerankalsocanbeviewedasaprobabilitydistributionofthelikelihoodthatarandomsurferwillarriveatanyparticularpageatcertaintime.hypertextinducedtopicselection(hits),etc.,centralities,subgraphcentrality:accountsfortheparticipationofanodeinallsubgraphsofthenetwork.thenumberofclosedwalksoflengthkstartingandendingnodevinthenetworkisgivenbythelocalspectralmomentsk(v).,observation,scale-freenetworks,basicpropertiespowerlawdegreedistributionsmallworldrobustnesshierarchicalmodularitydisassortativeorassortativethereshouldbesomebridgingnodes/edgesbetweenmodulesinscale-freenetworksbasedontheseobservations,andwedidrecognizethebridgingnodes/edgesbyvisualinspectionofsmallexamplenetworks.findingthebridgingnodes/edges,whicharelocatingbetweenmodules,isaninterestingandimportantproblemformanyapplicationsonmanydifferentfields.(networksrobustness,pathsprotection,effectivetargetsfinding,etc.),motivation,existingmeasurementsarenotenoughforidentifyingthebridgingnodes/edges:thoseexistingindicesaredominatedbydegreeofthenodeofinterest.betweennessofanedgealsohaveastronginclinationtoattachontohighdegreenodes.hightendencyofclutteringinthecenterofthenetwork.so,itishardtodifferentiatethebridgingnodes/edgesfromotherkindsofnodes/edges.ourfocusinthisresearchistotargetvulnerableandcentralcomponentsinanetworkfromatotallydifferentpointofview.,bridge,bridgeabridgeshouldbelocatedonanimportantpath,e.g.shortestpath.abridgeshouldbelocatedbetweenmodules.theneighborregionsofabridgingnodeshouldhavelowrangeofpublicdomainamongthem.,betweennessandbridgingcoefficient,betweenness:globalimportanceofanode/edgefromshortestpathsviewpoint.bridgingcoefficient:ameasurementthatmeasuringtheextenthowwellanodeoredgeislocatedbetweenwellconnectedregions.theaverageprobabilityofleavingthedirectneighborsub-graphofanodev.,bridgingcoefficient,figure1.bridgingcoefficient,bridgingcentrality,bridgingcentralityisdefinedastheproductoftherankofthebetweennessandtherankofthebridgingcoefficient.,applicationonasyntheticnetwork,figure2.figure2aand2bshowstheresultsofbridgingandbetweennesscentralityinthesyntheticnetworkrespectively.thenetworkcontained162nodesand362edgesandwascreatedbyaddingbridgingnodestothreeindependentlygeneratedsub-networks.figure2cshowstheresultsforasyntheticnetworkwherein500nodeswereaddedtoeachsub-graphinfigure2aandcontainingthesamebridgingnodes.,applicationonwebnetworkexamples,figure3.resultsforwebnetworks:figure1aand1bshowstheresultsfortheatthenodeswiththelowestvaluesofbridgingcentralityarethe85th-100thpercentilesandarehighlightedinwhitecircles.thecolormapforthepercentilevaluesisshowninthefigure.,applicationonsocialnetworkexamples,figure4.resultsforsocialnetworks:figure2aand2bshowstheresultsforthelesmiserablecharacternetworkandphysicscollaborationnetwork,respectively.thenodeswiththehighest0-5thpercentileofvaluesforthebridgingcentralityarehighlightedinredcircles;thenodeswiththelowestvaluesofbridgingcentralityarethe85th-100thpercentilesandarehighlightedinwhitecircles.thenodescorrespondingtovaljean(v),javert(j),pontmercy(p)andcosette(c)arelabeledinfigure4a.thenodescorrespondingtorothman(r),redner(r2),dodds(d),krapivsky(k)andstanley(s)arelabeledinfigure2b.thecolormapforthepercentilevaluesisshowninthefigure.,applicationonbiologicalnetworkexamples,figure5.resultsforbiologicalnetworks:figure3aand3bshowstheresultsthecardiacarrestnetworkandyeastmetabolicnetwork,respectively.thenodescorrespondingtosrc,shcandjak2(j2)arelabeledinfigure3a.thenodeswiththehighest0-5thpercentileofvaluesforthebridgingcentralityarehighlightedinredcircles;thenodeswiththelowestvaluesofbridgingcentralityarethe85th-100thpercentilesandarehighlightedinwhitecircles.thecolormapforthepercentilevaluesisshowninthefigure.,assessingnetworkdisruption,structuralintegrityandmodularity,figure6.sequentialnoderemovalanalysisontheyeastmetabolicnetwork,assessingabilitytooccupytopologicalposition,figure7ashowsthecliqueaffiliationofthenodesdetectedbythreemetrics,thebridgingcentrality(blacksquares),degreecentrality(opencircles),betweennesscentrality(blackcircles).maximalcliqueswereidentifiedintheyeastppinetwork,andthenwemeasuredwhetherthedetectednodesforeachmetricareintheidentifiedcliquesornot.infigure7b,randombetweennessbetweendetectedcliqueswasmeasuredinthecliquegraphforeachmetric,bridgingcentrality(blacksquares),degreecentrality(opencircles),betweennesscentrality(blackcircles).figure7ccomparesthenumberofsingletonsthatweregeneratedaccordingtosequentialnodedeletionforeachmetricsuchasbridgingcentrality(dotline),degreecentrality(grayline),betweennesscentrality(blackline).thenodeswiththehighestvaluesforeachofthesenetworkmetricsweresequentiallydeletedandenumeratedthenumberofsingletonsthatwereproduced.,assessingabilitytooccupymodulatingposition,figure8.thebiologicalandthetopologicalcharacteristicsofthedirectneighborsofthenodeorderedbytwometrics,thebridgingcentrality(blackbar),betweennesscentrality(whitebar).figure6(a)showsthegeneexpressioncorrelationonthedirectneighborsofeachpercentile.figure6(b)showstheaverageclusteringcoeffcientofthenodesineachpercentile.,druggability,thenodescorrespondingtoshc,src,andjak2hadthehighest,2ndand3rdhighestbridgingcentralityvalues.thetargetofreceptorantagonistdrugssuchaslosartan,alsosignalsviasrcandshcincardiacfibroblasts(cardiacstructuraltissue).jak2activationisakeymediatorofaldosterone-inducedangiotensin-convertingenzymeexpression;thelatteristhetargetofdrugssuchascaptopril,enaprilandotherangiotensin-convertingenzymeinhibitors(relatedhighbloodpressure),druggability,c21steroidhormonemetabolismnetworkthemetaboliteswiththehighestvaluesofbridgingcentralitywere:i)corticosterone,ii)cortisol,iii)11-hydroxyprogesterone,iv)pregnenoloneand,v)21-deoxy-cortisol.corticosteroneandcortisolareproducedbytheadrenalglandsandmediatetheflightorfightstressresponse,whichincludeschangestobloodsugar,bloodpressureandimmunemodulation.,druggability,steroidbiosynthesisnetworkthemetaboliteswiththehighestvaluesofbridgingcentralitywere:i)presqualenediphosphate,ii)squalene,iii)(s)-2,3-epoxy-squalene,iv)prephytoenediphosphateand,v)phytoene.anti-fungalagents,apromisingtargetforanti-cholesteroldrugs(25)andtheanti-cholesterolemicactivity,bridgecutalgorithm,iterativegraphpartitioningalgorithmcomputebridgingcentralityforeachedgecutthehighestbridgingedgeidentifyanisolatedmoduleasaclusterifthedensityoftheisolatedmoduleisgreaterthanathreshold.,clusteringvalidation,f-measuredavies-bouldinindexwherediam(ci)isthediameterofclusterciandd(ci;cj)isthedistancebetweenclusterciandcj.so,d(ci;cj)issmallifclusteriandjarecompactandtheirscentersarefarawayfromeachother.therefore,dbwillhaveasmallvaluesforagoodclustering.,bridgecut,ta