For decades, studies on decentralized algorithms have been emerging as one of the important research area for a building block of complex network systems, due to their convenient property to compute global quantities without any centralized agency. In this thesis, we consider one of the decentralized algorithmic problem, \emph{rank aggregation} problem. The goal of this problem is to make a ranking of a set of candidates in decreasing order of nodes` preference in a distributed manner. More specifically, in this problem each node in a complex network initially prefer candidates with some ratio and the goal for each node is to eventually compute a list of candidates which denotes an initial ranking. Each node communicates with each other and updates its current state based on the state communicated by the last contacted node.
Here we propose three algorithms related to this problem under restrictions on memory and communication. The first algorithm based on the inteval consensus result computes full ranking for any graph using $2^{m(m-1)}$ states per node where $m$ is the number of candidates for any connected graph. Next we show an efficient algorithm for a mode computation using only $2m$ states per node for complete graphs. Via mean field approach, we show that the error probability for this algorithm is bounded exponentially to the total number of nodes. Lastly we propose a reduction algorithm that reduces the problem of computing top-$k$ ranking with $m$ candidates to the problem of computing a mode with $O(m^k)$ many states. Based on our mode computation algorithm, we also provide that the error probability is bounded exponentially to the number of nodes for complete graphs.
그래프 상에서 local한 정보 교환만을 통하여 global한 값을 연산할 수 있는 분산 연산 알고리즘은 복잡계 망 연구의 발달과 더불어 논의되어 온 분야이다. 이 논문에서는 이러한 분산 연산 알고리즘 중 하나인 순위 종합 문제에 대하여 다룬다. 이 문제의 목표는 분산적으로 노드들의 선호도를 종합하여 후보군의 순위를 결정하는 것이다. 자세히 말하자면 이 문제에서 복잡계 망의 각 노드는 어떠한 비율에 따라 후보들을 선호하며, 각 노드의 최종 목표는 후보들의 초기 선호도 순위를 연산하는 것이다. 각 노드는 서로 통신하며 가장 마지막에 통신한 노드의 상태에 기반하여 자신의 상태를 업데이트한다.
이 논문에서는 이 문제와 관련하여 메모리와 통신의 제약을 고려하여 세 가지 알고리즘을 제시한다. 첫 번째 알고리즘은 interval consensus 결과에 기반한 것으로, $m$가지의 후보가 있을 때 $2^{m(m-1)}$ 가지 상태를 이용하여 모든 연결 그래프의 full ranking을 계산한다. 그 다음으로 완전 그래프에 대하여 오로지 $2m$ 가지 상태만을 허용하는 절약적인 최빈값 연산 알고리즘을 제시한다. mean field approach에 의하여 이 알고리즘의 오류 확률이 전체 노드 수에 exponentially 줄어드는 것을 보인다. 마지막으로 $m$가지 후보가 있는 top-$k$ ranking을 $O(m^k)$ 가지 상태가 있는 최빈값 연산으로 reduction 시키는 방법에 대하여 논의하며 앞서 소개한 최빈값 연산 알고리즘에 의해 top-$k$ ranking 알고리즘 또한 완전 그래프에 대해 오류 확률이 exponential함을 보인다.
