ABSTRACT (original article): The Internet is one of the most valuable technologies invented to date. Among them, Google is the most widely used search engine. The PageRank algorithm is the backbone of Google search, ranking web pages according to relevance and recency. We employ quantum stochastic walks (QSWs) to improve the classical PageRank (CPR) algorithm based on classical continuous time random walks. We implement QSW via two schemes: only incoherence and dephasing with incoherence. Page Rank using Quantum Stochastic Walks with only incoherence or with dephasing and incoherence best resolves degeneracies that are unresolvable via Classical Page Rank and with a convergence time comparable to that for Classical Page Rank, which is generally the minimum. For some networks, the two QSW schemes obtain a convergence time lower than CPR and an almost degeneracy-free ranking compared to CPR. CITATION (original article): Colin Benjamin and Naini Dudhe (2024), Resolving degeneracies in Google search via quantum stochastic walks, J. Stat. Mech. (2024) 013402. https://doi.org/10.1088/1742-5468/ad1384
Wolfram Technology Conference 2024: https://www.wolfram.com/events/technology-conference/2024/presentations/
Wolfram Technology Conference 2024: https://www.wolfram.com/events/technology-conference/2024/presentations/
Google Page Rank (Classical Page Rank)
Google Page Rank (Classical Page Rank)
◼
Two parameters define the efficiency of the PageRank algorithm, first, the degeneracy in ranks, and second, the convergence time. The better algorithm is the algorithm that returns the least degeneracies and converges faster.
◼
Internet query search devised by Google Page rank is a two-step process; first, based on your search query, a whole host of websites with matching content is listed in no particular order. Most pre-Google search engines, such as Lycos, Looksmart, etc., stopped here.
◼
The user looked through this list and found what was meaningful; s/he generally scrolled down sequentially.
◼
Google’s masterstroke was in adding the second step, which was to rank these websites with the matching content based on links between them.
◼
To do this, it relied on a continuous time random walk. The website with the highest rank on this listed network of websites will be the website with a high number of links to itself, i.e., a highly connected vertex in a network, as well as one that possesses links from other highly ranked websites.
S. Brin and L. Page, The anatomy of a large-scale hypertextual web search engine, Computer networks and ISDN systems 30, 107 (1998).
I. Rogers, The Google Pagerank algorithm and how it works, (2002). https://en.wikipedia.org/wiki/PageRank, PageRank, Wikipedia.
S. Brin and L. Page, The anatomy of a large-scale hypertextual web search engine, Computer networks and ISDN systems 30, 107 (1998).
I. Rogers, The Google Pagerank algorithm and how it works, (2002). https://en.wikipedia.org/wiki/PageRank, PageRank, Wikipedia.
Classical continuous time random walks and classical Page Rank
Classical continuous time random walks and classical Page Rank
◼
Any complex network can be modeled as a graph of M vertices with E edges. To model a network of different websites: the vertices would represent the webpages and the edges would represent the links from one webpage to the other.
◼
Adjacency matrix will have the entry = 1 and = 0 if the edge is directed from j to i and if it is undirected, then = = 1. The out-degree of a vertex is defined as the total number of edges leaving the vertex and is given by: out-deg(j) == . γ = transition rate between neighboring vertices .
A
ij
A
ji
A
ij
A
ji
d
j
Σ
ij
A
ij
◼
To find an expression for the evolution of the transition matrix in time, we define a generator matrix H with its entry: in the language of webpages, adjacent vertices or websites are those between whom an edge or a link exists.
th
ij
◼
Transition matrix entry T(t) is defined as probability of transitioning from vertex j to i during time interval ϵ.(ϵ) = 1 − γϵ, if and (ϵ) =γϵ, if .Transition matrix entry at time t+ϵ is product of transition matrix entries at t and t+ϵ, thus (t + ϵ) =(t)(ϵ), k runs over all vertices, or, (t + ϵ ) =(t)(ϵ) + (t)(ϵ) = (t)(1- ϵ) -ϵ (t)
ij
T
ij
d
j
i=j
T
ij
i≠j
T
ij
∑
k
T
ik
T
kj
T
ij
T
ij
T
jj
∑
k≠j
T
ik
T
kj
T
ij
H
jj
∑
k≠j
T
ik
H
kj
◼
Thus, we get: , the solution of this differential equation with initial condition T(0) = δ is T(t) = e
ij
ij
-Ht
◼
The probability vector is a vector with dimension M x 1 and denotes the probability of the walker being at each vertex of the graph.
Probability vector evolution:(t) = T (t) (0).
Probability vector evolution:
p
p
◼
Iterating this equation over and over again, we eventually reach the stationary state = probability vector of the stationary state.
◼
The entries of this stationary solution represent the ranks of the different vertices.
R. Portugal, Quantum Walks and Search Algorithms (Springer,2018).
R. Portugal, Quantum Walks and Search Algorithms (Springer,2018).
Google Matrix
Google Matrix
◼
◼
The factor 1/M is to avoid dead ends by introducing random jumps, in directed graphs. Continuously clicking on links from one website to another may lead us to a site with no further links to click, i.e., a dead end. In order to avoid that, random jumps are introduced, which take the user to another site chosen randomly.
◼
The factor α is the damping factor, and 0 ≤ α ≤1 . α controls the ratio of random jumps to the original edges of the graph. We want the random jumps to be minimal, and thus, a large value of α is needed. In our paper we take α to be 0.9.
◼
For an undirected graph, adjacency matric is symmetric and situation changes, there are no dead ends so α = 1. Since quantum mechanics is unitary, the Hamiltonian which is basically the adjacency matrix has to be Hermitian, and therefore graphs considered for QPR have to be undirected. To have a realistic comparison between Classical Page rank and Quantum Page rank we consider both directed and symmetric undirected graphs for CPR.
Remove["Global`*"]G1=Graph[Range[8],{12,13,14,23,24,34,35,57,65,76,78,82},VertexLabels"Name",VertexSizeLarge]AdjacencyMatrix[G1]//MatrixFormalpha=0.85;HighlightCentrality[G_,CPR_]:=HighlightGraph[G,Table[Style[VertexList[G]〚i〛,ColorData["TemperatureMap"][CPR〚i〛/Max[CPR]]],{i,VertexCount[G]}],VertexSizeLarge];CPR1=PageRankCentrality[G1,alpha]HighlightCentrality[G1,CPR1]CountDistinct[CPR1];Print["# of distinct vertex ranks via CPR(directed)=",CountDistinct[CPR1]]
Out[]=
Out[]//MatrixForm=
0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
Out[]=
{0.149239,0.192843,0.157958,0.149239,0.108274,0.0658326,0.110783,0.0658326}
Out[]=
# of distinct vertex ranks via CPR(directed)=6
Page - rank centralities represent the likelihood that a person randomly following links arrives at any particular page on the web graph .
In[]:=
G=Graph[Range[8],{12,13,14,23,24,34,3->5,5->7,6->5,7->6,7->8,8->2},VertexLabels"Name",VertexSizeLarge,DirectedEdgesFalse]AdjacencyMatrix[G]//MatrixFormCPR=PageRankCentrality[G,1.0]HighlightCentrality[G,CPR]CountDistinct[CPR];Print["# of distinct vertex ranks via CPR(Undirected)=",CountDistinct[CPR]]
Out[]=
Out[]//MatrixForm=
0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 |
1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
Out[]=
{0.125,0.166667,0.166667,0.125,0.125,0.0833333,0.125,0.0833333}
Out[]=
# of distinct vertex ranks via CPR(Undirected)=3
In[]:=
G1=DirectedGraph[RandomGraph[WattsStrogatzGraphDistribution[100,0.025]],"Random"];CPR1=PageRankCentrality[G1,alpha];HighlightCentrality[G1,CPR1]CountDistinct[CPR1];Print["# of distinct vertex ranks via CPR(directed)=",CountDistinct[CPR1]]
Out[]=
Quantum Stochastic Walks (QSW)
Quantum Stochastic Walks (QSW)
◼
Parameter 0 ≤ ω ≤1 is responsible for interpolating between CTRW and CTQW.
◼
X depends on the choice of the Lindblad operator, which represents scattering between a pair of vertices.
◼
The first term indicates a contribution from coherent dynamics. The second term accounts for a contribution from incoherent dynamics via the two methods: only incoherence (OI), and dephasing with incoherence (DI).
J. D. Whitfield, C. A. Rodr’guez-Rosario, and A. Aspuru-Guzik, Quantum stochastic walks: A generalization of classical random walks and quantum walks, Physical Review A 81, 022323 (2010).
A. Kossakowski, On quantum statistical mechanics of non-Hamiltonian systems, Reports on Mathematical Physics 3, 247 (1972).
G. Lindblad, On the generators of quantum dynamical semigroups, Communications in Mathematical Physics 48, 119 (1976).
A. Kossakowski, On quantum statistical mechanics of non-Hamiltonian systems, Reports on Mathematical Physics 3, 247 (1972).
G. Lindblad, On the generators of quantum dynamical semigroups, Communications in Mathematical Physics 48, 119 (1976).
Quantum stochastic walks
Quantum stochastic walks
Solving QSW
Solving QSW
◼
We use the QSW methods with either only incoherence or dephasing with incoherence to rank vertices in a network since the QSW scheme of pure dephasing, in its stationary state, returns the same rank for all vertices.
Calculation of Degeneracy & CONVERGENCE TIME
Calculation of Degeneracy & CONVERGENCE TIME
◼
CALCULATION OF DEGENERACY
• The quantum PageRank algorithm (QPR) computes the ranking of each vertex in a graph and gives the output. For classical PageRank we use the in built Mathematica command PageRankCentrality.
• Any vertex with more links to it will have a higher rank. Furthermore, any vertex having links from a higher ranked vertex will, in turn, have a high-rank itself.
• Unavoidably, some of the vertices have the possibility of getting the same rank as they might have the same number of links from other websites, and the quality of the links might be similar too.
• It is undesirable since the user might have difficulties perceiving which website is more relevant. It gives rise to poor search quality.
• Thus, our aim in this work is to find a scheme that eliminates degeneracies between ranks of vertices.
• To this end, we count the total number of all these possible degeneracies using CPR as well as QPR with the two QSW schemes and compare them.
• The quantum PageRank algorithm (QPR) computes the ranking of each vertex in a graph and gives the output. For classical PageRank we use the in built Mathematica command PageRankCentrality.
• Any vertex with more links to it will have a higher rank. Furthermore, any vertex having links from a higher ranked vertex will, in turn, have a high-rank itself.
• Unavoidably, some of the vertices have the possibility of getting the same rank as they might have the same number of links from other websites, and the quality of the links might be similar too.
• It is undesirable since the user might have difficulties perceiving which website is more relevant. It gives rise to poor search quality.
• Thus, our aim in this work is to find a scheme that eliminates degeneracies between ranks of vertices.
• To this end, we count the total number of all these possible degeneracies using CPR as well as QPR with the two QSW schemes and compare them.
Small World Networks
Small World Networks
◼
We analyze the quantum PageRank algorithm on these networks because they have properties of small-world networks, which is a proxy for internet networks on the world wide web.
◼
WATTS-STROGATZ: the vertex degree follows a modified Poisson distribution with an exponential tail and it possesses a high clustering coefficient.
◼
ERDOS-RENYI: ER networks have a Poisson distribution for the vertex degree. Examples: Zachary Karate and Bernoulli graph distribution.
◼
SPATIAL: Spatial networks can model neuron connectivity in the brain or short-range communication networks.
◼
All of them have some properties of small-world networks. ER, WS, and SF networks differ based on the distribution P(d) of the degree of the nodes d.
◼
Small world networks possess three essential properties:
(i) any two nodes will have a relatively small distance between them (distance here means that in order to get to one node from the other, the walker will not have to pass through too many nodes), (ii) clustering is high and (iii) hubs are present.
Hubs are the vertices possessing a large degree. In turn, the degree distribution will have a long tail since the hubs will have a much higher degree than others.
Clustering, let us assume one node A is connected to two other nodes B and C; in that case, the chances for B and C to be joined via an edge are high, i.e., A, B and C are mutually connected. It is called clustering.
Some examples of small-world networks are road maps, electric power grids, social networks, neural networks, and even the internet. ER, SF and WS networks all have the property that any two nodes will have relatively less distance between them.
(i) any two nodes will have a relatively small distance between them (distance here means that in order to get to one node from the other, the walker will not have to pass through too many nodes), (ii) clustering is high and (iii) hubs are present.
Hubs are the vertices possessing a large degree. In turn, the degree distribution will have a long tail since the hubs will have a much higher degree than others.
Clustering, let us assume one node A is connected to two other nodes B and C; in that case, the chances for B and C to be joined via an edge are high, i.e., A, B and C are mutually connected. It is called clustering.
Some examples of small-world networks are road maps, electric power grids, social networks, neural networks, and even the internet. ER, SF and WS networks all have the property that any two nodes will have relatively less distance between them.
Mathematica Code to Calculate Convergence time
Mathematica Code to Calculate Convergence time
QSWalk: a Mathematica package for quantum stochastic walks on arbitrary graphs, Peter E. Falloon, Jeremy Rodriguez, Jingbo B. Wang, Computer Physics Communications 217, Pages 162-170 (2017). https://doi.org/10.1016/j.cpc.2017.03.014, DOI:10.17632/8rwd3j9zhk.1 https://data.mendeley.com/datasets/8rwd3j9zhk/1/files/b3ef3c56-2e2c-40e2-9185-8f937641c07b
Example 1: 8 vertex graph
Example 1: 8 vertex graph
Example 2 : Watts Strogatz Graph
Example 2 : Watts Strogatz Graph
Mathematica code to calculate Quantum page rank
Mathematica code to calculate Quantum page rank
Example 1: 8 vertex graph
Example 1: 8 vertex graph
Example 2: Watts-STROGATZ
Example 2: Watts-STROGATZ
Conclusion
Conclusion
◼
Aim: To check whether QPR can resolve degeneracies unresolvable by CPR and the number of navigation steps required to reach the stationary state, which outputs the ranks of vertices in a graph.
◼
Methods: QSW with only incoherence or dephasing with incoherence scheme.
◼
Results: Their efficacy of resolving the degeneracies, is, in general, same or marginally better than CPR for directed graphs and especially much better than CPR for undirected graphs. The convergence time too is either marginally or significantly better than CPR for all networks.
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Resolving degeneracies in Google search via quantum stochastic walks
by Colin Benjamin & Naini Dudhe
Wolfram Community, STAFF PICKS, October 28, 2024
https://community.wolfram.com/groups/-/m/t/3310232
by Colin Benjamin & Naini Dudhe
Wolfram Community, STAFF PICKS, October 28, 2024
https://community.wolfram.com/groups/-/m/t/3310232