Abstract
We describe techniques that are useful for the detection of dense subgraphs (quasi-cliques) in massive sparse graphs whose vertex set, but not the edge set, fits in RAM. The algorithms rely on efficient semi-external memory algorithms used to preprocess the input and on greedy randomized adaptive search procedures (GRASP) to extract the dense subgraphs. A software platform was put together allowing graphs with hundreds of millions of nodes to be processed. Computational results illustrate the effectiveness of the proposed methods.
Work completed as an AT&T consultant and DIMACS visitor.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J. Abello, P. Pardalos and M. Resende, editors. Handbook of Massive Data Sets, Kluwer Academic Publishers, 2002.
J. Abello, A. Bushbaum, and J. Westbrook. A functional approach to external memory algorithms. In European Symposium on Algorithms, volume 1461 of Lecture Notes in Computer Science, pages 332–343. Springer-Verlag, 1998.
J. Abello and J. Vitter, editors. External Memory Algorithms, volume 50 of DIMACS Series on Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 1999.
S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. Proc. 33rd IEEE Symp. on Foundations of Computer Science, pages 14–23, 1992.
S. Arora and S. Safra. Probabilistic checking of proofs: A new characterization of NP. J. of the ACM, volume 45, pages 70–122, 1998.
U. Feige, S. Goldwasser, L. Lovász, S. Safra, and M. Szegedy. Approximating the maximum clique is almost NP-complete. In Proc. 32nd IEEE Symp. on Foundations of Computer Science, pages 2–12, 1991.
T.A. Feo and M.G.C. Resende. A probabilistic heuristic for a computationally dificults et covering problem. Operations Research Letters, volume 8, pages 67–71, 1989.
F. Glover. Tabu search. PartI. ORSA J. Comput., volume 1, pages 190–206, 1989.
J. Håstad, Clique is hard to approximate within n 1-∈. Acta Mathematica, volume 182, pages 105–142, 1999.
J. H. Holland. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI, 1975.
S. Kirkpatrick, C. D. Gellat Jr., and M. P. Vecchi. Optimization by simulated annealing. Science, volume 220, 671–680, 1983.
L.S. Pitsoulis and M.G.C. Resende. Greedy randomized adaptive search procedures. In P. M. Pardalos and M. G. C. Resende, editors, Handbook of Applied Optimization. Oxford University Press, pages 168–182, 2002.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Abello, J., Resende, M.G.C., Sudarsky, S. (2002). Massive Quasi-Clique Detection. In: Rajsbaum, S. (eds) LATIN 2002: Theoretical Informatics. LATIN 2002. Lecture Notes in Computer Science, vol 2286. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45995-2_51
Download citation
DOI: https://doi.org/10.1007/3-540-45995-2_51
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43400-9
Online ISBN: 978-3-540-45995-8
eBook Packages: Springer Book Archive