Refinement for community structures of bipartite networks

Modularity-based network community detectionPorter2009 ; Fortunato2010 ; Newman2004 is arguably the most popular framework for identifying communities in networks, partly because of its already established status quo including various numerical tools on top of its mathematically intuitive interpretation of detecting densely connected subsets of nodes. The most widely used type of modularity function for a given community partition $\{g_{i}\}$ ($g_{i}$ represents the community identity of node $i$) is given by

where the adjacency matrix elements $A_{ij}$ represent the existence of an edge between nodes $i$ and $j$ ($A_{ij}=1$ if the edge exists and $A_{ij}=0$ if it does not)⁴⁴4We only consider undirected networks with $A_{ij}=A_{ji}$ for every node pairs $(i,j)$, as the concept of communities in directed networks can be quite nontrivial. For the interested readers, see Refs.Leicht2008 ; YKim2010 , and the degree $k_{i}$ represents the number of neighbors of node $i$ and is given by $k_{i}=\sum_{j}A_{ij}$. The normalization constant is $\sum_{i}k_{i}=2m$, and the summand is counted only when the Kronecker delta term $\delta(g_{i},g_{j})$ is turned on for the node pairs $i$ and $j$ belonging to the same community. In the case of weighted networks, the elements $A_{ij}$ represents the weight on the edge between nodes $i$ and $j$ ($A_{ij}=0$ when the edge between nodes $i$ and $j$ is absent), and the strength $k_{i}$ represents the sum of the weights around node $i$, i.e., $k_{i}=\sum_{j}A_{ij}$ (the same formula as the degree in the case of unweighted networks). An important assumption behind the modularity function in Eq. (1) is that the contribution of each edge to the modularity is subtracted by the term $k_{i}k_{j}/(2m)$ called the Newman-Girvan (NG) null-model term named after the authors of Ref.Newman2004 and corresponds to the expected probability of the edge’s existence judged solely from each node’s degree. A practically useful parameter here is the resolution parameter $\gamma$ in front of the null-model term, which controls the overall scale of detected communitiesPorter2009 ; Fortunato2010 ; Reichardt2006 ; Onnela2012 . The role of $\gamma$ was first found empiricallyReichardt2006 , but the parameter has been demonstrated to be indeed related to the parameters controlling the number of preassigned communities in the stochastic block modelNewman2016 .

As a reminder, the mathematical form of the NG null-model term $k_{i}k_{j}/(2m)$ in Eq. (1) comes from the assumption of our ignorance except for the degree information: the larger the degree of a node is, the more likely the node will be connected to any other node. In reality, of course, one may get access to additional information that can sharpen the null-model term. Therefore, in general, the modularity function can be generalized as

where $P_{ij}$ is the generalized null-model term representing the expected probability of the existence of an edge connecting nodes $i$ and $j$ from all of the information available to usBassett2013 . For instance, a network can be embedded in space, and one may know the functional form of the distance-dependent connection probability, which can be utilized to set $P_{ij}$ to encode the spatial informationSHLee2019 .

For bipartite networks composed of two distinct types of nodes, the structural constraint of not allowing edges between the nodes of the same type can directly be used to modify $P_{ij}$. The specific type of null-model for bipartite networks called the Barber (BB) type null-model Barber2007 (named after the author of Ref.Barber2007 , of course), used in this work is illustrated in Fig. 1. Suppose that we have a given community structure (the light purple community above and the light green community below) in the bipartite network in Fig. 1(a). The NG null-model term in Eq. (1) corresponds to the “average” connection illustrated in Fig. 1(b) regardless of node types, which obviously allows a connection between nodes of the same type that would never exist in reality by construction. In other words, if we just use the original modularity in Eq. (1) to detect communities in bipartite networks, the modularity function $Q$ will include meaningless negative values in the summand, which would require unnecessary computational time and may systematically produce a misleading result in the worse case. In contrast, if we use the BB type null-model term corresponding to Fig. 1(c), the expected edges only connect node pairs from different types of nodes, and the modified modularity function in Eq. (2) with $P_{ij}$ in Ref.Barber2007 [$P_{ij}=0$ for all of the node pairs $(i,j)$ from the same type and $P_{ij}=k_{i}k_{j}/(2m)$ if nodes $i$ and $j$ are of different types] will yield communities more efficiently and more accurately. In practice, as illustrated in Fig. 1(d), we can directly use various types of modularity maximization algorithms for detecting communities in unipartite networks by constructing the augmented square matrix and its NG null-model counterpart for each rectangular blocks (equivalent to the BB-type null-model term).

Among modularity-maximization-based community detection algorithms, we use the GenLouvain algorithmGenLouvain , which is a variant of the popular Louvain algorithmLouvain . The algorithm is known for its convenient implementation and computational efficiency, but more importantly in this work, it is a stochastic algorithm allowing in principle different detection results for each realization. How can such a property be beneficial at all? We will look into that now.

