PageRank 대 SVD

Question

Pagerank은 일련의 페이지와 각각의 내부 및 외부 링크로 형성된 지향 에지의 노드 그래프에서 작동합니다. 따라서 특정 페이지의 순위는 광범위하게 노드 그래프에서 국지적으로 유발 된 효과입니다.

SVD은 값의 전체 매트릭스에서 작동하며 방향성이 없습니다. 사이트 A와 사이트 B 사이의 링크는 올바른 행렬 요소에 1로만 등록됩니다. 그것은 글로벌 시스템이므로 랭킹은 글로벌 효과입니다.

웹에서 파생 된 행렬의 극단적 인 희소성을 감안할 때 완전한 데이터 집합이 필요하고 중요한 메모리 요구 사항이 있으므로 SVD가 여기서는 성능이 좋지 않을 것으로 예상됩니다.

사실입니까? Pagerank는 노드 그래프 기반 알고리즘이기 때문에 SVD를 능가합니까? PageRank는 단어가 언급 된 횟수를 초과하여 페이지와의 의미 관련성을 어떻게 추론 할 수 있습니까? 또는 페이지 랭크 (PageRank)가 페이지 순위를 매긴 후에 수행되는 두 번째 단계일까요?

Answer 1

여기에는 두 가지 문제가 있습니다. 어느 측정 값이 계산하기 쉽고 찾고있는 정보가 있습니까? 어느 쪽의 질문에 대한 답을 모르지만 부분적인 답을 줄 수는 있습니다.

첫째, 관련성. 두 양은 네트워크 이론에서 용어를 사용하기 위해 centrality 대책입니다. PageRank는 eigenvector 중심성의 변종을 계산하는 반면, SVD는 분명히 HITS (Hyperlink-Induced Topics Search) 알고리즘을 유도합니다. 나는 이것을 Peter Dodds (University of Vermont)의 this handout에서 얻었다. 그들은 여러 가지를 측정하지만, 웹 페이지의 중요성을 측정하는 데 가장 적합한 것이 어느 것인지 명확하지 않습니다.

둘째로, 계산 비용. 수학적으로 말하면 페이지 랭크 (PageRank)는 위키 백과 페이지에서 설명 된 바와 같이 (수정 된) 인접 매트릭스의 지배적 인 고유 벡터입니다. 반면 HITS는 인접 매트릭스의 지배적 인 단일 벡터를 제공합니다. 둘 다 웹 페이지의 글로벌 네트워크와 웹 페이지 간의 링크로 정의되며 둘 다 노드 그래프 만 로컬로 고려하여 계산할 수 있습니다. 그래서 처음에는 계산 비용이 대략 같다고 생각합니다.

결론적으로 왜 PageRank가 SVD보다 나은지 나는 알지 못합니다. 그것이 SVD보다 낫다는 것이 나에게 분명하지 않다.

Answer 2

PageRank는 순간 이동 무작위 도보 행렬을 사용합니다. 순간 이동은 무작위 걸음 수 행렬의 (저차) 국부적 인 고유 벡터를 피하기 위해 중요합니다. 나는 degree-normalized adjacency matrix 인 랜덤 walk 행렬이 큰 degree 노드가 localized vector를 만들 수있는 HITS와는 대조적으로 큰 degree 노드와 루프의 효과를 저지하기 때문에 PageRank가 HITS보다 낫다고 생각한다.