# New Community Estimation Method in Bipartite Networks Based on Quality of Filtering Coefficient

Authors: Li Xiong; Guo-Zheng Wang; Hu-Chen Liu
Journal: Scientific Programming
 (2019)

---

## Abstract

Community detection is an important task in network analysis, in which we aim to find a network partitioning that groups together vertices with similar community-level connectivity patterns. Bipartite networks are a common type of network in which there are two types of vertices, and only vertices of different types can be connected. While there are a range of powerful and flexible methods for dividing a bipartite network into a specified number of communities, it is an open question how to determine exactly how many communities one should use, and estimating the numbers of pure-type communities in a bipartite network has not been completed. In our paper, we propose a method named as “biCNEQ” (bipartite network communities number estimation based on quality of filtering coefficient), which ensures that communities are all pure type, for estimating the number of communities in a bipartite network. This paper makes the following contributions: (1) we show how a unipartite weighted network, which we call similarity network, can be projected from a bipartite network using a measure of correlation; (2) we reveal the relation between the similarity correlation and community’s edges in the vertices of a unipartite network; (3) we design a measure of the filtering quality named QFC (quality of filtering coefficient) to filter the similarity network and construct a binary network, which we call approximation network; and (4) the number of communities in each type of unipartite networks is estimated using Riolo’s method with the approximation network as input. Finally, the proposed biCNEQ is demonstrated by both synthetic bipartite networks and a real-world network, and the results show that it can determine the correct number of communities and perform better than two classical one-mode projection methods.


---

## Body

## 1. Introduction

The bipartite network is a network whose vertices can be divided into two typesa and b, where every edge connects a vertex of type-a to one of type-b, and there are no edges connecting vertices of the same type. There are many examples of bipartite networks, such as those described in [1–3]. Regarding unipartite networks, a common task is to find groups or communities of vertices that connect to the rest of the network in similar ways. Finding this underlying group structure is of significant, which can, for example, divide a heterogeneous network into homogeneous subgraphs for subsequent analysis or modeling [4].Beginning from Newman’s [5] study, community detection has attracted considerable attention from researchers [6], aiming to identify good ways to divide up a network into communities. A range of powerful and flexible methods for dividing a bipartite network into a specified number of communities have been proposed in recent years [4, 7, 8]. However, most of them have one key shortcoming; that is, they require us to know the number of communities of a network in advance. In the real world, however, we usually do not know this number a priori, and thus, we need to estimate it from the data. Recently, several methods have been proposed for making such estimates for unipartite networks [9–12] and bipartite networks [13–16]. Barber [13] in his work introduced bipartite modularity, a variant of the modularity proposed by Newman and Girvan [17]. A dual-projection approach proposed by Han et al. [14] aims to maximize the Newman’s one-mode modularity. The authors of [15, 16] maximized Barber’s bipartite modularity for bipartite community detection. However, maximizing both modularities noted above proved to be a NP-hard problem [6, 18]. The bipartite network communities generated in the previous studies are of mixed type, and so far, there is no exploration inferring to the numbers of pure-type communities in a bipartite network.In our paper, we propose a method named “biCNEQ” (bipartite network communities number estimating based on quality of filtering coefficient), which ensures that communities are all pure type. The main innovations and contributions of this study can be illuminated as follows: (1) a percolation idea-based (PIB) method, proposed by Lambiotte and Ausloos [19], is used to project a bipartite network to unipartite correlation networks and reveal the emergence of social communities and music genres by filtering correlation matrices and (2) a first principles method given by Riolo et al. [11] is used for inferring the number of communities in a unipartite network. The quality of filtering coefficient (QFC) is designed to select a threshold to filter the correlation matrix in constructing a binary unipartite network. This method can roughly match the structural features of the correlation and degree of the vertices of the original ones, which cannot be done using PIB. Finally, we use Riolo et al.’s [11] method to estimate the number of communities in each type of unipartite networks. In addition, the proposed biCNEQ is demonstrated by both synthetic bipartite networks and a real-world network, and the results show that our method performs better than two classical one-mode projection methods.


## 2. Methods

Tests were performed on both synthetic bipartite networks and a real-world bipartite network with a known community structure.


### 2.1. Synthetic Networks

We construct a synthetic network based on a degree-corrected bipartite stochastic block model (biSBM) formulated by Larremore et al. [4]. Given a bipartite network G with N×N adjacency matrix A (where N=Na+Nb and Na are the vertices of type-a), we divide the Na vertices of type a into Ka groups and the Nb type-b vertices into Kb groups and express the matrix of group interrelationships as a K×K matrix, where K=Ka+Kb. Let vertex i of type ti belongs to group gi and Tr be the type of group r, imposing the constraint ti=Tgi, which indicates that vertex types and group types must match and ensures that groups will be pure type. Let the number of edges between vertices i and j follow a Poisson distribution with mean θiθjωgigj and choose the normalization ∑iθiδgi,r=1, where θi controls the expected degree of vertex i, ωrs is a K×K symmetric matrix of parameters to control the number of edges between groups r and s, and δ is the Kronecker delta. The probability of observing a network G with adjacency matrix A can be written as(1)PG∣g,θ,ω,T=∏i<jti≠tjθiθjωgigjAijAij!exp−θiθjωgigj=∏iθiki∏i<jti≠tjAij×∏rsTr≠Tsωrsmrs/2exp−12ωrs,where ki is the observed degree of vertex i and mrs=∑ijAijδgi,rδgj,s is the number of edges between groups r and s. After taking partial derivatives with respect to ωrs on the logarithm of equation (1), we can get the maximum likelihood parameter as follows:(2)ω^rs=mrs.The maximum likelihoodθ^i can be found via the constrained maximization of the logarithm of equation (1) subject to ∑iθiδgi,r=1 using Lagrange multipliers, i.e.,(3)θ^i=kiκgi,where κr=∑smrs is the sum of the degrees in group r.Empirically observed networks are often noisy with missing or spurious edges. Therefore, we examine the ability of biCNEQ to analyze a range of synthetic networks generated by a mixed model, which is a combination of planted structureωplanted and a random network model ωrandom. The later model is used to create various levels of uniformly random noise. We consider two forms, as in [4], an easy and a difficult case, to illustrate the biCNEQ’s performance under different conditions.We specifyg and ωplanted and create mixed networks using g. Then,(4)ω=λωplanted+1−λωrandom,where the mixed parameter λ takes values between 0 (all noise) and 1 (all planted structure) and ωrsplanted=mrs according to equation (2). We let ωrsrandom=κrκs/m, where m is the total number of edges in the network.


#### 2.1.1. An Easy Case

In the easy case, we define the mixed matrix to have an easily identifiable community structure which consists of four equally sized, unambiguous, and nonoverlapping components with each made up of one type-a and one type-b community. Let N = 60 for each type and divide these vertices evenly across the four components, where m1,5=m2,6=m3,7=m4,8=150. The symmetric entry has the same value. We create networks using ωrandom. Finally, we use the code, downloaded from http://www.danlarremore.com/bipartiteSBM/makeEasyCaseNetworks.m, to generate mixed synthetic networks of an easy case for testing with the specification above and with its degree distribution unchanged.


