Competition is ubiquitous in many complex biological, social, and technological systems, playing an integral role in the evolutionary dynamics of the systems. It is often useful to determine the dominance hierarchy or the rankings of the components of the system that compete for survival and success based on the outcomes of the competitions between them. Here we propose a ranking method based on the random walk on the network representing the competitors as nodes and competitions as directed edges with asymmetric weights. We use the edge weights and node degrees to define the gradient on each edge that guides the random walker towards the weaker (or the stronger) node, which enables us to interpret the steady-state occupancy as the measure of the node`s weakness (or strength) that is free of unwarranted degree-induced bias. We apply our method to two real-world competition networks and explore the issues of ranking stabilization and prediction accuracy, finding that our method outperforms other methods including the baseline win-loss differential method in sparse networks.
경쟁은 다양한 복잡계에서 체계 내의 개체 혹은 구성요소의 생존 및 진화를 결정짓는 주요한 메커니즘 가운데 하나이다. 이러한 경쟁의 결과를 정확히 반영해 개체 혹은 구성요소를 서열화하는 것은 체계 내의 위계질서를 파악함으로써 복잡계의 본질적인 이해를 돕고, 사회적으로는 구성원들의 경쟁에 대한 신뢰를 바탕으로 사회의 안정을 도모할 수 있다는 점에서 대단히 중요하다. 이에 본 논문에서는 복잡계 내의 경쟁 관계들을 하나의 연결망으로 보고, 연결망 과학의 랜덤 워크 개념에 기반을 둔 서열화 모델을 제안하였다. 해당 모델은 경쟁의 결과에 따라 랜덤 워커의 노드(node) 간 이동확률이 비대칭적으로 결정되어 랜덤 워커가 각 노드에 위치할 확률에 따라 노드의 영향력이 결정되고, 노드의 차수(degree)에 따른 부당한 결과가 발생하지 않도록 차수 중화 작업을 거쳐 체계 내 개체 혹은 구성요소 간의 정확한 서열 관계를 파악할 수 있다는 점에서 그 특징을 가진다. 나아가 해당 모델을 미국 미식축구리그와 영국 프리미어리그 등 실제 경쟁 네트워크에 적용해 봄으로써 경기팀 간의 서열을 측정하고 시간의 흐름에 따른 서열의 안정화 과정 등을 살펴보았으며, 특히 밀도가 낮은 연결망에서는 해당 모델이 기존에 제안된 다양한 서열화 방식들과 비교해 경기 결과 예측에 있어 뛰어난 정확도를 보임을 확인할 수 있었다.
