Back to : advanced-algorithms
Contents

๊ทธ๋ž˜ํ”„ ๋ฐ์ดํ„ฐ $G = (V, E)$ ๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์šฐ๋ฆฌ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋‘ ์งˆ๋ฌธ์— ๋‹ตํ•˜๊ณ  ์‹ถ์Šต๋‹ˆ๋‹ค.

  1. ๊ทธ๋ž˜ํ”„์—์„œ ์ค‘์š”ํ•œ ๋…ธ๋“œ๊ฐ€ ์–ด๋””์ธ๊ฐ€?
  2. ๊ทธ๋ž˜ํ”„์˜ ํŠน์ •ํ•œ ์ •์  $u$ ์˜ ์ž…์žฅ์—์„œ ๋ณผ ๋•Œ, ๊ฐ€์žฅ ์—ฐ๊ด€์ด ๊นŠ์€ ๋…ธ๋“œ๋Š” ์–ด๋””์ธ๊ฐ€?

์ „์ž์˜ ์งˆ๋ฌธ์— ๋‹ตํ•˜๋Š” ๊ฐ€์žฅ ๋ณดํŽธ์ ์ธ ๋ฐฉ๋ฒ•์ด Pagerank, ํ›„์ž์˜ ์งˆ๋ฌธ์— ๋‹ตํ•˜๋Š” ๋ณดํŽธ์ ์ธ ๋ฐฉ๋ฒ•์ด RWR์ž…๋‹ˆ๋‹ค. ์ด๋ฒˆ ํฌ์ŠคํŒ…์—์„œ๋Š” ์ด ๋‘๊ฐœ๋ฅผ ๊ฐ™์ด ๊ฐ„๋‹จํ•˜๊ฒŒ ์•Œ์•„๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.
์šฐ๋ฆฌ๋Š” Directed graph๋ฅผ ๊ธฐ๋ณธ ๋ชจ๋ธ๋กœ ์ƒ๊ฐํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.

PageRank

Pagerank๋Š” Google์ด ๊ฒ€์ƒ‰ ๊ฒฐ๊ณผ๋ฅผ ์ •๋ฆฌํ•˜๊ธฐ ์œ„ํ•ด ๊ฐœ๋ฐœํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ, ์›นํŽ˜์ด์ง€์˜ ์ˆœ์œ„ (rank) ๋ฅผ ์ •ํ•˜๊ธฐ ์œ„ํ•ด ๊ณ ์•ˆ๋˜์—ˆ์Šต๋‹ˆ๋‹ค.

Motivation

๋Œ€๋žต์ ์ธ motivation์€ ์•„๋ž˜ ๋‘ ๊ฐ€์ง€์ž…๋‹ˆ๋‹ค.

  • ๋งŽ์€ ํŽ˜์ด์ง€๋กœ๋ถ€ํ„ฐ ์ธ์šฉ๋œ (๋งํฌ๊ฐ€ ๊ฑธ๋ฆฐ) ํŽ˜์ด์ง€๋Š” ์ค‘์š”ํ•˜๋‹ค
  • ์ค‘์š”ํ•œ ํŽ˜์ด์ง€๋กœ๋ถ€ํ„ฐ ๋งํฌ๊ฐ€ ๊ฑธ๋ฆฐ ํŽ˜์ด์ง€๋Š” ์ค‘์š”ํ•˜๋‹ค

๊ต‰์žฅํžˆ ์ง๊ด€์ ์œผ๋กœ ๋ง์ด ๋˜๋Š” ์›์น™์ž…๋‹ˆ๋‹ค.

Algorithm

