betaFeedback

WorksComputer Science

Hierarchical Community Detection in Bipartite Networks

Abstract

Many bipartite networks exhibit hierarchical community structure, but existing community detection methods are not well-suited for detecting hierarchy. They also do not effectively handle weighted bipartite networks. In this work, we introduce a novel modularity-based objective function, called the generalized bipartite modularity density, Qbg, specifically designed for hierarchical community detection in bipartite systems. The framework incorporates a tunable resolution parameter that enables systematic exploration of community structure across multiple scales. It leverages resolution-limit behavior in bipartite networks as a tool to uncover hierarchical organization without projecting the network or altering its intrinsic bipartite topology. We evaluate the method using a hierarchical synthetic bipartite benchmark and apply it to two empirical networks. In all cases, Qbg recovers established mesoscale structure while revealing additional hierarchical and fine-scale organization beyond that detected by conventional bipartite approaches. These results establish Qbg as a flexible, interpretable, and resolution-aware framework for hierarchical community detection in bipartite networks.

Introduction

Community detection is a central problem in network science, providing insight into the structural and functional organization of complex systems [1, 2]. In many real-world networks, community organization is inherently hierarchical, with meaningful structure present across multiple scales [1, 3, 4]. Bipartite networks form an important class of network representations in which nodes are partitioned into two disjoint sets and edges connect only nodes of different types, often with weights encoding the strength of interactions. Such bipartite structures arise naturally in diverse domains, including social affiliation and collaboration networks [5, 6], social interaction systems [7, 8], and biomedical data [9, 10]. In many of these systems, community organization is expected to span multiple scales, motivating the need for methods capable of resolving hierarchical community structure while preserving the intrinsic bipartite topology.

Most existing community detection approaches for bipartite networks are based on modularity optimization. A well-known limitation of such methods is the resolution limit, which can cause small but well-defined communities to be merged into larger clusters [11, 12, 13]. However, previous work has shown that, rather than being a drawback, the scale associated with the resolution limit can be exploited as a tool to uncover hierarchical structure in unipartite networks by varying a resolution parameter [14]. In that work, a modularity-based objective function, termed the generalized modularity density, was introduced, incorporating a tunable parameter that enables the resolution of community structure at any desired scale.

Building on this idea, we extend the framework to bipartite networks. To this end, we introduce a novel objective function, termed the Generalized Bipartite Modularity Density, which incorporates a tunable resolution parameter λ\lambda. This parameter enables the systematic detection of communities at different scales, allowing hierarchical community structure to be identified directly within bipartite networks while preserving their intrinsic topology.

The remainder of the paper is organized as follows. In § 2, we present the proposed framework. We first discuss the resolution-limit problem in bipartite networks, followed by the definition of the generalized bipartite modularity density and its properties. We then analyze resolution-limit behavior using a benchmark network. In Sec. III, we first evaluate the performance of the method on benchmark tests. We then demonstrate its applicability to both synthetic and real-world bipartite networks, including hierarchical artificial networks, the Southern Women network, and an asthma patient network. Finally, additional analytical details and supporting results are provided in the Appendix.

Methods

Resolution Limit in Bipartite Networks

In the bipartite setting, the resolution-limit problem was explicitly demonstrated using a synthetic benchmark consisting of a ring of interconnected bipartite cliques [15]. In this construction, standard modularity-based methods incorrectly merge adjacent cliques and fail to recover the planted community organization, illustrating how resolution-limit effects can obscure hierarchical structure even in simple, well-controlled bipartite systems.

To examine this limitation more closely, we analyze the bipartite modularity formulation introduced by Barber [16], which extends modularity to bipartite networks without requiring one-mode projection. This formulation evaluates the quality of a partition by comparing observed edge weights within communities to those expected under an appropriate bipartite null model. The bipartite modularity introduced by Barber [16] is defined as

Qb=1F∑c(mc−qcdcF)(1)Q_b = \frac{1}{F} \sum_c \left(m_c - \frac{q_c d_c}{F}\right) \tag*{(1)}

where FF denotes the total edge weight of the bipartite graph, mcm_c is the total weight of edges within community cc, and qcq_c and dcd_c represent the total (weighted) degrees of the two node types within community cc.

We consider two competing partitions of a bipartite kk-clique ring: the Separated phase (S), in which each bipartite clique forms an individual community, and the Merged phase (M), in which adjacent cliques are grouped into larger modules [15]. Let Qb(S)Q_b(S) and Qb(M)Q_b(M) denote the corresponding bipartite modularity values. If

Qb(S)>Qb(M),(2)Q_b(S) > Q_b(M), \tag*{(2)}

then bipartite modularity favors the finer partition; otherwise, it fails to resolve all communities due to the resolution limit.

Our analytic derivation shows that this inequality holds only when

k>n−22,(3)k > \sqrt{\frac{n-2}{2}}, \tag*{(3)}

