HCIS

• Home
• About
• Articles
• Submission

During a quantum walk on a complex network, the observed results contain extensive redundant information generated by interference effects, which makes it difficult to determine a suitable walk step and find the structural characteristics of the network. A Grover coin driven quantum walk model (GWM) is proposed to identify significant nodes in undirected complex networks by simulating the particle moving on the network. To circumvent the negative effects of the associated redundant information, the proposed GWM adds a self-loop to each node and determines a three-step walk by exploiting the three degrees of influence rule. Experiments on correlation, Kendall coefficient, and robustness were reported to validate the effectiveness of the proposed GWM in identifying significant nodes. Outcomes show strong correlation between results from the susceptible-infected-recovered (SIR) model and our GWM, which signify accurate identification of the significant nodes of complex networks by our model. Furthermore, outcomes in terms of Kendall coefficient between different algorithms (comprising of conventional and quantum algorithms) alongside the proposed GWM further attest that the GWM can capture the structural characteristics of networks, e.g., triadic closure and degree. Additionally, based on robustness index, the practicality of the proposed GWM in terms of identifying significant nodes was demonstrated.

Quantum Computation, Quantum Walk, Complex Network, Grover Walk, Significant Nodes

Quantum computation and quantum information science have matured from laboratory-confined demonstrations to interesting fields and applications in science and engineering birthing many technologies of profound impact, e.g., the variational quantum paradigm has been applied to solve the optimization problem in smart logistic systems [1] and the quantum mutation reptile search algorithm has been successfully used in data clustering [2]. Among others, quantum walk is widely accepted as a universal model of quantum computation [3] because they can be utilized to simulate other quantum algorithms. Some of the excellent performances exhibited by quantum walks include those in structured data search [4], graph isomorphism [5], random number generator [6], and communication protocol [7]. In particular, exploiting their interference and superposition properties, the performance of quantum walks in targeted data search offers significant acceleration in spatial search compared to conventional search algorithms [8]. Whereas these studies on quantum walks are aimed at low-dimensional lattices and regular graphs, the more impactful applications of quantum walk are in complex networks since regular graphs belong to the special graphs of complex networks [9, 10]. When the quantum walk takes place on a low-dimensional lattice, its observed results are usually used to encrypt the required information, such as a hash scheme using a two-particle walk on a line applied in image encryption [11] and a cascading substitution box for image steganography [12]. Furthermore, the use of a one-particle quantum walk on a circle is employed to generate keys in the process of communication [13] while its subsequent application on a 5G Internet of Things platform has been reported in [14]. Additionally, a generalized communication protocol was proposed in [15] to implement teleportation using a discrete-time quantum walk (DTQW). In terms of the applications in random number generation, extensive redundant information has been generated by quantum effects when a particle oscillates between the same two nodes, which is exploited to produce required chaotic characteristics in [13]. Although longer walk steps contain more redundant information, quantum walk can always be employed for spatial search with a guaranteed faster hitting time compared to conventional spatial search algorithms because the traversal procedure of the particle to the nodes in a graph is similar to the breadth-first search [16].
Meanwhile, when aimed at the complex network, the application of quantum walk is broader, and since the dependent network has an associated adjacency matrix during the walk, the resulting eigenvalues of the evolution operator (i.e., after finite-step walk) becomes integral for obtaining the targeted observed outcomes [17]. Moreover, many studies have indicated that the eigenvalues of a matrix (Laplacian or adjacency matrix) can reflect the different structures of networks [18]. For example, the plus or minus of eigenvalues and eigenvectors of a Laplacian matrix can be utilized to detect community structure. Therefore, mining of network structures is a major application of quantum walk on complex networks. Quantum PageRank [19], which utilizes the Szegedy’s walk and Google matrix to estimate significant nodes of the complex network is another famous quantum counterpart of a popular conventional algorithm (PageRank), with application in identification of significant nodes as influential users in social media or the important proteins in protein-protein interaction network. Additionally, continuous-time quantum walks (CTQW), which is also another quantum walk tool employed to evaluate significant nodes, its ranking effectiveness has been verified using a simple star-shaped graph [20]. In addition to its use to identify important nodes, the property that every step of a CTQW can be observed, motivates the contention that a quantum walk driven by the Grover diffusion operator can be used to embed the role of nodes as presented in [21] and assess node similarity as presented in [22]. Further, an R-convolution graph kernel based on fast quantum walk has been employed to compute the similarity of different graphs in [23]. Additionally, since the distribution of eigenvalue decomposition in evolution operators using Fourier coin is well-distributed on a unit complex plane, the quantum walk driven by Fourier coin has also been deployed for community detection [24].
Notwithstanding the picture of progress in quantum walk portrayed above, many difficulties are encountered when it is deployed to complex networks. For example, some quantum walks cannot be executed on existing computing frameworks due to high temporal and complexity demands [20] while extensive information redundancy caused by the interference effects during the walk cannot be eliminated [22]. Moreover, the suitable walk step is difficult to determine [19]. Focused on mitigating the enumerated challenges, our study proposes a Grover coin driven quantum walk model (i.e., GWM) to identify significant nodes in undirected complex networks. The contributions of this study are listed as follows. (i) To reduce the computational overhead, the walk step of our GWM is determined using the three degrees of influence rule. (ii) The negative effects of information redundancy in the observed results are attenuated by adding a self-loop to each node of the complex network. (iii) Our proposed model is validated via experiments testing correlations, Kendall coefficient, and robustness index, which indicate that the observed result of our GWM can effectively reflect the structural characteristics of networks, e.g., degree and triangle structure. This facilitates the accurate identification of the significant nodes in complex networks by the proposed GWM model.
The rest of this study is organized as follows: in Section 2, essential precepts of the proposed a Grover coin driven quantum walk model where the walk step is defined by three degrees of influence rule is presented. Following that, in Section 3, we present extensive experiments to validate the proposed model’s performance in applications that require the identification of significant nodes in complex networks. The conclusions and future work are described in Section 4.

