NISQ-ready community detection on weighted graphs using separation-node identification

NISQ-ready community detection on weighted graphs using separation-node identification

Abstract:

An important optimization problem in computer science is the detection of communities. By analyzing networks, so-called communities can be found and important information in many fields – from biology to social structures – can be derived. By weighting individual edges, even more information can be processed than by the mere presence of these edges. However, for community detection on weighted graphs, more factors must be considered as a result. Since this is an NP-hard optimization problem, heuristics are often used to find an acceptable solution faster and more efficiently. One promising approach is the use of quantum computers, as it has already been experimentally shown that they can achieve more efficient results than classical computers in certain domains (e.g., Grover or Shor algorithm). However, since most approaches to community detection using QUBO matrices consume a lot of memory, the goal of this work is to find an approach with a good memory efficiency. To this end, this work presents a promising community detection approach based on the detection and analysis of separation nodes, which has the advantage that the dimensions of the resulting QUBO matrix do not exceed the number of nodes and the matrix itself is as sparse as the adjacency matrix of the graph. These separating nodes are designed to divide the graph when they are removed such that the remaining components are each exactly part of a community. This approach is extended to weighted graphs by determining the probability that an edge is a separating edge based on the information flow of the neighborhood. This approach is tested using synthesized graphs with a fixed ground truth about their communities, to which weights are assigned without changing the community structure.

Translated with www.DeepL.com/Translator (free version)

Author:

Advisors:

Jonas Stein, Jonas Nüßlein, Claudia Linnhoff-Popien

Student Thesis | Published August 2023 | Copyright © QAR-Lab
Direct Inquiries to this work to the Advisors