mathematics//graph theory//two-community graph
The two-community graph is a worked example of how a slow disagreement pattern becomes two groups of points. It has 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\).
The two-community graph is a worked example of how a slow disagreement pattern becomes two groups of points. It has 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.
One slow pattern 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).
An imbalance between communities evolves through that pattern alone. From x(0)=(1,1,0,0)Tx(0)=(1,1,0,0)^{\mathsf T}x(0)=(1,1,0,0)T the state is this:
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.
ε0.05 λ20.200 slow time 1/λ25.0 λ32.100 Two groups held together by edges of weight ε. The spectrum of L is (0.00, 0.20, 2.10, 2.10): the disagreement inside a group dies at rate λ3 or faster, the one between groups at λ2, and λ2 goes to zero with ε.
Play with one group hot and the disagreement rides exactly on its bound e−0.2te^{-0.2t}e−0.2t; switch to a split inside a pair and it falls at rate 2.1 instead, then move ε\varepsilonε and watch λ2=4ε\lambda_2=4\varepsilonλ2=4ε follow.
The columns of modes become 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).
The discrete walk has its own factors. 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 of vanishing ε\varepsilonε 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.