Community Detection: Finding Groups

The Friend Circles Your Phone Already Knows About

Open Instagram or WhatsApp and look at the people you know. Nobody sorted them into folders, but if you look closely they already form clumps: your class friends, your cousins, your cricket coaching batch, maybe three strangers you keep bumping into in the comments of the same meme page. You never told the app any of this, yet when it suggests "people you may know," it is oddly good at staying inside the right clump. That is not a coincidence and it is not magic. It is a graph algorithm called community detection, and by the end of this chapter you will have computed, by hand, the exact numbers such an algorithm uses to find those clumps.

The same trick shows up far beyond friend suggestions. Banks and payment platforms build a graph out of every UPI transaction (accounts are nodes, payments are edges) and look for tight little clusters of accounts that mostly pay each other and almost nobody else. A cluster like that, especially among freshly opened accounts, is a classic signature of a mule-account ring set up to launder stolen money, and it stands out precisely because it behaves like a community. Streaming platforms group viewers with similar taste so that a recommendation trained on one member of a cluster works for the rest of it. Public health teams building contact-tracing graphs during a disease outbreak look for dense clusters of contacts, so that testing and quarantine effort can be aimed at a hostel wing or a marketplace instead of an entire district. All of these are the same underlying question: given a graph, which sets of nodes form close-knit groups, without anyone telling you the groups in advance?

Groups Inside a Graph

Recall the basics: a graph is a set of nodes (or vertices) connected by edges, and the degree of a node is how many edges touch it. What is new in this chapter is the idea of a community: informally, a group of nodes that are densely connected to each other and only sparsely connected to nodes outside the group. That definition is deliberately fuzzy, because unlike a shortest path or a minimum spanning tree, a community does not have one single correct mathematical definition. What we do have are precise ways to score how good a proposed grouping is, and reasonably fast algorithms that search for groupings scoring well. That is the whole game in this chapter: define a score, then search for a grouping that pushes it as high as possible.

Why Connected Components Aren't Enough

Your first instinct might be to just find the connected components of the graph (the pieces reachable from each other via the flood-fill BFS/DFS approach from earlier chapters). That works when groups are truly separate. It fails the moment even one edge joins them, because then the whole graph collapses into a single connected component, hiding the structure inside it.

Here is a graph small enough to reason about entirely by hand. Six students in Class 10-A: Aarav, Bhavna and Chetan sit together and are inseparable; Divya, Esha and Farhan are a separate, equally tight trio. The only link between the two trios is that Chetan and Divya are lab partners in the school Science Club, so they talk to each other too. As a list of friendships (edges):

• Aarav - Bhavna
• Bhavna - Chetan
• Aarav - Chetan
• Divya - Esha
• Esha - Farhan
• Divya - Farhan
• Chetan - Divya

Run connected-components on this and you get one component containing all six people, technically correct but useless as a description of the social reality. Anyone looking at the list can see two obvious circles: {Aarav, Bhavna, Chetan} and {Divya, Esha, Farhan}, joined by exactly one cross-circle edge. Inside each circle, every possible pair is friends: three edges among three people, a triangle. Between the circles, out of the 3 × 3 = 9 possible cross-pairings, only one, Chetan and Divya, is actually an edge. That contrast (lots of edges inside, almost none across) is exactly what "community" is trying to capture, and it is what an algorithm needs to detect automatically on graphs far too big to eyeball.

Finding the Bridge: Edge Betweenness Centrality

Notice that the Chetan-Divya edge is special in a specific, measurable way: it is the only route between the two circles, so every shortest path from anyone in Aarav's circle to anyone in Divya's circle has to cross it. An edge that carries a disproportionate share of the graph's shortest paths is called high in edge betweenness centrality. Formally, the betweenness of an edge is the number of shortest paths, counted over every pair of nodes in the graph, that pass through that edge; when a pair has several equally short paths, each one contributes a fractional share so the total still adds up to exactly one per pair.

This observation is the basis of the Girvan-Newman algorithm, developed in the early 2000s by physicists Michelle Girvan and Mark Newman: repeatedly find the edge with the highest betweenness, delete it, and watch the graph fall apart into communities, because the edges with the highest betweenness act like "bridges" stitching separate clusters together.

Let's compute betweenness by hand for all seven edges in the Class 10-A graph.

