Two well-separated friendship groups are embedded inside a much larger acquaintance…

PHYSICS · Subjective · Fermi University Physics · Thermal, Statistical & Complex Systems · Complex and collective systems · Complex and collective systems

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

Problem

Two well-separated friendship groups are embedded inside a much larger acquaintance network of

M=8000

edges in total. The two groups have total degree (the sum of the degrees of their own members)

d_1=45

and

d_2=55

, and are joined by exactly one edge, which is counted in

M

; the two groups are otherwise unconnected to each other. (a) Starting from modularity written as a sum over groups,

Q=\sum_g\left[e_g/M-(d_g/2M)^2\right]

, derive the change in modularity from merging two groups joined by a single edge,

\Delta Q_{\rm merge}=\dfrac1M-\dfrac{d_1d_2}{2M^2}

. (b) Evaluate

\Delta Q_{\rm merge}

for the stated numbers, and state whether modularity maximisation favours merging these two genuinely separate groups, purely because of the size of the surrounding network.

Browse the problem library