Dataset-CommunityDetection

Datasets used in the work https://arxiv.org/abs/2412.13160.

Use of dataset

The datasets are released under MIT license. Please, use the following BibTex entry for citation:

@misc{umeano2024quantumcommunitydetectiondeterministic,
      title={Quantum community detection via deterministic elimination}, 
      author={Chukwudubem Umeano and Stefano Scali and Oleksandr Kyriienko},
      year={2024},
      eprint={2412.13160},
      archivePrefix={arXiv},
      primaryClass={quant-ph},
      url={https://arxiv.org/abs/2412.13160}, 
}

Preprint abstract

We propose a quantum algorithm for calculating the structural properties of complex networks and graphs. The corresponding protocol -- deteQt -- is designed to perform large-scale community and botnet detection, where a specific subgraph of a larger graph is identified based on its properties. We construct a workflow relying on ground state preparation of the network modularity matrix or graph Laplacian. The corresponding maximum modularity vector is encoded into a log(N)-qubit register that contains community information. We develop a strategy for ``signing'' this vector via quantum signal processing, such that it closely resembles a hypergraph state, and project it onto a suitable linear combination of such states to detect botnets. As part of the workflow, and of potential independent interest, we present a readout technique that allows filtering out the incorrect solutions deterministically. This can reduce the scaling for the number of samples from exponential to polynomial. The approach serves as a building block for graph analysis with quantum speed up and enables the cybersecurity of large-scale networks.