Resolving degeneracies in Google search via quantum stochastic walks

Colin Benjamin, NISER, HBNI, INDIA

www.niser.ac.in/profile/colin
(RowDefault[, (Spacer1), , (Spacer1), ])  #WolframTechConf

ABSTRACT

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.

Resolving degeneracies in Google search via quantum stochastic walks, Colin Benjamin and Naini Dudhe, J. Stat. Mech. (2024) 013402, DOI: 10.1088/1742-5468/ad1384

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.

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 Aij= 1 and Aji = 0 if the edge is directed from j to i and if it is undirected, then Aij = Aji = 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) = Σij Aij.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.

An expression for the evolution of the transition matrix in time, we define a generator matrix H with its ijth  entry  
in the language of webpages, adjacent vertices or websites are those between whom an edge or a link exists. 
Now, multiplying the transition matrices at different times and rearranging the indices, we get: , the solution of this differential equation with initial condition Tij(0) = δij is T(t) = e-Ht

Probability vector evolution:  (OverVector[p])(t) = T (t) (OverVector[p])(0).

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).

Google Matrix

The factor 1/M is to avoid dead ends by introducing random jumps, in undirected 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. We take α to be 0.9 throughout this paper, generally, it is taken to be 0.85.

For an Undirected graph, 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 undirected graphs for CPR.

Remove["Global`*"]
G1=Graph[Range[8],{1\[UndirectedEdge]2,1\[UndirectedEdge]3,1\[UndirectedEdge]4,2\[UndirectedEdge]3,2\[UndirectedEdge]4,3\[UndirectedEdge]4,3\[DirectedEdge]5,5\[DirectedEdge]7,6\[DirectedEdge]5,7\[DirectedEdge]6,7\[DirectedEdge]8,8\[DirectedEdge]2},VertexLabels->"Name",VertexSize->Large]
alpha=0.85;G = Graph[Range[8],{1\[UndirectedEdge]2,1\[UndirectedEdge]3,1\[UndirectedEdge]4,2\[UndirectedEdge]3,2\[UndirectedEdge]4,3\[UndirectedEdge]4,3->5,5->7,6->5,7->6,7->8,8->2},VertexLabels->"Name",VertexSize->Large,DirectedEdges->False]
HighlightCentrality[G_, CPR_]:=HighlightGraph[G,Table[Style[VertexList[G][[i]],ColorData["TemperatureMap"][CPR[[i]]/Max[CPR]]],{i,VertexCount[G]}],VertexSize->Large];
CPR1=PageRankCentrality[G1,alpha]
HighlightCentrality[G1,CPR1]
CountDistinct[CPR1]
CPR=PageRankCentrality[G,1.0]
HighlightCentrality[G,CPR]
CountDistinct[CPR]

Page-rank centralities represent the likelihood that a person randomly following links arrives at any particular page on the web graph.

Quantum Stochastic Walks (QSW)

QSW can be used to model quantum processes that are coupled to the environment. ρ(t) is the density matrix representation of walker at time t with dimension MxM.  
M is the total number of vertices and basis states as |1>,….|M>. Density matrix elements

The Kossakowski-Lindblad master equation, used to describe quantum stochastic processes and in modeling open quantum systems, is used to derive QSW

Parameter 0 ≤ ω ≤1 is responsible for interpolating between CTRW and  CTQW.

represents the Lindblad operator (sparse M x M matrices) with index x going up to maximum value X.

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).

Quantum stochastic walks

ONLY INCOHERENCE
• A model for QSW with only incoherence considers Lindblad operators involving only the off-diagonal elements of Google matrix,
• X =M(M-1) for only incoherence case with M being the total number of vertices in the Google matrix.
•   by the term "only incoherence", we mean that classical hopping due to the second term  only affects the off-diagonal elements of the Google matrix represents the off-diagonal elements of the Google matrix.