#### 2.1.2. A Difficult Case

In the difficult case, the mixed matrix we define is given a less easily identifiable community structure by creating partially overlapping communities,ka≠kb, and has a broad degree distribution. We set different sizes for the communities with 70 type-a vertices, divided evenly into 2 communities {35, 35}, and 30 type-b vertices, divided into 3 communities {10, 15, 5}. Then, we let m1,3=m2,4=250 and m1,5=m2,5=150; θi can be obtained using equation (3). The symmetric entry has the same value. Finally, we use the code, downloaded from http://www.danlarremore.com/bipartiteSBM/makeDifficultCaseNetworks.m, to generate the mixed synthetic network of a difficult case for testing with the specification above and degree distribution unchanged.


### 2.2. Empirical Networks

The Southern women network collected by Davis et al. [20] contains the observed attendance at 14 social events by 18 Southern women. This network was commonly used as a benchmark for bipartite network community detection algorithms [4, 13, 21, 22], much like the Zachary “karate club” that was used for benchmarking unipartite community detection algorithms.


### 2.3. Projection Procedure

#### 2.3.1. Projection

Given a bipartite network with anNa×Nb bipartite adjacency matrix B, where Na and Nb are the number of type-a and type-b vertices, respectively. Bil=1, if there is an edge between type-a vertex ai and type-b vertex bℓ; otherwise, Bil=0.A common way to represent and study bipartite networks consists of projecting them onto links of one kind of vertex [23]. The standard projection method simplifies the system to a unipartite network. For instance, from a bipartite network of scientists and papers, one can extract a network of scientists only, who are related by coauthorship. However, such a projection loses a lot of information and leads to an oversimplified and less useful representation [6, 19, 24]. Therefore, we refine it in an alternative way below.We define for each type-a vertex ai the Nb vector [19]:(5)σi=…,1,…,0,…,1,…,i=1,2,…,Na,where σℓi=Biℓ is equal to 1 if there exists one edge between ai and bℓ; otherwise, it is 0. Then, we calculate the correlation between vertices ai and aj using the cosine similarity [25], which is a symmetric correlation measure. That is,(6)Cij=σi⋅σjσiσj=cosθij,where σi⋅σj denotes the scalar product between σi and σj. Besides,(7)σi=∑ℓ=1Nbσℓi2=ki,where ki is the degree of vertex ai. This measure of correlation, which corresponds to the cosine of the two vectors in an Nb-dimensional space, is equal to 1 when their entries are strictly identical and vanishes when they have no common entries. Specifically, for each pair of type-a vertices, Cij=0 when ai and aj have no common edges with any type-b vertices, and Cij will become 1 when they have identical edges. We call the Na×Na matrix a similarity matrix, with its element Cij, and the unipartite weighted network with similarity matrix C is a similarity network.In [19], the authors revealed the emergence of social communities and music genres by filtering similarity matrices. However, the threshold of filtering coefficient was selected arbitrarily by the authors, and the community structures they found were not unique. To avoid this issue, we firstly would like to know the relation between the similarity correlation and community membership of vertices. We now make an analysis of relations among edge existence, similarity correlation, and community membership of the unipartite network vertices.


#### 2.3.2. Relation between Similarity Correlation and Community’s Edges

According to the definition of a community [6, 26, 27], there are many edges within communities but few edges between communities. Modularity [17, 28] is the most popular function to measure the division quality of a network. Given a particular network with an N×N adjacency matrix A=Aij, its modularity is defined as follows:(8)Q=12m∑ijAij−kikj2mδgi,gj,where ki is the degree of vertex i, m is the number of edges, and gi denotes the community to which vertex i is assigned. The δ function yields 1 if vertices i and j are in the same community (gi=gj) and is 0 otherwise. Therefore, each pair of vertices with an edge between them is more likely to be in the same community than in a different community. This is because it will increase the value of Q if they are in the same community but makes no contribution to Q otherwise.Now, we investigate whether a pair of vertices with a higher similarity correlation is more likely to be in the same community rather than a different community. We let theith row of A be the ith vertex’s N-vector σi and use the cosine of the two vectors σi and σj in the Nb-dimensional space, to quantify the correlation Cij between vertices i and j. It is obvious that there are more coneighbors between a pair of vertices with a higher correlation. Moreover, we have proven in the previous paragraph that two ends of an edge are more likely to be in the same community than in a different community. Therefore, a pair of vertices with a higher correlation is more likely to be in the same community than in a different community.We test our inference on two widely used unipartite networks, the “karate club” network of Zachary [29] and the network of political blogs assembled by Adamic and Glance [30]. Both the two networks have a known community structure. We define the average similarity correlation of the ith vertex with the vertices in the same community as Ciaver_s=∑j,gj=giCij/ngi and the average similarity correlation of the ith vertex with the vertices of different communities as Ciaver_d=∑j,gj≠giCij/n−ngi, where n is the total number of vertices and ngi denotes the vertices number of the community vertex I belongs to. In Figure 1, we plot the average correlation of each of the vertices with the vertices in the same community Ciaver_s against those in the different communities Ciaver_d for each vertex of the two networks, respectively. Figures 1(a) and 1(b) show that one vertex’s average similarity correlation with the vertices in the same community is greater than that in different communities.Figure 1
Average correlation value of each of the vertices with vertices in the same communityCiaver_s against those in different communities Ciaver_d. Tests on (a) the “karate club” network with 34 vertices and (b) the “political blogs” network with 1222 vertices.
(a)
(b)Therefore, we form an edge between each pair of vertices when its similarity correlation value is higher than a given value to construct a binary network from the similarity network of the bipartite network. We will discuss how to select such a threshold in the following section.


### 2.4. Filtering Procedure

To derive such a binary network from the similarity network of a bipartite network, i.e., transform the correlation values in the continuous range [0, 1] to an edge valued 1 or 0 between a pair of vertices, we define a filtering coefficientϕ∈0,1 as in [19]. We filter the similarity matrix elements using ϕ, so that Cij∣ϕ=1 if Cij>ϕ and is equal to 0 otherwise. We call the unweighted unipartite network C∣ϕ, obtained by filtering the similarity matrix, a filtering network, whose adjacency matrix C∣ϕ, with one element denoted as Cij∣ϕ, is named a filtering matrix.We take the Southern women network as an example and plot the total degreeDegreeC∣ϕ=∑ijCij∣ϕ of the filtering network as a function of the filtering coefficient ϕ on the women similarity network and events similarity network both projected from the Southern women dataset. As shown in Figure 2, the total degree DegreeC∣ϕ of the filtering network C∣ϕ reaches a maximum when ϕ=0, and the number decreases or remains unchanged with increasing ϕ, reaching a minimum when ϕ=1. We find a total degree value of 88, which is nearest to the exact number of 89, at ϕ=0.614 on the women filtering network and at ϕ=0.464 on the events filtering network.Figure 2
Total degreeDegreeC∣ϕ of filtering network as a function of the filtering coefficient ϕ. (a) Total degree DegreeC∣ϕ of the events filtering network as a function of ϕ. We can get the best total degree at ϕ=0.464. (b) Total degree DegreeC∣ϕ of the women filtering network as a function of ϕ. We can see that when ϕ=0.614 at the red point, and the total degree is 88 with one degree lost, which is nearest to the exact total degree of 89.
(a)
(b)This raises a question of how do we know when the filtering is good? To answer this, we first introduce the concept of null model. A null model is a random network which matches the original in some of its structural features but does not have any community structure. The most popular null model is known as the standard null model of modularity [17]. It consists of a randomized version of the original graph, where the edges are rewired at random, under the constraint that the expected degree of each vertex matches the degree of the vertices in the original graph. We call the original network the real network, which is assumed to be a unipartite unweighted network projected from a bipartite network.LetA¯ be the Na×Na adjacency matrix of the real network of type-a vertices, then ∑jA¯ij=ki and m=∑iki is the total degree of the real network. Now, we build a null mode R as in [17]:(9)Rij=ki×kjm.We would like the degree of each vertex of the filtering network to approximate the degree of the vertices in the original graph. Firstly, we define a measure of degree difference between the filtering network and the null model, and we call it degree difference (DD):(10)DDϕ=∑ijCij∣ϕ−Rij2.From equation (7), we know the degree of each vertex of the filtering network approximately matches the degree of the vertices in the original graph when DD is minimized. By taking a derivative with respect to Cij∣ϕ in equation (10) and let it equals to 0, we have(11)∑ijCij∣ϕ=∑ijRij=m,where ∑ijCij∣ϕ is the total degree of the filtering network and m is the edge number of the bipartite network. Now, we define a measure of the quality of a filtering network of a bipartite network, which we call QFC based on equation (11):(12)QFCϕ=∑ijCij∣ϕ−m,where QFCϕ is actually the absolute value of ∑ijCij∣ϕ−m. That is to say, the best filtering network, whose total degree matches or is closest to that of the original network, occurs when the QFC reaches a minimum with ϕ=ϕbest. We call the best filtering network the approximation network, whose adjacency matrix C∣ϕ=ϕbest is named an approximation matrix.Next, we perform experiments to test QFC criterion on the Southern women network. We plot theQFCϕ of the filtering network as a function of the filtering coefficient ϕ on the type-a similarity network and type-b similarity network projected from the real-world bipartite networks mentioned above. The approximation networks can be obtained when QFCϕ reaches its minimum value at the bottom of the curve, as shown in Figure 3.Figure 3
QFC
ϕ of filtering network as a function of the filtering coefficient ϕ. (a) QFCϕ of the women filtering network. We get the minimum QFCϕ=1 when ϕbest=0.614 at the red point. (b) QFCϕ of the events filtering network. We get the minimum QFCϕ=1 when ϕbest=0.464 at the red point.
(a)
(b)In this procedure, we construct theQFCϕ=∑ijCij∣ϕ−m as a function of the filtering coefficient ϕ∈0,1 and find the minimum value of QFCϕ and the corresponding ϕ=ϕbest. Then, we get the approximation matrix Aappro with elements Aijappro=Cij∣ϕ=ϕbest of type-a vertices.


### 2.5. Estimation Procedure

In the work of [11], the authors introduced a method for estimating the number of communities in a unipartite network. We can use this method to determine the number of communities in the approximation network of a bipartite network.Riolo et al. [11] employed a more sophisticated approach, the degree-corrected stochastic block model, to overcome the shortcomings of the stochastic block model [31], which gives substantially better results for real-world network data. With the model specified, they find the probability P that a particular network with adjacency matrix A=Aij is found by the following equation:(13)PA∣ω,θ,g,k=∏i<jθiθjωgigjAije−θiθjωgigj×∏i12θi2ωgigiAii/2e−θi2ωgigi/2=∏iθidi∏r<sωrsmrse−nrnsωrs∏rωrrmrre−nr2ωrr/2,where k is the number of groups, gi denotes the group to which vertex i is assigned, r and s are the groups to which the vertices belong to, and mrs is the number of edges running between groups r and s. The parameter θi is used to independently control the average degree of each node and hence match any desired distribution. The parameter ωrs is the expected value of the adjacency matrix entry Aij for vertices i and j belonging to groups r and s, respectively, and they control the community structure. The parameters above have been discussed in detail in [31].After integrating the parametersω and θ, from equation (13), we have(14)PA∣g,k=∏rnrκrnr−1!nr+κr−1!×∏r<smrs!ρnrns+1mrs+1∏rmrr!1/2ρnr2+1mrr+1,where nr is the number of vertices in group r and κr is the sum of the degrees of the vertices in group r.We use equation (13) to derive the probability Pg,k∣A:(15)Pg,k∣A=Pg,kPA∣g,kPA,where(16)Pg,k=n−2−k∏r=1knr!.The valuesk and g define the “state” of a statistical mechanical system with the probability Pg,k∣A. States of this system are sampled in proportion to the probability using Markov chain Monte Carlo sampling. Then, an estimate of the probability Pk∣A of having k communities given the observed network A is found using the histogram of values of k over the Monte Carlo sample. Then, the most likely value of k is the one for which Pk∣A is greatest. For one network, we performed 10000 Monte Carlo sweeps, each one of which include n individual nodes moves of two types [11]. After one sweep, the values k and g may change, if k = 5, k = 3, and k = 2 show out, respectively, 5000, 3000, and 2000 sweeps, then fraction of community numbers P(k = 5/A) = 5000/10000 = 0.5, P(k = 4/A) = 0.3, and P(k = 2/A) = 0.2. Thus, the most likely value of k is 5.We setAappro as the input to the unipartite network communities number estimating method of Riolo et al. [11] to estimate the number of communities in the network of type-a vertices. Then, by transposing the affiliation matrix B and using the same method as above, we can estimate the number of communities in the network of type-b vertices.Now, let us analyze the time complexity of our method for type-a network. In the projection procedure, we take ONa2Nb times to calculate cosine similarity. Then, we take time approximately ONa2 to finish the filtering procedure, mainly finding the total degree ∑ijCij∣ϕ of one filtering matrix. Finally, we take ONak to move n nodes to k communities and ONa2k2 to calculate the complete probability Pg,k∣A, so the estimation procedure takes time ONa2. Therefore, the complete time complexity of our method is ONa2Nb+Nb2Na.


## 2.1. Synthetic Networks

