ORIE Colloquium: Bruce Hajek (Illinois) - On community detection in preferential attachment networks
Location
Frank H. T. Rhodes Hall 253
Description
An extensive theory of community detection has developed within the past few years. The goal is to discover clusters of vertices in a graph based on the edges of the graph. Much work has focused on evaluation of algorithms, including message passing algorithms, for a particular generative model, namely, the stochastic block model. The stochastic block model is a variant of Erdos-Renyi type graph. In this talk we focus on the problem of community detection for the Barabasi-Albert preferential attachment model with communities, defined by J. Jordan. In such model, vertices are sequentially attached to the graph, with preference to attach more edges to existing vertices with larger degrees, multiplied by affinities based on community membership. While more complicated than SBM, it is shown that the model has sufficient structure to formulate approximate belief propagation algorithms for community detection.
Based on joint work with S. Sankagiri.
Bio:
Bruce Hajek is a Center for Advanced Study Professor of Electrical and Computer Engineering, Hoeft Chair of Engingeering, and Research Professor in the Coordinated Science Laboratory at the University of Illinois at Urbana-Champaign, where he has been on the faculty since 1979. He received a B.S. in mathematics and M.S. in electrical engineering from the University of Illinois and the Ph. D. in electrical engineering from the University of California at Berkeley. Professor Hajek's research interests include communication networks, auction theory, stochastic analysis, combinatorial optimization, machine learning, information theory, bioinformatics. He served as Editor-in-Chief for the IEEE Transactions on Information Theory, and as president of the IEEE Information Theory Society. He received the Institute of Electrical and Electronics Engineers (IEEE) Kobayashi Award for Computer Communication and the ACM SIGMETRICS Achievement Award and he is a member of the U.S. National Academy of Engineering.