# Modularity-Based Incremental Label Propagation Algorithm for Community Detection
## 2 Methods and Materials
### Evaluation Metrics
#### 2.2.2 Modularity  
When the real community structure of a network is unknown, modularity [23] proposed by [PERSON] is the most popular quality function to assess the community detection result of one algorithm. According to the general definition of community structure, nodes within the same community are densely connected, and nodes in different communities are sparsely connected. Modularity is used to measure whether a network has such a community structure, defined as  
\[Q=\sum_{c=1}^{n_{c}}\left[\frac{l_{c}}{m}-\left(\frac{d_{c}}{2m}\right)^{2}\right] \tag{2}\]  
where \(m\) is the total number of edges in a graph, \(n_{c}\) is the number of communities, \(l_{c}\) is the number of edges joining nodes of community \(l_{c}\) and \(d_{c}\) is  
of nodes, i.e., modularity-based label updating, which greatly reduces the randomness of the label updating process. The entire label propagation process of the algorithm is shown in Figure 1 and the flow chart of the proposed algorithm is shown in Figure 2.  
Given an undirected network G with \(n\) nodes and \(m\) edges, the relationship between nodes \(u\) and \(v\) is denoted by  
\[W_{uv}=\left\{\begin{array}{c}0\\ 1\end{array}\right\} \tag{3}\]  
where \(W_{uv}=1\) indicates that there is a connection between nodes \(u\) and \(v\), while \(W_{uv}=0\) indicates that there is no connection between them. The goal of the algorithm is to find a good partition with \(k\) communities, \(C_{1},C_{2},\ldots,C_{k}\), to maximize the modularity. Note that there is no overlap between any two communities \(C_{i}\) and \(C_{j}\), that is, each node belongs to only one community.  
There are two important concepts in MILPA, intensity and membership degree. The intensity of node \(u\) is defined as  
\[I_{u}=\sum_{v\in\mathcal{F}(u)}w_{uv} \tag{4}\]  
where \(\mathcal{F}(u)\) denotes the neighbors of \(u\). In an undirected network, \(I_{u}\) is the degree of \(u\), i.e., \(k_{u}\). The membership degree of a node indicates the degree to which it belongs to a community \(C\), defined as  
\[M(u,C)=\frac{\sum_{v\in\mathcal{F}(u)\ and\ v\in C}w_{uv}}{I_{u}}. \tag{5}\]  
In fact, \(M(u,C)\) is equivalent to the ratio between the number of the neighbors of node \(u\) in community \(C\) and the degree of \(u\). A high value of membership degree indicates that the node is more likely to belong to the community.  
Figure 1: The process of MILPA. Steps **1**–**2** show the process of incremental label propagation and steps **2**–**3** show the process of modularity-based label updating.  
**Incremental label propagation.** The detailed steps of this process are as follows:  
1. All nodes in the network are assigned into a set \(\tau\) and given the same label \(i=1\).
2. The intensity of all nodes in set \(\tau\) is calculated according to Equation (4).
3. Among the nodes in \(\tau\), the node with the highest intensity and its neighbors are put into a new set, denoted by \(\mathcal{C}\).  
Figure 2: The flow chart of MILPA.  
For any node \(v\in\mathcal{C}\) if the membership degree of \(v\) to \(\mathcal{C}\) is less than \(\varepsilon\), it indicates that node \(v\) is not closely connected with other nodes in \(\mathcal{C}\), and then node \(v\) is deleted from \(\mathcal{C}\). When all nodes in \(\mathcal{C}\) satisfy \(M(u,\mathcal{C})\geq\varepsilon\), they are marked \(F\).
5. A new label, \(i=i+1\), is assigned to these nodes in \(\mathcal{C}\), and then the set \(\mathcal{C}\) is cleared.
6. Steps (2) to (5) are repeated to create new densely connected subgraphs until no new label is generated, resulting in the initial community partition. The threshold of membership degree \(\varepsilon=0.5\) in this paper since it is proved to be the best for most networks.