We construct a synthetic network based on a degree-corrected bipartite stochastic block model (biSBM) formulated by Larremore et al. [4]. Given a bipartite network G with N×N adjacency matrix A (where N=Na+Nb and Na are the vertices of type-a), we divide the Na vertices of type a into Ka groups and the Nb type-b vertices into Kb groups and express the matrix of group interrelationships as a K×K matrix, where K=Ka+Kb. Let vertex i of type ti belongs to group gi and Tr be the type of group r, imposing the constraint ti=Tgi, which indicates that vertex types and group types must match and ensures that groups will be pure type. Let the number of edges between vertices i and j follow a Poisson distribution with mean θiθjωgigj and choose the normalization ∑iθiδgi,r=1, where θi controls the expected degree of vertex i, ωrs is a K×K symmetric matrix of parameters to control the number of edges between groups r and s, and δ is the Kronecker delta. The probability of observing a network G with adjacency matrix A can be written as(1)PG∣g,θ,ω,T=∏i<jti≠tjθiθjωgigjAijAij!exp−θiθjωgigj=∏iθiki∏i<jti≠tjAij×∏rsTr≠Tsωrsmrs/2exp−12ωrs,where ki is the observed degree of vertex i and mrs=∑ijAijδgi,rδgj,s is the number of edges between groups r and s. After taking partial derivatives with respect to ωrs on the logarithm of equation (1), we can get the maximum likelihood parameter as follows:(2)ω^rs=mrs.The maximum likelihoodθ^i can be found via the constrained maximization of the logarithm of equation (1) subject to ∑iθiδgi,r=1 using Lagrange multipliers, i.e.,(3)θ^i=kiκgi,where κr=∑smrs is the sum of the degrees in group r.Empirically observed networks are often noisy with missing or spurious edges. Therefore, we examine the ability of biCNEQ to analyze a range of synthetic networks generated by a mixed model, which is a combination of planted structureωplanted and a random network model ωrandom. The later model is used to create various levels of uniformly random noise. We consider two forms, as in [4], an easy and a difficult case, to illustrate the biCNEQ’s performance under different conditions.We specifyg and ωplanted and create mixed networks using g. Then,(4)ω=λωplanted+1−λωrandom,where the mixed parameter λ takes values between 0 (all noise) and 1 (all planted structure) and ωrsplanted=mrs according to equation (2). We let ωrsrandom=κrκs/m, where m is the total number of edges in the network.


### 2.1.1. An Easy Case

In the easy case, we define the mixed matrix to have an easily identifiable community structure which consists of four equally sized, unambiguous, and nonoverlapping components with each made up of one type-a and one type-b community. Let N = 60 for each type and divide these vertices evenly across the four components, where m1,5=m2,6=m3,7=m4,8=150. The symmetric entry has the same value. We create networks using ωrandom. Finally, we use the code, downloaded from http://www.danlarremore.com/bipartiteSBM/makeEasyCaseNetworks.m, to generate mixed synthetic networks of an easy case for testing with the specification above and with its degree distribution unchanged.


### 2.1.2. A Difficult Case

In the difficult case, the mixed matrix we define is given a less easily identifiable community structure by creating partially overlapping communities,ka≠kb, and has a broad degree distribution. We set different sizes for the communities with 70 type-a vertices, divided evenly into 2 communities {35, 35}, and 30 type-b vertices, divided into 3 communities {10, 15, 5}. Then, we let m1,3=m2,4=250 and m1,5=m2,5=150; θi can be obtained using equation (3). The symmetric entry has the same value. Finally, we use the code, downloaded from http://www.danlarremore.com/bipartiteSBM/makeDifficultCaseNetworks.m, to generate the mixed synthetic network of a difficult case for testing with the specification above and degree distribution unchanged.


## 2.1.1. An Easy Case

In the easy case, we define the mixed matrix to have an easily identifiable community structure which consists of four equally sized, unambiguous, and nonoverlapping components with each made up of one type-a and one type-b community. Let N = 60 for each type and divide these vertices evenly across the four components, where m1,5=m2,6=m3,7=m4,8=150. The symmetric entry has the same value. We create networks using ωrandom. Finally, we use the code, downloaded from http://www.danlarremore.com/bipartiteSBM/makeEasyCaseNetworks.m, to generate mixed synthetic networks of an easy case for testing with the specification above and with its degree distribution unchanged.


## 2.1.2. A Difficult Case

In the difficult case, the mixed matrix we define is given a less easily identifiable community structure by creating partially overlapping communities,ka≠kb, and has a broad degree distribution. We set different sizes for the communities with 70 type-a vertices, divided evenly into 2 communities {35, 35}, and 30 type-b vertices, divided into 3 communities {10, 15, 5}. Then, we let m1,3=m2,4=250 and m1,5=m2,5=150; θi can be obtained using equation (3). The symmetric entry has the same value. Finally, we use the code, downloaded from http://www.danlarremore.com/bipartiteSBM/makeDifficultCaseNetworks.m, to generate the mixed synthetic network of a difficult case for testing with the specification above and degree distribution unchanged.


## 2.2. Empirical Networks

The Southern women network collected by Davis et al. [20] contains the observed attendance at 14 social events by 18 Southern women. This network was commonly used as a benchmark for bipartite network community detection algorithms [4, 13, 21, 22], much like the Zachary “karate club” that was used for benchmarking unipartite community detection algorithms.


## 2.3. Projection Procedure

### 2.3.1. Projection

Given a bipartite network with anNa×Nb bipartite adjacency matrix B, where Na and Nb are the number of type-a and type-b vertices, respectively. Bil=1, if there is an edge between type-a vertex ai and type-b vertex bℓ; otherwise, Bil=0.A common way to represent and study bipartite networks consists of projecting them onto links of one kind of vertex [23]. The standard projection method simplifies the system to a unipartite network. For instance, from a bipartite network of scientists and papers, one can extract a network of scientists only, who are related by coauthorship. However, such a projection loses a lot of information and leads to an oversimplified and less useful representation [6, 19, 24]. Therefore, we refine it in an alternative way below.We define for each type-a vertex ai the Nb vector [19]:(5)σi=…,1,…,0,…,1,…,i=1,2,…,Na,where σℓi=Biℓ is equal to 1 if there exists one edge between ai and bℓ; otherwise, it is 0. Then, we calculate the correlation between vertices ai and aj using the cosine similarity [25], which is a symmetric correlation measure. That is,(6)Cij=σi⋅σjσiσj=cosθij,where σi⋅σj denotes the scalar product between σi and σj. Besides,(7)σi=∑ℓ=1Nbσℓi2=ki,where ki is the degree of vertex ai. This measure of correlation, which corresponds to the cosine of the two vectors in an Nb-dimensional space, is equal to 1 when their entries are strictly identical and vanishes when they have no common entries. Specifically, for each pair of type-a vertices, Cij=0 when ai and aj have no common edges with any type-b vertices, and Cij will become 1 when they have identical edges. We call the Na×Na matrix a similarity matrix, with its element Cij, and the unipartite weighted network with similarity matrix C is a similarity network.In [19], the authors revealed the emergence of social communities and music genres by filtering similarity matrices. However, the threshold of filtering coefficient was selected arbitrarily by the authors, and the community structures they found were not unique. To avoid this issue, we firstly would like to know the relation between the similarity correlation and community membership of vertices. We now make an analysis of relations among edge existence, similarity correlation, and community membership of the unipartite network vertices.


### 2.3.2. Relation between Similarity Correlation and Community’s Edges

