Skip to main content

Cliques and clubs in temporal graphs

Professor Baski Balasundaram The Wilson Bentley Professor School of Industrial Engineering and Management
University of Houston - Melcher Hall 180

Clique and its graph-theoretic generalization known as a k-club are widely used to represent “tightly knit” clusters in graphs. Clubs are vertex subsets that induce bounded-diameter subgraphs and are a practical cluster model in many applications of graph-based data mining where the “quality” of a cluster is based on pairwise distances or communication latency. In this talk, after reviewing problems that optimize over cliques and clubs in a single graph, we introduce our recent work on extending these ideas to graph sequences (e.g., temporal graphs) and unordered graph collections. We discuss our motivation behind studying these variants and review our recent work on finding cliques and clubs in temporal graphs that satisfy atomicity or persistency constraints.


Dr. Baski Balasundaram is the Wilson Bentley Professor in the School of Industrial Engineering and Management at Oklahoma State University. He received his B.Tech. in Mechanical Engineering from the Indian Institute of Technology–Madras in 2002 and his Ph.D. in Industrial Engineering from Texas A&M University in 2007. He is primarily interested in solving combinatorial optimization problems modeled on networks and applications of integer programming. This has led to work in diverse domains including computational biology, social network analysis, and graph-based data mining, as well as classical areas of operations research like transportation logistics, production-inventory planning, and scheduling. He enjoys teaching topics in optimization at the undergraduate and graduate levels.  Dr. Balasundaram is a recipient several prestigious university-wide awards including the 2022 Regents Distinguished Teaching Award, the 2019 Phoenix Award for Outstanding Faculty, and the 2016 Regents Distinguished Research Award. He is the 2015 recipient of the Award for Excellence in the Teaching of Operations Research from the Institute of Industrial and Systems Engineers His research has been supported by the National Science Foundation, the U.S. Department of Energy, the Air Force Office of Scientific Research, and industry partners. Publications coauthored with his students and other collaborators have appeared in reputed journals including Operations Research, INFORMS Journal on Computing, INFORMS Journal on Optimization, IISE Transactions, and INFORMS Journal on Applied Analytics. He serves on the editorial boards of Networks (Wiley) and Journal of Global Optimization (Springer).