論文の概要: Community detection in sparse time-evolving graphs with a dynamical
Bethe-Hessian
- arxiv url: http://arxiv.org/abs/2006.04510v2
- Date: Mon, 26 Oct 2020 09:17:16 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-25 17:54:38.226241
- Title: Community detection in sparse time-evolving graphs with a dynamical
Bethe-Hessian
- Title(参考訳): 動的ベーテ・ヘシアンをもつスパース時間進化グラフにおけるコミュニティ検出
- Authors: Lorenzo Dall'Amico, Romain Couillet, Nicolas Tremblay
- Abstract要約: 本稿では、コミュニティ構造が時間とともに進化するスパース力学グラフにおけるコミュニティ検出の問題について考察する。
クラスラベルの正の相関と時間進化の利点を生かしたBethe-Hessian行列の拡張に基づく高速スペクトルアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 47.82639003096941
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This article considers the problem of community detection in sparse dynamical
graphs in which the community structure evolves over time. A fast spectral
algorithm based on an extension of the Bethe-Hessian matrix is proposed, which
benefits from the positive correlation in the class labels and in their
temporal evolution and is designed to be applicable to any dynamical graph with
a community structure. Under the dynamical degree-corrected stochastic block
model, in the case of two classes of equal size, we demonstrate and support
with extensive simulations that our proposed algorithm is capable of making
non-trivial community reconstruction as soon as theoretically possible, thereby
reaching the optimal detectability threshold and provably outperforming
competing spectral methods.
- Abstract(参考訳): 本稿では,コミュニティ構造が時間とともに進化するスパース動的グラフにおけるコミュニティ検出の問題について考察する。
そこで,bethe-hessian行列の拡張に基づく高速スペクトルアルゴリズムを提案する。このアルゴリズムはクラスラベルの正の相関と時間発展の利点を生かしており,コミュニティ構造を持つ任意の動的グラフに適用できるように設計されている。
動的次数補正確率ブロックモデルでは、等サイズの2クラスの場合、提案アルゴリズムは、理論上はできるだけ早く非自明なコミュニティ再構築が可能であり、最適な検出可能性しきい値に達し、競合するスペクトル法よりも優れた性能を持つことを示す。
関連論文リスト
- Learning Persistent Community Structures in Dynamic Networks via
Topological Data Analysis [2.615648035076649]
本稿では,コミュニティ間構造における時間的一貫性の整合性を考慮した新しいディープグラフクラスタリングフレームワークを提案する。
MFCは、ノード埋め込みを保存する行列分解に基づくディープグラフクラスタリングアルゴリズムである。
TopoRegは、時間間隔でコミュニティ間構造間のトポロジカルな類似性を維持するために導入された。
論文 参考訳(メタデータ) (2024-01-06T11:29:19Z) - Deep Equilibrium Assisted Block Sparse Coding of Inter-dependent
Signals: Application to Hyperspectral Imaging [71.57324258813675]
相互依存信号のデータセットは、列が強い依存を示す行列として定義される。
ニューラルネットワークは、事前に構造として機能し、基礎となる信号相互依存性を明らかにするために使用される。
ディープ・アンローリングとディープ・平衡に基づくアルゴリズムが開発され、高度に解釈可能で簡潔なディープ・ラーニング・ベース・アーキテクチャを形成する。
論文 参考訳(メタデータ) (2022-03-29T21:00:39Z) - Harnessing Heterogeneity: Learning from Decomposed Feedback in Bayesian
Modeling [68.69431580852535]
サブグループフィードバックを取り入れた新しいGPレグレッションを導入する。
我々の修正された回帰は、以前のアプローチと比べて、明らかにばらつきを減らし、したがってより正確な後続を減らした。
我々は2つの異なる社会問題に対してアルゴリズムを実行する。
論文 参考訳(メタデータ) (2021-07-07T03:57:22Z) - Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
結合ネットワークトポロジ推論は、異種グラフ信号から複数のグラフラプラシア行列を学習する標準的な問題を表す。
新規な構造化融合正規化に基づく一般グラフ推定器を提案する。
提案するグラフ推定器は高い計算効率と厳密な理論保証の両方を享受できることを示す。
論文 参考訳(メタデータ) (2021-03-05T04:42:32Z) - Amortized Probabilistic Detection of Communities in Graphs [49.46170819501234]
そこで我々は,アモータイズされたコミュニティ検出のためのシンプルなフレームワークを提案する。
我々はGNNの表現力と最近のアモータイズクラスタリングの手法を組み合わせる。
我々は、合成および実データセットに関するフレームワークから、いくつかのモデルを評価する。
論文 参考訳(メタデータ) (2020-10-29T16:18:48Z) - Non-Convex Exact Community Recovery in Stochastic Block Model [31.221745716673546]
近年,対称ブロックモデル(SBM)に基づくグラフのコミュニティ検出が注目されている。
この問題の対数的疎度構造において、提案した2段階法は、$mathcalO(nlog2n/loglog n)$ timeにおいて、情報理論の限界まで正確に2つのコミュニティを復元できることを示す。
また, 提案手法の有効性を実証し, 理論的発展を補完するために, 合成データセットと実データセットの両方で数値実験を行った。
論文 参考訳(メタデータ) (2020-06-29T07:03:27Z) - A unified framework for spectral clustering in sparse graphs [47.82639003096941]
正規化ラプラシア行列の便利なパラメータ化形式はスパースネットワークにおけるスペクトルクラスタリングに利用できることを示す。
また、この提案された行列と、現在一般的な非バックトラック行列であるベーテ・ヘッセン行列との間の重要な関係を示す。
論文 参考訳(メタデータ) (2020-03-20T10:58:37Z) - Generalized Kernel-Based Dynamic Mode Decomposition [0.0]
我々は、カーネルベースの動的モード分解と呼ばれる最近のアプローチを一般化する低階制約最適化とカーネルベースの計算に基づくアルゴリズムを考案する。
このアルゴリズムの特徴は近似精度の向上、数値シミュレーションによる証明、計算複雑性である。
論文 参考訳(メタデータ) (2020-02-11T13:50:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。