HITS 알고리즘

하이퍼링크 유도 주제 검색(HITS; 허브 및 권한이라고도 함)은 존 클라인버그가 개발한 웹 페이지의 등급을 매기는 링크 분석 알고리즘입니다.Hubs and Authorities 뒤에 있는 아이디어는 인터넷이 처음 형성되었을 때 웹 페이지의 생성에 대한 특별한 통찰에서 비롯되었습니다. 즉, 허브라고 알려진 특정 웹 페이지는 그들이 보유한 정보에서 실제로 권위적이지 않은 큰 디렉토리 역할을 했습니다.그러나 사용자가 다른 권위 있는 페이지로 직접 이동할 수 있도록 하는 광범위한 정보 카탈로그의 컴파일로 사용되었습니다.즉, 좋은 허브는 다른 많은 페이지를 가리키는 페이지를 나타내는 반면, 좋은 권한은 많은 다른 ^[1]허브에 의해 연결된 페이지를 나타냅니다.

따라서 이 체계는 각 페이지에 대해 두 개의 점수를 할당합니다. 페이지 내용의 값을 추정하는 권한과 다른 페이지에 대한 링크 값을 추정하는 허브 값입니다.

역사

저널에서

과학 저널의 중요성을 평가하기 위해 많은 방법이 사용되었습니다.그러한 방법 중 하나가 가필드의 영향 요인입니다.사이언스나 네이처 같은 잡지들은 수많은 인용구들로 가득 차 있어서, 이러한 잡지들은 매우 높은 영향 요인을 가지고 있습니다.따라서, 거의 같은 수의 인용문을 받았지만 이 저널들 중 하나가 사이언스와 네이처로부터 많은 인용문을 받은 두 개의 더 알려지지 않은 저널을 비교할 때, 이 저널은 더 높은 순위를 차지해야 합니다.다시 말해서, 중요하지 않은 ^[2]저널보다 중요한 저널에서 인용문을 받는 것이 더 낫습니다.

웹에서

이 현상은 인터넷에서도 발생합니다.페이지에 대한 링크 수를 세는 것은 웹에서 해당 링크의 중요성에 대한 일반적인 추정치를 제공할 수 있지만, 이 링크 중 두 개가 Yahoo!, Google 또는 MSN과 같은 사이트의 홈 페이지에서 가져온 경우에는 들어오는 링크가 거의 없는 페이지도 두드러질 수 있습니다.이러한 사이트는 매우 중요하지만 검색 엔진이기도 하기 때문에 페이지의 실제 관련성보다 훨씬 더 높은 순위를 매길 수 있습니다.

알고리즘.

루트 세트를 기본 세트로 확장

스텝

HITS 알고리즘에서 첫 번째 단계는 검색 쿼리와 가장 관련이 있는 페이지를 검색하는 것입니다.이 집합을 루트 집합이라고 하며 텍스트 기반 검색 알고리즘에 의해 반환되는 최상위 페이지를 가져옴으로써 얻을 수 있습니다.기본 세트는 루트 세트에서 연결된 모든 웹 페이지와 연결된 일부 페이지로 루트 세트를 보강하여 생성됩니다.기본 집합의 웹 페이지와 해당 페이지 사이의 모든 하이퍼링크는 초점을 맞춘 하위 그래프를 형성합니다.HITS 계산은 이 포커스가 있는 하위 그래프에서만 수행됩니다.Kleinberg에 따르면 기본 집합을 구성하는 이유는 가장 강력한 권한의 대부분(또는 많은)이 포함되도록 보장하기 위한 것입니다.

권한 및 허브 값은 상호 재귀에서 서로의 관점에서 정의됩니다.권한 값은 해당 페이지를 가리키는 축척된 허브 값의 합계로 계산됩니다.허브 값은 허브가 가리키는 페이지의 크기가 조정된 권한 값의 합계입니다.일부 구현에서는 연결된 페이지의 관련성도 고려합니다.

이 알고리즘은 일련의 반복을 수행하며, 각 반복은 두 가지 기본 단계로 구성됩니다.

권한 업데이트:각 노드의 권한 점수를 해당 노드를 가리키는 각 노드의 허브 점수 합계와 동일하게 업데이트합니다.즉, 노드는 정보 허브로 인식되는 페이지에서 연결되어 높은 권한 점수를 받습니다.
허브 업데이트:각 노드의 허브 점수를 해당 노드가 가리키는 각 노드의 권한 점수 합계와 동일하게 업데이트합니다.즉, 해당 주제에 대한 권한으로 간주되는 노드에 링크하여 노드에 높은 허브 점수가 부여됩니다.

노드의 허브 점수 및 기관 점수는 다음 알고리즘을 사용하여 계산됩니다.

