HITS 알고리듬과 소셜 네트웍

웹 기반 정보 검색(Information Retrieval)에서 웹 문서간  하이퍼링크를 통해 좋은 문서를 찾는 랭킹 모델의 가장 중요한 알고리듬이 두 가지가 있다.

하나는 HITS(Hyperlink-Induced Topic Search)이고 나머지 하나는 페이지랭크(PageRank)이다. 두 가지 모두 너무 유명해서 설명할 것도 없지만 간단하게 정리해 보면 다음과 같다.

HITS는 웹 문서을 서로 링크로 인용하는 행렬로 보고 그 고유벡터(eigenvector)를 계산하는 방식을 기반으로 만들어졌다. 이 알고리듬은 크게 두 단계로 나뉘는데 질의어와 관계있는 문서의 부분집합(서브 그래프(subgraph))을 만든다. 그리고,  서브 그래프를 이용해서 Hub와 Authority를 계산하는 단계이다.

그림에서 보다시피 Hub는 링크를 내보내는 문서이고 Authorities는 링크를 많이 받는 문서이다. 따라서 두 가지 Factor를 모두 계산할 수 있는 장점이 있다. 이에 반해 PageRank는 백링크를 많이 받는 문서를 위주로 계산을 한다.

이 알고리듬의 문제는 질의어가 나와야 계산을 하기 때문에 문서를 인덱싱할 때 계산을 하는 PageRank에 비해 퍼포먼스가 떨어진다는 점이다. 그래서 검색 엔진에서 적극적으로 도입되지는 못했다. (Ask.com의 전신인 Teoma엔진 정도?)  테크노라티가 몇 년전에 블로그 검색 랭킹에서 이와 유사한 Authorities를 도입하기는 했었다.

HITS 알고리듬을 자세히 보면 소셜 그래프에도 적용이 가능하지 않을까 하는 생각이 든다. 기존의 소셜 네트웍에서는 친구 관계가 형성되려명 양방향이 모두 결합되어야만 가능했다.

하지만 최근 인기를 끌고 있는 Twitter의 경우는 일방향으로도 친구 관계가 성립된다. 즉, Twitter 같은 경우 Hub와 Authorities는 Follow를 받는 여부에 따라 확연히 달라지고 이들을 분석해 낼 수 있다는 것이다.

SNA의 경우, 기존의 네트워크 이론이나 복잡계 이론에서 소셜 네트웍 분석에 대한 연구가 많았지만, 소셜 네트웍이 기존 웹 문서와 링크 처럼 만들어지고 있다는 점에서 비슷하게 적용할 수 있지 않을까 하는 생각이 든다.

뿐만 아니라 이 모델은 사람들의 이동 행적과 같은 소셜 액션에도 적용이 가능하지 싶다. 요즘 토픽을 잡은 것 중에 하나가 그거다.