Notice: file_put_contents(): Write of 158488 bytes failed with errno=28 No space left on device in /opt/frankenphp/design.onmedianet.com/app/src/Arsae/CacheManager.php on line 36

Warning: http_response_code(): Cannot set response code - headers already sent (output started at /opt/frankenphp/design.onmedianet.com/app/src/Arsae/CacheManager.php:36) in /opt/frankenphp/design.onmedianet.com/app/src/Models/Response.php on line 17

Warning: Cannot modify header information - headers already sent by (output started at /opt/frankenphp/design.onmedianet.com/app/src/Arsae/CacheManager.php:36) in /opt/frankenphp/design.onmedianet.com/app/src/Models/Response.php on line 20
Routing betweenness centrality | Journal of the ACM

research-article

Routing betweenness centrality

Authors:

Rami PuzisAuthors Info & Claims

Journal of the ACM (JACM), Volume 57, Issue 4

Article No.: 25, Pages 1 - 27

https://doi.org/10.1145/1734213.1734219

Published: 03 May 2010 Publication History

Abstract

Betweenness-Centrality measure is often used in social and computer communication networks to estimate the potential monitoring and control capabilities a vertex may have on data flowing in the network. In this article, we define the Routing Betweenness Centrality (RBC) measure that generalizes previously well known Betweenness measures such as the Shortest Path Betweenness, Flow Betweenness, and Traffic Load Centrality by considering network flows created by arbitrary loop-free routing strategies.

We present algorithms for computing RBC of all the individual vertices in the network and algorithms for computing the RBC of a given group of vertices, where the RBC of a group of vertices represents their potential to collaboratively monitor and control data flows in the network. Two types of collaborations are considered: (i) conjunctive—the group is a sequences of vertices controlling traffic where all members of the sequence process the traffic in the order defined by the sequence and (ii) disjunctive—the group is a set of vertices controlling traffic where at least one member of the set processes the traffic. The algorithms presented in this paper also take into consideration different sampling rates of network monitors, accommodate arbitrary communication patterns between the vertices (traffic matrices), and can be applied to groups consisting of vertices and/or edges.

For the cases of routing strategies that depend on both the source and the target of the message, we present algorithms with time complexity of O(n²m) where n is the number of vertices in the network and m is the number of edges in the routing tree (or the routing directed acyclic graph (DAG) for the cases of multi-path routing strategies). The time complexity can be reduced by an order of n if we assume that the routing decisions depend solely on the target of the messages.

Finally, we show that a preprocessing of O(n²m) time, supports computations of RBC of sequences in O(kn) time and computations of RBC of sets in O(n³n) time, where k in the number of vertices in the sequence or the set.

Supplementary Material

Code (rbcsupplementarymaterial.zip)

Python implementation of the published algorithms (unrefereed material)

Download
66.79 KB

References

[1]

Anthonisse, J. M. 1971. The rush in a directed graph. Tech. rep. BN 9/71, Stichting Mathematisch Centrum, Amsterdam, The Netherlands.

[2]

Barabasi, A.-L., and Albert, R. 1999. Emergence of scaling in random networks. Science 286, 509--512.

[3]

Barabasi, A.-L., Albert, R., and Jeong, H. 2000. Scale-free characteristics of random networks: the topology of the world-wide web. Phys. A 281, 69--77.

[4]

Barthélemy, M. 2004. Betweenness centrality in large complex networks. The Europ. Phys. J. B -- Condensed Matter 38, 2 (Mar.), 163--168.

[5]

Bollobas, B., and Riordan, O. 2003. Robustness and vulnerability of scale-free random graphs. Internet Math. 1, 1, 1--35.

[6]

Borgatti, S. P. 2005. Centrality and network flow. Social Netw. 27, 55--71.

[7]

Borgatti, S. P., and Everett, M. G. 2006. A graph-theoretic perspective on centrality. Social Netw. 28, 4 (Oct.), 466--484.

[8]