허브 점수와 권한 점수가 1인 각 노드부터 시작합니다.
권한 업데이트 규칙 실행
허브 업데이트 규칙 실행
각 허브 점수를 모든 허브 점수의 제곱합의 제곱근으로 나누고 각 기관 점수를 모든 기관 점수의 제곱합의 제곱근으로 나누어 값을 정규화합니다.
필요에 따라 두 번째 단계부터 반복합니다.

페이지랭크와 비교

페이지 및 브린의 페이지랭크와 같은 HITS는 웹에 있는 문서의 연결을 기반으로 하는 반복 알고리즘입니다.그러나 몇 가지 주요 차이점이 있습니다.

PageRank의 경우처럼 모든 문서 집합 대신 '관련' 문서의 작은 하위 집합('초점 하위 그래프' 또는 기본 집합)에서 처리됩니다.
쿼리에 의존합니다. 동일한 페이지는 다른 기본 집합이 주어지면 다른 허브/권한 점수를 받을 수 있으며, 이는 다른 쿼리에 대해 나타납니다.
따라서 쿼리 시간 처리에 수반되는 성능 저하와 함께 인덱싱 시간이 아닌 쿼리 시간에 실행해야 합니다.
단일 점수가 아닌 문서(허브 및 권한)당 2개의 점수를 계산합니다.
검색 엔진에서는 일반적으로 사용되지 않습니다.(Ask Jeeves/Ask.com 에서 인수한 Teoma에서도 비슷한 알고리즘을 사용한다고 합니다.)

상세