In a coined quantum walk, common coin operators include the SU(2) operator [25], Hadamard operator, Grover operator, and Fourier operator [16]. However, in the Grover operator, the particle walking preference is related to the degrees of nodes at each step. Therefore, the Grover operator is selected as the coin of the quantum walk to reflect the structural characteristics of networks [21, 22]. In this section, we formalize our GWM and use it to identify significant nodes in complex networks. Taking the postulates of quantum mechanics as a reference [16], our proposed GWM is formalized in three stages: (i) definition of a Hilbert space, (ii) dynamic properties of a state vector and its evolution, and (iii) quantum observation based on three degrees of influence rule.

Definition of Hilbert Space to Grover Walk Model Since the Hilbert space of a quantum walk is related to the number of selectable paths (also interpreted as degree) of each node, we start by analyzing and defining a suitable network for the proposed GWM. As it propagates from its current step to the next one, the node selected using Grover operator is related to the degree of nodes. However, during such a process, some redundant information generated by interference effects may obstruct the observed results which may also propagate some irrelevant information. To elucidate, Fig. 1(a) presents the molecular structure of a lactic acid as an example. Supposing a four-step walk is implemented on it, a group of redundant information that vacillates between each pair of nodes can manifest as presented in Fig. 1(b), where the traceback paths are labelled in green. Whether discrete-time or continuous-time all the paths in a complex network are in a superposition, so the traceback cannot be eliminated entirely in which case the quantum walk will degenerate to a classical random walk. To decrease the negative effects generated by the illustrated traceback, we add a self-loop to the node of each network. This helps to increase the observed probability on the initial node. A node with a self-loop implies that the probability of a particle staying at the same position will increase, while, when wavering between nodes, corresponding probabilities will decrease because the sum of their probability is equal to 1 in an isolated quantum system.

Fig. 1. Description for traceback and three degrees of influence rule: (a) structure of lactic acid, (b) traceback on lactic acid, and (c) three degrees of influence.

To be precise, we consider the arbitrary dangling node in Fig. 1(b) as an example, where when there is no self-loop, the transition probability from such a node to its unique neighbor is equal to 1. In contrast, if there is a self-loop on an unsteady node, the transition probability from it to its unique neighbor will decrease to 1/2 as far as the negative effect caused by the particle oscillating repeatedly between a pair of nodes is weakened. Moreover, as outlined in the implementation of a three-state quantum walk on a low-dimensional lattice in [26, 27], the characteristics of self-loops can be employed to improve the probability of particle retention at the initial position.
Based on the above analysis, assuming that the proposed GWM takes place on an undirected complex network graph with self-loop G, where G=(V,E), such that V denotes the nodes set, E represents edges set, |V|=N and |E|=M, respectively then, defining the Hilbert space associated with the network G, since computation in our GWM is constrained by the dimensionality of the matrices and vectors. Taking node j as an example, its self-loop is e(j,j)∈E, j∈V and on a network G, the Hilbert space H of the GWM is constructed by H=$H_1$⊕$H_2$⊕⋯⊕$H_N$, where $H_j$ denotes the Hilbert space corresponding to node j. The Hilbert space adopts the direct sum operation ⊕, and, accordingly, the dimensionality $D_H$ of such a space G (i.e., that the GWM takes place on) is computed using Equation

(1)

where |N(j)| represents the number of selectable directions in the range of the nearest neighbors for node j. Meanwhile, according to its properties as an undirected complex network, $D_H$ can be expressed as $D_H$=2M, i.e., double the number of edges. By contrast, the dimensionality of a Hilbert space in the famous quantum PageRank [19] is equal to $N^2$, whereas, in general 2M≪$N^2$ is considered in a dense network.

State Vector and its Evolution
In quantum walks, the dependent network is considered as an isolated quantum system, where at an initial time, the entire system is denoted as a quantum state |ψ(0)⟩ while movement of the particle on the network is a multiplication of the state and evolution operator. Noting that in quantum computation, an arbitrary vector is expressed using a Dirac notation, (e.g., |ψ(0)⟩) then, as mentioned earlier in Section 2.1, the total dimension of network G is equal to $D_H$, which makes the length of the quantum state |ψ(0)⟩ equal to $D_H$, and state |ψ(0)⟩ can be defined as

(2)

where $α_{j,k}$ (0) denotes the probability amplitude from node j to node k at initial time, |j,k⟩ represent the orthogonal basis of the particle moving from node k to node j, and k is the nearest neighborhood node of node j, k∈N(j). At an initial time, assuming that the orthogonal basis of all nodes is a superposition state, then Equation can be expressed as

(3)

However, notwithstanding how many steps the quantum walk takes in Equation (3), the total probability amplitude satisfies the condition in Equation (4).

(4)

Equation (4) is always satisfied in undirected network G since in quantum computation, an undirected network is regarded as an isolated quantum system. In addition to network topology, each step of the proposed GWM is controlled by an evolution operator that is composed of a shift operator and a coin operator. Assuming that the evolution operator is denoted U, U can be written as

(5)

where the shift operator S plays a role akin to a “flip-flop” operation between node j and its neighbors, and C represents the coin operator of our evolution operator. A coin operator C is composed of N local coins $C_k$, e(j,k)∈E. Consequently, the effect of the shift operator in Equation is defined as S|j,$C_k$⟩=|$C_k$,j⟩, which provides a guarantee that the unitary transformation condition of quantum computation is satisfied. Meanwhile, referring to the definition in [24], a local Grover operator $C_j$ takes the form presented in Equation

(6)

where d_j is equal to |N(j)|. Trivially, for the Grover coin, the selection of the subsequent direction in the range of the nearest neighbors is related to the state of the current node. A global Grover coin operator is composed of local coins denoted in Equation whose direct sum operation is similar to the computation of the Hilbert space in the network G as C=$C_1$⊕$C_2$⊕⋯⊕$C_N$. Compared with other familiar coins (as highlighted earlier in Section 2), the use of the Grover operator as a coin of GWM has several advantages. First, the walking direction of the particle is inspired by degree information of each node, where degree is a direct and effective approach to record local topological information. Second, unlike the SU(2) operator, which is controlled by two phase parameters and one angle parameter. However, the effects caused by parameters are not required to consider in the Grover coin presented in Equation (6). Third, using other operators, since the relation between their walking preference and the structural characteristics of a network is not fully clear, they are unsuitable to be a coin operator in terms of identifying significant nodes. Meanwhile, GWM with one-step walk is equivalent to applying the evolution operator U once, where U is defined in the form presented in Equation Supposing the proposed GWM occurs on network G with some t-step (t>1) walk, then the evolution equation of the quantum state presented in Equation can be expressed as

(7)

Equation implies the particle in GWM starts at the initial quantum state |ψ(0)⟩ and its movement in such an isolated quantum system (i.e., the undirected network G) is described by a unitary operator U after t-step walk.

Quantum Observation based on Three Degrees of Influence Rule
Whereas different walk steps correspond to different observed outcomes, it is difficult to determine a suitable walk step that reflects the actual node attributions and network characteristics. In [16], a walk step is defined as the diameter of a complex network required to compute the similarity among nodes. However, in actual life, extensive complex networks belong to dense networks with a long diameter, although such a setting is not widely applicable. In [24], a walk step is defined as an infinity to detect the community of complex network, where extensive effects generated by the traceback path will perturb the observation of the outcome. In our GWM, a quantum observation process is proposed with a suitable walk step preset at 3 based on three degrees of influence rule [28], which is a famous social statistical conclusion according to the abundant cases analysis. The three degrees of influence rule was described in Fig. 1(c), where, for an arbitrary node u in a social network, three degrees of influence rule means that effective influence only occurs in the range of three-degree neighbors (i.e., a friends’ friends’ friends), where the neighbors of node u are first degree influence while the second degree and third degree are neighbors by parity of reasoning. Within this range, the influence will depreciate gradually with the depth of diffusion. Extensive diffusion phenomenon that are known to satisfy the three degrees of influence rule include behaviors leading to obesity, behavior of smoking, behavior of drunkenness, and diffusion of emotion on social media [28]. Considering the possibility of drunkenness as an example, for an individual, if the nearest (first-degree) comprises of friends frolicking at bars to drink all the time, the possibility of the individual becoming a drunkard will increase by 50%. When influenced by friends within the second-degree neighborhood, the possibility will grow by 36%, and when that influence is by the third-degree friends, the probability increases by approximately 15%. However, fourth-degree friends are found to manifest no influence on the diffusion of drunken behavior, i.e., the possibility is equal to 0 at that stage [29]. Further, beyond social networks, the three degrees of influence rule can also be used to determine the diffusion steps to measure node influence in complex networks [30, 31]. Based on the enumerated use cases, the walk step of our proposed GWM is confined to three according to such an influence rule. Combining the above analysis, after a t-step walk, the observation on node j can be defined as

(8)

where P(j;t) denotes the observed probability at node j after a t-step walk. Since the three degrees of influence rule is adopted to determine the walk steps, when the proposed GWM is used to estimate node significance in a complex network, within the three-step walk, the significance of each node is defined in Equation

(9)

where Sg(j) represents the measured significance value of node j; β is a parameter that amplifies the first degree influence while decreasing the second and third degrees of influence and the computational method of P(j;t) with reference to Equation In Equation the second and third degrees of influence are considered collectively, and since the three degrees of influence require that higher degrees influence decrease step wise, then β>1/2. Further, β is limited within the range (0.5, 0.9), and considered to have an average value (0.5+0.9)/2=0.7. The definition in Equation shows node-level description of the whole network G but supposing that P denotes the observed probability distribution of G, then the network-level definition can be presented as In the proposed GWM, the results obtained by Equation is employed to represent the significance of each node, and nodes with higher significance value indicates the significant node in a complex network. To sum up the structure of our GWM model, its architecture is presented in Fig. 2 wherefrom we note that the observed result is restrained by two factors aimed at reducing the negative effect generated by the interference effect. First, the walk step of the proposed GWM is confined to three according to three degrees of influence rule, where the shorter walk step is assigned with a higher coefficient to make the observed result closer to the node significance. This implies that the redundant information generated by traceback is reduced. Second, a self-loop is added to each node to improve the probability of the particle remaining at current node, i.e., decreasing the tottering of the transition probability from current node to its neighbors. Furthermore, when the largest walk step is preset as three, i.e., the observed result is accumulated within first-step through to the third-step, the highlighted information is simultaneously formalized in the proposed GWM. (i) The evolution operator enumerating all possible walk behaviors of the particle in our GWM, therefore the network connectivity is contained in the evolution operator when the walk step is equal to 1. (ii) Furthermore, when the walk step is 2, the evolution operator is applied twice (i.e., U2); Thus, the common neighbor information is included at that instant. The common neighbors will be employed for recording similarities between different nodes, and also to indicate the node significance. (iii) The path with length 3 is retained in the evolution operator with such an evolution operator is denoted U3, where the closeness between various nodes is calculated when the path with length 3 forms a triadic closure. The global connectivity, degree and triangle closure structure are useful metrics for identification of significant nodes. When the above information is effectively contained in the observed result of our proposed GWM, it guarantees that the proposed GWM depends on the structural characteristics of networks to identify the significant nodes of complex networks.

Fig. 2. Architecture of the proposed GWM.

In this section, we undertake a performance evaluation to establish the efficiency of our GWM in identifying significant nodes of complex networks. The analysis employs standard metrics including tests for correlation between the susceptible-infected-recovered (SIR) model and the proposed GWM, Kendall coefficient τ between measured results of two algorithms, and robustness index based on significant node removal. First, we start by highlighting essential features of the experimental dataset and algorithms employed for our performance evaluation.

Overview of Experimental Data and Comparison Algorithms
Complex networks traverse many areas of our daily lives [32]. Therefore, experiments to implement protocols such as our proposed model could cover traffic (Chesapeake network), social behavior among animals (Kangaroos network), co-occurrence relationships among words in a book (Adjnoun network), social settings (Karate, Enron-only, Tribes, and Jazz networks), and exchange of emails (Email network). The differentiated characteristics of experimental data are considerate in our analysis, Table 1 summarizes the statistical attributes of these enumerated undirected complex networks.

