Skip to main content
Diffusion Centrality: A Paradigm to Maximize Spread in Social Networks
Artificial Intelligence
  • Chanhyun Kang, University of Maryland
  • Sarit Kraus, Bar-Ilan University
  • Cristian Molinaro, Università della Calabria
  • Francesca Spezzano, Boise State University
  • V. S. Subrahmanian, University of Maryland
Document Type
Publication Date

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.

Citation Information
Kang, Chanhyun; Kraus, Sarit; Molinaro, Cristian; Spezzano, Francesca; and Subrahmanian, V.S. (2016). Diffusion Centrality: A Paradigm to Maximize Spread in Social Networks. Artificial Intelligence, 239, 70-96.