Diffusion Centrality in Social Networks

V.S. Subrahmanian, Ph.D.
Professor, Department of Computer Science
University of Maryland

Abstract: Though centrality of vertices in social networks has been extremely studied, all past efforts assume that centrality of a vertex solely depends on the structural properties of graphs. However, with the emergence of online "semantic" social networks where vertices have properties (e.g., sex, demographics) and edges are labeled with relationships (e.g., friends, follows) and weights (measuring the strength of a relationship), it is essential that we take semantics into account when measuring centrality. Moreover, the centrality of a node should be tied to diffusive property in the network - a Twitter vertex may have high centrality with regard to jazz, but low centrality with regard to Republican politics. We propose a new notion of "diffusion centrality" (DC) in which semantic aspects of the graph, as well as a diffusion model of how a diffusive property "p" is spreading is used to characterize the centrality of vertices. DC is polynomially computable - we present a hyper-graph based algorithm to compute DC and report on a prototype implementation and experiments showing how we can compute DCs (using real Youtube data) on semantic social networks of up to 100k vertices in a reasonable amount of time. Ongoing work focuses on scaling this up.

Joint work with Chanhyn Kang, Sarit Kraus, Cristian Molinaro, and Yuval Shavitt.



















This Web Page Created with PageBreeze Free HTML Editor / Web Hosting