Table 1. Statistical characteristics of complex networks used in experiments

Network	N	M	K	$D_{MAX}$	d	c	p
Tribes	16	58	7.25	10	3	0.527	0.049
Kangaroos	17	91	10.706	15	3	0.841	-0.193
Karate	34	78	4.588	17	5	0.256	-0.475
Chesapeake	39	170	8.717	33	3	0.284	-0.375
Adjnoun	112	425	7.589	49	5	0.19	-0.129
Enron-only	143	623	8.713	42	8	0.453	-0.019
Jazz	198	2742	27.697	100	6	0.52	0.02
Email	1,133	5451	9.622	71	8	0.22	0.078

In Table 1, N and M are the number of nodes and edges, respectively; ⟨k⟩ and d_max denote the average degree and maximum degrees of a complex network, respectively; d indicates the diameter of a network; c and ρ represent the clustering coefficient and the assortativity coefficient of a complex network, respectively. These eight network datasets can be obtained from [32]. In this study, we further employ eight algorithms to compare alongside our proposed model. These are (i) a conventional epidemic dynamic model, i.e., SIR model [33], (ii) quantum PageRank (QPageRank) [19], which is a competitive quantum walk algorithm based on Szegedy’s quantum walk model, (iii) other conventional algorithms, including degree centrality (DC) [34], betweenness centrality (BC) [34], closeness centrality (CC) [34], PageRank [35], local triangle centrality (LTC) [36], and k-shell [37].

Correlation between SIR and the Proposed GWM
As an important technology in dynamic system simulation [38], simulated results of each node obtained using the SIR model are always viewed as a standard reference when estimating the significant nodes of complex networks. Consequently, correlation between the measured results of SIR and the proposed GWM provides insights to establish the performance of our proposed model. A strong correlation between the measured values using SIR and our GWM is indicative of its efficiency in identifying significant nodes, where the measured value of node significance in GWM is calculated by Equation (9) and the measured value of node significance in SIR is computed by simulating the process of information diffusion. Fig. 3 presents plots of correlations for the various networks indicated, where horizontal and vertical directions denote the measured significance value of each node using SIR and the proposed GWM, respectively. Further, to distinguish overlapped scattered points in Fig. 3, each scattered point is labelled using diaphaneity, random color, and random size.
When the correlation result between the SIR model and our GWM exhibits a remarkable curve, it is indicative that they have a strong correlation, and the strong correlation points of the accuracy of our GWM in identifying significant nodes. Fig. 3(a)–3(g) exhibits a strong correlation between the SIR and our GWM, and by contrast, the correlation depicted in Fig. 3(h) is relatively weaker than other networks. In Fig. 3(a), 3(b), and 3(g), for the nodes with the high measured values (high significance), the correlation plots between the SIR model and our GWM described are especially remarkable. By comparison, the correlation in Fig. 3(d)–3(g) is better overall. Furthermore, since the diffusion step of the SIR model in various networks is always taken by diameters of networks, it can be surmised that, by its use of only a three-step walk, the proposed GWM has the approximate effect of the SIR model in ranking of significant nodes, i.e., the feasibility using three degrees of influence to determine walk step in GWM is validated. Combined the outstanding performance of the GWM in the reported correlation experiment and the property of the SIR model, the effectiveness of the proposed GWM in capturing the structural characteristics of neighboring nodes can be inferred. Finally, for the SIR model, the measured value of each node is repeated independently thousands of times, which in contrast, is not required in the proposed GWM because of its non-randomness. It can therefore be concluded that the proposed GWM not only required fewer computations but also effectively identified the significant nodes according to the reported performance in the correlation experiment.

Fig. 3. Correlations between node significance using our GWM and SIR model: (a) Tribes, (b) Kangaroos, (c) Karate, (d) Chesapeake, (e) Adjnoun, (f) Enron-only, (g) Jazz, and (h) Email.

Kendall Coefficient τ between Measured Results
The Kendall coefficient [36] is used to quantify the correlation between measured results for pairings of the proposed GWM and various algorithms as indicated when applied to identify significant nodes of complex networks. Assuming that X and Y represent the sequences of the significance of all nodes using two algorithms, then the combination of the elements in X and Y can be denoted as ($x_j$,$y_j$ ) and ($x_k$,$y_k$ ). Therefore, supposing that $N_c$ and $N_d$ indicate the amount of positive and negative correlation between ($x_j$,$y_j$ ) and ($x_k$,$y_k$ ), they can be computed using Equation

(10)

