Premium
Paths and flows for centrality measures in networks
Author(s) -
Bubboloni Daniela,
Gori Michele
Publication year - 2022
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.22088
Subject(s) - betweenness centrality , centrality , maximum flow problem , flow (mathematics) , disjoint sets , mathematics , monotonic function , combinatorics , flow network , singleton , sequence (biology) , group (periodic table) , discrete mathematics , physics , mathematical analysis , geometry , pregnancy , quantum mechanics , biology , genetics
We consider the number of paths that must pass through a subset X of vertices of a capacitated network N in a maximum sequence of arc‐disjoint paths connecting two vertices y and z . We consider then the difference between the maximum flow value from y to z in N and the maximum flow value from y to z in the network obtained from N by setting to zero the capacities of arcs incident to X . When X is a singleton, those quantities are involved in defining and computing the flow betweenness centrality and are commonly identified without any rigorous proof justifying the identification. On the basis of a deep analysis of the interplay between paths and flows, we prove that, when X is a singleton, those quantities coincide. Moreover they are both equal to the global flow that must pass through X in any maximum flow from y to z . On the other hand, we prove that, when X has at least two elements, those quantities and the global flow that must pass through X in any maximum flow from y to z may be different from each other. We next show that, by means of the considered quantities, two conceptually different group centrality measures, based on paths and flows respectively, can be naturally defined. Such group centrality measures both extend the flow betweenness centrality to groups of vertices and are proved to satisfy a desirable form of monotonicity.