Graph Theory in the Information Age

Graph Theory in the Information Age

그래프 이론은 그래프라고 하는 수학 구조를 공부하는 것을 말한다. 200년 역사 중 지난 10년 간 그래프 이론은 엄청난 변화를 겪었다. WWW의 웹 페이지들과 하이퍼링크들을 그래프 요소인 vertex와 edge로 보면 그래프 이론을 기반으로 웹 관련 알고리즘들을 만들 수 있었던 것이다. 훨씬 크고, 복잡하고, 방대한 그리고 실생활에 아주 밀접한 그래프를 다루는 'network science'가 등장했다. 네크워크의 많은 정보들을 다루려고 하다보니, 새로운 고민들이 생겼다. 이렇게 큰 네트워크는 구조를 어떻게 그려야하지? 어떻게 발전시키지? 그래프 작동의 기본적인 원리는 무엇일까? 이런 질문에 답하기 위해서 비록 충분하지는 않지만 먼저 기존 그래프 이론을 깊이 탐구하였다.

Random Graph Theory for General Degree Distributions

Erdos 와 Renyi 는 n개의 점 위에 정의된 그래프로서 두 점을 잇는 선분의 발생 확률을 p 로 주어 만들어지는 그래프 G(n, p) 를 랜덤 그래프의 모델로 선정하였다. 랜덤 그래프는 n 개의 점들 위에서 정해진 확률에 따라 선분이 한 개씩 늘어나면서 진화하는(evolve) 유기체로 이해될 수도 있다. 그렇다면 그래프가 진화하는 동안 어느 시점에 어떤 특정한 성질을 갖게 될까?

Random Subgraphs in Given Host Graph

많은 네트워크가 log n 이하의 작은 지름을 가지는데, 이를 small world phenomenon이라고 한다. 랜덤한 서브 그래프들을 다루는 방법 중 하나에는 여과하기 방법이 있다. 확률 threshold를 정하고 넘지 못하는 bond는 삭제하는 것이다. 이 방법으로 전염병의 확산 등을 알 수 있다.

PageRank and Local Partitioning

실제 세상을 표현한 그래프는 기본적으로 small world phenomenon이기 때문에 각 점들은 매우 짧은 path로 연결되어 있다. 1998년 Brin과 Page는 구글 웹 서치를 위해 PageRank라는 알고리즘을 고안했다. 페이지랭크는 더 중요한 페이지는 더 많은 사이트와 연결되었다는 사실을 이용하고 있다.

Network Games

아침마다 모든 사람들이 제일 빠르고 편한 길을 찾듯이, 게이머들은 기본적으로 이기기 위한 이기적인 플레이를 한다. 고전 그래프 이론은 게임의 입장에서 볼 수 도 있다. 예를 들어 인접한 점들은 다른 색을 가져야 하는 색칠하기 등이 있다.