PaperlayerView exact revision on arXiv

Source-linked AI summary

Link communities reveal multiscale complexity in networks

Yong-Yeol Ahn, James P. Bagrow, Sune Lehmann

arXiv:0903.3178v3physics.soc-phphysics.data-anq-bio.QM

TL;DR

Overlapping communities can have more external than internal connections, challenging node-based descriptions of network structure. The paper clusters links to expose hierarchical and overlapping relations, and reports that its approach reveals more network metadata than tested methods.

  • Problem

    Overlapping communities can have many more external than internal connections, complicating node-based descriptions of network communities.

  • Method

    The paper clusters links rather than nodes, placing each link in a single context to reveal hierarchical and overlapping relations.

  • Results

    The approach reveals more network metadata than tested methods and leads overall across every network evaluated.

  • Takeaways & Limitations

    Link communities indicate that overlap and hierarchical organization can be understood as two aspects of the same network phenomenon.

  • Takeaways & Limitations

    Selecting a single best community level remains partly driven by less-developed hierarchy-analysis tools and the greater difficulty of handling full hierarchical structure.

Abstract

from arXiv · show

Networks have become a key approach to understanding systems of interacting objects, unifying the study of diverse phenomena including biological organisms and human society. One crucial step when studying the structure and dynamics of networks is to identify communities: groups of related nodes that correspond to functional subunits such as protein complexes or social spheres. Communities in networks often overlap such that nodes simultaneously belong to several groups. Meanwhile, many networks are known to possess hierarchical organization, where communities are recursively grouped into a hierarchical structure. However, the fact that many real networks have communities with pervasive overlap, where each and every node belongs to more than one group, has the consequence that a global hierarchy of nodes cannot capture the relationships between overlapping groups. Here we reinvent communities as groups of links rather than nodes and show that this unorthodox approach successfully reconciles the antagonistic organizing principles of overlapping communities and hierarchy. In contrast to the existing literature, which has entirely focused on grouping nodes, link communities naturally incorporate overlap while revealing hierarchical organization. We find relevant link communities in many networks, including major biological networks such as protein-protein interaction and metabolic networks, and show that a large social network contains hierarchically organized community structures spanning inner-city to regional scales while maintaining pervasive overlap. Our results imply that link communities are fundamental building blocks that reveal overlap and hierarchical organization in networks to be two aspects of the same phenomenon.

revealing hierarchical organization. We find relevant link communities in many networks,

Link communities reconcile pervasive overlap with hierarchical organization by assigning links to single contexts while allowing nodes to inherit multiple memberships. Across diverse real-world networks, the approach outperformed tested node-based methods and revealed meaningful multiscale structure.

  • Social-network hierarchy: The mobile-phone social network contained hierarchical communities spanning inner-city to regional scales while maintaining pervasive overlap.Across dendrogram levels, smaller intra-city and larger spatially correlated communities remained meaningful, providing evidence of spatial hierarchical organization.
  • Motivation and objective: Pervasive overlap can leave communities with more external than internal connections, breaking node-based assumptions and motivating communities defined as closely interrelated links.A partition-density objective selects relevant dendrogram levels without modularity’s resolution limit and formulates overlap discovery without penalizing nodes’ multiple memberships.
  • Link-community method: Hierarchical clustering of similar links produces a dendrogram whose cuts yield communities at multiple levels, while nodes inherit all memberships of their links.This allows links unique positions and nodes multiple overlapping positions, reconciling hierarchy and overlap without penalizing multiple memberships.
  • Illustrative example: In the word-association example, ‘clever, wit’ nested within ‘smart/intellect’, while ‘Newton’ and ‘Gravity’ belonged simultaneously to ‘smart/intellect’, ‘weight’ and ‘apple’.The example illustrates that link communities capture multiple relationships between nodes.
  • Quantitative evaluation: The link-based approach was the overall leader in every network and won most individual composite-performance aspects, particularly community-quality measures.Its performance stood out in dense metabolic and word-association networks expected to have pervasive overlap.

Methods

The method groups links by similarity among adjacent edge pairs, hierarchically clusters them into link communities, and selects partitions using partition density. Community quality is evaluated through metadata enrichment, overlap measures, and coverage, with a controlled randomization testing hierarchical validity beyond a threshold.

  • Link similarity: Adjacent links sharing a node are assigned a similarity score that excludes their shared node to avoid redundant information and bias.The method focuses on connected edge pairs because they are expected to be more similar than disconnected pairs.
  • Hierarchical clustering: Single-linkage hierarchical clustering builds a link dendrogram, whose cut at a chosen threshold yields link communities.One example is the threshold maximizing partition density.
  • Partition density: Partition density averages each community’s link density weighted by its fraction of present links and has no resolution limit because its terms are local.Community density is normalized between the minimum and maximum possible links among the induced nodes, assuming they remain connected; D_c = 0 when n_c = 2.
  • Evaluation metrics: Community quality uses metadata enrichment, overlap quality via mutual information, community coverage, and overlap coverage based on average nontrivial memberships per node.Nontrivial communities contain at least 3 nodes, and enrichment compares within-community similarity with a global baseline.
  • Hierarchical validity control: A threshold-control randomization preserves edge-pair merging rates, similarity distributions, and the high-quality community structure while randomizing dendrogram merging order.Similarities are clustered normally, but pairs with S ≥ t* are merged in randomized descending order before fixing the structure at t*.

