摘要：In the planted bisection model a random graph G⃗ (n,p+,p−)G→(n,p+,p−) with nn vertices is created by partitioning the vertices randomly into two classes of equal size (up to ±1±1). Any two vertices that belong to the same class are linked by an edge with probability p+p+ and any two that belong to different classes with probability p−cd+lnd+−−−−−−−√d+−d−>cd+lnd+ for a certain constant c>0c>0.
