Betweenness Centrality of Sets of Vertices in Graphs: which Vertices to Associate

Betweenness centrality of a set of vertices can be seen as a measure of the control of flow of information that the set has within a network. We introduce the notion of saturated betweenness centrality set, which is defined as a set whose betweenness centrality will not increase by adding more members, but will decrease if any of its members is removed. We examine various properties of saturated betweenness centrality sets. These findings allow us to introduce an algorithm to optimally detect associations with high control of flow of information.