Distributed discovery of large near-cliques

ABSTRACT

Given an undirected graph and 0 ≤ ε ≤ 1, a set of nodes is called ε-near clique if all but an ε fraction of the pairs of nodes in the set have a link between them. In this paper we present a fast synchronous network algorithm that uses small messages and finds a near-clique. Specifically, we present a constant-time algorithm that finds, with constant probability of success, a linear size ε-near clique if there exists an ε³-near clique of linear size in the graph. The algorithm uses messages of O(log n) bits. The failure probability can be reduced to n^−Ω(1) in O(log n) time, and the algorithm also works if the graph contains a clique of size Ω(n/log^α log n) for some α ∈ (0,1). Our approach is based on a new idea of adapting property testing algorithms to the distributed setting.

REFERENCES

• 1: Stefano Basagni , Michele Mastrogiovanni , Alessandro Panconesi , Chiara Petrioli, Localized Protocols for Ad Hoc Clustering and Backbone Formation: A Performance Comparison, IEEE Transactions on Parallel and Distributed Systems, v.17 n.4, p.292-306, April 2006 [doi>10.1109/TPDS.2006.52]
• 2: Z. Brakerski and B. Patt-Shamir. Distributed discovery of large near cliques. Technical report, 2009. http://arxiv.org/abs/0905.4147.
• 3: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 4: Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998 [doi>10.1145/285055.285060]
• 5: R. Gupta and J. Walrand. "Approximating maximal cliques in ad-hoc networks". In Proc. IEEE Int. Symp. on Personal, Indoor and Mobile Radio Communications, pages 365--369, Barcelona, Sept. 2004.
• 6: Ravi Kumar , Jasmine Novak , Prabhakar Raghavan , Andrew Tomkins, On the Bursty Evolution of Blogspace, World Wide Web, v.8 n.2, p.159-178, June 2005 [doi>10.1007/s11280-004-4872-4]
• 7: R. Lempel , S. Moran, SALSA: the stochastic approach for link-structure analysis, ACM Transactions on Information Systems (TOIS), v.19 n.2, p.131-160, April 2001 [doi>10.1145/382979.383041]
• 8: Huy N. Nguyen , Krzysztof Onak, Constant-Time Approximation Algorithms via Local Improvements, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.327-336, October 25-28, 2008 [doi>10.1109/FOCS.2008.81]
• 9: Michal Parnas , Dana Ron, Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms, Theoretical Computer Science, v.381 n.1-3, p.183-196, August, 2007 [doi>10.1016/j.tcs.2007.04.040]
• 10: Michael Saks , C. Seshadhri, Parallel monotonicity reconstruction, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.962-971, January 20-22, 2008, San Francisco, California

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Theory

Keywords:
clique, communication networks, property testing, randomized algorithms