According to the definition of a community [6, 26, 27], there are many edges within communities but few edges between communities. Modularity [17, 28] is the most popular function to measure the division quality of a network. Given a particular network with an N×N adjacency matrix A=Aij, its modularity is defined as follows:(8)Q=12m∑ijAij−kikj2mδgi,gj,where ki is the degree of vertex i, m is the number of edges, and gi denotes the community to which vertex i is assigned. The δ function yields 1 if vertices i and j are in the same community (gi=gj) and is 0 otherwise. Therefore, each pair of vertices with an edge between them is more likely to be in the same community than in a different community. This is because it will increase the value of Q if they are in the same community but makes no contribution to Q otherwise.Now, we investigate whether a pair of vertices with a higher similarity correlation is more likely to be in the same community rather than a different community. We let theith row of A be the ith vertex’s N-vector σi and use the cosine of the two vectors σi and σj in the Nb-dimensional space, to quantify the correlation Cij between vertices i and j. It is obvious that there are more coneighbors between a pair of vertices with a higher correlation. Moreover, we have proven in the previous paragraph that two ends of an edge are more likely to be in the same community than in a different community. Therefore, a pair of vertices with a higher correlation is more likely to be in the same community than in a different community.We test our inference on two widely used unipartite networks, the “karate club” network of Zachary [29] and the network of political blogs assembled by Adamic and Glance [30]. Both the two networks have a known community structure. We define the average similarity correlation of the ith vertex with the vertices in the same community as Ciaver_s=∑j,gj=giCij/ngi and the average similarity correlation of the ith vertex with the vertices of different communities as Ciaver_d=∑j,gj≠giCij/n−ngi, where n is the total number of vertices and ngi denotes the vertices number of the community vertex I belongs to. In Figure 1, we plot the average correlation of each of the vertices with the vertices in the same community Ciaver_s against those in the different communities Ciaver_d for each vertex of the two networks, respectively. Figures 1(a) and 1(b) show that one vertex’s average similarity correlation with the vertices in the same community is greater than that in different communities.Figure 1
Average correlation value of each of the vertices with vertices in the same communityCiaver_s against those in different communities Ciaver_d. Tests on (a) the “karate club” network with 34 vertices and (b) the “political blogs” network with 1222 vertices.
(a)
(b)Therefore, we form an edge between each pair of vertices when its similarity correlation value is higher than a given value to construct a binary network from the similarity network of the bipartite network. We will discuss how to select such a threshold in the following section.


## 2.3.1. Projection

Given a bipartite network with anNa×Nb bipartite adjacency matrix B, where Na and Nb are the number of type-a and type-b vertices, respectively. Bil=1, if there is an edge between type-a vertex ai and type-b vertex bℓ; otherwise, Bil=0.A common way to represent and study bipartite networks consists of projecting them onto links of one kind of vertex [23]. The standard projection method simplifies the system to a unipartite network. For instance, from a bipartite network of scientists and papers, one can extract a network of scientists only, who are related by coauthorship. However, such a projection loses a lot of information and leads to an oversimplified and less useful representation [6, 19, 24]. Therefore, we refine it in an alternative way below.We define for each type-a vertex ai the Nb vector [19]:(5)σi=…,1,…,0,…,1,…,i=1,2,…,Na,where σℓi=Biℓ is equal to 1 if there exists one edge between ai and bℓ; otherwise, it is 0. Then, we calculate the correlation between vertices ai and aj using the cosine similarity [25], which is a symmetric correlation measure. That is,(6)Cij=σi⋅σjσiσj=cosθij,where σi⋅σj denotes the scalar product between σi and σj. Besides,(7)σi=∑ℓ=1Nbσℓi2=ki,where ki is the degree of vertex ai. This measure of correlation, which corresponds to the cosine of the two vectors in an Nb-dimensional space, is equal to 1 when their entries are strictly identical and vanishes when they have no common entries. Specifically, for each pair of type-a vertices, Cij=0 when ai and aj have no common edges with any type-b vertices, and Cij will become 1 when they have identical edges. We call the Na×Na matrix a similarity matrix, with its element Cij, and the unipartite weighted network with similarity matrix C is a similarity network.In [19], the authors revealed the emergence of social communities and music genres by filtering similarity matrices. However, the threshold of filtering coefficient was selected arbitrarily by the authors, and the community structures they found were not unique. To avoid this issue, we firstly would like to know the relation between the similarity correlation and community membership of vertices. We now make an analysis of relations among edge existence, similarity correlation, and community membership of the unipartite network vertices.


## 2.3.2. Relation between Similarity Correlation and Community’s Edges

According to the definition of a community [6, 26, 27], there are many edges within communities but few edges between communities. Modularity [17, 28] is the most popular function to measure the division quality of a network. Given a particular network with an N×N adjacency matrix A=Aij, its modularity is defined as follows:(8)Q=12m∑ijAij−kikj2mδgi,gj,where ki is the degree of vertex i, m is the number of edges, and gi denotes the community to which vertex i is assigned. The δ function yields 1 if vertices i and j are in the same community (gi=gj) and is 0 otherwise. Therefore, each pair of vertices with an edge between them is more likely to be in the same community than in a different community. This is because it will increase the value of Q if they are in the same community but makes no contribution to Q otherwise.Now, we investigate whether a pair of vertices with a higher similarity correlation is more likely to be in the same community rather than a different community. We let theith row of A be the ith vertex’s N-vector σi and use the cosine of the two vectors σi and σj in the Nb-dimensional space, to quantify the correlation Cij between vertices i and j. It is obvious that there are more coneighbors between a pair of vertices with a higher correlation. Moreover, we have proven in the previous paragraph that two ends of an edge are more likely to be in the same community than in a different community. Therefore, a pair of vertices with a higher correlation is more likely to be in the same community than in a different community.We test our inference on two widely used unipartite networks, the “karate club” network of Zachary [29] and the network of political blogs assembled by Adamic and Glance [30]. Both the two networks have a known community structure. We define the average similarity correlation of the ith vertex with the vertices in the same community as Ciaver_s=∑j,gj=giCij/ngi and the average similarity correlation of the ith vertex with the vertices of different communities as Ciaver_d=∑j,gj≠giCij/n−ngi, where n is the total number of vertices and ngi denotes the vertices number of the community vertex I belongs to. In Figure 1, we plot the average correlation of each of the vertices with the vertices in the same community Ciaver_s against those in the different communities Ciaver_d for each vertex of the two networks, respectively. Figures 1(a) and 1(b) show that one vertex’s average similarity correlation with the vertices in the same community is greater than that in different communities.Figure 1
Average correlation value of each of the vertices with vertices in the same communityCiaver_s against those in different communities Ciaver_d. Tests on (a) the “karate club” network with 34 vertices and (b) the “political blogs” network with 1222 vertices.
(a)
(b)Therefore, we form an edge between each pair of vertices when its similarity correlation value is higher than a given value to construct a binary network from the similarity network of the bipartite network. We will discuss how to select such a threshold in the following section.


## 2.4. Filtering Procedure

