# A Constrained Louvain Algorithm with a Novel Modularity
## 3 Materials and Methods
### Constrained Louvain Algorithm with F2  
We propose a constrained Louvain algorithm to detect communities by considering the definition of a weak community [12]. Next, we take \(F2\) as an objective function to introduce the constrained Louvain algorithm. The algorithm is described as two phases. In the first phase, the classical Louvain algorithm is executed. (1) Initially, each node is a community. (2) For the node \(i\), we calculate the increase \(\Delta F2_{j}\) of the objective function when removing \(i\) from its community and placing it next to the community of its neighbor \(j\). Find the maximal increase \(\Delta F2_{max}\) for all neighbors. If \(\Delta F2_{max}>0\), then remove the node \(i\) to the community with the maximal increase \(\Delta F2_{max}\). Otherwise, the node \(i\) stays in its original community. For all nodes, we execute the operation in turns. (3) Repeat the (2) sequentially until the movement of any one node cannot increase the objective function, so that all communities keep invariant. (4) Compress each community as a new node to construct a new network. The summation of edge weights within each community is converted to the weight of the self-ring of the new node. Moreover, the summation of the weights between the nodes of each pair of communities is converted to the weight between the two new nodes. (5) Repeat the steps (1)-(4) until the objective function of the community is not increased any more. In this phase, the step (1)-(3) is shown in Algorithm 1 and the step (4) is shown in Algorithm 2. ```
0: Network \(G(V,W)\)
0: temporary communities partition \(C=\{C_{i},i=1:m\}\)
1: Calculate the objective function \(F2\)
2:\(F2_{0}\gets F2-0.8\)
3:while\(F2>F2_{0}\)do
4:\(F2_{0}\gets F2\)
5: randomize nodes as \(\{v_{i},i=1...N\}\)
6:\(C_{i}\leftarrow\) node \(v_{i}\)
7:for\(i=1\to N\)do
8: Find the neighbor set of \(v_{i}\): \(T(v_{i})=\{u_{1},u_{2}..u_{|T(v_{i})|}\}\)
9:for\(j=1\to|T(v_{i})|\)do
10: calculate \(\Delta F2_{j}\) supposing removing \(v_{i}\) to \(C_{j}\)
11:endfor
12:\(\Delta F2_{max}\gets max(\Delta F2_{1},\Delta F2_{2},...,\Delta F2_{|T(v _{i})|})\)
13:\(u_{max}\leftarrow\) neighbor with \(\Delta F2_{max}\)
14:if\(\Delta F2_{max}>0\)then
15: remove node \(v_{i}\) to the community with \(u_{max}\)
16:\(F2\gets F2+\Delta F2_{max}\)
17:endif
18:endfor
19:endwhile
20:return\(C=\{C_{i},i=1:m\}\)
```  
**Algorithm 1** Optimization of objective function \(F2\). In the second phase, we find the communities to not be satisfying the definition of a weak community and the communities with the number of nodes less than 4. The nodes in these communities are disbanded to form a set of residual nodes. The other communities are the quasi-communities. Then, we assign each residual node to the quasi-communities. Select a node randomly from the residual nodes set and calculate the increase in the objective function \(\Delta F2_{j}\) when this node is removed to the community \(C_{j}\) of its neighbor \(j\)Finally, the node is assigned to the adjacent community with a maximal increase \(\Delta F2_{max}\). Repeat the step until all disbanded nodes are assigned into the communities. This phase is shown in Algorithm 3. In the algorithm above, when a node \(i\) is added to a community \(C_{i}\), the increase \(\Delta F2\) of the objective function is calculated as follows,  
\[\Delta F2=\frac{[d_{in}(C_{i})+2d_{in}(i)]^{2}}{[d(C_{i})+d(i)]^{2}}-\frac{[d _{in}(C_{i})]^{2}}{[d(C_{i})]^{2}}, \tag{12}\]  
here, \(d(C_{i})\) is the total degree of the community \(C_{i}\). \(d_{in}(i)\) is the number of edges between node \(i\) and the community \(C_{i}\). The \(d(i)\) represents the degree of the node \(i\). When a node \(i\) is removed from a community, the calculation is similar. In the algorithm, the order of adding nodes is random; thus, the result of the community partition is different every time. Here, we implement the method many times and take the community structure with the largest value of the modularity as the final result.