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:
Notes
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
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 |