• Chetan-Divya: every cross-circle pair (3 people on Aarav's side times 3 people on Divya's side, 9 pairs in total) has its one and only shortest path routed through this single connecting edge, since there is no other way across. Betweenness = 9.
• Aarav-Chetan: this edge carries the Aarav-Chetan pair itself (1), plus every cross-circle journey that starts at Aarav, since it must reach Chetan before it can cross the bridge: Aarav to Divya, Aarav to Esha, Aarav to Farhan (3 more). Total = 4.
• Bhavna-Chetan: the same reasoning from Bhavna's side. Total = 4.
• Divya-Esha: mirrors Aarav-Chetan on the other side of the bridge: the Divya-Esha pair itself, plus Esha's three cross-circle journeys (to Aarav, Bhavna, Chetan) that must reach Divya first. Total = 4.
• Divya-Farhan: the same reasoning for Farhan. Total = 4.
• Aarav-Bhavna: purely local. Going the long way around the triangle, Aarav to Chetan to Bhavna, is two steps against the direct edge's one step, so nothing ever needs to detour through it. It only carries its own pair. Betweenness = 1.
• Esha-Farhan: purely local, by the same argument. Betweenness = 1.

As a check, these seven scores add up to 9 + 4 + 4 + 4 + 4 + 1 + 1 = 27, which is exactly the sum of the shortest-path lengths of all fifteen pairs of students in the graph; each pair's path of length L contributes L units of betweenness, one to every edge it crosses, so the two totals have to match. The Chetan-Divya edge, at 9, towers over everything else, more than double its nearest competitor. Delete it, and the graph splits into precisely {Aarav, Bhavna, Chetan} and {Divya, Esha, Farhan}: the two friend circles, recovered without anyone telling the algorithm who was friends with whom.

In this particular graph, Chetan-Divya also happens to be a bridge in the strict graph-theory sense, an edge whose removal increases the number of connected components. That will not always be true in denser, messier real graphs, where two communities might be connected by several edges rather than one. Edge betweenness still works in that setting: it generalises the bridge idea, because the small set of edges connecting two dense clusters carries a disproportionate share of shortest paths even when no single one of them is a strict bridge on its own.

Checking It in Code

The hand calculation above generalises directly into a short Python program: run a breadth-first search from every node to get shortest distances and predecessors, reconstruct every shortest path between every pair, and tally how often each edge appears.

from collections import deque

graph = {
    'Aarav':  ['Bhavna', 'Chetan'],
    'Bhavna': ['Aarav', 'Chetan'],
    'Chetan': ['Aarav', 'Bhavna', 'Divya'],
    'Divya':  ['Chetan', 'Esha', 'Farhan'],
    'Esha':   ['Divya', 'Farhan'],
    'Farhan': ['Divya', 'Esha'],
}

def bfs_shortest_paths(graph, start):
    dist = {start: 0}
    parents = {start: []}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbour in graph[node]:
            if neighbour not in dist:
                dist[neighbour] = dist[node] + 1
                parents[neighbour] = [node]
                queue.append(neighbour)
            elif dist[neighbour] == dist[node] + 1:
                parents[neighbour].append(node)     # tie: another shortest path

    return dist, parents

def all_shortest_paths(graph, start, end):
    dist, parents = bfs_shortest_paths(graph, start)
    if end not in dist:
        return []
    def build(node):
        if node == start:
            return [[start]]
        return [path + [node] for p in parents[node] for path in build(p)]
    return build(end)

def edge_betweenness(graph):
    nodes = list(graph.keys())
    scores = {}
    for i, s in enumerate(nodes):
        for t in nodes[i + 1:]:
            paths = all_shortest_paths(graph, s, t)
            if not paths:
                continue
            share = 1 / len(paths)          # split credit when paths tie
            for path in paths:
                for u, v in zip(path, path[1:]):
                    edge = tuple(sorted((u, v)))
                    scores[edge] = scores.get(edge, 0) + share
    return scores

for edge, score in edge_betweenness(graph).items():
    print(edge, score)

Trace bfs_shortest_paths(graph, 'Aarav') by hand and it builds up layer by layer: Aarav is distance 0; Bhavna and Chetan, its direct neighbours, are distance 1; from Chetan we reach Divya at distance 2; from Divya we reach Esha and Farhan at distance 3. No node is ever discovered by two different edges at the same distance, so every parents list ends up with exactly one entry — confirming, as we noticed by hand, that this graph has no tied shortest paths. Running edge_betweenness(graph) over all six nodes reproduces the table from the previous section exactly: Chetan-Divya at 9.0, the four "gateway" edges at 4.0 each, and the two purely local edges at 1.0 each.

