Detecting global bridges in networks

Autor: Pierre Mercklé, Mathieu Jacomy, Jean-Philippe Cointet, Alessandro Vespignani, Eric Fleury, Tommaso Venturini, Márton Karsai, Matteo Morini, Pablo Jensen
Přispěvatelé: École normale supérieure de Lyon (ENS de Lyon), Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Joseph Fourier - Grenoble 1 (UJF)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Physique de l'ENS Lyon (Phys-ENS), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Dynamic Networks : Temporal and Structural Capture Approach (DANTE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-Université Joseph Fourier - Grenoble 1 (UJF)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), médialab (Sciences Po) (médialab), Sciences Po (Sciences Po), Laboratory for the Modeling of Biological and Socio-technical Systems [Boston] (MoBS), Northeastern University [Boston], Institute for Scientific Interchange (ISI) Foundation, Sciences en Société (SenS), Institut National de la Recherche Agronomique (INRA), Université Paris-Est (UPE), Centre Max Weber (CMW), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS), Funding provided by the CNRS 'Mission pour l'interdisciplinarité' (MASTODONS) is gratefully acknowledged., École normale supérieure - Lyon (ENS Lyon), École normale supérieure - Lyon (ENS Lyon)-Université Lumière - Lyon 2 (UL2)-Université Joseph Fourier - Grenoble 1 (UJF)-Université Jean Moulin - Lyon 3 (UJML), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Médialab (Sciences Po) (Médialab), Science en Société (INRA-SenS), École normale supérieure - Lyon (ENS Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Monnet [Saint-Étienne] (UJM)-Centre National de la Recherche Scientifique (CNRS), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon, Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Institut Rhône-Alpin des systèmes complexes (IXXI), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-Université Joseph Fourier - Grenoble 1 (UJF)-Université Jean Moulin - Lyon 3 (UJML), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Monnet [Saint-Étienne] (UJM)
Jazyk: angličtina
Rok vydání: 2016
Předmět:
FOS: Computer and information sciences
Physics - Physics and Society
Theoretical computer science
Control and Optimization
Computer science
Computer Networks and Communications
FOS: Physical sciences
Physics and Society (physics.soc-ph)
Management Science and Operations Research
01 natural sciences
Measure (mathematics)
[INFO.INFO-SI]Computer Science [cs]/Social and Information Networks [cs.SI]
010305 fluids & plasmas
Betweenness centrality
0103 physical sciences
Bridgeness centrality
Centrality measures
Computational Mathematics
Applied Mathematics
ddc:305.3
010306 general physics
Social and Information Networks (cs.SI)
Degree (graph theory)
Node (networking)
Computational mathematics
Computer Science - Social and Information Networks
Identification (information)
Graph (abstract data type)
Centrality
Zdroj: Journal of Complex Networks
Journal of Complex Networks, 2015, 4 (3), pp.319-329. ⟨10.1093/comnet/cnv022⟩
Journal of Complex Networks, Oxford, 2015, ⟨10.1093/comnet/cnv022⟩
Journal of Complex Networks (2015-09)
Journal of complex networks, Vol. 4, No 3 (2016) pp. 319-329
Journal of Complex Networks, Oxford University Press, 2015, 4 (3), pp.319-329. ⟨10.1093/comnet/cnv022⟩
ISSN: 2051-1310
2051-1329
DOI: 10.1093/comnet/cnv022⟩
Popis: 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.
Comment: Journal of Complex Networks Preprint; 14 pages; 6 figures
Databáze: OpenAIRE
Externí odkaz: