PageRank - Revision history

Ranjelin at 08:44, 15 June 2026

2026-06-15T08:44:03Z

←Older revision		Revision as of 08:44, 15 June 2026
Line 138:		Line 138:
	<math>		<math>
	x^\ast - y		x^\ast - y
-	= x^\ast - \alpha P x - (1-\alpha) v	+	\,=\, x^\ast - \alpha P x - (1-\alpha) v
-	= \alpha P x^\ast + (1-\alpha) v - \alpha P x - (1-\alpha) v	+	\,=\, \alpha P x^\ast + (1-\alpha) v - \alpha P x - (1-\alpha) v
-	= \alpha P (x^\ast - x)	+	\,=\, \alpha P (x^\ast - x)
	</math>		</math>
	<br><br>		<br><br>

Ranjelin at 08:41, 15 June 2026

2026-06-15T08:41:57Z

←Older revision		Revision as of 08:41, 15 June 2026
Line 97:		Line 97:
	Consider the matrix equation		Consider the matrix equation
	<br><br>		<br><br>
-	<math>~~\displaystyle~~	+	<math>
	y = \alpha Px + (1-\alpha) v		y = \alpha Px + (1-\alpha) v
	</math>		</math>
Line 115:		Line 115:
	Consequently, we need		Consequently, we need
	<br><br>		<br><br>
-	<math>~~\displaystyle~~	+	<math>
	x = \alpha Px + (1-\alpha) v		x = \alpha Px + (1-\alpha) v
	</math>		</math>
Line 121:		Line 121:
	This is really the linear system:		This is really the linear system:
	<br><br>		<br><br>
-	<math>~~\displaystyle~~	+	<math>
	(I - \alpha P) x = (1-\alpha) v		(I - \alpha P) x = (1-\alpha) v
	</math>		</math>
Line 136:		Line 136:
	Then		Then
	<br><br>		<br><br>
-	<math>~~\displaystyle~~	+	<math>
	x^\ast - y		x^\ast - y
	= x^\ast - \alpha P x - (1-\alpha) v		= x^\ast - \alpha P x - (1-\alpha) v
Line 145:		Line 145:
	Now, if we take the 1-norm of both sides of this equation:		Now, if we take the 1-norm of both sides of this equation:
	<br><br>		<br><br>
-	<math>~~\displaystyle~~	+	<math>
	\|\|x^\ast - y \|\|_1		\|\|x^\ast - y \|\|_1
	=\,\alpha \|\| P(x^\ast - x) \|\|_1		=\,\alpha \|\| P(x^\ast - x) \|\|_1

Ranjelin at 08:28, 15 June 2026

2026-06-15T08:28:38Z

←Older revision		Revision as of 08:28, 15 June 2026
Line 147:		Line 147:
	<math>\displaystyle		<math>\displaystyle
	\|\|x^\ast - y \|\|_1		\|\|x^\ast - y \|\|_1
-	= \alpha \|\| P(x^\ast - x) \|\|_1	+	=\,\alpha \|\| P(x^\ast - x) \|\|_1
-	\le \alpha \|\| P \|\|_1 \|\|(x^\ast - x) \|\|_1	+	\le\,\alpha \|\| P \|\|_1 \|\|(x^\ast - x) \|\|_1
-	\le \alpha \|\|(x^\ast - x) \|\|_1	+	\le\,\alpha \|\|(x^\ast - x) \|\|_1
	</math>		</math>
	<br><br>		<br><br>

Ranjelin at 08:25, 15 June 2026

2026-06-15T08:25:25Z

Ranjelin at 08:20, 15 June 2026

2026-06-15T08:20:29Z

Ranjelin at 07:59, 15 June 2026

2026-06-15T07:59:02Z

←Older revision		Revision as of 07:59, 15 June 2026
Line 82:		Line 82:

	Let <math>P</math> be a matrix where the <math>i,j</math>th entry is the probability of		Let <math>P</math> be a matrix where the <math>i,j</math>th entry is the probability of
-	moving from page <math>j</math> to page <math>i</math>. (We now need to assume	+	moving from page <math>j</math> to page <math>i</math>.
-	that page indices <math>i</math> run from 1 to the number of pages	+	(We now need to assume that page indices <math>i</math> run from 1 to the number of pages on the web, <math>n</math>.)
-	on the web, <math>n</math>.) Formally,	+	Formally,
	<br><br>		<br><br>
	<math>		<math>
