ترجمه فارسی مقاله رای گیری افزایشی گسسته در مورد گسترش دهندگان

چکیده

Pull voting is a random process in which vertices of a connected graph have initial opinions chosen from a set of $k$ distinct opinions, and at each step a random vertex alters its opinion to that of a randomly chosen neighbour. If the system reaches a state where each vertex holds the same opinion, then this opinion will persist forthwith. In general the opinions are regarded as incommensurate, whereas in this paper we consider a type of pull voting suitable for integer opinions such as $\{1,2,\ldots,k\}$ which can be compared on a linear scale; for example, 1 (‘disagree strongly’), 2 (‘disagree’), $\ldots,$ 5 (‘agree strongly’). On observing the opinion of a random neighbour, a vertex updates its opinion by a discrete change towards the value of the neighbour’s opinion, if different. Discrete incremental voting is a pull voting process which mimics this behaviour. At each step a random vertex alters its opinion towards that of a randomly chosen neighbour; increasing its opinion by $+1$ if the opinion of the chosen neighbour is larger, or decreasing its opinion by $-1$, if the opinion of the neighbour is smaller. If initially there are only two adjacent integer opinions, for example $\{0,1\}$, incremental voting coincides with pull voting, but if initially there are more than two opinions this is not the case. For an $n$-vertex graph $G=(V,E)$, let $λ$ be the absolute second eigenvalue of the transition matrix $P$ of a simple random walk on $G$. Let the initial opinions of the vertices be chosen from $\{1,2,\ldots,k\}$. Let $c=\sum_{v \in V} π_v X_v$, where $X_v$ is the initial opinion of vertex $v$, and $π_v$ is the stationary distribution of the vertex. Then provided $λk=o(1)$ and $k=o(n/\log n)$, with high probability the final opinion is the initial weighted average $c$ suitably rounded to $\lfloor c \rfloor$ or $\lceil c\rceil$.

چکیده به فارسی (ترجمه ماشینی)

رأی دادن یک فرآیند تصادفی است که در آن رئوس یک نمودار متصل دارای نظرات اولیه است که از مجموعه ای از $ k $ نظرات متمایز انتخاب شده است ، و در هر مرحله یک راس تصادفی نظر خود را نسبت به یک همسایه انتخاب شده به طور تصادفی تغییر می دهد.اگر سیستم به وضعیتی برسد که هر راس همان عقیده را داشته باشد ، این نظر بلافاصله ادامه خواهد یافت.به طور کلی نظرات به عنوان ناسازگار در نظر گرفته می شوند ، در حالی که در این مقاله نوعی رأی گیری مناسب برای نظرات عدد صحیح مانند $ \ {1،2 ، \ ldots ، k \} $ را می توان در نظر گرفتیم که می تواند در مقیاس خطی مقایسه شود.به عنوان مثال ، 1 (“به شدت مخالف”) ، 2 (“مخالف”) ، \ ldots $ ، 5 دلار (“کاملاً موافقم”).در صورت مشاهده نظر یک همسایه تصادفی ، یک راس نظر خود را با تغییر گسسته به ارزش نظر همسایه ، در صورت متفاوت بودن ، به روز می کند.رأی گیری افزایشی گسسته یک روند رأی گیری است که از این رفتار تقلید می کند.در هر مرحله ، یک راس تصادفی نظر خود را نسبت به یک همسایه انتخاب شده تصادفی تغییر می دهد.اگر نظر همسایه منتخب بزرگتر باشد ، یا اگر نظر همسایه کوچکتر باشد ، نظر خود را با 1 دلار+1 دلار افزایش می دهد.اگر در ابتدا فقط دو نظر عدد صحیح مجاور وجود داشته باشد ، به عنوان مثال $ \ {0،1 \} $ ، رأی گیری افزایشی همزمان با رأی گیری است ، اما اگر در ابتدا بیش از دو نظر وجود داشته باشد ، اینگونه نیست.برای نمودار $ n $ -VERTEX $ g = (v ، e) $ ، اجازه دهید $ λ $ دوم مقادیر دوم مطلق ماتریس انتقال $ p $ از یک پیاده روی تصادفی ساده در $ g $ باشد.بگذارید نظرات اولیه رئوس ها از $ \ {1،2 ، \ ldots ، k \} $ انتخاب شود.بگذارید $ c = \ sum_ {v \ in v} π_v x_v $ ، جایی که $ x_v $ نظر اولیه vertex $ v $ است ، و $ π_v $ توزیع ثابت راس است.سپس $ λk = o (1) $ و $ k = o (n/\ log n) $ ارائه شده است ، با احتمال زیاد نظر نهایی ، میانگین وزنی اولیه $ c $ مناسب به \ lfloor c \ rfloor $ یا $ $ گرد شده است\ lceil c \ rceil $.