147 problems

Let the stochastic block model have two equal-sized communities, with within-community and between-community edge probabilities $a/n$ and $b/n$, respectively. Weak recovery means o…

In the sparse symmetric stochastic block model, let $q$ be the number of equal-sized communities, let $a,b>0$ be the within-community and between-community edge parameters, and def…

Let a uniform hypergraph stochastic block model (HSBM) be a random uniform hypergraph whose vertices are assigned to communities and whose hyperedges appear independently according…

Fixed-point and spinodal-curve conjecture. (i) If $\lambda>1$, then $G$ has two fixed points, $0$ and $\alpha>0$; moreover, $0$ is unstable and $\alpha$ is stable. (ii) For…

Consider the two-community stochastic block model with equal-sized communities and edge probabilities $p=\alpha\frac{\log n}{n}$ and $q=\beta\frac{\log n}{n}$, where $\alpha>\beta$…

Let $a>0$ be the average-degree parameter and let $\rho$ be the noise parameter, with $\rho=\epsilon$ and $\epsilon\in[0,1/2]$. In the sparse regime $p=a/n$, an estimator…

Let $\mathcal{G}(n,a/n,b/n)$ be the sparse planted partition model with two equal-sized vertex classes, within-class edge probability $q=a/n$, and between-class edge probability…

Emergent-community conjecture. Communities are an emergent property of local network evolution: networks generated by local rules have finite $r_\kappa$, whereas their degree-prese…

Layer-size conjecture. For every $\alpha>-1$,

Consider a non-uniform hypergraph stochastic block model with hypergraph layers and a Bethe–Hessian method whose layer weights are chosen optimally as in Example 2 of the source. L…

Let a non-uniform hypergraph stochastic block model consist of multiple independent uniform hypergraph layers sharing a vertex set and community assignment. In the binary case, let…

Consider the stochastic block model with average degree $d$, signal parameter $\lambda$, and number of communities $q$. Weak recovery is nontrivial estimation of the community assi…

Consider the stochastic block model with parameters $d$, $\lambda$, and number of communities $q$, and let the Kesten–Stigum (KS) threshold be given by $d\lambda^2=1$. Abbe–Sandon'…

YLS24+'s conjecture. The same threshold remains valid when the average degrees $\lambda_\ell$ are constant.

Consider the problem of detecting a planted community in a dense bipartite graph, where the proposed max truncated degree test may be statistically optimal but is computationally i…

Consider the symmetric sparse stochastic block model with constant number of communities $q$, average degree $d$, signal parameter $\lambda$, spike prior $\pi$, and probability mat…

Emergence conjecture. Network communities are an emergent property of networks evolving with local rules.

Consider a collection of multiple correlated graphs, possibly with node attributes, and suppose that their edge sets and node attributes can be combined. Multi-graph aggregation co…

Consider correlated Gaussian mixture models with $n$ nodes, attribute dimension $d$, and correlation parameter $\rho$. Let ${\boldsymbol \sigma}$ denote the community assignment an…

Infinite-group recovery conjecture. In the extreme case $M\rightarrow\infty$, Theorem should still hold, and exact recovery of the clusters should be possible whenever the whole ne…

Degree-profiling conjecture. Replacing the community-recovery algorithm used in this work by the degree-profiling algorithm gives an efficient graph-matching algorithm in the gener…

Bethe-Hessian community-detection conjecture. Above the Kesten–Stigum threshold, the number of negative outlier eigenvalues of $H(\pm\sqrt{d})$ can consistently estimate the number…

Abbe–Baccelli–Sankararaman conjecture. The above impossibility result is tight: exact recovery should be possible whenever

Consider a stochastic block model in the sparse regime where the average degree is of constant order, and let the Kesten–Stigum threshold be $d_{\mathrm{KS}}=\lambda^{-2}$. ACKZ's…

Let $d$ be the average degree and let $d_{\tiny\textsf{\textup{KS}}}:=\lambda^{-2}$ denote the Kesten–Stigum threshold. DKMZ's conjecture. Above the Kesten–Stigum threshold,…