Technical Report MSC-2019-20

Title: Distributed Detection of Cliques in Dynamic Networks
Authors: Matthias Bonne
Supervisors: Keren Censor-Hillel
PDFCurrently accessibly only within the Technion network
Abstract: Real-world computer networks are dynamic in nature – nodes may join or leave the network at any time, and communication links may appear and disappear constantly. To study the capabilities of such networks, we use a dynamic variant of the CONGEST model of computer networks. In this model, a network is represented as an undirected graph, where each vertex is a computation unit, and each edge is a communication link. Since the network is dynamic, the graph may undergo certain changes during the network’s operation.

One of the fundamental problems in the CONGEST model – and in other models of distributed computer networks – is the detection of certain types of subgraphs in the network. In particular, the problem of detecting triangles and larger cliques has been extensively studied over the years.

This thesis provides an in-depth study of the problem of clique detection, and other related problems, in distributed dynamic networks. We show that different types of changes in the network have very different effects on the amount of resources required to solve many of these problems, and that some problems are fundamentally harder than others. We also show that, perhaps surprisingly, the amount of resources required to solve most of the problems is similar for triangles and for larger cliques.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2019
To the main CS technical reports page

Computer science department, Technion