Citation Context

...its mean E[D|σ], we expect v1 to be “close” to β and sign(x1) to be correlated with σ, where sign(x) gives the sign of x componentwise. Note that D is very similar to the modularity matrix defined in =-=[16]-=- and thus dividing the vertices into two communities according to sign(x1) can be seen as an algorithm to maximize the modularity. Unfortunately, in the sparse stochastic block log n model, there are ...

Citation Context

...ignment σ⋆ a.a.s. Moreover, the left hand side of (4) is maximized when w(ℓ) = aµ(ℓ)−bν(ℓ) aµ(ℓ)+bν(ℓ) , in which case (4) reduces to τ > 32 ln 2. IV. SPECTRAL METHOD The minimum bisection is NP-hard =-=[14]-=-. In this section, we present a simple spectral algorithm based on the matrix W introduced above (see [15] for a similar approach in the unlabeled case). We show that this algorithm finds an assignmen...

Citation Context

... stochastic block model, most previous work focuses on the “dense” regime with an average degree diverging as the size of the graph n grows and “exact” reconstruction, such as [6], [7], [8]. McSherry =-=[9]-=- showed that the spectral method works as long as p−q ≥ Ω( √ p log n/n) with average degree as low as Ω(log 6 n). Massoulié and Tomozei [10] reduced this lower bound on the average degree to Ω(log n)....

Citation Context