Supplementary Information

The supplementary information identifies the paper “Link Communities Reveal Multi-Scale Complexity in Networks” and its authors: Yong-Yeol Ahn, James P. Bagrow, and Sune Lehmann.

  • The paper is authored by Yong-Yeol Ahn, James P. Bagrow, and Sune Lehmann.

S1 Introduction

The document outlines implementation details and link-partition properties before presenting a validation methodology applied to a diverse, representative corpus of networks.

  • Document organization: Section S2 details link clustering implementation and the other community-detection methods used in the main text.
  • Document organization: Section S3 examines overlapping and non-overlapping link partitions, showing that the link-clustering algorithm can analyze both cases.
  • Community validation: The final sections validate community methods using evaluation measures and a diverse, representative sample of common network datasets.Section S5 introduces the measures used to evaluate different community algorithms; the networks were selected for diversity and representativeness.

S2 Methods

The methods define similarity between connected links using neighboring-node information, cluster links hierarchically, and partition the resulting dendrogram with partition density. They also establish node-clustering controls and compare link clustering with representative overlapping, non-overlapping, and modularity-based algorithms.

  • Link similarity: Connected links are compared with a Jaccard-style similarity based on the inclusive neighbors of their non-keystone endpoints, avoiding hub-degree bias.Disjoint links are excluded for efficiency, while the shared keystone node’s neighbors are omitted because they provide no useful information and can dominate similarity.
  • Hierarchical clustering: Single-linkage hierarchical clustering repeatedly merges the most similar link groups, providing an efficient procedure for detecting hierarchical communities in large networks.Complete-linkage and average-linkage clustering are also possible, but single-linkage is used mainly for simplicity and efficiency.
  • Dendrogram partitioning: Partition density identifies where to cut the link dendrogram by measuring whether each link community is clique-like or tree-like, with disconnected communities contributing negatively.Partition density ranges up to 1 for fully connected cliques and equals 0 when every community is a tree.
  • Control algorithm: A node-clustering control mirrors link clustering with alternative node similarities and the same single-linkage procedure, but cuts its dendrogram at maximum modularity.The selected node-similarity variant finds more relevant communities across most studied networks and most closely resembles link similarity.
  • Evaluation methods: Performance is compared with clique percolation [11], Infomap [12], and greedy modularity optimization [13], while modularity values are also obtained using Clauset et al.’s fast/greedy method [14].The comparisons represent overlapping, non-overlapping, and modularity-based community detection approaches, respectively.

S3 Properties of link communities

Link communities reconcile single-community link assignments with overlapping node memberships and reveal hierarchical structure that differs from node-based hierarchies. Their detected structures are meaningful, robust to weighting and filtering, and show stronger overlap in denser networks.

  • Overlapping links: Nodes can belong to multiple communities together even when each link is assigned to only one community, allowing link communities to represent overlapping relationships.This resolves the apparent limitation that links may occur in multiple contexts while preserving the link-based clustering framework.
  • Overlapping links: Link clustering can detect nested or cross-cutting social groups when they have distinguishing connectivity patterns, but completely subsumed groups without structural differences are undetectable by any method.Weighting interactions by time spent together or introducing slightly different connection probabilities can make otherwise hidden groups detectable.
  • Hierarchical organization: A link dendrogram can reveal structurally related cross-community links and produce a hierarchy different from the expected node hierarchy, even in a network with no overlap.In the illustrative graph, six link communities are found instead of four because the cross-community links form two structurally related groups.
  • Overlap statistics: Denser networks produce more highly overlapping link communities and higher average overlapping memberships than sparser networks.Figure S6 compares overlap size and membership number in sparse Amazon.com and actor networks with dense word-association and metabolic networks.
  • Partition-density validation: Maxima in partition density coincide with s2/s1 approaching 1/2, indicating that the selected link-community partitions are well structured.This relationship was observed for the metabolic and mobile-phone networks across dendrogram cut thresholds.
  • Empirical relevance and robustness: Link communities remain the overall leader after filtering the weighted word-association network, while more than 80% of communities contain an enriched GO term with p-value below 0.0001.More than 30% of communities have at least one enriched GO term with p-value below 10^-10, and biological examples correspond to known protein complexes.

S4 Generalizations and extensions of link communities

Link-community methods generalize to weighted, directed, signed, and multipartite networks by adapting similarity and partition density. Their local similarity also supports local clustering, while disjoint link partitions permit direct optimization with traditional techniques.

  • Weighted, directed, and signed networks: Link similarity extends to weighted, directed, or signed links by replacing the Jaccard index with the Tanimoto coefficient.The extension applies to networks without self-loops.
  • Multipartite networks: Multipartite link clustering accounts for forbidden same-type connections in similarity calculations and modifies partition density for sparser fully connected K-partite cliques.Similarity uses ordinary neighbor sets, while the full K-partite partition density sums contributions across communities and node types.
  • Local clustering: Local link clustering follows the highest-similarity adjacent links from a starting edge, updating similarities as the community grows until a stopping criterion is met.Because link similarity uses only local information, the procedure can agglomerate communities without globally clustering the entire network.
  • Direct optimization: Direct optimization can identify link communities because disjoint link partitions support traditional methods such as simulated annealing.The procedure begins with a random assignment of links to communities and optimizes partition density.

S5 Testing community methods

The section develops a metadata-based evaluation framework for community methods without requiring hidden ground-truth communities. It combines community and overlap quality with community and overlap coverage in a composite comparison.

  • S5 Testing community methods: Because real-network communities lack known ground truth, the evaluation uses descriptive metadata rather than assuming benchmark-generated communities are valid.Model-graph benchmarks may not extrapolate to real networks and can favor algorithms matching their creators’ community conceptions, especially when overlap and triangles are important.
  • S5 Testing community methods: The comparison balances four aspects: metadata-based community quality, metadata-based overlap quality, community coverage, and overlap coverage.The composite measure addresses tradeoffs between finding high-quality communities for limited network coverage and finding medium-quality communities covering most nodes, with or without overlap.
  • S5 Testing community methods: Community enrichment measures average metadata similarity among node pairs sharing a community relative to the network-wide baseline, with larger values indicating tighter communities.Metadata examples include product subjects, actor plot keywords, and protein GO terms; similarity definitions vary by network.
  • S5 Testing community methods: Overlap quality uses mutual information between each node’s assigned membership count and metadata indicating its expected number of communities or contexts.The measure does not require detected relationships to be linear or follow a prespecified functional form.
  • S5 Testing community methods: Coverage counts nodes in nontrivial communities and average memberships in such communities, while excluding trivial communities and singleton nodes from quality calculations.Community coverage requires membership in a community of at least three nodes; overlap coverage captures additional information from densely overlapping communities.

S6 Network datasets · S6.1 Overview · S6.2 Biological networks

The study evaluates eleven diverse networks, including yeast protein-interaction, E. coli metabolic, and mobile-phone social networks, using metadata to assess community and overlap quality. Its biological-network analyses use curated PPI datasets and a reconstructed metabolite network with domain-specific annotations and quality measures.

  • S6.1 Overview: Eleven networks, including the union of three, provide a diverse test set spanning protein interactions, metabolism, telecommunications, and other representative topologies.Table S2 summarizes the networks, their metadata, collection methods, and composite-performance calculations.
  • S6.2.1 Protein-protein interaction: The yeast PPI analysis uses three genome-scale datasets—Y2H, AP/MS, and literature-curated (LC)—plus their union, retaining only each network’s largest component.These datasets were compiled in a recently published resource 42.
  • S6.2.1 Protein-protein interaction: Gene Ontology terms serve as PPI metadata because they provide extensive, structured annotations of protein functions and locations.The annotations come from the Gene Ontology project 54.
  • S6.2.1 Protein-protein interaction: PPI community quality measures enrichment of functionally similar protein pairs, defining similarity as one when p < 10^-3 and zero otherwise.Similarity uses GO biological-process terms and the total-ancestry measure 55.
  • S6.2.1 Protein-protein interaction: PPI overlap quality is the mutual information between proteins’ GO-term counts and their discovered membership counts.The number of GO terms proxies how many functional contexts a protein occupies.
  • S6.2.2 Metabolic: The metabolic analysis uses the E. coli K-12 MG1655 iAF1260 reconstruction, retaining cellular reactions and projecting it into metabolite space.Compartments are ignored; metabolites connect when they share a reaction, producing cliques for multi-metabolite reactions.
  • S6.2.2 Metabolic: KEGG pathway annotations 56 define metabolic metadata, while community quality uses pathway-set Jaccard similarity and overlap quality uses mutual information with membership counts.Pathway counts represent the number of metabolic contexts in which metabolites participate.

S6.3 Social networks

