論文の概要: ONBRA: Rigorous Estimation of the Temporal Betweenness Centrality in Temporal Networks

• arxiv url: http://arxiv.org/abs/2203.00653v1
• Date: Tue, 1 Mar 2022 17:54:10 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-02 15:55:00.731805
• Title: ONBRA: Rigorous Estimation of the Temporal Betweenness Centrality in Temporal Networks
• Title（参考訳）: OnBRA:テンポラルネットワークにおける時間的相互中心性の厳密な推定
• Authors: Diego Santoro and Ilie Sarpe
• Abstract要約: ネットワーク分析では、ノード間の重心性はそのノードを訪れる最短経路のごく一部を非公式にキャプチャする。 時間ネットワークにおけるノードの時間差集中度値を推定するための最初のサンプリングベース近似アルゴリズムであるONBRAを提案する。
• 参考スコア（独自算出の注目度）: 0.76146285961466
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In network analysis, the betweenness centrality of a node informally captures the fraction of shortest paths visiting that node. The computation of the betweenness centrality measure is a fundamental task in the analysis of modern networks, enabling the identification of the most central nodes in such networks. Additionally to being massive, modern networks also contain information about the time at which their events occur. Such networks are often called temporal networks. The temporal information makes the study of the betweenness centrality in temporal networks (i.e., temporal betweenness centrality) much more challenging than in static networks (i.e., networks without temporal information). Moreover, the exact computation of the temporal betweenness centrality is often impractical on even moderately-sized networks, given its extremely high computational cost. A natural approach to reduce such computational cost is to obtain high-quality estimates of the exact values of the temporal betweenness centrality. In this work we present ONBRA, the first sampling-based approximation algorithm for estimating the temporal betweenness centrality values of the nodes in a temporal network, providing rigorous probabilistic guarantees on the quality of its output. ONBRA is able to compute the estimates of the temporal betweenness centrality values under two different optimality criteria for the shortest paths of the temporal network. In addition, ONBRA outputs high-quality estimates with sharp theoretical guarantees leveraging on the \emph{empirical Bernstein bound}, an advanced concentration inequality. Finally, our experimental evaluation shows that ONBRA significantly reduces the computational resources required by the exact computation of the temporal betweenness centrality on several real world networks, while reporting high-quality estimates with rigorous guarantees.
• Abstract（参考訳）: ネットワーク分析では、ノード間の重心性はそのノードを訪れる最短経路のごく一部を非公式にキャプチャする。 中間性中心性尺度の計算は、現代のネットワークの解析において基本的なタスクであり、そのようなネットワークにおける最も中央のノードの識別を可能にする。 大規模なネットワークに加えて、現代のネットワークにはイベントの発生時期の情報も含まれている。 このようなネットワークはしばしばテンポラルネットワークと呼ばれる。 時間的情報により、時間的ネットワーク(時間的ネットワーク)における間性中心性の研究は、静的ネットワーク(時間的情報を持たないネットワーク)よりもはるかに困難になる。 さらに、時間的中間性中心性の正確な計算は、計算コストが非常に高いため、中程度のネットワークでもしばしば実用的ではない。 このような計算コストを削減する自然なアプローチは、時間的相互中心性の正確な値の高品質な推定を得ることである。 本稿では,時間的ネットワークにおけるノードの時間的相互関係を推定する最初のサンプリングベース近似アルゴリズムであるonbraを提案する。 ONBRAは、時間的ネットワークの最短経路に対する2つの異なる最適基準の下で、時間的間隔中央値の推定を計算することができる。 加えて、ONBRA は高度集中不等式である 'emph{empirical Bernstein bound} を利用して、鋭い理論的保証を持つ高品質な推定を出力する。 最後に,本実験により,onbraは実世界のネットワーク上での時間的相互性中心性の正確な計算に必要な計算資源を大幅に削減すると同時に,厳密な保証によって高品質な推定を報告できることを示した。

関連論文リスト

• Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks [57.24087627267086]
  通信ネットワークのノード間で分散的に格納された凸関数の総和を最小化するタスクについて検討する。 この問題を解決するのに必要な分散通信数と(サブ)漸進計算の下位境界が確立されている。 我々は,これらの下界に適合する最初の最適アルゴリズムを開発し,既存の最先端技術と比較して理論性能を著しく向上させる。
  論文  参考訳（メタデータ） (2024-05-28T10:28:45Z)