where kk is the size of each bipartite clique and nn is the number of cliques in the ring. The detailed derivation, which corrects the earlier result reported in [15], is provided in Appendix A. This demonstrates that Barber’s bipartite modularity is also subject to a resolution limit and fails to recover the planted community structure when kk is small.

Generalized Bipartite Modularity Density

We introduce a novel modularity-based objective function, termed the Generalized Bipartite Modularity Density, designed for hierarchical community detection in bipartite networks. It is defined as

Qbg=1F∑c(mc−qcdcF)ρcχ,(4)Q_{bg} = \frac{1}{F} \sum_c \left(m_c - \frac{q_c d_c}{F}\right) \rho_c^\chi, \tag*{(4)}

where FF denotes the total edge weight of the bipartite network, mcm_c is the total weight of edges within co-cluster cc, and qcq_c and dcd_c represent the total weighted degrees of the two node types within cluster cc. The quantity ρc\rho_c denotes the internal link density of co-cluster cc, defined as

ρc=mcnrnb,(5)\rho_c = \frac{m_c}{n_r n_b}, \tag*{(5)}

where nrn_r and nbn_b are the numbers of nodes of the two types in the cluster. This density measures the fraction of realized links relative to the maximum possible number of bipartite connections. The parameter χ\chi is a tunable resolution parameter that controls the influence of internal link density on the modularity score.

By construction, QbgQ_{bg} reduces to the standard bipartite modularity QbQ_b when χ=0\chi= 0, preserving its emphasis on dense intra-community connectivity. For χ>0\chi> 0, the contribution of link density is progressively amplified, enabling explicit control over the resolution at which communities are detected. This makes QbgQ_{bg} a natural and interpretable multi-resolution extension of bipartite modularity.

The formulation in Eq. (4) naturally extends to weighted networks by interpreting mcm_c, qcq_c, and dcd_c as sums of link weights rather than edge counts, as in weighted modularity [17, 18]. However, incorporating link density in weighted networks requires additional care. A naive approach computes ρc\rho_c by ignoring weights and treating the network as unweighted [19], which discards information about edge strength. A more consistent definition introduces a weighted density,

ρc=mc(nrnb)wmax⁡,(6)\rho_c = \frac{m_c}{(n_r n_b)w_{\max}}, \tag*{(6)}

where wmax⁡w_{\max} is the maximum link weight in the network. While this definition preserves consistency with the unweighted case, it introduces strong sensitivity to extreme weight values. In particular, when link weights vary widely and the maximum weight wmax⁡w_{\max} is large, the value of ρc\rho_c becomes very small, which can lead to numerical instability in modularity density–based optimization.

In contrast, the generalized modularity density QbgQ_{bg} avoids this instability. In Eq. (4), both terms inside the summation are multiplied by ρcχ\rho_c^\chi, so the global factor wmax⁡χw_{\max}^\chi factors out uniformly across all partitions. As a result, the optimization of QbgQ_{bg} is independent of the absolute scale of edge weights, allowing relative link density to be used without affecting the outcome.

By tuning the parameter χ\chi, the method flexibly favors either the merging or separation of communities, depending on the desired level of granularity. As shown below II C, for appropriate values of χ\chi, maximizing QbgQ_{bg} can correctly identify distinct communities even in the presence of substantial interconnectivity. This flexibility makes QbgQ_{bg} particularly well suited for networks with hierarchical or multi-scale community structure, which are commonly observed in real-world systems.

Finally, we evaluate the performance of QbgQ_{bg} by comparing it with standard bipartite modularity QbQ_b on a challenging benchmark network that extends beyond simple ring-of-cliques constructions. Our results show that QbgQ_{bg} consistently outperforms QbQ_b across the benchmarks considered, accurately recovering the underlying community structure.

Resolution Limit Analysis on a Benchmark Network

The resolution limit (RL) problem arises when an objective function incorrectly merges well-defined communities [20]. A resolution-limit-free method should separate such groups while avoiding the artificial fragmentation of strongly connected ones.

We analyze this issue using the benchmark network shown in Figure 1, which is a bipartite extension of benchmark constructions introduced in [14, 21]. The network consists of two fully connected bipartite cliques and an external arbitrary component to which the cliques are weakly connected.

Benchmark network consisting of two fully connected bipartite cliques and an arbitrary external component

Figure 1. Benchmark network designed to study the resolution limit problem. It consists of two fully connected bipartite cliques of sizes n1n_1 and n2n_2, and an arbitrary external component containing nan_a nodes and total internal weight mam_a. The cliques are weakly connected to this external component via m1am_{1a} and m2am_{2a} weighted links, respectively. Additionally, the cliques are connected to each other via m12m_{12} links. If the network is weighted, then mam_a, m1am_{1a}, m2am_{2a}, and m12m_{12} represent the sum of link weights in their respective regions.

