論文の概要: A Generalisation of Voter Model: Influential Nodes and Convergence Properties

• arxiv url: http://arxiv.org/abs/2411.04564v1
• Date: Thu, 07 Nov 2024 09:38:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-08 19:37:18.761134
• Title: A Generalisation of Voter Model: Influential Nodes and Convergence Properties
• Title（参考訳）: 発声モデルの一般化:帰納的ノードと収束特性
• Authors: Abhiram Manohara, Ahad N. Zehmakan,
• Abstract要約: 我々は有権者モデルの一般化を紹介し,研究する。 そこで本研究では,いくつかのラウンド後に期待されるブルーノード数を最大化するために,種子のブルーノードを選択する問題について検討する。 実世界のグラフデータおよび合成グラフデータに関する実験により,提案アルゴリズムが他のアルゴリズムより優れていることを示す。
• 参考スコア（独自算出の注目度）: 5.4327243200369555
• License:
• Abstract: Consider an undirected graph G, representing a social network, where each node is blue or red, corresponding to positive or negative opinion on a topic. In the voter model, in discrete time rounds, each node picks a neighbour uniformly at random and adopts its colour. Despite its significant popularity, this model does not capture some fundamental real-world characteristics such as the difference in the strengths of individuals connections, individuals with neutral opinion on a topic, and individuals who are reluctant to update their opinion. To address these issues, we introduce and study a generalisation of the voter model. Motivating by campaigning strategies, we study the problem of selecting a set of seeds blue nodes to maximise the expected number of blue nodes after some rounds. We prove that the problem is NP- hard and provide a polynomial time approximation algorithm with the best possible approximation guarantee. Our experiments on real-world and synthetic graph data demonstrate that the proposed algorithm outperforms other algorithms. We also investigate the convergence properties of the model. We prove that the process could take an exponential number of rounds to converge. However, if we limit ourselves to strongly connected graphs, the convergence time is polynomial and the period (the number of states in convergence) divides the length of all cycles in the graph.
• Abstract（参考訳）: 各ノードが青か赤で、トピックに対する肯定的あるいは否定的な意見に対応する、ソーシャルネットワークを表す無向グラフGを考えてみましょう。 投票者モデルでは、個別のタイムラウンドで各ノードがランダムに隣人を選別し、その色を採用する。 非常に人気があるにもかかわらず、このモデルは、個人のつながりの強さの違い、トピックに関する中立的な意見を持つ個人、意見の更新に消極的な個人など、いくつかの基本的な現実世界の特徴を捉えていない。 これらの問題に対処するため、我々は有権者モデルの一般化を紹介し、研究する。 キャンペーン戦略により,いくつかのラウンド後に期待されるブルーノード数を最大化するために,種子のブルーノードの集合を選択するという課題について検討する。 この問題はNP-ハードであることが証明され、多項式時間近似アルゴリズムが最適な近似保証を提供する。 実世界のグラフデータおよび合成グラフデータに関する実験により,提案アルゴリズムが他のアルゴリズムより優れていることを示す。 また、モデルの収束性についても検討する。 我々は、このプロセスが収束するために指数的な数のラウンドを必要とすることを証明した。 しかし、自分自身を強連結グラフに制限すると、収束時間は多項式であり、周期(収束状態の数)はグラフのすべてのサイクルの長さを分割する。

関連論文リスト

• The Heterophilic Snowflake Hypothesis: Training and Empowering GNNs for Heterophilic Graphs [59.03660013787925]
  ヘテロフィリー・スノーフレーク仮説を導入し、ヘテロ親和性グラフの研究をガイドし、促進するための効果的なソリューションを提供する。 観察の結果,我々のフレームワークは多種多様なタスクのための多目的演算子として機能することがわかった。 さまざまなGNNフレームワークに統合することができ、パフォーマンスを詳細に向上し、最適なネットワーク深さを選択するための説明可能なアプローチを提供する。
  論文  参考訳（メタデータ） (2024-06-18T12:16:00Z)
