論文の概要: Mixed Integer Programming for Searching Maximum Quasi-Bicliques
- arxiv url: http://arxiv.org/abs/2002.09880v1
- Date: Sun, 23 Feb 2020 10:25:51 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-29 09:55:21.269693
- Title: Mixed Integer Programming for Searching Maximum Quasi-Bicliques
- Title（参考訳）: 最大準ユークリッド探索のための混合整数計画法
- Authors: Dmitry I. Ignatov, Polina Ivanova, Albina Zamaletdinova
- Abstract要約: 双部グラフの準双曲は、その「ほぼ」完備部分グラフである。
準斜め探索のための混合計画法 (MIP) に基づくいくつかのモデルを提案し, 検証した。
ビクラスタリングにインスパイアされた別のモデルが定式化され、テストされる。
- 参考スコア（独自算出の注目度）: 3.093890460224435
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper is related to the problem of finding the maximal quasi-bicliques
in a bipartite graph (bigraph). A quasi-biclique in the bigraph is its "almost"
complete subgraph. The relaxation of completeness can be understood variously;
here, we assume that the subgraph is a $\gamma$-quasi-biclique if it lacks a
certain number of edges to form a biclique such that its density is at least
$\gamma \in (0,1]$. For a bigraph and fixed $\gamma$, the problem of searching
for the maximal quasi-biclique consists of finding a subset of vertices of the
bigraph such that the induced subgraph is a quasi-biclique and its size is
maximal for a given graph. Several models based on Mixed Integer Programming
(MIP) to search for a quasi-biclique are proposed and tested for working
efficiency. An alternative model inspired by biclustering is formulated and
tested; this model simultaneously maximizes both the size of the quasi-biclique
and its density, using the least-square criterion similar to the one exploited
by triclustering \textsc{TriBox}.
- Abstract（参考訳）: 本論文は,二部グラフ(bigraph)における極大準双行数を求める問題に関連している。
複写の準二進法はその「ほぼ」完備部分グラフである。
ここで、その部分グラフが少なくとも$\gamma \in (0,1]$ となるような双斜体を形成するためのある数の辺を持たない場合、$\gamma$-quasi-biclique であると仮定する。
グラフと固定された$\gamma$の場合、極大準二進法の探索の問題は、誘導された部分グラフが準二進法であり、その大きさが与えられたグラフに対して最大となるような双進法の頂点の部分集合を見つけることである。
準斜め探索のための混合整数計画法 (MIP) に基づくモデルを提案し, 作業効率を検証した。
このモデルは、三重クラスタリング \textsc{tribox} によって悪用されたものと類似した最小二乗基準を用いて、準二次と密度の両方を同時に最大化する。
関連論文リスト
- Jaccard-constrained dense subgraph discovery [2.4511852052357628]
大きい対のジャカード類似係数を持つ高密度部分グラフを探索する。
我々は,我々のアルゴリズムが効率的であることを実験的に示し,合成データセットに基底真理を見つけ,実世界のデータセットから解釈可能な結果を提供する。
論文 参考訳（メタデータ） (2023-08-30T10:33:02Z) - Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。
我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。
平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
論文 参考訳（メタデータ） (2023-04-17T10:38:08Z) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。
本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。
実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文 参考訳（メタデータ） (2022-08-18T09:19:01Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - The Performance of the MLE in the Bradley-Terry-Luce Model in
$\ell_{\infty}$-Loss and under General Graph Topologies [76.61051540383494]
我々はBradley-Terry-Luceモデルの$ell_infty$推定誤差に関する新しい一般上限を導出する。
導出された境界は良好に機能し、場合によっては既知の結果よりもシャープであることを示す。
論文 参考訳（メタデータ） (2021-10-20T23:46:35Z) - Random Subgraph Detection Using Queries [29.192695995340653]
植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。
本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。
このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
論文 参考訳（メタデータ） (2021-10-02T07:41:17Z) - The Generalized Mean Densest Subgraph Problem [30.33731479053404]
1つのパラメータ$p$でパラメータ化された、高密度なサブグラフ対象の新しいファミリーを導入する。
我々の目的は、標準の高密度部分グラフ問題と特別な場合の最大$k$-coreの両方をキャプチャする。
我々の研究の大きな貢献は、理論と実践の両方において、密接な部分グラフに対する様々な種類の剥離アルゴリズムの性能を分析することである。
論文 参考訳（メタデータ） (2021-06-02T02:58:35Z) - Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
スパースな ErdHos-R'enyi ランダムグラフにおいて,大きな独立集合を求めるアルゴリズム的タスクについて検討する。
低次アルゴリズムのクラスは、半最適サイズの独立した集合を見つけることができるが、それ以上は見つからないことを示す。
論文 参考訳（メタデータ） (2020-10-13T17:26:09Z) - Mining Large Quasi-cliques with Quality Guarantees from Vertex
Neighborhoods [44.007522460918565]
密度の高い部分グラフをマイニングすることは、グラフマイニングタスクのスペクトルにおいて重要なプリミティブである。
実世界のグラフから非自明な大きさのクランプと準クランプをマイニングすることは、しばしば難しい問題ではないことを示す。
論文 参考訳（メタデータ） (2020-08-18T15:50:25Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。