One of the most tricky parts of network community detection is that in most cases, no ground-truth community division exists in the first place. In other words, finding communities is not searching for a rigorously defined mathematical object, but is close to trying an ensemble of divisions for a given network structure, the ultimate goal of which is the expectation of extracting practically useful results. In this spirit, throughout the series of worksHKim2019 ; DLee2021 in which the author participated, we have demonstrated that multiple different results of community detection, usually expressed as community inconsistencyHKwak2011 ; Lancichinetti2012 , are not necessarily a malfunction of stochastic algorithms that should be remedied. Local inspection of such an inconsistency provides valuable information on an individual node’s function as bridges connecting communitiesHKim2019 , and more importantly in this work, global inspection of community inconsistency effectively plays the role of a statistical reliability test, especially for a range of community resolution adjusted by using the $\gamma$ parameter in Eqs. (1) or (2).

Of course, due to the fundamental limit of community detection mentioned in the first part of this subsection, we should take the reliability as a measure of self-consistency rather than a ground-truth solution, but it still provides practically useful evidence on the validity of detected communities. In this work, we take the global inconsistency measure called the partition inconsistency (PaI) curve $\Omega$ as a function of the resolution parameter $\gamma$ introduced in Ref.DLee2021 and utilize it as the main inspection tool for comparative analysis on the effect of different null-model terms for bipartite networks. The PaI quantifies how inconsistently communities are detected for a given ensemble of results from a stochastic network community detection algorithm.

From the total number $m$ of community detection realizations, we denote the number of unique configurations detected by $\mathcal{C}$ and the proportion of each configuration $\alpha\in\{1,2,\cdots,\mathcal{C}\}$ by $p_{\alpha}=m_{\alpha}/m$, where $m_{\alpha}$ is the number of configurations that include $\alpha$. The similarity $S_{\alpha\beta}$ between configurations $\alpha$ and $\beta$ is defined by employing the element-centric similarity (ECS)⁵⁵5The ECS measure introduced in Ref.EC has a number of advantages over other conventional measures of similarity between different community configurations such as normalized mutual information (NMI), so we strongly encourage the practitioners of network community detection to try different measures instead of sticking to a single measure just because it is widely used.EC . In the cluster-induced element graph of configuration $\alpha$, we assign an attribute of node $i$ with respect to another node $j$, which is the stationary probability distribution $f_{ij}^{\alpha}$ induced by the personalized PageRank algorithm (PPR)PPR applied to node $i$. Then, the ECS between two community configurations $\alpha$ and $\beta$ is defined as

where $N$ is the number of nodes and $f_{ij}^{\alpha}$ is node $j$’s relative importance in the stationary state of PPR starting from the node $i$ in configuration $\alpha$. We use the default value of the damping factor $d=0.9$ as used in Ref.EC . Based on this similarity measure, we define the PaI of a community ensemble as

which corresponds to the reciprocal of the average similarity (weighted by the relative appearance $\{p_{\alpha}\}$) between all configuration pairs. If all the configurations are independent of the others and emerge with the same uniform probability $p_{\alpha}=1/\mathcal{C}$, all of the off-diagonal components of $S_{\alpha\beta}$ vanish, and the PaI of this ensemble reaches the maximum value of $\mathcal{C}$. In contrast, if every realization of the community detection gives exactly the same community structure, it becomes trivially $\Omega=1$ (the minimally inconsistent or the maximally consistent case). We will now see if the more sophisticated null-model term introduced by BarberBarber2007 indeed gives more reliable community divisions than the original NG null-model termNewman2004 .

As the first test, we use a series of bipartite model networks with planted community structures, almost literally a direct realization of Fig. 1(a). For a bipartite network model, we initially prepare two different types of nodes that will be connected only between nodes of different types. Our first bipartite network model called the “3vs3 model” is composed of $600$ nodes in total, each half of which constitutes a network type. (Thus, there are $300$ nodes for each type.) Each type of node is located either on the left (circular nodes) or right (square nodes) of the network illustrated in Figs. 2(a) and (b). The $300$ nodes of each type are further divided into three different equal-sized groups, with $100$ nodes for each group, vertically spaced in Figs. 2(a) and (b). The uppermost and the lowermost groups of different types are randomly connected to each other on the same vertical level with the probability $p_{\mathrm{in}}=0.1$ (the connection is only between nodes of different types of course, according to the definition of bipartite networks), and they are randomly connected to the groups located on different vertical levels with the probability $p_{\mathrm{out}}=0.02$. The nodes in the middle group (in terms of the vertical level) are randomly connected to any node of a different type with the probability $p_{\mathrm{mid}}=0.06$.