Let clique 1 contain nr1n_{r1} red nodes and nb1n_{b1} blue nodes, and clique 2 contain nr2n_{r2} red nodes and nb2n_{b2} blue nodes. Without loss of generality, we assume nr2nb2≥nr1nb1n_{r2}n_{b2} \ge n_{r1}n_{b1}. Let m12m_{12} denote the total weight of links between the two cliques, m1am_{1a} and m2am_{2a} the total weights of links connecting each clique to the external component, and mam_a the total internal weight of the external component, which contains nan_a nodes. We assume the cliques are weakly connected to the external component, such that m1a≪nr1nb1m_{1a} \ll n_{r1}n_{b1} and m2a≪nr2nb2m_{2a} \ll n_{r2}n_{b2}.

To characterize the network structure, we introduce the normalized inter-clique link density

d=m12nr1nb1nr2nb2d = \frac{m_{12}}{\sqrt{n_{r1}n_{b1}n_{r2}n_{b2}}}

the external influence parameter

t=manr1nb1nr2nb2t = \frac{m_a}{\sqrt{n_{r1}n_{b1}n_{r2}n_{b2}}}

the relative size ratio

p=nr1nb1nr2nb2p = \frac{\sqrt{n_{r1}n_{b1}}}{\sqrt{n_{r2}n_{b2}}}

and the clique size parameter

r=p+1p=nr1nb1+nr2nb2nr1nb1nr2nb2.r = p + \frac{1}{p} = \frac{n_{r1}n_{b1} + n_{r2}n_{b2}}{\sqrt{n_{r1}n_{b1}n_{r2}n_{b2}}}.

The parameter p∈(0,1]p \in(0,1] quantifies the relative sizes of the two cliques, while t∈[0,∞)t \in[0,\infty) measures the strength of the external component. For a given objective function, there exists a critical inter-clique link weight mexpm_{\mathrm{exp}} that determines whether the two cliques are merged or remain separated. Specifically, the cliques should be merged when m12≥mexpm_{12} \ge m_{\mathrm{exp}} and separated otherwise. We define the normalized expected critical density

δexp=mexpnr1nb1nr2nb2\delta_{\mathrm{exp}} = \frac{m_{\mathrm{exp}}}{\sqrt{n_{r1}n_{b1}n_{r2}n_{b2}}}

which enables resolution-independent comparison across networks of different sizes.

For a fixed set of parameters, the optimization outcome partitions the parameter space into a Merged (M) phase and a Split (S) phase, separated by a critical value δ\delta. An objective function is said to be resolution-limit-free with respect to the expected density if δ≥δexp\delta\ge\delta_{\mathrm{exp}} for all parameter configurations of the benchmark network.

Results

Benchmark test

We analytically examine the resolution-limit (RL) behavior of the benchmark network shown in Figure 1 using QbgQ_{bg} as the objective function. This analysis allows us to determine whether QbgQ_{bg} favors merging or splitting the two bipartite cliques under different network configurations, and to compare its behavior with that of other modularity-based objective functions.

Whether QbgQ_{bg} favors merging or splitting the cliques is determined by the sign of the quantity

ΔQbg=Qbgmerge−Qbgsplit,(7)\Delta Q_{bg}=Q_{bg}^{\mathrm{merge}}-Q_{bg}^{\mathrm{split}}, \tag*{(7)}

where QbgmergeQ_{bg}^{\mathrm{merge}} and QbgsplitQ_{bg}^{\mathrm{split}} are the values of QbgQ_{bg} when the cliques are merged and split, respectively. If ΔQbg<0\Delta Q_{bg}<0, the split partition yields a higher objective value and the cliques remain separate; if ΔQbg>0\Delta Q_{bg}>0, the merged partition is preferred and the cliques are grouped into a single community. This criterion provides a clear way to assess how QbgQ_{bg} handles community resolution across different benchmark configurations.

Then for QbgQ_{bg},

ΔQbg∼(d+rr+2)χ(d+r−(d+r)2r+t+d)−(r−rd+r2−2r+t+d)(8)\Delta Q_{bg}\sim\left(\frac{d+r}{r+2}\right)^{\chi}\left(d+r-\frac{(d+r)^2}{r+t+d}\right)-\left(r-\frac{rd+r^2-2}{r+t+d}\right) \tag*{(8)}

where r=p+1pr=p+\frac{1}{p}. Equation 8 determines whether, for a given value of the control parameter χ\chi, the system lies in the Merged (M) or Split (S) phase as a function of the parameters (p,d,t)(p,d,t). The threshold link density, denoted δQbg\delta_{Q_{bg}}, corresponds to the critical value of dd at which the transition between the M and S phases occurs, that is, the point where ΔQbg=0\Delta Q_{bg}=0.

When the external influence parameter tt becomes large, a situation commonly encountered in practical applications, the asymptotic form of δQbg\delta_{Q_{bg}} for a fixed χ\chi is given by

lim⁡t→∞δQbg→r((1+2r)χχ+1−1)(9)\lim_{t\to\infty}\delta_{Q_{bg}}\to r\left(\left(1+\frac{2}{r}\right)^{\frac{\chi}{\chi+1}}-1\right) \tag*{(9)}

