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.
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.
Abstract Critical node identification is the precondition for exploring complex networks, which is a graph‐based optimal search problem in principle. Classical methods, hindered by limited parallel processing capabilities, often grapple with high computational demands and inefficiency. Recent studies have leveraged quantum walk (QW) to tackle such challenges. However, existing QW‐based approaches are constrained by graph structures and prone to recurrent traversal issues. Being different, a novel forward discrete‐time quantum walk (F‐DTQW) method is proposed, which can traverse without redundant visits by prohibiting reverse and lateral propagations. The proposed method significantly enhances the efficiency of critical node identification and is applicable to arbitrary complex networks. The proposed method is validated on typical complex networks such as small‐world, scale‐free, and directed networks, and calculates the transition probability of nodes, corresponding to the centrality measurement index of transition connectivity (TC), which expands from the betweenness centrality (BC) index. The time complexity of F‐DTQW is also analyzed, which is reduced from O ( N 3 ) to O ( N 2 ) compared to the classical method.
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.
The large amount of data and dynamism in network structures make it very crucial to identify influential nodes in complex social networks. Both centrality measurebased and machine learning model-based methods tend to view node topology and node attribute separately, neglecting the important interaction between structural links and node-level information. Efficient identification of influential nodes demands an integrated strategy that embodies the two facets. In order to meet such a challenge, a new framework named Scalable Quantum Non-local Neural Network with Energy Valley Optimization (SQNLNNet-EVO) is presented. The steps start with the preprocessing of the data by Correlation Coefficients with Min-Max Normalization (CCMMN) that enhances the high-correlation features and preserves the lowcorrelation signals. The feature extraction task is carried out with Steerable Transformers (ST), consisting of steerable convolution layers and a hybrid positional encoding scheme that provides rotation-equivariant attention mapping, and robust dependency learning. Fundamentally, SQNLNNet encodes classical node information into quantum states using phase encoding and Hadamard gates and uses the quantum non-locality to encode complex node and network interactions. Lastly, Energy Valley Optimization (EVO) enhances convergence and improves detection accuracy. The conducted experiments indicate that the proposed SQNLNNet-EVO model provides 99.8% accuracy, precision, recall, AUC, and F1-score with mere 1.75 seconds of computation time. Moreover, it achieves a Top-50 Influential Node Match of 98.1 percent, which is far better than the current methods. These results make SQNLNNet-EVO a time-saving and effective method to identify influential nodes in dynamic social networks.
In this research, the computational efficiency of large-scale social network analysis is enhanced by the use of quantum random walk algorithms. The goal of this project is to address the need for high-efficiency centralized analysis of large-scale, heterogeneous social networks, community discovery, and dynamic effect mapping. In a theoretically sound framework of quantum random walks, amplitude superposition and unitary evolution principles have been used to improve both the sensitivity to local and global aspects. The solution uses real social network data with up to 5,000 nodes and more than 60,000 edges, and the testing results demonstrate its excellent scalability and fast convergence. Quantum algorithms have discovered community divisions and cut the mixing time by roughly 2.3 times after multiple optimizations. The performance indicators demonstrate that the above method has greatly improved key node detection accuracy and computation time as compared to the conventional baseline model in noisy situations. According to the aforementioned research, quantum-inspired algorithms have been used to expedite the analysis of large-scale data and reveal hidden structures that are challenging to identify using conventional techniques, such as bridge nodes and core-periphery distributions. The research assist data-driven choices in digital social ecosystems and lay the groundwork for in-depth network analysis.
Abstract The problem of detecting communities in real-world networks has been extensively studied in the past, but most of the existing approaches work on single-domain networks, i.e. they consider only one type of relationship between nodes. Single-domain networks may contain noisy edges and they may lack some important information. Thus, some authors have proposed to consider the multiple relationships that connect the nodes of a network, thus obtaining multi-domain networks. However, most community detection approaches are limited to multi-layer networks, i.e. networks generated from the superposition of several single-domain networks (called layers) that are regarded as independent of each other. In addition to being computationally expensive, multi-layer approaches might yield inaccurate results because they ignore potential dependencies between layers. This paper proposes a multi-domain discrete-time quantum walks (MDQW) model for multi-domain networks. First, the walking space of network nodes in multi-domain network is constructed. Second, the quantum permutation circuit of the coin state is designed based on the coded particle state. Then, using different coin states, the shift operator performs several quantum walks on the particles. Finally, the corresponding update rule is selected to move the node according to the measurement result of the quantum state. With continuous update iteration, the shift operator automatically optimizes the discovered community structure. We experimentally compared our MDQW method with four state-of-the-art competitors on five real datasets. We used the normalized mutual information (NMI) to compare clustering quality, and we report an increase in NMI of up to 3.51 of our MDQW method in comparison with the second-best performing competitor. The MDQW method is much faster than its competitors, allowing us to conclude that MDQW is a useful tool in the analysis of large real-life multi-domain networks. Finally, we illustrate the usefulness of our approach on two real-world case studies.
We propose a quantum circuit design for implementing coined quantum walks on complex networks. In complex networks, the coin and shift operators depend on the varying degrees of the nodes, which makes circuit construction more challenging than for regular networks. To address this issue, we use a dual-register encoding to enable a simplified shift operator and reduces the resource overhead. We implement the circuit using Qmod, a high-level quantum programming language, and evaluated the performance through numerical simulations on Erdős-Rényi, Watts-Strogatz, and Barabási-Albert models. The results show that the circuit depth scales as approximately N1.9 regardless of the network topology. Furthermore, we execute the proposed circuits on the ibm\_torino superconducting quantum processor for Watts-Strogatz models with N=4 and N=8. The experiments show that hardware-aware optimization slightly improved the variation distance and Hellinger fidelity for the larger network, whereas connectivity constraints imposed overhead for the smaller one. These results indicate that while current NISQ devices are limited to small-scale validations, the polynomial scaling of our framework makes it suitable for larger-scale implementations in the fault-tolerant quantum computing era.