Scoring a Split: Modularity

Betweenness tells you which single edge to cut next, but it does not tell you when to stop cutting, or whether the resulting groups are actually good communities rather than an arbitrary chop. For that we need a score for an entire proposed grouping, called modularity, again due to Newman and Girvan.

The idea: take the graph, keep every node's degree exactly as it is, but imagine reconnecting all the edges completely at random, a hypothetical rewiring called a configuration model. In that random version, a high-degree node is more likely to end up connected to another high-degree node purely by chance; there is nothing "communal" about that, it is just popularity. Modularity compares the edges actually observed inside a proposed group against how many that random baseline would predict. If a group has far more internal edges than chance would produce, it is a genuine community; if it is about what chance would produce anyway, it is not.

For a graph with m total edges split into communities, the contribution of one community c to the score is:

contribution of c  =  (edges inside c) / m  -  (sum of degrees inside c / 2m)²

and the overall modularity Q is the sum of this contribution over every community in the proposed grouping. Q is bounded between -0.5 and 1; as a rule of thumb, real networks with clear community structure tend to score somewhere around 0.3 or higher.

Let's compute Q for the Class 10-A graph under two different groupings. First, the grouping already found: {Aarav, Bhavna, Chetan} and {Divya, Esha, Farhan}. There are m = 7 edges in total. Each triangle has 3 internal edges, and the degrees inside each triangle sum to 2 + 2 + 3 = 7 (Aarav and Bhavna each have degree 2; Chetan has degree 3 because of the Science Club link, and symmetrically for Divya's side):

Q ≈ (3/7 - (7/14)²) + (3/7 - (7/14)²)
  ≈ (0.4286 - 0.25) + (0.4286 - 0.25)
  ≈ 0.1786 + 0.1786
  ≈ 0.357

Now compare that against a deliberately worse grouping, say {Aarav, Bhavna} and {Chetan, Divya, Esha, Farhan}, which ignores the fact that Chetan really belongs with Aarav and Bhavna:

Q ≈ (1/7 - (4/14)²) + (4/7 - (10/14)²)
  ≈ (0.1429 - 0.0816) + (0.5714 - 0.5102)
  ≈ 0.0612 + 0.0612
  ≈ 0.122

0.357 versus 0.122: modularity clearly prefers the grouping that matches the two real friend circles over the one that arbitrarily reassigns Chetan. This is exactly the signal an algorithm can search over without ever "seeing" the friend circles the way we can. It just hunts for whichever grouping pushes Q as high as possible. Reusing the same graph dictionary from before, a short Python function confirms both numbers:

def modularity(graph, communities):
    m = sum(len(nbrs) for nbrs in graph.values()) // 2
    degree = {node: len(nbrs) for node, nbrs in graph.items()}
    Q = 0.0
    for community in communities:
        internal = sum(1 for u in community for v in graph[u] if v in community)
        internal //= 2                      # each internal edge counted from both ends
        total_degree = sum(degree[u] for u in community)
        Q += internal / m - (total_degree / (2 * m)) ** 2
    return Q

natural = [{'Aarav', 'Bhavna', 'Chetan'}, {'Divya', 'Esha', 'Farhan'}]
mixed   = [{'Aarav', 'Bhavna'}, {'Chetan', 'Divya', 'Esha', 'Farhan'}]

print(round(modularity(graph, natural), 3))   # 0.357
print(round(modularity(graph, mixed), 3))     # 0.122

The Full Girvan-Newman Algorithm

Betweenness and modularity combine into one complete algorithm:

• Step 1: Compute edge betweenness for every edge in the current graph.
• Step 2: Remove the edge (or edges, if tied) with the highest betweenness.
• Step 3: Record the connected components at this point as a candidate grouping, and compute its modularity.
• Step 4: If any edges remain, recompute betweenness on the reduced graph and repeat from Step 2.
• Step 5: Out of every candidate grouping produced along the way, keep the one with the highest modularity.

Each removal potentially splits off a new piece, so this process traces out a hierarchy of groupings, from the whole graph as one giant community down to every node isolated on its own, a structure usually drawn as a tree called a dendrogram. Modularity is what tells you where along that hierarchy to actually cut and call it done. In the six-person example, the very first removal already reaches the peak: no other split of this graph scores higher than 0.357.

