개요

그래프 이론에 대해 살짝 공부한 것을 정리해본다. 사실 그래프 이론은 좀 두서없이 독학하는 경향이 있어 정리가 체계적이지 않다. 그래서 개념들을 조각 조각으로 정리해서 독자들한테는 그리 도움이 되지 않을지 모른다. 하지만 혹시나 그때 그때 필요한 개념을 익히기 위해 검색해서 들어온 독자라면 도움이 되기를 바라는 마음에서 정리해둔다. 또한 여기서 다루는 그래프 이론은 사회 현상을 그래프화 하여 컴퓨터 사이언스적인 접근을 하는 것이다.

그래프란?

아래와 같이 vertex와 edge로 구성된 요소. vertex/edge는 다른말로 노드/링크 라고도 말한다. 또한 방향성이 없는 Undirected 그래프와 방향성이 있는 Directed 그래프가 있다. 예를 들자면 페북은 Undirected 그래프로 친구를 나타낼 수 있고 트위터는 Follow 개념의 Directed 그래프로 나타낼 수 있다.

Node degree

정의는 한 vertex에 연결된 edge의 수이다.

평균 노드의 degree는 어떤 의미를 지닐까?
평균 노드 degree가 높다는 것은 서로 연결이 더 많다는 뜻이므로 서로 친구를 맺고있는 활성화 된 커뮤니티일 가능성이 높다.

왼쪽은 1/3 이고 오른쪽은 1이다.

또한 평균 노드 degree가 똑같이 2라고 하더라도 총 vertex의 수가 3개일때랑 30개일때 해석이 달라질 것이다.

WWW를 포함한 실제 세상의 평균 degree K는 아래와 같다. 즉 N값에 비해 Sparse한 특징을 지닌다.

k 분포

아래의 두 그래프 모두 k는 1.5이다. 따라서 평균 degree만으로 나타내지 않는 특징을 메트릭화 하여 보기 위해 k 분포 p(k) 아래와 같이 나타낼 수 있다.

Scale-Free network

Power Law 분포를 보이는 아래와 같은 degree당 p(k)는 아래와 같이 나타내지고 scale-free 네트워크라고도 말한다. 대다수의 노드들은 적은 degree를 가지고 극소수의 높은 degree를 가지는 노드를 일컬어 Hub라고 부른다.

예를 들어 SNS의 친구 분포라고 본다면 연예인등의 특수한 사람들은 부류는 Hub가 될 것이다.

Degree Distribution

그러면 Degree Distribution만으로 충분히 그래프를 분석할 수 있을까?

평균 Degree가 1이라고 하더라도 아래의 2가지 그래프와 같이 모양이 많이 다를수 있고 다른 특징들이 숨어있을 수 있다.

만약 G와 H가 사교 집단을 그래프화 했다면 내가 솔로인데 연애를 하기 위해서는 어떤 집단에 들어가야 확률이 더 높을까? 실제로 이부분에 대한 연구를 페이스북 등에서 활발하게 진행하고 있다. (페북의 싱글/연애 상태표시가 바뀐 사람들에 한해 연구를진행한 적이 있다.)

두 집단 중에서는 H가 확률이 더 높을 것이다.(건너 건너 소개를 받을 수 있으니까)

Clustering Coefficient

실제 바로 위의 개념이 Clustering Coefficient 개념으로 나타낼 수 있다.

내가 임의의 두 친구를 불렀을때 서로 알고있을 확률이고 이해하면 된다.

A 그래프는 1이고 B 그래프는 1/3이다.


[이미지 출처 : “Almagest ~ 가장 위대한 블로그 – 지식의 보고” 입니다.]

다른 예제로 아래의 경우 $C_v$는 1/2이다.

Clustering Coefficient처럼 아래와 같이 페북에서는 페북에서 서로 결혼한 사람과 그들의 중매 역할을 한 친구의 친구수에 대한 상관관계를 연구하고 있다.

페이스북의 matchmaker 그래프를 보면 각각의 소규모 집단에서는 서로 잘 알지만 이 소규모 집단 끼리는 약한 연결 혹은 연결이 안되어 있는 양상을 보인다.

Distance, Diameter, Average Path Length

  • Distance는 두 노드로 도달할 수 있는 Shortest path
  • Diameter는 구래프 내의 가장 큰 Distance 값
  • Average Path Length는 모든 노드 쌍의 Distance의 평균값

Erdos-Renyi Random Graph

수학자 에르되시가 고안한 개념으로 친구를 맺을 확률 P와 vertex의 수 n만 정하면 정규분포를 따르는 아래와 같은 그래프를 생성해준다.

예를 들어 n이 10이고 p가 1/6이면 아래와 같은 랜덤한 그래프들을 생성 할 수 있다.

Erdos-Renyi Random Graph의 아쉬운 점

위의 개념은 참 좋지만 현실은 k에 따른 p(k)가 정규 분포를 따르지 않는다는 것이다.

예를 들어 미국의 공항들의 연결을 그래프화 하면 아래의 왼쪽 그림과 같이 정규분포에 가깝지만 고속버스 터미널의 연결 등과 같은 아래의 오른쪽 그림과 같은 Power Law 분포에 더 가깝다. 또한 SNS 의 경우 Power Law에 더 가깝다는 연구결과가 많다.

일례로 MSN의 케이스의 경우도 아래와 같이 Power Law 분포에 더 가까운 것을 확인 할 수 있다.

케빈 베이컨 지수

6 Degree of Sepration의 재밌는 예제는 영화 배우 케빈 베이컨이 어떤 전세계 영화배우라도 잘 연결이 되는 특성이 있어서 케빈 베이컨 지수라는 것을 링크와 같이 제공해주는 사이트가 있다.

Erdos-Renyi Random Graph의 보완 모델

preferential 모델이라는 개념으로 뭐냐면 새로운 노드를 추가할 때(새로운 친구를 사귈때) 단순 확률 값(주사위를 굴리는 행위 정도로 생각하면 됨)으로만 정하는 것이 아니라 이미 친구가 꽤 있는 노드에 추가가 될 확률을 더 부여해주는 것이다. 좀 더 쉽게 말하면 이미 친구들에게 인기가 있는 친구가 새 친구를 생길 확률이 높은 현실세계의 개념을 반영한 것이다.(왜 대부분 중고등학교 때 내가 새로 친구 사귈 때 반에서 인기있는 친구를 사귀고 싶은 맘이 있지 않는가?)

에르되시의 수

특이하게 방랑을 하며 수많은 연구를 한 에르되시와 논문을 공저한 사람들을 그래프화 한 그림이 아래와 같다. 에르되시와 공저를 했으면 path가 1이고, 공저자와 공저를 했으면 path가 2 이런식이다.

Small World의 개념

켄자스에서 보스턴 까지 편지를 보낸다면 몇명의 친구수로 도달할 수 있을까? 연구에 따르면 여기에 걸리는 평균 path length가 6이라고 한다.

여기서 Small World를 얘기하는 이유는 다양한 Social Network들이 이 Small World의 특성을 지니기 때문이다.

Centrality

아래와 같은 그래프에서 누가 중심 노드라고 볼 수 있을까?

다양한 시각이 존재할 수 있다.

D라고 보는 사람은 Degree Centrality를 기준으로 꼽는 것이다. SNS에서 D가 친구가 제일 많고 글을 포스팅 했을때 가장 영향력이 좋기 때문에 D가 가장 중심이 아니냐는 시각이다.

F가 중심이라고 보는 시각은 Closeness Centrality이다. 친구간에 갈수 있는 path의 길이가 가장 짧기 때문이다 라는 것이다. 도시의 도심 같이 어느 지역에서가 가장 가깝게 도달할 수 있는 지역이 이런 F가 되지 않을까 싶다.

H가 가장 중요하다는 시각은 Bridge 역할을 하는 노드를 가장 중요하게 생각하는 것이다. 예를 들어 교통이라고 생각한다면 H라는 다리가 무너졌다고 생각하면 I와 J로 도달할 수 있는 방법이 없다는 시각이다. 개인적으로 되게 재밌다고 생각한다.

Degree Centrality

나한테 edge가 몇개나 달려있는지로 측정하는 Centrality로 너무 Naive한 감이 있다.

Closeness Centrality

수식의 의미는 노드 x와 다른 노드 간의 최단거리 경로의 합을 역수를 취해준 것이다. 즉 분모인 최단거리의 합이 값이 작을수록 Closeness Centrality 값은 커진다고 해석할 수 있다.

여러 노드들 중에 거리 개념으로 가장 중심에 위치하는 노드를 측정하는 지표이다.

보통 아래의 수식에서 $ N – 1 $을 곱하는 경우도 있다.

Betweeness Centrality

경유의 중심에 속하는지는 보는 기법이다. $ \sigma st $는 v가 아닌 s와 t노드간 존재하는 최단거리 경로의 합이고 $ \sigma st(v) $는 $ \sigma st $ 중에서 v를 경유하는 최단거리 경로의 합이다.

즉 교차로를 노드, 길을 링크로 본다면 가장 교통의 중심이 되는 없어서는 안될 교차로(노드)일 수록 Betweeness Centrality가 높다고 할 수 있다. 서울로 치면 양재 IC 정도 되지 않을까. 양재 IC가 제 역할을 못한다고 가정하면 교통이 마비 될 것이다.

$ C_b(v) = \sum_{s \ne t, s \ne v, v \ne t} \frac {\sigma st(v)}{\sigma {st}}$

PageRank 개념 익히기

