Faculty Candidate Talk: Francesca Spezzano
480 Dreese Labs
2015 Neil Ave
Columbus,
United States
Diffusion Centrality 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. 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 of vertices. However, HyperDC does not scale well to huge SNs (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” or CBAF to compute the top-k vertices (having the highest diffusion centrality w.r.t. p). We describe a prototype implementation of HyperDC and CBAF, and report on experiments comparing DC with classical centrality measures in terms of runtime and the “spread” achieved by the k most central vertices (using data from 7 real-world social networks and 3 different diffusion models). Our extensive experiments show that DC produces much higher quality results and is comparable to several centrality measures in terms of runtime. Moreover, the CBAF approximate algorithm is extremely fast and achieves a very high spread.
Francesca Spezzano received the PhD degree in Computer Science Engineering from the University of Calabria, Italy, in 2012. She was a Visiting Scholar at the Computer Science Department (Database Group) of the University of California - Santa Cruz (Oct 2010 - Jul 2011). After the PhD degree, she was postdoc at the University of Calabria. From Aug 2013, she is Postdoctoral Research Associate at the University of Maryland Institute for Advanced Computer Studies. Her research interests include social network analysis, data science, uncertainty in databases, data exchange, and logic programming.