디시인사이드 갤러리

갤러리 이슈박스, 최근방문 갤러리

갤러리 본문 영역

구글 검색 알고리즘의 원리 끗

...(141.223) 2007.04.24 15:08:40
조회 560 추천 0 댓글 8


예를 들어 4개의 웹 페이지 A, B, C, D가 있고, 그 중에 B와 D가 A를 link하고 있을 때
A의 page rank는
Q(A) = Q(B)/N(B) + Q(D)/N(D)
이렇게 구해. 이때 N은 해당 페이지가 걸고 있는 link의 개수를 의미하고,
이 계산을 Q(A), Q(B), Q(C), Q(D)가 모두 수렴할 때까지 계속 반복해주면 돼.

이제 이게 앞의 알고리즘과 어떻게 연결되는지 보자.

우선, PageRank 알고리즘에서 웹페이지는 따로 벡터화를 하지 않아.
그렇다면 P(A->B) 같은, random walk을 위한 확률은 대체 어떻게 구하는가?

구글은 random walk 대신 random click 이라는 아이디어를 적용했어.
예를 들어, 현재 웹페이지가 하나 떠 있는데, 여기에 link가 N개 있다고 하자.
random click이란, 그 중에 하나를 무작위로 click한다는 거야.
따라서 다음 턴에 각각의 link된 사이트들로 이동할 확률은, 1/N이 되겠지.

즉, P(A->B)는, A에서 B로 가는 link가 있는 경우 1/N이고, link가 없는 경우 0이 되는 거지.
(즉, 위의 예에서 Q(A)의 실제 식은 Q(B)*(1/N(B)) + Q(C)*0 + Q(D)*(1/N(D)) 가 돼)
벡터화니 직선거리 계산이니 하는 복잡한 과정 없이 굉장히 간단하지.
웹이 가지는 특성을 정말 잘 이용한 것 같아.

그외에 나머지는 이전 글에서 설명한 알고리즘과 똑같아. 웹에 적용함으로써 달라진 건 저것 뿐이지...
계산 식이 이전 글의 알고리즘이랑 다르긴 한데, 결국 나오는 값은 똑같고 방법만 다른 거야.
(간단한 계산을 수렴할 때까지 반복하느냐, 아니면 역행렬을 구하는 다소 복잡한 계산이지만
 한 방에 결과가 나오는 방법이냐 하는... 그런데 역행렬 계산은 complexity가 O(n^3)이라;;;;
 규모가 큰 데이터에 대해서는 간단한 계산을 적당한 수준까지 반복하는 방법을 쓰지...)

그런데, PageRank 알고리즘에 대한 잘 알려진 직관적인 설명들이 있잖아.
정말 실제 알고리즘과 직관적인 설명이 잘 대응이 될까 생각해 보자.

우선,
악의적으로 링크를 많이 걸어놓은 사이트들로 인해 검색 엔진의 성능이 떨어지는 것을 막기 위해
링크를 많이 걸은 사이트의 영향력을 줄인다는 이야기.
이건 위에 1/N, 그거야. 링크를 많이 걸 수록 N이 커져서,
결국 이 사이트를 거치는 path들의 확률은 무진장 작아지게 되지.
이는 다시 말하면 이 사이트의 영향력이 약해진다는 얘기가 되고...
설명대로의 효과를 잘 나타내.

다음으로, 링크가 많이 걸려 있는 사이트는 더 높은 rank를 준다는 이야기.
어떤 사이트로 들어오는 link가 많다는 얘기는, 결국
임의의 사이트에서 이 사이트로 올 수 있는 경우의 수가 그만큼 늘어난다는 얘기고,
따라서 다른 모든 사이트들에 대해 이 사이트의 랭킹이 높아지는 효과가 일어나지.
역시 설명대로의 효과를 잘 나타내지...

하지만 실제 구체적인 알고리즘이 어떻게 되는지 알고 나면
걔들이 발표한 직관적인 설명 및 장점들은, 실제 PageRank 알고리즘의 진가에 비하면
그저 빙산의 일각일 뿐이라는 것을 알 수 있지...

추천 비추천

0

고정닉 0

0

원본 첨부파일 1

댓글 영역

전체 리플 0
등록순정렬 기준선택

하단 갤러리 리스트 영역

왼쪽 컨텐츠 영역

갤러리 리스트 영역

