[NetworkX] HITS 알고리즘 (HITS Algorithm)

---

 

네트워크 그래프에서 노드의 중심성을 파악하고 계산하는 방법들을 살펴보았습니다.

• 연결중심성(Degree Centrality)과 근접중심성(Closeness Centrality)
• 매개중심성(Betweenness Centrality) 
• 페이지랭크(Page Rank)

이번엔 페이지랭크와 유사 하면서도 특별한 차이를 갖는 알고리즘을 소개합니다.
"얼마나 중심이 되는가", "얼마나 hub로서 역할을 하는가"를 별개로 계산하는 방법을  소개합니다.

바로 HITS 알고리즘(Hypertext Induced Topic Selection, HITS Algorithm)입니다.

 

 

페이지랭크와 구분되는 HITS 알고리즘의 차이점

페이지랭크와 구분되는 HITS 알고리즘의 특별한 점은 크게 두가지로 볼 수 있습니다.

 

1) 전체 그래프를 모두 탐색하지 않는다.

페이지랭크에서는 주어진 그래프 전체를 모두 탐색했습니다.

페이지랭크는 전체 웹, 하이퍼링크 상에서 가장 중요한 웹페이지들을 찾고, 우선순위를 메기고자 고안되었기 때문입니다.

 

반면 HITS 알고리즘은 전체 그래프를 따지지 않고 중심이 되는 root노드와 그 주변부를 이루는 Base노드까지만을 다룹니다.

 

Root

1차적으로 핵심인 것으로 여겨지는 노드들입니다.

예를 들어, "NetworkX"가 궁금해서 구글에 검색한다고 해봅시다.

이때 "NetworkX" 단어를 가진 웹페이지들을  Root 노드라고 할 수 있겠습니다.

 

Base

1차적으로 주변부인 것으로 여겨지는 노드들입니다.

직접적으로 "NetwrokX"를 언급하지는 않지만, root 노드로 out-degree를 가지는 노드들을 Base노드라고 할 수 있겠습니다.

 

HITS 알고리즘은 그래프 전체가 아니라 부분 그래프인, Root 노드와 Base 노드로 구성된 그래프만을 다룹니다.

 

2) 하나의 값만을 산출해내지 않는다.

페이지랭크는 일종의 노드 중요도를 단 하나의 값으로 산출해냈지만,

HITS 알고리즘은 두개의 값을 산출해냅니다. Authority값과 Hub값입니다.

 

Authority

"얼마나 중심이 되는가"

일종의 근접 중심성, 연결 중심성,  페이지랭크와 대충 비슷한 느낌입니다.

 

Hub

"얼마나 hub로서 역할을 하는가"

일종의 매개 중심성과 대충 비슷한 느낌입니다.

 

 

 

HITS 알고리즘 계산 방법

HITS 알고리즘은 k번 계산을 반복하며 값을 산출한다는 점에서 페이지랭크와 유사합니다.

페이지랭크는 값 1개, HITS 알고리즘은 Authority(이하 Auth)값과 Hub값 두개를 계산한다는 점이 큰 차이점이죠.

 

Auth(k)값은 Hub(k-1)값을 이용해 계산하고,

Hub(k)값은 Hub(k-1)값을 이용해 계산합니다.

 

아래 예시를 보면 이해가 되실거예요

 

1) k=1 단계 Auth 계산

일단 첫번째 사이클(k=1)이므로, 모든 노드의 Auth값, Hub값을 1로 둡시다.

D노드의 New Auth값

= D노드로 in-degree하는 노드들의 Old Hub값 총합

= A노드의 Old Hub값 + E노드의 Old Hub값

= 1+1 = 2

 

2) k=1 단계 Hub 계산

E노드의 New Hub값

= E노드로 out-degree하는 노드들의 Old Auth값 총합

= B,C,D,F노드의 Old Auth값 총합

= 1+1+1+1 = 4

 

3) k=1 단계 Auth, Hub Normalization

New Auth, New Hub 총합을 각각 구해서 정규화 해줍니다.

 

4) k=2 단계 Auth 계산

New Auth, Hub 값들을 Old Auth, Hub칸으로 옮겨줍니다.

저 값들은 k=1일때 도출된 값이고, 이제는 k=2니까요.

D노드의 New Auth값

= D노드로 in-degree하는 노드들의 Old Hub값 총합

= A노드의 Old Hub값 + E노드의 Old Hub값

= 1/15 + 4/15 = 5/15 = 1/3

 

5) k=2 단계 Hub 계산

E노드의 New Hub값

= E노드로 out-degree하는 노드들의 Old Auth값 총합

= B,C,D,F노드의 Old Auth값 총합

= 2/15 + 1/3 + 2/15 + 1/15 = 2/3

 

6) k=2 단계 Auth, Hub Normalization

New Auth, New Hub 총합을 각각 구해서 정규화 해줍니다.

 

 

위와 같은 과정을 반복하다보면 Auth값도, Hub값도 각각 특정 값에 수렴하게 됩니다.

 

HITS 알고리즘 값 해석

HITS 알고리즘을 통해 구한 값의 종류는 Auth, Hub 두가지니까 두가지 정보를 알 수 있습니다.

 

위 그래프에서 가장 높은 Authority(권위)를 가지는 노드는 B, C이고,

가장 Hub로서 역할을 하는 노드는 D, E라고 해석할 수 있습니다.

 

 

NetworkX로 HITS 알고리즘 계산하기

import networkx as nx

edges = [('A','D'),('B','C'),('B','E'),('C','A'),('D','B'),('D','C'),
         ('E','B'),('E','D'),('E','C'),('E','F'),
         ('F','C'),('F','H'),('G','A'),('G','C'),('H','A')]

G = nx.DiGraph()
G.add_edges_from(edges)


hub, auth = nx.hits(G)  # max_iter=100

# print(hub)
{'A': 0.0430501087640899,
 'D': 0.1874910015340169,
 'B': 0.144440892769927,
 'C': 0.02950848945012509,
 'E': 0.26762580040598083,
 'F': 0.144440892769927,
 'H': 0.02950848945012509,
 'G': 0.15393432485580816}
 
 #print(auth)
 {'A': 0.08751958702900821,
 'D': 0.12768284011810246,
 'B': 0.18704574169397806,
 'C': 0.3690360954887363,
 'E': 0.05936290157587555,
 'F': 0.10998993251842384,
 'H': 0.05936290157587562,
 'G': 0.0}

 

 

본 게시물은 Coursera의 Applied Social Network Analysis in Python(by Daniel Romero)를 통해 자습하며 작성한 게시물입니다.