University of Twente Student Theses
Algorithms for planted clique recovery in random geometric graphs.
Zhang, S. (2020) Algorithms for planted clique recovery in random geometric graphs.
|
PDF
1MB |
| Abstract: | Let G(n, r) be a random geometric graph. A random geometric graph is an undirected graph that has edges between vertices if and only if the vertices are close enough. We assume the number of points in the random geometric graph to be n and the points are randomly placed in a two dimensional unit square torus. Let r be the neighborhood radius such that vertices within radius r of each other are connected. We select k points out of n points from the random geometric graph. Let the set of k points be denoted by K. We add edges between each pair of vertices in K, such that K becomes a planted clique. In this thesis we investigate the problem of recovering the planted clique K in a random geometric graph G(n,r) for large n. We introduce two methods to almost surely recover the planted clique. One method is based on counting the number of common neighbors between vertex pairs, and is able to solve the problem for a large range of k. Another method is based on the vertex degree of each vertex in the graph, and it is able to solve the problem when k is equal to average degree of vertices in the graph. |
| Item Type: | Essay (Master) |
| Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
| Subject: | 31 mathematics, 54 computer science |
| Programme: | Applied Mathematics MSc (60348) |
| Link to this item: | https://purl.utwente.nl/essays/85090 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page