論文の概要: Listing Maximal k-Plexes in Large Real-World Graphs
- arxiv url: http://arxiv.org/abs/2202.08737v1
- Date: Thu, 17 Feb 2022 16:25:56 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-18 16:42:56.875051
- Title: Listing Maximal k-Plexes in Large Real-World Graphs
- Title（参考訳）: 大規模実世界グラフにおける最大k-プレックスの一覧
- Authors: Zhengren Wang, Yi Zhou, Mingyun Xiao and Bakhadyr Khoussainov
- Abstract要約: 大きなグラフで高密度なサブグラフをリストすることは、コミュニティ検出のような様々なネットワーク分析アプリケーションにおいて重要なタスクである。
本稿では、最大$k$-プレックスと最大$k$-プレックスを所定の大きさで列挙する研究線を継続する。
最初のコントリビューションはアルゴリズムemphListPlexで、$O*(gammaD)$のすべての最大$k$-plexesをリストアップします。
- 参考スコア（独自算出の注目度）: 5.85650819361755
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Listing dense subgraphs in large graphs plays a key task in varieties of
network analysis applications like community detection. Clique, as the densest
model, has been widely investigated. However, in practice, communities rarely
form as cliques for various reasons, e.g., data noise. Therefore, $k$-plex, --
graph with each vertex adjacent to all but at most $k$ vertices, is introduced
as a relaxed version of clique. Often, to better simulate cohesive communities,
an emphasis is placed on connected $k$-plexes with small $k$. In this paper, we
continue the research line of listing all maximal $k$-plexes and maximal
$k$-plexes of prescribed size. Our first contribution is algorithm
\emph{ListPlex} that lists all maximal $k$-plexes in $O^*(\gamma^D)$ time for
each constant $k$, where $\gamma$ is a value related to $k$ but strictly
smaller than 2, and $D$ is the degeneracy of the graph that is far less than
the vertex number $n$ in real-word graphs. Compared to the trivial bound of
$2^n$, the improvement is significant, and our bound is better than all
previously known results. In practice, we further use several techniques to
accelerate listing $k$-plexes of a given size, such as structural-based prune
rules, cache-efficient data structures, and parallel techniques. All these
together result in a very practical algorithm. Empirical results show that our
approach outperforms the state-of-the-art solutions by up to orders of
magnitude.
- Abstract（参考訳）: 大きなグラフで高密度なサブグラフをリストすることは、コミュニティ検出のような様々なネットワーク分析アプリケーションにおいて重要なタスクである。
最も密度の高いモデルであるクライクは広く研究されている。
しかし、実際には、データノイズなど、様々な理由でコミュニティが斜めに形成されることは滅多にない。
したがって、k$-plex、-graphは、最大$k$頂点を除いて全ての頂点に隣接し、リラックスしたcliqueバージョンとして導入される。
コヒーシブなコミュニティをよりよくシミュレートするために、接続された$k$-plexesに$k$を小さな$k$で強調することが多い。
本稿では,任意のサイズの最大$k$-plexes と最大$k$-plexes をリストアップする研究を継続する。
最初のコントリビューションはアルゴリズム \emph{listplex} で、各定数 $k$ に対して、最大$k$-plexes をリストアップします。 $o^*(\gamma^d)$ time ここで$\gamma$ は$k$ に関連する値ですが、2 より厳密に小さい値で、$d$ は実数グラフの頂点数 $n$ よりもはるかに小さいグラフの縮約です。
2^n$の自明なバウンドと比較すると、改善は重要であり、我々のバウンドはすべての既知の結果より優れている。
実際には、構造ベースのプルールール、キャッシュ効率のよいデータ構造、並列技術など、所定のサイズの$k$プレックスの一覧化を高速化するために、いくつかの手法を用いる。
これら全ては、非常に実用的なアルゴリズムをもたらす。
実証的な結果は、我々のアプローチが最先端のソリューションを最大で桁違いに上回っていることを示している。
関連論文リスト
- Efficient Top-k s-Biplexes Search over Large Bipartite Graphs [4.507351209412066]
二部グラフ解析において、$s$-ビスプレックスの列挙は基本的な問題である。
実世界のデータエンジニアリングでは、すべての$sビプレックスを見つけることは必要でも、計算的にも安価でもない。
単純な2n列挙アルゴリズムを破るMVBPを提案する。
FastMVBPは、いくつかのインスタンスで最大3桁のベンチマークアルゴリズムより優れている。
論文 参考訳（メタデータ） (2024-09-27T06:23:29Z) - A Faster Branching Algorithm for the Maximum $k$-Defective Clique Problem [18.720357905876604]
未分岐グラフの$k$-defective cliqueは、$G$は、最大で$k$の欠損エッジを持つほぼ完全なグラフを誘導する。
与えられたグラフから最大の$k$$-defective Cliqueを求める最大$k$-defective Clique問題は、社会的および生物学的ネットワーク分析のような多くのアプリケーションにおいて重要である。
論文 参考訳（メタデータ） (2024-07-23T15:40:35Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - 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) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth
regular graphs [0.0]
すべての次数$D ge 2$ of girth $> 5$に対して、QAOA$はQAOA$ on $G$よりも大きなカット率を持つことを示す。
任意の定数$p$に対して、すべてのグラフ上でQAOA$_p$と同様に動作する局所古典的MAX-CUTアルゴリズムが存在すると推測する。
論文 参考訳（メタデータ） (2021-01-14T09:17:20Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
スパースな ErdHos-R'enyi ランダムグラフにおいて,大きな独立集合を求めるアルゴリズム的タスクについて検討する。
低次アルゴリズムのクラスは、半最適サイズの独立した集合を見つけることができるが、それ以上は見つからないことを示す。
論文 参考訳（メタデータ） (2020-10-13T17:26:09Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Learning Bayesian Networks Under Sparsity Constraints: A Parameterized
Complexity Analysis [7.99536002595393]
本稿では,ネットワーク上あるいはそのモラル化されたグラフ上に制約を加える際に,最適なベイズネットワークの構造を学習する問題について検討する。
モラル化されたグラフに少なくとも$k$のエッジを持つ最適ネットワークを学習すると、おそらく$f(k)cdot |I|O(1)$-timeアルゴリズムが存在しない。
論文 参考訳（メタデータ） (2020-04-30T12:31:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。