| Contents |
| Many popular metrics used in social network analysis are based on the random walk. However, the random walk may not be appropriate for modeling and analyzing many social phenomena, including epidemics and information diffusion, in which one node may interact with many others at the same time, for example, by broadcasting the virus or information to its neighbors. To produce meaningful results, social network analysis algorithms have to take into account the nature of interactions between the nodes. We classify interactions as conservative (informally, one-to-one) and non-conservative (one-to-many) and show that while the former describes random walk dynamics, the latter is mathematically equivalent to epidemic dynamics. We then relate these to well-known metrics used in network analysis: PageRank and Alpha-Centrality. We demonstrate by ranking nodes in an online social network used for broadcasting information, that non-conservative Alpha-Centrality leads to a better agreement with an empirical ranking scheme than the conservative PageRank.
Our work unifies two areas of network analysis --- centrality and epidemic models --- and leads to insights into the relationship between dynamic processes and network structure, specifically, the existence of an epidemic threshold for non-conservative processes. |
|