Ahn et al., "Link communities reveal multiscale complexity in networks" (2010)

Yong-Yeol Ahn, James P. Bagrow, and Sune Lehmann, Nature 466(7307), 761–764 (2010)
DOI | arXiv | PDF | Code and visualization | Slides

@article{ahn2010link,
    author = {Yong-Yeol Ahn and James P. Bagrow and Sune Lehmann},
    title = {Link communities reveal multiscale complexity in networks},
    journal = {Nature},
    volume = {466},
    number = {7307},
    pages = {761--764},
    doi = {10.1038/nature09182},
    archivePrefix = {arXiv},
    eprint = {0903.3178},
    year = {2010},
}

Link community, Community detection, Overlapping community structure, Hierarchical link clustering

Most Community detection methods assign each node to a single community, yet real networks are full of nodes that naturally belong to multiple groups. This paper reframes the problem by clustering links rather than nodes: because each link typically has a single identity (connecting two people through one context), partitioning links into communities automatically yields overlapping node communities. The method uses a similarity measure based on the Jaccard coefficient of neighbor sets, feeds it into Hierarchical clustering, and cuts the resulting Dendrogram at the threshold that maximizes a Link community-adapted partition density. The hierarchy itself encodes the multiscale organization of the network.

The Edge centric perspective introduced here contrasts with node-centric overlapping methods such as Clique percolation and the Affiliation graph model. Evans and Lambiotte independently explored a related Line graph approach. The Hierarchical link clustering page in the wiki details the algorithm’s time complexity. Follow-up work extended the idea to Hypergraphs (Lotito2023hyperlink) and connections to higher-order flows (Rosvall2014memory). The Choobdar2019assessment DREAM challenge later benchmarked link communities against other methods for identifying functional modules in biological networks.