Shang-Hua Teng, USC 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 a joint work with Wei Chen of Microsoft Research Asia Lab Biography: Dr. Shang-Hua Teng has twice won the prestigious Gödel Prize in theoretical computer science, first in 2008, for developing the theory of smoothed analysis , and then in 2015, for designing the groundbreaking nearly-linear time Laplacian solver for network systems. Both are joint work with Dan Spielman of Yale --- his long-time collaborator. Smoothed analysis is fundamental for modeling and analyzing practical algorithms, and the Laplacian paradigm has since led to several breakthroughs in network analysis, matrix computation, and optimization. Citing him as, "one of the most original theoretical computer scientists in the world", the Simons Foundation named Teng a 2014 Simons Investigator, for pursuing long-term curiosity-driven fundamental research. He and his collaborators also received the best paper award at ACM Symposium on Theory of Computing (STOC) for what's considered to be the "first improvement in 10 years" of a fundamental optimization problem --- the computation of maximum flows and minimum cuts in a network. In addition, he is known for his joint work with Xi Chen and Xiaotie Deng that characterized the complexity for computing an approximate Nash equilibrium in game theory, and his joint papers on market equilibria in computational economics. He and his collaborators also pioneered the development of well-shaped Delaunay meshing algorithms for arbitrary three-dimensional geometric domains, which settled a long-term open problem in numerical simulation, also a fundamental problem in computer graphics. Software based on this development was used at the University of Illinois for the simulation of advanced rockets. Teng is also interested in mathematical board games. With his former Ph.D. student Kyle Burke, he designed and analyzed a game called Atropos , which is played on the Sperner's triangle and based on the beautiful, celebrated Sperner's Lemma. In 2000 at UIUC, Teng was named on the List of Teachers Ranked as Excellent by Their Students for his class, "Network Security and Cryptography". He has worked and consulted for Microsoft Research, Akamai, IBM Almaden Research Center, Intel Corporation, Xerox PARC, and NASA Ames Research Center, for which he received fifteen patents for his work on compiler optimization, Internet technology, and social networks. Teng's recent research interests include algorithmic theory for Big Data and network science, spectral graph theory, social-choice-theoretical approaches to community identification, and game-theoretical frameworks for understanding the interplay between influence processes and social networks. With a three-year old daughter, he also becomes intensely interested in the learning theory for early childhood bilingual acquisition.
Không có nhận xét nào:
Đăng nhận xét