Detecting global bridges in networks

Pablo Jensen; Matteo Morini; Márton Karsai; Tommaso Venturini; Alessandro Vespignani; Mathieu Jacomy; Jean-Philippe Cointet; Pierre Mercklé; Eric Fleury

Detecting global bridges in networks

Pablo Jensen ^{1, 2, 3} Matteo Morini ^{1, 4, 5} Márton Karsai ^{1, 4, 5} Tommaso Venturini ⁶ Alessandro Vespignani ^{7, 8} Mathieu Jacomy ⁶ Jean-Philippe Cointet ^{9, 10} Pierre Mercklé ^{1, 11} Eric Fleury ^{4, 2, 5}

1 ENS Lyon - École normale supérieure - Lyon

2 IXXI - Institut Rhône-Alpin des systèmes complexes

3 Phys-ENS - Laboratoire de Physique de l'ENS Lyon

4 LIP - Laboratoire de l'Informatique du Parallélisme

5 DANTE - Dynamic Networks : Temporal and Structural Capture Approach

Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme, IXXI - Institut Rhône-Alpin des systèmes complexes

6 MEDIALAB - médialab

7 MoBS - Laboratory for the Modeling of Biological and Socio-technical Systems [Boston]

8 Institute for Scientific Interchange (ISI) Foundation

9 INRA-SenS - Science en Société

10 UPE - Université Paris-Est

11 CMW - Centre Max Weber

Abstract : The identification of nodes occupying important positions in a network structure is crucial for the understanding of the associated real-world system. Usually, betweenness centrality is used to evaluate a node capacity to connect different graph regions. However, we argue here that this measure is not adapted for that task, as it gives equal weight to “local” centers (i.e. nodes of high degree central to a single region) and to “global” bridges, which connect different communities. This distinction is important as the roles of such nodes are different in terms of the local and global organisation of the network structure. In this paper we propose a decomposition of betweenness centrality into two terms, one highlighting the local contributions and the other the global ones. We call the latter bridgeness centrality and show that it is capable to specifically spot out global bridges. In addition, we introduce an effective algorithmic implementation of this measure and demonstrate its capability to identify global bridges in air transportation and scientific collaboration networks

Keywords : Betweenness Centrality Bridgeness Centrality Centrality Measures

Document type :

Journal articles

Domain :

Computer Science [cs] / Social and Information Networks [cs.SI]

Complete list of metadatas

Cited literature [31 references] Display Hide Download

https://hal.inria.fr/hal-01206166
Contributor : Matteo Morini <>
Submitted on : Thursday, October 1, 2015 - 1:31:15 PM
Last modification on : Monday, June 17, 2019 - 6:26:11 PM
Long-term archiving on : Saturday, January 2, 2016 - 10:13:41 AM

Jensen_MS.pdf

Files produced by the author(s)

Detecting global bridges in networks

Files

Licence

Identifiers

Collections

Relations

Citation

Export

Metrics

571

1626

Contact

Detecting global bridges in networks

Files

Licence

Identifiers

Collections

Relations

Citation

Export

Share

Metrics

571

1626

Contact