포털의 검색엔진 작동 원리, 구글의 pagerank 알고리즘

네이버나 구글같은 포털에검색을 하면 1초도 안돼서 엄청나게 많은 검색결과가 나온다. 검색 서비스는 어떤 원리로 작동하는것일까?

검색엔진이 정보를 수집하고 저장하는 방법은 물론 각 검색 서비스마다 차이는 있겠지만 작동 방식에는 총 3가지 단계가 있다고 할수있다.

1. 크롤링 - Crawling

2. 인덱싱 - Indexing

3. 랭킹 - Ranking

 

1. 크롤링

네이버의 화면을 보면 배너 메일 카페 블로그 쇼핑 뉴스 증권 날씨 등등 수많은 링크들이 숨어있다. 

화면의 글씨에는 클릭하면 다른 페이지로 넘어가는 링크들이 숨어있는것이다. 

크롤링은 웹 페이지를 그대로 가져와서 거기서 데이터를 추출하여 수집하는 것으로, 크롤링을 수행하면 이 모든 링크들을 다 돌아다니고 페이지 안에 있는 정보를 읽어들이게 된다. 

2. 인덱싱

크롤링으로 수집한 정보를 저장한다.  막 저장하는 건 아니고 알고리즘으로 컨텐츠 종류나 중요한 정보들을 추출하고 분석해 효율적으로 저장한다. 중복되거나 질이 낮은 데이터같이 필요없는 정보는 인덱싱이 되지 않는다. 인덱싱을 통과해야 우리가 검색 결과물로 보게 되는 것이다. 

3. 랭킹 

앞선 두 과정은 검색 전에 미리 검색엔진이 해두는 단계이다. 사용자가 검색한 검색어(쿼리)를 기반으로 인덱싱된 것 중 관련도, 중요도가 높은 것들을 상단에 띄우는 과정을 랭킹이라고 한다. 

 

즉 검색결과는 검색엔진이 크롤링하여 거른 데이터들 중 관련성이 높은 데이터들을 차례로 보는 것이다!

 

 

---

이 검색 알고리즘 중 가장 유명한건 구글의 PageRank 알고리즘입니다.

PageRank는 Google의 검색 알고리즘 중 가장 먼저 사용되었던 알고리즘입니다. PageRank는 webPage의 rank를 매기기 위해, 해당 webpage와 연결되어 있는 다른 webpage들의 개수가 몇 개인지, (ii) 연결된 webpage들은 각각 얼마나 중요한 webpage인지, 두 가지를 고려하게 됩니다. PageRank에 깔려있는 가정은, 더 중요한 webpage 일수록, 다른 중요한 webpage들로부터 link가 걸려있을 가능성이 높다는 것입니다 (https://en.wikipedia.org/wiki/PageRank).

어떤 webpage의 점수는, 해당 webpage를 link 건 다른 webpage들의 중요도의 weighted average로 계산합니다. 다음 예시를 통해서 알아봅시다.

위 그림에선, 4개의 wegbpage가 서로 link를 걸고 있음을 알 수 있습니다 (화살표가 링크를 걸었다는 의미입니다). D의 rank(중요도)는 몇일까요? 위 그림에선, D를 link 건 webpage가 A, C입니다. 따라서 A와 C는 D에게 본인의 rank를 나눠주게 됩니다. 이때 A는 나머지 3개 webpage를 전부 link걸었기 때문에, B,C,D 세 webpage에 1/3씩 본인의 rank를 나눠주게 됩니다. B는 B,C 두 webpage를 link걸었기 때문에, B,C 두 webpage에 1/2씩 본인의 rank를 나눠주게 됩니다.

Page A : B,C,D에게 본인 rank의 1/3씩 나눠주게 됨
Page B : C,D에게 본인 rank의 1/2씩 나눠주게 됨
Page C : Link가 없음
Page D : A,C에게 본인 rank의 1/2씩 나눠주게 됨

 

위 내용을 행렬로 정리하면, 다음과 같이 표현할 수 있습니다.

그럼 최종적으로 A,B,C,D의 rank는 어떻게 계산될까요? 최종 rank는 모든 webpage들의 rank가 변하지 않을 때까지 나눠주는 행위를 반복한 다음, 수렴된 값을 최종 rank로 생각하게 됩니다.

𝑀𝑛𝑥=𝑀𝑛+1𝑥 가 된다면, 더이상 값이 바뀌지 않는다는 의미이고, 그 값이 A,B,C,D 각각의 최종 rank가 됩니다.

그런데 문제점이 있습니다. Webpage C는 다른 webpage로 link를 걸기 때문에, rank를 나눠주지 않고 webpage C의 rank는 소멸되어버리기 때문에, 최종적으로 모든 webpage의 rank가 0으로 되어버리게 됩니다 (위의 예시에서 모든 rank의 합이 1, 0.75, 0.4167, ... 으로 점점 주는 것을 알 수 있습니다).

 

𝑝는 damping factor인데, 둘 간의 가중치를 정하기 위해 우리가 지정하는 hyper-parameter입니다. 결론적으로는, 𝐺는 𝑀과 다르게 𝑥과 non-zero vector로 수렴하게 됩니다. 이를 좀 더 엄밀하게 알고 싶으신 분은, 다음 강의를 참조하시기 바랍니다 (https://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/video-lectures/lecture-24-markov-matrices-fourier-series/.)

Lecture 24: Markov matrices; fourier series | Linear Algebra | Mathematics | MIT OpenCourseWare