Saturated Betweenness Centrality Sets of Vertices in Graphs

—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.