DEPHASING & INCOHERENCE
• A model for QSW with dephasing and incoherence considers Lindblad operators involving all the elements of Google matrix,
• X = M2for only incoherence case with M being the total number of vertices in the Google matrix.
• By the term "dephasing with incoherence", we mean that classical hopping due to the second term  affects all the  elements of the Google matrix.

represents ijth element of the Google matrix.

Solving QSW

Time evolution of the density matrix ρ. The first step is to vectorize the density matrix

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.

For all calculations related to page rank, we use different values for w, depending on which value gives us the shortest convergence time. By convergence time, we mean the time it takes the classical PageRank algorithm to converge to the equilibrium state:     and, by analogy, to the equilibrium state      in quantum PageRank.

Calculation of Degeneracy & CONVERGENCE TIME

CALCULATION OF DEGENERACY

• The PageRank (PR) algorithm (CPR or QPR) computes the ranking of each vertex in a graph and gives the output.
• 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.

CONVERGENCE TIME
• The time it takes the PageRank algorithm to converge to the stationary solution  for CPR and    for QPR is called the convergence time.

• Since at ω = 1, the two QSW schemes reduce to CPR, we consider the convergence time for the QSW scheme of dephasing with incoherence at ω = 1 to be the convergence time of CPR.
• If convergence time for QPR is better than CPR, then we expect  .

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.

SCALE FREE: Vertex degree in SF networks follows the distribution law: P(d) ~ d-h, where 2 < h < 3 .
  Examples: BarabasiAlbert graph and Price Graph distribution.
  BarabasiAlbert graph is generated based on an algorithm to generate random SF networks. World wide web, internet, citation networks, etc., are approximately SF networks. 
  SF networks possess hubs, but clustering is not that high

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.
Here, 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. Also, in order to explain 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

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

<<QSWalk`

Remove["Global`*"]
G=Graph[Range[8],{1\[UndirectedEdge]2,1\[UndirectedEdge]3,1\[UndirectedEdge]4,2\[UndirectedEdge]3,2\[UndirectedEdge]4,3\[UndirectedEdge]4,3\[DirectedEdge]5,5\[DirectedEdge]7,6\[DirectedEdge]5,7\[DirectedEdge]6,7\[DirectedEdge]8,8\[DirectedEdge]2},VertexLabels->"Name"]
SetOptions[MatrixPlot,Mesh->True,MeshStyle->LightGray];MatrixPlot[AdjacencyMatrix[G]]

gamma = 1.;alpha = 1.0;
n = VertexCount[G];
H = GeneratorMatrix[UndirectedGraph[G], gamma];MatrixPlot[H]

