論文の概要: Optimizing Reachability Sets in Temporal Graphs by Delaying
- arxiv url: http://arxiv.org/abs/2004.05875v2
- Date: Thu, 12 Nov 2020 16:59:54 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-24 11:30:18.190433
- Title: Optimizing Reachability Sets in Temporal Graphs by Delaying
- Title（参考訳）: 遅延による時間グラフの到達可能性セットの最適化
- Authors: Argyrios Deligkas and Igor Potapov
- Abstract要約: 時間グラフは、すべてのエッジが整数時間ラベルのセットに割り当てられる動的なグラフである。
本研究では、エッジの可用性の遅れに対応する時間ラベルの変化が、与えられたソースからの到達性セットにどのように影響するかを検討する。
- 参考スコア（独自算出の注目度）: 8.122270502556374
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A temporal graph is a dynamic graph where every edge is assigned a set of
integer time labels that indicate at which discrete time step the edge is
available. In this paper, we study how changes of the time labels,
corresponding to delays on the availability of the edges, affect the
reachability sets from given sources. The questions about reachability sets are
motivated by numerous applications of temporal graphs in network epidemiology,
which aim to minimise the spread of infection, and scheduling problems in
supply networks in manufacturing with the opposite objectives of maximising
coverage and productivity. We introduce control mechanisms for reachability
sets that are based on two natural operations of delaying. The first operation,
termed merging, is global and batches together consecutive time labels into a
single time label in the whole network simultaneously. This corresponds to
postponing all events until a particular time. The second, imposes independent
delays on the time labels of every edge of the graph. We provide a thorough
investigation of the computational complexity of different objectives related
to reachability sets when these operations are used. For the merging operation,
i.e. global lockdown effect, we prove NP-hardness results for several
minimization and maximization reachability objectives, even for very simple
graph structures. For the second operation, independent delays, we prove that
the minimization problems are NP-hard when the number of allowed delays is
bounded. We complement this with a polynomial-time algorithm for minimising the
reachability set in case of unbounded delays.
- Abstract（参考訳）: テンポラリグラフ(英: temporal graph)は、各辺が整数時間ラベルのセットに割り当てられた動的グラフで、どの離散時間ステップでエッジが利用可能かを示す。
本稿では,エッジの可用性の遅れに対応する時間ラベルの変化が,与えられたソースからの到達性セットに与える影響について検討する。
感染拡大を最小化することを目的としたネットワーク疫学における時間グラフの多岐にわたる応用と、カバー範囲と生産性の最大化という反対の目的を持つ製造におけるサプライネットワークの問題をスケジューリングすることによる。
遅延の2つの自然な操作に基づく到達可能性集合の制御機構を導入する。
マージと呼ばれる最初の操作はグローバルであり、連続したタイムラベルを同時にネットワーク全体で単一のタイムラベルにまとめる。
これは、特定の時間まで全てのイベントを延期することに対応する。
第2に、グラフのすべてのエッジのタイムラベルに独立した遅延を課す。
我々は,これらの操作を使用する場合の到達可能性集合に関連する異なる目的の計算複雑性について徹底的に検討する。
マージング操作、すなわちグローバルロックダウン効果では、非常に単純なグラフ構造であっても、いくつかの最小化および最大化到達性目的に対してNP硬度結果が証明される。
第2の動作, 独立遅延については, 許容遅延数が制限された場合, 最小化問題はNPハードであることが証明される。
非有界遅延の場合の到達可能性集合を最小化する多項式時間アルゴリズムでこれを補完する。
関連論文リスト
- Decentralized Optimization in Time-Varying Networks with Arbitrary Delays [22.40154714677385]
通信遅延によるネットワークの分散最適化問題を考察する。
そのようなネットワークの例としては、協調機械学習、センサーネットワーク、マルチエージェントシステムなどがある。
通信遅延を模倣するため、ネットワークに仮想非計算ノードを追加し、有向グラフを生成する。
論文 参考訳（メタデータ） (2024-05-29T20:51:38Z) - Multi-Scene Generalized Trajectory Global Graph Solver with Composite
Nodes for Multiple Object Tracking [61.69892497726235]
複合ノードメッセージパッシングネットワーク(CoNo-Link)は、超長いフレーム情報を関連付けるためのフレームワークである。
オブジェクトをノードとして扱う従来の方法に加えて、このネットワークは情報インタラクションのためのノードとしてオブジェクトトラジェクトリを革新的に扱う。
我々のモデルは、合成ノードを追加することで、より長い時間スケールでより良い予測を学習することができる。
論文 参考訳（メタデータ） (2023-12-14T14:00:30Z) - The Complexity of Envy-Free Graph Cutting [44.58084909019557]
我々は,異なる選好を持つエージェント間で,不均一なリソースの集合を公平に分割する問題を考察する。
我々は、リソースが連結グラフのエッジに対応するような設定に集中し、すべてのエージェントがこのグラフの連結片を割り当てなければならない。
問題はNP完全であり、エージェントの数とグラフ内のエッジの数という2つの自然な複雑さの尺度に関して、その複雑さを分析する。
論文 参考訳（メタデータ） (2023-12-12T07:54:30Z) - Temporal Aggregation and Propagation Graph Neural Networks for Dynamic
Representation [67.26422477327179]
時間グラフは連続時間を通してノード間の動的相互作用を示す。
本研究では,周辺地域全体と時間的グラフ畳み込みの新たな手法を提案する。
提案するTAP-GNNは,予測性能とオンライン推論遅延の両面で,既存の時間グラフ手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2023-04-15T08:17:18Z) - Direct Embedding of Temporal Network Edges via Time-Decayed Line Graphs [51.51417735550026]
時間的ネットワーク上での機械学習の方法は、一般的に2つの制限のうちの少なくとも1つを示す。
ネットワークのライングラフは,各インタラクションのノードを含むもので,インタラクション間の時間差に基づいて,このグラフのエッジを重み付けする。
実世界のネットワークにおける実験結果から,エッジ分類と時間リンク予測の両方において,本手法の有効性と有効性を示す。
論文 参考訳（メタデータ） (2022-09-30T18:24:13Z) - GraMeR: Graph Meta Reinforcement Learning for Multi-Objective Influence
Maximization [1.7311053765541482]
インフルエンス(IM)とは、ネットワーク内のシードノードと呼ばれるノードのサブセットを特定する問題である(グラフ)。
IMには、バイラルマーケティング、疫病対策、センサー配置、その他のネットワーク関連タスクなど、数多くの応用がある。
我々は、本質的および影響的アクティベーションの両方を扱うマルコフ決定プロセスとして、一般的なIM問題を開発する。
論文 参考訳（メタデータ） (2022-05-30T03:48:51Z) - Arch-Graph: Acyclic Architecture Relation Predictor for
Task-Transferable Neural Architecture Search [96.31315520244605]
Arch-Graphはタスク固有の最適アーキテクチャを予測するトランスファー可能なNASメソッドである。
Arch-Graphの転送性と,多数のタスクにわたる高いサンプル効率を示す。
わずか50モデルの予算の下で、2つの検索スペースで平均して0.16%と0.29%のアーキテクチャを見つけることができる。
論文 参考訳（メタデータ） (2022-04-12T16:46:06Z) - Disentangling the Computational Complexity of Network Untangling [2.127049691404299]
本稿では,Rozenshtein,Tatti,Gionisが導入したネットワークアンハングリング問題について検討する。
この問題は、複雑なネットワーク内のエンティティの相互作用を説明するアクティビティタイムラインの探索にデータマイニングの応用がある。
論文 参考訳（メタデータ） (2022-04-06T08:32:39Z) - Multivariate Time Series Forecasting with Dynamic Graph Neural ODEs [65.18780403244178]
動的グラフニューラル正規微分方程式(MTGODE)を用いた多変量時系列予測連続モデルを提案する。
具体的には、まず、時間進化するノードの特徴と未知のグラフ構造を持つ動的グラフに多変量時系列を抽象化する。
そして、欠落したグラフトポロジを補完し、空間的および時間的メッセージパッシングを統一するために、ニューラルODEを設計、解決する。
論文 参考訳（メタデータ） (2022-02-17T02:17:31Z) - Spatio-Temporal Joint Graph Convolutional Networks for Traffic
Forecasting [75.10017445699532]
近年、時間グラフモデリング問題として交通予測の定式化に焦点が移っている。
本稿では,道路網における交通予測の精度向上のための新しい手法を提案する。
論文 参考訳（メタデータ） (2021-11-25T08:45:14Z) - Efficient Temporal Piecewise-Linear Numeric Planning with Lazy
Consistency Checking [4.834203844100679]
本稿では,プランナがLP整合性チェックを可能な限り遅延的に計算できる手法を提案する。
また,時間依存ゴールチェックをより選択的に行うアルゴリズムを提案する。
結果として得られるプランナーは、より効率的であるだけでなく、最先端の時間数値とハイブリッドプランナーよりも優れています。
論文 参考訳（メタデータ） (2021-05-21T07:36:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。