To derive such a binary network from the similarity network of a bipartite network, i.e., transform the correlation values in the continuous range [0, 1] to an edge valued 1 or 0 between a pair of vertices, we define a filtering coefficientϕ∈0,1 as in [19]. We filter the similarity matrix elements using ϕ, so that Cij∣ϕ=1 if Cij>ϕ and is equal to 0 otherwise. We call the unweighted unipartite network C∣ϕ, obtained by filtering the similarity matrix, a filtering network, whose adjacency matrix C∣ϕ, with one element denoted as Cij∣ϕ, is named a filtering matrix.We take the Southern women network as an example and plot the total degreeDegreeC∣ϕ=∑ijCij∣ϕ of the filtering network as a function of the filtering coefficient ϕ on the women similarity network and events similarity network both projected from the Southern women dataset. As shown in Figure 2, the total degree DegreeC∣ϕ of the filtering network C∣ϕ reaches a maximum when ϕ=0, and the number decreases or remains unchanged with increasing ϕ, reaching a minimum when ϕ=1. We find a total degree value of 88, which is nearest to the exact number of 89, at ϕ=0.614 on the women filtering network and at ϕ=0.464 on the events filtering network.Figure 2
Total degreeDegreeC∣ϕ of filtering network as a function of the filtering coefficient ϕ. (a) Total degree DegreeC∣ϕ of the events filtering network as a function of ϕ. We can get the best total degree at ϕ=0.464. (b) Total degree DegreeC∣ϕ of the women filtering network as a function of ϕ. We can see that when ϕ=0.614 at the red point, and the total degree is 88 with one degree lost, which is nearest to the exact total degree of 89.
(a)
(b)This raises a question of how do we know when the filtering is good? To answer this, we first introduce the concept of null model. A null model is a random network which matches the original in some of its structural features but does not have any community structure. The most popular null model is known as the standard null model of modularity [17]. It consists of a randomized version of the original graph, where the edges are rewired at random, under the constraint that the expected degree of each vertex matches the degree of the vertices in the original graph. We call the original network the real network, which is assumed to be a unipartite unweighted network projected from a bipartite network.LetA¯ be the Na×Na adjacency matrix of the real network of type-a vertices, then ∑jA¯ij=ki and m=∑iki is the total degree of the real network. Now, we build a null mode R as in [17]:(9)Rij=ki×kjm.We would like the degree of each vertex of the filtering network to approximate the degree of the vertices in the original graph. Firstly, we define a measure of degree difference between the filtering network and the null model, and we call it degree difference (DD):(10)DDϕ=∑ijCij∣ϕ−Rij2.From equation (7), we know the degree of each vertex of the filtering network approximately matches the degree of the vertices in the original graph when DD is minimized. By taking a derivative with respect to Cij∣ϕ in equation (10) and let it equals to 0, we have(11)∑ijCij∣ϕ=∑ijRij=m,where ∑ijCij∣ϕ is the total degree of the filtering network and m is the edge number of the bipartite network. Now, we define a measure of the quality of a filtering network of a bipartite network, which we call QFC based on equation (11):(12)QFCϕ=∑ijCij∣ϕ−m,where QFCϕ is actually the absolute value of ∑ijCij∣ϕ−m. That is to say, the best filtering network, whose total degree matches or is closest to that of the original network, occurs when the QFC reaches a minimum with ϕ=ϕbest. We call the best filtering network the approximation network, whose adjacency matrix C∣ϕ=ϕbest is named an approximation matrix.Next, we perform experiments to test QFC criterion on the Southern women network. We plot theQFCϕ of the filtering network as a function of the filtering coefficient ϕ on the type-a similarity network and type-b similarity network projected from the real-world bipartite networks mentioned above. The approximation networks can be obtained when QFCϕ reaches its minimum value at the bottom of the curve, as shown in Figure 3.Figure 3
QFC
ϕ of filtering network as a function of the filtering coefficient ϕ. (a) QFCϕ of the women filtering network. We get the minimum QFCϕ=1 when ϕbest=0.614 at the red point. (b) QFCϕ of the events filtering network. We get the minimum QFCϕ=1 when ϕbest=0.464 at the red point.
(a)
(b)In this procedure, we construct theQFCϕ=∑ijCij∣ϕ−m as a function of the filtering coefficient ϕ∈0,1 and find the minimum value of QFCϕ and the corresponding ϕ=ϕbest. Then, we get the approximation matrix Aappro with elements Aijappro=Cij∣ϕ=ϕbest of type-a vertices.


## 2.5. Estimation Procedure

In the work of [11], the authors introduced a method for estimating the number of communities in a unipartite network. We can use this method to determine the number of communities in the approximation network of a bipartite network.Riolo et al. [11] employed a more sophisticated approach, the degree-corrected stochastic block model, to overcome the shortcomings of the stochastic block model [31], which gives substantially better results for real-world network data. With the model specified, they find the probability P that a particular network with adjacency matrix A=Aij is found by the following equation:(13)PA∣ω,θ,g,k=∏i<jθiθjωgigjAije−θiθjωgigj×∏i12θi2ωgigiAii/2e−θi2ωgigi/2=∏iθidi∏r<sωrsmrse−nrnsωrs∏rωrrmrre−nr2ωrr/2,where k is the number of groups, gi denotes the group to which vertex i is assigned, r and s are the groups to which the vertices belong to, and mrs is the number of edges running between groups r and s. The parameter θi is used to independently control the average degree of each node and hence match any desired distribution. The parameter ωrs is the expected value of the adjacency matrix entry Aij for vertices i and j belonging to groups r and s, respectively, and they control the community structure. The parameters above have been discussed in detail in [31].After integrating the parametersω and θ, from equation (13), we have(14)PA∣g,k=∏rnrκrnr−1!nr+κr−1!×∏r<smrs!ρnrns+1mrs+1∏rmrr!1/2ρnr2+1mrr+1,where nr is the number of vertices in group r and κr is the sum of the degrees of the vertices in group r.We use equation (13) to derive the probability Pg,k∣A:(15)Pg,k∣A=Pg,kPA∣g,kPA,where(16)Pg,k=n−2−k∏r=1knr!.The valuesk and g define the “state” of a statistical mechanical system with the probability Pg,k∣A. States of this system are sampled in proportion to the probability using Markov chain Monte Carlo sampling. Then, an estimate of the probability Pk∣A of having k communities given the observed network A is found using the histogram of values of k over the Monte Carlo sample. Then, the most likely value of k is the one for which Pk∣A is greatest. For one network, we performed 10000 Monte Carlo sweeps, each one of which include n individual nodes moves of two types [11]. After one sweep, the values k and g may change, if k = 5, k = 3, and k = 2 show out, respectively, 5000, 3000, and 2000 sweeps, then fraction of community numbers P(k = 5/A) = 5000/10000 = 0.5, P(k = 4/A) = 0.3, and P(k = 2/A) = 0.2. Thus, the most likely value of k is 5.We setAappro as the input to the unipartite network communities number estimating method of Riolo et al. [11] to estimate the number of communities in the network of type-a vertices. Then, by transposing the affiliation matrix B and using the same method as above, we can estimate the number of communities in the network of type-b vertices.Now, let us analyze the time complexity of our method for type-a network. In the projection procedure, we take ONa2Nb times to calculate cosine similarity. Then, we take time approximately ONa2 to finish the filtering procedure, mainly finding the total degree ∑ijCij∣ϕ of one filtering matrix. Finally, we take ONak to move n nodes to k communities and ONa2k2 to calculate the complete probability Pg,k∣A, so the estimation procedure takes time ONa2. Therefore, the complete time complexity of our method is ONa2Nb+Nb2Na.


## 3. Results