갤러리 리스트
번호 제목 글쓴이 작성일 조회 추천
설문 환불하러 갔다가 물건 더 사올 것 같은 순둥이 스타는? 운영자 20/10/27 - -
AD [삼성 디지털프라자] 가전을 나답게 BESPOKE&그랑데AI 운영자 20/10/23 - -
공지 프로그래밍 관련 내용이 있어야 합니다. [14] 운영자 20.09.28 898 18
1509253 string 클래스 하나 만드는데 2시간 걸리네.. [2] 뭐하냐지금갤로그로 이동합니다. 05:36 18 0
1509252 생활코딩 html 보는데 실습은 뭘로 해야함? [4] ㅇㅇ(125.189) 05:30 23 1
1509251 인덱스 거는 방법론적인 원ㄹ도 모르는게 뭔 풀스택이냨ㅋㅋㅋㅋㅋㅋㅋㅋ 솔직맨갤로그로 이동합니다. 05:24 15 2
1509250 풀스택의 상위호환은 아키텍쳐임 솔직맨갤로그로 이동합니다. 05:23 14 1
1509249 이제는 페북에 이어 kt마저 위키추상화갤로그로 이동합니다. 05:16 17 0
1509246 얘들아 난 페북으로 간다 [1] 위키추상화갤로그로 이동합니다. 04:33 42 0
1509245 서른다섯번째 문제 최소힙 파이썬4주완성갤로그로 이동합니다. 04:18 37 0
1509244 풀스택 다음 스텝은 뭐냐? [3] ㅇㅇ(124.44) 04:09 42 0
1509243 오늘 집합론이랑 일반물리복습마무리하고... 영어 소설 읽던거마무리하고.. 인공무현갤로그로 이동합니다. 04:07 24 0
1509242 헤르미온느 따먹은 네빌롱바텀 근황.jpg 동반꿀갤로그로 이동합니다. 04:04 53 2
1509241 리액트 네이티브를 이용한 특강에 참여하게됐는데요 ㅇㅇ(125.189) 04:03 15 0
1509240 혹시 S3 서울리전에 야짤 올리면 불법인거 아냐???? [4] ㅇㅇ(117.111) 03:51 55 0
1509239 서른네번째 문제 아나그램 파이썬4주완성갤로그로 이동합니다. 03:49 23 0
1509237 아 좀 한번에 연락 좀 하지말고 ㅇㅇ(61.40) 03:48 15 0
1509236 학교 과제땜시 리눅스에서 어셈으로 코딩하는데 [2] dd(61.77) 03:45 45 0
1509235 구글 아이콘 바뀐 거 나만 마음에 들어하나? [1] ㅇㅇ(14.63) 03:41 35 0
1509234 아이폰은 어플내 폴더 접근할수없음? ㅅㅂ 각성피에로(110.47) 03:41 29 0
1509233 커뮤니티 사이트의 게시판 보드 디자인 관련 [1] 허헉(123.142) 03:40 38 0
1509232 어플 3개 개발한 회사 vs 이제 막 시작한 [14] ㅇㅇ(61.40) 03:38 58 0
1509231 축구나 해외야구 api 어디가 젤 좋음? ㅁㄴㅇㅁㄴㅇ(106.242) 03:31 13 0
1509230 느긋하게 공부나 좀 하고 싶다. [3] 솨르(58.87) 03:30 38 0
1509229 솨르좌 / 와 이런 버전도 잇구나 나트륨찡갤로그로 이동합니다. 03:30 26 0
1509228 솨르좌 / 와 이런 그림도 잇구나 ㅇㅅㅇ [4] 나트륨찡갤로그로 이동합니다. 03:26 46 0
1509226 솨르좌 / ㅓㅜㅑ [6] 나트륨찡갤로그로 이동합니다. 03:21 65 0
1509225 님들 졸작 안드로이드어플 만드는데 질문좀용 [4] ㅇㅇ(119.194) 03:16 52 0
1509224 정선호-비주얼베이직2015 책 있는친구...? 완전급함(180.69) 03:14 15 0
1509223 내 클론코딩 필기 수준 이정도면 ㅇㅈ? [9] 솨르(58.87) 03:13 85 0
1509222 ffmpeg 잘알있음? ㅇㅇ(175.196) 03:12 29 0
1509221 아니 이새끼들 기술 스택쓰는거 다 사기네?? [5] ㅇㅇ(61.109) 03:07 61 0
1509220 LOC(코드수) 는 말 그대로 코드 라인수를 말하는 것 [3] 루비(118.216) 03:01 40 0
1509219 개 좆박았다ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ [3] 솔직맨갤로그로 이동합니다. 02:59 46 0
1509218 솔직히 인공지능 [1] ㅇㅇ(118.235) 02:55 31 1
1509217 어제 이번주에 신입왔는데 이새끼 [4] ㅇㅇ(59.14) 02:50 62 0
1509216 크리스마스 하면 이마트만 생각나 ㅇㅇ(218.54) 02:46 18 0
1509215 곧크리스마스니 스노우효과만들가 [2] 피에로는배달원갤로그로 이동합니다. 02:42 32 0
1509214 자야지 슬슬 [1] ㅇㅇ(218.54) 02:41 16 0
1509212 와 스프링 개좆같다. 왜케 어렵냐 ㅇㅇ(121.130) 02:39 20 0
1509211 국비충만 몰래 들어와봐 [1] ㅇㅇ(223.62) 02:39 28 0
1509210 대체 이게 뭔 뜻이다냐 ㅇㅇ(124.51) 02:37 28 0
1509209 구글캘린더 아이콘도 바꿔버렸노 헬마스터갤로그로 이동합니다. 02:35 32 0
1509207 본인 입갤함 [3] 솔직맨갤로그로 이동합니다. 02:22 48 0
1509206 백준 이거 node js readFileSync 머임 [4] 솨르(58.87) 02:21 51 0
1509205 내가 싫어하는 부류 [4] 산기대17세갤로그로 이동합니다. 02:20 74 0
1509204 아무리 생각해도 구글이 짱이다 나트륨찡갤로그로 이동합니다. 02:20 26 0
1509203 c 코딩 질문 받아주시나여 [11] ㅇㅇ(110.13) 02:19 61 0
1509201 과제 우액 [1] 저기,,갤로그로 이동합니다. 02:17 26 0
1509200 구글 음모론 고급정보 검색 잘 안댐 ㅇㅅㅇ 나트륨찡갤로그로 이동합니다. 02:16 26 0
1509199 방금 외주요청 들어옴 Python갤로그로 이동합니다. 02:16 25 0
1509198 나는 컴활을 왜 붙들고있는것인가 ㅇㅇ(220.82) 02:15 24 0
갤러리 내부 검색
전체게시물 정렬 옵션

오른쪽 컨텐츠 영역

이슈줌NEW

1/6

힛(HIT)NEW

그때 그 힛

1/3