Searching for a k-Clique in Unknown Graphs

Authors

  • Roni Stern Ben Gurion University of the Negev
  • Meir Kalech Ben Gurion University of the Negev
  • Ariel Felner Ben Gurion University of the Negev

DOI:

https://doi.org/10.1609/socs.v1i1.18175

Keywords:

Heuristic search, Clique, Unknown graphs, Online algorithms

Abstract

Agents that solve problems in unknown graphs are usually required to iteratively explore parts of the graph. In this paper we research the problem of finding a k-clique in an unknown graph while minimizing the number of required exploration actions. Two novel heuristics Known Degree and Clique* are proposed to reduce the required exploration cost by carefully choosing which part of the environment to explore. We further investigate the problem by adding probabilistic knowledge of the graph and propose an Markov Decision Process(MDP) and a Monte Carlo based heuristic (RClique*) that uses knowledge of edge probabilities to reduce the required exploration cost. We demonstrate the efficiency of the proposed approaches on simulated random and scale free graphs as well as on real online web crawls.

Downloads

Published

2010-08-25