Large maximal cliques enumeration in sparse graphs

ABSTRACT

Here we study a variant of maximal clique enumeration problem by incorporating a minimum size criterion. We describe preprocessing techniques to reduce the graph size. This is of practical interest since enumerating maximal cliques is a computationally hard problem and the execution time increases rapidly with the input size. We discuss basics of an algorithm for enumerating large maximal cliques which exploits the constraint on minimum size of the desired maximal cliques. Social networks are prime examples of large sparse graphs where enumerating large maximal cliques is of interest. We present experimental results on the social network formed by the call detail records of one of the world's largest telecom service providers. Our results show that the preprocessing methods achieve significant reduction in the graph size. We also characterize the execution behaviour of our large maximal clique enumeration algorithm.

REFERENCES

• 1: E. A. Akkoyunlu. The enumeration of maximal cliques of large graphs. SIAM Journal of Computing, 2(1):1--6, March 1973.
• 2: E. Loukakis and C. Tsouros. A depth first search algorithm to generate the family of maximal independent sets of a graph lexicographically. Computing by Springer-Verlog, 27:349--366, 1981.
• 3: K. Makino and T. Uno. New algorithm for enumerating all maximal cliques. In SWAT, pages 668--679, 2004.
• 4: R. E. Osteen and J. T. Tou. A clique-detection algorithm based on neighbourhoods in graph. Intl. Journal of Computer and Information Science, 2(4):257--268, 1973.
• 5: Etsuji Tomita , Akira Tanaka , Haruhisa Takahashi, The worst-case time complexity for generating all maximal cliques and computational experiments, Theoretical Computer Science, v.363 n.1, p.28-42, 25 October 2006 [doi>10.1016/j.tcs.2006.06.015]
• 6: S. Tsukiyama, M. Ide, H. Ariyoshi, and I. Shirakawa. A new algorithm for generating all the maximal independent sets. SIAM Journal of Computing, 6(3):505--517, September 1977.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Performance

Keywords:
filtering, maximal clique