-	P_{~~i,j~~}	+	P_{ij}
	= \left\{\begin{array}{lr}		= \left\{\begin{array}{lr}
	\frac{1}{d_j}\;, & \;{\rm page }i\;{\rm links to page }j\\		\frac{1}{d_j}\;, & \;{\rm page }i\;{\rm links to page }j\\
Line 96:		Line 96:
	<br><br>		<br><br>
	Consider the matrix equation		Consider the matrix equation
-	<br>	+	<br><br>
	<math>\displaystyle		<math>\displaystyle
-	y = \alpha Px + (1-\alpha) v.	+	y = \alpha Px + (1-\alpha) v
	</math>		</math>
-	<br>	+	<br><br>
	The <math>i</math>th row of this equation is precisely the update		The <math>i</math>th row of this equation is precisely the update
	for PageRank we described above. In this case, repeatedly applying		for PageRank we described above. In this case, repeatedly applying
Line 107:		Line 107:
	# Compute <math>y = \alpha Px + (1-\alpha) v</math>.		# Compute <math>y = \alpha Px + (1-\alpha) v</math>.
	# Set <math>x</math> to the probabilities computed in <math>y</math>,		# Set <math>x</math> to the probabilities computed in <math>y</math>,
-	i.e. just copy everything in <math>y</math> to <math>x</math>)	+	(i.e, just copy everything in <math>y</math> to <math>x</math>).
	# Go back to 2 and repeat.		# Go back to 2 and repeat.

	All we have left to do is show that this iteration converges.		All we have left to do is show that this iteration converges.
	If the above algorithm converges, then the probabilities in		If the above algorithm converges, then the probabilities in
-	<math>x</math> and <math>y</math> will be the same. Consequently, we need	+	<math>x</math> and <math>y</math> will be the same.
-	<br>	+	Consequently, we need
		+	<br><br>
	<math>\displaystyle		<math>\displaystyle
-	x = \alpha Px + (1-\alpha) v.	+	x = \alpha Px + (1-\alpha) v
	</math>		</math>
-	<br>	+	<br><br>
	This is really the linear system:		This is really the linear system:
-	<br>	+	<br><br>
	<math>\displaystyle		<math>\displaystyle
-	(I - \alpha P) x = (1-\alpha) v.	+	(I - \alpha P) x = (1-\alpha) v
	</math>		</math>
-	<br>	+	<br><br>
	Before we can address convergence, we need to establish		Before we can address convergence, we need to establish
	whether <math>x</math> is unique.		whether <math>x</math> is unique.
	Every column of the matrix <math>P</math> has entries that sum to 1		Every column of the matrix <math>P</math> has entries that sum to 1
	or 0. Assuming that no page links to itself, then		or 0. Assuming that no page links to itself, then
-	<math>(I - \alpha P)</math> is diagonally dominant when <math>\alpha < 1</math>,	+	<math>(I - \alpha P)</math> is diagonally dominant when <math>\alpha < 1</math>.
-	~~and~~ thus, <math>x</math> is unique.	+	And thus, <math>x</math> is unique.
	Does the iteration find a unique <math>x</math>? Yes.		Does the iteration find a unique <math>x</math>? Yes.
	Let <math>x^\ast</math> be the solution and let <math>x</math>		Let <math>x^\ast</math> be the solution and let <math>x</math>
-	and <math>y</math> be adjacency iterations. Then	+	and <math>y</math> be adjacency iterations.
-	<br>	+	Then
		+	<br><br>
	<math>\displaystyle		<math>\displaystyle
	x^\ast - y		x^\ast - y
	= x^\ast - \alpha P x - (1-\alpha) v		= x^\ast - \alpha P x - (1-\alpha) v
	= \alpha P x^\ast + (1-\alpha) v - \alpha P x - (1-\alpha) v		= \alpha P x^\ast + (1-\alpha) v - \alpha P x - (1-\alpha) v
-	= \alpha P (x^\ast - x).	+	= \alpha P (x^\ast - x)
	</math>		</math>
-	<br>	+	<br><br>
	Now, if we take the 1-norm of both sides of this equation:		Now, if we take the 1-norm of both sides of this equation:
-	<br>	+	<br><br>
	<math>\displaystyle		<math>\displaystyle
	\|\|x^\ast - y \|\|_1		\|\|x^\ast - y \|\|_1
	= \alpha \|\| P(x^\ast - x) \|\|_1		= \alpha \|\| P(x^\ast - x) \|\|_1
	\le \alpha \|\| P \|\|_1 \|\|(x^\ast - x) \|\|_1		\le \alpha \|\| P \|\|_1 \|\|(x^\ast - x) \|\|_1
-	\le \alpha \|\|(x^\ast - x) \|\|_1.	+	\le \alpha \|\|(x^\ast - x) \|\|_1
	</math>		</math>
-	<br>	+	<br><br>
-	Thus, we reduce the norm to the exact solution by a factor	+	Thus, we reduce the norm to the exact solution by a factor of <math>\alpha</math> at each iteration.
-	of <math>\alpha</math> at each iteration. This means the iteration	+	This means the iteration converges.
-	converges.	+

	[[User:Dgleich\|Dgleich]] 07:10, 10 August 2010 (PDT)		[[User:Dgleich\|Dgleich]] 07:10, 10 August 2010 (PDT)

Ranjelin at 07:43, 15 June 2026

2026-06-15T07:43:23Z

←Older revision		Revision as of 07:43, 15 June 2026
Line 83:		Line 83:
	Let <math>P</math> be a matrix where the <math>i,j</math>th entry is the probability of		Let <math>P</math> be a matrix where the <math>i,j</math>th entry is the probability of
	moving from page <math>j</math> to page <math>i</math>. (We now need to assume		moving from page <math>j</math> to page <math>i</math>. (We now need to assume
-	that ~~the~~ page indices <math>i</math> run from 1 to the number of pages	+	that page indices <math>i</math> run from 1 to the number of pages
	on the web, <math>n</math>.) Formally,		on the web, <math>n</math>.) Formally,
-	<br>	+	<br><br>
-	<math>~~\displaystyle~~	+	<math>
	P_{i,j}		P_{i,j}
-	= \begin{~~cases~~}	+	= \left\{\begin{array}{lr}
-	\frac{1}{d_j} & {\~~text~~{ if page } i \~~text~~{ links to page } j} \\	+	\frac{1}{d_j}\;, & \;{\rm page }i\;{\rm links to page }j\\
-	0 & {\~~text~~ otherwise. } \\	+	0\;, & {\rm otherwise}\\
-	\end{~~cases~~}	+	\end{array}
		+	\right.
	</math>		</math>
-	<br>	+	<br><br>
	Consider the matrix equation		Consider the matrix equation
	<br>		<br>

Ranjelin at 03:23, 14 June 2026

2026-06-14T03:23:18Z

←Older revision		Revision as of 03:23, 14 June 2026
Line 56:		Line 56:
	<math>		<math>
	y_i = \sum_{\begin{array}{c}{\rm page }j\\		y_i = \sum_{\begin{array}{c}{\rm page }j\\
-	{\rm linking to }i\end{array}}\alpha x_j/d_j + (1-\alpha)v_i	+	{\rm linking to }i\end{array}}\alpha x_j/d_j+_{}(1-\alpha)v_i
	</math>		</math>
	<br><br>		<br><br>

Ranjelin at 03:22, 14 June 2026

2026-06-14T03:22:06Z

←Older revision		Revision as of 03:22, 14 June 2026
Line 53:		Line 53:
	Then the probability of finding the surfer at node <math>i</math> after one		Then the probability of finding the surfer at node <math>i</math> after one
	step of surfing is		step of surfing is
-	<br>	+	<br><br>
-	<math>~~\displaystyle~~	+	<math>
-	y_i = \sum_{{\~~text~~ page } j\,\,{\~~text~~ linking to } i} \alpha x_j/d_j + (1-\alpha)v_i	+	y_i = \sum_{\begin{array}{c}{\rm page }j\\
		+	{\rm linking to }i\end{array}}\alpha x_j/d_j + (1-\alpha)v_i
	</math>		</math>
-	<br>	+	<br><br>
	In this expression, <math>d_j</math> is the number of links from page <math>j</math>		In this expression, <math>d_j</math> is the number of links from page <math>j</math>
	and <math>v_i</math> is the probability of a random jump to page <math>i</math>.		and <math>v_i</math> is the probability of a random jump to page <math>i</math>.

Ranjelin at 00:00, 7 May 2026

2026-05-07T00:00:21Z

←Older revision		Revision as of 08:25, 15 June 2026
Line 6:		Line 6:
	With this idea, the two key ingredients to PageRank are:		With this idea, the two key ingredients to PageRank are:
	<blockquote>		<blockquote>
-	i) A directed graph abstraction of the web; and <br>	+	(i) A directed graph abstraction of the web; and <br>
-	ii) A random surfer model of user behavior.	+	(ii) A random surfer model of user behavior.
	</blockquote>		</blockquote>

-	Idea i) implies that PageRank views each page on the web as a node	+	Idea (i) implies that PageRank views each page on the web as a node
	in a directed graph. A link on a particular page corresponds to		in a directed graph. A link on a particular page corresponds to
	a directed edge between the nodes. See the illustration below for		a directed edge between the nodes. See the illustration below for
Line 17:		Line 17:
	the web.		the web.

-	Idea ii) is the key insight to PageRank. Recall the fundamental idea:	+	Idea (ii) is the key insight to PageRank. Recall the fundamental idea:
	important pages are those where we expect to find web surfers. PageRank		important pages are those where we expect to find web surfers. PageRank
	proposes the following model for the behavior of web surfers:		proposes the following model for the behavior of web surfers:

←Older revision		Revision as of 08:20, 15 June 2026
Line 21:		Line 21:
	proposes the following model for the behavior of web surfers:		proposes the following model for the behavior of web surfers:
	<blockquote>		<blockquote>
-	a) at a page, a surfer follows a link to another page uniformly at random<br>	+	(a) at a page, a surfer follows a link to another page uniformly at random<br>
	or <br>		or <br>
-	b) at a page, a surfer does something else.	+	(b) at a page, a surfer does something else.
	</blockquote>		</blockquote>
-	Case a) is pretty straightforward. The surfer knows the current	+	Case (a) is pretty straightforward. The surfer knows the current
	page, and merely must make a random choice for an outlink.		page, and merely must make a random choice for an outlink.
-	In case b), we have no information on what the person actually does,	+	In case (b), we have no information on what the person actually does,
	and so we assume they randomly find a new page on the web to begin		and so we assume they randomly find a new page on the web to begin
	surfing again. Because the surfer behaves in a manner uncoupled		surfing again. Because the surfer behaves in a manner uncoupled
	with the connectivity of the web, we call this behavior "jumping" or		with the connectivity of the web, we call this behavior "jumping" or
	"teleporting". Also, variants of PageRank modify the behavior		"teleporting". Also, variants of PageRank modify the behavior
-	in step b) to teleport to a small set of specific nodes on the web.	+	in step (b) to teleport to a small set of specific nodes on the web.
	These are usually topic specific pages, for example only sports		These are usually topic specific pages, for example only sports
	pages for a sports surfer, or personally interesting pages, for example		pages for a sports surfer, or personally interesting pages, for example
	your bookmarks.		your bookmarks.

-	To decide if the surfer follows action a) or b), we toss a weighted coin.	+	To decide if the surfer follows action (a) or (b), we toss a weighted coin.
-	Thus, we assign probability <math>\alpha</math> to action a) and	+	Thus, we assign probability <math>\alpha</math> to action (a) and
-	probability <math>(1-\alpha)</math> to action b).	+	probability <math>(1-\alpha)</math> to action (b).

	At this point, we have a mathematical model for surfer behavior		At this point, we have a mathematical model for surfer behavior

←Older revision		Revision as of 00:00, 7 May 2026
Line 30:		Line 30:
	and so we assume they randomly find a new page on the web to begin		and so we assume they randomly find a new page on the web to begin
	surfing again. Because the surfer behaves in a manner uncoupled		surfing again. Because the surfer behaves in a manner uncoupled
-	with the connectivity of the web, we call this behavior ``jumping'' or	+	with the connectivity of the web, we call this behavior "jumping" or
-	``teleporting''. Also, variants of PageRank modify the behavior	+	"teleporting". Also, variants of PageRank modify the behavior
	in step b) to teleport to a small set of specific nodes on the web.		in step b) to teleport to a small set of specific nodes on the web.
	These are usually topic specific pages, for example only sports		These are usually topic specific pages, for example only sports
Line 46:		Line 46:
	index is a simple label so we can write our equations without always		index is a simple label so we can write our equations without always
	writing out full URLs. To be concrete, instead of writing		writing out full URLs. To be concrete, instead of writing
-	``the probability that the surfer is on slashdot.org'' we assign	+	"the probability that the surfer is on slashdot.org" we assign
	slashdot.org an arbitrary but unique number <math>i</math>, and then we call		slashdot.org an arbitrary but unique number <math>i</math>, and then we call
-	<math>x_i</math> ``the probability that the surfer is on slashdot.org.''	+	<math>x_i</math> "the probability that the surfer is on slashdot.org."
	In general, let <math>x_i</math> be the probability of finding the surfer at page <math>i</math>		In general, let <math>x_i</math> be the probability of finding the surfer at page <math>i</math>
	for each page on the web.		for each page on the web.
Line 55:		Line 55:
	<br>		<br>
	<math>\displaystyle		<math>\displaystyle
-	y_i = \sum_{{\text page } j\,\,{\text linking to } i} \alphax_j/d_j + (1-\alpha)v_i	+	y_i = \sum_{{\text page } j\,\,{\text linking to } i} \alpha x_j/d_j + (1-\alpha)v_i
	</math>		</math>
	<br>		<br>