---- > [!definition] Definition. ([[modularity]]) > Let $G$ be a [[network]] with $n$ nodes and $m$ edges whose nodes $i$ each belong to a class $g_{i}$, $i \in [n]$. The **modularity** of $G$ is given by the expression $Q:=\frac{1}{2m}\sum_{i,j}^{}\left( A_{ij}-\frac{k_{i}k_{j}}{2m} \right)\delta_{g_{i}g_{j}}=\sum_{r}^{}(e_{r}-a_{r}^{2}),$ > where [[Kronecker Delta]] denotes the [[Kronecker Delta|Kronecker delta function]], $e_{r}=\frac{1}{m}\cdot \frac{1}{2}\sum_{i,j}^{}A_{ij}\delta_{g_{_{i}}r_{}}\delta_{g_{_{j}}r}$ is the fraction of edges that join nodes in class $r$, and $a_{r}=\frac{1}{m}\cdot \frac{1}{2} \sum_{i}^{}k_{i} \delta_{g_{_{i}}r}$ is the fraction of ends of edges attached to nodes in class $r$. > \ > **Remark.** Modularity is a measure of the extent to which 'like connects to like' in a network. $0<Q<1$ implies a higher extent, $(-1<Q<0)$ implies an *anti-higher* extent (disassortative mixing). > [!justification] Derivation. > We begin by attempting to quantify the notion of [[assortative mixing]]: how can we compute the fraction of edges that run between nodes of the same class, minus the expected fraction if edges were positioned randomly (while preserving degree)? > \ > The total number of edges that run between nodes of the same class is $\frac{1}{2}\sum_{i,j}^{}A_{ij}\delta_{g_{i}g_{j}} \ (1)$ \ where we take the $\frac{1}{2}$ compensate for the fact that the summation counts every pair of nodes $(A_{ij}=A_{ji})$ twice. \ The expected number of edges between nodes if edges are placed at random (while preserved degrees) takes more work. Consider a particular node $i$ with [[degree]] $k$, and consider a particular edge attached to $i$. The entire network has $2m$ ends of edges; the [[probability]] that the end that edge of $i$ is one of the $k_{j}$ ends attached to a particular node $j$ is hence $\frac{k_{j}}{2m-1} \approx \frac{k_{j}}{2m}$. Counting *all* edges attached to $i$, the expected number of edges between nodes $i$ and $j$ is $\frac{k_{i}k_{j}}{2m}$. Therefore, the [[expectation|expected]] number of edges between all pairs of nodes of the same type is $\frac{1}{2}\sum_{i,j}^{}A_{ij} \frac{k_{i}k_{j}}{m}\delta_{g_{i}g_{j}} \ (2).$ Subtracting $(2)$ from $(1)$ then yields the difference between the actual and expected number of edges in the network joining nodes of the same class: $\frac{1}{2}\sum_{i,j}^{}(A_{ij}-\frac{k_{i}k_{j}}{2m})\delta_{g_{i}g_{j}} (3).$ Conventionally, one calculates not the number of such edges but the *fraction*, given by dividing the above expression by $m$. This is what we call **modularity**. \ To derive the second expression, let $e_{r}=\frac{1}{m}\cdot \frac{1}{2}\sum_{i,j}^{}A_{ij}\delta_{g_{_{i}}r_{}}\delta_{g_{_{j}}r}$ be the fraction of edges that join nodes in class $r$, and $a_{r}=\frac{1}{m}\cdot \frac{1}{2} \sum_{i}^{}k_{i} \delta_{g_{_{i}}r}$ be the fraction of ends of edges attached to nodes in class $r$. Notice that $\sum_{r}^{}\delta_{g_{_{i}}r}\delta_{g_{_{j}}r}$ equals $1$ in at most one term — when and only when $g_{i}=g_{j}=r$ — and $0$ otherwise. Thus, $(3)$ becomes $\begin{align} Q= & \frac{1}{2m}\sum_{ij}^{}\left( A_{ij}-\frac{k_{i}k_{j}}{2m} \right)\sum_{r}^{}\delta_{g_{_{i}}r}\delta_{g_{_{j}}r} \\ = & \sum_{r}^{}\left[ \frac{1}{2m} \sum_{ij}^{}A_{ij}\delta_{g_{_{i}}r}\delta_{g_{_{j}}r} - \frac{1}{2m} \sum_{i=1}^{n} k_{i} \delta_{g_{_{i}}r} \frac{1}{2m} \sum_{j=1}^{n} k_{j}\delta_{g_{_{j}}r} \right] \\ = & \sum_{r}^{}(e_{r}-a_{r}^{2}). \end{align}$ $\frac{2 \times \mathtt{mutual\_info}(\text{true}; \text{estimate})}{H(\text{true}) + H(\text{estimate})}$ ---- #### ---- #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```