On variants of shortest-path betweenness centrality and their generic computation

doi:10.1016/j.socnet.2007.11.001

Social Networks

Volume 30, Issue 2, May 2008, Pages 136-145

https://doi.org/10.1016/j.socnet.2007.11.001 Get rights and content

Abstract

Betweenness centrality based on shortest paths is a standard measure of control utilized in numerous studies and implemented in all relevant software tools for network analysis. In this paper, a number of variants are reviewed, placed into context, and shown to be computable with simple variants of the algorithm commonly used for the standard case.

Introduction

Centrality is a core concept for the analysis of social networks, and betweenness is one of the most prominent measures of centrality. It was introduced independently by Anthonisse (1971) and Freeman (1977), and measures the degree to which a vertex is in a position of brokerage by summing up the fractions of shortest paths between other pairs of vertices that pass through it. Betweenness is therefore classified as a measure of mediation in Borgatti and Everett (2006).

While some centrality indices impose requirements on the network data such as undirectedness and connectedness, Anthonisse (1971) defines betweenness on directed networks from the very beginning, and Freeman (1977) stresses applicability to disconnected networks. In this paper, we review and propose variations of the definition of betweenness that either generalize it to even more types of network data, or modify slightly the embodied notion of brokerage.

All of the variants treated in this paper, however, maintain the original model of geodesic trajectories (Borgatti, 2005), i.e., only shortest paths are considered in their definition. This excludes alternative models of transportation based on, e.g., network-flow (Freeman et al., 1991) or current-flow Newman, 2005, Brandes and Fleischer, 2005, and is due to the original motivation for writing this paper, namely to document that none of these variants poses additional algorithmic challenges, as all of them can be calculated with minor modifications of the efficient betweenness algorithm introduced in Brandes (2001).

The contribution of this paper is thus two-fold:

(1)
A compilation of shortest-path betweenness variants.
(2)
Algorithms for computing them efficiently.

As part of the first contribution we also clarify relations with other measures like stress (Shimbel, 1953) and load (Goh et al., 2001), but there will be no discussion in favor or against substantive applicability of these variant measures. The second contribution is especially valuable for software tools offering betweenness computation, since existing implementations can be adapted with little effort. In fact, most of the modifications discussed in the sequel can be combined in a single implementation. Let me stress again, however, that an evaluation of the appropriateness and usefulness of any of these variants, or their combination, for substantive network research is beyond the scope of this paper. For recent overviews of centrality measures and associated algorithms see Brandes and Erlebach (2005, Chapters 3–5) and Borgatti and Everett (2006).

In the next section, we recall the definition of shortest-path betweenness centrality and outline its efficient computation. The variations are presented in Section 3 together with corresponding modifications to the basic algorithm, and we conclude with a brief discussion.

Section snippets

Shortest-path betweenness

We will use graph-theoretic terminology neutral to interpretation. See Bollobás (1998) or Diestel (2000) for modern textbooks on graph theory. For introductions to algorithms and their analysis, see Cormen et al. (2001),Goodrich and Tamassia (2002) or Kleinberg and Tardos (2006).

Variants and their computation

We have already argued that the basic algorithm is suitable for vertex betweenness in both directed and undirected graphs. In this section, we discuss modifications that require adjustment of the basic algorithm.

Discussion

We have discussed several variants of betweenness centrality, in which either the interest is shifted, e.g., to edges, or the range of applicability is extended, e.g., to valued networks. Unlike related measures such as network-flow betweenness (Freeman et al., 1991), current-flow betweenness Newman, 2005, Brandes and Fleischer, 2005, or load (Goh et al., 2001), these do not alter the underlying model of transportation along geodesic trajectories (Borgatti, 2005).

For all these variants, small

Acknowledgements

I am grateful to Steve Borgatti, who shared ideas on distance-aware variants of betweenness and made other useful suggestions, and to Peter Sanders and two anonymous reviewers, whose comments were helpful in improving the presentation.

References (34)

S.P. Borgatti
Centrality and network flow
Social Networks
(2005)
S.P. Borgatti et al.
A graph-theoretic perspective on centrality
Social Networks
(2006)
M.G. Everett et al.
Ego network betweenness
Social Networks
(2005)
L.C. Freeman
Centrality in social networks: Conceptual clarification I
Social Networks
(1979)
L.C. Freeman et al.
Centrality in valued graphs: A measure of betweenness based on network flow
Social Networks
(1991)
R.V. Gould
Measures of betweenness in non-symmetric networks
Social Networks
(1987)
S. Lämmer et al.
Scaling laws in the spatial structure of urban road networks
Physica A
(2006)
M.E.J. Newman
A measure of betweenness centrality based on random walks
Social Networks
(2005)
D.R. White et al.
Betweenness centrality measures for directed graphs
Social Networks
(1994)
Anthonisse, J. M., October 1971. The rush in a directed graph. Tech. Rep. BN 9/71, Stichting Mathematisch Centrum, 2e...

