論文の概要: Why the Metric Backbone Preserves Community Structure
- arxiv url: http://arxiv.org/abs/2406.03852v1
- Date: Thu, 6 Jun 2024 08:36:21 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-07 15:49:43.757201
- Title: Why the Metric Backbone Preserves Community Structure
- Title（参考訳）: メトリクスバックボーンがコミュニティ構造を保存する理由
- Authors: Maximilien Dreveton, Charbel Chucri, Matthias Grossglauser, Patrick Thiran,
- Abstract要約: よく分断されたコミュニティを持つネットワークでは、計量バックボーンは多くのコミュニティ間のエッジを保持する傾向にある。
計量バックボーンは,コミュニティの存在下で効率的なスペーサーであることを示す。
- 参考スコア（独自算出の注目度）: 8.097200145973389
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The metric backbone of a weighted graph is the union of all-pairs shortest paths. It is obtained by removing all edges $(u,v)$ that are not the shortest path between $u$ and $v$. In networks with well-separated communities, the metric backbone tends to preserve many inter-community edges, because these edges serve as bridges connecting two communities, but tends to delete many intra-community edges because the communities are dense. This suggests that the metric backbone would dilute or destroy the community structure of the network. However, this is not borne out by prior empirical work, which instead showed that the metric backbone of real networks preserves the community structure of the original network well. In this work, we analyze the metric backbone of a broad class of weighted random graphs with communities, and we formally prove the robustness of the community structure with respect to the deletion of all the edges that are not in the metric backbone. An empirical comparison of several graph sparsification techniques confirms our theoretical finding and shows that the metric backbone is an efficient sparsifier in the presence of communities.
- Abstract（参考訳）: 重み付きグラフの計量バックボーンは、全ペアの最短経路の和である。
これは、$u$と$v$の間の最短経路ではないすべてのエッジを除去することによって得られる。
広く分断されたコミュニティを持つネットワークでは、メートル法バックボーンは2つのコミュニティを結ぶ橋として機能するため、多くのコミュニティ間のエッジを保持する傾向にあるが、コミュニティが密集しているため、多くのコミュニティ内のエッジを削除する傾向にある。
これは、メトリックバックボーンがネットワークのコミュニティ構造を減らしたり破壊したりすることを示している。
しかし、これは、実際のネットワークのメートル法バックボーンが元のネットワークのコミュニティ構造をよく保存していることが示される以前の経験的な研究によってもたらされるものではない。
本研究は,地域社会と多種多様なランダムグラフの計量バックボーンを解析し,計量バックボーンにないすべてのエッジの削除に関して,コミュニティ構造のロバスト性を正式に証明する。
いくつかのグラフスペーシフィケーション手法の実証的な比較により、我々の理論的発見が確認され、計量バックボーンがコミュニティの存在下で効率的なスペーシであることが示される。
関連論文リスト
- Semi-supervised Community Detection via Structural Similarity Metrics [0.0]
本研究では,新しいノードのコミュニティラベルを推定することを目的とした,半教師付きコミュニティ検出問題について検討する。
本稿では,新しいノードとK$コミュニティ間の構造的類似度メトリック'を計算するアルゴリズムを提案する。
我々の知る限りでは、理論的な保証を提供する最初の半教師付きコミュニティ検出アルゴリズムである。
論文 参考訳（メタデータ） (2023-06-01T19:02:50Z) - DCC: A Cascade based Approach to Detect Communities in Social Networks [1.80476943513092]
この研究はグラノヴェッターの主張によって動機付けられ、強い結びつきが密接な連結ノードの中に存在することを示唆している。
我々は,カスケードを用いたemphDisjoint Community Detectionと呼ばれる新しい手法を導入した。
論文 参考訳（メタデータ） (2022-12-21T11:25:07Z) - Coarsening the Granularity: Towards Structurally Sparse Lottery Tickets [127.56361320894861]
ロッテリーチケット仮説 (LTH) は、密集したモデルには厳密なスパースワーク(すなわち当選チケット)が含まれており、完全な正確性に合わせるために単独で訓練できることを示した。
本稿では,構造的にスパースな入賞券が一般に有効に発見できるという,最初の肯定的な結果を示す。
具体的には、まず、重要と考えられるいくつかのチャネルで「再充填」された要素を返却し、次に非ゼロ要素を「再群」して、柔軟なグループ単位の構造パターンを作成します。
論文 参考訳（メタデータ） (2022-02-09T21:33:51Z) - Uncovering the Local Hidden Community Structure in Social Networks [20.467702194064525]
本稿では,元のネットワークからサンプリングしたサブグラフ上で各レイヤを反復的に検出・増強する手法を提案する。
本手法は, 崩壊したコミュニティと地域コミュニティが, サブグラフの1つのコミュニティと見なされる状況を回避することができることを示す。
論文 参考訳（メタデータ） (2021-12-08T04:07:19Z) - QD-GCN: Query-Driven Graph Convolutional Networks for Attributed
Community Search [54.42038098426504]
QD-GCNは、ACS問題を解決するために、コミュニティ構造とノード属性を統一するエンドツーエンドフレームワークである。
本稿では、QD-GCNが既存の属性付きコミュニティ検索アルゴリズムを効率性と有効性の両方で上回ることを示す。
論文 参考訳（メタデータ） (2021-04-08T07:52:48Z) - Amortized Probabilistic Detection of Communities in Graphs [49.46170819501234]
そこで我々は,アモータイズされたコミュニティ検出のためのシンプルなフレームワークを提案する。
我々はGNNの表現力と最近のアモータイズクラスタリングの手法を組み合わせる。
我々は、合成および実データセットに関するフレームワークから、いくつかのモデルを評価する。
論文 参考訳（メタデータ） (2020-10-29T16:18:48Z) - On the use of local structural properties for improving the efficiency
of hierarchical community detection methods [77.34726150561087]
本研究では,階層型コミュニティ検出の効率向上のために,局所構造ネットワーク特性をプロキシとして利用する方法について検討する。
また,ネットワークプルーニングの性能への影響を,階層的コミュニティ検出をより効率的にするための補助的手法として検証する。
論文 参考訳（メタデータ） (2020-09-15T00:16:12Z) - Integrating Network Embedding and Community Outlier Detection via
Multiclass Graph Description [15.679313861083239]
そこで本稿では,ノード埋め込みとアウトレーヤとコミュニティ検出を統合した非教師なしグラフ埋め込み手法(DMGD)を提案する。
DMGDにより検出された外れ値の数に関する理論的境界を示す。
我々の定式化は、外れ値、コミュニティ割り当て、ノード埋め込み関数の間の興味深いミニマックスゲームに起因する。
論文 参考訳（メタデータ） (2020-07-20T16:21:07Z) - Provable Overlapping Community Detection in Weighted Graphs [3.04585143845864]
重み付きグラフにおける重なり合うコミュニティを、純粋ノードの仮定を明示的に定義することなく検出する証明可能な方法を提案する。
我々のアプローチは凸最適化に基づいており、多くの有用な理論的性質がすでに知られている。
人工および実世界のデータセット上でのアルゴリズムの成功を実証する。
論文 参考訳（メタデータ） (2020-04-15T15:25:46Z) - Detecting Communities in Heterogeneous Multi-Relational Networks:A
Message Passing based Approach [89.19237792558687]
コミュニティは、ソーシャルネットワーク、生物学的ネットワーク、コンピュータおよび情報ネットワークを含むネットワークの共通の特徴である。
我々は,全同種ネットワークのコミュニティを同時に検出する効率的なメッセージパッシングに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-04-06T17:36:24Z) - Certified Robustness of Community Detection against Adversarial
Structural Perturbation via Randomized Smoothing [81.71105567425275]
本研究は, 対向構造摂動に対するコミュニティ検出の信頼性保証を初めて開発した。
このスムーズなコミュニティ検出手法は,任意のノード群を同一のコミュニティにグループ化する。
また,本手法を複数の実世界グラフ上で実験的に評価した。
論文 参考訳（メタデータ） (2020-02-09T18:39:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。