1% Copyright ©2015 The Gonum Authors. All rights reserved. 2% Use of this source code is governed by a BSD-style 3% license that can be found in the LICENSE file. 4 5\documentclass{article} 6 7\usepackage{amsmath,amsfonts} 8\usepackage[margin=4cm]{geometry} 9 10\title{Louvain algorithm for undirected and directed graphs} 11\author{The {\tt gonum} Authors} 12 13\begin{document} 14 15\maketitle 16 17The algorithm attempts to find communities (highly connected sub-graphs), 18and it does this by minimising the modularity function 19\begin{equation} 20 Q(c) = \frac{1}{2m}\sum_i\sum_j\left[ A_{ij} - \gamma \frac{k_ik_j}{2m} \right] \delta_{ij}(c), 21\end{equation} 22where $c$ is a partition of nodes into subsets or communities, 23$A_{ij}$ is the edge weight between nodes $i$ and $j$, 24$\gamma$ is a tuning parameter, 25\begin{equation} 26m = \frac{1}{2}\sum_i\sum_jA_{ij}, 27\end{equation} 28\begin{equation} 29k_i = \sum_j{A_{ij}}, 30\end{equation} 31and 32\begin{equation} 33 \delta_{ij}(c) = \left \{ \begin{array}{ll} 34 1 & \text{if} \quad c(i) = c(j) \\ 35 0 & \text{otherwise} \end{array} \right .. 36\end{equation} 37Here $c(i)$ denotes the community to which node $i$ belongs 38in the partitioning $c$. 39 40The algorithm finds a hierarchical community structure by iterating 41between two phases: 42\begin{enumerate} 43 \item Find a set of communities that minimise $Q$. 44 \item Construct a new graph, whose nodes are the communities 45 found in the preceding phase one step. 46\end{enumerate} 47Each iteration of these two phases is called a `pass'. 48In this way, the algorithm obtains a nested community structure, 49where at each level $Q$ is minimised for the relevant graph. 50We consider this process in more detail, in particular looking 51at phase one first in the first pass, when each node is a single 52node, and then how this generalises to later passes when each node 53is a community. 54 55\section{Undirected Graphs} 56 57\subsection{Initial Pass} 58\label{sec:initialPass} 59 60The initial pass is simple as the initial pass uses the original graph, 61and in all following passes graphs constructed in the previous pass's 62phase two are used. 63Here we will consider this initial simple formulation for phase one, and 64in Section~\ref{sec:laterPasses} we consider how this generalises for 65passes two and onwards. 66Phase one works by initially allocating each node to a separate community, 67and then iterating through each node $a$ and checking if moving it into 68a different community $\beta$ will reduce $Q$. 69If there are possible moves that will reduce $Q$, $a$ is moved into the 70the community which will generate the largest reduction in $Q$. 71This process is continued until there are no moves left to reduce $Q$ 72further, meaning a local minimum for $Q$ has been achieved. 73Then the algorithm moves to phase two (constructing a new graph where 74each node in the new graph is a community in the old graph). 75 76Note that we assume the original graph to be simple and undirected. 77First, we introduce some notation that will be useful: 78Let $c(i)$ denote the community to which node $i$ belongs, 79and let $\alpha$ be the community that the node $a$ mentioned above 80belongs to, i.e., $\alpha = c_a$. 81Then we define 82\newcommand{\Stot}[1]{\Sigma_{\text{tot}}^{#1}} 83\begin{equation} 84 \Stot{\alpha} = \sum_{i \in \alpha}\sum_{j}A_{ij} = \sum_{i \in \alpha}k_i, 85\end{equation} 86\newcommand{\kin}[2]{k_{#1}^{#2}} 87\begin{equation} 88 \kin{i}{\alpha} = \sum_{j \in \alpha}A_{ij}, 89\end{equation} 90and 91\newcommand{\Sin}[1]{\Sigma_{\text{in}}^{#1}} 92\begin{equation} 93 \Sin{\alpha} = \sum_{i \in \alpha}\sum_{j \in \alpha}A_{ij} = \sum_{i \in \alpha}\kin{i}{\alpha}. 94\end{equation} 95 96We are interested in how $Q$ will change if we move a node $a$ from its 97current community $\alpha$, to a new community $\beta$. 98This will have two effects, it will remove the terms from $Q$ 99related to $a$ in $\alpha$, which we will call $Q^-$ and it will add terms 100related to $a$ in $\beta$, which we will call $Q^+$. 101The total change in $Q$ caused by the movement of $a$ from $\alpha$ to $\beta$ is 102\begin{equation} 103 \Delta Q = Q^{+} - Q^{-}, 104\end{equation} 105where 106\begin{align*} 107Q^- &= \frac{1}{2m}\left[ \left( A_{aa} - \gamma \frac{k_a^2}{2m} \right) 108+ 2\sum_{i \in \alpha, \, i \neq a} \left( A_{ia} - \gamma \frac{k_ik_a}{2m} \right) \right] \\ 109 &= \frac{1}{2m}\left[ \left( A_{aa} - \gamma \frac{k_a^2}{2m} \right) 110+ 2 \left( \kin{a}{\alpha} -A_{aa}\right) - \gamma \frac{2k_a}{2m}\sum_{i \in \alpha, \, i \neq a} k_i \right] \\ 111 &= \frac{1}{2m}\left[ \left( A_{aa} - \gamma \frac{k_a^2}{2m} \right) 112+ 2 \left( \kin{a}{\alpha} -A_{aa}\right) - \gamma \frac{2k_a}{2m}\left( \Stot{\alpha} - k_a \right) \right], \\ 113\end{align*} 114and 115\begin{align*} 116Q^+ &= \frac{1}{2m}\left[ \left( A_{aa} - \gamma \frac{k_a^2}{2m} \right) 117+ 2\sum_{i \in \beta} \left( A_{ia} - \gamma \frac{k_ik_a}{2m} \right) \right] \\ 118 &= \frac{1}{2m}\left[ \left( A_{aa} - \gamma \frac{k_a^2}{2m} \right) 119+ 2\kin{a}{\beta} - \gamma \frac{2k_a}{2m}\sum_{i \in \beta} k_i \right] \\ 120 &= \frac{1}{2m}\left[ \left( A_{aa} - \gamma \frac{k_a^2}{2m} \right) 121+ 2\kin{a}{\beta} - \gamma \frac{2k_a\Stot{\beta}}{2m} \right]. \\ 122\end{align*} 123The first term in both these expressions ($Q^-$ and $Q^+$) is the same, and so cancels: 124\begin{equation} 125\Delta Q = \frac{1}{2m}\left[ \left( 2\kin{a}{\beta} - \gamma \frac{2k_a\Stot{\beta}}{2m} \right) 126 - \left( 2 \left( \kin{a}{\alpha} -A_{aa}\right) - \gamma \frac{2k_a}{2m}\left( \Stot{\alpha} - k_a \right) \right) \right]. 127\end{equation} 128 129\subsection{Later Passes} 130\label{sec:laterPasses} 131 132In phase two a `meta-graph' is constructed where nodes correspond to 133the communities found in the preceding phase one step, and edge weight 134between two such communities (nodes, in the meta-graph) 135$\alpha$ and $\beta$ are defined to be 136\begin{equation} 137 A_{\alpha \beta}^* = \sum_{i \in \alpha}\sum_{j \in \beta}A_{ij}. 138 \label{eqn:Aij*} 139\end{equation} 140Note that $i$ and $j$ refer to nodes in the original graph, not nodes 141in the previous graph, and so holds any meta-graph, not just the first. 142Also note that this definition of $A^*_{\alpha \beta}$ allows for 143$A^*_{\alpha \alpha}$ to be non-zero as 144\begin{equation} 145A_{\alpha \alpha}^* = \sum_{i \in \alpha}\sum_{j \in \alpha}A_{ij} = \Sin{\alpha}. 146\end{equation} 147 148In this newly constructed graph, $\alpha$ and $\beta$ are nodes, but 149also refer to communities (sets of nodes) in the original graph, and I 150use these two interpretations interchangeably. 151This should be the only ambiguous bit of notation in this document, I hope. 152 153The results of Section~\ref{sec:initialPass} generalise to these meta-graphs, 154and the generalised results mirror those of Section~\ref{sec:initialPass} closely 155-- I distinguish the new results from those of Section~\ref{sec:initialPass} by a 156superscript $*$. 157I use $i$ and $j$ to denote nodes of the original graph as in Section~\ref{sec:initialPass}, 158and use $z$ and $w$ to denote nodes of the meta-graph (communities of the original). 159I use analogous notation to Section~\ref{sec:initialPass}, $c^*(z)$, to 160denote the community to which node $z$ of the meta-graph belongs, 161and let $\mathfrak{a}$ be the community that the node $\alpha$ belongs to 162($c^*(\alpha) = \mathfrak{a}$), i.e. 163\begin{equation} 164 \mathfrak{a} = \{z | c^*(z) = c^*(\alpha) \}. 165\end{equation} 166 167Given this notation, we can observe that 168\begin{equation} 169m^* = \frac{1}{2}\sum_{z}\sum_{w}{A_{zw}^*} = \frac{1}{2}\sum_{z}\sum_{w}{\sum_{i \in z}\sum_{j \in w}A_{ij}} = \frac{1}{2}\sum_i\sum_jA_{ij} = m, 170\end{equation} 171\begin{equation} 172k_{z}^* = \sum_{w}{A_{zw}^*} = \sum_{w}{\sum_{i \in z}\sum_{j \in w}A_{ij}} = \sum_{i \in z}\sum_{j}A_{ij} = \Stot{z}, 173\end{equation} 174\begin{equation} 175 \Stot{\mathfrak{a} *} = \sum_{z \in \mathfrak{a}}\sum_{w}A_{zw}^* = \sum_{z \in \mathfrak{a}}k_z^* = \sum_{z \in \mathfrak{a}}\Stot{z}, 176\end{equation} 177\begin{equation} 178 \kin{z}{\mathfrak{a} *} = \sum_{w \in \mathfrak{a}}{A_{zw}^*} = \sum_{w \in \mathfrak{a}}{\sum_{i \in z}\sum_{j \in w}A_{ij}}, 179\end{equation} 180and 181\begin{equation} 182\Sin{\mathfrak{a} *} = \sum_{z \in \mathfrak{a}}\sum_{w \in \mathfrak{a}}A_{zw}^* = \sum_{z \in \mathfrak{a}}\kin{z}{\mathfrak{a} *} = \sum_{z \in \mathfrak{a}}\sum_{w \in \mathfrak{a}}{\sum_{i \in z}\sum_{j \in w}A_{ij}}. 183 %\label{eqn:Sin} 184\end{equation} 185 186If we let $\mathfrak{b}$ denote the community to which we are considering moving $\alpha$, 187then the expression for $\Delta Q$ from Section~\ref{sec:initialPass} trivially generalises to 188\begin{equation} 189\Delta Q = \frac{1}{2m}\left[ \left( 2 \kin{\alpha}{\mathfrak{b} *} - \gamma \frac{2k_{\alpha}^*\Stot{\mathfrak{b} *}}{2m} \right) 190 - \left( 2\left( \kin{\alpha}{\mathfrak{a} *} - A_{\alpha \alpha}^* \right) - \gamma \frac{2k_{\alpha}^*}{2m} \left( \Stot{\mathfrak{a} *} - k_{\alpha}^* \right ) \right) \right] \\ 191\end{equation} 192 193\section{Directed Graphs} 194\label{sec:directedGraphs} 195 196It is of interest to consider how this generalises to directed graphs. 197If we are to treat incoming and outgoing nodes equally, there are several 198thoughts on how to extend the algorithm to directed graphs, of which we 199will explore three: 200\begin{itemize} 201 \item Construct an undirected graph first, and then use the undirected case. 202 \item Generalise the expressions from the undirected case to the directed case, 203 we will consider two different suggestions for such generalisations. 204\end{itemize} 205We will show that one of the two `generalisation of expressions' approaches is 206equivalent to constructing an undirected graph, and the other is not. 207 208\subsection{Construction of an undirected graph} 209A simple approach to generalising to directed graphs is to construct 210an undirected graph with edge weights 211\begin{equation} 212A_{ij} = B_{ij} + B_{ji}, 213\label{eqn:undirectedAB} 214\end{equation} 215and simply use the undirected algorithm. 216Another suggestion is to average the directed edges to make 217an undirected graph, i.e. to use a directed graph with edge weights 218\begin{equation} 219A_{ij} = \frac{B_{ij} + B_{ji}}{2}. 220\end{equation} 221This raises an important question: does scaling all edge weights across 222the entire graph by a constant affect the results of the algorithm? 223Hopefully not, but worth checking. 224We can follow this through the results for the undirected graph by 225substituting $A_{ij}^{(1)} = pA_{ij}$, $p \in \mathbb{R}$, and 226distinguishing the new expressions by a superscript ${(1)}$. These 227new expressions are: 228\begin{equation} 229m^{(1)} = \frac{1}{2}\sum_i\sum_jpA_{ij} = p\frac{1}{2}\sum_i\sum_j A_{ij} = pm , 230\end{equation} 231\begin{equation} 232k_i^{(1)} = \sum_j{pA_{ij}} = p\sum_j{A_{ij}} = pk_i, 233\end{equation} 234and so 235\begin{align*} 236 Q^{(1)}(c) &= \frac{1}{2pm}\sum_i\sum_j\left[ pA_{ij} - \gamma \frac{pk_ipk_j}{2pm} \right] \delta_{ij}(c) \\ 237 &= \frac{1}{2m}\sum_i\sum_j\left[ A_{ij} - \gamma \frac{k_ik_j}{2m} \right] \delta_{ij}(c) \\ 238 &= Q(c) 239\end{align*} 240Note that as we have shown $Q^{(1)} = Q$ there is no need to go into the remainder of the terms 241involved in the algorithm, as they all derive from $Q$. 242 243\subsection{First generalisation of expressions approach} 244 245One suggested extension to directed graphs is to modify the expressions 246involved by adding the `from' case and the `to' case for each term. 247If we let $B_{ij}$ be the edge weight between nodes $i$ and $j$ in 248the directed graph, and distinguishing these extended expressions by 249a superscript $(2)$, the extended expressions become: 250\begin{equation} 251m^{(2)} = \frac{1}{2}\left ( \sum_i\sum_jB_{ij} + \sum_i\sum_jB_{ji}\right) = \frac{1}{2}\sum_i\sum_j \left( B_{ij} + B_{ji} \right) , 252\end{equation} 253\begin{equation} 254k_i^{(2)} = \sum_jB_{ij} + \sum_jB_{ji} = \sum_j{\left( B_{ij} + B_{ji} \right)}, 255\end{equation} 256and similarly 257\begin{equation} 258 Q^{(2)}(c) = \frac{1}{2m}\sum_i\sum_j\left[ \left( B_{ij} + B_{ji} \right) - \gamma \frac{k_i^{(2)}k_j^{(2)}}{2m} \right] \delta_{ij}(c). 259\end{equation} 260 261Note how this is equivalent to the construction of an undirected graph as 262per Equation~(\ref{eqn:undirectedAB}). Similarly to above, 263there is no need to go into the remainder of the terms 264involved in the algorithm, as they all derive from $Q$. 265 266 267\subsection{Second generalisation of expressions approach} 268 269Another approach to generalising the expressions to the 270directed case, that still treats incoming and outgoing edges 271as equally important, is to propose an alternative modularity 272expression: 273\newcommand{\dkin}[1]{k_{#1}^{\text{in}}} 274\newcommand{\dkout}[1]{k_{#1}^{\text{out}}} 275\begin{equation} 276Q^{(3)}(c) = \frac{1}{2m}\sum_i\sum_j\left[ 2B_{ij} - 2\gamma \frac{\dkin{i}\dkout{j}}{2m} \right] \delta_{ij}(c), \\ 277\end{equation} 278where 279\begin{equation} 280\dkout{i} = \sum_j{B_{ij}} 281\quad \quad \text{and} \quad \quad 282\dkin{i} = \sum_j{B_{ji}}, 283\end{equation} 284so $k_i^{(2)} = \dkin{i} + \dkout{i}$. 285Note I leave the factor of two in the expression for $Q^{(3)}$ so that it 286remains as comparable to that for $Q^{(2)}$ as possible. 287There is no need for alternative $m$, as it will still be the same as above. 288$Q^{(3)}$ will differ from $Q^{(2)}$ in two ways. 289Firstly, as $k_i^{(2)} = \dkin{i} + \dkout{i}$, 290\begin{align*} 291\sum_i\sum_j k_i^{(2)} k_j^{(2)} \delta_{ij}(c) &= \sum_i\sum_j (\dkin{i} + \dkout{i}) (\dkin{j} + \dkout{j}) \delta_{ij}(c) \\ 292 &= \sum_i\sum_j \left[ (\dkin{i}\dkin{j} + \dkout{i}\dkout{j}) + (\dkin{i}\dkout{j} + \dkin{j}\dkout{i}) \right] \delta_{ij}(c). \\ 293 &= \sum_i\sum_j \left[ (\dkin{i}\dkin{j} + \dkout{i}\dkout{j}) + 2\dkin{i}\dkout{j} \right] \delta_{ij}(c), \\ 294\end{align*} 295and similarly, 296\begin{equation} 297\sum_i\sum_j \left( B_{ij} + B_{ji} \right) \delta_{ij}(c) = 2\sum_i\sum_j B_{ij} \delta_{ij}(c). 298\end{equation} 299From these two expressions, we can see that 300\begin{equation} 301Q^{(3)} - Q^{(2)} = \frac{1}{2m}\sum_i\sum_j \gamma \frac{\dkin{i}\dkin{j} + \dkout{i}\dkout{j}}{2m} \delta_{ij}(c). 302\end{equation} 303 304 305\section{Directed Graphs in more detail} 306\label{sec:directedGraphsDetail} 307 308In Section \ref{sec:directedGraphs} we essentially showed three 309things: 310\begin{itemize} 311 \item How an undirected graph could be constructed from a directed 312 graph, thereby allowing the undirected algorithm to be used for 313 directed graphs. 314 \item How scaling all edge weights by a non-zero constant would not 315 affect the modularity function. 316 \item An alternative approach to extending the algorithm to 317 directed graphs that is not equivalent to first reducing it 318 to an undirected graph. 319\end{itemize} 320It is this third point that we will explore here. 321Analogously to Sections \ref{sec:initialPass} and \ref{sec:laterPasses} we will 322break this up into the initial pass and the later passes. 323 324\subsection{Initial pass} 325\label{sec:initialPassDirected} 326 327Continuing with the notation of Section \ref{sec:initialPass}, in which 328$c(i)$ denotes the community to which node $i$ belongs, 329and $\alpha = c(a)$, we define 330\newcommand{\dinStot}[1]{\Sigma_{\text{tot}}^{\text{in}(#1)}} 331\newcommand{\doutStot}[1]{\Sigma_{\text{tot}}^{\text{out}(#1)}} 332\begin{equation} 333 \doutStot{\alpha} = \sum_{i \in \alpha}\sum_{j}B_{ij} = \sum_{i \in \alpha}\dkout{i} 334 \quad \quad \text{and} \quad \quad 335 \dinStot{\alpha} = \sum_{i \in \alpha}\sum_{j}B_{ji} = \sum_{i \in \alpha}\dkin{i}, 336\end{equation} 337\newcommand{\dinkin}[2]{k_{#1}^{\text{in}(#2)}} 338\newcommand{\doutkin}[2]{k_{#1}^{\text{out}(#2)}} 339\begin{equation} 340 \doutkin{i}{\alpha} = \sum_{j \in \alpha}B_{ij} 341 \quad \quad \text{and} \quad \quad 342 \dinkin{i}{\alpha} = \sum_{j \in \alpha}B_{ji}, 343\end{equation} 344and we will entertain one more ambiguous notation choice: 345%\newcommand{\Sin}[1]{\Sigma_{\text{in}}^{#1}} 346\begin{equation} 347 \Sin{\alpha} = \sum_{i \in \alpha}\sum_{j \in \alpha}B_{ij} = \sum_{i \in \alpha}\doutkin{i}{\alpha} = \sum_{i \in \alpha}\dinkin{i}{\alpha}. 348\end{equation} 349 350Analogously to Section \ref{sec:initialPass}, we are interested in how 351$Q^{(3)}$ will change if we move a node $a$ from its 352current community $\alpha$, to a new community $\beta$, 353and analogously this will have two effects -- it will remove the terms 354from $Q^{(3)}$ related to $a$ in $\alpha$, which we will call $Q^{-(3)}$ 355and it will add terms related to $a$ in $\beta$, which we will call $Q^{+(3)}$. 356The total change in $Q^{(3)}$ caused by the movement of $a$ from $\alpha$ to $\beta$ is 357\begin{equation} 358 \Delta Q^{(3)} = Q^{+(3)} - Q^{-(3)}, 359\end{equation} 360where 361\begin{align*} 362Q^{-(3)} &= \frac{1}{2m}\left[ \left( 2B_{aa} - 2\gamma \frac{\dkin{a}\dkout{a}}{2m} \right) 363+ \sum_{i \in \alpha, \, i \neq a} \left( 2B_{ia} + 2B_{ai} - 2\gamma \frac{\dkin{i}\dkout{a}}{2m} - 2\gamma \frac{\dkin{a}\dkout{i}}{2m} \right) \right] \\ 364 &= \frac{1}{2m}\left[ \left( 2B_{aa} - 2\gamma \frac{\dkin{a}\dkout{a}}{2m} \right) 365+ 2(\dinkin{a}{\alpha} - B_{aa}) + 2(\doutkin{a}{\alpha} - B_{aa}) \hdots \right . \\ 366 & \quad \quad \quad \quad \quad \quad \left . 367- \frac{2\gamma\dkout{a}}{2m} (\dinStot{\alpha} - \dkin{a}) - \frac{2\gamma\dkin{a}}{2m} (\doutStot{\alpha} - \dkout{a}) \right] \\ 368\end{align*} 369and 370\begin{align*} 371Q^{+(3)} &= \frac{1}{2m}\left[ \left( 2B_{aa} - 2\gamma \frac{\dkin{a}\dkout{a}}{2m} \right) 372+ \sum_{i \in \beta} \left( 2B_{ia} + 2B_{ai} - 2\gamma \frac{\dkin{i}\dkout{a}}{2m} - 2\gamma \frac{\dkin{a}\dkout{i}}{2m} \right) \right] \\ 373 &= \frac{1}{2m}\left[ \left( 2B_{aa} - 2\gamma \frac{\dkin{a}\dkout{a}}{2m} \right) 374+ 2\dinkin{a}{\beta} + 2\doutkin{a}{\beta} - \frac{2\gamma\dkout{a}}{2m} \dinStot{\beta} - \frac{2\gamma\dkin{a}}{2m} \doutStot{\beta} \right] \\ 375\end{align*} 376Similarly to Section \ref{sec:initialPass}, the first term in both these expressions is the same, and so cancels, leaving: 377\begin{align*} 378\Delta Q^{(3)} &= \frac{2}{2m}\left[ 379\left( \dinkin{a}{\beta} + \doutkin{a}{\beta} - \frac{\gamma\dkout{a}}{2m} \dinStot{\beta} - \frac{\gamma\dkin{a}}{2m} \doutStot{\beta} \right) \right. \\ 380& \hspace{-1cm} 381- \left. \left( (\dinkin{a}{\alpha} - B_{aa}) + (\doutkin{a}{\alpha} - B_{aa}) - \frac{\gamma\dkout{a}}{2m} (\dinStot{\alpha} - \dkin{a}) - \frac{\gamma\dkin{a}}{2m} (\doutStot{\alpha} - \dkout{a}) \right) \right] \\ 382 &= \frac{2}{2m}\left[ (\dinkin{a}{\beta}-\dinkin{a}{\alpha}) + (\doutkin{a}{\beta}-\doutkin{a}{\alpha}) + 2B_{aa} \right. \\ 383& \hspace{-1cm} \left. 384- \frac{\gamma\dkout{a}}{2m} (\dinStot{\beta}-\dinStot{\alpha}) - \frac{\gamma\dkin{a}}{2m} (\doutStot{\beta} - \doutStot{\alpha}) - \frac{2\gamma\dkin{a}\dkout{a}}{2m} \right] 385\end{align*} 386 387 388 389\subsection{Later passes} 390\label{sec:laterPassesDirected} 391 392In phase two a `meta-graph' is constructed where nodes correspond to 393the communities found in the preceding phase one step, and edge weight 394between two such communities (nodes, in the meta-graph) 395$\alpha$ and $\beta$ are defined to be 396\begin{equation} 397 B_{\alpha \beta}^* = \sum_{i \in \alpha}\sum_{j \in \beta}B_{ij}. 398 \label{eqn:Bij*} 399\end{equation} 400Note that $i$ and $j$ refer to nodes in the original graph, not nodes 401in the previous graph, and so holds any meta-graph, not just the first. 402Also note that this definition of $B^*_{\alpha \beta}$ allows for 403$B^*_{\alpha \alpha}$ to be non-zero, in fact 404\begin{equation} 405B_{\alpha \alpha}^* = \sum_{i \in \alpha}\sum_{j \in \alpha}B_{ij} = \Sin{\alpha}. 406\end{equation} 407 408In this newly constructed graph, $\alpha$ and $\beta$ are nodes, but 409also refer to communities (sets of nodes) in the original graph, and I 410use these two interpretations interchangeably, completely analogously to 411Section \ref{sec:laterPasses}. 412 413The results of Section~\ref{sec:initialPassDirected} generalise to these meta-graphs, 414and the generalised results mirror those of Section~\ref{sec:initialPassDirected} closely 415-- I distinguish the new results from those of Section~\ref{sec:initialPassDirected} by a 416superscript $*$. 417I use $i$ and $j$ to denote nodes of the original graph as in Sections~\ref{sec:initialPass} 418and \ref{sec:initialPassDirected}, 419and use $z$ and $w$ to denote nodes of the meta-graph (communities of the original). 420I use analogous notation to Section~\ref{sec:initialPass}, $c^*(z)$, to 421denote the community to which node $z$ of the meta-graph belongs, 422and let $\mathfrak{a}$ be the community that the node $\alpha$ belongs to, 423i.e., $\mathfrak{a} = c^*(\alpha) $. 424 425Given this notation, we get all the same results as in \ref{sec:laterPasses}, but 426each split into two cases `out' and `in', separating by direction, essentially, so 427\newcommand{\dkinStar}[1]{k_{#1}^{\text{in} *}} 428\newcommand{\dkoutStar}[1]{k_{#1}^{\text{out} *}} 429\begin{equation} 430\dkoutStar{z} = \sum_w{B_{zw}^*} = \sum_w\sum_{i \in z}\sum_{j \in w}B_{ij} = \sum_{i \in z}\sum_jB_{ij} = \doutStot{z}, 431\end{equation} 432\begin{equation} 433\dkinStar{z} = \sum_w{B_{wz}^*} = \sum_w\sum_{i \in z}\sum_{j \in w}B_{ji} = \sum_{i \in z}\sum_jB_{ji} = \dinStot{z}, 434\end{equation} 435\newcommand{\dinStotStar}[1]{\Sigma_{\text{tot}}^{\text{in}(#1) *}} 436\newcommand{\doutStotStar}[1]{\Sigma_{\text{tot}}^{\text{out}(#1) *}} 437\begin{equation} 438 \doutStotStar{\mathfrak{a}} = \sum_{z \in \mathfrak{a}}\sum_{w}B_{zw}^* = \sum_{z \in \mathfrak{a}}\dkoutStar{z} = \sum_{z \in \mathfrak{a}}\doutStot{z}, 439\end{equation} 440\begin{equation} 441 \dinStotStar{\mathfrak{a}} = \sum_{z \in \mathfrak{a}}\sum_{w}B_{wz}^* = \sum_{z \in \mathfrak{a}}\dkinStar{z} = \sum_{z \in \mathfrak{a}}\dinStot{z}, 442\end{equation} 443\newcommand{\dinkinStar}[2]{k_{#1}^{\text{in}(#2) *}} 444\newcommand{\doutkinStar}[2]{k_{#1}^{\text{out}(#2) *}} 445\begin{equation} 446 \doutkinStar{z}{\mathfrak{a}} = \sum_{w \in \mathfrak{a}}{B_{zw}^*} = \sum_{w \in \mathfrak{a}}{\sum_{i \in z}\sum_{j \in w}B_{ij}}, 447\end{equation} 448\begin{equation} 449 \dinkinStar{z}{\mathfrak{a}} = \sum_{w \in \mathfrak{a}}{B_{wz}^*} = \sum_{w \in \mathfrak{a}}{\sum_{i \in z}\sum_{j \in w}B_{ji}}, 450\end{equation} 451and 452\begin{equation} 453\Sin{\mathfrak{a} *} = \sum_{z \in \mathfrak{a}}\sum_{w \in \mathfrak{a}}A_{zw}^* = \sum_{z \in \mathfrak{a}}\kin{z}{\mathfrak{a} *} = \sum_{z \in \mathfrak{a}}\sum_{w \in \mathfrak{a}}{\sum_{i \in z}\sum_{j \in w}A_{ij}}. 454 %\label{eqn:Sin} 455\end{equation} 456 457If we let $\mathfrak{b}$ denote the community to which we are considering moving $\alpha$, 458then the expression for $\Delta Q$ from Section~\ref{sec:initialPassDirected} simply generalises as 459\begin{align*} 460\Delta Q^{(3)} &= \frac{2}{2m}\left[ (\dinkinStar{\alpha}{\mathfrak{b}}-\dinkinStar{\alpha}{\mathfrak{a}}) + (\doutkinStar{\alpha}{\mathfrak{b}}-\doutkinStar{\alpha}{\mathfrak{a}}) + 2B_{\alpha\alpha}^* \right. \\ 461& \hspace{-1cm} \left. 462- \frac{\gamma\dkoutStar{\alpha}}{2m} (\dinStotStar{\mathfrak{b}}-\dinStotStar{\mathfrak{a}}) - \frac{\gamma\dkinStar{\alpha}}{2m} (\doutStotStar{\mathfrak{b}} - \doutStotStar{\mathfrak{a}}) - \frac{2\gamma\dkinStar{\alpha}\dkoutStar{\alpha}}{2m} \right] 463\end{align*} 464 465 466\end{document} 467