The source detection problem is the reverse of information diffusion. It is identifying information sources of the diffusion process. However, most existing algorithms have limited performance due to various reasons, therefore the application is limited. We propose an approach, namely Quantum Walk based Source Detection (QWSD), to identify the source nodes based on the continuous-time quantum walk (CTQW). The continuous-time quantum walk can be utilized to simulate the diffusion process. Therefore, we utilize the reversed quantum walk to reverse the diffusion, thus revealing the probability for a node to be a source node. It is the first time that the continuous-time quantum walk is applied to the source detection problem. Extensive experiments demonstrate that our algorithm outperforms other source detection algorithms on both synthetic datasets and real-world datasets.
The source detection problem is the reverse of information diffusion. It is identifying information sources of the diffusion process. However, most existing algorithms have limited performance due to various reasons, therefore the application is limited. We propose an approach, namely Quantum Walk based Source Detection (QWSD), to identify the source nodes based on the continuous-time quantum walk (CTQW). The continuous-time quantum walk can be utilized to simulate the diffusion process. Therefore, we utilize the reversed quantum walk to reverse the diffusion, thus revealing the probability for a node to be a source node. It is the first time that the continuous-time quantum walk is applied to the source detection problem. Extensive experiments demonstrate that our algorithm outperforms other source detection algorithms on both synthetic datasets and real-world datasets.
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.
Diverse facets Of the Theory of Quantum Walks on Graph are reviewed Till now .In specific, Quantum network routing, Quantum Walk Search Algorithm, Element distinctness associated to the eigenvalues of Graphs and the use of these relation /connection in the study of Quantum walks is furthermore described. Different Researchers had contribution and put their benchmark idea Pertaining with this research concept. I furthermore try to investigate recent Application of Quantum walks, In specific the problem pertained with Graph matching i.e Matching nodes(vertices) of the Graphs. In this research paper,I consider how Continuous-time quantum walk (CTQW) can be directed to Graph-matching problems. The matching problem is abstracted using weighted(attributed) Graphs that connects vertices's of one Graph to other and Try to compute the distance b/n those Graphs Node's Beside that finding the matched nodes and the Cost related to Matching. eventually measuring the distance between two Graphs which might have different size then by using k-nearest neighbor (k-NN) method try to classifying those graph based on closest training examples in the feature space.
Diverse facets Of the Theory of Quantum Walks on Graph are reviewed Till now .In specific, Quantum network routing, Quantum Walk Search Algorithm, Element distinctness associated to the eigenvalues of Graphs and the use of these relation /connection in the study of Quantum walks is furthermore described. Different Researchers had contribution and put their benchmark idea Pertaining with this research concept. I furthermore try to investigate recent Application of Quantum walks, In specific the problem pertained with Graph matching i.e Matching nodes(vertices) of the Graphs. In this research paper,I consider how Continuous-time quantum walk (CTQW) can be directed to Graph-matching problems. The matching problem is abstracted using weighted(attributed) Graphs that connects vertices's of one Graph to other and Try to compute the distance b/n those Graphs Node's Beside that finding the matched nodes and the Cost related to Matching. eventually measuring the distance between two Graphs which might have different size then by using k-nearest neighbor (k-NN) method try to classifying those graph based on closest training examples in the feature space.
Dynamical evolution of systems with sparse Hamiltonians can always be recognized as continuous-time quantum walks (CTQWs) on graphs. In this paper, we analyze the short-time asymptotics of CTQWs. In recent studies, it was shown that for the classical diffusion process the short-time asymptotics of the transition probabilities follows power laws whose exponents are given by the usual combinatorial distances of the nodes. Inspired by this result, we perform a similar analysis for CTQWs in both closed and open systems, including time-dependent couplings. For time-reversal symmetric coherent quantum evolutions, the short-time asymptotics of the transition probabilities is completely determined by the topology of the underlying graph analogously to the classical case, but with a doubled power-law exponent. Moreover, this result is robust against the introduction of on-site potential terms. However, we show that time-reversal symmetry-breaking terms and noncoherent effects can significantly alter the short-time asymptotics. The analytical formulas are checked against numerics, and excellent agreement is found. Furthermore, we discuss in detail the relevance of our results for quantum evolutions on particular network topologies.
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.
The continuous-time quantum walk (CTQW) provides a new approach to problems in graph theory. In this paper, the correlation between the CTQW and cliques in graphs is studied, and an approximate algorithm for the maximum clique problem (MCP) based on the CTQW is given. Via both numerical and theoretical analyses, it is found that the maximum clique is related to the transmission characteristics of the CTQW on some special graphs. For general graphs, the correlation is difficult to describe analytically. Therefore, the transmission characteristics of the CTQW are applied as a vertex selection criterion to a classical MCP algorithm and it is compared with the original algorithm. Numerous simulation on general graphs shows that the new algorithm is more efficient. Furthermore, an approximate MCP algorithm based on the CTQW is introduced, which only requires a very small number of searches with a high approximation ratio.