unweighted graph에서 edge number / theoretical maximum edge number 로 정의할 수 있는 density가 큰 부분을 찾는 방법을 살펴 보자. 즉, 그래프에서 점들 사이에 선분이 많이 존재하는 곳을 찾는 작업. 이와 같은 류의 문제는 아직 deterministic한 알고리즘이 없어 보이며, 모든 경우에 적용할 수 있는 일반적 해법은 없고 문제에 따라 적절한 방법이 조금씩 다른 것으로 보인다. 이 글은 MCODE 라는 Cytoscape 플러그인에서 사용하는 방법을 기반으로 작성한다1.
이 방법은 우선 각 노드에 점수를 준다. 그 후, 점수가 높은 노드에서 시작해서 선택하는 노드를 퍼트려 나가는 것이다. 이 때 중요한 점은, 각 노드의 점수는 그 노드가 얼마나 dense한 곳에 '속해' 있는가를 반영하게 한다는 것이다. 이것을 원논문에서는 k-core 라고 표현을 하였다. 주어진 그래프가 k-core 라는 것은 그래프에 있는 모든 노드가 k-개의 edge를 갖는다는 것을 의미한다. 노드에 부여되는 점수는 그 노드에 연결된 노드들의 subgraph 가 포함하는 k-core에 대한 최대 k 를 반영한다. 그림으로 보자.
A는 3-core에 연결되어 있다. B는 2-core에 연결되어 있다. A가 B보다 dense한 곳에 속해 있으므로 A에 더 높은 값을 갖도록 scoring 할 수 있는 방법을 생각하자.
위의 왼쪽 그림을 보자. 그림에서 점 A 에 연결된 노드들을 살펴 보자. 즉, 푸른색 점들. 이 점들의 연결선을 보면 붉은색으로 연결된 점들 4개는모두 3개의 edge 가 연결되어 있는 것을 알 수 있다 (A에서 연결된 실선은 제외). 따라서 A에 연결된 그래프는 3-core를 포함하고 있다. 반면 오른쪽 그림의 점 B 에 연결된 노드로 이루어진 subgraph 는 2-core 인 것을 알 수 있다. 즉, B 에 연결된 node들은 4개의 붉은 노드가 2개의 edge 에 연결되는 것으로부터 2-core 인 것을 알 수 있다.
노드에 부여되는 점수는, 그 노드에 연결된 subgraph 에 포함되어 있는 k-core 중 가장 큰 k 에 의존하게 된다. 한 노드에 연결된 subgraph에 높은 core의 그래프가 포함되어 있다는 것은 그 노드가 보다 dense 한 그래프에 '속해' 있다는 것을 의미한다. 위의 그림에서 왼쪽의 A에 연결된 subgraph는 3-core를 포함하고, 오른쪽의 B에 연결된 subgraph는 2-core를 포함하고 있다. 따라서 점수를 준다면 A에 더 높은 점수를 주는 것이 합당할 것이다. 이번에는 다음과 같은 경우를 생각해 보자.
위에서 B와 C는 모두 2-core에 속해 있다. 이 경우 만약 scoring을 k-core만을 고려한다면 B와 C 가 같은 점수를 받게 될텐데, 우리는 위의 경우에 C에 좀 더 높은 점수를 주고 싶다. 왜냐 하면, 비록 B,C 모두 2-core에 포함되어 있으나 그 2-core subgraph 자체의 density가 C에서 더 높기 때문이다. 따라서 graph의 각 노드에 대한 score는 그 노드가 연결된 subgraph에 대해서
1. maximum number of k where k-core is in the subgraph,
2. density of the subgraph,
를 모두 고려하는 것이 합당해 보인다. 이 때 그래프의 density란 다음과 같이 계산한다.
즉, graph G는 노드(vertex)의 집합 V와 edge(node pair)의 집합 E로 되어 있다고 할 때, G의 density란 가능한 모든 edge의 수 중에 얼마나 많은 edge가 실제로 존재하는가를 의미한다고 간주한다2. 그래서 최종적으로 노드 n 에 주어지는 점수는 n에 직접적으로 연결된 subgraph에 속해 있는 k-core 중 최대 k와 그 k-core graph의 density 의 곱으로 한다.
위와 같이 각 노드에 점수를 부여한 이후 다음의 절차에 따라 dense한 영역을 찾아 낸다. 우선 가장 score가 높은 노드를 선택한다. 그 노드에서부터 이제 차차 다른 노드를 선택해 나갈 것인데, 다음의 기준을 사용한다. 즉, 현재 노드에 부여된 점수*d 보다 큰 점수를 갖는 노드들을 선택한다. 이렇게 2차로 선택된 노드들에 대하여 같은 절차를 반복한다. 더이상 추가가 되는 노드가 없을 때까지 반복한다. 이렇게 하여 하나의 subgraph 가 완성되면, 그것을 제외한 node 중 score가 가장 높은 노드에서부터 위의 절차를 다시 반복한다. 전체 graph 에 대하여 위 절차를 반복한다.
위 방법의 의미는 이러하다. 위에서 설명한 scoring scheme에 따르면 dense한 지역에 속해있을수록 노드는 높은 점수를 부여받는다. 따라서 우선 전체 그래프 중 점수가 가장 높은 노드가 다른 노드들보다 dense한 지역에 있는 것이므로 그 노드에서부터 시작하여 다른 노드들을 추가해 나간다. 현 단계까지 추가된 노드 각각에 대하여, 그 노드에 연결되어 있는 노드들을 살펴 보면서 그것을 현재의 dense subgraph에 추가할 것인가 말 것인가를 결정하게 되는데, 만약 현재 노드보다 더 점수가 높았거나 혹은 현재 노드 점수의, 예를 들면 0.95만큼의 점수를 갖고 있으면 그 노드를 현재의 dense subgraph에 추가하는 것이다. 이것이 의미하는 것은 우선 가장 dense 한 곳에 있는 노드에서부터 시작하여 차례로 노드를 선택해 나가되, 노드의 선택의 기준으로 그것이 어느 정도 dense 한 지역에 속해 있었는가를 사용하겠다는 것이다. 새로 선택할 노드들은 그것에 연결되어 있는 노드 중 가장 최근에 선택된 노드(C)의 점수보다 높으면 물론 좋은데, 그렇지 않더라도 적어도 C가 속해 있던 영역의 density에 비해 95% 정도 되면 충분히 dense한 영역에 있다고 가정하고 그것을 선택하는 것이다. 물론 0.95로 할 것인가, 아니면 0.99로 할 것인가에 따라 만들어지는 dense subgraph 는 다른 모습을 가질 것이다. 0.95로 할 때보다 0.99로 할 때 보다 dense하지만 작은 subgraph가 찾아지겠지.
전체적인 알고리즘에 대한 설명은 전반적으로 끝이 났다. 이제 좀 더 구체적으로 k-core를 찾는 방법을 생각해 보자. 주어진 graph G=(V, E)에 k-core subgraph g = (v, e)가 있다는 것은 g의 모든 노드 v 가 k개 이상의 edge를 갖는다는 것을 의미한다. 따라서 G에서 k-core를 찾기 위해서는 다음과 같이 한다.
1. G의 모든 노드 v에 대하여 만약 v가 k개 이하의 edge를 가지면 v를 제거한다.
2. 만약 1단계에서 제거된 노드가 없으면 k-core를 찾은 것이다. 만약 1단계에서 제거된 노드가 있으면 1단계로 간다. 만약 모든 노드가 제거되었으면 k-core가 없는 것으므로 끝낸다.
그림으로 보자면 다음과 같다.
3-core를 찾는 과정. edge 수가 3보다 작은 노드를 지워 나간다. 최종적으로 오른쪽 그래프가 얻어진다.
4-core를 찾는 과정. 최종적으로는 모든 node가 지워진다. 따라서 위 그래프에는 최대 3-core가 존재하게 된다.
그렇다면 주어진 graph G에 있는 k-core 중 최대의 k 를 찾으려면 어떻게 해야할까? 별다른 방법이 없다. 2-core부터 시작해서 3-core, 4-core, ... 를 쭉 찾아 나가는 수밖에. 그렇기 때문에 maximum k 를 찾는 문제는 O(n3)이 된다. 여기서 약간 짱구를 굴려 보자. 어차피 G에 있는 k-core 중 k의 최대값은 G에 있는 노드 수 - 1 일 수밖에 없다. 최소(2-core)와 최대( (|V|-1)-core) 값을 알고 있으므로 binary search 를 통해 찾는 것이다. 이렇게 하면 그나마 O(n2log(n))으로 계산시간을 줄일 수 있다.
글이 좀 길어져서 구현한 것은 별도의 글로 작성한다. 그 글에 대해 잠깐 예고를 하면, 코드는 C++로 작성되어 linux에서 gcc로 compile 되어있다. 이 글에 맞게끔 수정하려면 약간 시간이 걸릴듯 하다. 원래 나는 graph를 STL의 multimap 을 이용하여 표현하곤 하는데 속도 문제 때문에 double** 로 adjacency matrix를 표현하는 방식으로 다시 구현하였다. k-core를 구하는 부분이 살짝 복잡한데 코드 자체에 주석이 거의 없기 때문에 그것에 대한 약간의 작업이 필요하다.
다른 많은 dense subgraph 를 찾는 알고리즘들보다는 덜하지만 MCODE 에서 제안한 알고리즘 역시 node 수가
많아지면 속도가 급격히 떨어진다. 노드 수가 겨우 수백/수천 개만 되어도 꽤 긴 시간 - 짧게는 몇 분 정도 - 이 걸리기 때문에
사용하기 어렵다. 따라서 다음 번에는 IBM 연구소에서 발표한 논문 (discovering large dense
subgraphs in massive graphs)에 있는 알고리즘을 구현해 보자. 위에서 B와 C는 모두 2-core에 속해 있다. 이 경우 만약 scoring을 k-core만을 고려한다면 B와 C 가 같은 점수를 받게 될텐데, 우리는 위의 경우에 C에 좀 더 높은 점수를 주고 싶다. 왜냐 하면, 비록 B,C 모두 2-core에 포함되어 있으나 그 2-core subgraph 자체의 density가 C에서 더 높기 때문이다. 따라서 graph의 각 노드에 대한 score는 그 노드가 연결된 subgraph에 대해서
1. maximum number of k where k-core is in the subgraph,
2. density of the subgraph,
를 모두 고려하는 것이 합당해 보인다. 이 때 그래프의 density란 다음과 같이 계산한다.
즉, graph G는 노드(vertex)의 집합 V와 edge(node pair)의 집합 E로 되어 있다고 할 때, G의 density란 가능한 모든 edge의 수 중에 얼마나 많은 edge가 실제로 존재하는가를 의미한다고 간주한다2. 그래서 최종적으로 노드 n 에 주어지는 점수는 n에 직접적으로 연결된 subgraph에 속해 있는 k-core 중 최대 k와 그 k-core graph의 density 의 곱으로 한다.
위와 같이 각 노드에 점수를 부여한 이후 다음의 절차에 따라 dense한 영역을 찾아 낸다. 우선 가장 score가 높은 노드를 선택한다. 그 노드에서부터 이제 차차 다른 노드를 선택해 나갈 것인데, 다음의 기준을 사용한다. 즉, 현재 노드에 부여된 점수*d 보다 큰 점수를 갖는 노드들을 선택한다. 이렇게 2차로 선택된 노드들에 대하여 같은 절차를 반복한다. 더이상 추가가 되는 노드가 없을 때까지 반복한다. 이렇게 하여 하나의 subgraph 가 완성되면, 그것을 제외한 node 중 score가 가장 높은 노드에서부터 위의 절차를 다시 반복한다. 전체 graph 에 대하여 위 절차를 반복한다.
위 방법의 의미는 이러하다. 위에서 설명한 scoring scheme에 따르면 dense한 지역에 속해있을수록 노드는 높은 점수를 부여받는다. 따라서 우선 전체 그래프 중 점수가 가장 높은 노드가 다른 노드들보다 dense한 지역에 있는 것이므로 그 노드에서부터 시작하여 다른 노드들을 추가해 나간다. 현 단계까지 추가된 노드 각각에 대하여, 그 노드에 연결되어 있는 노드들을 살펴 보면서 그것을 현재의 dense subgraph에 추가할 것인가 말 것인가를 결정하게 되는데, 만약 현재 노드보다 더 점수가 높았거나 혹은 현재 노드 점수의, 예를 들면 0.95만큼의 점수를 갖고 있으면 그 노드를 현재의 dense subgraph에 추가하는 것이다. 이것이 의미하는 것은 우선 가장 dense 한 곳에 있는 노드에서부터 시작하여 차례로 노드를 선택해 나가되, 노드의 선택의 기준으로 그것이 어느 정도 dense 한 지역에 속해 있었는가를 사용하겠다는 것이다. 새로 선택할 노드들은 그것에 연결되어 있는 노드 중 가장 최근에 선택된 노드(C)의 점수보다 높으면 물론 좋은데, 그렇지 않더라도 적어도 C가 속해 있던 영역의 density에 비해 95% 정도 되면 충분히 dense한 영역에 있다고 가정하고 그것을 선택하는 것이다. 물론 0.95로 할 것인가, 아니면 0.99로 할 것인가에 따라 만들어지는 dense subgraph 는 다른 모습을 가질 것이다. 0.95로 할 때보다 0.99로 할 때 보다 dense하지만 작은 subgraph가 찾아지겠지.
전체적인 알고리즘에 대한 설명은 전반적으로 끝이 났다. 이제 좀 더 구체적으로 k-core를 찾는 방법을 생각해 보자. 주어진 graph G=(V, E)에 k-core subgraph g = (v, e)가 있다는 것은 g의 모든 노드 v 가 k개 이상의 edge를 갖는다는 것을 의미한다. 따라서 G에서 k-core를 찾기 위해서는 다음과 같이 한다.
1. G의 모든 노드 v에 대하여 만약 v가 k개 이하의 edge를 가지면 v를 제거한다.
2. 만약 1단계에서 제거된 노드가 없으면 k-core를 찾은 것이다. 만약 1단계에서 제거된 노드가 있으면 1단계로 간다. 만약 모든 노드가 제거되었으면 k-core가 없는 것으므로 끝낸다.
그림으로 보자면 다음과 같다.
3-core를 찾는 과정. edge 수가 3보다 작은 노드를 지워 나간다. 최종적으로 오른쪽 그래프가 얻어진다.
그렇다면 주어진 graph G에 있는 k-core 중 최대의 k 를 찾으려면 어떻게 해야할까? 별다른 방법이 없다. 2-core부터 시작해서 3-core, 4-core, ... 를 쭉 찾아 나가는 수밖에. 그렇기 때문에 maximum k 를 찾는 문제는 O(n3)이 된다. 여기서 약간 짱구를 굴려 보자. 어차피 G에 있는 k-core 중 k의 최대값은 G에 있는 노드 수 - 1 일 수밖에 없다. 최소(2-core)와 최대( (|V|-1)-core) 값을 알고 있으므로 binary search 를 통해 찾는 것이다. 이렇게 하면 그나마 O(n2log(n))으로 계산시간을 줄일 수 있다.
글이 좀 길어져서 구현한 것은 별도의 글로 작성한다. 그 글에 대해 잠깐 예고를 하면, 코드는 C++로 작성되어 linux에서 gcc로 compile 되어있다. 이 글에 맞게끔 수정하려면 약간 시간이 걸릴듯 하다. 원래 나는 graph를 STL의 multimap 을 이용하여 표현하곤 하는데 속도 문제 때문에 double** 로 adjacency matrix를 표현하는 방식으로 다시 구현하였다. k-core를 구하는 부분이 살짝 복잡한데 코드 자체에 주석이 거의 없기 때문에 그것에 대한 약간의 작업이 필요하다.
관련글
1. cytoscape: network 연구 프로그램(내부링크)
2. An automated method for finding molecular complexes in large protein interaction networks, BMC Bioinformatics 2003, 4:2 (MCODE에 관한 논문, 구독하지 않아도 읽을 수 있는 논문)
'연구관련 > Bioinfo류' 카테고리의 다른 글
| dense subgraph 찾기 구현 (MCODE) (2) | 2010.12.03 |
|---|---|
| R로 q-value 구하기 (1) | 2010.10.20 |
| Pubmed eUtils 사용하기 (0) | 2010.07.02 |
| 정규화(normalization) (18) | 2010.04.19 |
| drug 관련 싸이트 (0) | 2010.04.06 |
