{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T11:42:55Z","timestamp":1782992575542,"version":"3.54.5"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2010,4,1]],"date-time":"2010-04-01T00:00:00Z","timestamp":1270080000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2010,4]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>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\u2014the 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\u2014the 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.<\/jats:p>\n          <jats:p>\n            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\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>m<\/jats:italic>\n            ) where\n            <jats:italic>n<\/jats:italic>\n            is the number of vertices in the network and\n            <jats:italic>m<\/jats:italic>\n            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            <jats:italic>n<\/jats:italic>\n            if we assume that the routing decisions depend solely on the target of the messages.\n          <\/jats:p>\n          <jats:p>\n            Finally, we show that a preprocessing of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>m<\/jats:italic>\n            ) time, supports computations of RBC of sequences in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>kn<\/jats:italic>\n            ) time and computations of RBC of sets in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) time, where\n            <jats:italic>k<\/jats:italic>\n            in the number of vertices in the sequence or the set.\n          <\/jats:p>","DOI":"10.1145\/1734213.1734219","type":"journal-article","created":{"date-parts":[[2010,5,4]],"date-time":"2010-05-04T14:14:06Z","timestamp":1272982446000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":141,"title":["Routing betweenness centrality"],"prefix":"10.1145","volume":"57","author":[{"given":"Shlomi","family":"Dolev","sequence":"first","affiliation":[{"name":"Ben-Gurion University of the Negev, Beer-Sheva, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuval","family":"Elovici","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Beer-Sheva, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rami","family":"Puzis","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Beer-Sheva, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2010,5,3]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"Anthonisse J. M. 1971. The rush in a directed graph. Tech. rep. BN 9\/71 Stichting Mathematisch Centrum Amsterdam The Netherlands.  Anthonisse J. M. 1971. The rush in a directed graph. Tech. rep. BN 9\/71 Stichting Mathematisch Centrum Amsterdam The Netherlands."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-4371(00)00018-2"},{"key":"e_1_2_2_4_1","first-page":"2","article-title":"Betweenness centrality in large complex networks. The","volume":"38","author":"Barth\u00e9lemy M.","year":"2004","journal-title":"Europ. Phys. J. B -- Condensed Matter"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129080"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2004.11.008"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2005.11.005"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sbi.2004.05.003"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.2001.9990249"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2007.11.001"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1368436.1368444"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.07.019"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.1999.9990219"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/316194.316229"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.2307\/3033543"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(78)90021-7"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(91)90017-N"},{"key":"e_1_2_2_18_1","volume-title":"Proceedings of the 8th Workshop on Algorithm Engineering and Experimentation (ALENEX08)","author":"Geisberger R."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.87.278701"},{"key":"e_1_2_2_20_1","unstructured":"Harary F. Norman R. and Cartwright D. 1965. Structural Models. An Introduction to the Theory of Directed Graphs. Wiley New York.  Harary F. Norman R. and Cartwright D. 1965. Structural Models. An Introduction to the Theory of Directed Graphs. Wiley New York."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0219525903000803"},{"key":"e_1_2_2_22_1","volume-title":"Proceedings of the 6th IEEE International Symposium on Network Computing and Applications (NCA","author":"Jackson A.","year":"2007"},{"key":"e_1_2_2_23_1","unstructured":"Moy J. 1998. Rfc 2328 - osfp version 2. http:\/\/www.ietf.org\/rfc\/rfc2328.txt.  Moy J. 1998. Rfc 2328 - osfp version 2. http:\/\/www.ietf.org\/rfc\/rfc2328.txt."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.64.016132"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2004.11.009"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.65.036104"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1068\/b32045"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.056709"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1365534.1365539"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89900-6_20"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1108\/10662240910927821"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1038\/35065725"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comcom.2005.07.009"},{"key":"e_1_2_2_34_1","unstructured":"Villamizar C. 2002. OSPF optimized multipath (OSPF-OMP). http:\/\/www.faster-light.net\/ospf-omp\/ospf-omp.pdf.  Villamizar C. 2002. OSPF optimized multipath (OSPF-OMP). http:\/\/www.faster-light.net\/ospf-omp\/ospf-omp.pdf."},{"key":"e_1_2_2_35_1","doi-asserted-by":"crossref","unstructured":"Wasserman S. and Faust K. 1994. Social network analysis: Methods and applications. Cambridge University Press. Cambridge England.  Wasserman S. and Faust K. 1994. Social network analysis: Methods and applications. Cambridge University Press. Cambridge England.","DOI":"10.1017\/CBO9780511815478"},{"key":"e_1_2_2_36_1","unstructured":"Yagil D. 2005. Collaborative attack on www users' anonymity. M.S. dissertation Information Systems Engeneering Ben-Gurion University of the Negev Beer-Sheva Isreal.  Yagil D. 2005. Collaborative attack on www users' anonymity. M.S. dissertation Information Systems Engeneering Ben-Gurion University of the Negev Beer-Sheva Isreal."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.73.046108"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.172501399"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1088\/0256-307X\/23\/8\/099"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1734213.1734219","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1734213.1734219","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:45:28Z","timestamp":1750250728000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1734213.1734219"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,4]]}},"alternative-id":["10.1145\/1734213.1734219"],"URL":"https:\/\/doi.org\/10.1145\/1734213.1734219","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,4]]},"assertion":[{"value":"2009-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-05-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}