A Comparison of Graph Centrality Measures Based on Lazy Random Walks. Applied Modelling Techniques and Data Analysis 1: Computational Data Analysis Methods and Tools

Abstract

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 using some graph centrality measures. Since what constitutes an important node is different between different networks or even applications on the same network there is a large amount 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 very similar or equivalent centrality measures in the sense that they give the same ranks. In this paper we will focus on centrality measures based on powers of the adjacency matrix or similar matrices and those based on random walk in order to show how some of these are related and can be calculated efficiently using the same or slightly altered algorithms.
Keywords
Graph, Graph centrality, Lazy walk, Adjacency matrix, Power series