論文の概要: Efficient Sampling Algorithms for Approximate Temporal Motif Counting (Extended Version)

• arxiv url: http://arxiv.org/abs/2007.14028v1
• Date: Tue, 28 Jul 2020 07:15:25 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-06 03:13:01.871422
• Title: Efficient Sampling Algorithms for Approximate Temporal Motif Counting (Extended Version)
• Title（参考訳）: 近似時間モチーフ計算のための効率的なサンプリングアルゴリズム(拡張版)
• Authors: Jingjing Wang and Yanhao Wang and Wenjun Jiang and Yuchen Li and Kian-Lee Tan
• Abstract要約: 時間的モチーフのインスタンス数を推定する汎用エッジサンプリング(ES)アルゴリズムを提案する。 また、エッジサンプリングとウェッジサンプリングを併用した改良されたEWSアルゴリズムを考案し、3頂点と3エッジの時間的モチーフをカウントする。 我々のアルゴリズムは、時間的モチーフカウントのための最先端サンプリング手法よりも効率が高く、精度が高く、スケーラビリティが高い。
• 参考スコア（独自算出の注目度）: 24.33313864327473
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: A great variety of complex systems ranging from user interactions in communication networks to transactions in financial markets can be modeled as temporal graphs, which consist of a set of vertices and a series of timestamped and directed edges. Temporal motifs in temporal graphs are generalized from subgraph patterns in static graphs which take into account edge orderings and durations in addition to structures. Counting the number of occurrences of temporal motifs is a fundamental problem for temporal network analysis. However, existing methods either cannot support temporal motifs or suffer from performance issues. In this paper, we focus on approximate temporal motif counting via random sampling. We first propose a generic edge sampling (ES) algorithm for estimating the number of instances of any temporal motif. Furthermore, we devise an improved EWS algorithm that hybridizes edge sampling with wedge sampling for counting temporal motifs with 3 vertices and 3 edges. We provide comprehensive analyses of the theoretical bounds and complexities of our proposed algorithms. Finally, we conduct extensive experiments on several real-world datasets, and the results show that our ES and EWS algorithms have higher efficiency, better accuracy, and greater scalability than the state-of-the-art sampling method for temporal motif counting.
• Abstract（参考訳）: 通信ネットワークにおけるユーザインタラクションから金融市場の取引まで、さまざまな複雑なシステムは、一連の頂点と一連のタイムスタンプと有向エッジからなる時間グラフとしてモデル化することができる。 時間グラフの時間的モチーフは、構造に加えてエッジ順序と持続時間を考慮した静的グラフのサブグラフパターンから一般化される。 時間的モチーフの発生回数を数えることは、時間的ネットワーク分析の基本的な問題である。 しかし、既存のメソッドは時間的モチーフをサポートできないか、パフォーマンスの問題に悩まされている。 本稿では,ランダムサンプリングによる時間的モチーフの近似計算に着目する。 まず,任意の時相モチーフのインスタンス数を推定する汎用エッジサンプリング(es)アルゴリズムを提案する。 さらに,エッジサンプリングとウェッジサンプリングをハイブリッド化し,3頂点と3辺の時間モチーフをカウントする改良ewsアルゴリズムを考案した。 提案するアルゴリズムの理論的境界と複雑さを包括的に解析する。 最後に,複数の実世界のデータセットについて広範な実験を行い,ESとEWSのアルゴリズムは時間的モチーフカウントのための最先端サンプリング手法よりも効率,精度,スケーラビリティが高いことを示した。

関連論文リスト

• Accurate and Fast Estimation of Temporal Motifs using Path Sampling [5.114632024458956]
  モチーフと呼ばれる小さな部分グラフの数を数えることは、ソーシャルネットワークの分析とグラフマイニングの根本的な問題である。 本稿では,時間的経路サンプリングの新しい手法を用いて,この問題に対処するアルゴリズムTEACUPSを提案する。 数十億のエッジを持つBitcoinグラフの場合、TEACUPSは1分以内で実行され、正確なカウントアルゴリズムは1日以上かかる。
  論文  参考訳（メタデータ） (2024-09-13T16:48:39Z)
• Temporal Aggregation and Propagation Graph Neural Networks for Dynamic Representation [67.26422477327179]
  時間グラフは連続時間を通してノード間の動的相互作用を示す。 本研究では,周辺地域全体と時間的グラフ畳み込みの新たな手法を提案する。 提案するTAP-GNNは,予測性能とオンライン推論遅延の両面で,既存の時間グラフ手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2023-04-15T08:17:18Z)
• Scalable Spatiotemporal Graph Neural Networks [14.415967477487692]
  グラフニューラルネットワーク(GNN)は、しばしば予測アーキテクチャのコアコンポーネントである。 ほとんどの時間前GNNでは、計算複雑性はグラフ内のリンクの回数のシーケンスの長さの2乗係数までスケールする。 本稿では,時間的・空間的両方のダイナミックスを効率的に符号化するスケーラブルなアーキテクチャを提案する。
  論文  参考訳（メタデータ） (2022-09-14T09:47:38Z)
• Scalable Motif Counting for Large-scale Temporal Graphs [25.90869257290865]
  大規模時間グラフにおける時間的モチーフを正確にカウントするための拡張性のある並列フレームワークを提案する。 提案手法に基づいて,ノード間並列戦略とノード内並列戦略の両方を特徴とする階層型並列フレームワークを設計する。 16の実世界の時間グラフデータセットに対する実験により,提案フレームワークの優位性と性能が示された。
  論文  参考訳（メタデータ） (2022-04-20T05:41:38Z)
• Multivariate Time Series Forecasting with Dynamic Graph Neural ODEs [65.18780403244178]
  動的グラフニューラル正規微分方程式(MTGODE)を用いた多変量時系列予測連続モデルを提案する。 具体的には、まず、時間進化するノードの特徴と未知のグラフ構造を持つ動的グラフに多変量時系列を抽象化する。 そして、欠落したグラフトポロジを補完し、空間的および時間的メッセージパッシングを統一するために、ニューラルODEを設計、解決する。
  論文  参考訳（メタデータ） (2022-02-17T02:17:31Z)
• Cluster-and-Conquer: A Framework For Time-Series Forecasting [94.63501563413725]
  本稿では,高次元時系列データを予測するための3段階フレームワークを提案する。 当社のフレームワークは非常に汎用的で,各ステップで時系列予測やクラスタリングが利用可能です。 単純な線形自己回帰モデルでインスタンス化されると、いくつかのベンチマークデータセットで最先端の結果が得られる。
  論文  参考訳（メタデータ） (2021-10-26T20:41:19Z)
• Novel Features for Time Series Analysis: A Complex Networks Approach [62.997667081978825]
  時系列データは、気候、経済、医療などいくつかの領域で広く使われている。 最近の概念的アプローチは、複雑なネットワークへの時系列マッピングに依存している。 ネットワーク分析は、異なるタイプの時系列を特徴付けるのに使うことができる。
  論文  参考訳（メタデータ） (2021-10-11T13:46:28Z)
• odeN: Simultaneous Approximation of Multiple Motif Counts in Large Temporal Networks [7.025709586759655]
  時間的モチーフを研究する際の主な合併症の1つは、構築できる多くのモチーフである。 そこで我々は,すべてのモチーフを正確に近似したサンプリングベースアルゴリズムodeNを提案する。
  論文  参考訳（メタデータ） (2021-08-19T15:06:05Z)
• PRESTO: Simple and Scalable Sampling Techniques for the Rigorous Approximation of Temporal Motif Counts [7.025709586759655]
  時間的モチーフのカウントの厳密な近似を得るために,効率的かつスケーラブルなアルゴリズムを提案する。 私たちのアルゴリズムは、シンプルで効果的なサンプリングアプローチに基づいており、非常に大規模なデータセットに実用的です。
  論文  参考訳（メタデータ） (2021-01-18T16:35:12Z)
• Multi-Temporal Convolutions for Human Action Recognition in Videos [83.43682368129072]
  複数の解像度で抽出できる新しい時間・時間的畳み込みブロックを提案する。 提案するブロックは軽量で,任意の3D-CNNアーキテクチャに統合可能である。
  論文  参考訳（メタデータ） (2020-11-08T10:40:26Z)
• From Static to Dynamic Node Embeddings [61.58641072424504]
  本稿では,時間的予測に基づくアプリケーションにグラフストリームデータを活用するための汎用フレームワークを提案する。 提案フレームワークは,適切なグラフ時系列表現を学習するための新しい手法を含む。 トップ3の時間モデルは常に新しい$epsilon$-graphの時系列表現を利用するモデルであることが分かりました。
  論文  参考訳（メタデータ） (2020-09-21T16:48:29Z)

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

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