PaperlayerView exact revision on arXiv

Source-linked AI summary

Bi-clique Communities

Sune Lehmann, Martin Schwartz, Lars Kai Hansen

arXiv:0710.4867v2physics.data-anphysics.soc-ph

TL;DR

One-mode projections of bipartite networks lose structural information about how complementary nodes are shared. The paper extends k-clique detection to overlapping biclique communities, retaining bipartite information and adding independent thresholds for the two node sets. The method is computationally manageable for many sparse networks and preserves overlapping-community analysis.

  • Problem

    One-mode projections can discard essential bipartite structure, including higher-order information about which complementary nodes are shared.

  • Method

    The paper defines biclique communities as connected unions of overlapping Ka,b bicliques, extending the k-clique community framework to bipartite networks.

  • Results

    The biclique method retains overlapping-community analysis, avoids structural information loss during projection, and supports independent thresholds for the two node sets.

  • Takeaways & Limitations

    Direct biclique analysis provides a flexible alternative to k-clique detection when bipartite information is available, including for subtle structures and sparse regions.

Abstract

from arXiv · show

We present a novel method for detecting communities in bipartite networks. Based on an extension of the $k$-clique community detection algorithm, we demonstrate how modular structure in bipartite networks presents itself as overlapping bicliques. If bipartite information is available, the bi-clique community detection algorithm retains all of the advantages of the $k$-clique algorithm, but avoids discarding important structural information when performing a one-mode projection of the network. Further, the bi-clique community detection algorithm provides a new level of flexibility by incorporating independent clique thresholds for each of the non-overlapping node sets in the bipartite network.

I. INTRODUCTION

Community detection methods divide into global optimization approaches and local structural approaches. For bipartite networks, prior efforts had focused on global methods, motivating a local algorithm designed to retain power, flexibility, and accuracy.

  • Community structure describes densely linked groups with many intra-community links and sparse connections between modules.
  • Community detection methods comprise global optimization approaches and local methods based on local structural information.Global methods are typically stochastic, whereas local methods are usually deterministic.
  • Bipartite-network community detection had focused on global methods before this work introduced a local-framework algorithm.The authors describe the proposed algorithm as having considerable power, flexibility, and accuracy.

II. BIPARTITE NETWORKS

Bipartite networks connect two non-overlapping node sets, but one-mode projections can erase how complementary nodes are shared. Three distinct bipartite structures can therefore collapse into the same projected 4-clique, motivating direct analysis of the original network.

  • Bipartite networks contain two non-overlapping node sets, with every link joining one node from each set.Their adjacency matrix is typically sparse, and the two one-mode projections are formed from EET and ETE.
  • Because projected analyses discard important bipartite linkage information, the authors advocate analyzing the bipartite network directly.
  • Projection typically eradicates sparsity, encodes information in weights, and often removes further information through thresholding and zeroing diagonals.These costs are especially problematic when one node set is much larger than the other or when projected matrices are densely populated.
  • One-mode projections preserve pairwise sharing counts but lose which complementary nodes are shared across larger groups.The projection cannot reconstruct the original bipartite adjacency matrix E from the two projected matrices.
  • Three distinct bipartite networks become indistinguishable 4-cliques after projection onto the ∆ nodes.The examples include four ∆ nodes sharing one Γ node, six distinct pairwise Γ links, and a mixed structure.

III. BICLIQUE COMMUNITIES

Biclique communities generalize clique communities to bipartite networks by grouping overlapping complete sub-bigraphs under independently chosen node-set thresholds. The method preserves bipartite context by linking the two node sets directly.

  • Biclique definition: A K_a,b clique is a complete bipartite subgraph with a nodes from Δ and b nodes from Γ, and communities join such cliques through chains of adjacent cliques.Adjacency requires overlap of at least a K_a−1,b−1 biclique, equivalently a−1 upper and b−1 lower vertices.
  • Biclique definition: The approach is motivated by communities composed of several complete sub-bigraphs whose nodes overlap substantially.
  • Contextual communities: Biclique communities retain the two-set context that one-mode community analyses lose, such as actors paired with the films they share.The same contextual pairing can clarify functional groupings in metabolic networks by linking metabolites to reactions.
  • Contextual communities: The biclique formulation is related to co-clustering while maintaining explicit links between communities in the two node sets.

IV. RELATION TO k-CLIQUE COMMUNITIES

Biclique communities extend k-clique communities to bipartite data while avoiding information loss from one-mode projections. They preserve overlap, expose complementary-node context, and tune density thresholds independently across the two node sets.

  • Projection relationship: Biclique communities provide complementary-node information that may not form a connected component in the other one-mode projection.For K2,1 communities, the projected Δ structure is a connected component while the associated Γ nodes need not be connected there.
  • Projection relationship: A K_a,b community corresponds to an a-clique community in the Δ projection and a b-clique community in the Γ projection, with cross-set connectivity constraints.
  • Relation to k-clique communities: Biclique communities detect structures between 2-clique and 3-clique communities that the k-clique method can miss, including sparse regions where few nodes participate in 3-cliques.This matters especially in heavy-tailed networks, where many nodes have degree below two or do not belong to cliques of size three or greater.
  • Projection relationship: For K2,2, biclique communities reduce to connected components in both projections while requiring the two components to be correlated across the bipartite network.The authors state that thresholding one-mode projections further enhances this advantage.
  • Overlapping communities: The method preserves overlapping communities in both node sets, allowing users to observe communities linked by shared nodes.
  • Resolution control: Independent values of a and b let users probe different density patterns, such as actor ensembles versus films sharing a small group of actors.

