Title:
Overlapping Community Detection in Massive Social Networks

Abstract:
Massive social networks have become increasingly popular in recent years. Community detection is one of the most important techniques for the analysis of such complex networks. A community is a set of cohesive vertices that has more connections inside the set than outside. In many social and information networks, these communities naturally overlap. For instance, in a social network, each vertex in a graph corresponds to an individual who usually participates in multiple communities. In this talk, I will introduce scalable overlapping community detection algorithms that effectively identify high quality overlapping communities in various real-world networks.

I will first talk about an efficient overlapping community detection algorithm using a seed set expansion approach. The key idea of this algorithm is to find good seeds and then greedily expand these seeds using a personalized PageRank clustering scheme. Experimental results show that our algorithm significantly outperforms other state-of-the-art overlapping community detection methods in terms of run time, cohesiveness of communities, and ground-truth accuracy. To develop more principled methods, we formulate the overlapping community detection problem as a non-exhaustive, overlapping graph clustering problem where clusters are allowed to overlap with each other, and some nodes are allowed to be outside of any cluster. To tackle this non-exhaustive, overlapping clustering problem, we propose a simple and intuitive objective function that captures the issues of overlap and non-exhaustiveness in a unified manner. To optimize the objective, we develop not only fast iterative algorithms but also more sophisticated algorithms using a low-rank semidefinite programming technique. Our experimental results show that the new objective and the algorithms are effective in finding ground-truth clusterings that have varied overlap and non-exhaustiveness.

Biography:
Joyce Jiyoung Whang is an assistant professor of Computer Science and Engineering at Sungkyunkwan University. She received her B.S. degree in Computer Science and Engineering from Ewha Womans University, and Ph.D. in Computer Science from the University of Texas at Austin. Her main research interests are in big data, data mining, machine learning, and social network analysis with specific interests in community detection, overlapping clustering, and graph partitioning.