The social-network analysis constructs a large phone-call network from reciprocal calls in a spatially constrained region, then evaluates communities using geographic similarity and call frequency as overlap metadata. Comparable community and overlap measures are defined for actor collaborations and congressional collaborations using domain-specific similarity and participation proxies.

  • Phone-call social network: The phone-call network contains approximately 2.8 million links among users in a 350 km by 80 km region, connecting pairs who called each other during 30 weeks.Users are assigned the location of their most frequently used tower; the source dataset covers approximately 8 million users and includes calls, locations, age, and gender for some users.
  • Phone-call social network: Community quality is measured from geographic proximity, while overlap quality uses users’ total phone calls as a proxy for broader social roles.Node similarity is based on Euclidean distance between users’ most likely locations, and frequent phone users are assumed to participate in broader social networks.
  • Film-actor collaborations: The actor network links performers who co-starred in at least two films, retaining only the largest connected component after projecting the movie–actor bipartite network.Community similarity uses Jaccard overlap between actors’ movie-plot keywords, while overlap quality relates community memberships to career seniority.
  • Congressional collaborations: The congressional network filters bill co-sponsorships to retain tight working relationships, measuring community quality with ideological distance and overlap with representatives’ elected terms.The common-space coordinates capture political and ideological similarity, and mutual information quantifies the relationship between community memberships and seniority.

S6.4 Other networks

The study applies link-community analysis to philosopher, word-association, and Amazon co-purchase networks, evaluating community quality and overlap against semantic, categorical, and commercial metadata.

  • Philosopher network: The philosopher network uses Wikipedia hyperlinks between philosophers, with Jaccard similarity of shared linked pages measuring community quality.Philosophers’ category memberships provide overlap metadata, quantified through mutual information with community memberships.
  • Amazon co-purchase network: The Amazon network is a depth-12 BFS snowball of products linked by top-five co-purchases, starting from The Help and removing unexplored products at the final layer.User-applied tags measure community quality, while product subjects provide overlap metadata through mutual information with community counts.
  • Amazon co-purchase network: Reversing Amazon’s metadata roles does not qualitatively change composite performance, indicating that the test procedure is not dependent on a particular metadata choice.Using subjects for community quality and tag counts for overlap quality produces qualitatively similar results.

S7 Validating hierarchical organization

Link dendrograms reconcile pervasive overlap with hierarchical organization, revealing meaningful community structure across multiple network scales. Structural changes, persistent overlap, and metadata-based quality analyses validate that these levels are not artifacts of a single optimal cut.

  • Qualitative validation: Bottom-up link tracking and top-down subdivision qualitatively reveal meaningful communities at multiple levels in the word association network.These complementary views are illustrated in Fig. S23.
  • Structural validation: Community structure changes significantly when the dendrogram is cut at different thresholds, demonstrating that the hierarchy is dynamic rather than a single frozen partition.This structural test addresses whether one optimal cut determines the entire organization.
  • Structural validation: Many networks retain broad community-size and membership distributions at three dendrogram levels, showing that multiple size scales and significant overlap persist without collapse.The distributions vary smoothly across levels rather than suddenly disappearing.
  • Quantitative validation: Across the network corpus, actual community quality decays more slowly than randomized-control quality below the optimal threshold, indicating meaningful structure at multiple scales.This comparison is shown in Fig. S29.

A Tables of measures

This section lists raw, unnormalized values for four calculated measures across the networks and algorithms shown in main-text Fig. 2 and Fig. S19. For clique percolation, k is selected by the best overall composite score unless literature precedent applies, with coverage and quality weighted equally.

  • The tables report raw, unnormalized values for four calculated measures across the networks and algorithms presented in Fig. 2 and Fig. S19.
  • Clique percolation uses the k value yielding the best overall composite score, unless an established literature precedent determines the choice.
  • The composite score weights coverage and quality equally, although experimenters may prioritize either criterion instead.

A.1 Overall methods

The supplied passage contains only the fragment “#8### congress #############” and provides no substantive information about the paper’s overall methods.

  • A.1 Overall methods: The passage provides no identifiable description of the study’s methods or procedures.Its entire content is the fragment “#8### congress #############”.

A.2 Clique Percolation

Clique percolation selects k by maximizing a normalized composite score balancing community quality and coverage, except where prior work specifies a value. Across the listed datasets, cp3 wins for all protein-protein interaction and actor networks, while cp4 wins for the phone network.

  • Selection procedure: Higher k values tend to identify higher-quality communities but reduce coverage, so researchers may deliberately trade coverage for quality depending on the application.Choosing k by the composite score imposes equal weighting on coverage and quality.
  • Dataset-specific choices: cp3 is the overall winner for PPI (Y2H), PPI (LC), PPI (All), and actor networks.The listed comparisons evaluate cp3, cp4, and cp5 using community and overlap quality and coverage metrics.
Loading 0903.3178v3…