[펭귄] 페이지랭크 알고리즘에서 1-α가 의사코드에서는 1-S로 대체되는 이유

[mj950425]

🙌 질문자

• 펭귄 @CoodingPenguin

---

❓ 질문 내용

• S와 β를 사용했을 때 비슷하긴 하지만, 값이 조금 다른데 S와 β의 차이와 S를 사용하는 이유

---

📄 참고 자료

• [과제 1] 그래프를 컴퓨터 언어로 표현하기 & 페이지랭크 알고리즘 구현하기 hw1_handout p.3

---

[CoodingPenguin]

부스트캠프의 질문게시판에 비슷한 질문에 답변이 올라와 첨부합니다!

안녕하세요. 교안에서처럼 1−β 를 고정하여 teleport해준다면 막다른 간선(dead end)문제를 해결할 수 없습니다. dead end의 경우 자신이 받은 pagerank value를 다음 iteration 때 나누어 주어야 하지만, 나가는 간선이 없으므로 그 값을 나누어줄 수 없고 pagerank의 총합이 1이 아닌 순간이 존재하게 됩니다. 이러한 문제를 해결하기 위해서, teleport 하지않은 나머지 value를 모두 나누어 준 후 남은 값을 모아서 모든 vertex에 나누어주는 것입니다. 강의에서 설명해주신 내용보다 한 단계 더 advanced된 내용이라고 생각하시면 될 것 같습니다.

여기서 하나 알게 된 사실이 페이지랭크의 총합이 1이라는 사실인데 답변을 보면 β를 쓰면 총합이 1이 안되고 S를 쓰면 총합이 1이 된다는 말인데 이게 어떻게 보장되는지가 잘 감이 오질 않네요..

[bsm8734]

링크 - 그래프 PageRank 수도코드와 해석
여기에 설명하기에는 글이 좀 길어질 것 같아, 블로그에 따로 정리하여두었습니다! 😀