< C6AFC1FD28BCD5BDC2BFEC292E687770>

Size: px

Start display at page:

Download "<313530313237C6AFC1FD28BCD5BDC2BFEC292E687770>"

긔순 점
8 years ago
Views:

1 복잡계 네트워크 위에서의 진화 게임 DOI: /PhiT 손 승 우 Evolutionary Games on Complex Networks 네트워크 위에서의 진화 게임 이론으로 연결되었는지 알아보겠 다. Seung-Woo SON 게임 참여자들 간의 협력, 경쟁, 갈등, 대립을 수학적으로 나타 내려는 이전의 시도들을 이론적으로 집대성한 폰 노인만(John Classical game theory has become a key paradigm for ex- von Neumann, )과 모겐스턴(Oskar Morgenstern, plaining cooperation-competition phenomena in various sci )의 1944년 게임 이론과 경제 행동(Theory of Games entific disciplines ranging from biology and ecology to an- and Economic Behaviour)[3] 을 기점으로 게임 이론의 수학적 thropology, psychology, philosophy, politics, and economics. 틀이 공고해졌다. 1950년 존 내쉬(John Forbes Nash, Jr., In this article, we briefly review its successful history of be )의 내쉬 균형(Nash equilibrium) 과 최선의 행동(best ing one of the mainstream theories in interdisciplinary sci- response) 개념의 제안으로, 죄수의 딜레마(prisoners dilemma) ence and introduce a natural extension of the concepts to 와 공유지의 비극(tragedy of the commons)과 같은 사회적 evolutionary game theory on complex networks. The effects 딜레마 문제에서 중앙 집권적 설계자의 개입이 없을 경우, 개 of the topological features of the underlying networks and 인 수준의 상호작용이 어떠한 균형점을 찾아가는지, 그리고 이 of the possible complicated behaviors on other complex 러한 결과가 전체 계(system)의 관점에서는 효율적(efficient) networks are mainly discussed. 이지 않을 수도 있음을 설명할 수 있었다. 이러한 고전 게임 이론은 완벽한 합리성(perfect rationality) 과 공통지식(common 게임 이론은 진화생물학, 진화심리학, 컴퓨터 과학, 정치학, knowledge) 을 바탕으로 특정 효용함수(utility function) 를 최 군사전략학, 문화인류학, 윤리철학, 경제학 등 다양한 분야에 대화하는 해를 찾는 입장에서 고전 경제학과도 닮았고, 특정 응용되어, 특정 목표와 선호를 가지고 상호 작용하는 게임 참 상황 하에서 에너지나 해밀토니안(Hamiltonian)을 최소화하는 여자들 사이의 동역학을 기술하고 예측하는데 있어 하나의 통 상황을 찾고자 하는 물리학과도 닮았다. [1] 생물학과 사회학, 경제학에서 우리가 매일 푸는 물리 문제에서와 마찬가지로, 고전적 게 실제로 마주하는 상황들을 체계적인 수학적 구조로 단순화, 추 임 이론(물리학에서라면 고전역학)은 가정들이 잘 정의된 문 상화하는 강력한 방법론을 바탕으로 다양한 문제에 적용되어 제들을 성공적으로 설명하긴 하지만, 중요한 가정들로부터 벗 발전하였고, 최근 통계물리학 복잡계 이론 분야의 한 주제로 어나는 현실 세계에서는 설명하지 못하는 문제들에 봉착하기 일된 생각의 틀을 제공해 왔다. 활발히 연구되고 있다. 특히, 생물물리학(biophysics)과 사회물 마련이다. 특히, 완벽한 합리성 은 물리학에서는 정보 전달이 리학(sociophysics), 경제물리학(econophysics) 분야 중심이론 즉시 이루어진다는 무한대의 빛의 속도 가정과 비슷한 면이 의 바탕이 되었다.[2] 다음에서는 게임 이론 분야에서의 중요한 있어서, 이러한 가정을 부정하였을 때, 아인슈타인이 제한된 전환점과 핵심적인 개념들을 다시 짚어 보고, 어떻게 복잡계 저자약력 손승우 교수는 KAIST 물리학과 이학박사(2009)로 통계물리학의 복잡계 네트워크 이론을 공부하였다. KAIST와 University of Calgary에서 박사 후연구원(postdoctor) 과정을 마친 후, 2012년부터 한양대학교 ERICA 응용물리학과 조교수로 재직 중이다. (sonswoo@hanyang.ac.kr) [1] M. A. Nowak, Evolutionary Dynamics (Harvard University Press, Cambridge, MA, 2006). [2] G. Szabó and G. Fáth, Physics Reports 446, 97 (2007). [3] J. von Neumann and O. Morgenstern, Theory of Games and Economic Behaviour (Princeton University Press, Princeton, 1944). 27