where T denotes that a condition is true. Further, according to Equation the Kendall coefficient τ between two algorithms is defined as

(11)

where τ∈[-1,1] and a value τ=-1 connotes uncorrelation between the measured results of two algorithms, while τ=1 represents absolute correlation. Fig. 4 presents experimental outcomes on the Kendall coefficient, where each sub-figure is a symmetric matrix, and each element (calculated using Equation) in the matrix presents that the corresponding Kendall coefficient τ between arbitrary pairings of the algorithm. Additionally, in Fig. 4(a)–4(h), the color bar records the range of the Kendall coefficient between various algorithms in the current network.

Fig. 4. Kendall coefficient τ between measured results of various algorithms: (a) Tribes, (b) Kangaroos, (c) Karate, (d) Chesapeake, (e) Adjnoun, (f) Enron-only, (g) Jazz, and (h) Email.

As reported in Fig. 4, as an instance, the Kendall coefficient τ between DC and our GWM in eight complex networks, their average Kendall τ equals 0.897. This advantage is attributed to two reasons: first, the degree information of each node ascribed to the Grover operator and the reduction in redundant information as a result of the self-loops and three-step walk in our proposed model. Combining the property of DC, the average Kendall coefficient between our GWM and DC, and the advantages described in Section 2.3, it can be seen from the observed result that using our GWM can reflect the neighbor information of each node, i.e., the degrees of nodes, especially in Fig. 4(a), 4(b), 4(d), and 4(g). Further analysis of the reported outcome in Fig. 4 indicates that the τ for BC and CC for our proposed GWM is lower than those recorded using the other algorithms. Additionally, we also note that as a path-based algorithm, some inconsistent information between BC and CC is reflected in the Kendall coefficient τ reported between BC and CC (i.e., 0.697 in Fig. 4(a)). However, the τ between the GWM and CC is equal to 0.908 as described in the same figure. Correspondingly, we observe that in partial complex networks, BC and CC are not the common estimation standard due to inconsistent values of τ, especially in Fig. 4(f), 4(g), and 4(h).
Furthermore, the average τ between PageRank and the proposed GWM is 0.854 on eight complex networks. Nevertheless, looking at the corresponding τ for the various networks, although PageRank is based on global random walk, we note the impact of our GWM within the three-step walk is approximate to it (e.g., Fig. 4(c) and 4(d)). Meanwhile, at 0.814, the average Kendall coefficient between our proposed GWM and the LTC is slightly below the average value reported. This is indicative of the impact of the clustering coefficient c in the identification of significant nodes of such complex networks. For example, looking at the plot in Fig. 4(e), we can observe that at 0.687 the Kendall coefficient between our proposed GWM and LTC has the lowest clustering coefficient at c=0.19 (also reported in Table 1). However, as reported in Fig. 4(b), the τ between LTC and the GWM is equal to 0.913, where the Kangaroos network has the largest clustering coefficient c in all eight complex networks. Combining the analysis of Section 2.3, the Kendall coefficient between our GWM and the LTC, and the statistical characteristics of the networks presented in Table 1, these imply that the proposed GWM effectively contains the triangle structure between various nodes, especially for the networks with high cluster coefficients. Additionally, it can be seen that for all the competing algorithms, the Kendall coefficient τ between k-shell and arbitrary algorithms is low, as exhibited in Fig. 4(a), 4(b), 4(d), 4(f), and 4(g). This phenomenon is attributed to k-shell scoring the nodes in strongly connected subgraphs with an identical measured value, which makes node significance indistinguishable. Finally, despite being relatively low at 0.713, the average Kendall coefficient between QPageRank and our GWM satisfies the condition in [19] that stipulates concordance in their ranking result for it to be deemed significant in node evaluation. However, relative to other algorithms, Kendall coefficients for QPageRank are low for the reported complex networks, as exhibited in Fig. 4(c) and 4(e). It is noteworthy that the application of the QPageRank is limited by the scale of complex networks since it aggravates space complexity. By comparing the evolution operator of QPageRank and our GWM as an example, we see that the dimension of our GWM is O(2M) while that of QPageRank is as high as O($N^2$ ).
To summarize, the reported results demonstrate that our proposed GWM has the following advantages for identification of significant nodes (i) capture of neighborhood structure of each node (compared to DC), (ii) capture of triangle structure among nodes (compared to LTC), and (iii) replace global random walk with a three-step walk (compared to PageRank). In other words, for identification of significant nodes, based on the above analysis, it can be concluded that there is concordance in terms of the performance of the DC, PageRank, and LTC with our proposed GWM.

