論文の概要: Community detection in censored hypergraph
- arxiv url: http://arxiv.org/abs/2111.03179v1
- Date: Thu, 4 Nov 2021 22:03:20 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-09 02:33:13.863436
- Title: Community detection in censored hypergraph
- Title（参考訳）: 検閲ハイパーグラフにおけるコミュニティ検出
- Authors: Mingao Yuan, Bin Zhao, Xiaofeng Zhao
- Abstract要約: 情報理論の観点から,検閲付き$m$-uniformハイパーグラフのコミュニティ検出について検討した。
本稿では,コミュニティ構造をしきい値まで正確に復元するスペクトル時間アルゴリズムを提案する。
また、1つのスペクトルアルゴリズムがしきい値を洗練しないかどうかの研究も興味深い。
- 参考スコア（独自算出の注目度）: 8.790193989856403
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Community detection refers to the problem of clustering the nodes of a
network (either graph or hypergrah) into groups. Various algorithms are
available for community detection and all these methods apply to uncensored
networks. In practice, a network may has censored (or missing) values and it is
shown that censored values have non-negligible effect on the structural
properties of a network. In this paper, we study community detection in
censored $m$-uniform hypergraph from information-theoretic point of view. We
derive the information-theoretic threshold for exact recovery of the community
structure. Besides, we propose a polynomial-time algorithm to exactly recover
the community structure up to the threshold. The proposed algorithm consists of
a spectral algorithm plus a refinement step. It is also interesting to study
whether a single spectral algorithm without refinement achieves the threshold.
To this end, we also explore the semi-definite relaxation algorithm and analyze
its performance.
- Abstract（参考訳）: コミュニティ検出とは、ネットワークのノード(グラフまたはハイパーグラフ)をグループにクラスタ化する問題を指す。
様々なアルゴリズムがコミュニティ検出に利用でき、これらの手法は無検閲ネットワークに適用できる。
実際には、ネットワークは、検閲された(または欠落した)値を持ち、検閲された値は、ネットワークの構造特性に無視できない効果を持つ。
本稿では,情報理論の観点から,検閲付き$m$-uniformハイパーグラフのコミュニティ検出について検討する。
コミュニティ構造の正確な回復のための情報理論しきい値を導出する。
さらに,コミュニティ構造をしきい値まで正確に復元する多項式時間アルゴリズムを提案する。
提案アルゴリズムはスペクトルアルゴリズムと改良ステップからなる。
また、改良のない単一のスペクトルアルゴリズムが閾値を達成できるかどうかも興味深い。
この目的のために,半定値緩和アルゴリズムを探索し,その性能解析を行う。
関連論文リスト
- BOURNE: Bootstrapped Self-supervised Learning Framework for Unified
Graph Anomaly Detection [50.26074811655596]
自己指導型自己学習(BOURNE)に基づく新しい統合グラフ異常検出フレームワークを提案する。
ノードとエッジ間のコンテキスト埋め込みを交換することで、ノードとエッジの異常を相互に検出できる。
BOURNEは、負のサンプリングを必要としないため、大きなグラフを扱う際の効率を高めることができる。
論文 参考訳（メタデータ） (2023-07-28T00:44:57Z) - Semi-supervised Community Detection via Structural Similarity Metrics [0.0]
本研究では,新しいノードのコミュニティラベルを推定することを目的とした,半教師付きコミュニティ検出問題について検討する。
本稿では,新しいノードとK$コミュニティ間の構造的類似度メトリック'を計算するアルゴリズムを提案する。
我々の知る限りでは、理論的な保証を提供する最初の半教師付きコミュニティ検出アルゴリズムである。
論文 参考訳（メタデータ） (2023-06-01T19:02:50Z) - ARISE: Graph Anomaly Detection on Attributed Networks via Substructure
Awareness [70.60721571429784]
サブ構造認識(ARISE)による属性付きネットワーク上の新しいグラフ異常検出フレームワークを提案する。
ARISEは、異常を識別するグラフのサブ構造に焦点を当てている。
実験により、ARISEは最先端の属性付きネットワーク異常検出(ANAD)アルゴリズムと比較して、検出性能が大幅に向上することが示された。
論文 参考訳（メタデータ） (2022-11-28T12:17:40Z) - Implicit models, latent compression, intrinsic biases, and cheap lunches
in community detection [0.0]
コミュニティ検出は、ネットワークをノードのクラスタに分割して、その大規模な構造を要約することを目的としている。
いくつかのコミュニティ検出手法は、確率的生成モデルを通じてクラスタリングの目的を明示的に導出する。
他の方法は記述的であり、特定のアプリケーションによって動機付けられた目的に応じてネットワークを分割する。
本稿では,コミュニティ検出対象,推論対象,記述対象とそれに対応する暗黙的ネットワーク生成モデルとを関連付けるソリューションを提案する。
論文 参考訳（メタデータ） (2022-10-17T15:38:41Z) - A Systematic Evaluation of Node Embedding Robustness [77.29026280120277]
本研究では,ノード埋め込みモデルのランダムおよび逆毒攻撃に対する経験的ロバスト性を評価する。
ネットワーク特性とノードラベルを用いて計算したエッジの追加,削除,再切り替えの戦略を比較した。
その結果,ノード分類はネットワーク再構成とは対照的に,高い性能劣化に悩まされていることがわかった。
論文 参考訳（メタデータ） (2022-09-16T17:20:23Z) - Community-based anomaly detection using spectral graph filtering [2.320417845168326]
本稿では,スペクトルグラフに基づくフィルタを用いたコミュニティベース異常検出アルゴリズムを提案する。
計算実験において、SpecFと呼ばれる提案された戦略は、さらに離散的な異常を識別する上で優れた性能を示した。
ブラジルのサン・ジョゼ・ドス・カンポス地区における新型コロナウイルスの感染状況について検討する。
論文 参考訳（メタデータ） (2022-01-24T20:02:22Z) - Overlapping community detection in networks via sparse spectral
decomposition [1.0660480034605242]
各ノードが複数のコミュニティに属することができるネットワークにおいて,重複するコミュニティメンバシップを推定する問題を考える。
本アルゴリズムは,反復しきい値を用いたスパース主部分空間推定に基づく。
アルゴリズムの固定点がブロックモデルの下での正しいノードメンバシップに対応することを示す。
論文 参考訳（メタデータ） (2020-09-20T07:31:09Z) - On the use of local structural properties for improving the efficiency
of hierarchical community detection methods [77.34726150561087]
本研究では,階層型コミュニティ検出の効率向上のために,局所構造ネットワーク特性をプロキシとして利用する方法について検討する。
また,ネットワークプルーニングの性能への影響を,階層的コミュニティ検出をより効率的にするための補助的手法として検証する。
論文 参考訳（メタデータ） (2020-09-15T00:16:12Z) - Community detection in networks using graph embeddings [0.615738282053772]
ベンチマークグラフ上のコミュニティを検出するために,いくつかのグラフ埋め込み手法をテストした。
埋め込み手法のパラメータが好適に選択された場合、性能は同等である。
この発見は、ネットワークを埋め込み、ポイントをグループ化する高い計算コストとともに、コミュニティ検出において、現在の埋め込み技術はネットワーククラスタリングアルゴリズムよりも改善されたものではないことを示唆している。
論文 参考訳（メタデータ） (2020-09-11T07:49:21Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。