Suppose we have an undirected graph $G(V, E)$.
Perturbed graph: I construct the modified graph $G'(V', E')$ based on $G$. For each node $v \in V$, replace it with new vetices $F(v)$, such that $|F(v)| = k$ (hence |V'| = k|V|). Here is how the edges $E'$ are defined:
For any edge $u \rightarrow v \in V'\times V'$:
- if their corresponding vertices in G are connected (i.e. $F^{-1}(u) \rightarrow F^{-1}(v) \in E$), with probability $p_+$ add the edge: $E' \leftarrow E' \cup \{ u \rightarrow v \}$
- if their corresponding vertices in G are NOT connected (i.e. $F^{-1}(u) \rightarrow F^{-1}(v) \notin E$), with probability $p_-$ add the edge: $E' \leftarrow E' \cup \{ u \rightarrow v \}$
A cut in $G$: A given cut $C=(A, B)$ (i.e. $A \cup B = V$ and $A \cap B = \{\}$) and the size of the cut is denoted with $w(C)$.
Corresponding cup in $G'$: For the given cut $C=(A, B)$ in $G$, define the corresponding cut on $G'$ to be $C'=(\cup_{i \in A} F(i), \cup_{i \in B} F(i))$. Define the size of this cut to be $w(C')$.
A probability distribution over the size of the cuts in the new graph: The goal is to find a probability distribution over the size of the corresponding cuts in $G'$: $$ P\left( w(C') = \ell | w(C)=\tilde{\ell} \right) = ? $$ for some $\ell \leq k^2w(C)$.
Since the edges are modified independent of each other, we can think about them as a Binomial distribution. The tricky part is that, there are two Binomial distributions: $Bin\left(k^2w(C), p_+\right)$ and $Bin\left(k^2(|A||B|-w(C)), p_-\right)$.
$$ P\left( w(C') = \ell | w\left(C\right) = k, C=\left(A,B\right) \right) = \sum_{i = 0}^{\ell} \left[ {k^2w(C) \choose i} p_+^i (1 - p_+)^{k^2w(C) - i} \right] \left[ { k^2(|A||B|-w(C)) \choose \ell - i}p_{-}^{\ell - i} (1-p_-)^{k^2(|A||B|-w(C)) - (\ell -i)} \right] $$