REU for OAC grant, on Community Structure Detection in Large Networks

Instructors: George Chacko and Tandy Warnow

Textbook and course materials Most of the reading assignments will be to journal papers (see the current list); these will be part of the homework assignments. However, we will also use as a basic reference (textbook) Mining Complex Networks, second edition. If you have trouble accessing this second edition, you can see the first edition at Mining Complex Networks, published by Chapman and Hall, 2021. You should be able to download this by using your UIUC affiliation. For this textbook, we will mainly use material from Chapters 1-3, 5, 6, and 8.

Lectures: We will review a subset of the lectures that I presented in CS 598 - Graph Algorithms (see this page). You are expected to read these before coming to the meeting.

Homework Most of the homework is assigned reading or data analysis.

• May 19. Reading assignment: the PDF for Jan 20, 2026.
• May 20. Reading assignment: the PDF for Jan 22, 2026.
• May 21. Reading assignment: the PDF for Jan 27, 2026.
• May 22.
  • Reading assignment: Yang, J. and Leskovec, J., 2012, August. Defining and evaluating network communities based on ground-truth. In Proceedings of the ACM SIGKDD workshop on mining data semantics (pp. 1-8).
  • Run Leiden-CPM with resolution parameter 0.01 on the Orkut network. Report empirical statistics.
• May 25: no assignment (holiday)
• May 26: no assignment
• May 27. Reading assignments
  • Park et al., Well-connectedness and community detection.
  • the PDF for Jan 29, 2026.
• May 28
  • Use NetworKit to compute empirical statistics for the cit\_hepph
    • Number of nodes
    • Number of edges
    • Indegree distribution
    • Outdegree distribution
    • Average local clustering coefficient
    • Global local clustering coefficient
    • Diameter
• May 29
  Write up a report in latex (without using AI) about the analyses you did.

Course description:

Specific topics we will cover:

• Random graph models, with particular attentoin to Stochastic Block Models
• Community detection (aka graph partitioning)
• Community search
• Synthetic networks, and evaluating community detection methods
• The resolution limit (starting with Fortunato and Barthelemy)
• Properties of large real-world networks
• Performance (computational and accuracy) of methods on large networks
• Agent-based models

Our research in this field We work in network science and its relevance to understanding the development of scientific communities, with papers that range from pure theory to development of new algorithms and software to analyses of citation networks. See this page for more about our collaboration, which is funded by an NSF grant from the Office of Advanced Cyber-Infrastucture (OAC 2402559).

Other papers to read For other papers to read in the scientific literature, see the current list.