Robustness Estimation of Various Algorithms
By ordering the outcomes of our proposed GWM in descending manner, the resulting sequence can be used to rank the significance of the nodes. To validate the ranked sequence of significant nodes, the robustness index is used to quantify the identified results of an algorithm. Using this index, if a significant node is removed from the network, then the network may disintegrate into several independent sub-networks, and the degree of disintegration of the network represents the significance of the nodes. Therefore, the robustness index can be defined as presented in Equation (12).

(12)

where ξ/N denotes the rate that the number of significant nodes in the sequence are removed, σ(ξ/N) is the ratio that the number of nodes in maximum connected components after deleting ξ nodes to N, and 1/N is used to normalize the robustness outcome. Since the node removal approach of the robustness index is a common practice in network attack and defense, the outcomes using the robustness index can reflect the practicality of an algorithm in the identification of significant nodes. In Equation, a lower value of R implies the presence of more important nodes in the complex network. Using which the experimental results of the robustness index on eight complex networks are reported in Fig. 5.

Fig. 5. Experimental outcomes of various algorithms using robustness index: (a) Tribes, (b) Kangaroos, (c) Karate, (d) Chesapeake, (e) Adjnoun, (f) Enron-only, (g) Jazz, and (h) Email.

According to Fig. 5, use of the proposed GWM can accelerate the network disintegration as multiple connected components on the whole (as exhibited in Fig. 5(a), 5(d), 5(e), 5(g), and 5(h)). Further, compared to conventional non-quantum algorithms, the proposed GWM outperforms the DC, CC, LTC, and k-shell whose results are reported in Fig. 5(e) and 5(h). Since the final measured value of robustness must be equal to 0 until there is no node in the network (as defined in Equation) and the significant nodes are always the few nodes ranked at the top of the sequence [34, 36, 37], the falling speed of the robustness curve using an algorithm should be focused in Fig. 5. This indicates that the faster falling speed represents the more accuracy of an algorithm in identifying significant nodes. In terms of the first of half node removal, the falling speed of the GWM is faster than DC, PageRank, LTC, and k-shell in Fig. 5(e), 5(g), and 5(h). Referring to the statistical characteristics of the networks described in Table 1, it can be concluded that the three networks reported in Fig. 5(e), 5(g), and 5(h) (i.e., Adjnoun, Jazz, and Email) have the highest degree of network (i.e., dmax). This implies that the performance of our GWM is better in identifying significant nodes when the network has a higher maximum degree. Once again, this proves that the proposed GWM can effectively contain the neighbor topological structure of each node during significant node identification.
Additionally, taking a closer look at BC, which has an outstanding performance in Fig. 5(d), we note how its performance in Fig. 5(e) is below par. Therefore, it can be deduced that as a path-based algorithm, the performance using BC is not stable when identifying significant nodes. It is noteworthy that in terms of identifying significant nodes, the performances of PageRank and our GWM in Fig. 5(a), 5(b), 5(d), 5(e), 5(g), and 5(h) are the evidence that the three-step walk in our GWM is equivalent to the global random walk-based algorithm. Furthermore, although the proposed GWM and QPageRank are both quantum walk-based approaches, due to high complexity of QPageRank, in large-scale networks such as Fig. 5(f), 5(g), and 5(h), it is incapable of identifying the significant nodes within an acceptable time in the networks. The experimental analyses above show that our GWM is superior to both existing quantum algorithms and partial conventional algorithms in terms of robustness. The reported outcomes also suggest that, for shorter walk steps, the Grover coin operator is in favor of significant node mining in complex networks.

In this study, we presented a Grover-driven quantum walk model (i.e., GWM) to identify significant nodes in undirected complex networks. Our proposed GWM combined the three degrees of influence rule to determine the walk step and a self-loop to decrease the negative effects of traceback in phase observations. Three experiments were employed to establish the efficiency of the proposed GWM where a strong correlation between our proposed GWM and the SIR model was reported. In terms of significant node identification, experimental outcomes based on the Kendall coefficient and robustness index indicated that: (i) the proposed GWM is superior to existing quantum walk algorithms, (ii) the three-step walk of our model performs as well as other competing algorithms, and (iii) the observed result can reflect the structural characteristics of nodes. These performances support the conclusion that the proposed GWM can efficiently identify the significant nodes in complex networks. In ongoing work, we are exploring refinements to support the use of our proposed model to estimate characteristics and dynamics of other complex networks, such as in modelling epidemics. Further, by understanding the statistical characteristics of the Grover-driven quantum walk that is at the core of our proposed model, in short to midterm improvements to our study, the relation between the observed probability and other characteristics of complex networks, such as maximum degree of nodes, average shortest path of network, characteristics of module, and different type networks (e.g., small-world network, random scale-free network) need to be better understood. To do this, the accuracy of the GWM in identification of significant nodes must be further improved. Secondly, exploring the reduction of negative effects caused by redundant traceback information, the initial probability amplitude could be preset to the unequal superposition form. Meanwhile, since the effect of the initial probability amplitude is similar to weighted attribution of complex networks, it can be used to design advanced quantum walk models within finite walk steps and applied to more practical problems. Furthermore, inspired by [39], we plan to design a quantum walk model induced by a Fourier operator, where the phase and angle parameters in the Fourier operator make the use of the genetic algorithms to execute parametric optimization [40, 41]. Finally, the universal computational features inherent to the adopted discrete-time quantum walk model could be exploited to simulate advanced quantum devices that could be deployed to wide-ranging applications.

