# Detect Overlapping Community Based on the Combination of Local Expansion and Label Propagation
## 2 Related Works  
In this section, several detection algorithms for overlapping community are reviewed and classified based on characteristics that reflect how communities are detected. The idea of local expansion is to generate natural communities based on the local structure. This kind of algorithm constantly expands the seed by optimizing the fitness function. The form of fitness function and the rules for selecting the seed have a great influence on the performance; the two are diverse in different algorithms. Iterative scan (\(IS\)), a two-step local expansion process, was proposed by [PERSON] et al. [8], where nodes are ranked according to the page rank [12] first and then removed in order of ranking. The part of the nodes that are far away from each other serve as seeds. The fitness function adopted is the following:  
\[f(c)=\frac{w_{in}^{c}}{w_{in}^{c}+w_{out}^{c}}, \tag{1}\]  
where \(w_{in}^{c}\) and \(w_{out}^{c}\) are the total weight of the internal and external edges of the community, respectively. After each expansion, nodes in the current cluster are removed if the fitness function can be optimized. This action often divides a community into several disconnected parts, which could lead to interruption of the expansion before optimization. So, [PERSON] proposed an improved algorithm--connected iterative scan (\(CIS\)) [13]--where only the one that maximizes the fitness function is reminded after the community is split. In addition, \(CIS\) extends the fitness function with \(\lambda e_{p}\), where \(\lambda\) controls how the algorithm behaves in areas with different sparsity of edges, and \(e_{p}\) is the edge probability. The resolution problem of local expansion was pointed out by maximization of local fitness (\(LFM\)) [14], which argues that the size and internal density of a community are diverse. It is unreasonable to adopt the same fitness function to control expansion on different networks. Therefore, it proposed a fitness function that can adjust the resolution, as follows:  
\[f(c)=\frac{k_{in}^{c}}{\left(k_{in}^{c}+k_{out}^{c}\right)^{\alpha}}, \tag{2}\]  
where \(k_{in}^{c}\) and \(k_{out}^{c}\) are the total internal and external degree of the community. Parameter \(\alpha\) controls the algorithm performance in different sparsities, but the setting rules of \(\alpha\) cannot be interpreted. It determines the range of \(\alpha\) by a grid search with high computation costs. In addition, \(LFM\) takes random nodes as initial seeds. It is obvious that a single node must expand successfully at the first attempt. For this reason, the merging of overlapping natural communities (\(MONC\)) adds a constant 1 to the denominator of Equation (2),which makes the algorithm more stable [15]. Neighborhood-inflated seed expansion (\(NISE\)) develops new seeding strategies based on Page Rank that optimizes the community score [16]. Its main idea is embodied in the step of neighborhood inflation, where seeds can represent the characteristics of their entire neighborhood. In general, local expansion algorithms usually expand from the dense area of edge or degree to the sparse area so that the seed always plays an important role. The number, quality and location of the seed will affect the partitions significantly. If we can determine the seed in the center of the expected community at the beginning, the detection quality could be naturally higher. The optimization objective of local expansion is static, where the same fitness function is applied from beginning to end, so the quality of the communities detected are often poor, due to the diversity in the size and structure in the networks. Label propagation is a dynamic algorithm based on the speaker-listener information spread process. Nodes can propagate and accept labels with information of the local structure. Through the interaction of labels, nodes with the same structure are classified into one community. Label propagation algorithm (\(LPA\)), proposed by [PERSON] et al., is a classical algorithm based on this idea [17].