The limiting value of δQbg\delta_{Q_{bg}} increases from 0 when χ=0\chi=0 and approaches 1 as χ→∞\chi\to\infty, independent of the value of pp. For intermediate values of χ\chi, the dependence on pp is weak, with slightly higher critical values observed at smaller pp, as illustrated in Figure 2. This figure shows the phase diagram in the (p,d)(p,d) plane for several values of χ\chi under conditions of large external influence. When χ=0\chi=0, the cliques remain merged across the parameter space shown in Figure 2(a). For χ>0\chi>0, the cliques become separated at lower values of dd, indicating that they are successfully resolved. As χ\chi increases, the critical density δQbg\delta_{Q_{bg}} increases and approaches 1, as seen in Figure 2(b)–(Figure 2d). This implies that for sufficiently large χ\chi, the cliques are resolved throughout the parameter space.

Phase diagrams of clique splitting using $Q_{bg}$ for different values of $\chi$

Figure 2. Phase diagram of clique splitting using QbgQ_{bg} at large external influence as χ\chi varies. The regions where the M phase occurs are shown in orange, and the regions where the S phase occurs are shown in blue. Results are presented for different values of the control parameter χ\chi: (a) χ=0\chi= 0, (b) χ=0.2\chi= 0.2, (c) χ=0.5\chi= 0.5, and (d) χ=1.0\chi= 1.0. The external influence parameter is set to t=106t = 10^{6}.

The effect of varying the external influence parameter tt at fixed χ\chi is shown in Figure 3. When t=0t=0, as shown in Figure 3(a), the external component is absent and the S phase occupies the entire (p,d)(p,d) space. In this case, δQbg=1\delta_{Q_{bg}}=1 for all values of pp, implying that the cliques remain separated unless they are fully connected. When t>0t>0, the presence of the external component promotes merging at sufficiently large values of dd, reflecting a loss of resolution. As tt increases, shown in Figure 3(b)–(Figure 3d), the M phase expands and δQbg\delta_{Q_{bg}} decreases, eventually approaching the limiting value given by Equation 9.

Phase diagrams of clique splitting using $Q_{bg}$ for different values of $t$

Figure 3. Phase diagram of clique splitting using QbgQ_{bg} at fixed χ=1\chi= 1, as the external influence parameter tt is varied. The regions in the (p,d)(p,d) space where the Merged (M) phase occurs are indicated in orange, while the Split (S) phase regions are shown in blue. Results are presented for different values of tt: (a) t=0t = 0, (b) t=10t = 10, (c) t=104t = 10^{4}, and (d) t=106t = 10^{6}.

These results demonstrate that adjusting the control exponent χ\chi provides a direct way to tune δQbg\delta_{Q_{bg}} over a wide range. This tunability becomes broader as tt increases, and in the limit of large tt, δQbg\delta_{Q_{bg}} spans the full interval from 0 to 1. This flexibility is advantageous in applications, as it allows χ\chi to be chosen such that δQbg\delta_{Q_{bg}} matches the expected critical resolution density δexp\delta_{\mathrm{exp}}.

As χ\chi increases, the number of detected communities generally increases, while the results stabilize over a range of χ\chi values (see the example in Section III B 1). Increasing χ\chi typically leads to the detection of smaller communities. The optimal choice of χ\chi depends on the specific problem under consideration. When prior information about the community structure is available, it can guide the selection of χ\chi. In the absence of such information, χ=1\chi= 1 provides a reasonable default choice. A key advantage of the QbgQ_{bg} metric is that even for extreme values of tt and rr, it maintains a positive lower bound δQbg\delta_{Q_{bg}}, which can be adjusted through the choice of χ\chi.

Applications

Artificial hierarchical bipartite network

To examine how the proposed generalized bipartite modularity density QbgQ_{bg} captures multiscale community structure, we construct an artificial hierarchical bipartite network designed to exhibit clear organization across multiple resolution levels. Inspired by hierarchical network models [14, 22], the construction consists of four nested levels, each corresponding to a distinct structural scale.

At Level 1, the basic building block is a bipartite clique in which all red nodes are fully connected to all blue nodes, with each link assigned a weight α1\alpha_1. At Level 2, these Level 1 cliques are treated as generalized nodes and assembled into a larger clique, with full interconnections weighted by α2\alpha_2. This procedure is iterated such that the Level kk structure is formed by treating each Level k−1k-1 network as a generalized node and arranging them into a clique of size five, with interconnections weighted by αk\alpha_k. To preserve a clear hierarchical organization, the link weights are chosen to satisfy α1>α2>⋯>αk\alpha_1 > \alpha_2 > \cdots> \alpha_k, ensuring that connections weaken systematically at higher levels of the hierarchy. A schematic illustration of this construction is shown in Figure 4.

Artificial hierarchical bipartite network

Figure 4. Artificial hierarchical bipartite network. Level 1: A bipartite clique of three blue and three red nodes. Level 2: A clique of five Level 1 cliques. Level 3: A clique of five Level 2 cliques. Level 4: A clique of five Level 3 cliques.

