論文の概要: Efficient Top-k s-Biplexes Search over Large Bipartite Graphs

• arxiv url: http://arxiv.org/abs/2409.18473v1
• Date: Fri, 27 Sep 2024 06:23:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-10 14:57:59.401110
• Title: Efficient Top-k s-Biplexes Search over Large Bipartite Graphs
• Title（参考訳）: 大規模二部グラフ上での効率的なトップks-ビスプレックス探索
• Authors: Zhenxiang Xu, Yiping Liu, Yi Zhou, Yimin Hao, Zhengren Wang,
• Abstract要約: 二部グラフ解析において、$s$-ビスプレックスの列挙は基本的な問題である。 実世界のデータエンジニアリングでは、すべての$sビプレックスを見つけることは必要でも、計算的にも安価でもない。 単純な2n列挙アルゴリズムを破るMVBPを提案する。 FastMVBPは、いくつかのインスタンスで最大3桁のベンチマークアルゴリズムより優れている。
• 参考スコア（独自算出の注目度）: 4.507351209412066
• License:
• Abstract: In a bipartite graph, a subgraph is an $s$-biplex if each vertex of the subgraph is adjacent to all but at most $s$ vertices on the opposite set. The enumeration of $s$-biplexes from a given graph is a fundamental problem in bipartite graph analysis. However, in real-world data engineering, finding all $s$-biplexes is neither necessary nor computationally affordable. A more realistic problem is to identify some of the largest $s$-biplexes from the large input graph. We formulate the problem as the {\em top-$k$ $s$-biplex search (TBS) problem}, which aims to find the top-$k$ maximal $s$-biplexes with the most vertices, where $k$ is an input parameter. We prove that the TBS problem is NP-hard for any fixed $k\ge 1$. Then, we propose a branching algorithm, named MVBP, that breaks the simple $2^n$ enumeration algorithm. Furthermore, from a practical perspective, we investigate three techniques to improve the performance of MVBP: 2-hop decomposition, single-side bounds, and progressive search. Complexity analysis shows that the improved algorithm, named FastMVBP, has a running time $O^*(\gamma_s^{d_2})$, where $\gamma_s<2$, and $d_2$ is a parameter much smaller than the number of vertex in the sparse real-world graphs, e.g. $d_2$ is only $67$ in the AmazonRatings dataset which has more than $3$ million vertices. Finally, we conducted extensive experiments on eight real-world and synthetic datasets to demonstrate the empirical efficiency of the proposed algorithms. In particular, FastMVBP outperforms the benchmark algorithms by up to three orders of magnitude in several instances.
• Abstract（参考訳）: 双部グラフにおいて、部分グラフが$s$2プレックス(英: $s$-biplex)であるとは、部分グラフの各頂点がすべてに隣接しているが、反対集合上の少なくとも$s$の頂点であることを意味する。 与えられたグラフから$s$-ビスプレックスを列挙することは、二部グラフ解析における根本的な問題である。 しかし、実世界のデータエンジニアリングでは、すべての$s$-biplexesを見つけることは必要でも、計算的にも安価でもない。 より現実的な問題は、大きな入力グラフから最大の$s$-biplexのいくつかを特定することである。 この問題は,最大値$s$-biplexesを最大値として,最大値$s$-biplexes($k$を入力パラメータとする)を求めるTBS問題として定式化する。 TBS問題は任意の固定$k\ge 1$に対してNPハードであることを証明する。 そこで我々は,単純な2^n$列挙アルゴリズムを破る分岐アルゴリズムMVBPを提案する。 さらに,2ホップ分解,単辺境界,プログレッシブサーチという,MVBPの性能向上のための3つの手法について検討した。 複素解析によると、改良されたアルゴリズムであるFastMVBPはランニングタイム$O^*(\gamma_s^{d_2})$を持ち、$\gamma_s<2$と$d_2$はスパースな現実世界グラフの頂点数よりもはるかに小さいパラメータである。 最後に,提案アルゴリズムの実証的効率を実証するため,実世界の8つのデータセットと合成データセットについて広範な実験を行った。 特に、FastMVBPは、いくつかのインスタンスで最大3桁のベンチマークアルゴリズムより優れている。

関連論文リスト

• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。 我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。 提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
  論文  参考訳（メタデータ） (2024-08-03T20:08:02Z)
• The Computational Complexity of Finding Stationary Points in Non-Convex Optimization [53.86485757442486]
  近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。 制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
  論文  参考訳（メタデータ） (2023-10-13T14:52:46Z)
• Fast Maximum $k$-Plex Algorithms Parameterized by Small Degeneracy Gaps [30.06993761032835]
  最大$k$-plex問題は、グラフマイニングやコミュニティ検出といったアプリケーションでは重要であるが、計算的に困難である。 我々は、入力グラフのサイズで最悪のランニング時間を持ち、$g_k(G)$で指数関数的な$g_k(G)$でパラメータ化された正確なアルゴリズムを示す。 我々はさらに議論を、より小さなパラメータ$cg_k(G)$、コミュニティの世代境界と最大$k$-plexのサイズの間のギャップにまで拡張します。
  論文  参考訳（メタデータ） (2023-06-23T01:28:24Z)
• Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An Index-based Approach [9.13755431537592]
  本稿では,相関クラスタリング問題を$O(mtimesleft(2+ alpha (G) right)+n)$から$O(m+n)$に近似する複雑性を,完全符号グラフに対して$varepsilon$とする。 提案手法は,元のアルゴリズムと同じ出力を与え,そのアルゴリズムをフルダイナミックな設定で実装できるようにする。
  論文  参考訳（メタデータ） (2023-01-01T10:57:36Z)
• Listing Maximal k-Plexes in Large Real-World Graphs [21.79007529359561]
  大きなグラフで高密度なサブグラフをリストすることは、コミュニティ検出のような様々なネットワーク分析アプリケーションにおいて重要なタスクである。 本稿では、最大$k$-プレックスと最大$k$-プレックスを所定の大きさで列挙する研究線を継続する。 私たちの最初のコントリビューションはアルゴリズムListPlexで、すべての最大$k$-plexesを$O*(gammaD)$ time for each constant $k$, where $gamma$ is a value to $k$ but strictly smaller than 2, and $D$ is the degeneracy of the graph that far less。
  論文  参考訳（メタデータ） (2022-02-17T16:25:56Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Classical algorithms for Forrelation [2.624902795082451]
  1対の$n$-bit Boolean 関数 $f$ と $g$ が与えられたとき、$f$ と $g$ のフーリエ変換の間の相関を推定する。 この問題は、クエリの複雑さの観点から最大の量子スピードアップをもたらすことが知られている。 グラフに基づく回帰問題は、任意の二部グラフに対して時間$O(n)$で解けることを示す。
  論文  参考訳（メタデータ） (2021-02-13T17:25:41Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm [100.11971836788437]
  固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。 我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
  論文  参考訳（メタデータ） (2020-02-12T03:40:52Z)

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

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