In this section, we compare the partitions generated by other one-mode projections with the performance of the proposed biCNEQ. There are two types of projections, which we call classical unweighted projection (CUP) and classical weighted projection (CWP) in order to distinguish from our method. An unweighted projection of a bipartite network onto its type-a vertices is obtained by letting two type-a vertices i and j be connected if they share any type-b neighbor k. Each edge of a weighted projection has a weight equal to the number of shared neighbors. Given an adjacency matrix B=Na×Nb, the classical weighted projection matrix P and the classical unweighted projection matrix P¯ are, respectively, given by P=B2 and P¯ij=1,ifPij≥1,0,ifPij=0, where the diagonal blocks of Na×Na and Nb×Nb correspond to the projections onto type-a and type-b vertices, respectively. The matrix P is equivalent to a “two-step” adjacency matrix, with each entry weighted by the number of length-2 paths between each pair of vertices [4]. Then, we set P or P¯ as the input to the unipartite network communities number estimating method of Riolo et al. [11]. We will demonstrate that our method performs better than CUP and CWP in the following sections.


### 3.1. Synthetic Network: The Easy Case

As the mixed parameterλ increases, i.e., the level of noise is decreased, the fraction of correct community numbers of the approximation network of type-a vertices and type-b vertices calculated by the biCNEQ increases as a whole (blue line in Figure 4). However, CUP and CWP only give correct community numbers of the network in the noise-free situation (λ=1), as the red and green lines in Figure 4. Then, we use our method to derive the approximation networks of synthetic mixed networks generated with λ=0.6andλ=0.65 (red circles in Figure 4) and show posterior probabilities of the number of communities in the approximation network in Figure 5. As shown in Figures 4 and 5, when λ≥0.65, our method can estimate the correct number ka=4 of communities in the type-a vertices approximation network with the adjacent matrix Aa for this easy case. Analysis of the type-b vertices approximation network is carried out in the same way.Figure 4
Test of biCNEQ against classical projections on synthetic networks in the easy case. Each point shows the median of the corresponding values on 100 networks. (a) The fraction of correct numberka=4 of communities in the approximation network of type-a vertices. (b) The fraction of correct number kb=4 of communities in the approximation network of type-b vertices.
(a)
(b)Figure 5
Posterior probabilities calculated for the approximation networks of the synthetic mixed networks in the easy case. The synthetic networks were generated withλ=0.6 (a) and λ=0.65 (b). Each bar shows the median of the corresponding values on 100 networks.
(a)
(b)Next, we test whether the biCNEQ scales well when the parameters of synthetic networks were set as Table1. Firstly, we define success estimation rate (SER) as(17)SER=the  runs  of  Monte  Carlo  sweeps  that  estimates  correctly  the  highest  average  likelihoodthe  total  runs  of  Monte  Carlo  sweeps  performed,where each run includes 50000 Monte Carlo sweeps. The greater the SER is, the better the biCNEQ performs. As can be seen from Figure 6(a), our method performs reliably when λ≥0.65 and ka=kb=4 whereas CUP and CWP can only deal with the network when noise free. As can be seen from Figure 6(b), the biCNEQ performs less well when the size of communities ng grows. The biCNEQ performs less well when the level of noise increases, and the number K of planted communities grows and hardly gives right community number when K=Ka+Kb=20 and ng=300.Table 1
Parameters set for synthetic networks.
K
n
g
λ
m
r
s
,
r
=
1
,
…
,
K
a
,
s
=
r
+
K
a
Figure6(a)
K
a
=
K
b
=
4
100
0 to 1 with one step is 0.05
2000
Figure6(b)
K
a
=
K
b
=
7
100, 300
0.65 to 1 with one step is 0.05
2000, 18000
Figure6(c)
K
a
=
K
b
=
2
,
…
,
10
300
0.65, 0.8, 1
18000Figure 6
Tests of biCNEQ on synthetic networks with parameters set as Table1. For each network, we performed 10 runs of 50 000 Monte Carlo sweeps each. (a) The fraction of correct number ka=4 of communities in the approximation network of type-a vertices found by biCNEQ against classical projection as a function of λ. Each point shows the results from the run that finds the highest average likelihood. (b) The success estimation rate SER of biCNEQ tested on the approximation network of type-a of synthetic network with ng=100 against ng=300 as a function of λ. (c) The success estimation rate SER of biCNEQ tested on the approximation network of type-a of synthetic network with different values of λ as a function of the true number of communities Ka.
(a)
(b)
(c)


### 3.2. Synthetic Network: The Difficult Case

For our method, as shown in Figure7 (blue line), when the level of noise is decreased, the fraction of correct estimates of the number of communities of the approximation network type-a vertices remains stable with small fluctuations while λ<0.8. It increases sharply when λ≥0.8. That of type-b vertices remains stable with small fluctuations when λ<0.75 and increases sharply when λ≥0.75. We used our method to derive the approximation networks of synthetic mixed networks generated with λ=0.8and0.75 (see red circles in Figure 7) and show posterior probabilities of the number of communities in the approximation network in Figure 8. As seen from Figures 7 and 8, our method can estimate the correct number ka=2 of communities in the type-a vertices approximation network with the adjacent matrix Aa when λ≥0.8 and kb=3 of communities in the type-b vertices approximation network with the adjacent matrix Ab when λ≥0.75 for the difficult case.Figure 7
Test of biCNEQ against classical projections on synthetic networks in the difficult case. Each point shows the median of the corresponding values on 100 networks. The fraction of correct number (a)ka=2 of communities in the approximation network of type-a vertices and (b) kb=3 of communities in the approximation network of type-b vertices.
(a)
(b)Figure 8
Posterior probabilities calculated for the approximation networks of the synthetic mixed networks in the difficult case. The approximation network of (a) type-a vertices generated from a synthetic mixed network with λ=0.8 and (b) type-b vertices generated from a synthetic mixed network with λ=0.75. Each bar shows the median of the corresponding values on 100 networks.
(a)
(b)However, CUP and CWP can only correctly identify three communities in the type-b unipartite network without noise (λ=1) and fail to estimate the correct community number in testing on the type-a unipartite network, as the red and green lines shown in Figure 7, respectively. The reason is the average size of type-a communities (35 nodes) is bigger than that of type-b communities (10 nodes). Furthermore, we found that biCNEQ performs less well when the size of communities ng grows and fails to work even when ng reaches 40 nodes with λ=1 and ka=2,kb=3, which is a very small network.


### 3.3. Empirical Networks

We use our method, with a filtering coefficient ofϕ=0.614, as shown in Figure 3, to create the Southern women approximation network, whose adjacency matrix is denoted as Aw. Then, we use Aw as the input to the method of Riolo et al. [11]. As shown in Figure 9(a), we can estimate the correct number kw=2 of Southern women communities which matches the one determined in [4, 21, 22]. Figure 9(b) shows that, for the events, ke=3 receives the most weight but ke=2 comes a close second. It is interesting that the number of events groups in [21] is 2 but in [4], it is 3. However, the community numbers of women and events calculated by both the classical projection methods are 1 which is not plausible.Figure 9
Posterior probabilities calculated for the unipartite approximation network for the Southern women dataset using our method. For the approximation network of women and events, we performed 10 runs of 50, 000 Monte Carlo sweeps, respectively.
(a)
(b)


## 3.1. Synthetic Network: The Easy Case

