Community Detection

This post summarizes Google’s 2017 KDD paper Ego-Splitting Framework: from Non-Overlapping to Overlapping Clusters. Why Non-Overlapping Clustering Falls Short Real-world networks tend to have plenty of medium-sized communities (roughly 100 members), and a single node frequently belongs to several of them at once. Non-overlapping clustering algorithms assign each node to exactly one community, so they simply can’t capture that structure. Algorithms that attempt overlapping clustering already existed, but most were either too complex, too inflexible, or lacked theoretical guarantees. ...

Community detection is the problem of finding sets of densely connected nodes, communities, inside a graph. Think of it as a form of clustering. Methods like GraphRAG use exactly this technique to break a knowledge graph into manageable pieces. This post covers where modularity, the most widely used metric in community detection, comes from, and how the two algorithms most commonly used to optimize it, Louvain and Leiden, differ. Modularity: Measuring How Well-Formed a Community Is Say you’ve formed a community. What does it mean for that community to be “good”? The most common answer in community detection is a metric called modularity. The intuition is simple: compute how many edges you’d expect inside this community if the graph’s edges were wired up completely at random, then measure how far the actually observed edge count exceeds that expectation. If the connections are too dense to explain away as coincidence, that’s evidence you’ve found a real community. ...