๊ธฐ๋ณธ์ ์œผ๋กœ Pagerank๋Š” stochasticํ•˜๊ฒŒ ๋งค๊ฒจ์ง‘๋‹ˆ๋‹ค. ์ฆ‰, ์–ด๋–ค ๋…ธ๋“œ $i$์˜ pagerank๊ฐ’ $r_i$๋Š” $i$๋ฟ ์•„๋‹ˆ๋ผ ์Šคํ…์ˆ˜ $j$ (์‹œ๊ฐ„์ด๋ผ๊ณ  ๋ฐ›์•„๋“ค์ด๋ฉด ๋ฉ๋‹ˆ๋‹ค) ์˜ ์˜ํ–ฅ์„ ๋ฐ›์œผ๋ฉฐ, $r_{i, j}$ ๋Š” $r_{-, j-1}$ ๋“ค์— ์˜ํ•ด ๊ณ„์‚ฐ๋œ๋‹ค๋Š” ๋œป์ž…๋‹ˆ๋‹ค.

  • ๊ฐ ๋…ธ๋“œ์˜ ์ตœ์ดˆ ์ค‘์š”๋„ $r_{i, 0}$ ์€ ํŽธ์˜์ƒ $1/N$ ์œผ๋กœ ์ •ํ•ฉ๋‹ˆ๋‹ค. ($N$์€ ๋‹น์—ฐํžˆ ๋…ธ๋“œ ๊ฐœ์ˆ˜)
  • ์ด์ œ, ์—…๋ฐ์ดํŠธ ๊ณผ์ •์€ ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค. $N(i)$ ๋Š” ์›๋ž˜ neighbor๋ฅผ ์˜๋ฏธํ•˜์ง€๋งŒ, ์ž ์‹œ โ€˜incoming neighborsโ€™ ๋งŒ ์ƒ๊ฐํ•˜๊ธฐ๋กœ ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. ์ฆ‰ $N(i)$๋Š” $i$๋กœ ๋“ค์–ด์˜ค๋Š” edge๋ฅผ ๊ฐ–๋Š” ๋…ธ๋“œ์˜ ์ง‘ํ•ฉ์„ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค. ๋Œ€์‹ , ๋ฐ˜๋Œ€๋กœ $i$๊ฐ€ ์ธ์šฉํ•˜๋Š” ๋…ธ๋“œ์˜ ์ง‘ํ•ฉ์„ $L(i)$ ๋ผ๊ณ  ์“ฐ๊ฒ ์Šต๋‹ˆ๋‹ค. \(r_{i, t} = \frac{1-d}{N} + d \sum_{c \in N(i)} \frac{r_{c, t-1}}{\abs{L(c)}}\)
  • ๋‚˜๋จธ์ง€ ๊ฐ’๋“ค์€ ๋Œ€์ถฉ ์ž๋ช…ํ•ฉ๋‹ˆ๋‹ค. $d$๋Š” Damping factor๋ผ ํ•ด์„œ, ์–ผ๋งˆ๋‚˜ ๋น ๋ฅด๊ฒŒ ์ˆ˜๋ ดํ• ์ง€๋ฅผ ์ •ํ•˜๋Š” ์ƒ์ˆ˜๊ฐ’์ž…๋‹ˆ๋‹ค. ํ†ต์ƒ 0.85 ์ •๋„๋ฅผ ์‚ฌ์šฉํ•ฉ๋‹ˆ๋‹ค.
  • ๊ฐ€์žฅ ์ž์—ฐ์Šค๋Ÿฌ์šด ์–ธ์–ด๋กœ ์„ค๋ช…ํ•˜์ž๋ฉด, ์™„์ „ ๋žœ๋คํ•˜๊ฒŒ ํ•˜์ดํผ๋งํฌ๋ฅผ ํด๋ฆญํ•˜๋Š” ๊ฐ€์ƒ์˜ surfer๊ฐ€ ์žˆ์„ ๋•Œ, $t$์‹œ๊ฐ„์ด ์ง€๋‚œ ํ›„ ์ด surfer๊ฐ€ ์–ด๋””์— ์œ„์น˜ํ• ์ง€์˜ ํ™•๋ฅ  ๋ถ„ํฌ๋ฅผ ๊ณ„์‚ฐํ•˜๋Š” ๋ฐฉ์‹์ž…๋‹ˆ๋‹ค. Damping์€ ์—ฌ๊ธฐ์„œ, ํด๋ฆญ์„ ๋ฉˆ์ถ”๊ณ  ํ˜„์žฌ ๋…ธ๋“œ์— ์ •์ฐฉํ•  ํ™•๋ฅ ์„ ์ œ๊ณตํ•ฉ๋‹ˆ๋‹ค.

Linear Algebra PoV

