# Overlapping Community Detection of Bipartite Networks Based on a Novel Community Density
## 3 Community Density
### Key Definitions  
Given a bipartite network \(G=(U,V,E)(U\
eq\varnothing,V\
eq\varnothing,U\cap V=0)\) with no weight, no direction and the edges exist only between nodes of different types. \(U=\{u\mid u\in U\}\): \(U\) is a one node typeset, \(V=\{v\mid v\in V\}\): \(V\) is a another node typeset. \(a\) represents the number of nodes of type \(U\), and \(b\) represents the number of nodes of type \(V\). \(E\) represents the set of edges connected by two types of nodes, and \((u,v)\) represents a pair of nodes connected by edge \(e_{(u,v)}\). An example diagram of a bipartite network is shown in Figure 2. There are five U nodes and six V nodes, with a total of thirteen edges. \[E=\{e_{(u,v)}\mid u\in U,v\in V\}. \tag{1}\]  
In a bipartite network \(G=(U,V,E)\), \(PN(u)\) represents the set of all node pairs containing node \(u\), \(L(PN(u))\) represents the number of node pairs \(u\) in \(U\), and then \(L(PN(u))=L(u)\) is the total number of node pairs in the set. Likewise, \(PN(v)\) represents the set of all node pairs containing node \(v\), we let \(L(PN(v))\) be the number of node pairs \(v\) in \(V\), and then \(L(PN(v))=L(v)\) is the total number of node pairs in the set. As shown in Figure 3: For node \(U1\), \(PN(U1)=\{(U1,V1),(U1,V2),(U1,V3))\}\); for node \(V1\), \(PN(V1)=\{(U1,V1),(U2,V1),(U4,V1),(U6,V1)\}\). We express these as:  
\[PN(u)=\{(u,v)\mid v\in V,e_{u,v}\in E\}, \tag{2}\]  
\[PN(v)=\{(u,v)\mid u\in U,e_{u,v}\in E\}, \tag{3}\]  
Figure 2: Bipartite network example. \[L(u)=L(PN(u))=\sum_{j=1}^{b}(u,v_{j}), \tag{4}\]  
\[L(v)=L(PN(v))=\sum_{i=1}^{a}(u_{i},v). \tag{5}\]  
In a bipartite network \(G=(U,V,E)\), \(NeiPN(u,v)\) represents a set of neighbor node pairs of node pairs (u,v). \[NeiPN(u,v)=\{PN(p)\cup PN(q)\mid p\in PN(u),q\in PN(v),(p,q)\
eq(u,v)\}. \tag{6}\]  
In Figure 2, select a node pair \((U1,V1)\), and then its neighbor node pairs set is \(NeiPN(U1,V1)=\{(U1,V2),(U1,V3),(U2,V1),(U2,V3),(U4,V1),(U4,V3),(U6,V1),\)\((U6,V2)\}\). Figure 4 shows a set of neighbor node pairs of node pair \((U1,V1)\). In a bipartite network \(G=(U,V,E)\), assume that the bipartite network \(G\) is divided into \(X\) communities, where the \(t\)-th community is expressed as \(G_{t}=(U_{t},V_{t},E_{t})\), and \(\varphi(u,v)\) represents whether the node pair \((u,v)\) is a node pair within the community. \(D_{t_{(m,n)}}\) represents the node pair density of node pairs \((m,n)\) in community \(G_{t}\); in \(\sum_{k=1}^{L(m)}\varphi(m,v_{k})\), \(L(m)\) represents the total number of all V nodes connected to m, k represents the serial number of node \(v_{k}\) connected to m, and, when k = 1, it means that m is connected to V node \(v_{1}\). For node pair \((m,v_{k})\), if they are edges \(e_{(m,v_{k})}\) within the \(t\)-th community, then \(\varphi(m,v_{k})=1\). We express these as:  
\[\varphi(u,v)= \begin{cases}1,&e_{(u,v)}\in E_{t}\\ 0,&e_{(u,v)}\
otin E_{t}\end{cases} , \tag{7}\]  
\[D_{t_{(m,n)}}=\frac{\sum_{k=1}^{L(m)}\varphi(m,v_{k})+\sum_{k=1}^{L(n)}\varphi (u_{k},n)}{L(m)+L(n)}. \tag{8}\]  
Figure 4: A set \(NeiPN(U1,V1)\) of neighbor node pairs of node pairs \((U1,V1)\). Figure 3: All node pairs containing nodes \(U1\) and \(V1\). Suppose we use the bipartite network shown in Figure 2 for community detection, and the results are shown in Figure 1. There are two communities in Figure 2. In community 1, select node pair \((U1,V1)\) to calculate \(D_{1_{(U1,V1)}}\). For node pair \((U1,V1)\), \(PN(U1)=\{(U1,V1),(U1,V2),(U1,V3)\}\), \(PN(V1)=\{(U1,V1),(U2,V1),(U4,V1),(U6,V1)\}\), \(L(U1)=3\), \(L(V1)=4\). The calculation formula of \(D_{1_{U1,V1}}\) is shown in Formula (9).