論文の概要: Disentangling the Computational Complexity of Network Untangling

• arxiv url: http://arxiv.org/abs/2204.02668v1
• Date: Wed, 6 Apr 2022 08:32:39 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-07 14:49:34.799098
• Title: Disentangling the Computational Complexity of Network Untangling
• Title（参考訳）: ネットワークアンタングリングの計算複雑性の解消
• Authors: Vincent Froese, Pascal Kunz, Philipp Zschoche
• Abstract要約: 本稿では,Rozenshtein,Tatti,Gionisが導入したネットワークアンハングリング問題について検討する。 この問題は、複雑なネットワーク内のエンティティの相互作用を説明するアクティビティタイムラインの探索にデータマイニングの応用がある。
• 参考スコア（独自算出の注目度）: 2.127049691404299
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the network untangling problem introduced by Rozenshtein, Tatti, and Gionis [DMKD 2021], which is a variant of Vertex Cover on temporal graphs -- graphs whose edge set changes over discrete time steps. They introduce two problem variants. The goal is to select at most $k$ time intervals for each vertex such that all time-edges are covered and (depending on the problem variant) either the maximum interval length or the total sum of interval lengths is minimized. This problem has data mining applications in finding activity timelines that explain the interactions of entities in complex networks. Both variants of the problem are NP-hard. In this paper, we initiate a multivariate complexity analysis involving the following parameters: number of vertices, lifetime of the temporal graph, number of intervals per vertex, and the interval length bound. For both problem versions, we (almost) completely settle the parameterized complexity for all combinations of those four parameters, thereby delineating the border of fixed-parameter tractability.
• Abstract（参考訳）: 離散時間ステップでエッジセットが変化する時間グラフ上のVertex Coverの変種であるRozenshtein, Tatti, and Gionis [DMKD 2021]によるネットワークアンハングリング問題について検討する。 2つの問題がある。 目標は、頂点毎に最大で$k$の時間間隔を選択することで、すべての時間辺がカバーされ、(問題変量に依存する)最大間隔長または区間長の総和が最小になる。 この問題は、複雑なネットワーク内のエンティティの相互作用を説明するアクティビティタイムラインの探索にデータマイニングの応用がある。 この問題のどちらの変種もNPハードである。 本稿では,頂点数,時間グラフの寿命,頂点ごとの間隔数,間隔長境界といったパラメータを含む多変量複雑性解析を開始する。 どちらの問題バージョンに対しても、これらの4つのパラメータの組合せのパラメータ化複雑性を完全に解決し、固定パラメータのトラクタビリティの境界を規定する。

関連論文リスト

• The Complexity of Envy-Free Graph Cutting [44.58084909019557]
  我々は,異なる選好を持つエージェント間で,不均一なリソースの集合を公平に分割する問題を考察する。 我々は、リソースが連結グラフのエッジに対応するような設定に集中し、すべてのエージェントがこのグラフの連結片を割り当てなければならない。 問題はNP完全であり、エージェントの数とグラフ内のエッジの数という2つの自然な複雑さの尺度に関して、その複雑さを分析する。
  論文  参考訳（メタデータ） (2023-12-12T07:54:30Z)
• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。 特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
  論文  参考訳（メタデータ） (2023-11-18T04:41:07Z)
• Fully-Connected Spatial-Temporal Graph for Multivariate Time-Series Data [50.84488941336865]
  完全時空間グラフニューラルネットワーク(FC-STGNN)という新しい手法を提案する。 グラフ構築のために、時間的距離に基づいて、すべてのタイムスタンプにセンサーを接続する減衰グラフを設計する。 グラフ畳み込みのために,移動プールGNN層を用いたFCグラフ畳み込みを考案し,ST依存性を効果的に把握し,効率的な表現を学習する。
  論文  参考訳（メタデータ） (2023-09-11T08:44:07Z)
• Temporal Aggregation and Propagation Graph Neural Networks for Dynamic Representation [67.26422477327179]
  時間グラフは連続時間を通してノード間の動的相互作用を示す。 本研究では,周辺地域全体と時間的グラフ畳み込みの新たな手法を提案する。 提案するTAP-GNNは,予測性能とオンライン推論遅延の両面で,既存の時間グラフ手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2023-04-15T08:17:18Z)
• Are uGLAD? Time will tell! [4.005044708572845]
  条件独立グラフ(CI)を用いた多変量時系列セグメンテーションのための新しい手法を提案する。 CIグラフは、ノード間の部分的相関を表す確率的グラフィカルモデルである。 身体活動モニタリングデータを用いて実験結果を実証した。
  論文  参考訳（メタデータ） (2023-03-21T07:46:28Z)
• TimesNet: Temporal 2D-Variation Modeling for General Time Series Analysis [80.56913334060404]
  時系列解析は、天気予報、異常検出、行動認識などの応用において非常に重要である。 従来の手法では、1D時系列から直接これを達成しようと試みていた。 複雑な経時的変化を、複数の経時的変化と経時的変化に明らかにする。
  論文  参考訳（メタデータ） (2022-10-05T12:19:51Z)
• Convolutional Neural Networks for Time-dependent Classification of Variable-length Time Series [4.068599332377799]
  時系列データは、観測過程の中断により、限られた時間範囲内でのみ取得されることが多い。 このような部分的時系列を分類するには、1)異なるタイムスタンプから引き出された可変長のデータを考慮する必要がある。 既存の畳み込みニューラルネットワークは、畳み込み後のグローバルプールを使用して長さ差をキャンセルする。 このアーキテクチャは、時間的相関関係全体を長いデータに組み込むことと、短いデータの特徴的崩壊を避けることのトレードオフに悩まされる。
  論文  参考訳（メタデータ） (2022-07-08T07:15:13Z)
• Triformer: Triangular, Variable-Specific Attentions for Long Sequence Multivariate Time Series Forecasting--Full Version [50.43914511877446]
  本稿では,高い効率と精度を確保するために,三角形,可変特性に着目した注意点を提案する。 我々はTriformerが精度と効率の両方で最先端の手法より優れていることを示す。
  論文  参考訳（メタデータ） (2022-04-28T20:41:49Z)
• Spatio-Temporal Joint Graph Convolutional Networks for Traffic Forecasting [75.10017445699532]
  近年、時間グラフモデリング問題として交通予測の定式化に焦点が移っている。 本稿では,道路網における交通予測の精度向上のための新しい手法を提案する。
  論文  参考訳（メタデータ） (2021-11-25T08:45:14Z)
• Event2Graph: Event-driven Bipartite Graph for Multivariate Time-series Anomaly Detection [25.832983667044708]
  本稿では,時系列間の依存性を符号化する動的二部グラフ構造を提案する。 この設計に基づいて、時系列間の関係はイベントノードへの動的接続を通じて明示的にモデル化できる。
  論文  参考訳（メタデータ） (2021-08-15T17:50:37Z)
• Optimizing Reachability Sets in Temporal Graphs by Delaying [8.122270502556374]
  時間グラフは、すべてのエッジが整数時間ラベルのセットに割り当てられる動的なグラフである。 本研究では、エッジの可用性の遅れに対応する時間ラベルの変化が、与えられたソースからの到達性セットにどのように影響するかを検討する。
  論文  参考訳（メタデータ） (2020-04-13T11:36:52Z)

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

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