1. Home
  2. Issues
  3. Volume 21, Issue 4 (2023)
  4. Flowthrough Centrality: A Stable Node Ce ...

Journal of Data Science


Flowthrough Centrality: A Stable Node Centrality Measure
Volume 21, Issue 4 (2023), pp. 696–714
Pub. online: 22 December 2022      Type: Statistical Data Science      Open accessOpen Access
Received
30 March 2022
Accepted
6 December 2022
Published
22 December 2022

Abstract

This paper introduces flowthrough centrality, a node centrality measure determined from the hierarchical maximum concurrent flow problem (HMCFP). Based upon the extent to which a node is acting as a hub within a network, this centrality measure is defined to be the fraction of the flow passing through the node to the total flow capacity of the node. Flowthrough centrality is compared to the commonly-used centralities of closeness centrality, betweenness centrality, and flow betweenness centrality, as well as to stable betweenness centrality to measure the stability (i.e., accuracy) of the centralities when knowledge of the network topology is incomplete or in transition. Perturbations do not alter the flowthrough centrality values of nodes that are based upon flow as much as they do other types of centrality values that are based upon geodesics. The flowthrough centrality measure overcomes the problem of overstating or understating the roles that significant actors play in social networks. The flowthrough centrality is canonical in that it is determined from a natural, realized flow universally applicable to all networks.

Supplementary material

 Supplementary Material
Code: The code for this research consists of approximately 160 R Markdown files. The files include R code for the results and graphics as well as data files resulting from the linear programming algorithm in (4), (5), and (6).

References

 
Bauguion P, Ben-Ameur W, Gourdin E (2015). Efficient algorithms for the maximum concurrent flow problem. Networks, 65(1): 56–67.
 
Bavelas A (1950). Communication patterns in task-oriented groups. Journal of the Acoustic Society of America, 22(6): 725–730.
 
Breiger RL, Pattison PE (1986). Cumulated social roles: the duality of persons and their algebras. Social Networks, 8: 215–256.
 
Dong Y, Kratz T, Matula DW, Olinick EV (2015). A compact linear programming formulation for the maximum concurrent flow problem. Networks, 65(1): 68–87.
 
DuBois C (2008). UCI Network Data Repository. University of California, Irvine, School of Information and Computer Sciences. http://networkdata.ics.uci.edu.
 
Ford L, Fulkerson DR (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8(3): 399–404.
 
Ford L, Fulkerson DR (1962). Flows in Networks. Princeton University Press, Princeton, New Jersey.
 
Freeman L (1977). A set of measures of centrality based on betweenness. Sociometry, 40: 35–41.
 
Freeman LC, Borgatti S, White DR (1991). Centrality in valued graphs: a measure of betweennes based on network flow. Social Networks, 13: 141–154.
 
Holm S (1979). A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics, 6: 65–70.
 
Knoke D, Burt R (1983). Prominence. In: Burt RS and Minor MJ (eds.), Applied Network Analysis, 195–222. Sage.
 
Krebs VE (2002). Mapping networks of terrorist cells. Connections, 24(3): 43–52.
 
Mann CF (2008). Extensions of maximum concurrent flow to identify hierarchical community structure and hubs in networks, Ph.D. thesis, Southern Methodist University.
 
Mann CF, Matula DW, Olinick EV (2008). The use of sparsest cuts to reveal the hierarchical community structure of social networks. Social Networks, 30(3): 223–234.
 
Matula DW (1985). Concurrent flow and concurrent connectivity in graphs. In: Alavi Y, Chartrand G, Lesniak-Foster L, Lick DR, and Wall CE (eds.), Graph Theory and Its Applications to Algorithms and Computer Science, 543–559. Wiley. ISBN: 0471816353
 
Matula DW, Olinick EV (2016). A network flow duality foundation for hierarchical cluster analysis. SIAM Workshop on Network Science. Boston. https://archive.siam.org/meetings/ns16/ns16_abstracts.pdf.
 
Matula DW, Shahrokhi F (1990). Sparsest cuts and bottlenecks in graphs. Discrete Applied Mathematics, 27: 113–123.
 
Nace D, Pioro M (2008). Max-min fairnes and its applications to routing and load-balancing in communication networks: a tutorial. IEEE Communications Surveys & Tutorials. 10(4): 5–17. https://doi.org/10.1109/SURV.2008.080403.
 
Nashimoto K, Wright FT (2005). Multiple comparison procedures for detecting difference in simply ordered means. Computational Statistics and Data Analysis, 48: 291–306.
 
Padgett JF, Ansell CK (1993). Robust action and the rise of the Medici, 1400–1434. American Journal of Sociology, 98(6): 1259–1319.
 
Pohlert T (2018). PMCMRplus: calculate pairewise multiple comparisons of mean rank sums extended. R package version 1.4.1.
 
R Foundation for Statistical Computing (2018). R: a language and environment for statistical computing.
 
Sabidussi G (1966). The centrality index of a graph. Psychometrika, 31: 581–603.
 
Segarra S, Ribeiro A (2014). A stable betweeness centrality measure in networks. In: 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 3859–3863. https://doi.org/10.1109/ICASSP.2014.6854324.
 
Shahrokhi F, Matula DW (1990). The maximum concurrent flow problem. Journal of the ACM, 37(2): 318–334.
 
Wikipedia (2022). Centrality.
 
Zachary WW (1977). An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 33: 452–473.

PDF XML
PDF XML

Copyright
2023 The Author(s). Published by the School of Statistics and the Center for Applied Statistics, Renmin University of China.
Open access article under the CC BY license.

Keywords
incomplete networks max-min fairness network centrality measures network hubs robustness of network measures

Metrics
since February 2021
455

Article info
views

 0

Full article
views
270

PDF
downloads

 194

XML
downloads


Share


RSS