Cheng-Shang Chang

In this talk, we make an attempt to develop a formal framework for what a good community should look like and how strong a community is (community strength). Through this framework we can not only provide more physical insights and unified interpretations for various structural analyses of networks such as centralities and communities, but also develop efficient algorithms for local community detection with guaranteed community strength.

One of the key innovations of our framework is to incorporate the concept of relative centrality into structural analysis of networks. In our framework, relative centrality is a (probability) measure that measures how important a set of nodes in a network is with respect to another set of nodes, and it is a generalization of centrality that only measures (or ranks) how important a set of nodes in a network is with respect to the whole set of nodes in the network. Building on top of relative centrality, the community strength for a set of nodes is measured by the difference between its relative centrality with respect to itself and its centrality. A community is then a set of nodes with a nonnegative community strength. With such a definition of community, we are able to prove several mathematically equivalent statements of a community that can be intuitively explained by their social meanings. There are also several interesting interpretations for the community strength. In particular, we show that our community strength is related to conductance that is commonly used for measuring the strength of a small community. We then define the modularity for a partition of a network (graph) as the average community strength of the community to which a randomly selected nodes belongs. Such a definition generalizes the original Newman’s modularity and recovers the stability as special cases.

For the local community detection problem, we develop agglomerative algorithms that guarantee the community strength of the detected local community. There are two nice features of our local community detection algorithms: (i) local search: only nodes in the neighboring set need to be explored, and (ii) recursive update: the relative centralities can be efficiently updated by using recursive formulae. As such, our algorithms not only are as efficient as the Clauset’s algorithm in terms of computational complexity, but also take the clustering coefficient into account by looking beyond the first neighbors in local search. We test our algorithms on the dataset of the American football games. Our experimental results show that those conferences with strong community strengths can be detected with 100% precision and 100% recall.

Cheng-Shang Chang (S'85-M'86-M'89-SM'93-F’04) received the B.S. degree from the National Taiwan University, Taipei, Taiwan, in 1983, and the M.S. and Ph.D. degrees from Columbia University, New York, NY, in 1986 and 1989, respectively, all in Electrical Engineering. From 1989 to 1993, he was employed as a Research Staff Member at the IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y. Since 1993, he has been with the Department of Electrical Engineering at National Tsing Hua University, Taiwan, R.O.C., where he is a Tsing Hua Chair Professor. His current research interests are concerned with network science, high speed switching, communication network theory, and mathematical modeling of the Internet. Dr. Chang received an IBM Outstanding Innovation Award in 1992, an IBM Faculty Partnership Award in 2001, and Outstanding Research Awards from the National Science Council, Taiwan, in 1998, 2000 and 2002, respectively. He also received Outstanding Teaching Awards from both the college of EECS and the university itself in 2003. He was appointed as the first Y. Z. Hsu Scientific Chair Professor in 2002 and elected to an IEEE Fellow in 2004. Dr. Chang received the Academic Award from the Ministry of Education and the Outstanding Research Fellow Award from the National Science Council in 2011. He is the author of the book ``Performance Guarantees in Communication Networks'' and the coauthor of the book “Principles, Architectures and Mathematical Theory of High Performance Packet Switches.” He served as an editor for Operations Research from 1992 to 1999 and an editor for IEEE/ACM Transactions on Networking from 2007 to 2009. He is currently serving as an editor-at-large for IEEE/ACM Transactions on Networking and an editor for IEEE Transactions on Network Science and Engineering. Dr. Chang is a member of IFIP Working Group 7.3