論文の概要: Multi-Stage Graph Peeling Algorithm for Probabilistic Core Decomposition
- arxiv url: http://arxiv.org/abs/2108.06094v1
- Date: Fri, 13 Aug 2021 07:06:32 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-16 13:12:37.047419
- Title: Multi-Stage Graph Peeling Algorithm for Probabilistic Core Decomposition
- Title（参考訳）: 確率的コア分解のためのマルチステージグラフピーリングアルゴリズム
- Authors: Yang Guo, Xuekui Zhang, Fatemeh Esfahani, Venkatesh Srinivasan, Alex
Thomo, Li Xing
- Abstract要約: 最近Esfahaniらは、グラフの剥離と中央極限定理(CLT)に基づく確率的コア分解アルゴリズムを発表した。
本稿では,前回のPAの前に2段階のデータスクリーニング処理を付加したマルチステージグラフ剥離アルゴリズム(M-PA)を提案する。
我々は,M-PAが従来のPAよりも効率的であり,適切に設定されたフィルタリングしきい値により,従来のPAと非常によく似た密度のサブグラフを生成することを示す。
- 参考スコア（独自算出の注目度）: 3.004067332389205
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Mining dense subgraphs where vertices connect closely with each other is a
common task when analyzing graphs. A very popular notion in subgraph analysis
is core decomposition. Recently, Esfahani et al. presented a probabilistic core
decomposition algorithm based on graph peeling and Central Limit Theorem (CLT)
that is capable of handling very large graphs. Their proposed peeling algorithm
(PA) starts from the lowest degree vertices and recursively deletes these
vertices, assigning core numbers, and updating the degree of neighbour vertices
until it reached the maximum core. However, in many applications, particularly
in biology, more valuable information can be obtained from dense
sub-communities and we are not interested in small cores where vertices do not
interact much with others. To make the previous PA focus more on dense
subgraphs, we propose a multi-stage graph peeling algorithm (M-PA) that has a
two-stage data screening procedure added before the previous PA. After removing
vertices from the graph based on the user-defined thresholds, we can reduce the
graph complexity largely and without affecting the vertices in subgraphs that
we are interested in. We show that M-PA is more efficient than the previous PA
and with the properly set filtering threshold, can produce very similar if not
identical dense subgraphs to the previous PA (in terms of graph density and
clustering coefficient).
- Abstract（参考訳）: 頂点が互いに密接な関係にある密集した部分グラフのマイニングは、グラフの解析において一般的なタスクである。
部分グラフ解析における非常に一般的な概念は核分解である。
最近、Esfahaniら。
グラフの剥離に基づく確率的コア分解アルゴリズムと、非常に大きなグラフを扱うことができる中央極限定理(CLT)を提示した。
彼らの提案するピーリングアルゴリズム(pa)は、最低次数頂点から始まり、これらの頂点を再帰的に削除し、コア数を割り当て、最大コアに達するまで隣接する頂点の次数を更新する。
しかし、多くの応用、特に生物学において、より貴重な情報は密集したサブコミュニティから得ることができ、頂点が他とあまり相互作用しない小さなコアには興味がない。
従来のpaをより密集したサブグラフに焦点を合わせるために,マルチステージグラフ剥離アルゴリズム(m-pa,multi-stage graph peeling algorithm)を提案する。従来のpaの前に2段階のデータスクリーニング手順を追加する。ユーザが定義したしきい値に基づいてグラフから頂点を取り除いた結果,グラフの複雑性をほとんど低減し,関心のあるサブグラフの頂点に影響を与えることなく,グラフの複雑さを低減できる。
我々は,M-PAが従来のPAよりも効率的であり,適切に設定されたフィルタリングしきい値により,前のPAと同一でない(グラフ密度とクラスタリング係数の点で)非常によく似た部分グラフが得られることを示す。
関連論文リスト
- Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
ノード分類タスクにおける大規模グラフの利用は、グラフニューラルネットワーク(GNN)の現実的な応用を妨げる
本稿では,GNNのグラフコアセットについて検討し,スペクトル埋め込みに基づくエゴグラフの選択により相互依存の問題を回避する。
我々のスペクトルグレディグラフコアセット(SGGC)は、数百万のノードを持つグラフにスケールし、モデル事前学習の必要性を排除し、低ホモフィリーグラフに適用する。
論文 参考訳（メタデータ） (2024-05-27T17:52:12Z) - Differentiable Proximal Graph Matching [40.41380102260085]
微分可能近位グラフマッチング(DPGM)と呼ばれる近位演算子に基づくグラフマッチングアルゴリズムを提案する。
アルゴリズム全体をグラフ親和性行列からノード対応の予測への微分可能な写像とみなすことができる。
数値実験により、PGMは様々なデータセット上で既存のグラフマッチングアルゴリズムより優れていることが示された。
論文 参考訳（メタデータ） (2024-05-26T08:17:13Z) - Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better [18.121514220195607]
クラスタ削除は、計算およびソーシャルネットワーク分析におけるNPハードグラフクラスタリングの目的である。
まず,2つの近似アルゴリズムの厳密な解析を行い,その近似保証を4から3に改善する。
補助グラフにおいて最大等級を優しく取り、その周囲にクラスタを形成することにより、両アルゴリズムを驚くほど単純な方法でデランドマイズすることができることを示す。
論文 参考訳（メタデータ） (2024-04-24T18:39:18Z) - An Effective Branch-and-Bound Algorithm with New Bounding Methods for
the Maximum $s$-Bundle Problem [9.400610985728441]
最大s束問題(英: Maximum s-Bundle Problem、MBP)は、与えられたグラフ内の最大s束を特定するタスクに対処する問題である。
本稿では,グラフ分割技術を利用した分割型アッパーバウンド(PUB)を導入し,より厳密なアッパーバウンドを実現する。
また,グラフ削減のための前処理において,初期下界とPUBを利用する新しいBnBアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-02-06T06:05:11Z) - Graph Signal Sampling for Inductive One-Bit Matrix Completion: a
Closed-form Solution [112.3443939502313]
グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。
キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。
オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
論文 参考訳（メタデータ） (2023-02-08T08:17:43Z) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。
第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
論文 参考訳（メタデータ） (2023-02-02T08:33:36Z) - Online Correlation Clustering for Dynamic Complete Signed Graphs [9.13755431537592]
動的完備グラフに対する相関クラスタリングの問題点を考察する。
相関クラスタリングのための [CALM+21] におけるオンライン近似アルゴリズムを用いる。
これは、グラフ編集操作の完全なセットを可能にする、動的グラフのための最初のオンラインアルゴリズムである。
論文 参考訳（メタデータ） (2022-11-13T19:36:38Z) - The Generalized Mean Densest Subgraph Problem [30.33731479053404]
1つのパラメータ$p$でパラメータ化された、高密度なサブグラフ対象の新しいファミリーを導入する。
我々の目的は、標準の高密度部分グラフ問題と特別な場合の最大$k$-coreの両方をキャプチャする。
我々の研究の大きな貢献は、理論と実践の両方において、密接な部分グラフに対する様々な種類の剥離アルゴリズムの性能を分析することである。
論文 参考訳（メタデータ） (2021-06-02T02:58:35Z) - Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
多層グラフクラスタリングは、グラフノードをカテゴリまたはコミュニティに分割することを目指しています。
与えられた多層グラフの層をクラスタリングに親しみやすい埋め込みを提案する。
実験の結果,本手法は著しい改善をもたらすことがわかった。
論文 参考訳（メタデータ） (2021-03-30T17:36:40Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。