Diffusion centrality: A paradigm to maximize spread in social networks

We propose Diffusion Centrality (DC) in which semantic aspects of a social network are used to characterize vertices that are influential in diffusing a property p. In contrast to classical centrality measures, diffusion centrality of vertices varies with the property p, and depends on the diffusion model describing how p spreads. We show that DC applies to most known diffusion models including tipping, cascade, and homophilic models. We present a hypergraph-based algorithm (HyperDC) with many optimizations to exactly compute DC. However, HyperDC does not scale well to huge social networks (millions of vertices, tens of millions of edges). For scaling, we develop methods to coarsen a network and propose a heuristic algorithm called “Coarsened Back and Forth” (CBAF) to compute the top-k vertices (having the highest diffusion centrality). We report on experiments comparing DC with classical centrality measures in terms of runtime and the “spread” achieved by the k most central vertices (using 7 real-world social networks and 3 different diffusion models). Our experiments show that DC produces higher quality results and is comparable to several centrality measures in terms of runtime.