With this construction, for the 3vs3 model, we have two clear-cut communities (the uppermost and lowermost ones) and one group of nodes (the middle one) without any community identity, which we intentionally put to simulate noisy community-inconsistent parts [the local inconsistency is shown by large membership inconsistency (MeI)DLee2021 values in Figs. 2(a) and (b)]. The comparative inconsistency curves from the NG and the BB types of null-model terms [Figs. 2(c) versus 2(d)] share a common property that the inconsistency shows a local minimum In the range of $\gamma$ that yield two communities ($n_{c}=2$), which is supposedly detecting the planted communities. As discussed in Ref.DLee2021 , this type of local minima of PaI in the range of the flat value (an integer value, ideally) for the number of communities is a characteristic signature of statistically reliable communities with a small inconsistency level. However, if we observe the range of the resolution parameter $\gamma$ allowing those reliable communities, the BB null-model term [Figs. 2(d)] produces a notably wider range of $\gamma$ for valid community detection than the NG null-model term [Figs. 2(c)].

In other words, appropriate communities can be detected with the NG null-model term (as in previous worksSHLee2010 ; WCai2020 ; SHLee2020 ),just as with the BB null-model term, if we carefully choose the resolution parameter. At the same time, however, please note that if we use the BB null-model term tailor-made for treating underlying bipartite structures, the detected community structure is much less sensitive to the choice of $\gamma$, which signifies the importance of constructing the null-model term $P_{ij}$ in Eq. (2) by using as much information as possible. The same result is observed for other variants of the model.

The “3vs2 model” shown in Fig. 3 is composed of three groups on the left and the two groups on the right. The uppermost and the lowermost groups on the left are connected to the upper and lower groups on the right with the probability $p_{\mathrm{in}}=0.1$, respectively (and the cross-connection between the upper and the lower groups occurs with the probability $p_{\mathrm{out}}=0.02$). Moreover, the middle group on the left is connected to any group on the right with the probability $p_{\mathrm{mid}}=0.06$. The “3vs2BigSmall model” shown in Fig. 4 is also composed of three groups on the left and the two groups on the right, but for this model the middle group on the left is connected more densely with the lower group on the right with the probability $p_{\mathrm{mid}}=0.06$ than with the upper group on the right with the probability $p_{\mathrm{out}}=0.02$. The resultant 3vs2BigSmall model is composed of two clear-cut communities with different relative sizes.

For both models (3vs2 and 3vs2BigSmall), the results in Figs. 3 and 4 support the same conclusion: both types of null-model terms (NG and BB) can produce planted communities, but the BB null-model term always allows wider ranges of $\gamma$ including reliable community structures (in these cases, the planted or the ground-truth communities). With the verification learned from the model bipartite networks, in the next subsection, we will continue the cross-examination of null-model terms by taking into consideration real networks.

As we have checked the importance of the proper (BB) null-model termBarber2007 for community detection in model bipartite networks, we now start to cross-check different null-model terms in cases of real bipartite networks without explicitly given ground-truth communities. The first example is the bipartite network between languages and the countries in which they are spokenKONECT . The PaI curves and the average number of communities from the different null models in Fig. 5 show a similar trend to the model network results: the range of $\gamma$ yielding consistent communities (small inconsistency) is wider for the BB null-model term. In particular, we observe a sharp transition near $\gamma=4$, as shown in Fig. 5(b), i.e., jumping from $n_{c}\simeq 80$ to $n_{c}\simeq 120$, which may signal a characteristic division of linguistic cultural groups. Such a transition is not observed in the case of the NG model [Fig. 5(a)], which would miss this nontrivial piece of information. Therefore, it is another example that those detailed characteristics in each system necessitate a carefully chosen null-model term for detection.

Another example bipartite network is the association between human diseases and their related human genesKIGoh2007 , as shown in Fig. 6. Although the number of communities varies with quite similar functional forms for different null-model terms, the PaI curve from the BB null-model term shows more abrupt (vertical) fluctuations (the horizontal ranges of $\gamma$ for local minima are similar in this case), which might be better at pinpointing the appropriate range of $\gamma$.

Finally, we re-examine the community structure of bipartite mutualistic networks (pollination or seed dispersal) composed of animals and plants the author previously analyzed with the NG null-model termSHLee2020 . Based on the absence of the $\gamma$-range with a local minimum of PaI and with the flat part of the number $n_{c}$ of communities, the author has concluded that the community structure seems to be absent from this system, compared with other notable mesoscale structures such as core-periphery-nessRombach2014 and nestednessMariani2019 . As one can check from Fig. 7 (a single example is presented in the figure, but we have checked all of the networks and confirmed the general conclusion), the overall functional shapes of PaI and $n_{c}$ against the resolution parameter $\gamma$ are qualitatively similar for both the NG and the BB null-model terms, so we conclude that the absence of a well-defined community structure in mutualistic networks can be confirmed even with the BB null-model term modified to handle bipartite networks properly. If we observe the range of large $\gamma$ values in Fig. 7(b) carefully, though, the functional shape seems to deviate systematically from the NG null-model case, so further studies might be required for a more statistically concrete conclusion.