# Visual Analytic Method for Students' Association via Modularity Optimization
## 6 Qualitative Analysis of Association among Students
### Discovering Student Communities Based on Modularity Optimization
#### 6.2.2 Discovering Student Communities Using the Louvain Algorithm  
The Louvain algorithm has two phases that are reapplied iteratively. For a weighted network of \(N\) nodes, it first views each node as an independent community. Then it takes the neighbors \(j\) of \(i\) for each node \(i\) and evaluates the gain of modularity from placing the node \(i\) in the community of node \(j\); placing occurs when the gain is positive and maximum; otherwise, node \(i\) remains in its original community. This algorithm executes this operation repeatedly on all nodes in a specified order until a local maximum of the modularity is attained. The gain in modularity \(\triangle Q\) obtained by moving node \(i\) to community \(C\) can be computed as Equation (7) [17]:  
\[\triangle\,Q=[\frac{\sum_{in}+k_{i,in}}{2m}-(\frac{\sum_{tot}+k_{i}}{2m})^{2} ]-[\frac{\sum_{in}}{2m}-(\frac{\sum_{tot}}{2m})^{2}-(\frac{k_{i}}{2m})^{2}], \tag{7}\]  
where \(\sum_{in}\) is the sum of the weights of the edges in community \(C\), \(\sum_{tot}\) is the sum of the weights of the edges connected to nodes in community \(C\), \(k_{i}\) the sum of the weights of the edges from node \(i\) to nodes in community \(C\), and \(m\) is the sum of the weights of all the edges in the network.  
The second phase of the Louvain algorithm constructs a new network, whose nodes represent the communities discovered during the first phase. The weight of the edges between the new nodes is the sum of the weights of the edges between nodes in the corresponding communities, and the new nodes may have self-loops, whose weights are the sum of the weights of all the edges in the corresponding communities. When the second phase is completed, we can reuse the first phase in the new network; this iterative operation does not converge until the maximum of modularity is attained or the gain of modularity does not exceed a specified threshold. Through the iterative operation, the Louvain algorithm constructs the hierarchical community structure.  
To discover student communities using the Louvain algorithm, we constructed a weighted network \(G=(V,E)\) of 8685 nodes, where \(V\) is the set of nodes representing the students, and \(E\) is the set of edges, whose weight is computed using the above similarity operators. The process is shown as Algorithm 1.  
We implemented this algorithm using Java and ran it in multi-threading mode. The network \(G=(V,E)\) can be divided into \(k\) non-intersecting subnets \(G_{i}=(V_{i},E_{i})(i=1,2,\ldots,k)\). Based on the results, we can understand the association subnet for each student.  
```
0: Weighted Association Network \(G=(V,E)\)
0:\(G_{i}=(V_{i},E_{i})\), \((i=1,2,\ldots,k)\)
1: viewing each node as an independent community
2: Flag\(=False\)
3:while!Flag do
4: Flag\(=True\)
5:for\(i\in V\)do
6: maxgain=0
7: index\(=-1\)
8:for\(j\in\) neighbors of node \(i\)do
9: calculating \(\triangle Q\) by using Equation (7)
10:if\(\triangle Q\)\(>\) maxgain then
11: maxgain=\(\triangle Q\)
12: index=\(j\)
13:endif
14:endfor
15:if maxgain\(>\)0 then
16: placing node \(i\) in the community of corresponding node \(index\)
17: Flag\(=False\)
18:endif
19:endfor
20:if!Flag then
21: constructing the new network \(G^{{}^{\prime}}\)
22:\(G=G^{{}^{\prime}}\).
23:endif
24:endwhile
```  
**Algorithm 1** Algorithm to discover student communities.