On the complexity of quantum link prediction in complex networks.

ABSTRACT: Link prediction methods use patterns in known network data to infer which connections may be missing. Previous work has shown that continuous-time quantum walks can be used to represent path-based link prediction, which we further study here to develop a more optimized quantum algorithm. Using a sampling framework for link prediction, we analyze the query access to the input network required to produce a certain number of prediction samples. Considering both well-known classical path-based algorithms using powers of the adjacency matrix as well as our proposed quantum algorithm for path-based link prediction, we argue that there is a polynomial quantum advantage on the dependence on N, the number of nodes in the network. We further argue that the complexity of our algorithm, although sub-l

SUBMITTER: Moutinho JP 

PROVIDER: S-EPMC10781705 | biostudies-literature | 2024 Jan

REPOSITORIES: biostudies-literature