1. New models and algorithms

Adding loops to SBM
Problem 1.1.
[Emmanuel Abbe] Realworld networks are likely to have many small loops (e.g. friends introduce their friends to each other) but this feature is not captured by the SBM. One proposed model to capture this is as follows. Fix parameters $t \in [0,1]$ and $\tau > 0$. Let $\mathcal{D}_{+}$ and $\mathcal{D}_{}$ be two (highdimensional) Gaussian distributions. For each vertex $u$, randomly choose a community assignment $x_u \in \{+,\}$ and sample $y_u \sim \mathcal{D}_{x_u}$. For each pair of vertices $u,v$, decide whether to include edge $(u,v)$ as follows. With probability $t$, decide based on the usual SBM. With probability $1t$, add the edge iff $\y_u  y_v\ \le \tau$. More generally, $\tau_{uv}$ could depend on the relative community status $x_u x_v$. 
Triangle closure
Problem 1.2.
[Cris Moore] Let $G \sim G_{n,p}$ with $p = \Theta(1)/n$. For each pair of vertices at distance 2, add an edge between them with probability $q$. Call the resulting graph $H$. Is it possible to recover $G$ from $H$? If $G$ is instead drawn from the SBM, is it possible to recover the communities from $H$? Is the threshold the same or different? 
Graph localization
Problem 1.3.
[Andrea Montanari] The following graph localization problem is a nonmean field model, which means that many standard tools from statistical physics do not apply. Let $R \subseteq \mathbb{R}^d$ and let $x_1, \ldots, x_n$ be drawn i.i.d. from the uniform distribution on $R$. For each $i,j$, observe $$Y_{ij} = \left\{ \begin{array}{cl}\x_i  x_j\^2 + z_{ij} & \text{if } \x_i  x_j\ \le \rho \\ * & \text{otherwise} \end{array} \right.$$ where $z_{ij}$ is noise. The goal is to recover the values $\x_i  x_j\^2$. 
Iterative plurality
Problem 1.4.
[Luca Trevisan] Let $G \sim \mathrm{SBM}$. Consider the following algorithm. Initialize each vertex to a random color from $[k]$. Repeatedly update each node’s color to the plurality of its neighbors. Are there any conditions under which this is guaranteed to converge to a partition that is correlated with the true communities? 
Projective sampling scheme for sparse graphs
Problem 1.5.
[Victor Veitch] For each $n$, let $\mathcal{D}_n$ be a distribution over graphs of $n$ vertices. A projective sampling scheme is as follows. For any $k < n$ we have a procedure to, given a sample from $\mathcal{D}_n$, choose $k$ vertices so that the induced subgraph is distributed according to $\mathcal{D}_k$. We would like interesting examples of such sampling schemes for sparse graphs. More generally, we may not require the parameter $n$ to be the number of vertices. One example is taking a subbox for random geometric graphs. Graphons use the sampling scheme of selecting $k$ vertices uniformly at random. 
Node vs. edge information
Problem 1.6.
[Elchanan Mossel] Some realworld graphs (e.g. facebook) have information both on the nodes and on the edges. Can you quantify how much information is contained in the nodes versus in the edges? An example model is as follows. Take a metric space $(X,d)$. Nodes are sampled from $X$, and each $x \in X$ has features $f(x)$. The probability of edge $(x,y)$ depends on $d(x,y)$. 
Can local changes shift the threshold?
Problem 1.7.
[Nikhil Srivastava] Let $G \sim \mathrm{SBM}$. Now let $G$ be changed by local rules. For what types of rules does this change the threshold?
Cite this as: AimPL: Connecting communities via the block model, available at http://aimpl.org/blockmodel.