Centrality measures and thermodynamic formalism for complex networks

Research output: Contribution to journalArticle

3 Downloads (Pure)

Abstract

In the study of small and large networks it is customary to perform a simple random walk where the random walker jumps from one node to one of its neighbors with uniform probability. The properties of this random walk are intimately related to the combinatorial properties of the network. In this paper we propose to use the Ruelle-Bowens random walk instead, whose probability transitions are chosen in order to maximize the entropy rate of the walk on an unweighted graph. If the graph is weighted, then a free energy is optimized instead of the entropy rate. Specifically, we introduce a centrality measure for large networks, which is the stationary distribution attained by the Ruelle-Bowens random walk; we name it entropy rank. We introduce a more general version, which is able to deal with disconnected networks, under the name of free-energy rank. We compare the properties of those centrality measures with the classic PageRank and hyperlink-induced topic search (HITS) on both toy and real-life examples, in particular their robustness to small modifications of the network. We show that our centrality measures are more discriminating than PageRank, since they are able to distinguish clearly pages that PageRank regards as almost equally interesting, and are more sensitive to the medium-scale details of the graph.
Original languageEnglish
JournalPhysical Review E - Statistical, Nonlinear, and Soft Matter Physics
Volume83
Issue number4
DOIs
Publication statusPublished - 2011

Fingerprint

Thermodynamic Formalism
Centrality
Complex Networks
random walk
PageRank
formalism
thermodynamics
Random walk
Entropy
entropy
Free Energy
Graph in graph theory
free energy
Simple Random Walk
Stationary Distribution
Transition Probability
Walk
transition probabilities
Jump
Maximise

Cite this

@article{097f5db9b08d4381b55601a01e04a347,
title = "Centrality measures and thermodynamic formalism for complex networks",
abstract = "In the study of small and large networks it is customary to perform a simple random walk where the random walker jumps from one node to one of its neighbors with uniform probability. The properties of this random walk are intimately related to the combinatorial properties of the network. In this paper we propose to use the Ruelle-Bowens random walk instead, whose probability transitions are chosen in order to maximize the entropy rate of the walk on an unweighted graph. If the graph is weighted, then a free energy is optimized instead of the entropy rate. Specifically, we introduce a centrality measure for large networks, which is the stationary distribution attained by the Ruelle-Bowens random walk; we name it entropy rank. We introduce a more general version, which is able to deal with disconnected networks, under the name of free-energy rank. We compare the properties of those centrality measures with the classic PageRank and hyperlink-induced topic search (HITS) on both toy and real-life examples, in particular their robustness to small modifications of the network. We show that our centrality measures are more discriminating than PageRank, since they are able to distinguish clearly pages that PageRank regards as almost equally interesting, and are more sensitive to the medium-scale details of the graph.",
author = "J.-C. Delvenne and A.-S. Libert",
note = "Copyright 2011 Elsevier B.V., All rights reserved.",
year = "2011",
doi = "10.1103/PhysRevE.83.046117",
language = "English",
volume = "83",
journal = "Physical Review E - Statistical, Nonlinear, and Soft Matter Physics",
issn = "1539-3755",
publisher = "American Physical Society",
number = "4",

}

TY - JOUR

T1 - Centrality measures and thermodynamic formalism for complex networks

AU - Delvenne, J.-C.

AU - Libert, A.-S.

N1 - Copyright 2011 Elsevier B.V., All rights reserved.

PY - 2011

Y1 - 2011

N2 - In the study of small and large networks it is customary to perform a simple random walk where the random walker jumps from one node to one of its neighbors with uniform probability. The properties of this random walk are intimately related to the combinatorial properties of the network. In this paper we propose to use the Ruelle-Bowens random walk instead, whose probability transitions are chosen in order to maximize the entropy rate of the walk on an unweighted graph. If the graph is weighted, then a free energy is optimized instead of the entropy rate. Specifically, we introduce a centrality measure for large networks, which is the stationary distribution attained by the Ruelle-Bowens random walk; we name it entropy rank. We introduce a more general version, which is able to deal with disconnected networks, under the name of free-energy rank. We compare the properties of those centrality measures with the classic PageRank and hyperlink-induced topic search (HITS) on both toy and real-life examples, in particular their robustness to small modifications of the network. We show that our centrality measures are more discriminating than PageRank, since they are able to distinguish clearly pages that PageRank regards as almost equally interesting, and are more sensitive to the medium-scale details of the graph.

AB - In the study of small and large networks it is customary to perform a simple random walk where the random walker jumps from one node to one of its neighbors with uniform probability. The properties of this random walk are intimately related to the combinatorial properties of the network. In this paper we propose to use the Ruelle-Bowens random walk instead, whose probability transitions are chosen in order to maximize the entropy rate of the walk on an unweighted graph. If the graph is weighted, then a free energy is optimized instead of the entropy rate. Specifically, we introduce a centrality measure for large networks, which is the stationary distribution attained by the Ruelle-Bowens random walk; we name it entropy rank. We introduce a more general version, which is able to deal with disconnected networks, under the name of free-energy rank. We compare the properties of those centrality measures with the classic PageRank and hyperlink-induced topic search (HITS) on both toy and real-life examples, in particular their robustness to small modifications of the network. We show that our centrality measures are more discriminating than PageRank, since they are able to distinguish clearly pages that PageRank regards as almost equally interesting, and are more sensitive to the medium-scale details of the graph.

UR - http://www.scopus.com/inward/record.url?scp=79961063554&partnerID=8YFLogxK

U2 - 10.1103/PhysRevE.83.046117

DO - 10.1103/PhysRevE.83.046117

M3 - Article

AN - SCOPUS:79961063554

VL - 83

JO - Physical Review E - Statistical, Nonlinear, and Soft Matter Physics

JF - Physical Review E - Statistical, Nonlinear, and Soft Matter Physics

SN - 1539-3755

IS - 4

ER -