B. Bollobás

Modern Graph Theory of Graduate Texts in Mathematics, vol. 184

(1998)

U. Brandes

A faster algorithm for betweenness centrality

Journal of Mathematical Sociology

(2001)

U. Brandes et al.

Centrality measures based on current flow

U. Brandes et al.

Centrality estimation in large networks

International Journal of Bifurcation and Chaos

(2007)

T.H. Cormen et al.

Introduction to Algorithms

(2001)

P. De et al.

Sexual network analysis of a gonorrhoea outbreak

Sexually Transmitted Infections

(2004)

Cited by (729)

TransNeT-CGP: A cluster-based comorbid gene prioritization by integrating transcriptomics and network-topological features
2024, Computational Biology and Chemistry
The local disruptions caused by the genes of one disease can influence the pathways associated with the other diseases resulting in comorbidity. For gene therapies, it is necessary to prioritize the key genes that regulate common biological mechanisms to tackle the issues caused by overlapping diseases. This work proposes a clustering-based computational approach for prioritising the comorbid genes within the overlapping disease modules by analyzing Protein-Protein Interaction networks. For this, a sub-network with gene interactions of the disease pair was extracted from the interactome. The edge weights are assigned by combining the pairwise gene expression correlation and betweenness centrality scores. Further, a weighted graph clustering algorithm is applied and dominant nodes of high-density clusters are ranked based on clustering coefficients and neighborhood connectivity. Case studies based on neurodegenerative diseases such as Amyotrophic Lateral Sclerosis- Spinal Muscular Atrophy (ALS-SMA) pair and cancers such as Ovarian Carcinoma-Invasive Ductal Breast Carcinoma (OC-IDBC) pair were conducted to examine the efficacy of the proposed method. To identify the mechanistic role of top-ranked genes, we used Functional and Pathway enrichment analysis, connectivity analysis with leave-one-out (LOO) method, analysis of associated disease-related protein complexes, and prioritization tools such as TOPPGENE and Heml2.0. From pathway analysis, it was observed that the top 10 genes obtained using the proposed method were associated with 10 pathways in ALS-SMA comorbidity and 15 in the case of OC-IDBC, while that in similar methods like SAPDSB and S2B were 4, 6 respectively for ALS-SMA and 9, 10 respectively for OC-IDBC. In both case studies, 70 % of the disease-specific benchmark protein complexes were linked to top-ranked genes of the proposed method while that of SAPDSB and S2B were 55 % and 60 % respectively. Additionally, it was found that the removal of the top 10 genes disconnect the network into 14 distinct components in the case of ALS-SMA and 9 in the case of OC-IDBC. The experimental results shows that the proposed method can be effectively used for identifying key genes in comorbidity and can offer insights about the intricate molecular relationship driving comorbid diseases.
Shortest path-based centrality metrics in attributed graphs with node-individual context constraints
2024, Social Networks
Citation Excerpt :
Geisberger et al. (2008) proposed linearly-scaled betweenness using a distance function to weigh a path based on its relative distance from a source node. Of these and further variants, which were discussed in detail by Brandes (2008), with the only exception being the linearly scaled betweenness, none of the surveyed algorithms considers a node-individual weight for the set of geodesics. Another approach originally aiming at an improved calculation of betweenness centrality was proposed by Pfeffer & Carley (2012).
Centrality measurements are a well-known method to assess the importance of actors in networks. They are easy to obtain and provide a versatile interpretability adaptable to the meaning of nodes and edges. The current centrality measurements use structural information alone. In real-world situations, however, actors and the connections between them are subject to contextual settings and can be significantly influenced by these settings. In fact, such real-world observations are often modeled using attributed networks in which contextual information can be associated as attributes to nodes and edges. However, this information is disregarded when evaluating the importance of actors in terms of network centrality measurements. Hence, this paper proposes a method for obtaining shortest path-based centrality measurements for attributed networks that exploit attribute information on nodes for shortest path calculations. We add abstracts of scientific publications to a co-publishing network and use topic models to create node-individual context constraints for shortest path calculations. This creates additional analytic opportunities and can aid in gaining a detailed understanding of complex social networks.
A centrality analysis of the Lightning Network
2024, Telecommunications Policy
Blockchain technology has a huge impact on our digital society by enabling a more decentralized economy and policy making. This decentralization is also pivotal in payment Payment channel networks (PCNs), including the Lightning Network, have emerged as a promising solution to the scalability challenges that many blockchain-based cryptocurrencies, like Bitcoin, grapple with. These PCNs, while innovative, also inherit the rigorous dependability demands of the blockchain. A pivotal aspect of this dependability is the need for a high degree of decentralization, essential for mitigating liquidity bottlenecks and on-path attacks.
Driven by this imperative, our research embarks on an empirical centrality analysis of the Lightning Network, with a keen focus on the betweenness centrality distribution of its routing system. Utilizing an extensive dataset, sourced from several millions of broadcasted messages via the gossip protocol, we introduce the TimeMachine tool, an innovative method that allows for a temporal exploration of the network’s evolution.
Our findings reveal that while the Lightning Network exhibits a commendable level of decentralization, there is a discernible skew: a limited set of nodes command a significant portion of the transactions. Alarmingly, over the past two years, the network’s centrality has surged, with the inequality, as gauged by the Gini index, rising by over 15 uptick of approximately 5 in. This research not only uncovers critical insights into the Lightning Network’s structural dynamics but also raises the question about strategies and policies that ensure its sustained decentralization in the face of evolving challenges such as security vulnerabilities, potential monopolistic tendencies, liquidity bottlenecks, the risk of transaction censorship and many more.
Global Street Experiment: A Geospatial Database of Pandemic-induced Street Transitions
2024, Landscape and Urban Planning
Street experiment is a tactical urbanism practice that involves implementing temporary changes in street use through regulatory or physical interventions, aimed at people-centric street transition. During the Covid-19 pandemic, cities worldwide implemented street experiments to accommodate the need for socially-distanced physical and commercial activities. However, we know little about the locations and urban environments of these pandemic-induced street experiments on a global scale. This knowledge gap hinders us from understanding where these experiments took place, the conditions of the neighbourhoods involved, and the factors contributing to their longevity beyond the pandemic. We thus developed a geospatial database to document the pandemic-induced street experiments (PISE Database), enabling quantitative analysis of these interventions. We mapped the locations and calculated the neighbourhood environment attributes of 539 street experiments in 333 cities. Our contributions are twofold. Firstly, we enhanced the comparability of built environment indicators between cities, thereby advancing the construction of global geospatial datasets. Specifically, we established a standardised template encompassing unified neighbourhood-level built environment indicators and methodologies, for which we devised relative values to facilitate comparisons between different cities and defined study areas using the 15-minute walking city and Urban Centre concepts. Secondly, we conducted primary analyses based on spatial and temporal visualisations of the street experiment locations and durations, shedding light on locational patterns and development trajectories during times of crisis. This global, quantitative approach complements the growing body of local and often qualitative studies. Our work improves existing global quantitative databases and provides a robust foundation for future research on tactical urbanism.
A new centrality measure based on neighbor loop structure for network dismantling
2024, Digital Communications and Networks
Nearly all real-world networks are complex networks and usually are in danger of collapse. Therefore, it is crucial to exploit and understand the mechanisms of network attacks and provide better protection for network functionalities. Network dismantling aims to find the smallest set of nodes such that after their removal the network is broken into connected components of sub-extensive size. To overcome the limitations and drawbacks of existing network dismantling methods, this paper focuses on network dismantling problem and proposes a neighbor-loop structure based centrality metric, NL, which achieves a balance between computational efficiency and evaluation accuracy. In addition, we design a novel method combining NL-based nodes-removing, greedy tree-breaking and reinsertion. Moreover, we compare five baseline methods with our algorithm on ten widely used real-world networks and three types of model networks including Erdös-Rényi random networks, Watts-Strogatz small-world networks and Barabási-Albert scale-free networks with different network generation parameters. Experimental results demonstrate that our proposed method outperforms most peer methods by obtaining a minimal set of targeted attack nodes. Furthermore, the insights gained from this study may be of assistance to future practical research into real-world networks.
Community detection in the human connectome: Method types, differences and their impact on inference
2024, Human Brain Mapping

View all citing articles on Scopus

^☆: Research partially supported by DFG under grant Br 2158/2-3.

View full text

On variants of shortest-path betweenness centrality and their generic computation☆

Abstract

Introduction

Section snippets

Shortest-path betweenness

Variants and their computation

Discussion

Acknowledgements

Social Networks

Social Networks

Social Networks

Social Networks

Social Networks

Social Networks

Physica A

Social Networks

Social Networks

Modern Graph Theory of Graduate Texts in Mathematics, vol. 184

A faster algorithm for betweenness centrality

Journal of Mathematical Sociology

Centrality measures based on current flow

Centrality estimation in large networks

International Journal of Bifurcation and Chaos

Introduction to Algorithms

Sexual network analysis of a gonorrhoea outbreak

Sexually Transmitted Infections