Centrality measures and thermodynamic formalism for complex networks

Jean-Charles Delvenne and Anne-Sophie Libert
Phys. Rev. E 83, 046117 – Published 22 April 2011

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.

  • Figure
  • Figure
  • Figure
  • Received 27 September 2010

DOI:https://doi.org/10.1103/PhysRevE.83.046117

©2011 American Physical Society

Authors & Affiliations

Jean-Charles Delvenne*,† and Anne-Sophie Libert

  • Department of Mathematics, Namur Centre for Complex Systems, Facultés Universitaires Notre-Dame de la Paix, B-5000 Namur, Belgium

  • *jean-charles.delvenne@uclouvain.be
  • Present address: Department of Applied Mathematics, Université Catholique de Louvain, B-1348 Louvain-la Neuve, Belgium.
  • anne-sophie.libert@fundp.ac.be

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 83, Iss. 4 — April 2011

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×