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 can’t capture that structure.

Algorithms that attempt overlapping clustering already existed, but most were either too complex, too inflexible, or lacking in theoretical guarantees.

There’s a subtler problem too. At the level of the whole graph, a single hub node can pull otherwise unrelated groups into one giant community. Picture running community detection on a social network’s follow graph. Elon Musk is a businessman, a politician, and a scientist all at once. Cluster around him, and groups that barely overlap in reality (business leaders, politicians, scientists) can end up merged into a single community purely because of his presence.

Background: The Ego-Net

The concept the paper builds on is the ego-net. For a node $u$, its ego-net ($G[N_u]$) is the induced subgraph made up only of $u$’s direct (1-hop) neighbors, $N_u$. $u$ itself is excluded.

The induced subgraph concept is worth pinning down too. For a subset of nodes $S$ within a graph $G$, the induced subgraph $G[S]$ satisfies two properties: its node set is exactly $S$, and only edges between nodes within $S$ count; anything leaving $S$ is dropped.

The non-overlapping clustering algorithm $A$ the paper works with takes a graph $G$ and partitions its nodes into $A(G) = (V_1, ..., V_t)$. Any two distinct clusters $V_i$ and $V_j$ must not overlap ($V_i \cap V_j = \emptyset$), and every node must belong to exactly one cluster ($V_1 \cup ... \cup V_t = V$). The authors note that any non-overlapping clustering algorithm can slot in here; the paper itself uses a label propagation algorithm based on the Absolute Potts Model, chosen for its high scalability in distributed processing over large graphs and because prior ego-net research had already relied on the same approach.

The Core Idea: Splitting an Ego

The paper’s central insight is simple: apply a non-overlapping clustering algorithm locally, node by node, and use the results to construct overlapping clusters.

Back to the Elon Musk example: the idea is to split his ego into one persona per community he belongs to. Building the business-leader community pulls in one persona (a1); building the politician community pulls in a different persona (a2). The algorithm breaks into two stages: Local Ego-Net Analysis and Global Graph Partitioning.

Local Ego-Net Analysis

First, compute the ego-net $G[N_u]$ for every node $u$. Then apply a non-overlapping clustering algorithm $A^l$ to that ego-net, splitting $u$’s neighbors into partitions:

$$A^l(G[N_u]) = \{N^1_u, N^2_u, ..., N^t_u\}, \quad t_u = np(A^l, G[N_u])$$

For each resulting partition, create a copy of the original node $u$, called a persona.

Once every persona is created, remove the original node $u$ from the graph. Repeat this across every node in the graph, and the result is a new graph: the persona graph.

Global Graph Partitioning

Now apply a non-overlapping clustering algorithm $A^g$ again, this time to the persona graph. Map the resulting persona-node clusters back to their original nodes, and you get overlapping clusters, since a single original node can now belong to more than one.

The whole pipeline: split each node’s ego locally into one persona per community it touches, expanding the graph; run ordinary non-overlapping clustering on that expanded graph a second time; then fold the personas back down to their original nodes. This produces overlapping clusters by applying non-overlapping clustering at two stages, without changing the underlying algorithm.

Why This Matters

The biggest advantage is that it reduces a hard problem, overlapping clustering, to a well-understood one, non-overlapping clustering, using proven algorithms as-is. That comes with real flexibility: any non-overlapping clustering algorithm works as the underlying engine.

The structure also fits large-scale distributed processing environments like MapReduce well. In the reported experiment, a 100x increase in graph size only costs about a 10x increase in runtime.

The results back this up. Against DEMON, a representative existing ego-net-based overlapping clustering algorithm, the framework wins by a wide margin on benchmarks,

and it comes out on top in experiments on real-world graph datasets as well.

Wrap-up

Ego-Splitting reuses non-overlapping clustering to find overlapping communities. Splitting each node into personas lets the framework use familiar clustering algorithms at both the local and global stages.