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.
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.
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.
Many systems such as social networks and biological networks take the form of complex networks, which have a community structure.Community detection in complex networks is of great interest to many researchers in statistical physics and mathematical physics.There have been studies on community detection that use the classical random walk.The present study utilizes the discrete-time quantum walk instead.The quantum walk plays an important role in various fields, especially in research on quantum computers, and attracts much attention from mathematical physics too.The discrete-time quantum walk has two properties: it linearly spreads on a flat space, and it localizes in some cases because of quantum coherence.We demonstrate that these properties of the quantum walk are useful for community detection on complex networks.We define the discrete-time quantum walk on complex networks and utilize it for community detection.We numerically show that the quantum walk with a Fourier coin is localized in a community to which the initial node belongs.Meanwhile, the quantum walk with a Grover coin tends to be localized around the initial node, not over a community.The probability of a classical random walk on the same network converges to a uniform distribution with a relaxation time generally unknown a priori.We thus claim that the time average of the probability of a Fourier-coin quantum walk on complex networks reveals the community structure more explicitly than that of a Grover-coin quantum walk and a snapshot of the classical random walk.We first demonstrate our method of community detection for a prototypical three-community network, producing the correct grouping.We then apply our method to two real-world networks, namely, Zachary's karate club and the U.S. Airport network.We successfully reveal the community structure, the two communities of the instructor and the administrator in the former and major airline companies in the latter.
Compared with the classical random walk, the quantum walk has the advantages of less time to find the target node and less time scattered from the source node to all nodes. Therefore, in order to further improve the accuracy of link prediction algorithms, a link prediction algorithm based on discrete-time quantum walk (DTQW) on weighted graphs is proposed by integrating node attributes and introducing the idea of assigning weights to edges in network dynamics. In this algorithm, a weighted graph is first constructed based on the attribute information of nodes in the graph, and then a DTQW model is constructed based on the weighted graph. Then, under the control of the evolution operator, the walker performs a DTQW on the weighted graph; Finally, the link prediction algorithm is implemented by defining the similarity between nodes based on the average probability of the walker reaching each node. The experimental results show that in three real social networks, Douban, Weibo and Zhihu, this algorithm has different degrees of improvement in prediction accuracy and the algorithm stability is among the top in comparison with the optimal benchmark prediction algorithm.
Identifying influential nodes in complex networks is essential for a wide range of applications, from social network analysis to enhancing infrastructure resilience. While quantum walk-based methods offer potential advantages, existing approaches face challenges in dimensionality, computational efficiency, and accuracy. To address these limitations, this study proposes a novel method inspired by the one-dimensional discrete-time quantum walk (IOQW). This design enables the development of a simplified shift operator that leverages both self-loops and the network's structural connectivity. Furthermore, degree centrality and path-based features are integrated into the coin operator, enhancing the accuracy and scalability of the IOQW framework. Comparative evaluations against state-of-the-art quantum and classical methods demonstrate that IOQW excels in capturing both local and global topological properties while maintaining a low computational complexity of O(N⟨k⟩), where ⟨k⟩ denotes the average degree. These advancements establish IOQW as a powerful and practical tool for influential node identification in complex networks, bridging quantum-inspired techniques with real-world network science applications.
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.