list1=LindbladSet[Sqrt[gamma]*GoogleMatrix[G,alpha]];
list2=Table[SparseArray[{{i,i}->Sqrt[Abs[gamma*GoogleMatrix[G,alpha][[i,i]]]]},{n,n}],{i,n}];
LkSetdec=DeleteCases[list1,Alternatives@@list2];
LkSetdephanddec = LindbladSet[Sqrt[gamma] GoogleMatrix[G, alpha]];tf = 400.;
rho0 = SparseArray[{{i_,i_}->1/n},{n,n},0];
tsteplistdec=List[];
tsteplistdephanddec=List[];
omega=0.1;
While[omega≤1.,

QPRdec = QuantumStochasticWalk[H, LkSetdec, omega, rho0, tf] // Diagonal // Chop;
QPRdephanddec = QuantumStochasticWalk[H, LkSetdephanddec, omega, rho0, tf] // Diagonal // Chop;
CPR = PageRankCentrality[UndirectedGraph[G], alpha];
rhodec=rho0//Diagonal//Chop;
normdec[rhodec_]:= Sqrt[Sum[(rhodec[[i]]-QPRdec[[i]])^2,{i,n}]];
normdephanddec[rhodephanddec_]:= Sqrt[Sum[(rhodephanddec[[i]]-QPRdephanddec[[i]])^2,{i,n}]];
tol=10^(-6);
QSWdec=List[];
tstepdec=0;
While[normdec[rhodec]≥tol,rhodec=QuantumStochasticWalk[H, LkSetdec, omega, rho0, tstepdec] // Diagonal // Chop;tstepdec++];
tsteplistdec=Append[tsteplistdec,tstepdec];
rhodephanddec=rho0//Diagonal//Chop;
QSWdephanddec=List[];
tstepdephanddec=0;
While[normdephanddec[rhodephanddec]≥tol,rhodephanddec=QuantumStochasticWalk[H, LkSetdephanddec, omega, rho0, tstepdephanddec] // Diagonal // Chop;tstepdephanddec++];
tsteplistdephanddec=Append[tsteplistdephanddec,tstepdephanddec];omega=omega+0.1];
taudecratio=tsteplistdec/tsteplistdephanddec[[-1]];
taudephanddecratio=tsteplistdephanddec/tsteplistdephanddec[[-1]];
omegaval=Range[0.1,1,0.1];
ListPlot[Transpose@{omegaval,taudecratio},PlotRange->All,Joined->True,
Axes->False,Frame->True ,FrameLabel->{{Style["(Subscript[τ, QPR - OI])/(Subscript[τ, CPR])",Black,16,Bold],None},{Style["ω",Black,16,Bold],None}},LabelStyle->Directive[Black, FontSize->16],FrameTicks->All]
ListPlot[Transpose@{omegaval,taudephanddecratio},PlotRange->All,Joined->True,
Axes->False,Frame->True ,FrameLabel->{{Style["(Subscript[τ, QPR - DI])/(Subscript[τ, CPR])",Black,16,Bold],None},{Style["ω",Black,16,Bold],None}},LabelStyle->Directive[Black, FontSize->16],FrameTicks->All]
Print[tsteplistdec]
Print[tsteplistdephanddec]

Example 2 : Watts Strogatz Graph

Remove["Global`*"]
gamma = 1.;
G = DirectedGraph[RandomGraph[WattsStrogatzGraphDistribution[100,0.2]],"Random"]
alpha = 1.0;
n = VertexCount[G];
H = GeneratorMatrix[UndirectedGraph[G], gamma];
list1=LindbladSet[Sqrt[gamma]*GoogleMatrix[G,alpha]];
list2=Table[SparseArray[{{i,i}->Sqrt[Abs[gamma*GoogleMatrix[G,alpha][[i,i]]]]},{n,n}],{i,n}];
LkSetdec=DeleteCases[list1,Alternatives@@list2];
LkSetdephanddec = LindbladSet[Sqrt[gamma] GoogleMatrix[G, alpha]];tf = 400.;
rho0 = SparseArray[{{i_,i_}->1/n},{n,n},0];
tsteplistdec=List[];
tsteplistdephanddec=List[];
omega=0.1;
While[omega≤1.,
QPRdec = QuantumStochasticWalk[H, LkSetdec, omega, rho0, tf] // Diagonal // Chop;
QPRdephanddec = QuantumStochasticWalk[H, LkSetdephanddec, omega, rho0, tf] // Diagonal // Chop;
CPR = PageRankCentrality[UndirectedGraph[G], alpha];
rhodec=rho0//Diagonal//Chop;
normdec[rhodec_]:= Sqrt[Sum[(rhodec[[i]]-QPRdec[[i]])^2,{i,n}]];
normdephanddec[rhodephanddec_]:= Sqrt[Sum[(rhodephanddec[[i]]-QPRdephanddec[[i]])^2,{i,n}]];
tol=10^(-6);
QSWdec=List[];
tstepdec=0;
While[normdec[rhodec]≥tol,rhodec=QuantumStochasticWalk[H, LkSetdec, omega, rho0, tstepdec] // Diagonal // Chop;tstepdec++];
tsteplistdec=Append[tsteplistdec,tstepdec];
rhodephanddec=rho0//Diagonal//Chop;
QSWdephanddec=List[];
tstepdephanddec=0;
While[normdephanddec[rhodephanddec]≥tol,rhodephanddec=QuantumStochasticWalk[H, LkSetdephanddec, omega, rho0, tstepdephanddec] // Diagonal // Chop;tstepdephanddec++];
tsteplistdephanddec=Append[tsteplistdephanddec,tstepdephanddec];omega=omega+0.1];
taudecratio=tsteplistdec/tsteplistdephanddec[[-1]];
taudephanddecratio=tsteplistdephanddec/tsteplistdephanddec[[-1]];
omegaval=Range[0.1,1,0.1];
ListPlot[Transpose@{omegaval,taudecratio},PlotRange->All,Joined->True,
Axes->False,Frame->True ,FrameLabel->{{Style["(Subscript[τ, QPR - OI])/(Subscript[τ, CPR])",Black,16,Bold],None},{Style["ω",Black,16,Bold],None}},LabelStyle->Directive[Black, FontSize->16],FrameTicks->All]
ListPlot[Transpose@{omegaval,taudephanddecratio},PlotRange->All,Joined->True,
Axes->False,Frame->True ,FrameLabel->{{Style["(Subscript[τ, QPR - DI])/(Subscript[τ, CPR])",Black,16,Bold],None},{Style["ω",Black,16,Bold],None}},LabelStyle->Directive[Black, FontSize->16],FrameTicks->All]
Print[tsteplistdec]
Print[tsteplistdephanddec]

Mathematica code to calculate Quantum page rank

<<QSWalk`

Example 1:  8 vertex graph

Remove["Global`*"]
gamma = 1.;
G=Graph[Range[8],{1\[UndirectedEdge]2,1\[UndirectedEdge]3,1\[UndirectedEdge]4,2\[UndirectedEdge]3,2\[UndirectedEdge]4,3\[UndirectedEdge]4,3\[DirectedEdge]5,5\[DirectedEdge]7,6\[DirectedEdge]5,7\[DirectedEdge]6,7\[DirectedEdge]8,8\[DirectedEdge]2}];
alpha = 1.0;
G1 = Graph[Range[8],{1\[UndirectedEdge]2,1\[UndirectedEdge]3,1\[UndirectedEdge]4,2\[UndirectedEdge]3,2\[UndirectedEdge]4,3\[UndirectedEdge]4,3->5,5->7,6->5,7->6,7->8,8->2},VertexLabels->"Name",VertexSize->Large,DirectedEdges->False]
n = VertexCount[G];
H = GeneratorMatrix[UndirectedGraph[G], gamma];
list1=LindbladSet[Sqrt[gamma]*GoogleMatrix[G,alpha]];
list2=Table[SparseArray[{{i,i}->Sqrt[Abs[gamma*GoogleMatrix[G,alpha][[i,i]]]]},{n,n}],{i,n}];
LkSetdec=DeleteCases[list1,Alternatives@@list2];
LkSetdephanddec = LindbladSet[Sqrt[gamma] GoogleMatrix[G, alpha]];
omega = 0.6; tf = 500.;
rho0 = SparseArray[{{i_,i_}->1/n},{n,n},0];
HighlightCentrality[G_, CPR_]:=HighlightGraph[G,Table[Style[VertexList[G][[i]],ColorData["TemperatureMap"][CPR[[i]]/Max[CPR]]],{i,VertexCount[G]}],VertexSize->Large];
CPR = PageRankCentrality[G, 0.9]
HighlightCentrality[G,CPR]
CPRdeg=CountDistinct[CPR]
CPR1 = PageRankCentrality[G1,alpha]
HighlightCentrality[G1,CPR1]
CPR1deg=CountDistinct[CPR1]
QPRdec = QuantumStochasticWalk[H, LkSetdec, omega, rho0, tf] // Diagonal //Chop
HighlightCentrality[G1,QPRdec]
QPRdecdeg=CountDistinct[QPRdec]
QPRdephanddec = QuantumStochasticWalk[H, LkSetdephanddec, omega, rho0, tf] // Diagonal//Chop 
HighlightCentrality[G1,QPRdephanddec]
QPRdephanddecdeg=CountDistinct[QPRdephanddec]
ListLinePlot[{QPRdec, CPR1}, PlotRange -> Full, PlotMarkers -> Automatic, 
 Axes -> False, Frame -> True, 
 FrameLabel -> {{Style["Page Rank", Bold, Black, 16], 
    None}, {Style["Vertices", Black, Bold, 16], None}}, 
 LabelStyle -> Directive[Black, FontSize -> 16], FrameTicks -> All, 
 PlotLegends -> 
  Placed[LineLegend[{"QPR-OI", "CPR"}, LegendFunction -> Framed], {0.3, 0.3}]]
ListLinePlot[{QPRdephanddec, CPR1}, PlotRange -> Full, PlotMarkers -> Automatic, 
 Axes -> False, Frame -> True, 
 FrameLabel -> {{Style["Page Rank", Bold, Black, 16], 
    None}, {Style["Vertices", Black, Bold, 16], None}}, 
 LabelStyle -> Directive[Black, FontSize -> 16], FrameTicks -> All, 
 PlotLegends -> 
  Placed[LineLegend[{"QPR-DI", "CPR"}, LegendFunction -> Framed], {0.3, 0.3}]]

Example 2: Watts-STROGATZ

gamma = 1.;
G = DirectedGraph[RandomGraph[WattsStrogatzGraphDistribution[100,0.2]],"Random"]
alpha = 1.0;
n = VertexCount[G];
H = GeneratorMatrix[UndirectedGraph[G], gamma];
LkSetdeph=Table[SparseArray[{{i,i}->Sqrt[Abs[gamma*GoogleMatrix[G,alpha][[i,i]]]]},{n,n}],{i,n}];
list1=LindbladSet[Sqrt[gamma] GoogleMatrix[G,alpha]];
list2=Table[SparseArray[{{i,i}->Sqrt[Abs[gamma*GoogleMatrix[G,alpha][[i,i]]]]},{n,n}],{i,n}];
LkSetdec=DeleteCases[list1,Alternatives@@list2];
LkSetdephanddec = LindbladSet[Sqrt[gamma] GoogleMatrix[G, alpha]];
omega = 0.5; tf = 400.;
rho0 = SparseArray[{{i_,i_}->1/n},{n,n},0];

QPRdec = QuantumStochasticWalk[H, LkSetdec, omega, rho0, tf] // Diagonal // Chop;
QPRdephanddec = QuantumStochasticWalk[H, LkSetdephanddec, omega, rho0, tf] // Diagonal // Chop;
CPR = PageRankCentrality[UndirectedGraph[G], alpha];
QPRdecac=SetPrecision[QPRdec,5];
QPRdephanddecac=SetPrecision[QPRdephanddec,5];
CPRac=SetPrecision[CPR,5];
QPRdecdeg=CountDistinct[QPRdecac]
QPRdephanddecdeg=CountDistinct[QPRdephanddecac]
CPRdeg=CountDistinct[CPRac]

ListLinePlot[{QPRdec, CPR}, PlotRange -> Full, PlotMarkers -> Automatic, 
 Axes -> False, Frame -> True, 
 FrameLabel -> {{Style["Page Rank", Bold, Black, 16], 
    None}, {Style["Vertices", Black, Bold, 16], None}}, 
 LabelStyle -> Directive[Black, FontSize -> 16], FrameTicks -> All, 
 PlotLegends -> 
  Placed[LineLegend[{"QPR-OI", "CPR"}, LegendFunction -> Framed], {0.3, 0.3}]]

ListLinePlot[{QPRdephanddec, CPR}, PlotRange -> Full, PlotMarkers -> Automatic, 
 Axes -> False, Frame -> True, 
 FrameLabel -> {{Style["Page Rank", Bold, Black, 16], 
    None}, {Style["Vertices", Black, Bold, 16], None}}, 
 LabelStyle -> Directive[Black, FontSize -> 16], FrameTicks -> All, 
 PlotLegends -> 
  Placed[LineLegend[{"QPR-DI", "CPR"}, LegendFunction -> Framed], {0.3, 0.3}]]