Jiaming Xu

University of Illinois, Urbana-Chamoaign

Abstract
This talk addresses the problem of clustering nodes in a network, which is known as community detection problem. This problem has many applications such as link prediction in social or biological networks, and rating prediction in recommender systems. We consider the “planted partition” model which is a generalized Erdos-Renyi random graph model with “planted” clusters. Our goal is to exactly recover the underlying planted clusters from observing a graph generated under the planted partition model.

We proposed a series of cluster recovery algorithms and analyzed their performance. We show that some polynomial-time algorithm can successfully recover the planted clusters up to a spectral barrier and achieves the best known performance guarantee among all polynomial-time algorithms; while an exponential-time algorithm succeeds in a substantial region beyond the spectral barrier and achieves the fundamental information limit.

This work is at the intersection of information theory, machine learning, and optimization theory. Based on joint work with Yudong Chen (UC Berkeley).

Bio:
Jiaming Xu is a PhD candidate in ECE department under the supervision of Professor Bruce Hajek. He received the B.E. degree from Tsinghua University in 2009 and the M.S. degree from UT-Austin in 2011, all in ECE. His research interests are in statistical learning, queueing and game theory.