cooperation-competition phenomena in various sci- 1902-1977)의 1944년 게임 이론과 경제 행동(Theory of Games entific disciplines ranging from biology and ecology to an- and Economic Behaviour)[3] 을 기점으로 게임 이론의

2 Fig. 1. (Left) complete graph. It describes the well-mixed case. (Center) regular one-dimensional ring structure with four neighbours. (Right) small-world network. It is generated by rewiring only few links of regular one-dimensional ring conserving the number of neighbours. 빛의 속도 개념으로부터 특수상대성이론을 생각해낼 수 있었 적 나선(stable spiral)에, 내쉬 균형점은 시간 의존 동역학방정 듯이, 제한된 합리성(bounded rationality) 으로부터 더 풍부하 식을 풀 필요가 없는 고정점(fixed point)에 해당된다.[5] 기본적 고 재미있는 현실 문제에 접근할 수 있게 된다. 동물 군집의 인 진화 게임에서는 모든 전략이 다른 전략을 항상 만날 수 경쟁과 협력을 생각할 때면, 주어진 문제 상황으로부터 완벽히 있는 잘 섞여있는 조건(well-mixed condition) 을 가정한다. 소 정보가 전달된다고 하더라도 제한된 합리성을 가정하는 것이 위 물리학에서 말하는 평균장 근사(mean-field approximation) 자연스럽다고 생각할지 모르겠다. 인간이라고 다를까? 이러한 에 해당된다 말할 수 있다. 입장에서, 게임이론의 전략(strategy)은 유전자에 입력되어 죽 하지만, 최근 복잡계 네트워크 연구 결과에 따르면 특히, 사 을 때까지 유지되고, 전략의 채택(adoption)과 변화(change)는 회 연결망과 같은 우리가 살고 있는 현실 세계의 상호작용은 미리 결정되어 있는 생물학적 학습과 돌연변이 확률에 의해서 평균장 근사와 상당히 거리가 먼 불균등하며 복잡한 다양한 주어지며, 각 전략의 성공은 생물학적 적합성(fitness) 으로 나 모습을 보인다는 것이 잘 알려져 있다.[6] 사회와 생물 군집의 타나 재생산에 반영된다는 생물학적 개념을 받아들여 진화 게 경쟁과 협력에 대한 보다 적절한 모델을 고려해 볼 때, 그 기 임 이론(evolutionary game theory) 이 탄생하게 된다. 저의 상호작용 구조가 게임 동역학에 무의미하지 않다면, 그 진화 게임 이론은 제한된 합리성을 고려한 자연스러운 확 상호작용의 구조를 고려해 넣어야만 할 것이다. 이와 같이 상 장으로, 게임 참여자가 다양한 상황에서 제한된 합리성 아래 호작용의 관계 구조를 포함한 모델링을 하기 위해서는, 더 이 에서는 이러이러한 행동을 할 것이라는 구체적인 행동규칙이 상 평균장 근사에서 사용할 수 있었던 유용한 해석적 접근법 주어져야 한다. 이에는 지난 결과를 전략에 얼마나 반영할지 들은 사용할 수 없고, 거의 유일한 방법은 각 상황에 대한 구 (memory), 앞의 수는 얼마나 고려할 것인지(myope), 어떤 전 체적인 규칙이 주어지는 에이전트 기반 모델링이 된다. 기존의 략들 중에서 고를 것인지(search space), 성공적인 전략으로 잘 섞여있는 조건 은 모든 노드가 연결된 그림 1과 같은 완전 어떻게 바꿀 것인지(adaptive learning) 등을 고려한다. 그 결 그래프(complete graph)로 표현할 수 있기 때문에, 복잡계 네 과로 자연스럽게 물리학에서 관심을 갖는 동역학적 특성, 즉, 트워크 위에서의 진화게임은 기존의 평균장 근사를 사용한 진 전략의 진화를 보이게 되는데, 이는 완전한 합리성에서의 평형 화 게임 이론보다 일반화된 문제가 된다. 상태에서는 볼 수 없는 것이다. 이러한 개념은 자연스럽게 생 복잡계 네트워크 위에서의 진화 게임을 이해하기 위해서는 물학 분야에서 먼저 시작되어 게임이론의 다양한 문제로 확장 우리가 살고 있는 세계와 가까운 2차원 공간 모델을 생각하는 [4] 되었다. 진화 게임에서 전략의 승패가 반영되는 개체군의 밀 것이 가장 이해하기 쉬울 것이다. 2차원 공간을 가로, 세로의 도(population density) 혹은 전략 빈도의 변화는 복제자 동역 학(replicator dynamics) 또는 에이전트 기반 모델링(agent- based modeling) 으로 기술된다. 복제자 동역학의 경우, 전략 [4] J. Maynard Smith, Evolution and the Theory of Games (Cambridge University Press, Cambridge, 1982); R. Axelrod, The Evolution of Cooperation (Basic Books, New York, 1984). [5] S. H. Strogatz, Nonlinear Dynamics and Chaos (Westview Press, Perseus Books Publishing, 1994). [6] Hawoong Jeong and Byungnam Kahng, Phys. High Technol. 16(10), 7 (2007). 의 빈도는 보통 게임의 보수(payoff) 에 따른 시간 의존 비선형 방정식으로 쓸 수 있는데, 메이나드 스미스(John Maynard Smith, )에 의해 제안된 진화적으로 안정적인 전략 (evolutionary stable strategy) 은 소위 비선형 동역학의 안정 28

빛의 속도 개념으로부터 특수상대성이론을 생각해낼 수 있었 적 나선(stable spiral)에, 내쉬 균형점은 시간 의존 동역학방정 듯이, 제한된 합리성(bounded rationality) 으로부터 더 풍부하 식을 풀 필요가 없는 고정점(fixed point)에 해당된다.[5] 기본적 고 재미있는 현실 문제에 접근할 수 있게 된다.

3 (a) (b) (c) Fig. 2. Various network models. (a) regular two-dimensional square lattice structure, (b) random network, (c) scale-free network. (Images from: Hawoong JEONG and Byungnam KAHNG, Phys. High Technol. 16(10), 7 (2007)). 사각 격자 구조로 이루어졌다고 생각하면, 네트워크 위에서의 환 불변성(translation invariance)이 있어, 고체물리와 통계물 진화 게임의 게임 참여자는 각 사각면 혹은 격자점(노드)에 위 리 이론 분야에서 개발된 수학적 방법들을 적용하여 분석할 치하고, 반복적으로 주변의 이웃들과 고전적 방법의 게임을 하 수 있다. 하지만, 이러한 격자 구조에서 간단히 몇 개의 연결 는 상황을 생각할 수 있다. 주변 이웃들과의 게임 결과로부터 선을 마구잡이로 제거하거나, 연결선을 바꿔주는 작업만으로도 얻은 보수의 누적이 총 수입이 되고, 수입을 최대화하여 적합 공간적으로 불균일한 구조(inhomogeneous structure)를 만들 한 전략이 되는 것은 곧 주변 이웃들이 어떤 전략을 가지고 수 있어서, 앞서 말한 해석적 방법을 적용할 수 없게 된다. 이 있는가에 대한 전략의 공간적 분포의 문제가 된다. 각 게임 참 런 대표적인 예가 링크를 불규칙적으로 제거한 드문드문 격자 여자는 자신의 수입, 즉 효용함수를 최대화하기 위해 주변 이 (diluted lattice) 이고, 후자의 몇 개의 링크를 바꿔준 것이 다 웃의 전략에 대해 자신의 전략을 수정할 수 있고, 때로는 주변 음에 설명할 좁은 세상 네트워크(small-world network) 이다.[8] 이웃의 전략 중 효과적인 전략 하나를 배울 수도 있다. 이러한 좁은 세상 네트워크는 그림 1의 가운데 그림처럼 규칙적인 세세한 규칙을 정한 에이전트 기반 모델링의 결과로 우리가 1차원 링 구조에서 시작하여 몇 개의 링크를 다른 곳에 연결 사회나 동물 군집에서 목격하는 집단적 거동을 관찰하려는 것 하는 작업(rewiring)을 통해서, 그림 1의 오른쪽과 같이 전체적 이 공간적 진화 게임, 즉 복잡계 네트워크 위에서의 진화 게임 으로 규칙적 구조는 크게 훼손하지 않으면서, 먼 거리 연결 이론의 목적이다. 이는 미세 상호작용(microscopic interaction) (long-range interaction)을 형성한다. 이로써, 진화 게임에서 의 결과로부터 거시적 상전이(macroscopic phase transition) 중요한 역할을 할 수 있는 요소들인, 한 노드의 이웃들이 얼마 [7] 특히, 진 나 서로 연결되었는지를 나타내는 뭉침 계수(clustering co- 화 게임 이론에서의 상호 작용이 대칭적이지 않고(asymmetric), efficient) 는 높게 유지하며, 평균 도달 거리(average dis- 시간 가역적이지 않아(time-reversal symmetry breaking), 비 tance) 를 획기적으로 줄일 수 있게 된다. 이때, 얼마나 많은 를 연구하는 통계물리학의 방법론과 일맥상통한다. 평형계(nonequilibrium system)에 해당되어 전략 공간에서 복 연결선을 변경하는지를 나타내는 변수를 조절하여, 완전히 규 잡하고 다양한 양상이 전개된다. 칙적인 구조와 완전히 불규칙적인 연결 구조 사이의 정도를 이제는 간단히 전형적인 네트워크 연결 구조에 대해서 살펴 연속적으로 조정할 수 있다. 이때 불규칙적인 한 쪽 극한은 이 보자. 앞서 논의한 2차원 공간 모델에 해당하는 사각 격자 미 확률적 조합 수학 분야에서 많이 연구된 그림 2(b)의 마구 (square lattice)구조를 네트워크로 표현하면, 그림 2의 (a)와 잡이 네트워크(random network)가 된다.[9] 같은 규칙적인 2차원 사각 격자 구조로 생각할 수 있고, 이때 이와 같이 규칙적 격자 구조나 그 변형 구조는 모든 노드가 게임을 하게 되는 고정적인 이웃은 연결선(링크)으로 이어진 같은 수의 연결선 수(degree)를 가지고 있거나 거의 비슷한 수 노드들이 된다. 직접 연결된 네 이웃만을 생각하는 경우를 폰 의 연결선을 가지고 있어, 연결선 수 분포(degree distribution) 노이만 이웃 이라 하고, 대각선 방향의 노드들을 포함하여 한 노드를 둘러싼 모든 노드들을 고려하는 경우를 무어 이웃 이라 고 한다. 비슷한 방법으로 1차원 구조도 생각할 수 있어서, 그 [7] Seung Ki Baek, Beom Jun Kim and Jung Kyoo Choi, Phys. High Technol. 16(10), 19 (2007). [8] D. J. Watts and S. H. Strogatz, Nature 393, 440 (1998). [9] B. Bollobás, Random Graphs, 2nd edition (Cambridge University Press, 2001). 림 1의 가운데 있는 규칙적인 1차원 링 구조를 만들 수 있고, 반대로 더 높은 3 이상의 차원도 초립장체(hypercubic lattice) 로 표현할 수 있다. 규칙적인 격자 구조에서는 공간에 대한 변 29

