Centrality measures and thermodynamic formalism for complex networks

Area of Science:

• Network Science
• Graph Theory
• Information Theory

Background:

• Traditional random walks on networks rely on uniform probability transitions.
• Network properties are closely linked to the behavior of these random walks.
• Existing centrality measures like PageRank and HITS have limitations in discriminating network importance.

Purpose of the Study:

• To propose and analyze the Ruelle-Bowens random walk for network analysis.
• To introduce novel centrality measures, entropy rank and free-energy rank.
• To compare the efficacy and robustness of these new measures against established methods.

Main Methods:

• Implementing the Ruelle-Bowens random walk, optimizing entropy rate (unweighted) or free energy (weighted).
• Deriving centrality measures (entropy rank, free-energy rank) from the stationary distribution of the Ruelle-Bowens walk.
• Comparative analysis with PageRank and HITS on synthetic and real-world networks.

Main Results:

• The Ruelle-Bowens random walk provides a more discriminating centrality measure than PageRank.
• Entropy rank and free-energy rank better distinguish between nodes with similar PageRank scores.
• The proposed measures exhibit greater sensitivity to medium-scale graph structures and robustness to network modifications.

Conclusions:

• The Ruelle-Bowens random walk offers a powerful alternative for network centrality analysis.
• Entropy rank and free-energy rank provide superior insights into network topology and node importance.
• These novel centrality measures enhance the analysis of complex networks, particularly in distinguishing subtle differences in importance.