Finding Planted Cliques in Erdős–Rényi Random Graphs: Improving previous methods and expanding applications

Sochinski, Megan

Undergraduate Honors Thesis

Finding Planted Cliques in Erdős–Rényi Random Graphs: Improving previous methods and expanding applications Public Deposited

Analytics

Download PDF

Citations

Citeable URL: https://scholar.colorado.edu/concern/undergraduate_honors_theses/qn59q451q

Abstract

In this paper, we will discuss new methods for finding planted cliques within Erdős–Rényi random graphs. An Erdős–Rényi random graph is a graph with n vertices, where each vertex is connected to each other vertex with some probability p, independent of all other choices. The planted clique problem asks us to find the most efficient way to find a planted clique in an Erdős–Rényi random graph. A planted clique is a secretly chosen set of vertices in the graph that are purposefully connected with edges added to the graph until all of the selected vertices are connected. There are many other similar problems which have been posed and examined, regarding finding patterns in random graphs or matrices. This paper will begin briefly by discussing previous methods for finding planted cliques in Erdős–Rényi random graphs. It will then present two algorithms for finding planted cliques, one which finds any number of disjoint cliques, and another which finds only one planted clique. Disjoint implies that none of the points can be included in more than one clique. The paper will then prove theorems that state that these algorithms will find such planted cliques, under certain assumptions on some parameters. These theorems are the main results of the paper, and the algorithms can be run in polynomial time. Finally, the paper will discuss the improvements made using these algorithms over previous methods, such as the fact that it is no longer necessary to know the size of a planted clique to find it, and suggest areas of future research.

Creator