論文の概要: Provable Overlapping Community Detection in Weighted Graphs

• arxiv url: http://arxiv.org/abs/2004.07150v2
• Date: Sun, 19 Apr 2020 17:42:13 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-13 03:03:15.386955
• Title: Provable Overlapping Community Detection in Weighted Graphs
• Title（参考訳）: 重み付きグラフにおける確率的重複コミュニティ検出
• Authors: Jimit Majmudar, Stephen Vavasis
• Abstract要約: 重み付きグラフにおける重なり合うコミュニティを、純粋ノードの仮定を明示的に定義することなく検出する証明可能な方法を提案する。 我々のアプローチは凸最適化に基づいており、多くの有用な理論的性質がすでに知られている。 人工および実世界のデータセット上でのアルゴリズムの成功を実証する。
• 参考スコア（独自算出の注目度）: 3.04585143845864
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Community detection is a widely-studied unsupervised learning problem in which the task is to group similar entities together based on observed pairwise entity interactions. This problem has applications in diverse domains such as social network analysis and computational biology. There is a significant amount of literature studying this problem under the assumption that the communities do not overlap. When the communities are allowed to overlap, often a pure nodes assumption is made, i.e. each community has a node that belongs exclusively to that community. This assumption, however, may not always be satisfied in practice. In this paper, we provide a provable method to detect overlapping communities in weighted graphs without explicitly making the pure nodes assumption. Moreover, contrary to most existing algorithms, our approach is based on convex optimization, for which many useful theoretical properties are already known. We demonstrate the success of our algorithm on artificial and real-world datasets.
• Abstract（参考訳）: コミュニティ検出(community detection)は、観察されたペアワイズなエンティティインタラクションに基づいて類似のエンティティをグループ化する、広く研究されている教師なし学習問題である。 この問題は、ソーシャルネットワーク分析や計算生物学といった様々な分野に応用されている。 コミュニティが重複しないという前提の下で,この問題を研究する文献が多数存在する。 コミュニティが重複することを許された場合、多くの場合、純粋なノードの仮定が行われ、すなわち、各コミュニティは、そのコミュニティに属するノードを持っている。 しかし、この仮定は実際には必ずしも満たされるとは限らない。 本稿では,重み付きグラフの重複コミュニティを,純粋ノードを明示的に仮定することなく検出する手法を提案する。 さらに,既存のアルゴリズムとは対照的に,提案手法は凸最適化に基づいており,多くの有用な理論的特性がすでに知られている。 人工および実世界のデータセット上でのアルゴリズムの成功例を示す。

関連論文リスト

• Enhancing Community Detection in Networks: A Comparative Analysis of Local Metrics and Hierarchical Algorithms [49.1574468325115]
  本研究は,地域間類似度指標を用いた地域検出の関連性を評価するために,同じ手法を用いている。 これらの指標の有効性は,異なるコミュニティサイズを持つ複数の実ネットワークにベースアルゴリズムを適用して評価した。
  論文  参考訳（メタデータ） (2024-08-17T02:17:09Z)
• A multi-core periphery perspective: Ranking via relative centrality [4.33459568143131]
  コミュニティとコア周辺は、広く研究されている2つのグラフ構造である。 グラフのコア周辺構造がコミュニティ構造を理解することに与える影響は、十分に利用されていない。 我々は,各コミュニティが密接な連結部分(中核)を持ち,残りの部分(周辺部)が疎い,基底真理コミュニティを持つグラフのための小説を紹介する。
  論文  参考訳（メタデータ） (2024-06-06T20:21:27Z)
• Semi-supervised Community Detection via Structural Similarity Metrics [0.0]
  本研究では,新しいノードのコミュニティラベルを推定することを目的とした,半教師付きコミュニティ検出問題について検討する。 本稿では,新しいノードとK$コミュニティ間の構造的類似度メトリック'を計算するアルゴリズムを提案する。 我々の知る限りでは、理論的な保証を提供する最初の半教師付きコミュニティ検出アルゴリズムである。
  論文  参考訳（メタデータ） (2023-06-01T19:02:50Z)
• Is it easier to count communities than find them? [82.90505487525533]
  コミュニティ構造が異なるモデル間の仮説テスト問題について考察する。 2つの選択肢間のテストは、コミュニティを見つけるのと同じくらい難しいことを示しています。
  論文  参考訳（メタデータ） (2022-12-21T09:35:19Z)
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection [0.0]
  コミュニティ検出は、ネットワークをノードのクラスタに分割して、その大規模な構造を要約することを目的としている。 いくつかのコミュニティ検出手法は、確率的生成モデルを通じてクラスタリングの目的を明示的に導出する。 他の方法は記述的であり、特定のアプリケーションによって動機付けられた目的に応じてネットワークを分割する。 本稿では,コミュニティ検出対象,推論対象,記述対象とそれに対応する暗黙的ネットワーク生成モデルとを関連付けるソリューションを提案する。
  論文  参考訳（メタデータ） (2022-10-17T15:38:41Z)
• Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks [61.2383572324176]
  本稿では,データマイニングにおける頻繁なアイテムセットマイニングの概念をよく知られたメメティック検索フレームワークに統合する,頻繁なアイテムセット駆動探索手法を提案する。 頻繁なアイテムセット組換え演算子を反復的に使用して、高品質なソリューションで頻繁に発生するアイテムセットに基づいた有望な子孫ソリューションを生成する。 特に、29個の新しい上界を発見し、以前の18個の最もよく知られた境界と一致する。
  論文  参考訳（メタデータ） (2022-01-18T11:16:40Z)
• QD-GCN: Query-Driven Graph Convolutional Networks for Attributed Community Search [54.42038098426504]
  QD-GCNは、ACS問題を解決するために、コミュニティ構造とノード属性を統一するエンドツーエンドフレームワークである。 本稿では、QD-GCNが既存の属性付きコミュニティ検索アルゴリズムを効率性と有効性の両方で上回ることを示す。
  論文  参考訳（メタデータ） (2021-04-08T07:52:48Z)
• Variational Embeddings for Community Detection and Node Representation [5.197034517903854]
  コミュニティ検出とノード表現のための変分埋め込みを共同学習するためのVECoDeRと呼ばれる効率的な生成モデルを提案する。 我々は、VECoDeRが3つのタスクすべてで多くの競合ベースラインを効果的に上回るいくつかのグラフデータセットを実証します。
  論文  参考訳（メタデータ） (2021-01-11T13:36:29Z)
• Mixed Membership Graph Clustering via Systematic Edge Query [22.77704627076251]
  この研究は、ほとんど不完全なグラフのクラスタリングノードを考慮する。 問題設定の下では、エッジに関する少数のクエリしか作成できないが、グラフ全体はオブザーバブルではない。 この問題は,限定アノテーションを用いた大規模データクラスタリング,限定された調査リソースによるコミュニティ検出,グラフトポロジ推論などに適用できる。
  論文  参考訳（メタデータ） (2020-11-25T19:19:05Z)
• 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)

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

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