JournalofComplexNetworks(2015)3,84–112
doi:10.1093/comnet/cnu015
AdvanceAccesspublicationon29April2014
Topologymanipulationsforspeedingbetweennesscentralitycomputation
R.Puzis andY.Elovici
DepartmentofInformationSystemsEngineeringandTelekomInnovationLaboratoriesatBen-Gurion
UniversityoftheNegev,Beer-Sheva,Israel Correspondingauthor:puzis@bgu.ac.il
P.ZilbermanandS.Dolev
DepartmentofComputerScienceandTelekomInnovationLaboratoriesatBen-GurionUniversityof
theNegev,Beer-Sheva,Israel
and
U.Brandes
DepartmentofComputerandInformationScience,UniversityofKonstanz,Konstanz,Germany
Editedby:ChristopherMoore
[Receivedon27November2013;acceptedon2April2014]
Weproposeandevaluatetwocomplementaryheuristicstospeedupexactcomputationoftheshortest-pathbetweennesscentrality(BC).BothheuristicsarerelativelysimpleadaptationsofthestandardalgorithmforBC.Consequently,theygeneralizethecomputationofedgebetweennessandmostothervariants,andcanbeusedtofurtherspeedupbetweennessestimationalgorithms,aswell.Inthe rstheuristic,structurallyequivalentverticesarecontractedbasedontheobservationthattheyhavethesamecentralityandalsocontributeequallytothecentralityofothers.Inthesecondheuristic,we rstapplyalinear-timebetweennessalgorithmontheblock-cut-pointtreeandthencomputetheremainingcontribu-tionsseparatelyineachbi-connectedcomponent.Experimentsonavarietyoflargegraphsillustratetheef ciencyandcomplementarityofourheuristics.
Keywords:structuralanalysisofnetworks;betweennesscentrality;topologyreduction.
1.Introduction
Whilevariouskindsofnetworkrepresentationsarestudiedinavarietyofdisciplines[1],centralityindicescapturingthestructuralimportanceofnodesandedgesareanessentialtoolacrossallsubstantivedomains.Somecentralityindicesaretrivialtocompute,butothersrequiremoreinvolvedalgorithms.Inthispaper,weareinterestedincentralityindicesbasedonshortestpaths,andshortest-pathbetweennesscentrality(BC)inparticular[2,3].Shortest-pathBCisconsideredtobeagoodapproximationforthequantityofinformationpassingthroughavertexincommunicationnetworks[4].Infact,theBCofverticeswasusedin[5]tode neacongestionfreeroutingstrategy.TheBCofedgeswasusedin[6,7]toidentifycommunitiesinsocialandbiologicalnetworks.Algorithmstocomputeshortest-pathBCtypicallyinvolveperformingalargenumberofsingle-sourceshortest-pathscomputations,andthereforedonotscalewelltothelargegraphsencounteredin,forinstance,theanalysisofdataproducedinsocio-technicalsystems.
cTheauthors2014.PublishedbyOxfordUniversityPress.Allrightsreserved.Downloaded from doc.guandang.net by Richard Langer on March 19, 2015
热门文档