Link Analysis and Web Search

그래프 데이터는 map, SNS, … 데이터 하나하나가 노드인데, 데이터 간 연관상황이 생기는 것. 이걸 그래프로 표현할 때 제일 간단명료하게 표현할 수 있다.

웹그래프에서 노드를 분석할수도 있지만, 노드는 각각 분리된 정보들. 재밌는 일은 이 노드들이 복잡하게 연결되어서 벌어지는 거니까, 그래프 중에서도 노드가 아니라 링크 분석임.

 

 

인포메이션 리트리벌이라는 말 알아둬라. 줄임말 IR

→ document쪽에서 많은 document가 모여있을 때 키워드 중에서 document를 뽑아내는 분야가 IR.

라이브러리 사이언스와 같은 학과에서 이게 가장 중요함.

Synonymy : 파(양파 쪽파 대파 등등 종류)

Polysemy : 재규어 -> 동물, 차 등등

사람들이 똑같은 생각을 가져도 검색어를 똑같이 쓰지 않고, 또 생각이 다르고 → 서치엔진은 중요하다.

 

- 웹이 있으면 중요도가 다름 -> 이걸 숫자화

-> 어떤게 중요한 웹? 다른 웹페이지들이 링크를 많이 걸어주는 녀석!

 

 

- 모든 인커밍 링크를 누구한테서 왔는지를 고려! 개수만 많은게 중요한게 아니라, 중요한 사람이 링크 걸어주는게 나를 더 중요하게 만듦.

- new score : 소스쪽의 점수의 합.

 

- 상호간의 인터 디펜던시가 있음.

-> 왼쪽의 애들이 중요해지려면, 오른쪽 애들의 합이. 오른쪽에들이 중요해지려면, 왼쪽 애들의 합이 되어야함.

- 왓다갓다하며 점수 계산해야 좀 더 이상적인 계산. -> 왔다갔다 노말라이즈를 해야함!

- 굿 리스트에서 오는 인커밍의 경우 웨이트를 높게 평가함.

- 키워드를 포함하는지, 얼마나 빈번하게 포함되는가가 중요한가? 단순히 키워드의 포함여부, 빈도로 안되겠다 해서 나온게 이런 알고리즘임.

-> '미국 동부'에서 개발됐음. 서부는 구글. 요즘은 구글에서 이 동부 알고리즘도 병행해서 사용.

 

- 허브: 여러개로 뻗어나가는 그 지점. 주로 디그리가 높은 노드. 좋은 링크를 걸고 있는 쪽을 허브라고 함.

- 오솔리티 : 권위 있는 페이지. 찾고자 하는 페이지.

-> 차를 사려면 현대차도 기아차도 들어가봐야하는데 , 이 차 회사 홈페이지들이 오솔리티고. 차 목록 정보를 모아놓은게 리스트를 가진게 허브. -> 위 그림에서는 허브가 왼쪽이겠지.

- 각 웹페이지 p에 대해서, 허브 역할을 할 수도 있고 오솔리티 역할을 할 수도 있음. 그래서 두 스코어를 다 계산해야함. 처음엔 이니셜라이즈를 다 똑같이 해주고 시작함.

 

- 일반적인 모든 웹페이지는 이 두개의 스코어를 다 계산해야함.

→ 일단 오솔로지 스코어 업데이트를 함.

→ 어떤 웹페이지 p의 오솔로지 스코어 : p를 가리키는 페이지들의 허브 스코어의 합을 오솔리지 스코어로 함.

→ 허브 스코어는 그럼 어떻게? 그 허브를 가리키는 페이지들의 오솔리지 스코어가 높아야함.

 

- 이거를 얼터네이팅(왔다갔다) 할거임. 1로 초기화 후 몇 번 돌지 정한다음, 허브 오솔러티 각각 계산.

-> 계속 k번을 돌아가고 노말라이즈

- 오솔러티 스코어는 나를 가르켜주는 노드들의 허브스코어,

- 허브 스코어는 내가 가리키는 페이지들의 오솔리티 스코어

→ 왔다갔다하면서 점수 계산 → 노말라이즈

 

