DAOC: Stable Clustering of Large Networks
  Clustering is a crucial component of many data mining systems involving the
analysis and exploration of various data. Data diversity calls for clustering
algorithms to be accurate while providing stable (i.e., deterministic and
robust) results on arbitrary input networks. Moreover, modern systems often
operate with large datasets, which implicitly constrains the complexity of the
clustering algorithm. Existing clustering techniques are only partially stable,
however, as they guarantee either determinism or robustness. To address this
issue, we introduce DAOC, a Deterministic and Agglomerative Overlapping
Clustering algorithm. DAOC leverages a new technique called Overlap
Decomposition to identify fine-grained clusters in a deterministic way
capturing multiple optima. In addition, it leverages a novel consensus
approach, Mutual Maximal Gain, to ensure robustness and further improve the
stability of the results while still being capable of identifying micro-scale
clusters. Our empirical results on both synthetic and real-world networks show
that DAOC yields stable clusters while being on average 25% more accurate than
state-of-the-art deterministic algorithms without requiring any tuning. Our
approach has the ambition to greatly simplify and speed up data analysis tasks
involving iterative processing (need for determinism) as well as data
fluctuations (need for robustness) and to provide accurate and reproducible
results.
