Abstract—Betweenness centrality of a set of vertices is a measure of centrality in a graph based on the notion of geodesics between vertices. Starting from betweenness centrality of vertices a similar measure can be defined on sets of vertices which allows us to determine the control of the flow of information that these sets have within a network. We introduce the notion of saturated betweenness centrality set, as a set with a positive betweenness centrality, such that its betweenness centrality is greater than the betweenness centrality of any proper subset and is smaller or equal than the betweenness centrality of any possible superset. We examine various properties of saturated betweenness centrality sets. These findings allow us to introduce an algorithm aiming to detect sets of vertices of minimal size that have a high level of control of flow of information. We provide some experimental results run on artificial and on several real-world networks.
 

Index Terms—saturated betweenness centrality set, social networks, biological networks, network control algorithm

Cite: Cristina Maier and Dan Simovici, "Saturated Betweenness Centrality Sets of Vertices in Graphs," Journal of Advances in Information Technology, Vol. 12, No. 4, pp. 287-295, November 2021. doi: 10.12720/jait.12.4.287-295

Copyright © 2021 by the authors. This is an open access article distributed under the Creative Commons Attribution License (CC BY-NC-ND 4.0), which permits use, distribution and reproduction in any medium, provided that the article is properly cited, the use is non-commercial and no modifications or adaptations are made.