- 노말라이즈는 합이 1이되도록 많이 하는데,

- k번 반복하는데, 이걸 굉장히 오랫동안(큰K)진행하게 되면 노말라이즈 된 값들의 경우엔 converge해서 이퀼리브리엄으로 간다. 수렴한다.

- 수렴했다가 무슨 뜻? → K번째 인터레이션 계산한거랑 K+1번째랑 별로 차이가 안나~

-> 이전 인터레이션-바로다음인터레이션 해서 절댓값 뭐 더하든 제곱하든 해서 특정한 주어진 값 미만이면 끝을 내게 됨. 차이값이 0.0001 이하면 0으로 치고 끝내자 하고 돌아가는 것.

→ 노드가 엄청 많은데, 딱 수렴하는 경우는 잘 없으니까.

- 또 중요한 사실. 초기 값이 중요할까? →positive 값으로 초기화만 해주면 같은 극한 값으로 간다.

 

- 왼쪽에 쪼꼬만 동그라미도 사실은 업데이트 되는데, 이 값도 같이 수렴할 것이다(?) 당연하지

- 지금 배우는 뱅법이 허브 오쏠러티임.

- endorsment 낙인을 꽉 : 내가 좋은사이트 링크 잘 걸면 허브 스코어가 올라감. 누군가가 나를 인도어스 해준 적은 없지만. 내가 링크 건 애들이 오솔러티 스코어가 높은 애들이기 때문.

- 새로운 웹페이지(오솔리티)가 나의 허브 스코어를 받잖아. 내가 강력하게 인도어스 해줄 수 있음. 내가 좋은 링크 걸어서 나의 허브스코어 올려놨으니까.

- 허브오솔리티에서 페이지는 멀티플 = 허브 or 오솔리티의 롤을 함. → 그럼 페이지랭크는 멀티플 아니겠지?

 

- 페이지 랭크라는 방법도 있다. 얘는 중요도 하나만 계산함.

- 한 페이지에서 다른 페이지로 중요도 점수를 전달해준다. 어떤 페이지의 임폴턴스 스코어가 올라가려면?

- 많은 인도어스. 많은 인커밍 링크를 받음 or 중요한 쪽(임포턴스 스코어가 높은)에서 나를 인도어스 해줘야 함.

-> 현재 중요하다고 여겨지는 페이지는 점점 더 강력해지는 현상이 생김

 

- 여기서 링크는 방향성이 있음. 다이렉티드. 보아하니 A가 스코어가 제일 높을 것 처럼 보임.

- 근데 A는 이미 슈가야. A는 B,C에 링크를 검. B,C는 인커밍 링크가 하나임. 하나는 원래 대단한게 아니지만, 그 하나가 슈가로부터 왔음

→ B,C도 같이 중요해진다. → 단순히 인커밍링크 개수뿐만이 아니라, 그 각 링크의 가치는 다르다.

 

- 페이지 랭크는 플루이드. 임폴턴스 스코어가 링크를 타고 흐른다고 생각.

- 노드 위에 관찰되는 물의 총 량. 이게 많으려면 ? 들어오는 물의 양이 많아야지. 인커밍 링크 개수가 많아야 하고, 그리고 스코어가 높은쪽에서 물을 이빠이 보내주면 좋다.

- 처음에 1/n으로 초기화함. 처음엔 누가 더 좋은지 모르니까.

→ 어떤 값으로 이니셜라이즈해도 같은 페이지 랭크 값으로 수렴한다.

→ 그럼 1/n으로 이니셜라이즈 하는 이유는? 이게 제일 나아서 그냥..

 

- 기본형 페이지 랭크는 어떻게 하느냐. 아웃풋이 5개야 → 스코어를 공정하게 나눠줘야 한다.

만약 아웃풋 링크가 없다? → 나에게로.

 

- 이런 개념으로 생각하면, 1/n으로 이니셜 라이즈 했어 → 모든 스코어의 합은 1이 되도록 함.

→ 누가 물을 더 부어주지 않고 전달만 하고 있음 → 합이 달라질 일이 없음 → 줄줄 새는 것도 없음

 

