論文の概要: Exponential random graph models with soft clique constraints
- arxiv url: http://arxiv.org/abs/2608.30869v1
- Date: Mon, 31 Aug 2026 14:31:57 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-01 18:31:31.444613
- Title: Exponential random graph models with soft clique constraints
- Title（参考訳）: ソフトな斜め制約を持つ指数ランダムグラフモデル
- Authors: Yasmin Tousinejad, Vera Koponen,
- Abstract要約: 指数的ランダムグラフモデルを考えると、$G$が$H$よりも$r$cliquesが小さい場合、mathbfG_n$よりも$H$の方が高い確率を与える。
r$-傾きの少ないグラフがより高い確率で与えられる度合いは、正の重み$w$によって決定される。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Let $r\geq3$ be fixed, and let $\mathbf{G}_n$ be the set of all simple graphs with vertex set $[n]=\{1,\ldots,n\}$. We consider an exponential random graph model which gives higher probability to $G \in \mathbf{G}_n$ than to $H \in \mathbf{G}_n$ if $G$ has fewer $r$-cliques than $H$. But all graphs in $\mathbf{G}_n$ have positive probability. The degree to which graphs with fewer $r$-cliques are given higher probability is determined by a positive weight $w$. We prove that, asymptotically almost surely as $n \to \infty$, a random graph from $\mathbf{G}_n$ has a vertex partition into $r-1$ parts of roughly equal size, the density of edges between the parts is close to $1/2$, and for every $\varepsilon > 0$ the density of edges within any part is less than $\varepsilon$. The asymptotic structural properties are independent of the weight $w$ as long as it is positive. We also extend the result to the context of several clique sizes, each one with its own weight.
- Abstract（参考訳）: r\geq3$ を固定とし、$\mathbf{G}_n$ を頂点集合 $[n]=\{1,\ldots,n\}$ を持つすべての単純グラフの集合とする。
G$ が $H$ よりも$r$-cliques が少ない場合、$G \in \mathbf{G}_n$ よりも $H \in \mathbf{G}_n$ の方が高い確率を与える指数的ランダムグラフモデルを考える。
しかし、$\mathbf{G}_n$ のすべてのグラフは正の確率を持つ。
r$-傾きの少ないグラフがより高い確率で与えられる度合いは、正の重み$w$によって決定される。
漸近的にほぼ確実に$n \to \infty$, $\mathbf{G}_n$ のランダムグラフは、大まかに等しい大きさの $r-1$ の部分への頂点分割を持ち、各部分間の辺の密度は $1/2$ に近く、任意の部分内の辺の密度は $\varepsilon$ より小さいことを証明している。
漸近構造特性は、それが正である限り重量$w$とは独立である。
また、その結果をいくつかの斜めの大きさの文脈にまで拡張し、それぞれが自重を持つようにした。
関連論文リスト
- On the Capacity Region of Individual Key Rates in Vector Linear Secure Aggregation [55.126702858312456]
すべてのユーザがキーを保持する必要はないことを示し、それによって文学における最もよく知られた到達可能な領域を厳密に拡大する。
以上の結果から,各ユーザがキーを保持する必要はないという新たな事実が明らかになった。
論文 参考訳（メタデータ） (2026-01-06T18:34:07Z) - Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
複素ヒルベルト空間上で作用するエルミート作用素 $A$ を 2n$ とする。
A$ がパウリ拡大において小さな次数を持つとき、あるいは言い換えれば、$A$ は局所 $n$-量子ハミルトニアンである。
A$ が $d$-local, textiti.e., $deg(A)le d$ であるときは常に、次の離散化型不等式を持つことを示す。
論文 参考訳（メタデータ） (2025-09-15T14:26:11Z) - Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs [54.28273395444243]
我々は,モノトニック値 Omega (MVP) アルゴリズムが,差分を考慮した差分依存残差境界を$tildeOleft(left(sum_Delta_h(s,a)>0 fracH2 log K land MathttVar_maxtextc$。
論文 参考訳（メタデータ） (2025-06-06T20:33:57Z) - A note on estimating the dimension from a random geometric graph [2.3020018305241337]
グラフの隣接行列にアクセスする際に、基礎空間の次元$d$を推定する問題について検討する。
また、密度の条件がなければ、$d$の一貫した推定子は$n r_nd to infty$と$r_n = o(1)$が存在することを示す。
論文 参考訳（メタデータ） (2023-11-21T23:46:44Z) - 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) - Planted Bipartite Graph Detection [13.95780443241133]
ランダムグラフに隠れた二部グラフを検出するタスクについて検討する。
ヌル仮説の下では、このグラフは、エッジ密度$q$の$n$上のアードホスラーイランダムグラフの実現である。
k_mathsfR times k_mathsfL$ bipartite subgraph with edge density $p>q$。
論文 参考訳（メタデータ） (2023-02-07T18:18:17Z) - Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
本稿では, エッジ重み付き2つの完全グラフが潜在測地によって相関する問題について検討する。
近似最大極大推定器を導出し、高い確率で$pi*$の完全回復を確実に達成する。
副次的な発見として、[Ume88] の有望なスペクトルアルゴリズムが幾何モデルにおける最大可能性のさらなる近似として現れることを示す。
論文 参考訳（メタデータ） (2022-02-22T04:14:45Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
本稿では, ErdHos--R'enyi グラフに対するグラフマッチングやネットワークアライメントの問題を扱う。
これはグラフ同型問題のうるさい平均ケース版と見なすことができる。
論文 参考訳（メタデータ） (2021-10-11T05:07:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。