As the mixed parameterλ increases, i.e., the level of noise is decreased, the fraction of correct community numbers of the approximation network of type-a vertices and type-b vertices calculated by the biCNEQ increases as a whole (blue line in Figure 4). However, CUP and CWP only give correct community numbers of the network in the noise-free situation (λ=1), as the red and green lines in Figure 4. Then, we use our method to derive the approximation networks of synthetic mixed networks generated with λ=0.6andλ=0.65 (red circles in Figure 4) and show posterior probabilities of the number of communities in the approximation network in Figure 5. As shown in Figures 4 and 5, when λ≥0.65, our method can estimate the correct number ka=4 of communities in the type-a vertices approximation network with the adjacent matrix Aa for this easy case. Analysis of the type-b vertices approximation network is carried out in the same way.Figure 4
Test of biCNEQ against classical projections on synthetic networks in the easy case. Each point shows the median of the corresponding values on 100 networks. (a) The fraction of correct numberka=4 of communities in the approximation network of type-a vertices. (b) The fraction of correct number kb=4 of communities in the approximation network of type-b vertices.
(a)
(b)Figure 5
Posterior probabilities calculated for the approximation networks of the synthetic mixed networks in the easy case. The synthetic networks were generated withλ=0.6 (a) and λ=0.65 (b). Each bar shows the median of the corresponding values on 100 networks.
(a)
(b)Next, we test whether the biCNEQ scales well when the parameters of synthetic networks were set as Table1. Firstly, we define success estimation rate (SER) as(17)SER=the  runs  of  Monte  Carlo  sweeps  that  estimates  correctly  the  highest  average  likelihoodthe  total  runs  of  Monte  Carlo  sweeps  performed,where each run includes 50000 Monte Carlo sweeps. The greater the SER is, the better the biCNEQ performs. As can be seen from Figure 6(a), our method performs reliably when λ≥0.65 and ka=kb=4 whereas CUP and CWP can only deal with the network when noise free. As can be seen from Figure 6(b), the biCNEQ performs less well when the size of communities ng grows. The biCNEQ performs less well when the level of noise increases, and the number K of planted communities grows and hardly gives right community number when K=Ka+Kb=20 and ng=300.Table 1
Parameters set for synthetic networks.
K
n
g
λ
m
r
s
,
r
=
1
,
…
,
K
a
,
s
=
r
+
K
a
Figure6(a)
K
a
=
K
b
=
4
100
0 to 1 with one step is 0.05
2000
Figure6(b)
K
a
=
K
b
=
7
100, 300
0.65 to 1 with one step is 0.05
2000, 18000
Figure6(c)
K
a
=
K
b
=
2
,
…
,
10
300
0.65, 0.8, 1
18000Figure 6
Tests of biCNEQ on synthetic networks with parameters set as Table1. For each network, we performed 10 runs of 50 000 Monte Carlo sweeps each. (a) The fraction of correct number ka=4 of communities in the approximation network of type-a vertices found by biCNEQ against classical projection as a function of λ. Each point shows the results from the run that finds the highest average likelihood. (b) The success estimation rate SER of biCNEQ tested on the approximation network of type-a of synthetic network with ng=100 against ng=300 as a function of λ. (c) The success estimation rate SER of biCNEQ tested on the approximation network of type-a of synthetic network with different values of λ as a function of the true number of communities Ka.
(a)
(b)
(c)


## 3.2. Synthetic Network: The Difficult Case

For our method, as shown in Figure7 (blue line), when the level of noise is decreased, the fraction of correct estimates of the number of communities of the approximation network type-a vertices remains stable with small fluctuations while λ<0.8. It increases sharply when λ≥0.8. That of type-b vertices remains stable with small fluctuations when λ<0.75 and increases sharply when λ≥0.75. We used our method to derive the approximation networks of synthetic mixed networks generated with λ=0.8and0.75 (see red circles in Figure 7) and show posterior probabilities of the number of communities in the approximation network in Figure 8. As seen from Figures 7 and 8, our method can estimate the correct number ka=2 of communities in the type-a vertices approximation network with the adjacent matrix Aa when λ≥0.8 and kb=3 of communities in the type-b vertices approximation network with the adjacent matrix Ab when λ≥0.75 for the difficult case.Figure 7
Test of biCNEQ against classical projections on synthetic networks in the difficult case. Each point shows the median of the corresponding values on 100 networks. The fraction of correct number (a)ka=2 of communities in the approximation network of type-a vertices and (b) kb=3 of communities in the approximation network of type-b vertices.
(a)
(b)Figure 8
Posterior probabilities calculated for the approximation networks of the synthetic mixed networks in the difficult case. The approximation network of (a) type-a vertices generated from a synthetic mixed network with λ=0.8 and (b) type-b vertices generated from a synthetic mixed network with λ=0.75. Each bar shows the median of the corresponding values on 100 networks.
(a)
(b)However, CUP and CWP can only correctly identify three communities in the type-b unipartite network without noise (λ=1) and fail to estimate the correct community number in testing on the type-a unipartite network, as the red and green lines shown in Figure 7, respectively. The reason is the average size of type-a communities (35 nodes) is bigger than that of type-b communities (10 nodes). Furthermore, we found that biCNEQ performs less well when the size of communities ng grows and fails to work even when ng reaches 40 nodes with λ=1 and ka=2,kb=3, which is a very small network.


## 3.3. Empirical Networks

We use our method, with a filtering coefficient ofϕ=0.614, as shown in Figure 3, to create the Southern women approximation network, whose adjacency matrix is denoted as Aw. Then, we use Aw as the input to the method of Riolo et al. [11]. As shown in Figure 9(a), we can estimate the correct number kw=2 of Southern women communities which matches the one determined in [4, 21, 22]. Figure 9(b) shows that, for the events, ke=3 receives the most weight but ke=2 comes a close second. It is interesting that the number of events groups in [21] is 2 but in [4], it is 3. However, the community numbers of women and events calculated by both the classical projection methods are 1 which is not plausible.Figure 9
Posterior probabilities calculated for the unipartite approximation network for the Southern women dataset using our method. For the approximation network of women and events, we performed 10 runs of 50, 000 Monte Carlo sweeps, respectively.
(a)
(b)


## 4. Conclusions

In this paper, we developed a method called biCNEQ for inferring the number of pure-type communities into which a bipartite network can divide. We designed a measure of the filtering quality named QFC to select a threshold of filtering coefficient to filter a weighted similarity network projected from a bipartite network to obtain a binary unipartite network. Then, we used the method of [11] to estimate the number of communities in the approximation network of each type of vertices. Via tests, biCNEQ gives correct answers and performs better than the classical unweighted and weighted projection methods on an empirical network with a known community structure and mixed synthetic networks including an easy case and a difficult case.As discussed in the last section, the performance of our method degrades when the community size grows, especially in the difficult case synthetic network. This shortcoming makes biCNEQ hard to scale well on the real-world networks where there exists community structure. The reason for this may be due to information loss in the projection and filtering procedure or other stages of the proposed method. Thus, in the future work, the following two issues can be investigated: (1) an improved projection approach to minimize the information lost in the biCNEQ method can be developed and (2) a projection-free approach using a bipartite degree-corrected stochastic block model and Markov chain Monte Carlo sampling may be proposed.



---

*Source: 4310561-2019-05-21.xml*