- 노드가 총 8개. 모든 노드의 페이지랭크스코어를 1/8로 이니셜라이즈 함.

A의 입장에서 보면, 첫번째 인터레이션에서는 인커밍링크가 5개.

D도 최초에 1/8로 시작해서, D입장에서는 아웃풋이 2개 → A에게 1/16을 줄 것.

E는 1/16, H는 1/8, F도 1/8, G는 1/8을 줄터이니 → 덧셈하면 1/2임. 다른 노드들에 대해서도 등일하게 진행하면 됨.

이렇게 스텝1이 끝나면, 스텝 2에서는 1의 결과를 가지고 동일한 계산을 진행함.

그러다보면 컨벌즈하게 됨.

 

- 컨벌즈 상태. 이퀼리브리엄 페이지 랭크.

- A는 D로부터 1/26, E로부터 1/26, H로 1/13, F G도 1/13 → 합하면 4/13인데

→ 현재 있던 값과 동일한 값이 다음 인터레이션에도 나온 것. 다른 노드도 마찬가지.

- B C : 인커밍링크 하나밖에 없지만 슈가의 링크를 받으니까 값이 나름 큼.

- H는 인커밍링크가 두개지만, 잔잔바리다. 중요도가 B,C의 반 밖에 안되는 것.

-> 인커밍링크 개수도 중요하지만 누가 줬는지도 중요하고, 수렴하고, 계산과정도 알고.

 

- k가 이터레이션 횟수 → 무한대로 가면 페이지 랭크 값은 극한값으로 수렴함. 허브 오솔러티 스코어 마냥!

- 한 스텝 더 해보면, 모든 페이지 랭크 값이 동일하게 나옴.

-> 그래프의 구조에 따라 그 땐 극한값이. 즉 이퀼리브리엄이 여러 세트일 수도 있음.

-> 그러나 스트롱리 커넥티드 그래프의 경우 이퀼리브리엄이 유니크하다.

 

- 근데 베이직 버전엔 문제점이 있다. 문제적인 오류가 발생해서 페이지랭크를 쏙 다 빼먹어버릴 수 있음.

 

- 이 케이스에서 F G는 서로 빼고는 다른 노드들로 물을 흘려보내지 않음.

-> 링크가 있는데도, 악의적으로 F G는 서로 주고받기만 함. → 진행될수록 모든 물이 흡수될 것.

1/2, 1/4, 1/8 , … → 다 털림 → 이게 현실로 F, G가 중요하고 나머지는 임포턴스가 0인가?

→ 실질적인 웹페이지의 중요성을 평가하지 못함

 

- 그 다음에 나온게 스케일링한 페이지랭크. 적어도 이정도 버전 정도는 다뤄주야지

- 기존의 문제가 들어오는 길은 있는데, 나가는 길이 없음 → 쌓이게됨 → 가상으로 길을 뚫어주면 좋겠지? 링크에 100% 의존해서 물이 흐르게 하니까 물의 흐름이 막혀버리는 경우가 생김 → 페이지 중요도 계산에 악영향

 

→ 100%라 생각하지 말고, 1이라는 것 중에서 S(0.7~8)정도는 링크를 따라 흐르게 하고, 나머지 1-S만큼은 증발시켜서 비로 내리도록 하자가 아이디어.

- 한 노드의 입장에서는 링크를 따라 흐르는게 80%지만, 링크가 없는 노드라도 나의 20%를 공평하게 나눠주는 셈 → 모든 다른 노드로 가는 눈에 보이지 않는 링크가 생긴 셈

= s 만큼 scale down하겠다 → 남아있는 1-s만큼의 페이지랭크값은 똑같이 모든 노드에 나눠주겠다.

 

- 이렇게하면, scaled버전도 유일한 이퀼리브리엄으로 수렴을 함. 물론 s값이 바뀌면 정답도 바뀜.

- 실제로 많이 사용된 알고리즘임 → s값이 대략 0.8~9 정도 되면 전체 시스템이 잘 동작하는 것으로 경험적으로 알려졌음.

 