그래프를 통해 PageRank를 익히면 생각보다 개념이 간단하다. (또한 개인적으로 개발자를 하면서 PageRank 알고리즘을 한번쯤은 제대로 익혀보고 싶었다. 기회가 되면 논문을 읽고 분석글을 한번 올리겠다.)

실제 지금 서비스 되는 페이지 랭크 알고리즘은 다양한 어뷰징을 방지 하기 위해 더 복잡하다고 들었지만 기본 아이디어는 아래와 같다.

페이지랭크에서 화살표의 의미는 내가 투표를 받았다는 추상화의 개념으로 점수를 계산한다고 이해해도 무방하다. 사실 투표의 의미는 다른 사이트에서 내 사이트를 링크로 걸었다는 의미이다.

자 시작해보자. 아래의 왼쪽과 같이 투표가 오고 갔으면 위에서 얘기 했다 싶이 내가 투표를 얼마나 받았는지를 계산하는 과정이다.

행렬 M에서 행은 yahoo, amazon, microsoft의 의미이고 열은 누구로 부터 투표를 얼마나 받았는지의 의미이다.

화살표의 가중치 값을 정하는 기준은 내가 화살표를 N개 다른 노드로 보냈다면 가중치 값은 1/N씩 가진다. 예를 들어 Amazon의 경우 투표를 Yahoo에 1표, Mircrosoft에 1표 행사했으니 2개의 화살표이므로 1/2, 1/2로 가중치 값을 계산한다. 반면에 microsoft는 amazon에 1표만 행사했으므로 가중치 값은 1이다.

이렇게 계산된 행렬 M을 전체 사이트 수로 나눈 1/3값씩으로 곱해준다. 그러면 1/3, 1/2, 1/6의 값을 가지게 된다.

위에서 나온 값을 다시 동일한 행렬 M으로 곱해준다.

이렇게 반복해서 곱해주면 특정 값으로 수렴한다. 이게 페이지 랭크 알고리즘으로써 실제 검색으로써의 의미는 무한에 가까운 시간동안에 인터넷에 존재하는 링크를 사람들이 계속해서 서핑을 한다면 각각 사이트의 중요도는 어느순간 위의 알고리즘에 의해 수렴한다는 것이다.

연구에 의하면 약 50 Iteration정도면 수렴하는 것으로 얘기하고 있다.

PageRank의 문제점, “dead-end”

현재의 구글 페이지 랭크 알고리즘이 이 문제를 가지고 있다는 것은 아니고 위에 설명한 알고리즘의 한계점은 아래와 같이 Outlink가 존재하지 않는 Microsoft와 같은 사이트가 있다면 아래와 같이 특정 사이트 말고는 모드 가중치가 0이 되어버리는 괴현상이 발생한다.


“dead-end” 해결책

  • Random Surfer 모델 : Random한 확률로 사이트를 연속적으로 링크를 타고 다닌다.
  • 개선된 모델 : Random Surfing을 하다가 갑자기 지루해져 전혀 다른 사이트로 jump 해버린다.

Jaccard’s coefficient

페북으로 치자면 x와 y의 친구가 맺어진 사람들의 합집합 중에 x와 y가 둘다 친구가 맺어진 사람의 수로 나누는 것이다.

Adamic / Adar

수식의 의미는 x와 y가 동시에 아는 친구 z에 대해 z자체가 친구가 적으면 적을수록 더 높은 가중치를 주겠다는 의미이다.

예를 들어 A와 C의 공통된 친구중에 B는 원체 친구가 많은 사람으로 중요도가 낮지만 E는 전체 친구가 A와 C밖에 없으니 굉장히 Exclusive 하다고 말할 수 있다.

Katz Centrality

Katz Centrality의 수식은 아래와 같다. 의미는 최단경로만 의미가 있는것이 아니라 모든 가능한 경로를 다 고려해서 Centrality를 구해야 되는것이 아니냐는 것이다.

$ a_{ji} $는 경로가 존재하면 1 아니면 0이라고 한다. 즉 중요한 값은 $ \alpha ^k $이다. 실제로 수식을 보면 최단거리가 아닌 우회경로를 다 계산에 반영하긴 하지만 우회경로가 거리가 멀면 제곱에 의해 사실 미미한 영향력을 가지게 된다.

예제를 통해 배워보자.

$ \alpha = 0.5 $라고 가정해보자.

또한 우리는 John의 Centrality를 구하는 것으로 생각해보자.

$ John, Bob = (0.5)^1$
$ John, Jane = (0.5)^1$
$ John, Jose = (0.5)^2$
$ John, Agneta = (0.5)^3$
$ John, Jose= (0.5)^4, through Diego $

출처 : 위키피디아

다양한 그래프 알고리즘의 성능 측정

개략적으로 보면 Adamic / Adar, Katz 등이 성능이 준수한 편이다. 볼드체가 좋은 성능을 의미한다.

재밌는 그래프 관련 논문