# Detect Overlapping Community Based on the Combination of Local Expansion and Label Propagation
## 2 Related Works
Initially, each node is given a unique label. In each propagation, the label of a node \(i\) is replaced by the most common label in neighborhood \(c\), as shown in the following:  
\[l(i)=l(\underset{j\in c}{max}\{l(j)\}). \tag{3}\]  
The labels are updated constantly until they reach a stable state, and nodes with the same label form a community. The community overlap propagation algorithm (\(COPRA\)) allows nodes to have multiple labels [18]. The membership of a node is no longer hard but rather a series of labels with different attribution coefficients. However, the maximum number of communities that a node can belong to is limited. In the speed label propagation algorithm (\(SLPA\)), proposed by [PERSON], nodes update their labels based on pairwise interaction rules [19]. In each propagation, the node no longer passively receives the neighbors' labels to update its own, but interacts with the neighbors and shares information. In addition, the history labels of each iteration are recorded and nodes update labels based on the previous information. The label propagation algorithm can adapt to the diverse community structure, but the general issue is that local label always reaches stability quickly in the simple structure. Given that stable nodes in the early stages have a significant impact on the subsequent propagation, the performance of algorithms will be poor if propagation starts from an inappropriate place, such as the border of the expected community and several dense substructures in the expected community. Contrarily, if the labels of nodes in the center area of the expected community reach stability first, the communities could be detected more accurately. The clique percolation method (\(CPM\)) argues that a community is composed of many small cliques, and there are common members among adjacent cliques [20]. Through these shared members, small cliques are connected together to form a community. \(CFinder\) proposed by [PERSON] is an implementation of \(CPM\)[1]. First, it searches for maximal cliques of size \(K\). If two adjacent k-cliques share k-1 members, they will merge into a new component. In the process of percolation, more cliques connect together and nodes shared by multiple cliques are regarded as overlapping. Agglomerative hierarchical clustering based on maximal clique (\(EAGLE\)) takes maximal k-cliques as the seeds and simply employs the aggregate framework to detect the community [21]. Specially, there is a step called community merging for aggregating two cliques with plenty of identical nodes in case too many nodes are treated as overlapping. However, this kind of algorithm depends on parameter \(K\). Too- large \(K\) could lead to a lot of trivial, isolated cliques, which hinders the detection of large communities. Otherwise, it also fails to terminate in many large social networks when the \(K\) is too small. There are other interesting algorithms. For example, a game-theoretic framework is proposed in [PERSON] et al. [22]. In this theory, each node is regarded as an agent who can choose to join, quit and change his/her community affiliation. The goal of each agent is to maximize his/her own utility, which is determined by the gain function and loss function. A community is associated with a Nash local equity. When the local equilibrium is reached, the members of the community are determined. [PERSON] et al. proposed an extended method of [PERSON]'s work [23]. They take two strategies instead of the action set for obtaining a new label of each agent, and a gain function with similarity is adopted. The difference between the detection algorithms based on game theory mainly lies in the utility functions. In order to prevent confusion, the algorithm named _Game_ mentioned in this paper refers to that of [PERSON] et al. Another kind of algorithm is based on generative stochastic modeling, such as internal and external association to detect communities (\(IEDC\)), whose general framework is based on the principle of dividing each community into non-overlapping and overlapping parts [24].