Conceptualization, WL. Funding acquisition, AMI. Investigation and methodology, WL, FY. Supervision, KH. Writing of the original draft, WL. Writing of the review and editing, WL, FY, AMI, ASS, KH. Software, WL. Formal analysis, ASS. Visualization, FY, AMI.

This study is sponsored by the Deputyship for Research and Innovation of the Saudi Ministry of Education via its funding for the PSAU (Grant No. If-PSAU-2021/01/18316).

The authors declare that they have no competing interests.

Name: Wen Liang
Affiliation: School of Computer Science and Technology, Changchun University of Science and Technology
Biography: Wen Liang received the B.Eng degree and M.Sc degree in computer science from Jiangxi University of Science and Technology in 2017 and 2020, respectively. He is currently a Ph.D. candidate in School of Computer Science and Technology, Changchun University of Science and Technology, Changchun, China. His research interests include quantum computation and complex network.


Name: Fei Yan
Affiliation: School of Computer Science and Technology, Changchun University of Science and Technology
Biography: Fei Yan received the doctoral degree in engineering from the Department of Computational Intelligence and Systems Science, Tokyo Institute of Technology, Japan. He is currently a Professor with the School of Computer Science and Technology, Changchun University of Science and Technology, China. He has been serving as an Associate Editor for the Journal of Advanced Computational Intelligence and Intelligent Informatics and a Guest Editor for the Journal of Medical Imaging and Health Informatics and the International Journal of Information Science and Technology. His current research interests include quantum information processing, computational intelligence, and medical image analysis.


Name: Abdullah M. Iliyasu
Affiliation: College of Engineering, Prince Sattam Bin Abdulaziz University
Biography: Abdullah M. Iliyasu received the M.E. and Dr.Eng. degrees in computational intelligence and intelligent systems engineering from the Tokyo Institute of Technology, Japan. He is currently the Principal Investigator and the Team Leader of the Advanced Computational Intelligence and Intelligent Systems Engineering Research Group, College of Engineering, Prince Sattam Bin Abdulaziz University, Saudi Arabia. He has to his credit more than 100 publications traversing the areas of computational intelligence, quantum cybernetics, quantum machine learning, cyber and information security, hybrid intelligent systems, and the Internet of Things. He is an Associate Editor of many journals, including IEEE Access and Information Sciences.


Name: Ahmed S. Salama
Affiliation: Faculty of Engineering and Technology, Future University in Egypt
Biography: Ahmed S. Salama received his Ph.D. in Electrical Engineering, Communications and Electronics from Alexandria University, Egypt in 2020. He is currently a researcher of Electrical Engineering Department, Future University and a supervisor of Computer Science Department, Cairo Higher Institute for Engineering, Computer Science and Management in New Cairo, Egypt. From 2008 to 2018, he was a researcher in College of Engineering, Salman Bin Abdulaziz University, Saudi Arabia. His research interests include quantum computing, Internet of Things, and neural networks.


Name: Kaoru Hirota
Affiliation: Department of Computational Intelligence and Systems Science, Tokyo Institute of Technology
Biography: Kaoru Hirota received the Dr. Eng. degree in electrical engineering from the Tokyo Institute of Technology, Japan. He is currently an Emeritus Professor with the Tokyo Institute of Technology and a Distinguished Professor with the Beijing Institute of Technology. His research interests include fuzzy systems, intelligent robot, computational intelligence, and industrial informatics. He was the President of the International Fuzzy Systems Association (IFSA). He is also a Fellow of the IFSA and the President of the Japan Society for Fuzzy Theory and Systems (SOFT). He is also the Editor-in-Chief of the Journal of Advanced Computational Intelligence and Intelligent Informatics.