Department of Statistics & Data Science Seminar

  • Vijay Nair Collegiate Professor of Statistics
  • Department of Statistics
  • University of Michigan

Hierarchical Community Detection By Recursive Partitioning

Community detection in networks has been extensively studied in the form of finding a single partition into a “correct” number of communities. In large networks, however, a multi-scale hierarchy of communities is much more realistic. We show that a hierarchical tree of communities, obviously more interpretable, is also potentially more accurate and more computationally efficient. We construct this tree with a simple top-down recursive algorithm, at each step splitting the nodes into two communities with a non-iterative spectral algorithm, until a stopping rule suggests there are no more communities. The algorithm is model-free, extremely fast, and requires no tuning other than selecting a stopping rule. We propose a natural model for this setting, a binary tree stochastic block model, and prove that the algorithm correctly recovers the entire community tree under relatively mild assumptions. As a by-product, we obtain explicit and intuitive results for fitting the stochastic block model under model misspecification. We illustrate the algorithm on a statistics papers dataset constructing a highly interpretable tree of statistics research communities.  This is joint work with Tianxi Li, Lihua Lei, Sharmodeep Bhattacharyya, Purnamrita Sarkar, and Peter Bickel.

Liza Levina is the Vijay Nair Collegiate Professor of Statistics at the University of Michigan, as well as affiliated faculty at the Michigan Institute for Data Science and the Center for the Study of Complex Systems. She received her PhD in Statistics from UC Berkeley in 2002, and has been at the University of Michigan since.  She is well known for her work on high-dimensional inference and statistical network analysis.   She is a recipient of the ASA Noether Young Scholar Award, a fellow of the ASA and the IMS, and a Web of Science Highly Cited Researcher.  She was an invited speaker at the 2018 International Congress of Mathematicians and a 2019 IMS Medallion lecturer.

Refreshments: 3:30-4:00, outside Baker Hall 232M

For More Information, Please Contact: