[논문] 이산 증분 투표: 일반 그래프와 확장 그래프에 대한 새로운 한계

출처: arXiv - 2606.06381v1

개요

우리는 Cooper, Radzik, Shiraga가 제안한 이산 증분 투표 과정(DIV) [OPODIS ‘23]을 분석한다. 이 과정에서는 무방향 그래프 (G = (V, E))의 정점 집합 (V)에 (n)개의 노드가 존재하고 각 노드는 정수 의견을 가진다. 한 단계에서 무작위로 선택된 노드가 무작위로 선택된 이웃과 상호작용하여 이웃의 의견 방향으로 의견을 (1)만큼 바꾼다. 이 과정은 고유한 의견으로 수렴하며, 기대값으로는 초기 의견들의 차수 가중 평균이 된다. 그래프의 전도율을 (Φ(G)), 평균 차수와 최소 차수의 비율을 (γ(G)), 초기 의견 간 최대 차이를 (K)라 할 때, 기대 수렴 시간은

[ O!\left(\frac{n\bigl(K\log (Kn)+γ(G), n \bigr)}{Φ(G)^2}\right) ]

이다. 이 경계는 확장성이 제한된 큰 클래스의 그래프에 대해 본질적으로 최적이다. 또한 정규 그래프의 경우, 두 번째로 큰 고유값이 (o(1/\log^2 n))이고 (K = o!\left(\frac{n}{\log^2 n}\right))이면, 높은 확률로 DIV는 초기 평균 의견(올림 또는 내림)으로 수렴한다.

주요 기여

이 논문은 다음 분야의 연구를 제시한다:

• cs.DC

방법론

자세한 방법론은 전체 논문을 참고한다.

실용적 함의

이 연구는 cs.DC 분야의 발전에 기여한다.

저자

• Petra Berenbrink
• Colin Cooper
• Thorsten Götte
• Lukas Hintze
• Tomasz Radzik

논문 정보

• arXiv ID: 2606.06381v1
• 분류: cs.DC
• 출판일: 2026년 6월 4일
• PDF: PDF 다운로드