We apply the QbgQ_{bg} metric to a Level 4 hierarchical network constructed using αk=5−k\alpha_k = 5^{-k}. The resulting network contains 216 Level 1 cliques, comprising a total of 648 red nodes and

648 blue nodes. By maximizing QbgQ_{bg}, we demonstrate that the planted community structure at each hierarchical level can be successfully recovered. The communities identified at different resolutions are shown in Figure 5, where distinct partitions emerge as the resolution parameter χ\chi is varied.

Figure 5. Multiresolution community detection in the artificial hierarchical bipartite network. The generalized bipartite modularity density QbgQ_{bg} is plotted as a function of the resolution parameter χ\chi, with curves corresponding to partitions into 6 cliques (blue), 36 cliques (orange), and 216 cliques (green). (a) Low-resolution regime, −1.5≤χ≤1.5-1.5 \leq\chi\leq1.5. In this regime, for χ<0.15\chi< 0.15, the blue curve attains the highest value of QbgQ_{bg}, indicating that the partition into six Level-3 cliques is optimal. (b) Higher-resolution regime. For 0.15≤χ<6.50.15 \leq\chi< 6.5, the orange curve dominates, corresponding to the emergence of 36 Level-2 cliques. For χ≥6.5\chi\geq6.5, the green curve yields the maximum QbgQ_{bg}, resolving the finest-scale structure of 216 Level-1 cliques. Together, panels (a) and (b) illustrate how varying χ\chi reveals community structure from the largest to the smallest scales in the hierarchical bipartite network.

Specifically, the six Level 3 cliques are detected for χ<0.15\chi< 0.15, the 36 Level 2 cliques emerge for 0.15≤χ<6.50.15 \leq\chi< 6.5, and the 216 Level 1 cliques are resolved for χ≥6.5\chi\geq6.5. These transitions define three distinct regimes, each corresponding to a different level of the hierarchical construction. The dependence of the number of detected communities on the resolution parameter χ\chi is summarized in Figure 6, which illustrates how finer structures are progressively uncovered as χ\chi increases.

Figure 6. The number of communities detected using QbgQ_{bg} varies with different values of χ\chi. As χ\chi increases, communities are progressively uncovered from the largest to the smallest.

Due to the inherently multiscale nature of the hierarchical network, there is no single optimal choice of χ\chi. Instead, the resolution parameter should be selected based on the scale of interest and any available prior knowledge about the system. This example demonstrates the flexibility of QbgQ_{bg} in uncovering meaningful community structure across multiple hierarchical levels.

Real bipartite networks

Southern women bipartite network

We apply the bipartite modularity density metric QbgQ_{bg} to the well-known Southern Women bipartite network, which records attendance patterns of 18 women at 14 social events in a Southern U.S. town during the 1930s [23]. Figure 7 shows the bipartite representation of this network, where nodes correspond to women and social events, and edges indicate event attendance. In this network, edges represent participation of women in events. Because many women attended similar subsets of events, an effective community detection method should be able to identify groups of women with comparable attendance behavior, as well as the events that define those groups.

Bipartite representation of the Southern Women network

Figure 7. Bipartite representation of the Southern Women network. Circles represent women and squares represent social events; an edge connects a woman to an event she attended. The network encodes attendance patterns of 18 women at 14 events in a Southern U.S. town during the 1930s [23].

We examine how the detected community structure evolves as the resolution parameter χ\chi varies from −1.0-1.0 to 2.02.0, as shown in Figure 8. An animated visualization illustrating the transitions of nodes between partitions across resolutions is available at this link.

Hierarchical clustering of the Southern Women event network with increasing chi

Figure 8. Hierarchical clustering of the Southern Women event network with increasing χ\chi.

For the lowest resolution range, −1.0≤χ<−0.5-1.0 \le\chi< -0.5, the women are broadly divided into two communities. This coarse partition closely corresponds to the primary division identified in the original ethnographic study [23], which described two major social groups within the town.

As the resolution increases to −0.5≤χ<0-0.5 \le\chi< 0, the network separates into three communities. Two of these correspond to the main groups of socially active women, while the third (shown in pink) consists of women who attended relatively few events. According to the ground-truth analysis [23], these women occupy a peripheral position in the social structure: they participate infrequently, have weaker social ties, and do

not strongly affiliate with either of the main groups. The emergence of this peripheral cluster demonstrates that QbgQ_{bg} is sensitive to differences in participation intensity at intermediate resolutions.

For 0≤χ<1.00 \le\chi< 1.0, the detected partition exactly matches the canonical community structure reported by Barber [16]. This agreement provides strong validation of our method, showing that QbgQ_{bg} recovers well-established bipartite community divisions without requiring projection to a unipartite network.

