© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

Entropy

A Simplified Quantum Walk Model for Predicting Missing Links of Complex Networks

Wen Liang, Fei Yan, Abdullah M. Iliyasu, Ahmed S. Salama, Kaoru Hirota

Published Oct 28, 2022• 5 citations

Abstract

Prediction of missing links is an important part of many applications, such as friends' recommendations on social media, reduction of economic cost of protein functional modular mining, and implementation of accurate recommendations in the shopping platform. However, the existing algorithms for predicting missing links fall short in the accuracy and the efficiency. To ameliorate these, we propose a simplified quantum walk model whose Hilbert space dimension is only twice the number of nodes in a complex network. This property facilitates simultaneous consideration of the self-loop of each node and the common neighbour information between arbitrary pair of nodes. These effects decrease the negative effect generated by the interference effect in quantum walks while also recording the similarity between nodes and its neighbours. Consequently, the observed probability after the two-step walk is utilised to represent the score of each link as a missing link, by which extensive computations are omitted. Using the AUC index as a performance metric, the proposed model records the highest average accuracy in the prediction of missing links compared to 14 competing algorithms in nine real complex networks. Furthermore, experiments using the precision index show that our proposed model ranks in the first echelon in predicting missing links. These performances indicate the potential of our simplified quantum walk model for applications in network alignment and functional modular mining of protein-protein networks.

DOI: 10.3390/e24111547

Related papers

GCQW: A Quantum Walk Model for Predicting Missing Links of Complex Networks

Wen Liang, Fei Yan, Abdullah M. Iliyasu +1 more

Link prediction remains a challenging pursuit in existing complex networks. Our study proposes a Grover coin driven quantum walk (GCQW) model for prediction of missing edges on complex networks. The GCQW model uses observed probabilities of common neighbours of two nodes as similarity between the nodes. Furthermore, each walk step of the proposed model is determined by a three degree of influence rule. Results of experiments based on the area under the receiver operating characteristic curve (AUC) index demonstrate the proposed model’s performance in eight real complex networks outperforms nine conventional comparison algorithms. Outcomes show that even when the ratio of testing to training is set in the range 0.1∼0.5, our GCQW model maintained a stable and competitive performance in terms of the AUC index. The proposed GCQW model will be expectedly applied in function modular mining of protein-protein interaction networks and friend recommendation of social media.

International Conference on Information Communication and Software Engineering (ICICSE)•Mar 18, 2022•1 citation

Quantum link prediction in complex networks

João P. Moutinho, André Melo, Bruno Coelho Coutinho +2 more

Predicting new links in physical, biological, social, or technological networks has a significant scientific and societal impact. Path-based link prediction methods utilize the explicit counting of even- and odd-length paths between nodes to quantify a score function and infer new or unobserved links. Here, we propose a quantum algorithm for path-based link prediction using a controlled continuous-time quantum walk to encode even and odd path-based prediction scores. Through classical simulations on a few real networks, we confirm that the quantum walk scoring function performs similarly to other path-based link predictors. In a brief complexity analysis we identify the potential of our approach in uncovering a quantum speedup for path-based link prediction.

Physical Review A•Mar 10, 2023•24 citations

Quantum Link Prediction in Complex Networks

João P. Moutinho, André Melo, Bruno Coelho Coutinho +2 more

Predicting new links in physical, biological, social, or technological networks has a significant scientific and societal impact. Path-based link prediction methods utilize explicit counting of even and odd-length paths between nodes to quantify a score function and infer new or unobserved links. Here, we propose a quantum algorithm for path-based link prediction, QLP, using a controlled continuous-time quantum walk to encode even and odd path-based prediction scores. Through classical simulations on a few real networks, we confirm that the quantum walk scoring function performs similarly to other path-based link predictors. In a brief complexity analysis we identify the potential of our approach in uncovering a quantum speedup for path-based link prediction.

arXiv:2112.04768•Dec 9, 2021•3 citations

On the quantum simulation of complex networks

Duarte Magano, João P. Moutinho, Bruno Coelho Coutinho

Quantum walks provide a natural framework to approach graph problems with quantum computers, exhibiting speedups over their classical counterparts for tasks such as the search for marked nodes or the prediction of missing links. Continuous-time quantum walk algorithms assume that we can simulate the dynamics of quantum systems where the Hamiltonian is given by the adjacency matrix of the graph. It is known that such can be simulated efficiently if the underlying graph is row-sparse and efficiently row-computable. While this is sufficient for many applications, it limits the applicability for this class of algorithms to study real world complex networks, which, among other properties, are characterized by the existence of a few densely connected nodes, called hubs. In other words, complex networks are typically not row-sparse, even though the average connectivity over all nodes can be very small. In this work, we extend the state-of-the-art results on quantum simulation to graphs that contain a small number of hubs, but that are otherwise sparse. Hopefully, our results may lead to new applications of quantum computing to network science.

