Ego-splitting Framework: from Non-Overlapping to Overlapping Clusters

We propose a new framework called Ego-splitting for detecting
clusters in complex networks which leverage the local structures
known as ego-nets (i.e. the subgraph induced by the neighborhood
of each node) to de-couple overlapping clusters. Ego-splitting is
highly scalable and flexible framework, with provable theoretical
guarantees, that reduce the complex overlapping clustering problem
to a simpler and more amenable non-overlapping (partitioning)
problem. We can solve community detection in graphs with tens
of billions of edges and outperform previous solutions based on
ego-nets analysis.
More precisely, our framework works in two steps: a local ego-
net analysis, and a global graph partitioning. In the local step, we
first partition the nodes’ ego-nets using non-overlapping clustering.
We then use these clusters to split each node of the graph into
its persona nodes that represents the instantiation of the node in
its communities. Then, in the global step, we partition these new
persona nodes to obtain an overlapping clustering of the original
graph.

• Algorithms and Theory

• Data Mining and Modeling