As χ\chi is increased further, finer-grained structure becomes visible. At higher resolutions, the network splits into five communities, including a newly resolved cluster primarily composed of core members from the second major social group identified in the original study [23]. At χ=2.0\chi= 2.0, the algorithm identifies six smaller communities, including a new group formed by core members of the first major subgroup. These results indicate that increasing the resolution parameter reveals progressively finer subdivisions within the broader social organization.

Overall, the patterns uncovered by our method are consistent with those reported in the original ethnographic analysis [23] and subsequent studies [16]. However, prior work provided only partial and resolution-specific views of the community structure. In contrast, our approach offers a unified hierarchical perspective across the full range of χ\chi, revealing how communities emerge, split, and refine as resolution changes. To the best of our knowledge, this represents the first complete multiscale characterization of the Southern Women bipartite network.

It is important to emphasize that our method does not cluster women alone; rather, it identifies biclusters. Each detected community consists of a group of women together with the specific events that connect them. In this way, the algorithm simultaneously groups women with similar attendance patterns and the events that define those patterns. By preserving the full bipartite structure, this biclustering approach avoids the information loss inherent in unipartite projections and provides a more faithful representation of the joint social–event organization.

These results demonstrate that the proposed metric QbgQ_{bg} is highly effective for uncovering hierarchical community structure in bipartite networks and holds strong promise for applications to other real-world bipartite systems.

Asthma patient bipartite network

We apply our bipartite community detection method based on the modularity density function QbgQ_{bg} to an asthma-related bipartite network consisting of 83 patients and 18 cytokines, where edges represent significant cytokine activity levels measured in patients [24]. The original biological study identified three major patient groups: (i) a group associated with IL-4 and Eotaxin, (ii) a group enriched in IL-5, IFN-γ\gamma, IL-17, MIP-1α\alpha, MIP-1β\beta, and MIG, and (iii) a group characterized by generally low cytokine expression.

Figure 9 shows the detected community structure as the resolution parameter χ\chi varies from −2.0-2.0 to 0.30.3. An animated visualization illustrating how patients and cytokines transition between communities across resolutions is available at this link.

Hierarchical clustering of the asthma patient–cytokine bipartite network with increasing $\chi$

Figure 9. Hierarchical clustering of the asthma patient–cytokine bipartite network with increasing χ\chi.

For low resolution values, −2.0≤χ<0-2.0 \le\chi< 0, our method identifies three broad clusters, consistent with the coarse partition reported in the original study [24]. As χ\chi increases, the detected communities align more closely with biologically meaningful cytokine groupings. In particular, we observe a strong and persistent association between IL-4 and Eotaxin, reflecting a T-helper-2 (TH2TH_2) immune response in asthma, where IL-4 induces Eotaxin production and promotes eosinophil recruitment [24].

Notably, IL-2 is consistently clustered with IL-4 and Eotaxin across a wide range of χ\chi values. Although not emphasized in the original study [24], this association is supported by the underlying data: patients with elevated IL-4 and Eotaxin levels also tend to exhibit increased IL-2 expression, suggesting coordinated immune activation within this cluster.

At χ=0\chi= 0, we observe a stable cluster containing IL-5, IFN-γ\gamma, IL-17, and MIP-1β\beta, in agreement with the original analysis [24]. This cytokine group is regulated by the NF-κ\kappaB pathway, which is associated with enhanced pro-inflammatory responses and more severe asthma phenotypes. In contrast, MIG and MIP-1α\alpha, which were previously grouped with this cluster, instead form a separate community in our analysis. These cytokines merge with IL-15, TNF-α\alpha, and IL-1Ra, forming a distinct pro-inflammatory subgroup, suggesting additional heterogeneity in cytokine co-expression patterns.

As χ\chi increases further (χ≥0.15\chi\ge0.15), new structures emerge that were not explicitly reported in the original study. In particular, RANTES and IL-8 form a distinct cluster, accompanied by a subgroup of patients exhibiting elevated expression of these cytokines. At higher resolutions (χ>0.3\chi> 0.3), IP-10 separates into its own cluster, driven primarily by a single patient with exceptionally high IP-10 expression.

In general, our results provide a multiresolution view of patient–cytokine interactions that recovers the major groupings reported in [24], while also revealing additional and potentially meaningful immune signaling patterns. The persistent clustering of IL-2 with IL-4 and Eotaxin, the emergence of a RANTES–IL-8 cluster, and the isolation of IP-10 at higher resolutions highlight the ability of QbgQ_{bg} to uncover the hierarchical structure and biological heterogeneity. Importantly, the method performs true biclustering, simultaneously grouping patients with the cytokines they express most strongly, providing a more complete representation of asthma immune phenotypes.

Resolution Limit in Bipartite Clique Ring

In Ref. [15], the authors derived a criterion describing when bipartite modularity fails to resolve individual communities in a bipartite clique ring. Upon re-examination, however, we find that their derivation is incorrect. Here, we present the corrected condition determining when a bipartite kk-clique ring exhibits the resolution limit.

Starting from Eq. (2), we obtain

