구심점(Centrality)의 정의란 네트워크에서 어떤 노드가 중요한지 정의하는것이라 할 수 있다.
3.1.1 중심도(Degree Centrality)의 정의
실생활의 상호작용에서, 다양한 인맥을 가진 사람은 인간관계에서 중요한 사람으로 생각된다.
중심도는 이와같은 생각을 측정하는 개념이다.
중심도 측정에서 높은 순위를 가지는 노드는 많은 연결을 가졌다는 의미이다.
비방향성 그래프에서 노드 Vi에 해당하는 중심도 Cd는 다음과 같이 표현한다
방향성 그래프에서, in-degree와 out-degree를 사용할수 있으며, 중심도 값을 조합해서 사용하는것도 가능하다:
순서대로 수식 3.2,3,4
in degree상황(들어오는 엣지)에서, 중심도 측정을 수행한다는 것은 해당 노드가 얼마나 명성이 있는 사람인지 알수 있는 부분이다.
out degree 상황에서는, 해당 노드가 사교적인 사람임을 알려준다.
in과 out이 복합된 상황에서는, 엣지의 방향성은 무시하게 된다.
사실, 엣지의 방향성이 제거되었을때, 위의 수식 3.4는 비방향성 그래프의 측정 방식과 같은 3.1과 같은 성격을 지니게 된다.
하지만 이때 측정된 중심도는 네트워크 전체에서 사용할수 있는 중심값은 아니다.
이 문제를 극복하기 위해서, 측정된 중심도를 정규화 시킬 필요가 있다.
단순 수치 정규화 방법은 최대 수치 정규화 방법과 동일하게 진행된다,
최대치의 수치 역시 정규화 시킬수 있는데, 수식은 다음과 같다
그림 3.1 : 그림 3.1은 단순 그래프 상황을 보여준다.
이 그래프에서, 노드 V1에 해당하는 중심도는 Cd (V1) = D1 = 8 이며 , 모든 다른 노드는 Cd (Vj) = Dj = 1이다 (j는 1이 아닌상황에서, 노드 V1이 중심에 있는 노드이기 때문에 8이고 나머지는 1이다).
3.1.2 고유백터 구심점 (Eigenvector Centrality)
중심도에서, 많은 연결을 가진 노드는 더 많은 중요성을 가진다.
하지만, 실상황에서, 친구가 많다는게 꼭 중요한 사람 이라고 생각할순 없다: 더 중요한 친구들을 갖는게 더 강한 신호가 될수있다.
고유백터 구심점은 이웃들을 경합시키는 과정을 통해 구심도를 정규화 시키게 된다(방향성 그래프에서는 들어오는 방향의 엣지를 대상으로 시행한다).
이때 방향/비방향 모두 사용가능한 상황이다.
이웃들을 살펴보면, 인접행렬 a에 대한 그래프 역시 활용이 가능하다.
Ce(Vi)는 노드 Vi에 대한 고유백터 구심점을 나타낸다.
노드 Vi에 대한 구심정이 Vi의 이웃들중 중심이 되도록 만들려 한다면.
한가지 가정으로 중심도가 균형잡혀있다고 가정한다
람다가 고정되어 일정하다고 할때.
노드 V1부터 n까지의 구심점 백터가 Ce^T가 모든 노드의 중심 벡터로 수식 3.8과 같이 작성이 가능하다.
행렬은 많은 고유값을 가질수 있기 때문에, 많은 상응하는 고유벡터 역시 가질수 있다.
그러므로, 이런 질문이 떠오를것이다: 어떤 고유값과 고유벡터의 쌍을 선택 해야할까?, 우리는 보통 이럴때 편리한 비교를 위해 양수의 중앙값을 선택하는 경향이 있다.
그러므로, 이번에도 양수를 선택하는 방향으로 진행 할것이다.
그리고 이때 우린 Perron-Frobenius 정리 (theorem) 를 짚고 넘어가야 한다.
정리 3.1 Perron-Frobenius Theorem.
Perron-Frobenius 고유값 (람다)최대치가 양수로 존재한다, 고유값 (람다)가 A가 최대치일때 다른 고유값은 max값에 못미친다.
더 나아가서, Vi와 같은 고유값 (ramda)max 를 상응하는 고유백터 v = (v1,v2..vn)값이 존재한다.
그러므로, 양수의 중심점을 가지기 위해서, a의 고유값을 계산하고 그중 가장 최대값을 계산하면된다.
이때 상응하는 고유 벡터는 Ce값이다.
Perron-Frobenius 정리의 기반해서, 모든 Ce의 컴포넌트는 양수이다, 그리고 이 벡터는 그래프의 고유벡터 중심도에 상응하게된다.
그림 3.2 : 고유백터 중앙화 예제.
예시 3.2. 그림 3.2의 a에서 보이는 그래프를 보면, 이 그림은 그림 3.9를 기반으로 만들어졋다,이것은
따라서 고유값은
를 따라간다.
최대 고유값인
를 선택해서 이에 상응하는 고유백터값을 계산할수 있다.
Ce의 벡터에 표준 1이 있다고 가정할때, 솔루션은 다음과 같다
예시 3.3. 그림 3.2(b)에서 볼수 있는 그래프를 인접 행렬로 표시하면 다음과 같은 상황으로 알수있다.
A에 대한 고유값은 다음과 같다 (-1:74;-1:27; 0:00;+0:33;+2:68).
고유백터 중심도에서, 가장큰 고유값인 2.68이 선택되었다.
대응하는 고유백터는 고유백터 중심도에 기반을 두고있는데,현제 노드 V2가 가장 중심 노드임을 알수 있다.
3.1.3 Katz Centrality 이론
중심백터 중심도의 가장큰 문제는 방향성 그래프에서 발생하게 된다 (Exercises 1에서 해당 문제를 알수있다)
중심도는 밖으로 나가는 엣지(outgoing) 와 노드에 방향성이 있는 비순환 그래프에서, 노드가 많은 엣지를 연결할수 있어도 중심도가 0이 될수 있다.
이상황에서, 중심도에 편향치를 더해서 이 문제를 해결 할 수 있다.
치우침을 표시할때 (베타) 로 표기하고, 이 값은 해당 노드가 어떤 위치에 있던지 추가해서 계산하게 된다(네트워크 토폴로지(형태)에 관계없이 더해준다)
그 결과의 중심성 척도는 Katz centralit 라고 부르고 고유백터 중심도와 유사한 성격을 가진다, 그리고 이건 일정한 (알파)값에 의에 조정된다
우린 방정식 3.19를 벡터 형태로 다시 작성할수 있는데, 여기서 1은 모든 1의 벡터가 된다.
여기서 행렬을 조사하면서부터 , 모든 (알파) 값이 사용되는것은 아니다.
(알파)가 0일때, 고유 백터 중심도 부분이 제거되며 모든 노드는 동일값으로 (베타)값을 취하게된다.
하지만, (알파)가 큰값을 가지게 되면, (베타)의 효과가 감소한다, 또한 (I - (알파)A^T ) = 0의 상황이라면, 행렬 (I - (알파)A^T ) = 0 가 역행렬을 가지수 없고 중심도가 나뉘게 된다.
(알파) = 1/(람다)의 상황에서 (I - (알파)A^T )가 0이 된다, 이때 (람다)는 고유값 A^T보다 큰값을 가지게 된다.
연습해보자, 중앙값이 알맞게 계산되도록 (알파) < 1/(람다)가 선택 되었다.
예시 3.4.
그림 3.3에서 보이는 그래프를 인접 행렬로 나타내면 다음과 같다.
고유값 A는 다음과 같다 (-1.68,-1.0,-1.0,+0.35,+3.32).
이중 가장큰 고유값은 A는 3.32로 (람다) 가 된다.
이떄 (알파)가 0.25< 1/(람다) 이며 (베타)는 0.2라고 가정해보자
그렇다면 Katz centralities 는 다음과 같은데
그러므로, 노드 V2와 V3가 가장 높은 Katz centralities 를 가진다고 볼수 있다.
3.1.4 페이지 순위 (PageRank) 의 정의
고유백터 중심도에서와 비슷하게 Katz centrality 에서도 몇몇 문제가 있다.
문제는 바로 방향성 그래프에서 발생하게 되는데, 노드가 높은 중심도를 가지게 되면,모든 out link를 따라서 중심도가 통과하게 된다는것이다.
이 현상은 바람직한 현상이 아니다, 왜냐면 모든 사람들이 유명인을 아는것이 아니기 때문이다.
이 문제를 줄이기 위해서, outdegree의 갯수를 기준으로 중심도를 나누어서 연결된 이웃이 높은 중심도를 가진 노드로 부터 값을 나눠 받는것이다.
이 방정식은 d^out(j) 가 0이 아닌 경우에만 성립한다.
그러므로, 모든 노드가 양의 out-degree를 가질때 (d^out (j) >0)^3 에서, 방정식 3.24는 행렬 형태로 재구성 되었는데
중심도 측정은 페이지순위 중심도 측정으로 알려져 있으며 구글에서 검색결과에 대한 순위 배치에 이용하는 기능이다.
웹페이지와 링크는 엄청나게 거대한 웹 그래프를 의미한다고 볼수있다.
페이지 순위는 웹그래프 상에서 노드의 중심도를 측정한다고 볼수 있다.
사용자가 구글에 질의를 날리면, 질의에 맞는 내용을 가진 높은 순위의 웹페이지를 상위로 올려서 보여주는 것이다.
Katz centrality와 비슷하게, 연습해보면 , (알파) < 1/(람다) 가 선택되었다면, (람다)는 고유값 A^T*D^-1 에서 가장큰 값이 된다.
비 방향성 그래프에서, 가장큰 A^T*D^-1의 고유값은 (람다)=1 이다, 그러므로 (알파) <1 이 성립한다.
예시 3.5. 그림 3.4에서 보이는 그래프를 활용해 인접 행렬을 제작하면 다음과 같다
이때 , 페이지 랭크값은 다음과 같이 표기되며 , 노드 V1과 V3가 가장 높은 페이지 랭크 값을 지님을 확인 할 수 있다.
3.1.5 Betweenness Centrality의 정의.
다른 방식으로 중심도를 확인하는 방법은 얼마나 중요한 노드들이 서로 연결되어 있는지 보는것이다.
한가지 방법으로, 노드 Vi에 대해, Vi를 지나는 노드간 가장 짧은 최단 경로를 구하는 방법이 있는데, (시그마)(st)를 노드 s에서 t까지 가는 가장 짧은 경로라고 할때(우린 이걸 information pathways 라고 하자), 또한 (시그마)(st)(Vi) 를 s에서 출발해 Vi를 지나 t까지 가는 최단 경로라고 하자.
다른 의미로, 노드 Vi 가 노드쌍 s t에서 얼마나 높은 중심되를 가지는지 확인하는 것이다.
그리고 이 상황을 betweenness centrality 라고 하자.
Betweenness centrality 측정을 위해서는 네트워크에 대한 정규화 과정이 필요하다.
betweenness centrality를 정규화하기 위해서는,최대값을 계산할 필요가 있다.
(뒤집어진 A) (s, t),s =/ t =/ vi, st(vi) st = 1.
간에 노드 Vi의 최대값을 취한다, 그리고 이를 식으로 표현하면 다음과 같다
그러므로, 최대값은 다음식으로 표현된다
중간값은 최대값을 정규화 시킴으로서 나눌수 있는데 다음과 같이 표현 가능하다.
Betweenness 계산하기.
betweenness centrality (방정식 3.29)에서 ,모든 노드의 쌍에 대해서 betweenness 값을 계산할수 있다.
다익스트라 같은 알고리즘이 사용되는 경우, 모든 노드를 대상으로 수행되야 한다, 왜냐하면 다익스트라 알고리즘은 하나의 노드에서 다른 노드로 가는 가장 최소거리를 계산하기 때문이다.
따라서, 모든 노드의 쌍에 대한 최소 경로 산정을 위해서, 다익스트라 알고리즘의 수행 횟수는 |V|-1 로 전체 노드 개수 -1 이다( 중심성이 계산되는 노드는 제외한 수치).
따라서 Brandes 알고리즘 처럼 조금더 효과적인 알고리즘이 설계되었다.
Brandes 알고리즘에 관심있는 독자들은 마지막 챕터를 참고할수 있다.
그림 3.5 : 중간 중심도(Betweenness Centrality) 예시.
예시 3.6.
그림 3.1을 보자, (정규화에서) 노드쌍 s,t의 경로에서 V1에 대한 중간 중심도를 보여주고 있다.
비슷하게, 이 그래프에서의 다른 모든 노드에 대한 중간 중심도는 0이 된다.
예시 3.7.
그림 3.5는 샘플 그래프를 표현하고 있다.
이 그래프에서, 노드 V1에 대한 중간 중심도는 0이다, 왜냐면 이것을 통하는 최소 비용 경로가 없기 때문이다.
다른 노드에 대해서, 중심도 계산에서 2를 곱해야 하는데 이유는 비 방향성 그래프이기 때문이다.
3.1.6 근접 접근성 중심도.
근접 접근성 중심도에서, 직관이란 많은 중심노드와, 더 빠르게 다른 노드에 도달할수 있다는 것이다.
공식적으로 이 노드는 다른 노드에 비해 더 작은 최소 경로를 지녀야 한다.
근접 접근 중심도의 정의는 (sik37.png)로 정의되며 다른 노드에 대한 노드 Vi의 평균 최단 경로 길이가 된다.
평균 최단 경로 길이가 작아질수록 노드의 중심성이 높아진다.
예시 3.8.
그림 3.5를 보면, 근접 중심도는 다음과 같다:
그러므로, 노드 v2 는 가장 높은 근접 중심도를 지님을 알수있다.
지금까지 논의돈 중심성 조치들은 중심 노드가 무엇인지에 대해 서로 다른 견해를 가지고 있다
그러므로, 중심 노드는 다른 측정 방법에 비해 중요하지 않다고 여겨질수 있다
예시 3.9.
그림 3.6의 그래프를 살펴보자.
이 그래프 상에서, 우린 수치를 기반으로 상위 3개 노드에 대한 중심도를 구했다,고유백터,katz,페이지 순위, 중간도, 근접 중심도이다.
이 노드는 테이블 3.1에서 확인할수 있다.
테이블에서 볼수 있듯이, 처음 4개 측정값에서 중심 노드간에 높은 수치의 유사성이 존재한다, 이를 위해 고유백터 수치를 활용하는데 : 중심도, 고유백터 중심도, katz 중심도, 페이지 순위 등을 활용한다.
중간 중심도의 생성은 인접 중심도와 비슷한 결과를 보이게 되는데, 이유는 두가지 모두 최소 거리를 활용해 중심 노드를 찾기 때문이다.
그림 3.6: 모든 중심도 측정의 예시.
Table 3.1 표3.1 : 중심도 측정방법의 비교
3.1.7 그룹 중심도의 정의.
지금까지 정의된 중심도 측정은 각 각의 개별 노드에 대해서 측정했다.
이 측정은 그룹 노드들에 의해 정규화 될수 있다
이장에서는,노드 그룹에 대해 중심성, 근접 중심, 중간 중심성이 어떻게 정규화 될수 있는지에 대해서 논하게 된다.
S를 측정된 중심도라고 생각해 보자.
V - S 는 그룹에 없는 노드 집합을 의미한다.
Group Degree Centrality
그룹 중심도(Group Degree Centrality)의 정의.
드룹 중심도는 그룹 맴버와 연결된 그룹 외부의 노드의 갯수에 의해 정의된다.
마지막으로,중심도와 비슷하게, 방향성 그래프에서 들어오고/나가는 연결성을 정의할수 있다.
이 값역시 정규화가 가능하다.
최고의 상황에서는, 그룹의 맴버가 모두 다른 맴버들과 연결된다.
그러므로, 최대값은 다음과 같이 정의된다 (sik40.png).
따라서 그룹 중심도 값을 |V -S| 로 나누면 정규화가 가능하다.
Group Betweenness Centrality
그룹 중간 중심도.
그룹 중간 중심도와 비슷하게, 그룹 중간 중심도를
로 정의하고 S의 멤버를 통과하는 s와 t사이의 최단 경로 수를 나타낸다.
가장 최선의 방법은, 모든s와 t사이의 최단 경로는 S의 멤버를 통과하므로 ,
의 최대값이 된다.
중간 중심도와 비슷하게, 최대 값을 나눠줌으로써 그룹 중간 중심도 역시 정규화 시킬수 있다.
Group Closeness Centrality
그룹 근접 중심도의 정의(Group Closeness Centrality).
그룹에 대한 근접 중심도는 다음과 같이 정의될수 있는데
과
을 보면 그룹 S와 비 맴버 사이의 최단거리를 나타낸다.
한가지 방법으로는 그룹 S와 가까이 있는 노드 Vj를 찾는것인데:
예시 3.10. 그림 3.7의 그래프를 살펴보자.
그룹 S를 v2,v3라고 하자.
이때 그룹 중심도 S를 구하면 다음과 같음을 알수 있는데
그림 3.7 : 그룹 중심도 예시.
해당 멤버들은 다른 세 멤버들이 {v1, v4, v5} 과 연결되어 있기 때문에.
정규화 값은 3/|V - S| = 1에 의해 정규화 값은 1이된다.
2(3 2)상황에서 v-s 의 최단 경로 그룹 중간 중심도는 6이며, 경로는 그룹 S의 맴버를 통과해서 지나간다.
6/2(|V-S|))=1 상황에서 정규화된 그룹 중간값은 1이 된다.
마지막으로 그룹 중간값은 어떤 멤버이던 V - S 이 그룹 S의 멤버와 직접 연결되어 있을때 거리를 1이라 한다- 이때 비그룹 맴버에서 그룹 S의 맴버까지의 거리는 최소 비용으로 연결되었다고 가정해야 한다-.
댓글 없음:
댓글 쓰기