CAM Colloquium: Nate Veldt (CAM Postdoc) - Detecting and Learning Community Structure in Graphs with LambdaCC

Description

Abstract:
Graph clustering is the somewhat ill-defined task of separating a graph into so-called communities of nodes that share many edges with each other but few edges with the rest of the graph. But what do "many" and "few" mean in this context? We discuss several combinatorial objective functions for graph clustering, each of which strikes a different balance between finding clusters with (1) many internal edges and (2) few external edges. We then present a more flexible framework for graph clustering called LambdaCC, which detects different types of communities in a graph by varying a resolution parameter lambda. LambdaCC generalizes and interpolates between several previous clustering objective functions and comes with new approximation algorithms. We then outline a technique for learning how to set lambda in order to match different types of community structure that one might wish to detect in practice.

Bio:
Nate Veldt is a postdoctoral associate in the Center for Applied Math at Cornell University. He received his PhD from Purdue University, where he was advised by Professor David Gleich. Nate’s research is in algorithm design, optimization, and machine learning for network science.