Linde Institute/SISL Seminar: Shang-Hua Teng

Abstract

Data and network analysis is not just a mathematical task, but also a computational task. In the age of Big Data, networks are massive. Thus, any effective solution concept in network science should be both mathematically meaningful and algorithmically scalable. Bearing this in mind, in this talk, I will focus on the interplay between social influence and network centrality by addressing the following fundamental question: "Given a social network, what is the impact of influence models on network centrality?"

Social influence involves both static network structures and dynamic influence processes. It is well known that formulations based solely on the static structures, such as PageRank, local sphere-of-influences, and betweenness, may not sufficiently capture social-influence centrality. I will discuss a game-theoretical approach that integrates the dynamic and static aspects of this complex network data. A succinct cooperative game naturally defined by the network-influence process is identified in which each group's utility is its influence spread. Thus, fundamental game-theoretical concepts of this social-influence game, particularly the Shapley value, can be instrumental to understanding network influence.

Mathematically, we present an axiomatic characterization which captures the essence of using the Shapley value as a measure of social-influence centrality. Algorithmically, we give a scalable algorithm for approximating the Shapley values of a large family of social-influence instances. This dual axiomatic and algorithmic characterization provides a comprehensive and comparative framework for evaluating the effectiveness of different centrality formulations of influence models.

Based on joint work with Wei Chen of Microsoft Research Asia Lab.