Link Clustering with Extended Link Similarity and EQ Evaluation Division

Lan Huang, Guishen Wang, Yan Wang, Enrico Blanzieri, Chao SuPLoS 2013 · DOI

Abstract

Link Clustering (LC) is a relatively new method for detecting overlapping communities in networks. The basic principle of LC is to derive a transform matrix whose elements are composed of the link similarity of neighbor links based on the Jaccard distance calculation; then it applies hierarchical clustering to the transform matrix and uses a measure of partition density on the resulting dendrogram to determine the cut level for best community detection. However, the original link clustering method does not consider the link similarity of non-neighbor links, and the partition density tends to divide the communities into many small communities. In this paper, an Extended Link Clustering method (ELC) for overlapping community detection is proposed. The improved method employs a new link similarity, Extended Link Similarity (ELS), to produce a denser transform matrix, and uses the maximum value of EQ (an extended measure of quality of modularity) as a means to optimally cut the dendrogram for better partitioning of the original network space. Experimentation on five real-world networks and artificially-generated networks shows that the ELC method achieves higher EQ and In-group Proportion (IGP) values.

Introduction: The Challenge of Overlapping Communities

In real-world networks, nodes rarely belong to a single group. Proteins participate in multiple biological pathways, and individuals belong to various social circles. Detecting these overlapping communities is a major challenge in network science.

A popular approach is Link Clustering (LC), which clusters the links between nodes rather than the nodes themselves. However, the original LC method has two major flaws:

  1. Short-sightedness: It only calculates similarity between links that share a common node, ignoring "non-neighbor" links that might still be part of the same functional group.
  2. Over-segmentation: It uses a metric called "partition density" to decide where to cut its clustering tree, which often results in the network being shattered into too many tiny, fragmented communities.

The authors introduce two primary innovations to create the ELC framework: Extended Link Similarity (ELS) and EQ Evaluation Division.

Unlike the standard Jaccard-based similarity that only looks at immediate neighbors, ELS considers the relationship between all four nodes involved in a pair of links. This allows the algorithm to recognize similarity between links that are "near" each other but don't necessarily share a vertex, resulting in a much richer "transform matrix" for clustering.

Illustration of link relationships (A-D) used to define Extended Link Similarity (ELS).

EQ Evaluation Division

Instead of relying on partition density, ELC uses EQ (Extended Modularity) to determine the optimal cut level in the hierarchical clustering dendrogram. EQ is specifically designed to measure the quality of overlapping communities, helping the algorithm find the "sweet spot" between too few and too many groups.

Experimental Results

The study evaluates ELC against five diverse real-world networks (including Zachary’s Karate Club and the Y2H Yeast Protein-Protein Interaction network) and synthetic benchmarks.

  • Accuracy: On the Karate Club dataset, ELC correctly identified the 2 primary communities, whereas the original LC method split the club into 8 fragmented groups.
  • Biological Relevance: In the Y2H network, ELC identified communities that were significantly more "enriched" with specific biological functions compared to LC and CPM.
  • Superior Coverage: In the large Y2H protein network, traditional methods like CPM (Clique Percolation Method) failed to assign over 80% of the nodes to any community. ELC maintained a 100% cover rate.
  • Performance: ELC consistently achieved higher In-group Proportion (IGP) scores, meaning nodes within its identified communities were more likely to have their nearest neighbors in the same community.

Discussion and Limitations

The core insight of this research is that link similarity should not be binary. By capturing indirect relationships, ELC creates a denser similarity matrix that provides a stronger signal for clustering. Furthermore, EQ proves to be a more sensible stopping rule than partition density, which tends to favor mathematically dense but practically useless micro-communities.

However, ELC is not a universal solution. In the US College Football dataset, ELC performed slightly worse than the original LC and CPM methods. The authors attribute this to the network's high average node degree, where the "extended" similarity might introduce more noise than signal. Future work may explore ways to handle "noise" nodes or outliers that do not belong to any functional group.

Summary updated

Abstract

Link Clustering (LC) is a relatively new method for detecting overlapping communities in networks. The basic principle of LC is to derive a transform matrix whose elements are composed of the link similarity of neighbor links based on the Jaccard distance calculation; then it applies hierarchical clustering to the transform matrix and uses a measure of partition density on the resulting dendrogram to determine the cut level for best community detection. However, the original link clustering method does not consider the link similarity of non-neighbor links, and the partition density tends to divide the communities into many small communities. In this paper, an Extended Link Clustering method (ELC) for overlapping community detection is proposed. The improved method employs a new link similarity, Extended Link Similarity (ELS), to produce a denser transform matrix, and uses the maximum value of EQ (an extended measure of quality of modularity) as a means to optimally cut the dendrogram for better partitioning of the original network space. Since ELS uses more link information, the resulting transform matrix provides a superior basis for clustering and analysis. Further, using the EQ value to find the best level for the hierarchical clustering dendrogram division, we obtain communities that are more sensible and reasonable than the ones obtained by the partition density evaluation. Experimentation on five real-world networks and artificially-generated networks shows that the ELC method achieves higher EQ and In-group Proportion (IGP) values. Additionally, communities are more realistic than those generated by either of the original LC method or the classical CPM method.
BibTeX
@inproceedings{huang2013link,
  author = {Lan Huang and Guishen Wang and Yan Wang and Enrico Blanzieri and Chao Su},
  title = {{Link Clustering with Extended Link Similarity and EQ Evaluation Division}},
  booktitle = {PLoS},
  year = {2013},
  doi = {10.1371/journal.pone.0066005},
}
Figure