Bork, P., Jensen, L. J., von Mering, C., Ramani, A. K., Lee, I., and Marcotte, E. M. 2004. Protein interaction networks from yeast to human. Curr. Opin. Struct. Biol. 14, 3 (Jun.), 292--299.

[9]

Brandes, U. 2001. A faster algorithm for betweenness centrality. Math. Soc. 25, 2, 163--177.

[10]

Brandes, U. 2008. On variants of shortest-path betweenness centrality and their generic computation. Social Netw. 30, 2, 136--145.

[11]

Cantieni, G. R., Iannaccone, G., Barakat, C., Diot, C., and Thiran, P. 2006. Reformulating the monitor placement problem: optimal network-wide sampling. In Proceedings of the ACM CoNEXT Conference (CoNEXT'06). ACM, New York, 1--12.

Digital Library

[12]

Dolev, S., Elovici, Y., Puzis, R., and Zilberman, P. 2009. Incremental deployment of network monitors based on group betweenness centrality. Inf. Proc. Lett. 109, 20, 1172--1176.

Digital Library

[13]

Everett, M. G., and Borgatti, S. P. 1999. The centrality of groups and classes. Math. Soc. 23, 3, 181--201.

[14]

Faloutsos, M., Faloutsos, P., and Faloutsos, C. 1999. On power-law relationships of the internet topology. SIGCOMM Comput. Comm. Rev. 29, 4, 251--262.

Digital Library

[15]

Freeman, L. C. 1977. A set of measures of centrality based on betweenness. Sociometry 40, 1, 35--41.

[16]

Freeman, L. C. 1979. Centrality in social networks conceptual clarification. Social Netw. 1, 215--239.

[17]

Freeman, L. C., Borgatti, S. P., and White, D. R. 1991. Centrality in valued graphs: A measure of betweenness based on network flow. Social Netw. 13, 2 (Jun.), 141--154.

[18]

Geisberger, R., Sanders, P., and Schultes, D. 2008. Better approximation of betweenness centrality. In Proceedings of the 8th Workshop on Algorithm Engineering and Experimentation (ALENEX08). SIAM, Philadelphia, PA.

[19]

Goh, K.-I., Kahng, B., and Kim, D. 2001. Universal behavior of load distribution in scale-free networks. Phys. Rev. Lett. 87, 27 (Dec.), 278701.

[20]

Harary, F., Norman, R., and Cartwright, D. 1965. Structural Models. An Introduction to the Theory of Directed Graphs. Wiley, New York.

[21]

Holme, P. 2003. Congestion and centrality in traffic flow on complex networks. Adv. Complex Syst. 6, 2, 163--176.

[22]

Jackson, A., Milliken, W., Santivanez, C., Condell, M., and Strayer, W. 2007. A topological analysis of monitor placement. In Proceedings of the 6th IEEE International Symposium on Network Computing and Applications (NCA 2007). IEEE Computer Society Press, Los Alamitos, CA, 169--178.

[23]

Moy, J. 1998. Rfc 2328 - osfp version 2. http://www.ietf.org/rfc/rfc2328.txt.

[24]

Newman, M. E. J. 2001. Scientific collaboration networks. ii. shortest paths, weighted networks, and centrality. Phys. Rev. E 64, 016132.

[25]

Newman, M. E. J. 2005. A measure of betweenness centrality based on random walks. Soc. Netw. 27, 1 (Jan.), 39--54.

[26]

Pastor-Satorras, R., and Vespignani, A. 2002. Immunization of complex networks. Phys. Rev. E 65, 036104.

[27]

Porta, S., Crucitti, P., and Latora, V. 2006. The network analysis of urban streets: a primal approach. Environment and Plan. B: Planning and Design 33 5 (Sept.), 705--725.

[28]

Puzis, R., Elovici, Y., and Dolev, S. 2007a. Fast algorithm for successive computation of group betweenness centrality. Phys. Rev. E 76, 5, 056709.

[29]

Puzis, R., Elovici, Y., and Dolev, S. 2007b. Finding the most prominent group in complex networks. AI Comm. 20, 287--296.

Digital Library

[30]

Puzis, R., Klippel, M. D., Elovici, Y., and Dolev, S. 2007c. Optimization of NIDS placement for protection of intercommunicating critical infrastructures. In EuroISI. (Esbjerg, Denmark) Lecture Notes in Computer Science, Springer-Verlag, Berlin, Germany, (Esbejerg, Denmark).

Digital Library

[31]

Puzis, R., Yagil, D., Elovici, Y., and Braha, D. 2009. Collaborative attack on internet users' anonymity. Internet Res. 19, 1, 60--77.

[32]

Strogatz, S. H. 2001. Exploring complex networks. Nature 410, 268--276.

[33]

Suh, K., Guo, Y., Kurose, J., and Towsley, D. 2006. Locating network monitors: Complexity, heuristics, and coverage. Comput. Commun. 29, 1564--1577.

Digital Library

[34]

Villamizar, C. 2002. OSPF optimized multipath (OSPF-OMP). http://www.faster-light.net/ospf-omp/ospf-omp.pdf.

[35]

Wasserman, S., and Faust, K. 1994. Social network analysis: Methods and applications. Cambridge University Press., Cambridge, England.

[36]

Yagil, D. 2005. Collaborative attack on www users' anonymity. M.S. dissertation, Information Systems Engeneering, Ben-Gurion University of the Negev, Beer-Sheva, Isreal.

[37]

Yan, G., Zhou, T., Hu, B., Fu, Z.-Q., and Wang, B.-H. 2006. Efficient routing on complex networks. Phys. Rev. E 73, 046108.

[38]

Yook, S.-H., Jeong, H., and Barabasi, A.-L. 2002. Modeling the internet's large-scale topology. Proc. Nat. Acad. Sci. 99, 21 (Oct.), 13382--13386.

[39]

Zhou, T., Liu, J.-G., and Wang, B.-H. 2006. Notes on the algorithm for calculating betweenness. Chinese Phys. Lett. 23, 2327--2329.

Cited By

Kemgne MTsemogne OKamhoua C(2026)Shapley value to rank vulnerabilities on attack graphs: Applications to cyberdeceptionJournal of Dynamics and Games10.3934/jdg.202501613(130-157)Online publication date: 2026
https://doi.org/10.3934/jdg.2025016
Li PLiu YSu JYu B(2025)ROVReco: An ROV deployment recommendation approach with GNN based on routing betweennessComputer Networks10.1016/j.comnet.2025.111588271(111588)Online publication date: Oct-2025
https://doi.org/10.1016/j.comnet.2025.111588
Yong NNi SShen S(2025)A method of characterizing the impact of traffic load on metro system from the control centralityJournal of Safety Science and Resilience10.1016/j.jnlssr.2025.01.0016:3(100192)Online publication date: Sep-2025
https://doi.org/10.1016/j.jnlssr.2025.01.001
Show More Cited By

Index Terms

Routing betweenness centrality

Recommendations

Effective co-betweenness centrality computation
WSDM '14: Proceedings of the 7th ACM international conference on Web search and data mining

Betweenness centrality of vertices is essential in the analysis of social and information networks, and co-betweenness centrality is one of two natural ways to extend it to sets of vertices. Existing algorithms for co-betweenness centrality computation ...
An efficient algorithm for approximate betweenness centrality computation
CIKM '13: Proceedings of the 22nd ACM international conference on Information & Knowledge Management

Betweenness centrality is an important centrality measure widely used in social network analysis, route planning etc. However, even for mid-size networks, it is practically intractable to compute exact betweenness scores. In this paper, we propose a ...
Finding k-highest betweenness centrality vertices in graphs
WWW '14 Companion: Proceedings of the 23rd International Conference on World Wide Web

The betweenness centrality is a measure for the relative participation of the vertex in the shortest paths in the graph. In many cases, we are interested in the k-highest betweenness centrality vertices only rather than all the vertices in a graph. In ...

Comments

View Issue’s Table of Contents