Community Identification in Social Networks: From the Lens of Social Choice Theory and Game Theory

Speaker:        Professor Shang-Hua Teng
                Computer Science Department
                Viterbi School of Engineering
                University of Southern California

Title:          "Community Identification in Social Networks:
                 From the Lens of Social Choice Theory and Game Theory"

Date:           Tuesday, 9 December 2014

Time:           2:30pm - 3:30pm

Venue:          Lecture Theater K (near lifts 31/32) HKUST


Abstract:

I will discuss some recent progress in addressing two basic questions in
network analysis:
- [Conceptual question]: What constitutes a community in a social network?
- [Complexity question]: Can we identify communities efficiently?

The journey towards understanding these two fundamental questions lead us
to Social Choice Theory and Game Theory. The talk is based on joint work
with Christian Borgs, Jennifer Chayes, and Adrian Marple.


******************
Biography:

Shang-Hua Teng is the Seeley G. Mudd Professor at the Computer Science
Department, Viterbi School of Engineering, USC, where he was a former
chair (2009-2012). He received a dual B.S. degree in computer science and
electrical engineering from Shanghai Jiao Tong University in 1985, M.S.
degree in computer science from USC in 1988, and Ph.D. degree in computer
science from Carnegie Mellon University (CMU) in 1991. He was an
instructor in the Department of Mathematics of MIT and professor in the
Computer Science Departments of Boston University, the University of
Minnesota and UIUC. He has worked and consulted for Microsoft Research,
Akamai, IBM Almaden Research Center, Intel Corporation, Xerox PARC, Cray
Research/SGI, Thinking Machines Corporation, and NASA Ames Research
Center. He has received more than ten US Patents for his work on compiler
optimization, Internet technology, and social network analysis.

Teng's main research is in algorithm design, analysis, and applications.
He and coauthor Dan Spielman received the Godel Prize (2008) and Fulkerson
Prize (2009) for developing Smoothed Analysis and his recent work
addresses Spectral Graph Theory & the Laplacian Paradigm and its
applications to maximum flows, for which he and coauthors Paul Christiano,
Jon Kelner, Aleksander Madry, and Dan Spielman received the best paper
award at ACM STOC 2011. Teng's past research interests include algorithmic
game theory, scientific computing, Internet algorithms, computational
geometry, percolation theory, compiler optimization, parallel algorithms,
cryptography, computer graphics and three-dimensional mesh generation,
where he had obtained fundamental results in geometric separators,
well-shaped Delaunay meshing, spectral graph partition, N-body simulation,
and robust statistics. He is an ACM Fellow, Alfred P. Sloan Fellow, winner
of Senior Xerox Award for Outstanding Faculty Research (UIUC), and NSF
CAREER Award.