論文の概要: BBK: a simpler, faster algorithm for enumerating maximal bicliques in large sparse bipartite graphs

• arxiv url: http://arxiv.org/abs/2405.04428v2
• Date: Fri, 24 May 2024 09:00:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-11 00:58:46.215872
• Title: BBK: a simpler, faster algorithm for enumerating maximal bicliques in large sparse bipartite graphs
• Title（参考訳）: BBK:大きなスパース二部グラフにおける最大双斜線を列挙するより単純で高速なアルゴリズム
• Authors: Alexis Baudin, Clémence Magnien, Lionel Tabourier,
• Abstract要約: 本稿では,二部グラフ内の最大双斜線を包括的に列挙するアルゴリズムを提案する。 BBK for Bipartite Bron-Kerboschと呼ばれるこのアルゴリズムは、Bron-Kerboschアルゴリズムの新しい拡張である。 最先端のアルゴリズムよりも高速で、既存の実装では管理できない巨大な二部グラフの列挙を可能にする。
• 参考スコア（独自算出の注目度）: 0.3277163122167434
• License:
• Abstract: Bipartite graphs are a prevalent modeling tool for real-world networks, capturing interactions between vertices of two different types. Within this framework, bicliques emerge as crucial structures when studying dense subgraphs: they are sets of vertices such that all vertices of the first type interact with all vertices of the second type. Therefore, they allow identifying groups of closely related vertices of the network, such as individuals with similar interests or webpages with similar contents. This article introduces a new algorithm designed for the exhaustive enumeration of maximal bicliques within a bipartite graph. This algorithm, called BBK for Bipartite Bron-Kerbosch, is a new extension to the bipartite case of the Bron-Kerbosch algorithm, which enumerates the maximal cliques in standard (non-bipartite) graphs. It is faster than the state-of-the-art algorithms and allows the enumeration on massive bipartite graphs that are not manageable with existing implementations. We analyze it theoretically to establish two complexity formulas: one as a function of the input and one as a function of the output characteristics of the algorithm. We also provide an open-access implementation of BBK in C++, which we use to experiment and validate its efficiency on massive real-world datasets and show that its execution time is shorter in practice than state-of-the art algorithms. These experiments also show that the order in which the vertices are processed, as well as the choice of one of the two types of vertices on which to initiate the enumeration have an impact on the computation time.
• Abstract（参考訳）: Bipartite Graphsは、2つの異なるタイプの頂点間の相互作用をキャプチャする、現実世界のネットワークのための一般的なモデリングツールである。 この枠組みの中では、高密度な部分グラフを研究する際、双斜線は重要な構造として現れる:それらは第1型のすべての頂点が第2型のすべての頂点と相互作用するような頂点の集合である。 そのため、類似した関心を持つ個人や類似した内容を持つWebページなど、ネットワークの近縁な頂点のグループを識別することができる。 本稿では,二部グラフ内の最大双斜線を包括的に列挙するアルゴリズムを提案する。 このアルゴリズムは BBK for Bipartite Bron-Kerbosch と呼ばれ、Bron-Kerbosch アルゴリズムの双極子の場合への新たな拡張であり、標準(非双極子)グラフの最大傾きを列挙する。 最先端のアルゴリズムよりも高速で、既存の実装では管理できない巨大な二部グラフの列挙を可能にする。 理論的には、入力の関数としての1と、アルゴリズムの出力特性の関数としての1の2つの複雑性公式を確立する。 また、C++におけるBBKのオープンアクセス実装も提供し、大規模な実世界のデータセット上でその効率を実験し、検証し、その実行時間が最先端のアルゴリズムよりも短いことを示す。 これらの実験は、頂点が処理される順序と、列挙を開始するための2種類の頂点の1つを選択することが計算時間に影響を及ぼすことを示した。

関連論文リスト

• A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
  このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。 我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
  論文  参考訳（メタデータ） (2024-03-21T11:57:16Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。 本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。 このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
  論文  参考訳（メタデータ） (2023-05-12T11:27:20Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。 第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
  論文  参考訳（メタデータ） (2023-02-02T08:33:36Z)
• Online Correlation Clustering for Dynamic Complete Signed Graphs [9.13755431537592]
  動的完備グラフに対する相関クラスタリングの問題点を考察する。 相関クラスタリングのための [CALM+21] におけるオンライン近似アルゴリズムを用いる。 これは、グラフ編集操作の完全なセットを可能にする、動的グラフのための最初のオンラインアルゴリズムである。
  論文  参考訳（メタデータ） (2022-11-13T19:36:38Z)
• Graph Spectral Embedding using the Geodesic Betweeness Centrality [76.27138343125985]
  本稿では、局所的な類似性、接続性、グローバル構造を教師なしで表現するグラフSylvester Embedding (GSE)を紹介する。 GSEはシルヴェスター方程式の解を用いて、ネットワーク構造と近傍の近接を1つの表現で捉える。
  論文  参考訳（メタデータ） (2022-05-07T04:11:23Z)
• Hierarchical Clustering: $O(1)$-Approximation for Well-Clustered Graphs [3.2901541059183432]
  階層クラスタリングのための2時間近似アルゴリズムを提案する。 本研究の意義は,合成データセットと実世界のデータセットの両方における経験的分析によって実証された。
  論文  参考訳（メタデータ） (2021-12-16T17:52:04Z)
• Bipartite Graph Embedding via Mutual Information Maximization [8.382665371140503]
  バイパートグラフの埋め込みは、様々なアプリケーションドメインで広く使われているため、多くの注目を集めている。 我々は,新しい局所的グローバルインフォマックス目標を導入することにより,このようなグローバル特性を捉えるためにbigiと呼ばれる2部グラフ埋め込みを提案する。 提案モデルは,top-kレコメンデーションとリンク予測のための様々なベンチマークデータセット上で評価される。
  論文  参考訳（メタデータ） (2020-12-10T04:03:39Z)
• Biclustering and Boolean Matrix Factorization in Data Streams [12.005731086591139]
  データストリームにおける二部グラフのクラスタリングとブール行列の分解について検討する。 ストリームを渡った後、サブ線形空間を用いてグラフの右側のクラスタの集合を復元するアルゴリズムを提案する。 合成データと実世界のデータに対するアルゴリズムの実装を評価する。
  論文  参考訳（メタデータ） (2020-12-05T23:02:43Z)
• 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)

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

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