# Bridgeness: a novel centrality measure to detect global bridges

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

► To cite this version:

Pablo Jensen, Matteo Morini, Tommaso Venturini, Mathieu Jacomy, Jean-Philippe Cointet, et al. Bridgeness: a novel centrality measure to detect global bridges. ECCS 2014 – European Conference on Complex Systems, Sep 2014, Lucca, Italy., 2014. hal-01175702

HAL Id: hal-01175702

https://inria.hal.science/hal-01175702

Submitted on 11 Jul 2015

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# BRIDGENESS
## A NOVEL CENTRALITY MEASURE TO DETECT GLOBAL BRIDGES

Pablo Jensen
IXXI, ENS Lyon, LabPhys, UMR 5672

Matteo Morini
IXXI, ENS Lyon, LIP, INRIA, UMR 5668

Tommaso Venturini
Médialab, Sciences Po, Paris

Mathieu Jacomy
Médialab, Sciences Po, Paris

Jean-Philippe Cointet
Université Paris-Est, SenS - IFRIS

Pierre Mercklé
Centre Max Weber, UMR 5283, ENS Lyon

Márton Karsai
IXXI, ENS Lyon, LIP, INRIA, UMR 5668

Eric Fleury
IXXI, ENS Lyon, LIP, INRIA, UMR 5668

Finding nodes occupying interesting positions in a graph is useful to extract meaningful information from large datasets. While numerous measures have been proposed to evaluate the centrality of nodes, few indicators quantify the capacity of nodes to connect different regions of the graph. Usually, betweenness centrality is used for this purpose, but we show here that it gives equal scores to “local” centers (i.e. nodes of high degree central to a single region) and to “global” bridges, which connect different regions. This distinction is important because the roles of these nodes are quite diverse. For example, in networks of scientific collaborations, local centers correspond to nodes which are important for a single sub-discipline, while bridges correspond to nodes which connect different sub-disciplines, leading to interdisciplinary collaborations. We show that a new measure of network topology, the bridgeness, is able to discriminate between local centers and global bridges, in synthetic and real networks.

The figures show the betweenness (a) and bridgeness (b) scores for a simple graph. Betweenness does not distinguish centers from bridges, as it attributes a slightly higher score (Figure a, scores = 27) to high-degree nodes which are local centers, than to the global bridge (Figure a, score = 25). In contrast, bridgeness rightly spots out the node (Figure b, score = 16) that plays the role of a global bridge.

<figure><img src="image_2.png" /><figcaption>(a) Betweenness Node Centrality</figcaption></figure>

Example of the two largest Argentinean airports, Ezeiza (EZE) and Aeroparque (AEP). Both have a similar degree (54 and 45 respectively), but while the first connects Argentina to the rest of the world (85% of international connections, average distance 2.848 miles), Aeroparque is only a local center (18% of international connections, average distance 570 miles). However, as in the simple graph (Figure 1), BC gives the same score to both (BC_EZE = 79 000 and BC_AEP = 82,000), while bridgeness clearly distinguishes the local center and the bridge to the rest of the world, by attributing to the global bridge a score 250 times higher (Bri_EZE = 46,000 and Bri_AEP = 174).

Bridgeness removes all shortest-paths which start or end in the neighbourhood of v.

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /><figcaption>(b) Bridgeness Node Centrality</figcaption></figure>

## Node Betweenness Centrality

<figure><img src="image_5.png" /></figure>

BRIDGE

BRIDGE

## Node Bridgeness Centrality

<figure><img src="image_6.png" /></figure>

LOCAL BRIDGE

GLOBAL BRIDGE

## The problem with betweenness centrality

$$G = (V, E)$$

$$g(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}$$

$s, v, t \in V$

$\sigma_{st}$ - Shortest-path between s and t

* Somewhat captures the centrality of nodes

* Assigns high centrality values for high degree nodes by default

* This definition mixes the global and local bridges

<figure><img src="image_7.png" /></figure>

Local bridges:

* placed in communities

* connects similar nodes

Global bridges:

* placed between communities

* connects dissimilar nodes

## Bridging node centrality - properties

$$g(v) = g_{br}(v) + g'(v)$$

$$g_{br}(v) \leq g(v)$$

<figure><img src="image_8.png" /></figure>