Applied Modeling Techniques and Data Analysis 1

5 A Comparison of Graph Centrality Measures Based on Lazy Random Walks

When working with a network, it is often of interest to locate the “most important” nodes in the network. A common way to do this is by using some graph centrality measures. Since what constitutes as an important node varies from one network to another, or even in applications on the same network, there is a large number of different centrality measures proposed in the literature. Due to the large amount of different centrality measures proposed in different fields, there is also a large amount of very similar or equivalent centrality measures (in the sense that they give the same ranks). In this chapter, we focus on the centrality measures based on powers of the adjacency matrix and those based on random walk. In this case, we show how some of these centrality measures are related, as well as their lazy variants. We will perform some experiments to demonstrate the similarities between the centrality measures.

5.1. Introduction

In any network, it is important to identify key nodes within it. According to Roy et al. (2010), Das et al. (2018), Li and Zhang (2018), one of the most interesting tools used to establish the importance of a node from a complex network is its centrality measure. The concept of centralities is said to have originated between the 1940s and 1950s (Bavelas 1948, 1950; Leavitt 1951). To date, more than 100 different centrality measures have been proposed to describe several research fields ...