페이지랭크 알고리즘(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')

Figure contains an axes object. The axes object with title PageRank Score Transfer Between Nodes contains an object of type graphplot.

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'})

Figure contains an axes object. The axes object contains an object of type graphplot.

이 그래프의 페이지랭크 중심성(Centrality) 점수를 계산해 보겠습니다. 팔로우 확률(감쇠 인자라고도 함) 0.85를 사용합니다.

pr = centrality(G,'pagerank','FollowProbability',0.85)

각 페이지의 페이지랭크 점수와 차수 정보를 확인해 보겠습니다.

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)

Figure contains an axes object. The axes object with xlabel nz = 632 contains a line object which displays its values using only markers.

희소 인접 행렬 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')

Figure contains an axes object. The axes object with title Websites linked to https://www.mathworks.com contains an object of type graphplot.

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

Figure contains an axes object. The axes object with title Websites linked to https://www.mathworks.com contains an object of type graphplot.

상위 웹 사이트의 페이지랭크 점수는 임의의 웹 사용자가 각 페이지에 도달할 가능성이 약 4.5%로서 다들 거의 비슷합니다. 밀접하게 연결된 페이지의 이 작은 그룹은 플롯의 가운데에 클릭(Clique)을 형성합니다. 이 중앙의 클릭에는 여러 개의 더 작은 클릭이 연결되어 있으며, 이러한 작은 클릭도 자체적으로 밀접하게 연결되어 있습니다.

참고 문헌

Moler, C. Experiments with MATLAB. Chapter 7: Google PageRank. MathWorks, Inc., 2011.

참고 항목

digraph | graph | centrality