V. DETECTING BICLIQUE COMMUNITIES

The detection procedure enumerates maximal bicliques, thresholds their overlaps separately for the two node sets, combines those constraints, and extracts connected components as communities. Figure 4 examines how the number of maximal bicliques scales in two real networks.

  • Enumerate maximal bicliques: It begins by enumerating maximal bicliques and constructing separate Δ- and Γ-overlap matrices from their node overlaps.The procedure uses the LCM version 4.0 closed-itemset miner to obtain maximal bicliques.
  • Threshold overlap matrices: The overlap matrices are thresholded using the independent clique thresholds a and b, including diagonal eligibility and filtered off-diagonal overlaps.
  • Threshold overlap matrices: The final matrix retains overlap only when it is present in both individual matrices, encoding adjacency in the K_a−1,b−1 sense.The combination uses a logical AND operation.
  • Find connected components: The algorithm finds connected components of a final overlap matrix, with each component representing one biclique community.Node indices are then extracted from the maximal bicliques belonging to each component.
  • Empirical scaling: Figure 4 reports how the number of maximal bicliques scales with edge count in IMDb and cond-mat networks, comparing real and randomized data.The caption states that IMDb shows significant real-versus-randomized differences, whereas cond-mat changes little.

VI. NETWORK OF COMMUNITIES

The network of communities represents biclique overlaps explicitly, while varying K_a,b thresholds changes which author–paper structures are emphasized. These choices distinguish author-heavy, paper-heavy, and balanced communities and reveal different collaboration patterns.

  • VI. NETWORK OF COMMUNITIES: Communities are represented as nodes linked when they share authors or papers, with link weights encoding overlap and node size encoding community membership.
  • VI. NETWORK OF COMMUNITIES: As thresholds increase from K1,1, one large community separates into smaller pieces whose connectivity reflects modularity or homogeneity.Highly modular networks yield sparse community networks with many isolated nodes, whereas homogeneous networks yield dense interconnection.
  • VI. NETWORK OF COMMUNITIES: Varying K_a,b thresholds probes different aspects of the bipartite network, from author-heavy to paper-heavy and balanced communities.K8,2 emphasizes shared authors, K2,12 emphasizes shared papers, and K3,5 produces more balanced communities.
  • VI. NETWORK OF COMMUNITIES: For K3,5, author-to-paper ratios mirror the global network, communities are similarly sized, and author- and paper-overlap are distributed more evenly.
  • VI. NETWORK OF COMMUNITIES: Small a and large b identify longtime collaborators with few authors and many papers, whereas large a and small b identify large collaborations with many authors and few papers.In the cond-mat network, longstanding theoretical collaborations typically involve 2–4 authors and 20–60 papers, while the largest community has 12 authors and 290 papers.

VII. ALGORITHMIC COMPLEXITY

The biclique algorithm is tractable on many sparse real-world networks despite maximal biclique enumeration being NP complete. Its main bottleneck is overlap-matrix construction and thresholding.

  • VII. ALGORITHMIC COMPLEXITY: The biclique method remains computationally manageable for sparse networks when the number of bicliques grows linearly with input links.The maximal-biclique enumeration step has complexity proportional to the number of maximal bicliques and linear memory usage in the cited algorithm.
  • VII. ALGORITHMIC COMPLEXITY: The number of maximal bicliques can grow exponentially with input size, making enumeration NP complete in the worst case.
  • VII. ALGORITHMIC COMPLEXITY: In IMDb and cond-mat, the number of maximal bicliques N scales linearly with the number of edges M.
  • VII. ALGORITHMIC COMPLEXITY: Overlap-matrix construction and thresholding scale as O(N^2) ∝ O(M^2), forming the algorithmic bottleneck.Finding connected components is linear in the sparse overlap representation, while cond-mat processing took a little over 30 minutes on the reported hardware.

VIII. DISCUSSION

The paper presents biclique communities as an overlapping extension of k-clique detection that preserves bipartite structure and allows independent thresholds. A cond-mat example shows how overlap and author–paper context distinguish related scientific communities.

  • VIII. DISCUSSION: The biclique method avoids information loss from one-mode projection while retaining overlapping communities and enabling independent thresholds for the two node sets.
  • VIII. DISCUSSION: The method is computationally manageable for many sparse networks and has O(M^2) complexity when biclique counts scale linearly with edges.
  • VIII. DISCUSSION: Two K3,5 communities share H. E. Stanley and L. A. N. Amaral but concern econophysics and biophysics, respectively.The example contains communities of 4 authors and 11 papers, and 5 authors and 13 papers.
  • VIII. DISCUSSION: The authors expect biclique community detection to be practically useful for bipartite biological, affiliation, and information networks.

APPENDIX A: TABLES

The appendix tables document the two K3,5 communities illustrated in Figure 6. They provide the underlying community memberships for the econophysics and biophysics examples.

  • APPENDIX A: TABLES: The two tabulated communities correspond to distinct K3,5 groups in the cond-mat author–paper network, with overlapping authors providing context for their relationship.
  • APPENDIX A: TABLES: Table I lists the community displayed in Figure 6’s top panel.
  • APPENDIX A: TABLES: Table II lists the community displayed in Figure 6’s bottom panel.
Loading 0710.4867v2…