[논문소개] anti-preferential attachment로 부터 창발하는 동류성과 leadership

 Preferential attachment는 degree distribution에서 scale-free의 성질을 형성한다. 다만, 오로지 degree에 대한 preferential 만을 반영하므로, topology에는 관여하지 않는다. 이런 측면에서 preferential attachment는 topology를 제외한 0차 근사로 볼 수 있다. 

 네트워크에서 주로 보는 topology로는 clustering, degree assortativity, core-periphery 구조, community 구조 등이 있다. clustering과 degree assortativity는 보통 macro-scale의 관점을 갖는 것이 일반적이지만, 각각 local scale에서 보는 방법들이 고안되어있다. 한편, core-periphery, community는 조금 더 meso-scale의 측면이 강하다. 

 이런 특성을 preferential 과 결합하기 위한 방법으로, 다양한 알고리즘들이 고안되어 왔다. 그 중 하나는 preferential attachment을 국부적인 임의 선호성의 규칙으로 치환하는 방법이다 [1]. 좀 더 풀어 쓰자면, 임의로 한 node를 선택하고 그 주변 node 중 한 node를 선택하는 방법이다. 이 방법에서는 오로지 임의적인 선택만이 사용되지만, 결과적으로는 degree가 높은 node가 선택될 확률이 높다. 처음 선택한 node의 주변 node를 선택하기 때문에, '주변'으로 많이 채택 되는 것이 유리하게 되는데,  그러기 위해서는 degree가 많은 node가 유리하기 때문이다. 이 방법은 부수적인 효과로 degree와 clustering coefficient에 음의 상관관계를 형성한다. 임의 선택이라는 점에서 degree가 높을 수록 삼각형을 더 만들기 힘들어 지는 반면, degree가 낮은 node에서는 삼각형이 비교적 많이 형성되기 때문이다. 이러한 형태는 계층구조를 지닌 네트워크 구조에서 많이 발견되는데, 이 또한 실제 네트워크에서 많이 발견되는 현상이다 [2]. 

 

 오늘 본 논문 [3]은 두 개의 규칙을 지닌 network의 성장이 실제 network에서의 아주 높은 degree를 지닌 node들 (leadership)과 assortativity (동류성)을 잘 설명한다는 것이다. 여기서 두 개의 규칙은 다음과 같다.

 

# follower : 임의의 node를 선택하고 그 node의 주변에 있는 임의의 node와 link를 형성한다.

# potential leader : 임의의 node를 선택하고 그 node의 주변 node 중 가장 낮은 degree의 node와 link를 형성한다.

 

 Potential leader는 일부러 가장 낮은 degree의 node와 link를 형성하기 때문에 이 논문에서는 이를 anti-preferential attachment 라고 표현한다. 만약 follower만 있다면 이는 위에서 설명한 계층적 scale-free network를 형성하는 메커니즘과 같다 [1]. 

 흥미로운 점은 follower와 potential leader를 적절히 (2:8) 정도로 섞어서 성장시킨다면 potential leader의 성장이 두드러진다는 점이다. potential leader가 등장하면, 이들은 낮은 degree 주변에 포진하게 되는데, 낮은 degree의 주변에 있다는 것은 더 높은 확률로 선택된다는 것을 의미하므로, 신규 node에게 선택받을 확률이 증가한다. follwer만 있는 경우에는 주변 node에 대한 degree 선호성이 없으므로 주변 node에 대한 degree 편향성이 없기 때문에 이 효과가 나타나지 않는다. 또 하나 potential leader만 있다면 계속 낮은 degree에만 연결되려고 하기 때문에 degree distribution이 이루는 heavy-tail이 사라지며 괄목할만한 hub가 형성되지 못한다. 그래서 이 현상을 보기 위해서는 둘이 적절히 섞인 heterogeneous network의 성장 메커니즘이 필요하다.

 

 또한 이 heterogeneous network의 성장은 중간(median) degree 부근에서의 assortativity를 급격히 증가시킨다. 일반적인 follwer뿐만이라면 degree가 낮은 node를 성장시킬 동력이 충분치 않지만, potential leader가 섞인다면, 낮은 degree의 node의 degree를 끌어올린다. 이 때 낮은 degree를 지닌 node들끼리는 서로의 성장을 끌어올리는 동력이 형성되는데 이것이 median degree까지 assortativity를 끌어올릴 수 있는 동력을 제공한다. (assortativity에 대한 메커니즘은 논문에서는 자세한 설명이 없어 개인적인 해석을 덧붙였다.)

 

 이 현상의 중요성을 실제 social network 분석을 통해 강조하는데, 실제 social network에서도 최종적으로 degree를 가장 많이 지닌 hub들은 처음 network에 유입될 때 적은 수의 degree의 node와 link를 형성했다는 것을 보인다. 즉, 처음에 친구를 적게 가진 node가 최종적으로는 크게 성장했다는 뜻이다.

 논문에서는 이를 Dunbar의 연구와 결합한다. 새로운 node가 임의로 degree가 낮은 node를 선택했다는 것은, 반대로 보면 기존 degree가 낮은 node가 새로운 node와 연결을 형성했다는 말도 된다. 이는 사람은 정해진 수의 interaction만이 허용된다는 점에서 합리적이다. 즉, degree가 너무 높은 node는 새로운 node와 degree를 형성하기 어렵다는 뜻이다.

 

 흥미로운 논문이다. 일부러 degree가 낮은 node와 결합하는 전략이 오히려 자신을 성장시킬 수 있는 동력이 될 수 있다니 말이다. 하지만, 이 논문에서는 아주 높은 hub에 대해서는 설명력이 부족하다. 실제 network에서 degree가 아주 높은 node들의 초기 선호성을 조사한 것과 비교하면, 여기서 제안한 메커니즘은 degree가 낮은 node 주변에서의 초기 성장동력을 설명하는데 그쳐있다는 인상이다.

 물론, 이 동력에 의해 어느 정도 선 상에 올라가는 것은 아주 중요하다. 어쨋든 degree가 높아야 follower들이 더 접근하기 좋은 환경에 진입할 수 있게 해주기 때문이다. 다만, potential leader는 follwer들이 대다수인 상황에서 더 유리하다. potential leader만 많아지면 network는 그냥 길게길게 늘어질 뿐이기 때문이다. 이 논문을 한마디로 종합하자면 이렇다.

 

 적은 친구 수를 지닌 node와 초기연결을 형성하는 potential leader들는 이후 유입되는 follower들로부터 성장동력을 흡수하며 급격한 성장을 이루며, 계층적이고 동류성을 지닌 네트워크 구조를 형성하는데 기여한다. 

 

[1] Boccaletti, Stefano, D-U. Hwang, and Vito Latora. "Growing hierarchical scale-free networks by means of nonhierarchical processes." International Journal of Bifurcation and Chaos 17.07 (2007): 2447-2452.

[2] Vázquez, Alexei. "Growing network with local rules: Preferential attachment, clustering hierarchy, and degree correlations." Physical Review E 67.5 (2003): 056104.

[3] Sendiña-Nadal, Irene, et al. "Assortativity and leadership emerge from anti-preferential attachment in heterogeneous networks." Scientific reports 6.1 (2016): 1-7.