# Overlapping Community Detection of Bipartite Networks Based on a Novel Community Density
## 4 DSNE Algorithm
### A New Strategy to Merge The Sub-Communities  
For two communities to be merged, \(G_{1}(U_{1},V_{1},E_{1})\) and \(G_{2}(U_{2},V_{2},E_{2})\), the usual practice is to merge the node pairs and edges directly. However, this will increase the noise, such as adding some node pairs that are not very closely connected to the newly merged community. In this regard, we provide a new merging idea: starting from the perspective of node pairs, we extract the central node pairs \((u_{1},v_{1})\) and \((u_{2},v_{2})\) from two communities \(G_{1}(U_{1},V_{1},E_{1})\) and \(G_{2}(U_{2},V_{2},E_{2})\) to be merged, and form a new community \(NG_{1}(U_{1},V_{1},E_{1})\) from the two type of node pairs. We define an identifier for each sub-community \(Sub_{(u_{i},v_{j})}(U_{i},V_{j},E_{u_{i},v_{j})}\): _mark_, which indicates whether the central node pair in the sub-community has participated in the merge.  
\[mark=\begin{cases}1,\;\;\;\text{\it has been involved in mergers}\\ 0,\;\;\;\text{\it Not involved in mergers}\end{cases}. \tag{25}\]  
The flow of the first stage is shown in Algorithm 2.  
```
0: Sub-communities set \(Sub-DC\);
0: The merged community set NC;
1: Sort in descending order according to the number of node pair in the sub-communities of \(Sub-DC\) set, Add a mark to each sub-community with an initial value of 0;
2: The sub-community \(G_{i}(U_{i},V_{i},E_{i})\) with the current \(mark=0\) and the most node pairs is selected to merge, and the merged community is \(NG_{j}(U_{j},V_{j},E_{j})\). The initial value of j is 1, the central node pair of \(G_{i}(U_{i},V_{i},E_{i})\) is selected as the central node pair of the merged community, and the mark of the sub-community \(G_{i}(U_{i},V_{i},E_{i})\) is set as 1;
3: Calculate the similarity \(CD_{G_{i},G_{k}}\) between sub-community \(G_{i}(U_{i},V_{i},E_{i})\) and other sub-communities \(G_{k}(U_{k},V_{k},E_{k})\), if \(CD_{G_{i},G_{k}}>\beta\), add the central node pairs of sub-community \(G_{k}(U_{k},V_{k},E_{k})\) to the merged community \(NG_{j}(U_{j},V_{j},E_{j})\), and the mark of the sub-community \(G_{k}(U_{k},V_{k},E_{k})\) is set as 1;
4: Repeat step 3 until all sub-communities have been traversed, j increment by 1;
5: Repeat steps 2, 3, and 4 until all sub-communities have marks of 1;
6: Return \(NC=\{NG_{p}(U_{p},V_{p},E_{p})\mid p=1,2,3,\ldots,j\}\).
```  
**Algorithm 2** Use New Strategy To Merge Sub-communities.  
In the DSNE algorithm, parameter \(\alpha\) is used to judge whether the neighbor node pair \((m,n)\) can join the sub-community \(G_{t}(U_{t},V_{t},E_{t})\). We believe that, if half of all the neighbor node pairs of a node pair are in the community, then the node pair should be in the community, so parameter \(\alpha\) is set to \(0.5\pm 0.1\). The \(\beta\) parameter is defined as the ratio of all identical node pairs in both communities \(G_{i}(U_{i},V_{i},E_{i})\) and \(G_{k}(U_{k},V_{k},E_{k})\) to the total node pairs, parameter \(\beta\) is set to \(0.5\pm 0.1\).  
Complexity Analysis  
Algorithm DSNE is divided into two stages to complete, so we analyze the complexity in turn according to the stage. Assume that there are m nodes of type U and n nodes of type V in the bipartite network. In constructing sub-communities for each node pair, the time complexity required for constructing sub-communities for each central node pair is \(O(m^{2}n^{2})\), and, in merging sub-communities, the time complexity required is \(O(m^{2}n^{2})\). Therefore, \(O(m^{2}n^{2})\) is the time complexity of the algorithm. Since the algorithm does not use unknown storage space during execution, the space complexity is \(O(n)\).