์ง€๊ธˆ๊นŒ์ง€์˜ ๋…ผ์˜๋ฅผ ์„ ํ˜•๋Œ€์ˆ˜ํ•™์˜ ์–ธ์–ด๋กœ ๋‹ค์‹œ ์จ ๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.

  • ๋จผ์ €, ์ธ์ ‘ํ–‰๋ ฌ $A$์— ๋Œ€ํ•ด, $A$๋ฅผ Normalizeํ•ด์„œ ๊ฐ ์—ด์˜ ํ•ฉ์„ 1๋กœ ๊ณ ์ •ํ•ฉ๋‹ˆ๋‹ค. ์ด๋ฅผ Markov matrix๋ผ๊ณ  ๋ถ€๋ฆ…๋‹ˆ๋‹ค.
  • Markov matrix๋Š” ๋งˆ๋ฅด์ฝ”ํ”„ ์ฒด์ธ์„ ๋‚˜ํƒ€๋‚ด๋Š” ํ–‰๋ ฌ์ด๋ผ๋Š” ๋œป์ธ๋ฐ, ์ด๋Ÿฌ๊ธฐ ์œ„ํ•ด์„œ๋Š” Dangling node๊ฐ€ ์žˆ์–ด์„œ๋Š” ์•ˆ ๋ฉ๋‹ˆ๋‹ค. ์œ„ construction์€ ์ด๋ฅผ ๋ณด์žฅํ•˜์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์—, ์ „์ฒด๋ฅผ connected component๋กœ ์ด์–ด์ฃผ๊ธฐ ์œ„ํ•ด \(S = A + \frac{1}{N}\mathbb{1}e^T\) ์ด๋Ÿฐ ํ–‰๋ ฌ์„ ์ƒˆ๋กœ์ด ๊ณ„์‚ฐํ•ฉ๋‹ˆ๋‹ค. ์—ฌ๊ธฐ์„œ $\mathbb{1}$ ์€ ๋ชจ๋“  ํ•ญ์ด 1์ธ ์—ด๋ฒกํ„ฐ์ด๊ณ , $e$๋Š” ์—ด์˜ ๊ฐ’์ด 0์ธ dangling $j$์— ๋Œ€ํ•ด์„œ๋งŒ 1์ธ ๋ฒกํ„ฐ์ž…๋‹ˆ๋‹ค.
  • Damping factor๋ฅผ ๊ณ ๋ คํ•ด์„œ ์ตœ์ข…์ ์ธ Google Matrix (์‹ค์ œ๋กœ ์ด๋Ÿฐ ์ด๋ฆ„์ด ๋ถ™์—ˆ์Šต๋‹ˆ๋‹ค) ๋ฅผ ์•„๋ž˜์™€ ๊ฐ™์ด ๋งŒ๋“ญ๋‹ˆ๋‹ค. \(G = \frac{1-d}{N} \mathbb{11^T} + d S\)
  • ์„ ํ˜•๋Œ€์ˆ˜ํ•™์˜ Perron-Frobenius ์ •๋ฆฌ์— ์˜ํ•˜๋ฉด irreducible markov matrix๋Š” ์‹œ์ž‘์  $x_0$์™€ ์ƒ๊ด€์—†์ด, $x_i = G x_{i-1}$ ์—ฐ์‚ฐ์„ ๋ฐ˜๋ณตํ•˜๋ฉด ์–ด๋”˜๊ฐ€๋กœ ์ˆ˜๋ ดํ•จ์ด ์•Œ๋ ค์ ธ ์žˆ์Šต๋‹ˆ๋‹ค.
  • ์„ ํ˜•๋Œ€์ˆ˜ํ•™์ ์œผ๋กœ, ์ด ํ–‰๋ ฌ์€ $0 < d < 1$ ์— ๋Œ€ํ•ด Unique Maximal Eigenvalue $\lambda = 1$ ์„ ๊ฐ€์ง‘๋‹ˆ๋‹ค. ์ด Eigenvalue์— ๋Œ€์‘ํ•˜๋Š” eigenvector๊ฐ€ ๋ฐ”๋กœ pagerank vector์ž…๋‹ˆ๋‹ค.
  • Iteration $x_{i} = G x_{i-1}$ ์„ ๋น ๋ฅด๊ฒŒ ์ˆ˜๋ ด์‹œํ‚ค๋Š” ๋ฐฉ๋ฒ•์€ numerical linear algebra์˜ ์˜์—ญ์ด๋ฉฐ, $G$ํ–‰๋ ฌ์€ ์ผ๋ฐ˜์ ์œผ๋กœ ์—„์ฒญ๋‚˜๊ฒŒ ํฌ์ง€๋งŒ ๋Œ€์‹  sparseํ•˜๊ธฐ ๋•Œ๋ฌธ์— ๊ทธ๋ƒฅ ๊ทธ๋Œ€๋กœ ๋†“๊ณ  iteration์„ ๋ฐ˜๋ณตํ•ด๋„ ์ƒ๊ฐ๋ณด๋‹ค ๋น ๋ฅด๊ฒŒ ๊ณ„์‚ฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

Random Walk with Restart

Pagerank๊ฐ€ globalํ•œ ๋…ธ๋“œ์˜ ์ค‘์š”๋„๋ฅผ ๊ณ„์‚ฐํ•ด ์ฃผ๋Š”๋ฐ ๋ฐ˜ํ•ด, Random Walk (with Restart) ๋Š” Localํ•œ ๊ด€์ ์—์„œ์˜ ์ค‘์š”๋„๋ฅผ ์ œ๊ณตํ•ฉ๋‹ˆ๋‹ค. ์–ด๋–ค ๋…ธ๋“œ $u$์— ๋Œ€ํ•ด, ๊ฐ ๋…ธ๋“œ $i$ ์˜ ์ค‘์š”๋„ ๋ฒกํ„ฐ $r_i = C_{u, i}$๋ฅผ ๊ณ„์‚ฐํ•œ๋‹ค๊ณ  ์ƒ๊ฐํ•˜๋ฉด ๋˜๊ฒ ์Šต๋‹ˆ๋‹ค. ๊ธฐ๋ณธ์ ์ธ ๊ด€์  (random-surfer) ์ด Pagerank์™€ ๋˜‘๊ฐ™๊ธฐ ๋•Œ๋ฌธ์—, Personalized Pagerank ๋ผ๋Š” ์ด๋ฆ„์œผ๋กœ ๋ถˆ๋ฆฌ๊ธฐ๋„ ํ•ฉ๋‹ˆ๋‹ค. 1

Motivation

๋…ธ๋“œ ๊ฐ„์˜ ์–ด๋–ค ์—ฐ๊ด€์„ฑ์„ ์ฐพ๋Š” ๋ฐฉ๋ฒ•์€ ๋ณดํ†ต ๋‘๊ฐ€์ง€๋ฅผ ์ƒ๊ฐํ•ด ๋ณผ ์ˆ˜ ์žˆ์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค.

  • Path์˜ ๊ธธ์ด ๊ธฐ๋ฐ˜ : Shortest path ๋“ฑ์˜ metric์— ๊ธฐ๋ฐ˜ํ•˜๋Š” ๋ฐฉ๋ฒ•๋“ค
  • Flow ๊ธฐ๋ฐ˜ : Flow network๋ฅผ ๋งŒ๋“ค์–ด์„œ Flow๊ฐ€ ์–ผ๋งˆ๋‚˜ ํ๋ฅผ ์ˆ˜ ์žˆ๋Š”์ง€์— ๊ธฐ๋ฐ˜ํ•˜๋Š” ๋ฐฉ๋ฒ•๋“ค

์ด ๋‘ ๋ฐฉ๋ฒ• ๋ชจ๋‘, ๋ช…ํ™˜ํ•œ ํ•œ๊ณ„๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด SNS ๊ทธ๋ž˜ํ”„์—์„œ ๋‚˜๋ฅผ ๊ธฐ์ค€์œผ๋กœ, A๋ฅผ ํ†ตํ•ด B๋กœ, C๋ฅผ ํ†ตํ•ด D๋กœ ๊ฐˆ ์ˆ˜ ์žˆ๋‹ค๊ณ  ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.
์ด๋•Œ, A๊ฐ€ ์ˆ˜๋งŽ์€ ์‚ฌ๋žŒ์„ ์•Œ๊ณ  ์žˆ๋Š” ์œ ๋ช…์ธ์ด๊ณ , C๊ฐ€ ์ผ๋ฐ˜์ ์ธ ์นœ๊ตฌ๋ผ๋ฉด, ๋‚˜๋Š” B๋ณด๋‹ค๋Š” D์™€ ๋” ๊ฐ€๊นŒ์šด ์‚ฌ์ด๋ผ๊ณ  ํŒ๋‹จํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ๊ทธ๋Ÿฌ๋‚˜ ์œ„ ๋‘ ๋ฐฉ๋ฒ•๋“ค์€ ์ด๋Ÿฌํ•œ ์ฐจ์ด๋ฅผ ์žก์•„๋‚ด์ง€ ๋ชปํ•ฉ๋‹ˆ๋‹ค. ์ด๋Ÿฐ ์ ์—์„œ Random walk๋Š” A์—์„œ ๊ฐˆ์ˆ˜์žˆ๋Š” ๋…ธ๋“œ๊ฐ€ ๋งŽ๋‹ค๋Š” ์ ์„ Penalizeํ•˜๊ธฐ ๋•Œ๋ฌธ์— ๋ณด๋‹ค ์ ์ ˆํ•˜๋‹ค๊ณ  ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