• Viral Marketing in Social Networks with Competing Products [23.48809201078124]
  ネットワーク内のレッドシードノードを選択するための時間近似アルゴリズムを提案する。 実世界および合成ネットワークにおける実験により,提案アルゴリズムが他のアルゴリズムより優れていることを示す。 特に、ノード数/エッジ数、最大外度、直径など、異なるグラフパラメータの観点から収束時間に関するいくつかの厳密な境界を証明します。
  論文  参考訳（メタデータ） (2023-12-25T21:59:15Z)
• Temporal Aggregation and Propagation Graph Neural Networks for Dynamic Representation [67.26422477327179]
  時間グラフは連続時間を通してノード間の動的相互作用を示す。 本研究では,周辺地域全体と時間的グラフ畳み込みの新たな手法を提案する。 提案するTAP-GNNは,予測性能とオンライン推論遅延の両面で,既存の時間グラフ手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2023-04-15T08:17:18Z)
• Graph Convolutional Neural Networks with Diverse Negative Samples via Decomposed Determinant Point Processes [21.792376993468064]
  グラフ畳み込みネットワーク(GCN)はグラフ表現学習において大きな成功を収めている。 本稿では, 様々な負のサンプルを得るために, 品質多様性の分解を決定点過程に用いた。 本稿では,計算効率を向上させるための最短パスベース手法を提案する。
  論文  参考訳（メタデータ） (2022-12-05T06:31:31Z)
• Unveiling the Sampling Density in Non-Uniform Geometric Graphs [69.93864101024639]
  グラフを幾何学グラフとみなす: ノードは基礎となる計量空間からランダムにサンプリングされ、その距離が指定された近傍半径以下であれば任意のノードが接続される。 ソーシャルネットワークでは、コミュニティは密集したサンプル領域としてモデル化でき、ハブはより大きな近傍半径を持つノードとしてモデル化できる。 我々は,未知のサンプリング密度を自己監督的に推定する手法を開発した。
  論文  参考訳（メタデータ） (2022-10-15T08:01:08Z)
• Influence Maximization (IM) in Complex Networks with Limited Visibility Using Statistical Methods [2.320417845168326]
  影響文学(IM)問題はNP完全問題(NP完全問題)として知られており、時間内に解が存在しない。 この複雑さを改善するために提案された手法のほとんどは、グラフ全体が見えるという仮定に基づいている。 本研究では,リンク予測手法による現在の手法を擬似可視グラフに拡張する。
  論文  参考訳（メタデータ） (2022-08-28T07:55:54Z)
• Walk for Learning: A Random Walk Approach for Federated Learning from Heterogeneous Data [17.978941229970886]
  私たちは標準的アプリケーションとしてフェデレートラーニング(FL)に注目します。 FLの主な課題の1つは、ノードとパラメータサーバの間の通信ボトルネックである。 適応型ランダムウォーク学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-01T19:53:24Z)
• Factorizable Graph Convolutional Networks [90.59836684458905]
  本稿では,グラフに符号化された相互に絡み合った関係を明示的に解消する新しいグラフ畳み込みネットワーク(GCN)を提案する。 FactorGCNは単純なグラフを入力として取り、それをいくつかの分解グラフに分解する。 提案したFacterGCNは,合成および実世界のデータセットに対して質的かつ定量的に評価する。
  論文  参考訳（メタデータ） (2020-10-12T03:01:40Z)
• CatGCN: Graph Convolutional Networks with Categorical Node Features [99.555850712725]
  CatGCNはグラフ学習に適したノード機能である。 エンドツーエンドでCatGCNを訓練し、半教師付きノード分類でそれを実証する。
  論文  参考訳（メタデータ） (2020-09-11T09:25:17Z)
• Convergence and Stability of Graph Convolutional Networks on Large Random Graphs [22.387735135790706]
  グラフ畳み込みネットワーク(GCN)の特性をランダムグラフの標準モデル上で解析することによって検討する。 まず,GCNの連続的な収束について検討し,ノード数の増加について検討する。 ランダムグラフモデルの小さな変形に対するGCNの安定性を解析する。
  論文  参考訳（メタデータ） (2020-06-02T18:36:19Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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