文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 电子/电路 > Topology manipulations for s peeding b etweenness centrality c omputation
侵权投诉

Topology manipulations for s peeding b etweenness centrality c omputation

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

第1页

TOP相关主题

你可能喜欢

热门文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email