n(k2n+nk2−(k2+1)2(n+nk2)2)>n2(2k2+1n+nk2−4(k2+1)2(n+nk2)2)⇒2k22(n+nk2)−2k2+12(n+nk2)>−(k2+1)2(n+nk2)2⇒12<(k2+1)2(n+nk2)⇒k>n−22(10)\begin{aligned} n\left(\frac{k^2}{n+nk^2}-\frac{(k^2+1)^2}{(n+nk^2)^2}\right)>\frac{n}{2}\left(\frac{2k^2+1}{n+nk^2}-\frac{4(k^2+1)^2}{(n+nk^2)^2}\right) \\ &\Rightarrow\quad\frac{2k^2}{2(n+nk^2)}-\frac{2k^2+1}{2(n+nk^2)}>\frac{-(k^2+1)^2}{(n+nk^2)^2} \\ &\Rightarrow\quad\frac{1}{2}<\frac{(k^2+1)^2}{(n+nk^2)} \\ &\Rightarrow\quad k>\sqrt{\frac{n-2}{2}} \tag*{(10)} \end{aligned}

Thus, bipartite modularity remains resolution-limit-free only when

k>n−22.(11)k>\sqrt{\frac{n-2}{2}}. \tag*{(11)}

We illustrate this condition with two examples:

  1. For n=4n=4 and k=2k=2,

Qb(M)=0.4andQb(S)=0.55,Q_b(M)=0.4\quad\text{and}\quad Q_b(S)=0.55,

so Qb(S)>Qb(M)Q_b(S)>Q_b(M) and the network is resolution-limit-free.

  1. For n=12n=12 and k=2k=2,

Qb(M)=0.733andQb(S)=0.716,Q_b(M)=0.733\quad\text{and}\quad Q_b(S)=0.716,

giving Qb(S)<Qb(M)Q_b(S)<Q_b(M) and demonstrating the resolution limit.

Phase diagrams illustrating clique splitting behavior under modularity QbQ_b in Benchmark Network

The respective values of QbQ_b resulting from splitting or merging the two cliques in the benchmark network are

Qbsplit=Qb1+Qb2+Qb(ex)(12)Q_b^{\mathrm{split}}=Q_{b1}+Q_{b2}+Q_{b(\mathrm{ex})} \tag*{(12)}
Qbmerge=Qb(1+2)+Qb(ex)(13)Q_b^{\mathrm{merge}}=Q_{b(1+2)}+Q_{b(\mathrm{ex})} \tag*{(13)}

Here, Qb1Q_{b1} and Qb2Q_{b2} denote the modularity contributions of cliques 1 and 2 when they are treated as separate communities, whereas Qb(1+2)Q_{b(1+2)} corresponds to the merged configuration. The term Qb(ex)Q_{b(\mathrm{ex})} represents the contribution from the external component, which remains unchanged in both cases.

Thus, the modularity difference between the merged and split configurations is

ΔQb=Qbmerge−Qbsplit=Qb(1+2)−Qb1−Qb2,(14)\Delta Q_b=Q_b^{\mathrm{merge}}-Q_b^{\mathrm{split}}=Q_{b(1+2)}-Q_{b1}-Q_{b2}, \tag*{(14)}

and we obtain

ΔQb=1F[(m(1+2)−q(1+2)d(1+2)F)−(m1−q1d1F+m2−q2d2F)](15)\Delta Q_b=\frac{1}{F}\left[\left(m_{(1+2)}-\frac{q_{(1+2)}d_{(1+2)}}{F}\right)-\left(m_1-\frac{q_1d_1}{F}+m_2-\frac{q_2d_2}{F}\right)\right] \tag*{(15)}
=1F(m12−2nr1nb1nr2nb2+(nr1nb1+nr2nb2)m12+m122nr1nb1+nr2nb2+m12+ma)(16)=\frac{1}{F}\left(m_{12}-\frac{2n_{r1}n_{b1}n_{r2}n_{b2}+(n_{r1}n_{b1}+n_{r2}n_{b2})m_{12}+m_{12}^{2}}{n_{r1}n_{b1}+n_{r2}n_{b2}+m_{12}+m_a}\right) \tag*{(16)}

Equation B5 can be rewritten in terms of the nondimensional variables (d,r,t)(d,r,t) introduced in Section II C, yielding

ΔQb∼d−2+rd+d2r+d+t.(17)\Delta Q_b\sim d-\frac{2+rd+d^2}{r+d+t}. \tag*{(17)}

The phase behavior is determined by (d,r,t)(d,r,t), with 0≤d≤10\le d\le1, r≥2r\ge2, and t≥2t\ge2. The phase boundary occurs when ΔQb=0\Delta Q_b=0, giving

δQb=2t(18)\delta Q_b=\frac{2}{t} \tag*{(18)}
Phase diagrams illustrating clique splitting behavior under modularity Qb

Figure 10. Phase diagrams illustrating clique splitting behavior under modularity QbQ_b as the external influence parameter tt is varied. Each panel shows the regions in the (p,d)(p,d) space where the two cliques are either merged (M phase, orange) or split (S phase, blue), for t=0,3,10,50t=0,3,10,50.