Algorithm

์œ„ Pagerank์™€ ๋˜‘๊ฐ™์ง€๋งŒ, ํ•œ ๋…ธ๋“œ $u$์—์„œ๋งŒ ์‹œ์ž‘ํ•˜๊ธฐ๋กœ ํ•ฉ๋‹ˆ๋‹ค. Notation์˜ ํŽธ์˜๋ฅผ ์œ„ํ•ด Adjacent matrix๋ฅผ $A$๋กœ, ์ด๋ฅผ normalizeํ•ด์„œ ์–ป์€ Weight matrix๋ฅผ $W$ ๋กœ ์“ฐ๊ฒ ์Šต๋‹ˆ๋‹ค.
RWR-vector๋Š” ๋‹ค์Œ ์‹์„ ํ†ตํ•ด ๊ณ„์‚ฐ๋ฉ๋‹ˆ๋‹ค. \(r_{i} = dWr_{i-1} + (1-d) e_u\) ์—ฌ๊ธฐ์„œ $e_u$๋Š” ์‹œ์ž‘๋…ธ๋“œ $u$๋งŒ 1์ธ standard basis vector์ž…๋‹ˆ๋‹ค.
์ด ์‹์ด ๋ฒกํ„ฐ $r$๋กœ ์ˆ˜๋ ดํ•œ๋‹ค๊ณ  ํ•˜๋ฉด, $r = dWr + (1-d) e_u$์ด๋ฏ€๋กœ, ์ด๋ฅผ ์กฐ๊ธˆ ์ •๋ฆฌํ•˜๋ฉด $(I - dW)r = (1-d) e_u$์—์„œ, \(r = (1 - d) (I - dW)^{-1} e_u\) ์ด๋ ‡๊ฒŒ ๊ณ„์‚ฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

Fast Computation

์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์‹ค์ œ๋กœ ์“ฐ๊ธฐ์—๋Š” ์ƒ๋‹นํžˆ ๋Š๋ฆฌ๊ธฐ ๋•Œ๋ฌธ์— (ํ–‰๋ ฌ๊ณฑ์…ˆ ์—ฐ์‚ฐ์ด ๋Š๋ฆฌ๋ฏ€๋กœโ€ฆ) ๋‹ค์–‘ํ•œ ๋ฐฉ๋ฒ•๋“ค์ด ๊ฐœ๋ฐœ๋˜์–ด ์™”์Šต๋‹ˆ๋‹ค. ํŠนํžˆ, Pagerank๋Š” ํ•œ๋ฒˆ ๋Œ๋ฆฌ๋ฉด ๋ชจ๋“  ๋…ธ๋“œ์— ๋Œ€ํ•œ ์ •๋ณด๋ฅผ ์–ป์œผ๋ฏ€๋กœ ๊ทธ cost๊ฐ€ amortize๋˜์ง€๋งŒ, RWR์€ ์ฟผ๋ฆฌ๋…ธ๋“œ๊ฐ€ ๋ฐ”๋€Œ๋ฉด ์ฒ˜์Œ๋ถ€ํ„ฐ ๋‹ค์‹œ ํ•ด์•ผํ•œ๋‹ค๋Š” ์ ์—์„œ, ์ฟผ๋ฆฌ๋‹น ๋ณต์žก๋„๊ฐ€ ๋งค์šฐ ๋†’์Šต๋‹ˆ๋‹ค. ์ด๋ฅผ ๊ฐœ์„ ํ•˜๊ธฐ ์œ„ํ•œ ๋ฐฉ๋ฒ•๋“ค์— ๋Œ€ํ•ด์„œ๋Š” ๋ณ„๋„ ํฌ์ŠคํŒ…์œผ๋กœ ๋‹ค๋ฃฐ ์˜ˆ์ •์ž…๋‹ˆ๋‹ค.


  1. ๊ณต์‹์ ์œผ๋กœ ๋ฐœํ‘œ๋œ ๋…ผ๋ฌธ์—์„œ๋Š” ์•„์ฃผ ์•ฝ๊ฐ„์˜ ์ฐจ์ด๊ฐ€ ์žˆ์œผ๋‚˜, ์‹ ์ •๋ฆฌ์˜ ๋ฌธ์ œ์ด๊ณ  ์‹ค์ œ๋กœ๋Š” identicalํ•ฉ๋‹ˆ๋‹ค.ย โ†ฉ