論文の概要: Temporal Network Creation Games

• arxiv url: http://arxiv.org/abs/2305.07494v2
• Date: Sun, 21 May 2023 22:28:56 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-24 02:43:43.434530
• Title: Temporal Network Creation Games
• Title（参考訳）: 時間ネットワーク創造ゲーム
• Authors: Davide Bil\`o, Sarel Cohen, Tobias Friedrich, Hans Gawendowicz, Nicolas Klodt, Pascal Lenzner, George Skretas
• Abstract要約: 時間グラフでは、ノードの固定セットがあり、それらの間の接続は特定の時間ステップでのみ利用可能である。 これにより、このようなグラフ上のアルゴリズム上の問題が多く発生し、特に時間スパンナーを見つける問題が顕著である。 我々は、均衡ネットワークの収束と存在、最良のエージェント戦略の発見の複雑さ、均衡の質に関する結果を証明した。
• 参考スコア（独自算出の注目度）: 10.489101634786003
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Most networks are not static objects, but instead they change over time. This observation has sparked rigorous research on temporal graphs within the last years. In temporal graphs, we have a fixed set of nodes and the connections between them are only available at certain time steps. This gives rise to a plethora of algorithmic problems on such graphs, most prominently the problem of finding temporal spanners, i.e., the computation of subgraphs that guarantee all pairs reachability via temporal paths. To the best of our knowledge, only centralized approaches for the solution of this problem are known. However, many real-world networks are not shaped by a central designer but instead they emerge and evolve by the interaction of many strategic agents. This observation is the driving force of the recent intensive research on game-theoretic network formation models. In this work we bring together these two recent research directions: temporal graphs and game-theoretic network formation. As a first step into this new realm, we focus on a simplified setting where a complete temporal host graph is given and the agents, corresponding to its nodes, selfishly create incident edges to ensure that they can reach all other nodes via temporal paths in the created network. This yields temporal spanners as equilibria of our game. We prove results on the convergence to and the existence of equilibrium networks, on the complexity of finding best agent strategies, and on the quality of the equilibria. By taking these first important steps, we uncover challenging open problems that call for an in-depth exploration of the creation of temporal graphs by strategic agents.
• Abstract（参考訳）: ほとんどのネットワークは静的オブジェクトではなく、時間とともに変化する。 この観測は、過去数年間に時間グラフに関する厳密な研究を引き起こした。 時間グラフではノードの固定セットがあり、それらの間の接続は特定の時間ステップでのみ利用可能である。 このことは、時間的スパンナーを見つけるという問題、すなわち時間的パスを通じて全てのペアが到達可能であることを保証する部分グラフの計算など、このようなグラフ上のアルゴリズム上の多くの問題を引き起こす。 我々の知る限りでは、この問題の解決のための集中的なアプローチのみが知られている。 しかし、多くの現実世界のネットワークは中心的なデザイナーによって形成されず、代わりに多くの戦略エージェントの相互作用によって出現し進化する。 この観測は、ゲーム理論ネットワーク形成モデルに関する最近の集中的な研究の原動力である。 本研究は、時間グラフとゲーム理論ネットワーク形成という2つの最近の研究方向をまとめる。 この新たな領域への第一歩として、完全なテンポラリホストグラフが与えられ、そのノードに対応するエージェントが自発的にインシデントエッジを生成して、生成されたネットワーク内のテンポラリパスを介して、他のすべてのノードに到達できるようにします。 これは時間的スパンナーをゲームの平衡として生み出す。 我々は,均衡ネットワークへの収束と存在,最良のエージェント戦略の発見の複雑さ,および平衡の質についての結果を示す。 これらの最初の重要なステップを踏むことで、戦略エージェントによる時間グラフの作成を深く探究することを要求する、挑戦的なオープンな問題を明らかにする。

関連論文リスト

• Online Learning Of Expanding Graphs [14.952056744888916]
  本稿では,信号ストリームからグラフを拡張するためのオンラインネットワーク推論の問題に対処する。 ネットワークに加入したばかりのノードや,それまでのノードに対して,さまざまなタイプの更新を可能にする戦略を導入する。
  論文  参考訳（メタデータ） (2024-09-13T09:20:42Z)
• Using Time-Aware Graph Neural Networks to Predict Temporal Centralities in Dynamic Graphs [0.8057006406834466]
  De Bruijn Graph Neural Networks (DBGNN) の時系列データにおける時間的経路に基づく集中度予測への応用について検討する。 生物学的および社会システムからの13の時間グラフを用いて,我々のアプローチを実験的に評価した。
  論文  参考訳（メタデータ） (2023-10-24T14:23:10Z)
• Graph Structure from Point Clouds: Geometric Attention is All You Need [0.0]
  本稿では,グラフを学習空間内に構築し,関係性の流れを幾何学的に処理するアテンション機構を提案する。 我々は、トップジェットタグ付けのタスクにおいて、GravNetNormと呼ばれるこのアーキテクチャをテストし、タグ付け精度の競争力を示す。
  論文  参考訳（メタデータ） (2023-07-31T13:44:22Z)
• Learning to Identify Graphs from Node Trajectories in Multi-Robot Networks [15.36505600407192]
  本稿では,グローバル収束保証付きグラフトポロジを効率的に発見する学習ベースアプローチを提案する。 マルチロボット生成および群れ処理におけるグラフの同定におけるアプローチの有効性を実証する。
  論文  参考訳（メタデータ） (2023-07-10T07:09:12Z)
• Temporal Aggregation and Propagation Graph Neural Networks for Dynamic Representation [67.26422477327179]
  時間グラフは連続時間を通してノード間の動的相互作用を示す。 本研究では,周辺地域全体と時間的グラフ畳み込みの新たな手法を提案する。 提案するTAP-GNNは,予測性能とオンライン推論遅延の両面で,既存の時間グラフ手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2023-04-15T08:17:18Z)
• Evidential Temporal-aware Graph-based Social Event Detection via Dempster-Shafer Theory [76.4580340399321]
  ETGNN(Evidential Temporal-aware Graph Neural Network)を提案する。 ノードがテキストであり、エッジがそれぞれ複数の共有要素によって決定されるビュー固有グラフを構築する。 ビュー固有の不確実性を考慮すると、すべてのビューの表現は、明らかなディープラーニング(EDL)ニューラルネットワークを介してマス関数に変換される。
  論文  参考訳（メタデータ） (2022-05-24T16:22:40Z)
• Spatio-Temporal Joint Graph Convolutional Networks for Traffic Forecasting [75.10017445699532]
  近年、時間グラフモデリング問題として交通予測の定式化に焦点が移っている。 本稿では,道路網における交通予測の精度向上のための新しい手法を提案する。
  論文  参考訳（メタデータ） (2021-11-25T08:45:14Z)
• Temporal Graph Network Embedding with Causal Anonymous Walks Representations [54.05212871508062]
  本稿では,時間グラフネットワークに基づく動的ネットワーク表現学習のための新しいアプローチを提案する。 評価のために、時間的ネットワーク埋め込みの評価のためのベンチマークパイプラインを提供する。 欧州の大手銀行が提供した実世界のダウンストリームグラフ機械学習タスクにおいて、我々のモデルの適用性と優れた性能を示す。
  論文  参考訳（メタデータ） (2021-08-19T15:39:52Z)
• Spatio-Temporal Inception Graph Convolutional Networks for Skeleton-Based Action Recognition [126.51241919472356]
  我々はスケルトンに基づく行動認識のためのシンプルで高度にモジュール化されたグラフ畳み込みネットワークアーキテクチャを設計する。 ネットワークは,空間的および時間的経路から多粒度情報を集約するビルディングブロックを繰り返すことで構築される。
  論文  参考訳（メタデータ） (2020-11-26T14:43:04Z)
• Towards Deeper Graph Neural Networks [63.46470695525957]
  グラフ畳み込みは近傍の集約を行い、最も重要なグラフ操作の1つである。 いくつかの最近の研究で、この性能劣化は過度に滑らかな問題に起因している。 本研究では,大きな受容領域からの情報を適応的に組み込むディープ適応グラフニューラルネットワーク(DAGNN)を提案する。
  論文  参考訳（メタデータ） (2020-07-18T01:11:14Z)

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

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