The catch is cost. Computing edge betweenness across a whole graph efficiently takes roughly O(mn) time using standard algorithms, and Girvan-Newman recomputes it after every single edge removal, so the total cost climbs to roughly O(m²n) — fine for a six-person friend graph, painfully slow for a graph with millions of nodes, like a country's actual UPI transaction network or a national mobile-phone call graph.

Doing It at Scale: The Louvain Method

For large graphs, practitioners reach for the Louvain method instead, published by Vincent Blondel and colleagues in 2008. It optimises modularity directly, without ever computing a single shortest path, by alternating two phases:

• Local moving: start with every node in its own one-node community. Visit each node in turn and check whether moving it into a neighbouring community would raise the overall modularity; if the best available move helps, make it. Keep sweeping over all the nodes until no single move improves Q any further.
• Aggregation: collapse every community found in the local-moving phase into one "super-node." Edges between two communities become a single weighted edge between their super-nodes; edges inside a community become a self-loop carrying that internal edge count.

Repeat both phases on the shrinking, coarser graph until modularity stops improving. Because each pass only looks at a node's immediate neighbours rather than every shortest path in the graph, Louvain runs close to linear time in the number of edges, which is why it comfortably handles networks with millions of nodes (social graphs, telecom call graphs, transaction networks) where Girvan-Newman would never finish. Applied to the Class 10-A graph, local moving would quickly notice that grouping Chetan with Aarav and Bhavna, and Divya's side into its own group, both raise modularity, converging on the same two triangles found earlier through careful edge-cutting, only this time reached by fast local nudges instead of a global betweenness search. A newer refinement called the Leiden algorithm, introduced by Vincent Traag, Ludo Waltman and Nees Jan van Eck in 2019, fixes a subtle flaw in Louvain where a detected "community" can occasionally end up internally disconnected, while keeping the same speed.

Where This Shows Up

The canonical test case for every community-detection algorithm, including the original Girvan-Newman paper, is a real, small social network: Wayne Zachary's study of a university karate club from the 1970s, 34 members and 78 friendships, which famously split into two factions after a dispute between the club's instructor and its administrator over the price of lessons. Decades later it is still the graph every new algorithm gets tested against first, because the "correct" split is independently known from the real-world fallout, a rare case where the ground truth for community detection is not in dispute.

Beyond that benchmark, the same machinery runs quietly behind several everyday systems. Banks and payment processors scan transaction graphs for clusters of accounts trading heavily among themselves and barely at all with the outside world, a strong indicator of a mule-account ring assembled to launder money through UPI or card networks. Streaming and e-commerce platforms cluster users with overlapping tastes so that "customers like you also liked" recommendations pull from the right community rather than the entire user base. Social platforms use community structure to shape "people you may know" suggestions, since two people who share many mutual community members are far more likely to actually know each other than two random users. Public health agencies building contact-tracing graphs during an outbreak look for dense clusters of contacts so that testing and quarantine resources can be aimed at the cluster driving transmission instead of an entire district.

Two Honest Limitations

Modularity maximisation is powerful but not perfect. Santo Fortunato and Marc Barthélemy showed in 2007 that it suffers from a resolution limit: in a large enough network, several small, genuinely dense communities can score higher on modularity when merged into one bigger detected group than when correctly kept separate, simply because the network as a whole is big. A ten-person study group is a real community inside a college of ten thousand students, but modularity maximisation, applied blindly at that scale, can fail to notice it.

The other limitation is structural: every method in this chapter assigns each node to exactly one community. Real people do not work that way: Chetan belongs to Aarav and Bhavna's friend circle and to the Science Club at the same time, and a modularity-maximising partition has to pick a side. Detecting these overlapping communities is an active, more advanced extension of the ideas in this chapter, beyond what we cover here, but it is worth knowing the limitation exists before treating a clean community-detection output as the final word on how a real social group is organised.

Back to Your Followers List

Every idea in this chapter reduces to the same recipe: define what makes a group dense inside and sparse outside using modularity, then search for a grouping that maximises it, either by repeatedly cutting the highest-betweenness edge in Girvan-Newman fashion, or by fast greedy local moves in Louvain fashion. Next time your phone suggests a "person you may know" who you have genuinely never messaged but who sits inside your exact friend circle, or a bank's fraud system flags a tight little ring of UPI accounts nobody asked it to look for, you now know the graph math running underneath: find the edges that act as bridges between groups, weigh them against a random-chance baseline, and let the numbers show you the circles that were there all along.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where community detection: finding groups is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting community detection: finding groups to at least 3 other topics you have studied.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind community detection: finding groups, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.