페이지랭크 알고리즘(PageRank Algorithm)을 사용하여 웹 사이트의 순위 매기기
이 예제에서는 페이지랭크 알고리즘을 사용하여 웹 사이트들의 순위를 매기는 방법을 보여줍니다. 페이지랭크 알고리즘은 원래 검색 엔진 결과의 순위를 매기도록 설계되었지만, 여러 다른 유형의 그래프의 노드에도 광범위하게 적용될 수 있습니다. 페이지랭크 점수는 각 그래프 노드가 다른 노드에 연결되어 있는 방식에 따라 각 그래프 노드의 상대적 중요도를 제공합니다.
이론적으로, 페이지랭크 점수는 각 웹 사이트의 링크를 임의로 클릭하는 누군가가 어떤 특정한 페이지에 도달하게 되는 극한 확률(Limiting Probability)입니다. 따라서 높은 점수를 가진 페이지가 네트워크 내에서 더 많이 연결되어 있고 더 자주 검색될 수 있으며, 임의의 웹 사용자가 이 페이지를 방문할 가능성이 더 높아집니다.
알고리즘 설명
페이지랭크 알고리즘(PageRank Algorithm)의 각 단계에서, 다음 식에 따라 각 페이지의 점수가 업데이트됩니다.
r = (1-P)/n + P*(A'*(r./d) + s/n);
r
은 페이지랭크 점수로 구성된 벡터입니다.P
는 스칼라 감쇠 인자(대개 0.85)로, 임의의 웹 사용자가 다른 임의의 페이지를 계속 방문하는 대신 현재 페이지에서 링크를 클릭할 확률입니다.A'
는 그래프의 인접 행렬의 전치입니다.d
는 그래프에 있는 각 노드의 진출차수가 포함된 벡터입니다. 진출 간선이 없는 노드에 대해d
는1
로 설정됩니다.n
은 그래프에 있는 노드의 스칼라 개수입니다.s
는 링크가 없는 페이지에 대한 페이지랭크 점수의 스칼라 합입니다.
다시 말해서, 각 페이지의 순위는 해당 페이지에 연결되는 페이지들의 순위에 따라 크게 달라집니다. 항 A'*(r./d)
는 그래프의 각 노드로 연결되는 소스 노드의 점수를 뽑아내며, 이 점수는 소스 노드의 아웃바운드 링크의 총 개수를 기준으로 정규화됩니다. 이렇게 하면 페이지랭크 점수의 합이 항상 1
이 됩니다. 예를 들어, 노드 2가 노드 1, 3, 4로 연결되는 경우 노드 2는 알고리즘이 반복될 때마다 노드 1, 3, 4에 각각 자신의 페이지랭크 점수의 1/3
을 넘겨줍니다.
각 노드가 자신의 페이지랭크 점수를 그래프의 다른 노드에 넘겨주는 방식을 보여주는 그래프를 만들어 보겠습니다.
s = {'a' 'a' 'a' 'b' 'b' 'c' 'd' 'd' 'd'}; t = {'b' 'c' 'd' 'd' 'a' 'b' 'c' 'a' 'b'}; G = digraph(s,t); labels = {'a/3' 'a/3' 'a/3' 'b/2' 'b/2' 'c' 'd/3' 'd/3' 'd/3'}; p = plot(G,'Layout','layered','EdgeLabel',labels); highlight(p,[1 1 1],[2 3 4],'EdgeColor','g') highlight(p,[2 2],[1 4],'EdgeColor','r') highlight(p,3,2,'EdgeColor','m') title('PageRank Score Transfer Between Nodes')
centrality
함수에는 페이지랭크 점수를 계산할 수 있는 옵션이 포함되어 있습니다.
6개 노드에 대한 페이지랭크(PageRank)
허구의 웹 사이트를 나타내는 6개의 노드가 포함된 유방향 그래프를 만들고 플로팅해 보겠습니다.
s = [1 1 2 2 3 3 3 4 5]; t = [2 5 3 4 4 5 6 1 1]; names = {'http://www.example.com/alpha', 'http://www.example.com/beta', ... 'http://www.example.com/gamma', 'http://www.example.com/delta', ... 'http://www.example.com/epsilon', 'http://www.example.com/zeta'}; G = digraph(s,t,[],names)
G = digraph with properties: Edges: [9x1 table] Nodes: [6x1 table]
plot(G,'Layout','layered', ... 'NodeLabel',{'alpha','beta','gamma','delta','epsilon','zeta'})
이 그래프의 페이지랭크 중심성(Centrality) 점수를 계산해 보겠습니다. 팔로우 확률(감쇠 인자라고도 함) 0.85
를 사용합니다.
pr = centrality(G,'pagerank','FollowProbability',0.85)
pr = 6×1
0.3210
0.1706
0.1066
0.1368
0.2008
0.0643
각 페이지의 페이지랭크 점수와 차수 정보를 확인해 보겠습니다.
G.Nodes.PageRank = pr; G.Nodes.InDegree = indegree(G); G.Nodes.OutDegree = outdegree(G); G.Nodes
ans=6×4 table
Name PageRank InDegree OutDegree
__________________________________ ________ ________ _________
{'http://www.example.com/alpha' } 0.32098 2 2
{'http://www.example.com/beta' } 0.17057 1 2
{'http://www.example.com/gamma' } 0.10657 1 3
{'http://www.example.com/delta' } 0.13678 2 1
{'http://www.example.com/epsilon'} 0.20078 2 1
{'http://www.example.com/zeta' } 0.06432 1 0
이 결과는 페이지 링크의 개수뿐만 아니라 품질도 점수에 영향을 미친다는 것을 보여줍니다. alpha
웹 사이트와 gamma
웹 사이트는 모두 총 차수가 4이지만, alpha
는 역시 순위가 높은 epsilon
과 beta
로 모두 연결됩니다. 반면, gamma
는 순위가 중간 정도인 한 페이지 beta
에 의해서만 연결됩니다. 따라서, 알고리즘은 gamma
보다 alpha
에 더 높은 점수를 매깁니다.
MathWorks.com에 있는 웹 사이트의 페이지랭크(PageRank)
mathworks100.mat
의 데이터를 불러오고 인접 행렬 A
를 확인해 보겠습니다. 이 데이터는 2015년에 자동 페이지 크롤러를 사용하여 생성되었습니다. 페이지 크롤러는 https://www.mathworks.com
에서 시작하여, 인접 행렬이 100개의 고유한 웹 페이지의 연결에 대한 정보를 포함할 때까지 링크를 따라 그다음 웹 페이지로 이동했습니다.
load mathworks100.mat
spy(A)
희소 인접 행렬 A
와, U
에 포함된 URL을 노드 이름으로 사용하여 유방향 그래프를 만들어 보겠습니다.
G = digraph(A,U)
G = digraph with properties: Edges: [632x1 table] Nodes: [100x1 table]
역학(force) 레이아웃을 사용하여 그래프를 플로팅해 보겠습니다.
plot(G,'NodeLabel',{},'NodeColor',[0.93 0.78 0],'Layout','force'); title('Websites linked to https://www.mathworks.com')
200번의 반복 횟수와 감쇠 인자 0.85
를 사용하여 그래프 G
의 페이지랭크 점수를 계산해 보겠습니다. 점수와 차수 정보를 그래프의 노드 테이블에 추가합니다.
pr = centrality(G,'pagerank','MaxIterations',200,'FollowProbability',0.85); G.Nodes.PageRank = pr; G.Nodes.InDegree = indegree(G); G.Nodes.OutDegree = outdegree(G);
상위 25개 결과 점수를 확인합니다.
G.Nodes(1:25,:)
ans=25×4 table
Name PageRank InDegree OutDegree
______________________________________________________________________________ ________ ________ _________
{'https://www.mathworks.com' } 0.044342 20 14
{'https://ch.mathworks.com' } 0.043085 20 14
{'https://cn.mathworks.com' } 0.043085 20 14
{'https://jp.mathworks.com' } 0.043085 20 14
{'https://kr.mathworks.com' } 0.043085 20 14
{'https://uk.mathworks.com' } 0.043085 20 14
{'https://au.mathworks.com' } 0.043085 20 14
{'https://de.mathworks.com' } 0.043085 20 14
{'https://es.mathworks.com' } 0.043085 20 14
{'https://fr.mathworks.com' } 0.043085 20 14
{'https://in.mathworks.com' } 0.043085 20 14
{'https://it.mathworks.com' } 0.043085 20 14
{'https://nl.mathworks.com' } 0.043085 20 14
{'https://se.mathworks.com' } 0.043085 20 14
{'https://www.mathworks.com/index.html%3Fnocookie%3Dtrue' } 0.0015 0 1
{'https://www.mathworks.com/company/aboutus/policies_statements/patents.html'} 0.007714 6 6
⋮
점수가 0.005
보다 큰 모든 노드를 포함하는 부분 그래프를 추출하고 플로팅해 보겠습니다. 페이지랭크 점수에 따라 그래프 노드에 색을 칠합니다.
H = subgraph(G,find(G.Nodes.PageRank > 0.005)); plot(H,'NodeLabel',{},'NodeCData',H.Nodes.PageRank,'Layout','force'); title('Websites linked to https://www.mathworks.com') colorbar
상위 웹 사이트의 페이지랭크 점수는 임의의 웹 사용자가 각 페이지에 도달할 가능성이 약 4.5%로서 다들 거의 비슷합니다. 밀접하게 연결된 페이지의 이 작은 그룹은 플롯의 가운데에 클릭(Clique)을 형성합니다. 이 중앙의 클릭에는 여러 개의 더 작은 클릭이 연결되어 있으며, 이러한 작은 클릭도 자체적으로 밀접하게 연결되어 있습니다.
참고 문헌
Moler, C. Experiments with MATLAB. Chapter 7: Google PageRank. MathWorks, Inc., 2011.
참고 항목
digraph
| graph
| centrality