mathematics//graph theory//two-community graph
Worked example: how a slow disagreement pattern becomes two groups of points. Four nodes: the pairs \((1,2)\) and \((3,4)\) are joined internally with weight 1, and each node of one pair connects to both nodes of the other with weight \(\varepsilon>0\).
Worked example: how a slow disagreement pattern becomes two groups of points. Four nodes: the pairs (1,2)(1,2)(1,2) and (3,4)(3,4)(3,4) are joined internally with weight 1, and each node of one pair connects to both nodes of the other with weight ε>0\varepsilon>0ε>0.
W=[01εε10εεεε01εε10].W=\begin{bmatrix}0&1&\varepsilon&\varepsilon\\1&0&\varepsilon&\varepsilon\\\varepsilon&\varepsilon&0&1\\\varepsilon&\varepsilon&1&0\end{bmatrix}.W=01εε10εεεε01εε10.
Every degree is d=1+2εd=1+2\varepsilond=1+2ε. The weights are abstract affinities here; diffusion time is model time, not physical seconds.
The pattern that tells the groups apart. An orthonormal eigenbasis of L=D−WL=D-WL=D−W is v1=12(1,1,1,1)Tv_1=\tfrac12(1,1,1,1)^{\mathsf T}v1=21(1,1,1,1)T, v2=12(1,1,−1,−1)Tv_2=\tfrac12(1,1,-1,-1)^{\mathsf T}v2=21(1,1,−1,−1)T, v3=12(1,−1,0,0)Tv_3=\tfrac1{\sqrt2}(1,-1,0,0)^{\mathsf T}v3=21(1,−1,0,0)T, v4=12(0,0,1,−1)Tv_4=\tfrac1{\sqrt2}(0,0,1,-1)^{\mathsf T}v4=21(0,0,1,−1)T, with eigenvalues 000, 4ε4\varepsilon4ε, 2+2ε2+2\varepsilon2+2ε and 2+2ε2+2\varepsilon2+2ε. For ε=0.05\varepsilon=0.05ε=0.05 these are 000, 0.20.20.2, 2.12.12.1 and 2.12.12.1. The mode v2v_2v2 barely changes inside each community and only differs across the weak links; its diffusive time constant is 5 units, against 1/2.1≈0.4761/2.1\approx0.4761/2.1≈0.476 for the internal disagreements (spectral gap).
Evolution of an imbalance between communities. From x(0)=(1,1,0,0)Tx(0)=(1,1,0,0)^{\mathsf T}x(0)=(1,1,0,0)T,
x(t)=12(1,1,1,1)T+12e−0.2t(1,1,−1,−1)T.x(t)=\tfrac12(1,1,1,1)^{\mathsf T}+\tfrac12e^{-0.2t}(1,1,-1,-1)^{\mathsf T}.x(t)=21(1,1,1,1)T+21e−0.2t(1,1,−1,−1)T.
The internal modes do not take part because each pair starts with equal values. An existing eigenvalue does not guarantee that its mode appears in every trajectory.
From columns of modes to rows of coordinates. Since every degree is equal, Lsym=L/dL_{\mathrm{sym}}=L/dLsym=L/d shares eigenvectors with LLL. For two groups use U=[v1 v2]U=[v_1;v_2]U=[v1v2]; its rows are ξ1=ξ2=(1/2,1/2)\xi_1=\xi_2=(1/2,1/2)ξ1=ξ2=(1/2,1/2) and ξ3=ξ4=(1/2,−1/2)\xi_3=\xi_4=(1/2,-1/2)ξ3=ξ4=(1/2,−1/2). After row normalization two positions remain, (1,1)/2(1,1)/\sqrt2(1,1)/2 and (1,−1)/2(1,-1)/\sqrt2(1,−1)/2, and K-means with two centers separates the pairs exactly in this ideal case. Columns describe patterns over the whole network; rows describe nodes in the new representation. No initial condition was projected to build those rows (spectral coordinates).
What happens in the discrete walk. The eigenvalues of LrwL_{\mathrm{rw}}Lrw are 000, 2/112/112/11 and 21/1121/1121/11 twice; those of P=I−LrwP=I-L_{\mathrm{rw}}P=I−Lrw are 111, 9/119/119/11 and −10/11-10/11−10/11 twice. Although the chain converges for ε>0\varepsilon>0ε>0 on this graph, the alternating modes can also persist. For Plazy=(I+P)/2P_{\mathrm{lazy}}=(I+P)/2Plazy=(I+P)/2 the factors are 111, 10/1110/1110/11 and 1/221/221/22 twice: the between-community pattern is now clearly slow relative to the internal ones.
The limit that explains clustering. At ε=0\varepsilon=0ε=0 there are two disconnected components and two zero eigenvalues. For small ε\varepsilonε the exact separation becomes a separation of scales; as external connections grow, that justification weakens. The two groups are a property of this affinity, not a truth independent of the model. The graph, the numbers and the spectral representation were built for this note; they do not come from a measured dataset.