순위를 매기기 위해 각 $페이지$ p{ $displaystyle$ $\mathrm {auth}(p)$ $=$ $1$ 과 ${displaystyle \mathrm$ { $mathrm}(p$ $)=$ $1}$ 을 ${\mathrm {hub}}(p)=1$ (를 $p$ $\mathrm {auth} (p)=1$ 합니다. 두 가지 유형의 업데이트를 고려합니다.권한 업데이트 규칙 및 허브 업데이트 규칙.각 노드의 허브/권한 점수를 계산하기 위해 권한 업데이트 규칙과 허브 업데이트 규칙을 반복적으로 적용합니다.Hub-Authority 알고리즘을 k단계로 적용하려면 먼저 권한 업데이트 규칙을 k배 적용한 다음 Hub Update 규칙을 적용해야 합니다.

권한 업데이트 규칙

$각$ p $\displaystyle$ p $p$ 에 대해, $\mathrm {auth} (p)$ 는 $\mathrm {auth} (p)$ ( $\mathrm {auth} (p)=\displaystyle \sum \nolimits _{q\in P_{\mathrm {to} }}\mathrm {hub} (q)$ {\ $displaystyle \mathrm {auth}$ ( $\mathrm {auth} (p)=\displaystyle \sum \nolimits _{q\in P_{\mathrm {to} }}\mathrm {hub} (q)$ $=$ $\mathrm {auth} (p)=\displaystyle \sum \nolimits _{q\in P_{\mathrm {to} }}\mathrm {hub} (q)$ ∑ $P$ 를 $\mathrm {auth} (p)=\displaystyle \sum \nolimits _{q\in P_{\mathrm {to} }}\mathrm {hub} (q)$ ub ( $)$ ( $q)$ ({\displaystyle \ $mathrm$ {auth} (p $)$ =\ $displaystyle \mathrm$ ${auth$ $} (p)$ 로 $\mathrm {auth} (p)=\displaystyle \sum \nolimits _{q\in P_{\mathrm {to} }}\mathrm {hub} (q)$ $\mathrm {auth} (p)$ 합니다. $P_{\mathrm {to} }$ 서 $P는$ $p$ 를 모든 페이지에 $P_{\mathrm {to} }$ $P_{\mathrm {to} }$ 링크합니다 $.$ $페이지$ 의 권한 점수는 해당 페이지를 가리키는 모든 허브 점수의 합계입니다 $p$

허브 업데이트 규칙

$각$ p $\displaystyle$ p $p$ 에 대해,우리는 $($ $\mathrm {hub} (p)=\displaystyle \sum \nolimits _{q\in P_{\mathrm {from} }}\mathrm {auth} (q)$ ) {\ $displaystyle$ $\mathrm {hub} (p)=\displaystyle \sum \nolimits _{q\in P_{\mathrm {from} }}\mathrm {auth} (q)$ $\mathrm$ { $mathrm$ $\mathrm {hub} (p)=\displaystyle \sum \nolimits _{q\in P_{\mathrm {from} }}\mathrm {auth} (q)$ ) $=$ $\mathrm {hub} (p)=\displaystyle \sum \nolimits _{q\in P_{\mathrm {from} }}\mathrm {auth} (q)$ $\mathrm {hub} (p)=\displaystyle \sum \nolimits _{q\in P_{\mathrm {from} }}\mathrm {auth} (q)$ $\mathrm {hub} (p)=\displaystyle \sum \nolimits _{q\in P_{\mathrm {from} }}\mathrm {auth} (q)$ $\mathrm {hub} (p)=\displaystyle \sum \nolimits _{q\in P_{\mathrm {from} }}\mathrm {auth} (q)$ { $mathrm}(p$ ) $\mathrm {hub} (p)=\displaystyle \sum \nolimits _{q\in P_{\mathrm {from} }}\mathrm {auth} (q)$ =\ $displaystyle \mathrm$ {p $}(p)$ )\displaystyle \ $mathrmetits_{q\$ $in$ $P_{from}}}}\mathrmathrm$ $P_{\mathrm {from} }$ { $auth}(q$ } $페이지$ $P}$ $페이지$ 를 $P_{\mathrm {from} }$ $P_{\mathrm {from} }$ 합니다. $링크$ 를 $p$ $표시합니다.$ 즉, 페이지의 허브 점수는 해당 페이지가 가리키는 모든 권한 점수의 합계입니다.

정규화

노드의 최종 허브 권한 점수는 알고리듬의 무한 반복 후 결정됩니다.허브 업데이트 규칙 및 권한 업데이트 규칙을 직접적이고 반복적으로 적용하면 값이 분산되므로 반복할 때마다 행렬을 정규화해야 합니다.따라서 이 과정에서 얻은 값은 결국 수렴됩니다.

의사코드

G : = G do.auth = 1 // p.auth의 각 페이지에 대한 페이지 집합은 페이지 p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.p.1.p.p.p.p.p.p.p.p.p.p.p.p.1incomingNeighbors do // p.incomingNeighbors는 p.auth += q.squarenorm(p.auth) // 연결된 페이지 집합으로, G do // 인증 점수 p.auth = p의 각 페이지에 대한 표준화를 위해 제곱된 인증 값의 합을 계산합니다.auth / norm // G do //의 각 페이지에 대한 auth 값 norm = 0을 정규화한 다음 p.outgoingNeighbors do // p.outgoingNeighbors는 p.do += r.auth norm + square(p.에서 각 페이지 r.r.에 대한 모든 허브 값을 업데이트합니다.hub) // G do의 각 페이지에 대해 norm = sqrt(norm)를 정규화하기 위한 제곱 허브 값의 합을 계산한 다음 모든 허브 값 p.sql = p.sql / norm // hub 값을 정규화합니다.

허브 및 권한 값은 위의 유사 코드에 수렴됩니다.

알고리즘이 실행되는 단계 수를 제한해야 하기 때문에 아래 코드는 수렴되지 않습니다.그러나 이 문제를 해결하는 한 가지 방법은 각 권한 값을 모든 권한 값의 제곱합의 제곱근으로 나누고 각 허브 값을 모든 허브 값의 제곱근의 제곱근으로 나누어 각 허브 값과 권한 값을 정규화하는 것입니다.위의 의사 코드는 다음과 같습니다.

비집약 의사 코드

G := 각 페이지 p에 대한 페이지 집합 G dop.auth = 1 // p.auth는 페이지 p의 권한 점수입니다.pg = 1 // p.pg는 페이지 p 함수 Hubs And의 허브 점수입니다.1부터 k do //까지의 단계에 대한 권한(G)은 각 페이지 p do // update 모든 권한 값의 첫 번째 p.auth = 0 p.incomingNeighbors do // p.incomingNeighbors는 p.auth + q에 연결되는 페이지 집합입니다.G do //의 각 페이지에 대한 허브를 선택한 후 p.dll = 0을 업데이트합니다.p.outgoingNeighbors do //p.outgoingNeighbors는 p.dll += r.auth로 연결되는 페이지 집합입니다.

참고 항목

페이지랭크

레퍼런스

^ Christopher D. Manning; Prabhakar Raghavan; Hinrich Schütze (2008). "Introduction to Information Retrieval". Cambridge University Press. Retrieved 2008-11-09.
^ Kleinberg, Jon (December 1999). "Hubs, Authorities, and Communities". Cornell University. Retrieved 2008-11-09.

Kleinberg, Jon (1999). "Authoritative sources in a hyperlinked environment" (PDF). Journal of the ACM. 46 (5): 604–632. CiteSeerX 10.1.1.54.8485. doi:10.1145/324133.324140. S2CID 221584113.
Li, L.; Shang, Y.; Zhang, W. (2002). "Improvement of HITS-based Algorithms on Web Documents". Proceedings of the 11th International World Wide Web Conference (WWW 2002). Honolulu, HI. ISBN 978-1-880672-20-4.

외부 링크

미국 특허 6,112,202
관계형 데이터베이스에서 데이터 검색 엔진을 생성합니다. HITS 기반의 C# 검색 엔진입니다.

[1] Christopher D. Manning; Prabhakar Raghavan; Hinrich Schütze (2008). "Introduction to Information Retrieval". Cambridge University Press. Retrieved 2008-11-09.

[2] Kleinberg, Jon (December 1999). "Hubs, Authorities, and Communities". Cornell University. Retrieved 2008-11-09.

[1]

[2]

Search