論文の概要: Random Majority Opinion Diffusion: Stabilization Time, Absorbing States, and Influential Nodes

• arxiv url: http://arxiv.org/abs/2302.06760v1
• Date: Tue, 14 Feb 2023 00:14:22 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-15 16:49:26.033643
• Title: Random Majority Opinion Diffusion: Stabilization Time, Absorbing States, and Influential Nodes
• Title（参考訳）: ランダム多数意見拡散:安定化時間、吸収状態、影響力のあるノード
• Authors: Ahad N. Zehmakan
• Abstract要約: 我々は,RMM (Random Majority Model) が期待する安定な構成に到達するために指数関数的に多数のラウンドを必要とするグラフが存在することを証明した。 また、初期着色における色に関する合意が、すべてのノードがその色を共有する色付けにおいて終了するプロセスを強制するノードの集合である、勝利集合の最小サイズについても検討する。
• 参考スコア（独自算出の注目度）: 10.279748604797911
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Consider a graph G with n nodes and m edges, which represents a social network, and assume that initially each node is blue or white. In each round, all nodes simultaneously update their color to the most frequent color in their neighborhood. This is called the Majority Model (MM) if a node keeps its color in case of a tie and the Random Majority Model (RMM) if it chooses blue with probability 1/2 and white otherwise. We prove that there are graphs for which RMM needs exponentially many rounds to reach a stable configuration in expectation, and such a configuration can have exponentially many states (i.e., colorings). This is in contrast to MM, which is known to always reach a stable configuration with one or two states in $O(m)$ rounds. For the special case of a cycle graph C_n, we prove the stronger and tight bounds of $\lceil n/2\rceil-1$ and $O(n^2)$ in MM and RMM, respectively. Furthermore, we show that the number of stable colorings in MM on C_n is equal to $\Theta(\Phi^n)$, where $\Phi = (1+\sqrt{5})/2$ is the golden ratio, while it is equal to 2 for RMM. We also study the minimum size of a winning set, which is a set of nodes whose agreement on a color in the initial coloring enforces the process to end in a coloring where all nodes share that color. We present tight bounds on the minimum size of a winning set for both MM and RMM. Furthermore, we analyze our models for a random initial coloring, where each node is colored blue independently with some probability $p$ and white otherwise. Using some martingale analysis and counting arguments, we prove that the expected final number of blue nodes is respectively equal to $(2p^2-p^3)n/(1-p+p^2)$ and pn in MM and RMM on a cycle graph C_n. Finally, we conduct some experiments which complement our theoretical findings and also lead to the proposal of some intriguing open problems and conjectures to be tackled in future work.
• Abstract（参考訳）: n 個のノードと m 個のエッジを持つグラフ g を考えると、それはソーシャルネットワークを表し、最初に各ノードが青か白であることを仮定する。 各ラウンドでは、すべてのノードが同時に、近隣で最も頻繁に色を更新する。 これは、ノードがネクタイの場合の色を保ち、確率1/2とホワイトで青を選ぶ場合、ランダム多数派モデル(rmm)を保った場合、多数派モデル(mm)と呼ぶ。 我々は、RMMが期待されるような安定な構成に達するために指数関数的に多くのラウンドを必要とするグラフがあることを証明し、そのような構成は指数関数的に多くの状態(つまり着色)を持つことができる。 MMとは対照的に、1または2つの状態が$O(m)$ラウンドで常に安定な状態に達することが知られている。 サイクルグラフ C_n の特別の場合、それぞれ MM と RMM において $\lceil n/2\rceil-1$ と $O(n^2)$ の強い境界と強い境界を証明する。 さらに、C_n 上の MM の安定な着色数は $\Theta(\Phi^n)$ で、$\Phi = (1+\sqrt{5})/2$ は黄金比であり、RMM は 2 である。 また,初期色付けにおける色に同意するノードの集合である勝利集合の最小サイズについて検討し,すべてのノードがその色を共有する色付けを終了させるプロセスについて検討する。 本稿では,MM と RMM の双方に対して,勝利集合の最小サイズに関する厳密な境界を示す。 さらに、ランダムな初期色付けのためにモデルを解析し、各ノードが独立に1つの確率$p$と白色で色付けされる。 いくつかのマーチンゲール解析と数え上げ引数を用いて、サイクルグラフ C_n 上の MM における青ノードの最終数は、それぞれ $(2p^2-p^3)n/(1-p+p^2)$ と pn であることを示す。 最後に, 理論的な知見を補完する実験を行い, 今後の研究で取り組むべき興味をそそるオープン問題や予想の提案にも繋がる。

関連論文リスト

• A Generalisation of Voter Model: Influential Nodes and Convergence Properties [5.4327243200369555]
  我々は有権者モデルの一般化を紹介し,研究する。 そこで本研究では,いくつかのラウンド後に期待されるブルーノード数を最大化するために,種子のブルーノードを選択する問題について検討する。 実世界のグラフデータおよび合成グラフデータに関する実験により,提案アルゴリズムが他のアルゴリズムより優れていることを示す。
  論文  参考訳（メタデータ） (2024-11-07T09:38:42Z)
• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Viral Marketing in Social Networks with Competing Products [23.48809201078124]
  ネットワーク内のレッドシードノードを選択するための時間近似アルゴリズムを提案する。 実世界および合成ネットワークにおける実験により,提案アルゴリズムが他のアルゴリズムより優れていることを示す。 特に、ノード数/エッジ数、最大外度、直径など、異なるグラフパラメータの観点から収束時間に関するいくつかの厳密な境界を証明します。
  論文  参考訳（メタデータ） (2023-12-25T21:59:15Z)
• Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
  オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。 本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
  論文  参考訳（メタデータ） (2023-10-21T18:38:13Z)
• Inferences on Mixing Probabilities and Ranking in Mixed-Membership Models [5.992878098797828]
  ネットワークデータは、経済や健康ネットワークを含む多くのビッグデータアプリケーションで広く利用されている。 本稿では,Degree-Corrected Mixed Membership (DCMM)モデルを用いてネットワークをモデル化する。 我々は、$boldsymbolpi_i(k)$sに対して、メンバシップ混合確率と他の関連する集団量の分布と信頼区間を得られるような、新しい有限サンプル展開を導出する。
  論文  参考訳（メタデータ） (2023-08-29T02:35:45Z)
• Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
  我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。 私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
  論文  参考訳（メタデータ） (2023-06-03T04:00:47Z)
• The joint node degree distribution in the Erd\H{o}s-R\'enyi network [0.0]
  ErdHos-R'enyiランダムグラフはノード次数分布の最も単純なモデルである。 本稿では,ErdHos-R'enyiグラフのノードごとの次数が多変量正規分布 MVN であるかどうかを検証することを目的とする。
  論文  参考訳（メタデータ） (2023-03-09T09:46:48Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討 我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
  論文  参考訳（メタデータ） (2022-10-05T22:52:00Z)
• Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs [62.52390282012508]
  我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。 提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。 また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-04T04:36:15Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。