• Node Centrality Approximation For Large Networks Based On Inductive Graph Neural Networks [2.4012886591705738]
  ネットワーク分析において、クローズネス中央度(CC)とブロードネス中央度(BC)が重要な指標である。 大規模なネットワーク上での実践的な実装は、その高速な複雑さのため、計算的に要求される。 本稿では,CNCA-IGEモデルを提案する。CNCA-IGEモデルは,CCやBCのメトリクスに基づいてノードをランク付けするインダクティブグラフエンコーダ・デコーダモデルである。
  論文  参考訳（メタデータ） (2024-03-08T01:23:12Z)
• 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)
• QuickCent: a fast and frugal heuristic for harmonic centrality estimation on scale-free networks [3.35083992351906]
  本稿では,ネットワーク集中度指数を近似する簡易かつ迅速な手法を提案する。 私たちのアプローチはQuickCentと呼ばれ、いわゆる高速かつ軽快な推論にインスパイアされています。 我々はQuickCentが精度で競争力のある見積もりをすることができることを示した。
  論文  参考訳（メタデータ） (2023-03-02T03:04:55Z)
• Semantic Strengthening of Neuro-Symbolic Learning [85.6195120593625]
  ニューロシンボリックアプローチは一般に確率論的目的のファジィ近似を利用する。 トラクタブル回路において,これを効率的に計算する方法を示す。 我々は,Warcraftにおける最小コストパスの予測,最小コスト完全マッチングの予測,スドクパズルの解法という3つの課題に対して,アプローチを検証した。
  論文  参考訳（メタデータ） (2023-02-28T00:04:22Z)
• Optimal Complexity in Non-Convex Decentralized Learning over Time-Varying Networks [8.860889476382594]
  時間変化ネットワークによる分散最適化は、機械学習の新たなパラダイムである。 大規模な深層トレーニングでは通信オーバーヘッドが大幅に削減され、特にノードの移動時の無線シナリオでは堅牢になる。
  論文  参考訳（メタデータ） (2022-11-01T15:37:54Z)
• Direct Embedding of Temporal Network Edges via Time-Decayed Line Graphs [51.51417735550026]
  時間的ネットワーク上での機械学習の方法は、一般的に2つの制限のうちの少なくとも1つを示す。 ネットワークのライングラフは,各インタラクションのノードを含むもので,インタラクション間の時間差に基づいて,このグラフのエッジを重み付けする。 実世界のネットワークにおける実験結果から,エッジ分類と時間リンク予測の両方において,本手法の有効性と有効性を示す。
  論文  参考訳（メタデータ） (2022-09-30T18:24:13Z)
• PRESTO: Simple and Scalable Sampling Techniques for the Rigorous Approximation of Temporal Motif Counts [7.025709586759655]
  時間的モチーフのカウントの厳密な近似を得るために,効率的かつスケーラブルなアルゴリズムを提案する。 私たちのアルゴリズムは、シンプルで効果的なサンプリングアプローチに基づいており、非常に大規模なデータセットに実用的です。
  論文  参考訳（メタデータ） (2021-01-18T16:35:12Z)
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks [56.084798078072396]
  ネットワーク幅と収束時間の両方で既知の理論境界を大幅に改善することにより、理論と実践のギャップを埋める一歩を踏み出します。 本研究では, サンプルサイズが2次幅で, 両者の時間対数で線形なネットワークに対して, 地球最小値への収束が保証されていることを示す。 私たちの分析と収束境界は、いつでも合理的なサイズの同等のRELUネットワークに変換できる固定アクティベーションパターンを備えたサロゲートネットワークの構築によって導出されます。
  論文  参考訳（メタデータ） (2021-01-12T00:40:45Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。 我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。 いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
  論文  参考訳（メタデータ） (2020-05-05T18:08:23Z)
• Asynchronous Decentralized Learning of a Neural Network [49.15799302636519]
  我々は、ARockと呼ばれる非同期コンピューティングフレームワークを利用して、分散シナリオでフィードフォワードニューラルネットワーク(SSFN)を推定する自己サイズ推定と呼ばれるディープニューラルネットワークを学習する。 非同期分散SSFNは1ノードのアクティベーションと一方の通信を許容することで通信ボトルネックを緩和し、通信オーバーヘッドを大幅に低減する。 実験結果において、非同期dSSFNと従来の同期dSSFNを比較し、特に通信ネットワークが疎い場合に、非同期dSSFNの競合性能を示す。
  論文  参考訳（メタデータ） (2020-04-10T15:53:37Z)

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

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