論文の概要: Community Recovery in the Geometric Block Model
- arxiv url: http://arxiv.org/abs/2206.11303v1
- Date: Wed, 22 Jun 2022 18:10:49 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-24 14:40:34.630948
- Title: Community Recovery in the Geometric Block Model
- Title（参考訳）: 幾何学的ブロックモデルにおけるコミュニティリカバリ
- Authors: Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, Barna Saha
- Abstract要約: 幾何ブロックモデルにおけるコミュニティを検出するための単純な三角形計数アルゴリズムは、ほぼ最適であることを示す。
コミュニティ検出の最近の理論的および実践的な進歩に触発されたランダムなコミュニティモデルの自然な拡張でもある。
- 参考スコア（独自算出の注目度）: 46.05998148820958
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: To capture inherent geometric features of many community detection problems,
we propose to use a new random graph model of communities that we call a
\emph{Geometric Block Model}. The geometric block model builds on the
\emph{random geometric graphs} (Gilbert, 1961), one of the basic models of
random graphs for spatial networks, in the same way that the well-studied
stochastic block model builds on the Erd\H{o}s-R\'{en}yi random graphs. It is
also a natural extension of random community models inspired by the recent
theoretical and practical advancements in community detection. To analyze the
geometric block model, we first provide new connectivity results for
\emph{random annulus graphs} which are generalizations of random geometric
graphs. The connectivity properties of geometric graphs have been studied since
their introduction, and analyzing them has been difficult due to correlated
edge formation.
We then use the connectivity results of random annulus graphs to provide
necessary and sufficient conditions for efficient recovery of communities for
the geometric block model. We show that a simple triangle-counting algorithm to
detect communities in the geometric block model is near-optimal. For this we
consider two regimes of graph density.
In the regime where the average degree of the graph grows logarithmically
with number of vertices, we show that our algorithm performs extremely well,
both theoretically and practically. In contrast, the triangle-counting
algorithm is far from being optimum for the stochastic block model in the
logarithmic degree regime. We also look at the regime where the average degree
of the graph grows linearly with the number of vertices $n$, and hence to store
the graph one needs $\Theta(n^2)$ memory. We show that our algorithm needs to
store only $O(n \log n)$ edges in this regime to recover the latent
communities.
- Abstract（参考訳）: コミュニティ検出問題の多くに固有の幾何学的特徴を捉えるため,我々は,コミュニティのランダムグラフモデルを用いて,これを「emph{Geometric Block Model}」と呼ぶ。
幾何学ブロックモデルは、Erd\H{o}s-R\'{en}yiランダムグラフ上によく研究された確率ブロックモデルが構築されるのと同じように、空間ネットワークのランダムグラフの基本モデルの一つである 'emph{random geometry graphs} (Gilbert, 1961) の上に構築される。
コミュニティ検出の最近の理論的および実践的な進歩に触発されたランダムなコミュニティモデルの自然な拡張でもある。
幾何学的ブロックモデルを分析するために、まずランダム幾何グラフの一般化である \emph{random annulus graphs} に対する新たな接続結果を提供する。
幾何グラフの接続性は導入以来研究されており、エッジ形成の相関により解析は困難である。
次に,ランダムアニュラスグラフの接続結果を用いて,幾何学的ブロックモデルにおけるコミュニティの効率的な回復に必要な十分条件を提供する。
幾何ブロックモデルのコミュニティを検出する単純な三角計数アルゴリズムがほぼ最適であることを示す。
このため、グラフ密度の2つのレギュレーションを考える。
グラフの平均次数が頂点数と対数的に増加する体制において、我々のアルゴリズムは理論的にも実用的にも非常によく機能することを示す。
対照的に、三角数え上げアルゴリズムは対数次数法における確率的ブロックモデルに最適ではない。
また、グラフの平均次数は頂点数$n$で線形に増加するので、グラフを保存するためには$\Theta(n^2)$メモリが必要である。
我々のアルゴリズムは、潜伏するコミュニティを回復するために、この体制に$O(n \log n)$ edgeだけを格納する必要がある。
関連論文リスト
- A Survey of Geometric Graph Neural Networks: Data Structures, Models and
Applications [67.33002207179923]
本稿では、幾何学的GNNに関するデータ構造、モデル、および応用について調査する。
幾何学的メッセージパッシングの観点から既存のモデルの統一的なビューを提供する。
また、方法論開発と実験評価の後の研究を促進するために、アプリケーションと関連するデータセットを要約する。
論文 参考訳（メタデータ） (2024-03-01T12:13:04Z) - Contrastive Graph Clustering in Curvature Spaces [74.03252813800334]
本研究では,CONGREGATE という新しいグラフクラスタリングモデルを提案する。
幾何学的クラスタリングを支援するため、理論的に基底とした不均一曲率空間を構築した。
次に、拡張不要な再重み付きコントラスト的アプローチでグラフクラスタをトレーニングする。
論文 参考訳（メタデータ） (2023-05-05T14:04:52Z) - GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
本稿では,高次元分布をモデル化し,グラフスケルトンと整合した複雑な関係特徴構造を持つデータの新しい例を生成することの問題点を考察する。
提案するモデルは,タスクを2つのフェーズに分割することで,各データポイントのグラフ構造に制約されたデータ特徴を生成する問題に対処する。
第一に、与えられたグラフのノードに関連する機能の分布をモデル化し、第二に、ノードのフィーチャに条件付きでエッジ機能を補完する。
論文 参考訳（メタデータ） (2022-12-01T11:49:07Z) - Unveiling the Sampling Density in Non-Uniform Geometric Graphs [69.93864101024639]
グラフを幾何学グラフとみなす: ノードは基礎となる計量空間からランダムにサンプリングされ、その距離が指定された近傍半径以下であれば任意のノードが接続される。
ソーシャルネットワークでは、コミュニティは密集したサンプル領域としてモデル化でき、ハブはより大きな近傍半径を持つノードとしてモデル化できる。
我々は,未知のサンプリング密度を自己監督的に推定する手法を開発した。
論文 参考訳（メタデータ） (2022-10-15T08:01:08Z) - On the Power of Edge Independent Graph Models [22.085932117823738]
本研究では,エッジ独立乱数グラフモデルの限界について検討する。
有界重なり条件の下では、エッジ独立モデルは本質的に、高い三角形やその他の部分グラフ密度を持つグラフを生成する能力に制限されていることを示す。
論文 参考訳（メタデータ） (2021-10-29T19:12:14Z) - T-LoHo: A Bayesian Regularization Model for Structured Sparsity and
Smoothness on Graphs [0.0]
グラフ構造化データでは、構造化されたスパーシリティと滑らかさが団結する傾向にある。
グラフィカルな関係を持つ高次元パラメータに先立って提案する。
構造された空間と滑らかさを同時に検出するために使用します。
論文 参考訳（メタデータ） (2021-07-06T10:10:03Z) - Regularization of Mixture Models for Robust Principal Graph Learning [0.0]
D$次元データポイントの分布から主グラフを学習するために,Mixture Modelsの正規化バージョンを提案する。
モデルのパラメータは期待最大化手順によって反復的に推定される。
論文 参考訳（メタデータ） (2021-06-16T18:00:02Z) - Finding Geometric Models by Clustering in the Consensus Space [61.65661010039768]
本稿では,未知数の幾何学的モデル,例えばホモグラフィーを求めるアルゴリズムを提案する。
複数の幾何モデルを用いることで精度が向上するアプリケーションをいくつか提示する。
これには、複数の一般化されたホモグラフからのポーズ推定、高速移動物体の軌道推定が含まれる。
論文 参考訳（メタデータ） (2021-03-25T14:35:07Z) - Community detection and percolation of information in a geometric
setting [5.027571997864707]
疎系においてブロックモデルの理論を一般化する第一歩を踏み出す。
接続すべき二つの頂点の確率が距離の任意の関数である等質距離空間上の幾何学的ランダムグラフを考える。
我々は,モッセルとペレスにより,木上の情報の流れのモデルと幾何的な相似性を定義する。
論文 参考訳（メタデータ） (2020-06-28T11:23:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。