論文の概要: Mining Large Quasi-cliques with Quality Guarantees from Vertex Neighborhoods

• arxiv url: http://arxiv.org/abs/2008.07996v1
• Date: Tue, 18 Aug 2020 15:50:25 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-27 22:24:02.420036
• Title: Mining Large Quasi-cliques with Quality Guarantees from Vertex Neighborhoods
• Title（参考訳）: 頂点近傍からの品質保証による大規模準斜晶の採掘
• Authors: Aritra Konar, and Nicholas D. Sidiropoulos
• Abstract要約: 密度の高い部分グラフをマイニングすることは、グラフマイニングタスクのスペクトルにおいて重要なプリミティブである。 実世界のグラフから非自明な大きさのクランプと準クランプをマイニングすることは、しばしば難しい問題ではないことを示す。
• 参考スコア（独自算出の注目度）: 44.007522460918565
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Mining dense subgraphs is an important primitive across a spectrum of graph-mining tasks. In this work, we formally establish that two recurring characteristics of real-world graphs, namely heavy-tailed degree distributions and large clustering coefficients, imply the existence of substantially large vertex neighborhoods with high edge-density. This observation suggests a very simple approach for extracting large quasi-cliques: simply scan the vertex neighborhoods, compute the clustering coefficient of each vertex, and output the best such subgraph. The implementation of such a method requires counting the triangles in a graph, which is a well-studied problem in graph mining. When empirically tested across a number of real-world graphs, this approach reveals a surprise: vertex neighborhoods include maximal cliques of non-trivial sizes, and the density of the best neighborhood often compares favorably to subgraphs produced by dedicated algorithms for maximizing subgraph density. For graphs with small clustering coefficients, we demonstrate that small vertex neighborhoods can be refined using a local-search method to ``grow'' larger cliques and near-cliques. Our results indicate that contrary to worst-case theoretical results, mining cliques and quasi-cliques of non-trivial sizes from real-world graphs is often not a difficult problem, and provides motivation for further work geared towards a better explanation of these empirical successes.
• Abstract（参考訳）: 高密度部分グラフのマイニングは、グラフマイニングタスクのスペクトル全体にわたって重要なプリミティブである。 本研究では,実世界のグラフ,すなわち重み付き次数分布と大規模クラスタリング係数の2つの繰り返し特性が,エッジ密度の高いかなり大きな頂点近傍の存在を正式に証明する。 この観察は、頂点近傍をスキャンし、各頂点のクラスタリング係数を計算し、そのようなサブグラフを出力するという、非常に単純なアプローチを示唆している。 このような方法の実装には、グラフマイニングにおいてよく研究されている問題であるグラフの三角形を数える必要がある。 頂点近傍には非自明な大きさの極大クランクが含まれており、最良近傍の密度はしばしば、サブグラフ密度を最大化する専用のアルゴリズムによって生成されるサブグラフと比較される。 小さいクラスタリング係数を持つグラフに対して、小さな頂点近傍は局所探索法を用いてより大きな斜めと近傾斜に洗練できることを示した。 以上の結果から,実世界のグラフから非自明な大きさの非自明なクレークや準クレークをマイニングすることは難しい問題ではなく,これらの経験的成功をよりよく説明するためのさらなる作業の動機となる。

関連論文リスト

• Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
  クラスタリングと単純化を統一する非負行列分解に基づく確率モデルを提案する。 ハードクラスタリングをソフトクラスタリングに緩和することにより、ハードクラスタリングの潜在的な問題をトラクタブルクラスタに緩和する。
  論文  参考訳（メタデータ） (2023-08-12T02:47:57Z)
• Tight and fast generalization error bound of graph embedding in metric space [54.279425319381374]
  非ユークリッド計量空間へのグラフ埋め込みは、既存の有界よりもはるかに少ない訓練データを持つユークリッド空間におけるグラフ埋め込みよりも優れていることを示す。 我々の新しい上限は、既存の上限よりもかなり強く速く、最大で$R$と$O(frac1S)$に指数関数できる。
  論文  参考訳（メタデータ） (2023-05-13T17:29:18Z)
• Contrastive Graph Clustering in Curvature Spaces [74.03252813800334]
  本研究では,CONGREGATE という新しいグラフクラスタリングモデルを提案する。 幾何学的クラスタリングを支援するため、理論的に基底とした不均一曲率空間を構築した。 次に、拡張不要な再重み付きコントラスト的アプローチでグラフクラスタをトレーニングする。
  論文  参考訳（メタデータ） (2023-05-05T14:04:52Z)
• Scalable and Effective Conductance-based Graph Clustering [9.938406925123722]
  グラフクラスタリングフレームワーク textitPCon を開発した。 既存のソリューションの多くをフレームワークに還元できることを示します。 本稿では,線形時間と空間の複雑さを考慮した2つの新しいアルゴリズムである textitPCon_core と emphPCon_de を提案する。
  論文  参考訳（メタデータ） (2022-11-22T12:45:27Z)
• Unveiling the Sampling Density in Non-Uniform Geometric Graphs [69.93864101024639]
  グラフを幾何学グラフとみなす: ノードは基礎となる計量空間からランダムにサンプリングされ、その距離が指定された近傍半径以下であれば任意のノードが接続される。 ソーシャルネットワークでは、コミュニティは密集したサンプル領域としてモデル化でき、ハブはより大きな近傍半径を持つノードとしてモデル化できる。 我々は,未知のサンプリング密度を自己監督的に推定する手法を開発した。
  論文  参考訳（メタデータ） (2022-10-15T08:01:08Z)
• A Note on Graph-Based Nearest Neighbor Search [4.38837720322254]
  高いクラスタリング係数は、グラフの最大強連結成分 (scc) に、q の k に近い近傍の大半を配置することを示している。 グラフに基づく探索アルゴリズムは,任意の地点を訪れると最大 SCC を横切ることが保証されている。
  論文  参考訳（メタデータ） (2020-12-21T02:18:05Z)
• LCS Graph Kernel Based on Wasserstein Distance in Longest Common Subsequence Metric Space [22.215852332444904]
  パスとウォークのより包括的類似性を計算するグラフカーネルを提案する。 また、グラフのより深い特徴を抽出するために、最適輸送理論と組み合わせる。 提案手法は多くの最先端グラフカーネル手法に勝る。
  論文  参考訳（メタデータ） (2020-12-07T11:59:14Z)
• 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)

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

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