사각 격자 구조로 이루어졌다고 생각하면, 네트워크 위에서의 환 불변성(translation invariance)이 있어, 고체물리와 통계물 진화 게임의 게임 참여자는 각 사각면 혹은 격자점(노드)에 위 리 이론 분야에서 개발된 수학적 방법들을 적용하여 분석할 치하고, 반복적으로 주변의 이웃들과 고전적 방법의 게임을 하 수 있다.

4 에 있어서 균등한 네트워크(homogeneous networks) 라고 할 생각하게 되고, 그 결과로 두 게임 참여자의 보수의 합은 최선 수 있다. 특별히, 모든 연결선 수가 k로 일정한 경우를 이산수 의 결과가 되지 못하는 딜레마에 빠진다. 학에서 k-정규 그래프(k-regular graph) 라 한다. 정규 그래프 우리의 주변에서 이런 예가 종종 발생하고, 심지어 동물이 에서도 2차원 사각 격자 구조, 1차원 링 구조 외에도 전혀 닫 나 박테리아 수준의 행동에도 이런 선택의 상황이 있음이 여 힌 연결 구조(loop)가 없는 베테 격자(Bethe lattice) 까지 다양 러 연구를 통하여 보고되었다. 그런데, 이런 죄수의 딜레마 상 한 구조가 가능하여 다양한 동역학적 특징을 나타낸다. 하지 황에서도 고전 게임 이론에서 예측하는 바와 달리, 이타적으로 만, 복잡계 네트워크 연구의 결과에 따르면, 공학 분야의 인터 협력하는 행동이 종종 나타나는 것에 대한 연구가 여러 연구 넷, 사회학의 주제인 친분 관계 및 공동 연구자 관계, 생물학 자에 의해 진행되었다. 그 결과, 반복되는 죄수의 딜레마 게임 의 신진대사 작용 혹은 단백질 상호작용 네트워크 등 무수히 에서 전략의 종류와 보수, 전략의 진화 규칙, 게임 참여자 사 많은 실제 네트워크들이 이러한 균등한 연결선 분포를 따르지 이의 연결 관계 등에 따라 협력의 비율이 달라지는 것을 알게 않고, 그림 2의 (c)와 같이 대부분의 많은 노드들은 소수의 연 되었다. 이런 협력에 있어서 직 간접적인 상호성 혹은 호혜 결선만을 가지고 있는 반면, 소수의 몇몇 중심 노드(hub)가 대 (reciprocity)가 중요한 역할을 하는 것이 잘 알려져 있다. 부분의 연결선을 가지고 있는 매우 불균등한 연결선 분포 이때 공간적인 연결 관계는 어떤 영향을 줄까? 노박(Martin (inhomogeneous degree distribution) 를 보인다는 것이 밝혀 Nowak, 1965-)의 1992년 진화 게임에서 공간적 분포의 영향 [10] 대부분의 네트워크들의 연결선 수 k의 분포가 에 대한 연구에 따르면,[12] 시뮬레이션의 결과 유혹이 그리 크 의 멱함수 법칙(power-law)을 따른다는 데서 척도 없는 지 않은 영역에서도 배반자는 협력자들 속에서 살아남을 수 네트워크(scale-free network) 라 부른다. 있다. 하지만, 배반자끼리 붙어있게 되면 불이익이 생기기 때 졌다. 이러한 척도 없는 네트워크의 연결선 수 분포의 특징을 나 문에 배반자들은 무리지어 있을 수 없다. 협력자에 둘러싸여 타내는 다양한 모델들이 제시되었다. 그 중 핵심적인 요소라 있는 배반자는 총 수입이 가장 커서 주변의 다른 협력자들보 할 수 있는 것은 성장하는 네트워크(growing network)에서 이 다 적합이므로, 주변 협력자들은 틈틈이 옆의 배반자의 전략을 미 연결선이 많은 허브 노드에 추가 연결선의 선호적 연결 학습하려 한다. 그러나 배반자끼리 연결이 생기는 순간 그 둘 [11] (preferential attachment)이라 할 수 있다. 네트워크가 성장 의 수입이 감소하여 다시 협력으로 되돌아 올 수밖에 없어진 하며 이미 연결선 수가 많은 중심 노드에 더 많은 연결선이 다. 여기서 유혹을 조금 키우게 되면, 배반자의 곁에 새로운 추가되므로, 연결선 수 분포에서 매우 불균등한 특징을 보인 배반자가 있을 수 있게 된다. 하지만, 여전히 배반자가 무리지 다. 이러한 연결 구조의 불균등성과 복잡성은 진화 게임 동역 어 있을 수는 없다. 이런 식으로 배반자는 협력자와의 연결선 학에 큰 영향을 주며, 연결선 수가 많은 중심 노드와 연결선 수를 특정수로 유지하며 협력자들 사회에 침투해 들어올 수 수가 적은 변방 노드(peripheral node)는 서로 다른 전략을 사 있다. 그러나 유혹이 아주 커지면 주변에 대부분이 배반자가 용하게 될 가능성이 크다는 것을 알 수 있다. 되게 된다. 이 경우 협력자들은 무리를 지어 있어야 유리하므 잘 알려져 있는 죄수의 딜레마를 생각해 보자. 고전 게임 로 배반자들을 피해 무리를 이루어 있게 된다. 배반자들만이 이론에서 두 게임 참여자는 서로 상의할 수 없고, 배반(D)과 모여 있는 곳에서는 총 수입이 적음에도 주변에 배울 별 다른 협동(C), 이 두 가지의 옵션 중 하나를 선택할 수 있다. 그 결 전략이 없는 상태가 되고, 오직 협력자들을 둘러싸고 있는 배 과로 각각 다음과 같은 보수를 받을 것을 알고 있다. 둘 다 협 반자들은 그 경계에서 둘 사이의 균형을 이루게 된다. 이와 같 동할 경우, 이들은 같은 크기의 보상(R)을 받고, 이때 두 게임 이, 협력자들은 무리지어 있는 것이 유리하고, 배반자들은 협 참여자의 보수의 합이 다른 어떤 경우보다 크다. 둘 중 하나 력자들의 곁에 있는 것이 중요하게 되어, 연결선 수와 전략들 가 배반을 하게 되면, 배반을 한 사람은 유혹(T)에 해당하는 의 배치 구조가 구조적 진화 게임에서 아주 중요한 역할을 하 보수를 받고, 배반당한 협력자는 시련(S)에 해당하는 보수를 게 된다. 받는다. 둘 다 배반을 하는 경우, 둘은 처벌(P)에 해당하는 같 은 보수를 받는다. 여기서 각 보수의 크기는 이고, 둘이 협동할 경우 가장 큰 보수의 합을 받게 되므로, [10] R. Albert and A.-L. Barabási, Rev. Mod. Phys. 74, 47 (2002); S. N. Dorogovtsev and J. F. F. Mendes, Adv. Phys. 51, 1079 (2002); M. E. Newman, SIAM Review 45, 167 (2003). [11] A.-L. Barabási, R. Albert and H. Jeong, Physica A 272, 173 (1999). [12] M. Nowak and R. M. May, Nature 359, 826 (1992). 이다. 모두 협력하는 경우에 비해서 배반자의 이 득은 로 협력자의 손실인 보다 작음에도 불구하고, 잘 알려진 내쉬 균형의 결과와 같이 이기적인 각 게임 참여자 는 어떤 한 경우에도 자신이 배반을 선택하는 것이 유리하다 30

그런데, 이런 죄수의 딜레마 상 한 구조가 가능하여 다양한 동역학적 특징을 나타낸다. 하지 황에서도 고전 게임 이론에서 예측하는 바와 달리, 이타적으로 만, 복잡계 네트워크 연구의 결과에 따르면, 공학 분야의 인터 협력하는 행동이 종종 나타나는 것에 대한 연구가 여러 연구 넷, 사회학의 주제인 친분 관계 및 공동 연구자 관계, 생물학 자에 의해 진행되었다.

5 연결선 수의 분포가 매우 불균등한 척도 없는 네트워크의 비선형 성을 내재한 진화 게임 이론에 보다 실제에 가까운 경우에는 이런 영향이 더욱 극명하게 나타날 수 있다. 최근 연 상황을 이해하기 위해 복잡계 네트워크 구조까지 변수에 고려 구 결과에 따르면, 연결선 수의 불균등 정도(degree hetero- 하여 모든 변수 공간에서의 완벽한 분석은 불가능할 것이다. [13] geneity)가 협력의 경향을 극적으로 향상시킬 수 있다 한다. 하지만, 복잡계 네트워크 위에서의 진화 게임은 정적인 결과를 앞서 노박의 연구 결과와 마찬가지 논리로 협력자의 경우는 찾기 위한 것이 아니라 동적인 변화를 이해하기 위한 과정이 다른 협력자들과 뭉치는 것이 유리하다. 배반자는 뭉치는 것은 다. 여러 요인의 관련성을 따져 보고 정수를 가려내 핵심을 이 치명적이지만, 배반자 역시 다른 협력자들에게 둘러싸이는 것 해하는 과정은 아마도 이러한 복잡계에 익숙한 물리학자들의 은 선호한다. 특정 초기 상태와 네트워크 구조에 따라 달라질 몫일 것이다. 최근에는 단일 네트워크만을 반영한 것이 아니라 수 있는 여지가 많아 일반적인 결론을 내릴 수는 없지만, 같은 게임을 하는 네트워크와 학습을 하는 네트워크가 다른 두 겹 수의 협력자에 둘러싸여 서로 연결되어 있는 중심노드 위의 네트워크에서의 게임[14]이나, 성장하거나 구조가 바뀌는 진화하 협력자와 배반자의 경쟁 논의는 흥미롭다. 처음에는 배반자의 는 네트워크(evolving network) 위에서의 진화 게임, 게임의 수입이 크기 때문에 유리할 수 있다. 하지만, 곧 다음 단계에 결과로 네트워크의 구조가 바뀌는 상호 진화하는 게임, 일시적 서 배반자의 주변에 있는 협력자들은 배반자를 따라하게 되고, 네트워크(temporal network) 위에서의 진화 게임 등으로 연구 이게 독이 되어 다음 단계에 중심노드 위 배반자의 수입은 낮 의 영역이 확장되며 활발한 후속 연구가 진행되고 있다. 아지게 된다. 반면, 중심노드의 협력자는 다음 단계에도 안정 적이므로, 다음 단계에서 중심노드 위의 배반자는 옆의 중심노 드 위 협력자를 따라 협력으로 돌아서게 된다. 이와 같은 원리 로 연결선 수가 많은 노드들은 협력을 할 가능성이 높아지고, 협력자들의 공고한 무리를 이루게 된다. 반면, 배반자들은 변 방의 노드들에서 주변의 협력자 곁에 살아있게 된다. 네트워크 구조에서 주변의 이웃이 서로 얼마나 연결되어 있는지를 나타 내는 뭉침 계수와 연결선 수 상관계수와 같은 구조적 특징들 도 다채로운 동역학적 특징에 영향을 주게 된다. [13] F. C. Santos and J. M. Pacheco, Phys. Rev. Lett. 95, (2005); F. C. Santos, J. F. Rodrigues and J. M. Pacheco, Proc. Roy. Soc. Lond. B 273, 51 (2006); F. C. Santos, J. M. Pacheco and T. Lenaerts, Proc. Natl. Acad. Sci. USA 103, 3490 (2006). [14] H. Ohtsuki, C. Hauert, E. Lieberman and M. A. Nowak, Nature 441, 502 (2006); H. Ohtsuki, M. A. Nowak and J. M. Pacheco, Phys. Rev. Lett. 98, (2007). 31

하지만, 복잡계 네트워크 위에서의 진화 게임은 정적인 결과를 앞서 노박의 연구 결과와 마찬가지 논리로 협력자의 경우는 찾기 위한 것이 아니라 동적인 변화를 이해하기 위한 과정이 다른 협력자들과 뭉치는 것이 유리하다. 배반자는 뭉치는 것은 다.

02(007-014) CPL12-16.hwp

02(007-014) CPL12-16.hwp 국내 웹 그래프의 링크 구조 분석 7 국내 웹 그래프의 링크 구조 분석 (Link Structure Analysis of Korean Web Graph) 서 정 주 김 진 일 김 은 상 김 영 호 (Jungjoo Seo) (Jinil Kim) (Eunsang Kim) (Daniel Kim) 정 하 웅 김 성 렬 박 근 수 (Hawoong Jeong) (Sung-Ryul