Seminar
| Parent Program: | |
|---|---|
| Location: | SLMath: Eisenbud Auditorium, Online/Virtual |
Planted clique recovery in geometric graphs
We investigate the problem of identifying planted cliques in random geometric graphs, focusing on two distinct algorithmic approaches: the first based on vertex degrees (VD) and the other on common neighbors (CN). We analyze the performance of these methods under varying regimes of key parameters, namely the average degree of the graph and the size of the planted clique. We demonstrate in which set of parameters the algorithms succeed with high probability, as the graph size increases. Notably, our results reveal that the CN-algorithm significantly outperforms the VD-algorithm. In particular, in the connectivity regime extremely small planted cliques (even edges) are correctly identified by the CN-algorithm, yielding very strong impact on anomaly detection. Finally, our results are confirmed by a series of numerical experiments, showing that the effectiveness of the devised algorithms.
No Notes/Supplements Uploaded