Link Based Community Detection for Overlapping Networks

29 concepts20 papers1 proposal

The Node Partitioning Dilemma

Traditional graph clustering algorithms operate on a intuitive premise: they partition nodes into discrete, non-overlapping groups. This approach works well if every entity in a network possesses a single, unambiguous identity.

However, real-world networks are rarely so simple. In a social network, an individual is not defined by a single community; they simultaneously belong to a family, a professional circle, and a cohort of college friends. In biological systems, a single protein might participate in multiple distinct cellular complexes to perform different functions (Li et al.). Similarly, in cognitive science, a single brain region must dynamically switch and share its connectivity to coordinate vision, motor planning, and feedback loops (Badier et al.; Dyballa et al.).

When we force these multi-faceted nodes into a single, mutually exclusive community, we erase the network's underlying functional diversity. Early attempts to capture this complexity relied on node-centric overlapping methods, such as clique percolation, which find adjacent fully connected subgraphs (Shuigeng Zhou; Li et al.). However, allowing nodes to directly maintain fractional memberships in multiple groups introduces severe algorithmic complexity and makes it difficult to define clean, objective boundaries between clusters.

The Core Insight: Edges Have a Single Context

Link-based (or edge-centric) community detection resolves this dilemma by shifting the target of clustering from the entities (nodes) to the relationships (links) between them (Giannotti et al.).

The foundational insight of this paradigm—popularized by Bagrow et al.—is that while a node can have multiple identities, an individual interaction usually has only one. Your relationship with a coworker belongs strictly to your professional community; your relationship with your sister belongs strictly to your family community.

Traditional Node Partitioning:
[Community A: Node 1, Node 2] vs [Community B: Node 3] 
(Node 2 is forced to choose, hiding its connection to Node 3)

Link-Based Partitioning:
Link(1-2) -> Assigned to Community A
Link(2-3) -> Assigned to Community B
Result: Node 2 naturally overlaps, belonging to both Community A and B!

By treating links as the primary units of community membership, we can deploy standard, non-overlapping partitioning techniques on the edges (He et al.; Tian et al.). Once the edges are assigned to discrete, single-context clusters, the overlapping node communities emerge naturally as a byproduct: a node automatically belongs to every community inherited from its incident edges (Baquero et al.; Liu et al.).

Mechanics of Edge Partitioning

To cluster links effectively, algorithms must evaluate the similarity of relationships rather than the similarity of isolated nodes. This is frequently achieved through a mathematical transformation known as a line graph (or dual graph).

In a line graph, the edges of the original network are converted into nodes, and edges are drawn between these new "edge-nodes" if their corresponding original links share a common vertex (Tian et al.). Once this transformation is complete, researchers can apply a variety of optimization frameworks to partition the space:

  • Partition Density Optimization: Rather than relying on traditional node-based modularity, the authors in Li et al. maximize a "partition density" metric. This approach evaluates the quality of link clusters without requiring any prior knowledge of the total number of communities.
  • Probabilistic Generative Models: Instead of hard assignments, frameworks like vGraph (Sun et al.) model community membership at the edge level via a variational distribution conditioned on both endpoints of an interaction. This allows the local context of a specific neighbor to dictate which community is active during that interaction. Similarly, stochastic models use expectation-maximization and matrix factorization to determine how individual links are generated by underlying community profiles (Baquero et al.; He et al.).
  • Geometric Ricci Flows: Advanced structural approaches, such as those proposed by Tian et al., compute discrete Ricci curvature on the line graph. By running a "Ricci flow," the algorithm systematically thins out and eliminates "bridge" edges that connect different functional contexts, cleanly isolating the underlying edge communities.

Reconciling Overlap and Hierarchy

Beyond uncovering mixed memberships, link-centric clustering solves a long-standing structural paradox in network science: the mathematical conflict between pervasive overlap and hierarchical organization.

In traditional node-centric hierarchies (like a standard corporate organizational chart), a node must belong to a single branch to maintain a clean tree structure. If a node belongs to multiple branches, the nested hierarchy collapses into an uninterpretable tangle.

Node Hierarchy (Broken by Overlap):
       Root
      /    \
  Dept A   Dept B
      \    /
      Node X  <-- Destroys the clean tree structure

Edge Hierarchy (Preserved):
       Root
      /    \
  Dept A   Dept B
    |        |
  Link 1   Link 2
    \        /
      Node X  <-- Node X safely inherits both contexts

As demonstrated by Bagrow et al., grouping edges completely bypasses this limitation. Because individual interactions are highly specific, edge communities can be organized into a strict, beautifully nested tree hierarchy. Meanwhile, because individual nodes possess multiple distinct edges, they can participate in entirely different branches of that hierarchy at various scales, capturing both local and global roles simultaneously.

Extension to Higher-Order and Multilayer Structures

The utility of edge-centric modeling becomes even more pronounced when moving beyond simple, static graphs.

In heterogeneous information networks (HINs), where nodes and edges carry different semantic types, treating links as first-class citizens allows algorithms to dynamically weight specific "meta paths," leading to highly granular node categorization (Liu et al.). For multilayer networks—where interactions span across different social platforms or physical layers—measuring link similarities both within and across layers allows researchers to track how overlapping communities persist or shift across contexts (Liu et al.).

Finally, because real-world interactions often occur in groups rather than pairs, the concept has been extended to higher-order structures like simplicial complexes and hypergraphs. For example, Wu et al. utilize random walks derived from the Hodge 1-Laplacian to perform link partitioning on simplicial complexes, while Chodrow et al. utilize generative hypergraph stochastic blockmodels where affinity functions dictate how community labels within a set of nodes drive the formation of multi-node hyperedges. By focusing on the connection rather than the entity, these models preserve the multi-faceted reality of complex systems.

Key Foundational Work

Link communities reveal multiscale complexity in networks (2010) — contributed 2 concept elements to this direction.
Searching for functional gene modules with interaction component models (2010) — contributed 1 concept elements to this direction.
Computational approaches for detecting protein complexes from protein interaction networks: a survey (2010) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 20 papers
  2. Version 1 · 2026-10-04 · 46 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_overlapping_community_detection_link_bas_8f1baddf,
  title = {overlapping community detection (link-based community detection)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/overlapping-community-detection-link-based-community-detection/rdr_8f1baddfa26b45da8cbf08f227eead08},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_overlapping_community_detection_link_bas_8f1baddf_v2,
  title = {overlapping community detection (link-based community detection)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/overlapping-community-detection-link-based-community-detection/rdr_8f1baddfa26b45da8cbf08f227eead08/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake