Community Detection
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. ...