Four water-quality sensors are placed along a river and linked to their nearest…

PHYSICS · Subjective · Fermi University Physics · Mathematical Methods for Physics · Thermal, Statistical & Complex Systems · Linear algebra and vector spaces

Many Parts, One Behaviour, Ch Communities: finding the groups in a network

Problem

Four water-quality sensors are placed along a river and linked to their nearest neighbours upstream and downstream, forming the path network

1-2-3-4

with edges

\{1,2\}, \{2,3\}, \{3,4\}

. A survey team bisects the sensors into an upstream pair

\{1,2\}

and a downstream pair

\{3,4\}

, assigning labels

s_1=s_2=+1

and

s_3=s_4=-1

. (a) Starting from the cut-size definition

R = \frac14\sum_{ij}A_{ij}(1-s_is_j)

, derive

R = \frac14\mathbf s^{\rm T}\mathbf L\mathbf s

, where

\mathbf L = \mathbf D - \mathbf A

is the graph Laplacian, using

\sum_jA_{ij}=k_i

and

s_i^2=1

. (b) Write down

\mathbf L

for this path network, and use the derived formula to compute

R

for the stated bisection. Check the result against a direct count of edges cut.

Browse the problem library