An Introduction to Graph Partitioning Algorithms and Community Detection

Graph partitioning has been a long-lasting problem and has a wide range of applications. This post shares the methodology for graph partitioning with both theoretical explanations and practical implementations of some popular graph partitioning algorithms with python codes. "Clustering" can be confusing under different contexts. In this article, clustering means node clustering, i.e. partitioning the graphs into clusters (or communities). We use graph partitioning, (node) clustering, and community detection interchangeably. In other words, we do not consider overlapping communities anywhere in this article.