References

References

  1. [1]M. E. J. Newman, The structure and function of complex networks, SIAM Review 45, 167 (2003), https://doi.org/10.1137/S003614450342480.
  2. [2]S. Fortunato, Community detection in graphs, Physics Reports 486, 75 (2010).DOI
  3. [3]J. Reichardt and S. Bornholdt, Statistical mechanics of community detection, Phys. Rev. E 74, 016110 (2006).DOI
  4. [4]X. Lu, B. Cross, and B. K. Szymanski, Asymptotic resolution bounds of generalized modularity and multi-scale community detection, Information Sciences 525, 54 (2020).DOI
  5. [5]M. J. Barber, M. Faria, L. Streit, O. Strogan, C. C. Bernido, and M. V. Carpio-Bernido, Searching for communities in bipartite networks, in AIP Conference Proceedings, Vol. 1021 (AIP, 2008) p. 171–182.DOI
  6. [6]M. Latapy, C. Magnien, and N. Del Vecchio, Basic notions for the analysis of large two-mode networks, Social Networks 30, 31 (2008).
  7. [7]M. E. J. Newman, The structure of scientific collaboration networks, Proceedings of the Na- tional Academy of Sciences 98, 404 (2001), https://www.pnas.org/doi/pdf/10.1073/pnas.98.2.404.
  8. [8]Y. Matsuo and H. Yamamoto, Community gravity: measuring bidirectional effects of trust and rating on online social networks, in Proceedings of the 18th International Conference on World Wide Web, WWW ’09 (Association for Computing Machinery, New York, NY, USA, 2009) p. 751–760.DOI
  9. [9]K. I. Goh, M. E. Cusick, D. Valle, B. Childs, M. Vidal, and A. L. Barabási, The human disease network, Proceedings of the National Academy of Sciences of the United States of America 104, 8685 (2007), epub 2007 May 14.pubmed.ncbi.nlm.nih.gov/17502601
  10. [10]A.-L. Barabási, N. Gulbahce, and J. Loscalzo, Network medicine: A network-based approach to human disease, Nature Reviews Genetics 12, 56 (2011).DOI
  11. [11]Z. Bu, J. Cao, H.-J. Li, G. Gao, and H. Tao, Gleam: a graph clustering framework based on potential game optimization for large-scale social networks, Knowl. Inf. Syst. 55, 741–770 (2018).DOI
  12. [12]M. Chen, K. Kuzmin, and B. K. Szymanski, Community detection via maximization of modularity and its variants, IEEE Transactions on Computational Social Systems 1, 46–65 (2014).DOI
  13. [13]M. Rezapoor Mirsaleh and M. Reza Meybodi, A michigan memetic algorithm for solving the community detection problem in complex network, Neurocomputing 214, 535 (2016).
  14. [14]J. Guo et al., Resolution limit revisited: community detection using generalized modularity density, Journal of Physics: Complexity 4, 025001 (2023).arxiv.org/abs/2012.14543
  15. [15]J. Kim, K. Feng, G. Cong, D. Zhu, W. Yu, and C. Miao, Abc: attributed bipartite co-clustering, Proc. VLDB Endow. 15, 2134–2147 (2022).DOI
  16. [16]M. J. Barber, Modularity and community detection in bipartite networks, Phys. Rev. E 76, 066102 (2007).DOI
  17. [17]M. E. J. Newman, Analysis of weighted networks, Phys. Rev. E 70, 056131 (2004).DOI
  18. [18]E. A. Leicht and M. E. J. Newman, Community structure in directed networks, Phys. Rev. Lett. 100, 118703 (2008).pubmed.ncbi.nlm.nih.gov/18517839
  19. [19]M. Chen, T. Nguyen, and B. K. Szymanski, A new metric for quality of network community structure, CoRR abs/1507.04308 (2015), 1507.04308.arxiv.org/abs/1507.04308
  20. [20]M. E. J. Newman, Networks: an introduction (Oxford University Press, Oxford; New York, 2010).DOI
  21. [21]A. Lancichinetti and S. Fortunato, Limits of modularity maximization in community detection, Phys. Rev. E 84, 066122 (2011).DOI
  22. [22]A. Arenas, A. Fernández, and S. Gómez, Analysis of the structure of complex networks at different resolution levels, New Journal of Physics 10, 053039 (2008).DOI
  23. [23]A. Davis, B. B. Gardner, and M. R. Gardner, Deep South: A Social Anthropological Study of Caste and Class (University of Chicago Press, 1941).
  24. [24]S. K. Bhavnani, G. Bellala, S. Victor, K. E. Bassler, and S. Visweswaran, The role of complementary bipartite visual analytical representations in the analysis of snps: a case study in ancestral informative markers, Journal of the American Medical Informatics Association 19, e5 (2012).DOI

Paper details

vlnc:W_2cpkgxd4
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents