論文の概要: odeN: Simultaneous Approximation of Multiple Motif Counts in Large Temporal Networks

• arxiv url: http://arxiv.org/abs/2108.08734v1
• Date: Thu, 19 Aug 2021 15:06:05 GMT
• ステータス: 処理完了
• システム内更新日: 2021-08-20 14:17:17.454329
• Title: odeN: Simultaneous Approximation of Multiple Motif Counts in Large Temporal Networks
• Title（参考訳）: odeN: 大規模時間ネットワークにおける複数モチーフ数の同時近似
• Authors: Ilie Sarpe and Fabio Vandin
• Abstract要約: 時間的モチーフを研究する際の主な合併症の1つは、構築できる多くのモチーフである。 そこで我々は,すべてのモチーフを正確に近似したサンプリングベースアルゴリズムodeNを提案する。
• 参考スコア（独自算出の注目度）: 7.025709586759655
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Counting the number of occurrences of small connected subgraphs, called temporal motifs, has become a fundamental primitive for the analysis of temporal networks, whose edges are annotated with the time of the event they represent. One of the main complications in studying temporal motifs is the large number of motifs that can be built even with a limited number of vertices or edges. As a consequence, since in many applications motifs are employed for exploratory analyses, the user needs to iteratively select and analyze several motifs that represent different aspects of the network, resulting in an inefficient, time-consuming process. This problem is exacerbated in large networks, where the analysis of even a single motif is computationally demanding. As a solution, in this work we propose and study the problem of simultaneously counting the number of occurrences of multiple temporal motifs, all corresponding to the same (static) topology (e.g., a triangle). Given that for large temporal networks computing the exact counts is unfeasible, we propose odeN, a sampling-based algorithm that provides an accurate approximation of all the counts of the motifs. We provide analytical bounds on the number of samples required by odeN to compute rigorous, probabilistic, relative approximations. Our extensive experimental evaluation shows that odeN enables the approximation of the counts of motifs in temporal networks in a fraction of the time needed by state-of-the-art methods, and that it also reports more accurate approximations than such methods.
• Abstract（参考訳）: 時間的モチーフと呼ばれる小さな連結部分グラフの出現数を数えることが、それらが表す事象の時刻にアノテートされたエッジを持つ時間的ネットワークの分析の基本的なプリミティブとなっている。 時間的モチーフの研究における主な合併症の1つは、限られた数の頂点や辺でも構築できるモチーフの多さである。 その結果、多くのアプリケーションでモチーフが探索分析に使われているため、ユーザーはネットワークの異なる側面を表現する複数のモチーフを反復的に選択して分析する必要がある。 この問題は、1つのモチーフでさえも解析が計算的に要求される大規模ネットワークにおいて悪化する。 解決策として、本研究では、同じ(静的な)トポロジ(三角形など)に対応する複数の時間的モチーフの発生数を同時に数える問題を提案し、研究する。 正確な数を計算する大きな時間的ネットワークが実現不可能であることを考えると,モチーフのすべての数の正確な近似を提供するサンプリングベースのアルゴリズムであるodenを提案する。 厳密で確率的、相対的な近似を計算するためにodenが要求するサンプル数に関する解析的境界を提供する。 実験により, 時間的ネットワークにおけるモチーフの数を, 最先端の手法が必要とする時間のごく一部で近似することが可能であり, また, それらの手法よりも正確な近似を報告できることが確認された。

関連論文リスト

• Accurate and Fast Estimation of Temporal Motifs using Path Sampling [5.114632024458956]
  モチーフと呼ばれる小さな部分グラフの数を数えることは、ソーシャルネットワークの分析とグラフマイニングの根本的な問題である。 本稿では,時間的経路サンプリングの新しい手法を用いて,この問題に対処するアルゴリズムTEACUPSを提案する。 数十億のエッジを持つBitcoinグラフの場合、TEACUPSは1分以内で実行され、正確なカウントアルゴリズムは1日以上かかる。
  論文  参考訳（メタデータ） (2024-09-13T16:48:39Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。 最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。 シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
  論文  参考訳（メタデータ） (2023-10-05T07:10:40Z)
• Scalable Motif Counting for Large-scale Temporal Graphs [25.90869257290865]
  大規模時間グラフにおける時間的モチーフを正確にカウントするための拡張性のある並列フレームワークを提案する。 提案手法に基づいて,ノード間並列戦略とノード内並列戦略の両方を特徴とする階層型並列フレームワークを設計する。 16の実世界の時間グラフデータセットに対する実験により,提案フレームワークの優位性と性能が示された。
  論文  参考訳（メタデータ） (2022-04-20T05:41:38Z)
• Novel Features for Time Series Analysis: A Complex Networks Approach [62.997667081978825]
  時系列データは、気候、経済、医療などいくつかの領域で広く使われている。 最近の概念的アプローチは、複雑なネットワークへの時系列マッピングに依存している。 ネットワーク分析は、異なるタイプの時系列を特徴付けるのに使うことができる。
  論文  参考訳（メタデータ） (2021-10-11T13:46:28Z)
• Temporal and Object Quantification Networks [95.64650820186706]
  複雑な関係時間事象を認識できる構造バイアスを持つニューロシンボリックネットワークを新たに提案する。 我々は、TOQ-Netsが、少量のデータから、トレーニング中に存在したものよりも多くのオブジェクトを含むシナリオ、入力シーケンスの時間的ワープまでを一般化できることを実証した。
  論文  参考訳（メタデータ） (2021-06-10T16:18:21Z)
• Frequent Pattern Mining in Continuous-time Temporal Networks [0.0]
  我々は,時間的ネットワークデータセットにおける頻繁な時間パターンの完全集合をマイニングするための一連のアルゴリズムを開発した。 3つの実世界のデータセットに対するアルゴリズムの実装は、提案アルゴリズムの実用性を証明する。
  論文  参考訳（メタデータ） (2021-05-12T02:47:24Z)
• Consistency of mechanistic causal discovery in continuous-time using Neural ODEs [85.7910042199734]
  ダイナミカルシステムの研究において,連続時間における因果的発見を検討する。 本稿では,ニューラルネットワークを用いた因果探索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-06T08:48:02Z)
• A Survey of Quantization Methods for Efficient Neural Network Inference [75.55159744950859]
  量子化は、必要なビット数を最小限に抑えるために、固定された離散数の集合に連続実数値を分散する問題である。 近年、コンピュータビジョン、自然言語処理、関連分野でのニューラルネットワークモデルの顕著な性能のために最前線に達しています。 浮動小数点表現から4ビット以下の低精度固定整数値への移行は、メモリフットプリントとレイテンシを16倍削減する可能性を秘めている。
  論文  参考訳（メタデータ） (2021-03-25T06:57:11Z)
• PRESTO: Simple and Scalable Sampling Techniques for the Rigorous Approximation of Temporal Motif Counts [7.025709586759655]
  時間的モチーフのカウントの厳密な近似を得るために,効率的かつスケーラブルなアルゴリズムを提案する。 私たちのアルゴリズムは、シンプルで効果的なサンプリングアプローチに基づいており、非常に大規模なデータセットに実用的です。
  論文  参考訳（メタデータ） (2021-01-18T16:35:12Z)
• Efficient Sampling Algorithms for Approximate Temporal Motif Counting (Extended Version) [24.33313864327473]
  時間的モチーフのインスタンス数を推定する汎用エッジサンプリング(ES)アルゴリズムを提案する。 また、エッジサンプリングとウェッジサンプリングを併用した改良されたEWSアルゴリズムを考案し、3頂点と3エッジの時間的モチーフをカウントする。 我々のアルゴリズムは、時間的モチーフカウントのための最先端サンプリング手法よりも効率が高く、精度が高く、スケーラビリティが高い。
  論文  参考訳（メタデータ） (2020-07-28T07:15:25Z)
• Consistency of a Recurrent Language Model With Respect to Incomplete Decoding [67.54760086239514]
  逐次言語モデルから無限長のシーケンスを受信する問題について検討する。 不整合に対処する2つの対策として、トップkと核サンプリングの一貫性のある変種と、自己終端の繰り返し言語モデルを提案する。
  論文  参考訳（メタデータ） (2020-02-06T19:56:15Z)

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

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