Rethinking Centrality: The Role of Dynamical Processes in Social Network\n Analysis

Many popular measures used in social network analysis, including centrality,\nare based on the random walk. The random walk is a model of a stochastic\nprocess where a node interacts with one other node at a time. However, the\nrandom walk may not be appropriate for modeling social phenomena, including\nepidemics and information diffusion, in which one node may interact with many\nothers at the same time, for example, by broadcasting the virus or information\nto its neighbors. To produce meaningful results, social network analysis\nalgorithms have to take into account the nature of interactions between the\nnodes. In this paper we classify dynamical processes as conservative and\nnon-conservative and relate them to well-known measures of centrality used in\nnetwork analysis: PageRank and Alpha-Centrality. We demonstrate, by ranking\nusers in online social networks used for broadcasting information, that\nnon-conservative Alpha-Centrality generally leads to a better agreement with an\nempirical ranking scheme than the conservative PageRank.\n