Random Walks도 별로 안중요한 줄 알았으나, 여기 저기서 언급됨.이 링크 저 링크 누르는걸 웹서핑이라고 함.

- 랜덤 서퍼 : 랜덤 walk를 하는데, 다음 갈 페이지를 링크를 따라 가겠다. → 선호하는 링크도 없음. 말 그대로 눈 앞에 있는 링크 중 랜덤하게 선택. 아웃고잉 링크가 20개면 1/20확률로 하나 골라서 가는 것.

k스텝 가는 것으로 생각하면, 각 스텝에서 random walk하는 서퍼들이, 현재 페이지에서 랜덤하게 골라서 링크가 가리키는 페이지로 이동한다. 이게 랜덤워크(?) -> 기본형 페이지 랭크와 동일하게 움직임.

 

- 리피티드 임프루브먼트 : 앞에 나왔던 것. 극한값 관련해서 이전 인터레이션 값을 가지고 좀 더 정확한 다음 값을 구하고, 뭐 이런식으로 극한값에 다가가는 계산

-> F나 G노드로 가긴 감. 각자 1/2이라는 페이지 랭크 값을 갖게 되고, 나머지는 다 0이라는 값으로 수렴하게 됐었음.

스케일드 S라는 이름으로 랜덤하게 엣지를 하나 골라서 따라간다. 1-S로는 어떻게 하냐? 텔레포트!

 

구체적으로 이렇게저렇다 얘기하는게 어렵다. 알고리즘을 알면 순위를 올리는 생각을 할 수 있다. 의도를 가지고.

어쨋거나 페이지랭크라는 알고리즘은 구글이 몇 년에 한 번씩 논문을 냄. 알고리즘은 간단하다.

 

웹에는 하이퍼링크도 있지만, 다른 많은 것들이 들어있음. 그래서 이런것들도 이용하면 좋다.

ex) 앵커 텍스트도 이용. 하이퍼링크 달 때 파란색으로 나와있는 텍스트를 누르는데, 그 텍스트. 연결된 페이지의 서머리 같은게 쓰여 있을 것.

→ 이걸 통해 해당 웹페이지의 서머리를 알 수도 있음. 다른 텍스트와 다르게 좀 더 중요하게 이용을 하고싶다.

- 사용 데이터도 있는데, 로그의 형태로 남아있을 것. 뭐를 클릭했냐, 클릭 한번에 몇 초 봤냐 이런거.

→ 이런거까진 얘기할 순 없고. 이 챕터에서는 오매불망 웹페이지들의 링크구조 가지고 중요도계산하는것에 집중.

 

- 무빙 타겟 : 타겟은 고정되어 있어야 하는데, 애매한 상황(?)

→ 게임 이론 관점에서 봤을 때, 사람들은 서치엔진 결과에 대해 상위에 오르고 싶어함. 클릭을 유도하고 구매까지 이끌어내고싶기 때문

→ 유저의 눈에 들기 위해 서치엔진의 결과에 상위에 들어가야함.

 

- 구글의 랭킹 펑션이 업뎃되면 많은 사람이 영향을 받음.

 

서치 엔진 옵티미제이션이라고 부름

- 퍼펙트 랭킹 펑션이 있다 치면, SEO 업체들이 알아내서 실제로 퀄리티 높지 않은 링크들이 올라가고 그러겠지.

→ 퍼펙트 랭킹 펑션의 정의가 또 훼손됨 → 또 펑션 바꾸고 이게 반복

-> 서치 엔진은 웹사이트 디자이너 SEO사람들 때문에 잘 안알려준다. 광고로 서치 인더스트리가 엄청 돈을 벌었다.

 

- 허브 오쏠리지, 페이지랭크의 한계값이 네트워크에서 파생된 특정 행렬의 eigenvectors(고유벡터)의 좌표로 해석됨을 보인다.

- 그래프에도 스펙트랄 애널리시스가 있다.

 

- 행 1이 노드1, 열1이 노드1 이런 식으로 [0][1]에서 보면 노드1에서 노드2로 가는 방법이 한개다!

- 매트릭스 1과 2, 1과 4가 연결됐음 → 합이 9(6+3) : 첫 칸이 1 to 1임! 인덱스가 아님! 0 시작 아님!