...− E[D|σ]‖ 2 . (8) Also, a simple derivation yields ‖ ˆ D ′ − E[D|σ]‖ ≤ 2‖W ′ − E[W |σ]‖. (9) The following lemma bounds the quantity ‖W ′ − E[W |σ]‖. Its proof is similar to the proof of Lemma 3.2 in =-=[19]-=-. ℓLemma 3. For any σ ∈ {±1} n , there exists an universal constant C such that ‖W ′ − E[W |σ]‖ ≤ C √ a + b, a.a.s. (10) Combining this lemma with (8) and (9), we get 1 n a + b min{d(σ, sign(ˆx), d(σ...

Citation Context

...d Work For the stochastic block model, most previous work focuses on the “dense” regime with an average degree diverging as the size of the graph n grows and “exact” reconstruction, such as [6], [7], =-=[8]-=-. McSherry [9] showed that the spectral method works as long as p−q ≥ Ω( √ p log n/n) with average degree as low as Ω(log 6 n). Massoulié and Tomozei [10] reduced this lower bound on the average degre...

Citation Context

...(ˆx), d(σ, −sign(ˆx)} ≤ C , β2 and the theorem follows. C. Proof of Theorem 3 The proof follows the same steps as for Theorem 2, except that we are able to strengthen Lemma 3 thanks to a result of Vu =-=[20]-=-. Note that the variance of the elements of W is upper bounded by 1 ∑ n ℓ w2 (ℓ) (aµ(ℓ) + bν(ℓ)) so that by Theorem 1.4 in [20], we get Lemma 4. Under the conditions of Theorem 3, we have √ ∑ ‖W − E[W...

Citation Context

...D. Related Work For the stochastic block model, most previous work focuses on the “dense” regime with an average degree diverging as the size of the graph n grows and “exact” reconstruction, such as =-=[6]-=-, [7], [8]. McSherry [9] showed that the spectral method works as long as p−q ≥ Ω( √ p log n/n) with average degree as low as Ω(log 6 n). Massoulié and Tomozei [10] reduced this lower bound on the ave...

Citation Context

...elated Work For the stochastic block model, most previous work focuses on the “dense” regime with an average degree diverging as the size of the graph n grows and “exact” reconstruction, such as [6], =-=[7]-=-, [8]. McSherry [9] showed that the spectral method works as long as p−q ≥ Ω( √ p log n/n) with average degree as low as Ω(log 6 n). Massoulié and Tomozei [10] reduced this lower bound on the average ...

Citation Context

...tion of pairwise interactions between individuals [2]. The stochastic block model, also known as planted partition model, is a popular random graph model for analyzing the community detection problem =-=[3]-=-, [4], in which pairwise interactions are binary: an edge is either present or absent between two individuals. In its simplest form, the stochastic block model consists of two communities of approxima...

Citation Context

...n which case (4) reduces to τ > 32 ln 2. IV. SPECTRAL METHOD The minimum bisection is NP-hard [14]. In this section, we present a simple spectral algorithm based on the matrix W introduced above (see =-=[15]-=- for a similar approach in the unlabeled case). We show that this algorithm finds an assignment correlated with the true assignment provided τ is large enough. First note that we have E[W |σ] = α n 11...

Citation Context

... fundamentally impossible. Theorem 4. If τ < 1, then for any fixed vertices ρ and v, Pn(σρ = +1|G, L, σv = +1) → 1/2 a.a.s. (7) Theorem 4 is related to the Ising spin model in the statistical physics =-=[17]-=-, [18], and it essentially says that there is no long range correlation in the type assignment when τ < 1. The main idea in the proof of Theorem 4 is borrowed from [12] and works as follows: (1) pick ...

Citation Context

...ined in Definition 1) is conjectured in [4] by analyzing the belief propagation algorithm. The converse part of the conjecture was rigorously proved in [12]. In the converse direction, it is shown in =-=[13]-=- that a variant of spectral method gives a positively correlated partition when above the threshold by an unknown constant factor. The labeled stochastic block was first proposed and studied in [1] an...

Citation Context

...of pairwise interactions between individuals [2]. The stochastic block model, also known as planted partition model, is a popular random graph model for analyzing the community detection problem [3], =-=[4]-=-, in which pairwise interactions are binary: an edge is either present or absent between two individuals. In its simplest form, the stochastic block model consists of two communities of approximately ...

Citation Context

...es of approximately equal size, and the edges are drawn and labeled at random with probability depending on whether their two endpoints belong to the same community or not. It has been conjectured in =-=[1]-=- that this model exhibits a phase transition: reconstruction (i.e. identification of a partition positively correlated with the “true partition” into the underlying communities) would be feasible if a...

Citation Context

... and “exact” reconstruction, such as [6], [7], [8]. McSherry [9] showed that the spectral method works as long as p−q ≥ Ω( √ p log n/n) with average degree as low as Ω(log 6 n). Massoulié and Tomozei =-=[10]-=- reduced this lower bound on the average degree to Ω(log n). More recently, it was shown in [11] that a matrix completion approach works when p − q ≥ Ω(r √ p/n log 2 n) where the number of communities...

Citation Context

... works as long as p−q ≥ Ω( √ p log n/n) with average degree as low as Ω(log 6 n). Massoulié and Tomozei [10] reduced this lower bound on the average degree to Ω(log n). More recently, it was shown in =-=[11]-=- that a matrix completion approach works when p − q ≥ Ω(r √ p/n log 2 n) where the number of communities r could scale with n. For the “sparse” regime with bounded average degrees, a sharp phase trans...

Citation Context

... transition threshold for reconstruction (as defined in Definition 1) is conjectured in [4] by analyzing the belief propagation algorithm. The converse part of the conjecture was rigorously proved in =-=[12]-=-. In the converse direction, it is shown in [13] that a variant of spectral method gives a positively correlated partition when above the threshold by an unknown constant factor. The labeled stochasti...

Citation Context

...mentally impossible. Theorem 4. If τ < 1, then for any fixed vertices ρ and v, Pn(σρ = +1|G, L, σv = +1) → 1/2 a.a.s. (7) Theorem 4 is related to the Ising spin model in the statistical physics [17], =-=[18]-=-, and it essentially says that there is no long range correlation in the type assignment when τ < 1. The main idea in the proof of Theorem 4 is borrowed from [12] and works as follows: (1) pick any tw...