# Detect Overlapping Community Based on the Combination of Local Expansion and Label Propagation
## 3 Algorithm  
The essence of our algorithm is the combination of local expansion and label propagation (\(LELP\)). It first intends to detect immature communities based on the improved local expansion. These immature communities are pruned to obtain dense regions that are likely to be the central area of the expected communities. Then, the label propagation that takes the dense regions as a source is conducted, where nodes are allowed to carry multiple labels. After propagation, nodes with the same label form a community and nodes with multiple labels are identified as overlapping. In the stage of local expansion, a new fitness function, different from the previous ones that are related to only edges, is adopted to evaluate expansion. The basic assumption behind it is that a community essentially comprises local structures, involving those close nodes. It is difficult to determine the relationship between two nodes depending only on edges. Therefore, we introduce a new metric named _closeness_ to measure the relationship of nodes. The _closeness_ is defined as the number of neighbors shared by two nodes divided by the number of neighbors in their union, shown as follows:  
\[\mathit{closeness}_{(d)}(i,j)=\frac{\mathit{cover}(i,d)\cap\mathit{cover}(j, d)}{\mathit{cover}(i,d)\cup\mathit{cover}(j,d)}, \tag{4}\]  
where \(\mathit{cover}(i,d)\) is the neighborhood of node \(i\) and parameter \(d\) is a positive integer governing the range of neighbors. The _closeness_ is the same as the Jaccard coefficient when \(d\) is equal to 1 [25]. The larger the \(d\), the wider the range of neighbors considered. However, the relationship of the population will decline with distance in the real world, so \(d\) should be set to a small integer. In addition, two nodes that are not directly connected to each other may have common second-order neighbors, which means that their second-order closeness is not 0. For this case, the _closeness_ between two nodes without direct edges is uniformly set to 0. In this way, we can weight edges by the _closeness_ according to Equation (4) and generate a new weighted network. Local expansion is no longer dependent on random seeds in \(LELP\). Random seeds mean that the starting position of the local expansion is random, which leads to unstable results in repeated experiments. There is no guarantee that the local expansion could start from an appropriate place, so the quality of the partition is often poor. In general, the node pairs with a high ratio of common neighbors tend to be located in the center of the expected community, while those with a low ratio of common neighbors tend to be located in the border. For this reason, node pairs are sorted according to _closeness_, and those with the largest _closeness_ are determined as seeds first in order to ensure an optimal starting point of the local expansion. Therefore, the fitness function is modified as follows:  
\[f(c)=\frac{closeness_{in}^{c}}{closeness_{in}^{c}+closeness_{out}^{c}}, \tag{5}\]  
where \(closeness_{in}^{c}\) and \(closeness_{out}^{c}\) are the total internal and external _closeness_ of the cluster. When a round of local expansion ends, the next round starts from another seed that has not yet expanded. In the previous works of detecting an overlapping community based on local expansion methods, such as \(CIS\), \(LFM\), \(MONC\), the detection is over after the above process. These algorithms always have low quality because the fitness function is static during the entirety of the detection. In fact, the effect of detecting is not always good when the same fitness function is used to detect communities with different sizes. A diverse scale of communities in networks affects the algorithm accuracy, especially at the border of communities. Unlike previous algorithms, the purpose of local expansion adopted in \(LELP\) is not to generate the final communities, but to obtain the central area of expected communities, which are named the dense region. These dense regions are used as the source for label propagation in the following.