이 매트릭스를 눈 뜨고 잘 보면, 1번이 4번을 링크를 걸고잇다 → 바로바로 나옴.

→ 오솔리티 스코어 계산할 땐 할 수 있음.

 

- 허브 스코어는 이런 남을 가리키는 링크 만으로 계산되지 않음.

왔다갔다 하면서 일을 진행하는데, auth는 오솔리티 벡터에서 왔을 것.

이 매트릭스 M을 가지고는 순방향으로 밖에 못감.

-> 이 링크는 어디에서 왔냐 ? 보려면 트랜스포즈 해줘야함.

-> 그런다음 허브스코어 곱해주면 오솔리티스코어가 나옴.

 

결론적으로 이거를 정돈해보면,h(1) = M a^(0) h(1)= (MM^T)^k * h^(0).

 

- 이런식으로 계산하면 매그니튜드(크기)가 커지기만 함.

-> 계속 자라니까 노말라이즈 해줘야 converge가 됨 → 벡터의 길이는 길어져서 노말라이즈 하지만, 방향이 컨버지했다는 것.

벡터는 크기=길 + 방향으로 이루어짐 → 길이 1로 고정하면 오로지 방향

→ 이게 컨버지된다 = 어느순간부터 바뀌지 않는다.

 

(구) PPT -> 여기서부터 뇌절임!!

- Convergence criteria : 허브와 오솔리티스 벡터 값의 차이의 제곱의 합이 e(?)보다 작으면 종료

- HITS 알고리즘 : 허브와 오솔리티 벡터값을 루트n 분의 1로 이니셜라이즈

-> t번쨰 인터레이션 가지고 t+1번쨰 인터레이션을 구함.

 

오솔리티 벡터는 a1~an, 허브도 h1~hn

Aij → i : j로 가는 길이 있다

hi = 시그마Aij * aj 해서 나온다.

→ h = A * a -> a = A^t(트랜스포즈) * h

나에서 나가는 정보는 A → 들어오는 정보는 트랜스포즈 해야함.

a = a^T * h?

a = a^T * (A*a)

a= a^T(Aa) = (A^T A)a

h= A(A^T h) = (A A^T)h

then,

a = (A^t*A)^k * a

h = (A*A^T)^k * h

수렴했을 때, a = (A^T A)의 아이겐벡터

허브 h = (AA^T)의 아이겐벡터

여기서 페이지랭크 매트릭스 포물레이션에서는

Mij를 1/dj로 해놨음(디그리 분의 일)

Mij는 j에서 i로 가는 링크가 있다는 뜻. 페이지랭크에서 계산하는 것은 주변으로부터 받은 물을 모으고 모아서 덧셈을 한 것이 나의 다음 인터레이션 페이지 랭크 값임. → i로 오는 것들을 이렇게 써놓은 것.

디그리가 3이라면 1/3이 3개, 5라면 1/5가 5개. 한 컬럼의 줄 다 더하면 1임.

r = M * r(수렴)

하…….

수렴하긴한다…

1~10000000등까지가 아님. 해봤자 상위 수백등까지만 제대로해줘도 만족임.

 

 

 

< 다른 주제. Personalized PageRank : PPR>

- PPR : 주어진 검색어에 맞춰서 특화해서 페이지랭크를 함

- 목표는 페이지를 검색어(topic)가 주어지면 일반적인 파퓰래러티만 고려하는게 아니라, 이 쿼리랑 얼마나 가까운지를 보겠다

- 핵심→ 텔레포트 : 링크를 따라 100%의 페이지랭크값이 흘러가는게 아니다.

- 다른 노드들에게 똑같이 나눠주세요(x) 검색어가 잇다면 검색어를 직접적으로 포함하는 웹페이지 중에 하나로 점프한다!

→ 주변에 또 뿌림 → 다시 들어오겟지? → 주변에 또 뿌리는걸 반복

- 실제로 검색을 위해 PPR 돌려보면 상위의 페이지가 해당 키워드를 갖는 경우가 많음 그러나 100%는아님.