arXiv:2212.06126•SciPost Physics Core•Aug 24, 2023•6 citations

Applications of Quantum Walks in Link Mining

Fei Yan, Wen Liang, Fangyan Dong

This chapter explores the applications of quantum walks in identifying and predicting critical links in complex networks. It covers the Hadamard walk algorithm for mining critical links in static networks and its applications in dynamic unmanned aerial vehicle (UAV) networks, the continuous-time quantum walk algorithm for link prediction, and the simplified quantum walk algorithm for predicting missing links in complex networks.

CRC Press eBooks•Nov 24, 2025•0 citations

On the complexity of quantum link prediction in complex networks

João P. Moutinho, Duarte Magano, Bruno Coelho Coutinho

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-linear in N, is limited by the complexity of performing a quantum simulation of the network's adjacency matrix, which may prove to be an important problem in the development of quantum algorithms for network science in general.

arXiv:2211.16331•Scientific Reports•Jan 10, 2024•12 citations

Prediction of missing links is an important part of many applications, such as friends' recommendations on social media, reduction of economic cost of protein functional modular mining, and implementation of accurate recommendations in the shopping platform. However, the existing algorithms for predicting missing links fall short in the accuracy and the efficiency. To ameliorate these, we propose a simplified quantum walk model whose Hilbert space dimension is only twice the number of nodes in a complex network. This property facilitates simultaneous consideration of the self-loop of each node and the common neighbour information between arbitrary pair of nodes. These effects decrease the negative effect generated by the interference effect in quantum walks while also recording the similarity between nodes and its neighbours. Consequently, the observed probability after the two-step walk is utilised to represent the score of each link as a missing link, by which extensive computations are omitted. Using the AUC index as a performance metric, the proposed model records the highest average accuracy in the prediction of missing links compared to 14 competing algorithms in nine real complex networks. Furthermore, experiments using the precision index show that our proposed model ranks in the first echelon in predicting missing links. These performances indicate the potential of our simplified quantum walk model for applications in network alignment and functional modular mining of protein-protein networks.

Link prediction remains a challenging pursuit in existing complex networks. Our study proposes a Grover coin driven quantum walk (GCQW) model for prediction of missing edges on complex networks. The GCQW model uses observed probabilities of common neighbours of two nodes as similarity between the nodes. Furthermore, each walk step of the proposed model is determined by a three degree of influence rule. Results of experiments based on the area under the receiver operating characteristic curve (AUC) index demonstrate the proposed model’s performance in eight real complex networks outperforms nine conventional comparison algorithms. Outcomes show that even when the ratio of testing to training is set in the range 0.1∼0.5, our GCQW model maintained a stable and competitive performance in terms of the AUC index. The proposed GCQW model will be expectedly applied in function modular mining of protein-protein interaction networks and friend recommendation of social media.

Predicting new links in physical, biological, social, or technological networks has a significant scientific and societal impact. Path-based link prediction methods utilize the explicit counting of even- and odd-length paths between nodes to quantify a score function and infer new or unobserved links. Here, we propose a quantum algorithm for path-based link prediction using a controlled continuous-time quantum walk to encode even and odd path-based prediction scores. Through classical simulations on a few real networks, we confirm that the quantum walk scoring function performs similarly to other path-based link predictors. In a brief complexity analysis we identify the potential of our approach in uncovering a quantum speedup for path-based link prediction.

Predicting new links in physical, biological, social, or technological networks has a significant scientific and societal impact. Path-based link prediction methods utilize explicit counting of even and odd-length paths between nodes to quantify a score function and infer new or unobserved links. Here, we propose a quantum algorithm for path-based link prediction, QLP, using a controlled continuous-time quantum walk to encode even and odd path-based prediction scores. Through classical simulations on a few real networks, we confirm that the quantum walk scoring function performs similarly to other path-based link predictors. In a brief complexity analysis we identify the potential of our approach in uncovering a quantum speedup for path-based link prediction.

Quantum walks provide a natural framework to approach graph problems with quantum computers, exhibiting speedups over their classical counterparts for tasks such as the search for marked nodes or the prediction of missing links. Continuous-time quantum walk algorithms assume that we can simulate the dynamics of quantum systems where the Hamiltonian is given by the adjacency matrix of the graph. It is known that such can be simulated efficiently if the underlying graph is row-sparse and efficiently row-computable. While this is sufficient for many applications, it limits the applicability for this class of algorithms to study real world complex networks, which, among other properties, are characterized by the existence of a few densely connected nodes, called hubs. In other words, complex networks are typically not row-sparse, even though the average connectivity over all nodes can be very small. In this work, we extend the state-of-the-art results on quantum simulation to graphs that contain a small number of hubs, but that are otherwise sparse. Hopefully, our results may lead to new applications of quantum computing to network science.

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-linear in N, is limited by the complexity of performing a quantum simulation of the network's adjacency matrix, which may prove to be an important problem in the development of quantum algorithms for network science in general.