Ranking nodes in directed networks via continuous-time quantum walks Paola Boito1and Roberto Grena2

2025-04-29 0 0 331.72KB 25 页 10玖币

侵权投诉

Ranking nodes in directed networks via

continuous-time quantum walks

Paola Boito1and Roberto Grena2

1Dipartimento di Matematica, Universit`a di Pisa, Largo B.

Pontecorvo 5, 56127 Pisa, Italy

2C. R. ENEA Casaccia, via Anguillarese 301, 00123 Roma,

Italy

Abstract

Four new centrality measures for directed networks based on unitary, continuous-

time quantum walks (CTQW) in ndimensions – where nis the number of

nodes – are presented, tested and discussed. The main idea behind these

methods consists in re-casting the classical HITS and PageRank algorithms

as eigenvector problems for symmetric matrices, and using these symmetric

matrices as Hamiltonians for CTQWs, in order to obtain a unitary evolution

operator.

The choice of the initial state is also crucial. Two options were tested: a

vector with uniform occupation and a vector weighted w.r.t. in- or out-degrees

(for authority and hub centrality, respectively). Two methods are based on

a HITS-derived Hamiltonian, and two use a PageRank-derived Hamiltonian.

Centrality scores for the nodes are deﬁned as the average occupation values.

All the methods have been tested on a set of small, simple graphs in

order to spot possible evident drawbacks, and then on a larger number of

artiﬁcially generated larger-sized graphs, in order to draw a comparison with

classical HITS and PageRank. Numerical results show that, despite some

pathologies found in three of the methods when analyzing small graphs, all

the methods are eﬀective in ﬁnding the ﬁrst and top ten nodes in larger

arXiv:2210.13379v1 [quant-ph] 24 Oct 2022

graphs. We comment on the results and oﬀer some insight into the good

accordance between classical and quantum approaches.

1 Introduction

Centrality measures for networks [1, 2] can be loosely deﬁned as measures

of importance of nodes. Notions of centrality have received considerable

interest in the last decades, especially boosted by the important task of

ﬁnding eﬃcient algorithms for ranking web pages in search engines. Two

classical examples of algorithms for computing centrality scores are HITS [3]

and PageRank [4].

In directed networks, nodes can be ranked according to their importance

as hubs or authorities. Roughly speaking, a strong hub is a node that points

to many important nodes and a strong authority is a node that is pointed to

by many important nodes. The notion of “important nodes” depends on the

method: in HITS, which simultaneously provides hubs and authority scores,

good hubs point to good authorities and good authorities are pointed to by

good hubs, whereas in PageRank a node has a higher authority centrality

score if it is pointed to by strong authorities.

Algorithms for webpage ranking usually compute authority centrality, but

any authority method can be easily converted to a hub method by applying

it to the reverse graph obtained by inverting the direction of each link. In

matrix terms, if Ais the adjacency matrix of the original graph, the reverse

graph has adjacency matrix AT. For instance, PageRank is an authority

ranking algorithm, but it can be easily converted to hub ranking (Reverse

PageRank, see e.g. [5, 6]) by applying it to ATinstead of A. HITS, on the

other hand, is fundamentally a power method that alternates between Aand

ATand yields both hub and authority rankings.

An interesting feature of PageRank is the fact that it can be seen as a

random-walk problem: the Google matrix Gbuilt from Ais a stochastic

matrix, thus representing a random walk, and the ranking score of a node

is the asymptotic probability of ﬁnding the walker in that node. This is

an example of the important role that random walks play in many ranking

methods.

The increasing development of research in quantum computation has

sparked an interest in ﬁnding quantum-formulated ranking algorithms for

networks. The relation between node-ranking algorithms and classical ran-

dom walks suggests that it may be useful to explore the theory of quantum

walks on networks, for ranking purposes. On the theory of quantum walks,

we mention, among others, the seminal papers [7, 8, 9, 10] and the review

[11]. A good introduction can be found, for instance, in the recent book [12].

Among other features, quantum walks exhibit faster diﬀusion w.r.t. classical

random walks, thus allowing for algorithmic speedup [13, 14].

In contrast to classical random walks, unitary quantum walks typically

do not converge to a stationary distribution, because of unitary evolution.

Therefore, time-averaging is expected to be required for the extraction of

centrality scores, unless one resorts to the use of mixed quantum-classical

evolution [15] or tunable time-dependent Hamiltonian for adiabatic compu-

tations [16]. Another remarkable feature is that the average occupation of

each node may depend on the initial state, i.e., the prescription of the initial

state is part of the ranking method.

Like classical random walks, quantum walks can be deﬁned either in a

discrete-time (DTQW) or a continuous-time (CTQW) framework [17, 18].

Here we focus on the continuous-time case, which has the merit of taking

place in a Hilbert space of dimension equal to the number of nodes, whereas

DTQW typically require a dimension of the order of the number of edges.

The formulation of a quantum method for centrality measures based on

DTQW or CTQW has been explored by several authors [19, 20, 21, 22,

23, 24, 25, 26, 27]. [20] proposes a method, called Quantum PageRank,

based on a DTQW that evolves in a Hilbert space of dimension n2, where

nis the number of nodes. In CTQW-based methods such as [22, 21], the

quantum walk takes place in a Hilbert space of dimension n; however, such

methods are applicable to undirected graphs only. The authors of [23] have

circumvented the diﬃculty of obtaining an evolution operator from a non-

symmetric Aby forgoing unitarity, and adopting instead non-standard PT-

symmetric Hamiltonians.

In a recent work [28], three unitary-CTQW-based centrality measures for

directed networks were introduced and discussed. Unitarity was obtained

by deﬁning the CTQW on the associated bipartite graph, following the idea

behind [29], hence with a number of degrees of freedom equal to 2n. One of

the methods proved to be especially robust and its rankings were very well

related to HITS rankings; however, no satisfactory results were obtained

when trying to design an algorithm well-related to PageRank. Moreover, the

doubling of the dimension of the Hilbert space is a drawback, only partially

mitigated by the fact that two of the three proposed methods compute hub-

and authority-centrality in a single run.

However, doubling the dimension of the Hilbert space could be unneces-

sary. Classical HITS and PageRank methods can both be reframed as eigen-

vector problems on n×nsymmetric matrices. This fact suggests the idea

of using such matrices as Hamiltonians to deﬁne a unitary n-dimensional

CTQW on the network. Rankings obtained by such a CTQW can be ex-

pected to yield results similar to HITS and PageRank, respectively.

In this paper we explore this possibility, proposing two evolution operators

for CTQW in ndimensions, based on a (slightly modiﬁed) HITS-derived

Hamiltonian and on a PageRank-derived Hamiltonian. As mentioned above,

the initial state must be supplied as well, in order to properly deﬁne the

method. Two choices were studied: a uniformly occupied initial state and

an initial state with occupation numbers weighted w.r.t. node degrees (in-

degrees for authority centrality or out-degrees for hub centrality). On the

whole, we propose four new algorithms, combining the two choices for the

Hamiltonian and the two initial states.

Section 2 provides the background to understand the problem and recalls

the HITS and PageRank algorithms, formulating them as eigenvector prob-

lems on symmetric n×nmatrices. It also outlines the main ideas behind

quantum centrality algorithms. Our CTQW-based methods are presented in

Section 3. Section 4 is devoted to numerical experiments: tests on simple

toy models, which allow us to discuss certain features of the methods, are

followed by tests on more than 5000 larger graphs of diﬀerent sizes (from 128

to 1024 nodes). These tests are designed to check whether the obtained rank-

ings are in good accordance with the results of the classical methods they

are derived from. Three indicators are used: the probability of ﬁnding the

same top-ranked node, the number of common nodes in the top-ten ranking,

and Kendall’s τ[30]. Sections 5 and 6 contain a discussion of the results and

concluding remarks.

2 Background

A(directed) graph Gis a pair (V, E), where Vis 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)∈Eimplies (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.

The adjacency matrix associated with Gis the n×nmatrix A= (Aij ) such

that Aij = 1 if t(i, j)∈E, and Aij = 0 otherwise. Clearly Ais symmetric if

and only if Gis undirected.

The in-degree degin(i) of node iis the number of nodes pointing to node

i, whereas its out-degree degout(i) is the number of nodes pointed to by node

i. It holds degin(i)=(1TA)iand degout(i)=(A1)i, where 1∈Rnis the

vector with all entries equal to 1.

2.1 Classical centrality measures for directed graphs

Among the many centrality measures proposed in the literature for directed

graphs, we recall two popular ones that inspired the present work. Both of

them were originally developed for ranking web pages.

HITS (Hyperlink-Induced Topic Search) [3]. This is an iterative scheme

that computes an authority score and a hub score for each node. Each iter-

ation takes the form

x(k)=ATy(k−1), y(k)=Ax(k),(1)

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 deﬁned as the limit values of the corresponding scores for

k→ ∞. The initial vector is usually chosen as 1

√n1.

This process can also be reframed as a power method, yielding the dom-

inant eigenvector of the symmetric matrices ATA(for authorities) and AAT

(for hubs).

PageRank [4, 31]. Here we recall the PageRank method for authority

scores, as originally conceived for web page ranking. Hub centralities can

be obtained via Reverse PageRank [5, 32], that is, PageRank applied to the

“reversed graph” with adjacency matrix AT.

In the PageRank algorithm, the adjacency matrix Aof the graph is

modiﬁed to obtain the so-called patched adjacency matrix ˜

A, which is row-

stochastic:

Aij =Aij /degout(i) if degout(i)>0,

1/n otherwise.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Rankingnodesindirectednetworksviacontinuous-timequantumwalksPaolaBoito1andRobertoGrena21DipartimentodiMatematica,UniversitadiPisa,LargoB.Pontecorvo5,56127Pisa,Italy2C.R.ENEACasaccia,viaAnguillarese301,00123Roma,ItalyAbstractFournewcentralitymeasuresfordirectednetworksbasedonunitary,continuous-timeq...

展开>> 收起<<

Ranking nodes in directed networks via continuous-time quantum walks Paola Boito1and Roberto Grena2.pdf

共25页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Ranking nodes in directed networks via continuous-time quantum walks Paola Boito1and Roberto Grena2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: