2015 ScalableLargeNearCliqueDetectio

• (Mitzenmacher et al., 2015) ⇒ Michael Mitzenmacher, Jakub Pachocki, Richard Peng, Charalampos Tsourakakis, and Shen Chen Xu. (2015). “Scalable Large Near-Clique Detection in Large-Scale Networks via Sampling.” In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783385

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222015%22+Scalable+Large+Near-Clique+Detection+in+Large-Scale+Networks+via+Sampling
• http://dl.acm.org/citation.cfm?id=2783258.2783385&preflayout=flat#citedby

Quotes

Author Keywords

• Dense subgraphs; graph algorithms; graph mining; near-clique extraction

Abstract

Extracting dense subgraphs from large graphs is a key primitive in a variety of graph mining applications, ranging from mining social networks and the Web graph to bioinformatics [41]. In this paper we focus on a family of poly-time solvable formulations, known as the k-clique densest subgraph problem (k-Clique-DSP) [57]. When k =2, the problem becomes the well-known densest subgraph problem (DSP) [22, 31, 33, 39]. Our main contribution is a sampling scheme that gives densest subgraph sparsifier, yielding a randomized algorithm that produces high-quality approximations while providing significant speedups and improved space complexity. We also extend this family of formulations to bipartite graphs by introducing the (p,q)- biclique densest subgraph problem ((p, q) - Biclique-DSP), and devise an exact algorithm that can treat both clique and biclique densities in a unified way.

As an example of performance, our sparsifying algorithm extracts the 5-clique densest subgraph -- which is a large-near clique on 62 vertices -- from a large collaboration network. Our algorithm achieves 100% accuracy over five runs, while achieving an average speedup factor of over 10,000. Specifically, we reduce the running time from ∼2 107 seconds to an average running time of 0.15 seconds. We also use our methods to study how the k - clique densest subgraphs change as a function of time in time-evolving networks for various small values of k. We observe significant deviations between the experimental findings on real-world networks and stochastic Kronecker graphs, a random graph model that mimics real-world networks in certain aspects.

We believe that our work is a significant advance in routines with rigorous theoretical guarantees for scalable extraction of large near-cliques from networks.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 ScalableLargeNearCliqueDetectio	Michael Mitzenmacher Charalampos Tsourakakis Jakub Pachocki Richard Peng Shen Chen Xu			Scalable Large Near-Clique Detection in Large-Scale Networks via Sampling				10.1145/2783258.2783385		2015