{'fraction_non_alphanumeric': 0.03757218331490355, 'fraction_numerical': 0.011524757341196706, 'mean_word_length': 4.370282396410662, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Quantum hub and authority centrality measures for directed networks based on continuous-time quantum walks

In this work we introduce, test and discuss three quantum methods for computing hub and authority centrality scores in directed networks. The methods are based on unitary, continuous-time quantum walks; the construction of a suitable Hermitian Hamiltonian is achieved by performing a quantum walk on the associated bipartite graph. Two methods, called CQAu and CQAw, use the same evolution operator, inspired by the classical HITS algorithm, but with different initial states; the computation of hub and authority scores is performed simultaneously. The third method, called CQG and inspired by classical PageRank, requires instead two separate runs with different evolution operators, one for hub and one for authority scores. The methods are tested on several directed graphs with different sizes and properties; a comparison with other well-established ranking algorithms is provided. CQAw emerges as the most reliable of the three methods and yields rankings that are largely compatible with results from HITS, although CQAu and CQG also present interesting features and potential for applications.


Introduction
The design and analysis of centrality measures for networks -i.e., measures of importance of nodes -plays a crucial role in network analysis and has sparked much interest in the last decades; a classical example is the Page Rank algorithm [7] for ranking web pages in search engines.
For directed networks, moreover, there is a distinction to be made between hub and authority centrality. For instance, in a network of Web pages or documents, hubs can be seen as pointers to high quality resources, whereas authority are the resources themselves. Therefore each node plays a double role in the network and is assigned separate hub and authority scores. This notion was initially popularized by the HITS algorithm [21] for ranking Web pages (see Section 2). Benzi et al. [5] have proposed a bipartization approach where hub and authority centrality is defined through the exponential of the adjacency matrix of the undirected bipartite graph associated with the original graph.
Meanwhile, interest in quantum computation fueled the development of the theory of quantum walks on networks, the quantum version of classical random walks. Quantum walks have, of course, the advantage of exploiting the considerable potential of quantum algorithms for fast computation, and exhibit a few peculiar differences w.r.t. classical quantum walks. A good introduction to quantum walks can be found, for instance, in the recent book [30]; we mention also the seminal paper [1] and the review [32].
As in the case of classical random walks, quantum walks are available in two flavors: discrete-time quantum walks (DTQW) and continuous-time quantum walks (CTQW). DTQWs typically take place in a Hilbert space with dimension higher than the number of nodes, because extra degrees of freedom are added in order to obtain a unitary evolution operator U modeling each step. In the coin-flip formalism, for instance, the dimension of the Hilbert space is of the order of the number of edges in the graph. In CTQW, on the other hand, the underlying Hilbert space usually has dimension equal to the number of nodes and the evolution operator is U (t) = exp(−itH), where H is a suitably defined Hermitian Hamiltonian operator that encodes the structure of the network.
Following the idea behind PageRank, where centrality is defined as the stationary vector of a (classical) random walk, several authors have proposed quantum algorithms for centrality computation based on quantum walks. A DTQW-based ranking algorithm, called Quantum PageRank (DQPR), was proposed in [28]. The dimension of the Hilbert space used in DQPR is n 2 , where n is the number of nodes. Another DTQW-based approach is presented in [8]. The use of DTQW has also been proposed in connection with community detection in networks [27]. Unitary CTQW have been applied for ranking purposes in undirected networks [31,23]: in this case the quantum walk takes place in a Hilbert space of dimension n. An extension of the idea in [23] to directed networks forgoes the requirement for a unitary evolution operator and adopts instead non-standard PT-symmetric Hamiltonians [22]. See also [33] for a physical implementation of a CTQW-based approach to ranking in directed networks.
A common feature of unitary quantum walks, due to the unitary evolution, is the absence of asymptotic states. As a consequence, the quantum state of the system (which encodes the occupation values of each node) does not converge to a stationary state: the extraction of centrality scores usually requires step-or time-averages. Another consequence is that the occupation of each node may depend on the initial state, i.e., the prescription of the initial state is part of the ranking method. We mention however that there are also quantum methods that obtain stable states without averaging, through a tunable time-dependent Hamiltonian (adiabatic computations, as in [24]) or using mixed quantum-classical evolution [25].
In this work we introduce and discuss three new unitary-CTQW-based hub and authority centrality measures for directed networks. Two different Hamiltonians are used: one based directly on the adjacency matrix, the other one built starting from the Google matrix. We rely on bipartization in order to define Hermitian Hamiltonians, and consequently unitary evolution operators. The dimension of the underlying Hilbert space is 2n (that is, the number of nodes of the bipartite graph associated with the given network). In two of the three methods, hub and authority rankings are computed simultaneously.
Section 2 provides the background to understand the problem and briefly presents a few popular ranking algorithms that will later be used for comparison purposes. Our CTQW-based methods are outlined in Section 3 according to the evolution operators they use. Section 4 is devoted to numerical experiments: tests on simple toy models, which allow us to discuss certain features of the methods, tests on artificial 128-nodes scale-free graphs, and tests on real-life larger graphs (up to 4472 nodes). The results are compared to rankings obtained from four other algorithms, three classical (HITS, PageRank and the method in [5]) and one quantum (QPR). Section 5 discusses the proposed methods in the light of the numerical results.

Background
For our purposes, a (directed) graph G is a pair (V, E), where V is the set of nodes, labeled from 1 to n, and E = {(i, j)|i, j ∈ V } is the set of edges. The graph is called undirected if (i, j) ∈ E implies (j, i) ∈ E. The graphs we consider are weakly connected, unweighted and contain no loops (i.e., edges from one node to itself) or multiple edges.
Recall that the adjacency matrix associated with a graph G is the n × n matrix A = (A ij ) such that A ij = 1 if there is an edge from node i to node j, A ij = 0 otherwise. Clearly A is symmetric if and only if G is undirected.
The in-degree deg in (i) of node i is the number of nodes pointing to node i, whereas its out-degree deg out (i) is the number of nodes pointed to by node i. In matrix terms, it holds deg in (i) = (1 T A) i and deg out (i) = (A1) i , where 1 is the column vector formed by n components all equal to 1.
A graph is called bipartite if its vertices can be divided into two disjoint sets, such that no edge of the graph connects vertices from the same set. Given a directed graph G = (V, E), an associated undirected bipartite graph B G can be defined as follows: • take as set of nodes the union of two copies V and V of V , • nodes i ∈ V and j ∈ V , corresponding to nodes i and j in G, are connected by an edge if and only if there is an edge from i to j in G.
As the graph is bipartite, there is no edge between nodes of V , nor between nodes of V .
See Figure 2 for an example of bipartite graph associated with a given directed graph. Note that, if the nodes of B G are labeled by listing first the nodes in V and then the nodes in V , in the same order as in V , then the adjacency

Classical centrality measures for directed graphs
Among the numerous centrality measures proposed in the literature for directed graphs, we recall a few that are especially popular and that will be used for comparison purposes in Section 4. Two of them (HITS and PageRank) were originally developed for ranking web pages. The HITS (Hyperlink-Induced Topic Search) algorithm [21] is an iterative scheme that computes an authority score and a hub score for each node. Each iteration takes the form followed by normalization in 2-norm, where x (k) and y (k) are the vectors of authority and hub scores, respectively, at the k-th step. Authority and hub centralities are defined as the limit values of the corresponding scores for k → ∞. This process can also be reframed as a power method yielding the dominant eigenvector of A T A (for authorities) and of AA T (for hubs). As the Perron-Frobenius theorem does not necessarily apply to these matrices, the scores computed by HITS may depend on the choice of the initial vector. See [13] for an analysis of existence and uniqueness properties of the HITS vectors. PageRank [7,26] is very well known, following its success as a web ranking algorithm. In the PageRank algorithm, the adjacency matrix A of the graph is modified to obtain the so-called patched adjacency matrixÃ, which is row-stochastic: Each entryÃ ij can be seen as the probability, for a walker placed at node i, to reach node j, with the assumption that from each dangling node -i.e., a node with zero out-degree -the walker can reach all other nodes with uniform probability (or, more generally, with a probability given by a "personalization vector"). Next, one introduces a "teleportation" or "random surfer" effect by adding a rank-one correction: where α ∈ [0, 1] is a parameter, usually chosen as α = 0.85. The matrix G is sometimes referred to as the Google matrix. By the Perron-Frobenius theorem, 1 is the (simple) eigenvalue of maximum modulus for G T . The associated eigenvector x > 0 such that G T x = x yields the PageRank scores of the nodes, and it can be computed efficiently via the power method. Note that PageRank defines authority scores, since the importance of each node is determined by the importance of the nodes pointing to it. Conversely, reverse PageRank [16], that is, PageRank applied to the "reversed graph" with adjacency matrix A T , provides hub scores.
The third approach we mention is presented in [5] and can be placed in the more general framework of walk-based centrality mesures defined through matrix functions. Recall that the notion of subgraph centrality for undirected graphs takes as centrality scores the diagonal entries of e A , where A is the (symmetric) adjacency matrix [12]. In the directed case, the authors of [5] consider instead the exponential of the symmetric 2n × 2n augmented matrix Observe that, as mentioned above, A is the adjacency matrix of the undirected bipartite graph associated with the directed graph under consideration. The hub and authority scores of the i-th node are defined as [e A ] i,i and [e A ] n+i,n+i , respectively. A walk-based interpretation of these quantities relies on the observation that [(AA T ) k ] ij counts the number of alternating walks of length 2k that connect node i to node j starting with an out-edge, whereas [(A T A) k ] ij is the number of alternating walks of length 2k from node i to node j starting with an in-edge.

Quantum centrality
Quantum walks (i.e., quantum versions of classical random walks) have been used by several authors to define measures of centrality on graphs. A detailed presentation of quantum walks goes beyond the scope of the present work; we refer the interested reader to the seminal paper [1] and to the review [32], as well as the book [30]. Much of the literature on quantum centrality relies on discrete-time quantum walks: one notable example is the (discrete) Quantum Page Rank, here abbreviated as DQPR [28]. Note that, for a graph with n nodes, these methods typically work in an n 2 -dimensional state space, as required by the coined or Szegedy formulations of the DTQW (although in some cases, as for DQPR, it can be proved that the non-trivial component of the dynamics actually takes place in a subspace of dimension at most 2n).
Continuous-time quantum walks [15,14,9] have also been used to define notions of quantum centrality for undirected networks. A CTQW on a graph G with n vertices is a process that takes place in a complex Hilbert space of dimension n, spanned by basis states |j , with j = 1, . . . , n, each of them associated with the corresponding node. A generic state of the system is denoted as |ψ and takes the form where the amplitudes a 1 , . . . , a n ∈ C are such that n j=1 |a j | 2 = 1. Note that each amplitude a j can be expressed as the scalar product j|ψ . Its square modulus |a j | 2 is the occupation of node j, i.e., the probability of finding the system in the state |j after a measurement.
The time evolution of a CTQW on a graph G is described by the Schrödinger equation where |ψ(t) is the state of the system at time t, and the Hamiltonian operator H encodes the structure of the graph. Two common choices for the Hamiltonian are the graph Laplacian and the adjacency matrix, which are symmetric in the hypothesis of undirected G; see [34] for motivation and a comparison. The general solution of (4) yields the state of the system at time t and is given by where U (t) = e −iHt is the unitary evolution operator of the system and |ψ(0) is the initial state. Quantum properties of the CTQW include superposition of states and time reversibility; the latter is a consequence of the unitarity of the evolution operator and implies that there is no limiting state. We recall here a CTQW-based centrality measure introduced in [23] for undirected graphs. This approach has the merit of limiting the dimension of the Hilbert space to n, for an n-node graph. It can be summarised in three main steps: 1. Prepare the initial state (the "walker") in an equal superposition of all vertex states: |j .
2. Propagate the walker for a sufficiently large time t: where the Hamiltonian H is chosen as the adjacency matrix of the graph.
3. Compute the time-average probability distribution of finding the walker at each vertex j; this is the centrality score of node j: Note that the introduction of time averages at step 3 is made necessary by the absence of a limit state and is a recurrent ingredient in the analysis of both discrete-and continuous-time quantum walks. An interesting attempt at modeling quantum centrality on directed graphs through a nonunitary evolution operator has been proposed in [22] and [35] exploiting parity-time symmetry.

Three centrality methods in directed networks based on unitary CTQW
Building on ideas from [23] and [5], in this work we propose to employ continuous-time quantum walks to define a measure of hub and authority centrality for directed graphs, while maintaining unitarity. We apply a bipartization approach: broadly speaking, one can think of obtaining hub and authority centrality scores for G by applying an undirected centrality measure to the bipartite graph associated with G. This idea is put forward in [5] for the exponential-based subgraph centrality. It also holds for HITS: one may equivalently apply HITS to a directed graph and compute the hub and authority scores x and y as in (1), or consider the associated undirected bipartite graph, compute the positive dominant eigenvector u of A and take u(1 : n) as hub scores, u(n + 1 : 2n) as authority scores (see again [5]). In other words, we can think of nodes 1, . . . , n in the bipartite graph as corresponding to the nodes of G in their role as hubs, and of nodes n + 1, . . . , 2n as the nodes of G in their role as authorities.

Two methods based on the adjacency matrix: CQAu and CQAw
Now, let G be a directed graph with n nodes and let A be the associated adjacency matrix. As in PageRank, consider the rank-one correctioñ where α ∈ [0, 1] is a suitably chosen parameter. Define the symmetric matrix H of size 2n × 2n as follows: The matrix H represents our Hamiltonian operator, which will be used to model a CTQW in a Hilbert space of dimension 2n. The motivation for introducing the correction (6) stems from the following considerations. If α = 1, that is, if there is no rank-one correction of the adjacency matrix, then the Hamiltonian H is the adjacency matrix of the undirected bipartite graph B G associated with G. Note that B G might not be connected, even if G is strongly connected; see, e.g., Example 5 in Section 4. In such cases, the Hamiltonian H with α = 1 gives rise to a biased model, because the resulting CTQW is "trapped" in separate connected components. An extreme example of such behavior arises in presence of a node with zero in-degree or out-degree: one of its corresponding nodes in B G turns out to be disconnected from the rest of the graph, so its occupation remains fixed at the initial value throughout the walk. The rank-one correction in (6) solves this difficulty and adds a moderate random surfer effect. In our experiments we take α = 0.85 as is often done for classical PageRank.
The CTQW is now described by the Schrödinger differential equation (4) with H as in (7). Therefore the state of the system at time t is where the evolution operator U (t) = e −iHt is the exponential of a Hermitian matrix and is therefore unitary. (More details on the choice of the initial state |ψ(0) will be given later in this section).
With this approach, the hub centrality of node j in G is defined as and the authority centrality of node j is The limits in (8) and (9) are always well-defined. In fact we have the following result, adapted from its discrete-time version in [1]: a j |φ j , with a 1 , . . . , a N ∈ C, be the initial state of the system, written in the eigenstate basis, and denote as |ψ(t) the state of the system at time t. Then for any state |ξ it holds where the asterisk * denotes the complex conjugate.
Proof. Since we have U (t) = N j=1 λ j (t) |φ j φ j | and |ψ(0) = N j=1 a j |φ j , the state of the system at time t can be written as using the orthonormality of the eigenstate basis. Given a state |ξ , let us consider the projection of |ξ on |ψ(t) . It holds and therefore the probability of measuring the state |ξ in |ψ(t) is, for a given t, Now the time average can be written as Let us focus on the quantity is uniformly bounded in modulus, and therefore κ = 0. As a consequence, in the right-hand side of (10) the terms corresponding to pairs (j, k) where θ j = θ k are zero in the limit T → ∞. From a physical viewpoint one might say that the interference between subspaces of different energy vanishes in the long-time average. The thesis follows immediately.
Note that the limit (and hence the centrality scores) depend on the initial state and on the eigenstates of H, but not on the eigenvalues of H.
Let us now discuss the choice of the initial state |ψ(0) . This is a crucial part in the definition of our centrality measures, as highlighted by the results above.
The most natural choice would seem to be the same as in [23], i.e., a uniform occupation of the nodes: The method that computes hub and authority scores as in (8) and (9), with the initial state defined as in (11), will be referred to as CQAu. (Here "CQ" stands for Continuous-time Quantum walk, "A" denotes the use of the adjacency matrix in the definition of the Hamiltonian, and "u" refers to the choice of a uniformly distributed initial state).
For reasons that will be discussed below in this section and in Section 4, we also consider the following choice for the initial state: where d k is the degree of the k-th node in the bipartite graph. Therefore, the initial occupation of the first n nodes in the bipartite graph is proportional to the out-degrees of the nodes in the original directed graph, and the occupation of the last n nodes is proportional to the in-degrees. The method that computes hub and authority scores via (8) and (9), with the weighted initial state (12), will be referred to as CQAw. Despite the use of the same evolution operator, the two methods can lead to significantly different centrality rankings, as it will be seen in Section 4. Theorem 1 offers an interesting perspective on the choice of the initial state |ψ(0) and on comparisons with other (classical) ranking methods where the eigenstructures of suitably chosen matrices play a relevant role. Let us assume for simplicity that in this discussion all matrices have simple, distinct eigenvalues. Consider first the definition of subgraph centrality (see e.g. [12]) for an undirected n-node network: the score c(i) of node i is given by the i-th diagonal entry of the exponential of the (symmetric) adjacency matrix: where e i is the i-th vector of the canonical basis in R n . Let A = V ΛV T be the eigendecomposition of A, with Λ = diag(λ 1 , . . . , λ n ). We assume here that the eigenvalues are in decreasing order. Then it holds e A = n k=0 e λ k v k v T k , where v 1 , . . . , v n , the columns of V , are the eigenvectors of A. So the expression for c(i) can be rewritten as In other words, we are looking at e A as a linear combination of rank-one terms, each of them defined by one eigenvector and weighted with the exponential of the corresponding eigenvalue. The centrality c(i) is the sum of the i-th diagonal entries of these rank-one terms and can be seen as a term e λ 1 (V i,k ) 2 associated with the dominant eigenvector, plus corrections with smaller coefficients depending on the other eigenvectors. Now let us look at HITS. It has been already mentioned in Section 2 that this method computes the dominant eigenvectors of AA T and A T A. Consider, as above, the eigendecomposition AA T = V ΛV T : then the hub score h(i) of node i can be written as where f (x) is any function such that f (λ 1 ) = 1 and f (λ j ) = 0 for j = 2, . . . , n.
A similar expression, obtained from the eigendecomposition of A T A, holds for authority scores, and an analogous argument could be made for other ranking methods that ultimately rely on the computation of a dominant eigenvector. Generally speaking, we conclude that, for a large family of ranking methods, centrality scores are given by expressions like (14), where {λ j , v j } are the eigenpairs of the relevant matrix encoding the graph structure, and f (x) is a suitably chosen function. Now compare (13) and (14) to Corollary 2. In the CTQW setting, the coefficients a j of the initial state in the eigenvector basis clearly play a similar role to e λ j or f (λ j ) for subgraph centrality and HITS, respectively. In other words, the choice of the initial state for a CTQW, where the relevant matrix is the evolution operator, corresponds to the choice of a weight function f (x) in (14).
Remark 1. It is well-known (see e.g., [11]) that the HITS hub and authority scores correlate strongly with the out-and in-degrees of the nodes. This observation, combined with the discussion above, provides an additional motivation for the choice of the initial state |ψ(0) as in (12).

A method based on the Google matrix: CQG
The construction of the Hamiltonian operator H in (6) and (7) is based on the adjacency matrix A. In principle, however, any matrix that encodes the structure of the graph can be employed to build a valid H on the bipartite graph. For instance, in order to obtain rankings related to the classical PageRank, one can use the Google matrix G from (2) instead of A and define In this setup, the matrix G T in the second block row, acting on the upper half of the state vector, describes a "Google-like" CTQW. Authority scores are extracted from the lower half of the limiting distribution. Note that the Google matrices used for classical and reverse PageRank are not the transpose of one another. Indeed, the correction of dangling nodes is not symmetrical, nor is the row normalization. In order to compute hub scores, we need to consider a different random walk described by a different Hamiltonian operator where G r is the Google matrix obtained from the transpose of the adjacency matrix of the graph, as in reverse PageRank. As above, the hub scores are given by the lower half of the limiting distribution. Note that in this approach we need to run two separate CTQW to obtain hub and authority scores, whereas in CQAu and in CQAw a single random walk yields both. The method described in this subsection, with the initial state defined as in (11), will be referred to as CQG in the following.
Of course, the results of Theorem 1 and of Corollary 1 and 2 also hold in this case, since they apply to any unitary evolution.

Numerical experiments
We test the behavior of the three proposed CTQW-based centrality measures (CQAu, CQAw and CQG) on several examples of directed networks and compare them to other ranking algorithms: HITS, the method by Benzi et al. (BEK) [5], PageRank/reverse PageRank (PR) and, when computationally feasible, the discrete-time quantum PageRank presented in [28] (DQPR). In these experiments, HITS is always initialized with a uniform vector and implemented as a power method for the computation of the dominant eigenvalue of AA T and A T A. DQPR is applied through an adaptation of Theorem 3.4 in [1], in combination with the speedup techniques outlined in [28].
In this paper we do not attempt a quantum implementation of the proposed centrality measures: all the numerical tests involve classical computations. The limits in (8) and (9) are computed via the results of Theorem 1. We also tried approximating these limits by computing integrals for increasing values of T via numerical quadrature and stopping when the variation of the corresponding time average became smaller than a fixed tolerance. Note that, in the interest of speeding up these classical simulations, one may also apply fast methods for approximating the action of the matrix exponential on a vector or bilinear forms associated with a matrix function: see, e.g., [2,17]. The approach based on Theorem 1, however, turned out to be faster.
All the methods were implemented in Octave and run on a laptop equipped with a 4-core Intel i7-7500U 2.70GHz processor, with 16 GB of RAM.
This section summarizes the main results obtained for the various methods. See Appendix 5 for the complete data.

Small graphs
In this subsection we compare ranking methods on a few small, simple graphs, where "reasonable" rankings are easily determined by inspection. These examples are useful to observe typical behaviours and pathologies of the tested methods. The examples are shown in Figures 1 (examples 1-4) and 2 (example 5).
Example 3: star graph, i.e., a central hub (node 1) connected to all the other nodes, and no other edge present.
Example 4: tailed graph, i.e., n 1 initial nodes connected as in a path graph, followed by n 2 nodes that form a complete subgraph. Node n 1 is connected to all the n 2 nodes in the complete subgraph.
Example 5: an example of strongly connected graph whose associate bipartite graph is not connected, taken from [5].
An interesting result emerging from these tests is the evidence of a pathology affecting almost all the quantum methods (including DQPR), except CQAw. When a graph contains "no-hub" nodes, i.e., nodes with zero outdegree, any sensible hub ranking should place them at the bottom. The same can be said for "no-authority" nodes (i.e., nodes with zero in-degree) in authority rankings. This expectation is satisfied for all the classical methods and for CQAw, but not in the other quantum methods. CQAu fails in Example 2 (node n comes second in the hub ranking; by symmetry, node 1 comes second in the authority ranking) and in Example 3 (node 1 comes first as an authority). DQPR fails in Example 2, with the same behaviour as CQAu, and in Example 4, where node 1 is not last in the authority ranking. CQG fails on Example 4, where node 1 is slightly above nodes 2, 3 and 4 as an authority. This "quantum pathology" will have very noticeable consequences in an example of the next subsection, and affects especially CQAu. In fact, it is the discovery of this anomalous behaviour in CQAu that led us to devise the method CQAw. In all the tests we performed, CQAw proved to be immune to the pathology, correctly ranking no-hub and no-authority nodes in the last positions 1 .
The results of the numerical experiments also lead us to formulate the following observations: • Recall that, in path graphs, HITS and PR display different behaviours.
HITS singles out the last node (worse hub) or the first node (worse authority) and gives a tie for all the other nodes. PR, on the other hand, finds a strictly monotonic sequence of scores: increasing for authorities and decreasing for hubs.
How do the quantum methods compare? It turns out that only DPQR behaves like PR, whereas all the other methods, including CQG, produce HITS-like rankings.
• Note that in our results HITS does not detect the top-ranked hubs and authorities in Examples 2 and 5, whereas the other methods do. HITS also fails to recognize the worse authority in Example 4, because node 1 has the same score as nodes 2, 3 and 4, although this is a less significant failure. However, note that Example 5 is a case where the hub and authority matrices A T A and AA T have a dominant eigenvalue of multiplicity 2; as a consequence, the computed eigenvectors -and therefore the rankings -depend on the initial vector and on implementation details. For a discussion of Example 5 see also [5].
• Hub results for Example 4 highlight the difference between Google-like rankings, where tail nodes receive top scores, thus emphasizing the fact that they indirectly reach all the other nodes, and HITS-like rankings, which give more importance to the number of direct outgoing edges. Among the other methods, CQAw, BEK and -curiously -DQPR show a HITS-like behaviour, while CQG exhibits a PR-like behaviour.
• DQPR gives an unexpected authority ranking in Example 4: the first two nodes in the ranking are 3 and 2, but they clearly do not have a relevant role as authorities in the graph structure. Moreover, node 1 is not ranked last as it should be.
In conclusion, from the tests on small graphs, CQAw appears to be immune to "quantum pathologies" and provides rankings that look overall quite similar to HITS. CQG is not immune to quantum pathologies, but does not seem to be strongly affected, either. Its rankings are mostly related to PR, with some exception, such as path graphs. CQAu, on the other hand, is too strongly affected by quantum pathologies to give reliable results on small graphs, but it usually gives the same result as CQAw at least on the topranked node.

Artificial scale-free graphs
In this example, three 128-nodes graphs have been generated using the software NetworkX [19], according to the model developed in [6] for the construction of scale-free graphs. The model requires three parameters: α and γ determine the probability of adding new nodes according to the in-degree and out-degree distributions, respectively, whereas β determines the probability of adding edges between pairs of existing nodes. Here the parameters have been chosen so as to generate three graphs with different properties. We examine the qualitative accordance of the top 10 nodes of the rankings, which are usually the most interesting, and the global correspondence of the rankings measured by Kendall's τ test.
The chosen examples are: The experiments show the effect of "quantum pathologies" on CQAu rankings: "bubbles" of ex-aequo no-hub or no-authority nodes tend to float up to high-ranked positions, disrupting the expected structure of the rankings and, in some cases, even reaching top positions. The most striking example is given by Example 6. In the hub ranking, the 9 no-hub nodes are ranked from 3rd to 11th, disrupting the top 10 ranking. (Incidentally, the same happens in DQPR, with the difference that the no-hub nodes are not ex-aequo). In the authority ranking, the 116 no-authority nodes are placed 8th-121st, above 7 nodes that indeed have incoming edges.
In the other two examples, the "bubble" does not reach the top 10 positions, but it is present anyway, as one can see by observing the overall ranking: in Example 7, positions 14th-74th for hubs and 19th-83rd for authorities; in Example 8, positions 14th-73rd for hubs and 16th-80th for authorities. So, Figure 3: Graphs used for testing the ranking methods (Examples 6, 7, 8). At the right of each graph the adjacency matrix is shown.
when we look at the global rankings given by CQAu we cannot expect to find meaningful results. Kendall's τ between CQAu and any of the other methods, including CQAw, is typically quite low, sometimes even negative.
However, if one looks at the top-ranked nodes, avoiding the "bubble" in CQAu, there is usually an excellent agreement between CQAu and CQAw. So, the CQAu method may still have some interest if only a few top-ranked nodes are sought. Its advantage over CQAw lies in the preparation of the quantum initial state, which is easier for a uniform vector.
The CQAw method seems to provide fully satisfying results. It does not show any evident pathologies, and its rankings are generally in excellent agreement with HITS (and BEK) rankings. Kendall's τ between CQAw and HITS is always above 0.82. The top-ranked node and the set of top 3 nodes coincide in all the six computed rankings. The average superposition of the top 10 nodes (i.e., the number of nodes appearing in both top 10 lists given by CQAw and HITS, averaged over the six rankings) is 9.17.
CQG, on the whole, shows a good agreement with PR. Kendall's τ is almost always above 0.8 (except for hubs in Example 6, where it is 0.573), and the average superposition of the top 10 nodes is 7.58. However, some peculiarities can be observed. For instance, in the autority ranking for Example 6, node 84 is in second position, above node 2, whereas no other method places node 84 above the 10th position. In the hub ranking for Example 7, CQG is the only method that does not place node 15 first (it is 5th instead). In the authority ranking for Example 8 it fails to identify node 2 as the main authority, placing node 36 instead on top. We did not find a clear explanation for this behaviour.

Larger real-life networks
Here we test ranking algorithms on a few larger real-life graphs. As above, we examine the top 10 nodes by inspection and compare the global rankings via Kendall's τ . In these examples we do not apply DQPR because of its high computational cost.
The test networks are: Example 9: the metabolic network of the bacterium E. coli, taken from companion data [4] to Barabási's book [3]. Each node represents a metabolite, and, if there is a reaction where A is an input and B is a product, an edge A→B is present. The network has 1039 nodes and 5802 edges.
Example 10: a network extracted from references between word categories in Roget's Thesaurus. The network is taken from the SuiteSparse Matrix Collection [10]. It has 1022 nodes and 5075 links.
Example 11: a network of the web pages linking to www.epa.gov, which dates from 2006. The network is taken from the SuiteSparse Matrix Collection [10]. The graph has 4472 nodes and 8965 links.
The results confirm the good agreement between CQAw and HITS: the top-ranked node is always the same, Kendall's τ is always above 0.66, and the average superposition of the top 10 nodes is 8.17. The agreement is especially good for Examples 9 and 10 (τ > 0.82 and never less than 9 coincident nodes), but a slight discordance is present in Example 11. Note that in these examples the top 10 nodes for CQAu are in excellent agreement with the results of CQAw: on average, there are 9 coincident nodes. This result supports the claim that the method can be useful when looking for the top-ranked nodes in large graphs. However, Kendall's τ between the two methods is not always good, as it can fall below 0.5: this shows that the overall agreement is not as good as the agreement of the top 10 nodes.
The behaviour of CQG is sometimes puzzling. When looking at the first 10 nodes, we see a good agreement with the other methods in Example 9, a bad agreement in Example 10 (in both hub and authority rankings, only one of the top 10 nodes is present in PR rankings, and no nodes in HITS rankings) and, in Example 11, a very good agreement with PR for hubs (8 coincident nodes) and a very bad agreement for authorities (no coincident nodes). However, Kendall's τ paints a different picture, showing a poor agreement with PR in Example 9 (τ ≈ 0.46), a better agreement for Example 10 (τ ≈ 0.57, despite the results on the top 10 nodes) and a surprisingly good agreement (τ > 0.8 for both hubs and authorities) in Example 11. No clear explanations were found for this apparently erratic behaviour.

Conclusions
We have presented and tested three centrality methods for directed networks based on continuos-time quantum walks. The underlying common idea is the introduction of a Hermitian Hamiltonian matrix related to the undirected bipartite graph associated to the given network, therefore allowing for a unitary evolution in 2n dimensions. The results of the numerical tests lead to the following evaluations of the three proposed methods: • The method CQAw gives completely satisfying results on all the tests.
It seems to be the only quantum method among the tested ones (the three proposed, plus DQPR) that is immune to the typical "quantum pathologies" present in certain small graphs, a fact confirmed by further experiments performed on much larger diamond-, star-and tailedgraphs. The rankings for CQAw are strongly correlated with the rankings given by HITS. Moreover, the method provides hub and authority rankings in a single run. The only drawback we see is the potential difficulty in preparing an initial quantum state with the required mean occupation values, when implementing a quantum algorithm based on this method; note however that this drawback is common to other quantum ranking algorithms such as DQPR, and that efficient methods for the preparation of non-trivial quantum states are available (see e.g., [18,20]).
• The method CQAu, despite the use of the same evolution operator as CQAw, is the most affected by the quantum pathologies discussed above, and it fails on diamond-and star-graphs for any tested number of nodes. In graphs with a large number of no-hubs (or no-authority) nodes, these nodes are often ranked higher than weak hubs or weak authorities. Despite these problems, however, the method performed surprisingly well in identifying the top nodes in large graphs, in the tested examples: in the three tests with n > 1000 (Examples 9-11), the top 10 rankings turned out to be almost indistinguishable from CQAw. Also, for the three tests on 128-node graphs, the only unfavourable case -when considering the top 10 nodes only -is Example 6. Of course, quantum pathologies disrupt in any case the rankings below the top positions, and a good agreement of the whole ranking cannot be expected: this is confirmed by the usually poor results of Kendall's τ test when comparing CQAu with other methods. In conclusion, from these experiments it seems plausible that CQAu could be employed, for large networks and with the goal of identifying top-ranked nodes only, in the case where the preparation of a uniformly-occupied state proved to be advantageous enough w.r.t. CQAw to justify a potentially less dependable performance.
• The CQG method is the most puzzling of the three. It has the disadvantage of requiring two runs to obtain hub and authority rankings, as it needs two different evolution operators. It is only slightly affected by quantum pathologies. Usually it identifies top-ranked nodes that are compatible with other rankings (especially PR and DQPR), but its behaviour sometimes does not look consistent with the graph structure (see e.g. Example 8). On a same graph, it can give good results for hubs and bad results for authorities (Example 11). However, Kendall's τ between CQG and PR is usually high, showing that the two rankings, as a whole, are in fact closely related; but this property do not always translate to detection of the same top-ranked nodes. Such considerations discourage the use of CQG as presented here, although they suggest intriguing questions for future research.
Appendix A