PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Community Detection in Large Networks using Content and Links

Yiye Ruan, David Fuhry, Srinivasan Parthasarathy

arXiv:1212.0146v1cs.SIphysics.soc-ph

TL;DR

Large networks contain noisy links, making content-aware community detection difficult to combine with scalability. CODICIL fuses content and topology, samples locally relevant edges, and then applies standard clustering algorithms; experiments report strong quality and much faster execution, including on large graphs.

  • Problem

    Community detection must combine noisy link structure with content information efficiently and effectively at web scale.

  • Method

    CODICIL fuses content and graph topology, retains locally relevant edges through biased sampling, and passes the simplified graph to a content-insensitive clustering algorithm.

  • Results

    CODICIL often achieves comparable or superior clustering quality while running several orders of magnitude faster than state-of-the-art approaches.

  • Takeaways & Limitations

    Content-conscious graph simplification preserves clustering accuracy more effectively than topology-only sampling while reducing computation cost across the three datasets.

  • Takeaways & Limitations

    On Flickr, PCL-DC exceeded 16 GB of memory for larger requested cluster counts, while its reported F-scores remained below 0.25 for tested settings.

Abstract

from arXiv · show

In this paper we discuss a very simple approach of combining content and link information in graph structures for the purpose of community discovery, a fundamental task in network analysis. Our approach hinges on the basic intuition that many networks contain noise in the link structure and that content information can help strengthen the community signal. This enables ones to eliminate the impact of noise (false positives and false negatives), which is particularly prevalent in online social networks and Web-scale information networks. Specifically we introduce a measure of signal strength between two nodes in the network by fusing their link strength with content similarity. Link strength is estimated based on whether the link is likely (with high probability) to reside within a community. Content similarity is estimated through cosine similarity or Jaccard coefficient. We discuss a simple mechanism for fusing content and link similarity. We then present a biased edge sampling procedure which retains edges that are locally relevant for each graph node. The resulting backbone graph can be clustered using standard community discovery algorithms such as Metis and Markov clustering. Through extensive experiments on multiple real-world datasets (Flickr, Wikipedia and CiteSeer) with varying sizes and characteristics, we demonstrate the effectiveness and efficiency of our methods over state-of-the-art learning and mining approaches several of which also attempt to combine link and content analysis for the purposes of community discovery. Specifically we always find a qualitative benefit when combining content with link analysis. Additionally our biased graph sampling approach realizes a quantitative benefit in that it is typically several orders of magnitude faster than competing approaches.

1 Introduction

The paper frames community detection as combining noisy link structure with content information in very large networks. It introduces CODICIL to fuse both signals, simplify graphs, and support efficient clustering with competitive community quality.

  • 1 Introduction: Community detection must combine link and content information despite noisy links, unclear fusion strategies, and graphs containing millions of nodes and billions of edges.The noise includes both false-positive and false-negative links.
  • 1 Introduction: Existing approaches either ignore content or incorporate it at potentially prohibitive scalability costs.The paper describes content-aware methods as qualitatively promising but often expensive.
  • 1 Introduction: CODICIL fuses content and graph topology to retain important edges, producing a transformed graph for clustering with METIS or Markov clustering.The framework separates graph simplification from subsequent content-insensitive clustering.
  • 1 Introduction: Experiments on Flickr, Wikipedia, and CiteSeer show comparable or superior community quality while CODICIL runs several orders of magnitude faster than state-of-the-art approaches.The evaluation spans multiple real-world datasets and graph clustering algorithms.

2 Related Work

Prior work spans topology-only clustering, probabilistic content-link models, graph augmentation, multiple-view methods, and edge sampling. The paper positions CODICIL as a lighter and more scalable alternative to approaches whose complexity or assumptions limit larger problems.

  • Community Discovery using Topology (and Content): Most graph-clustering methods discard content information while optimizing structural community discovery.The related work includes widely used algorithms such as Metis, Graclus, and Markov clustering.
  • Clustering/Learning Multiple Graphs: Probabilistic models incorporate content and links through latent-variable or discriminative formulations, but their applications include citation and email networks.Examples include PLSA-PHITS, Community-User-Topic, Link-PLSA-LDA, and PCL-DC.
  • Related-work limitations: Several alternatives achieve decent performance on small and medium graphs but incur model complexity, parameter sensitivity, or limited scalability.Some methods also rely on domain-specific assumptions or search spaces constrained by neighborhood intersections.
  • Clustering/Learning Multiple Graphs: Content-aware alternatives augment graphs with attribute nodes, use multiple views, or factorize graph representations before clustering.The paper discusses SA-Cluster-Inc, consensus functions, and linked matrix factorization.
  • Graph Sampling for Fast Clustering: Edge-sampling methods can preserve locally relevant structural edges, but the cited approach does not incorporate content information.Other sampling work targets cuts, graph-stream structure, or outlier detection rather than community preservation.

3 Methodology

CODICIL constructs a simplified graph that preserves the original vertices while retaining edges connecting structurally and content-wise similar nodes. The resulting sparse graph is intended to improve clustering runtime and memory use.

  • 3 Methodology: The input graph contains vertices, topological edges, and per-vertex term vectors representing words, tags, or n-grams.The notation treats graph and network, and vertex and node, interchangeably.
  • 3 Methodology: CODICIL generates a sampled graph with the same vertex set and far fewer edges than the input graph.Reducing |Esample| relative to |Et| targets lower runtime and memory use during clustering.
  • 3 Methodology: The sampled edges connect node pairs that are similar in both graph structure and content, including content-supported pairs absent from the original topology.The design uses graph simplification to preserve relevant structure while incorporating content similarity.

3.1 Key Intuitions

CODICIL’s workflow creates content edges, combines them with topological edges, samples the union using local relevance, and clusters the resulting simplified graph.

  • 3.1 Key Intuitions: CODICIL first creates content edges from the nodes’ content representations.These edges supplement the original topological graph.
  • 3.1 Key Intuitions: It then samples the union of content and topological edges with bias, retaining locally relevant connections.The biased sampling forms a smaller edge set containing the most relevant edges.
  • 3.1 Key Intuitions: Finally, a graph clustering algorithm partitions the simplified graph into the desired number of clusters.The clustering stage operates on the sampled-edge graph.

3.2 Basic Framework

CODICIL constructs a sparse graph by combining topological and content similarities, retaining locally relevant edges before applying a standard graph clustering algorithm. The framework supports flexible similarity, normalization, weighting, and graph-clustering choices.

  • Framework inputs: CODICIL takes an original graph, term vectors, a content-neighbor count, normalization and weighting functions, and a clustering algorithm as inputs.Any content-insensitive graph clustering algorithm can be plugged into the framework.
  • Content-edge construction: For each vertex, CODICIL adds edges to its k most content-similar neighbors, computed using cosine similarity between TF-IDF term vectors.The k vertices with the highest cosine similarity values are selected.
  • Similarity fusion: The method unions content and topological edges, computes normalized topological and content similarities, and combines them as α · simnormtij + (1 − α) · simnormcij.Topological similarity compares overlapping neighbor sets, while content similarity compares the nodes’ term vectors.
  • Local graph simplification: CODICIL retains the highest-scoring edges from each local neighborhood, targeting a much smaller sampled edge set while ensuring every vertex remains incident to at least one edge.The retention rule gives smaller-degree vertices a larger retained-edge fraction than larger-degree vertices.
  • Clustering and extensions: The sampled graph is clustered into l clusters, and the framework can be extended to weighted-edge and attribute graphs.Weighted graphs incorporate original edge weights, while node attributes can be represented as indicator vectors.

3.3 Key Speedup Optimizations

CODICIL accelerates content-similarity computation through sparse TF-IDF vectors, topological neighborhood restrictions, minwise hashing, and random projections. These optimizations reduce similarity-estimation cost while aiming to preserve useful accuracy.

  • Sparse content vectors: Truncating TF-IDF vectors to their m highest-weight elements makes them sparser and speeds cosine-similarity calculations with little loss in accuracy.The remaining vector elements are set to zero.
  • Neighborhood restriction: Restricting content edges to 1-hop or 2-hop topological neighborhoods greatly reduces the search space for the TopK operation.The 1-hop option uses direct neighbors; the 2-hop option also includes neighbors’ neighbors.
  • Fast Jaccard estimation: Minwise hashing estimates Jaccard similarity using h random permutations, reducing the post-hashing similarity-estimation cost to O(h).The estimator is unbiased, and h is usually smaller than the set sizes.
  • Fast cosine estimation: Random projection estimates cosine similarity by assigning each d-dimensional vector a sign-based hash signature from a randomly drawn projection vector.The method uses hash-signature agreement to estimate similarity.

3.4 Performance Analysis

CODICIL’s preprocessing computes reusable top-k similarities, while its per-vertex sampling loop has a worst-case runtime of O(n^2 log n). Overall runtime also includes edge preprocessing and the selected clustering algorithm.

  • Preprocessing: The top-k similarity preprocessing is computed once and can be reused for every k′ ≤ k.On the largest Wikipedia dataset, this step completed within a few hours.
  • Loop operations: The Jaccard estimator used in the sampling loop runs in O(h) with a constant number of hashes, while normalization and edge sorting depend on each local neighborhood size.Sorting edges by weight costs O(|Γi| log |Γi|).
  • Overall complexity: O(n^2 log n) is the stated runtime for CODICIL’s loop over vertices, with |Γi| at most n but typically much smaller in real-world graphs.Total runtime adds edge-preprocessing time and the time required by clusteralgo.

4 Experiments

Experiments evaluate CODICIL and baseline clustering methods on CiteSeer, Wikipedia, and Flickr using ground-truth F-score, scalability, and graph-structure analyses. Across datasets, content-aware simplification improves clustering over topology-only sampling while retaining competitive quality with lower computational cost.

  • Datasets: Experiments use three publicly available datasets spanning document and social networks, with graph, content, and ground-truth community information.The datasets are CiteSeer, Wikipedia, and Flickr; Wikipedia categories and Flickr groups overlap.
  • Baseline Methods: The comparison includes content-aware methods, topology-only clustering, and content-only LDA and K-means baselines.CODICIL is compared with SA-Cluster-Inc, PCL-DC, Link-PLSA-LDA, Original Topo, Sampled Topo, LDA, and K-means.
  • Graph Structure: Simplification increases the number of connected components for CiteSeer but leaves Flickr’s count unchanged, with Wikipedia showing similar spectral behavior to Flickr.The Laplacian spectra otherwise have similar overall trends, including spectral gaps and relative eigenvalue changes.
  • Clustering Quality: Average F-score against ground-truth communities is used because conductance measures structural cohesiveness but not content cohesiveness.Precision and recall are defined between predicted and reference node-set clusters.
  • CiteSeer: On CiteSeer, CODICIL reaches within 90% of PCL-DC for both similarity measures and surpasses it when k increases to 70.PCL-DC obtains an F-score of 0.570, while SA-Cluster-Inc and Link-PLSA-LDA obtain 0.348 and 0.458.
  • Efficiency: CODICIL’s CiteSeer edge sampling plus clustering takes under 1 second, versus 234 seconds for PCL-DC and 306 seconds for SA-Cluster-Inc.The authors report CODICIL as at least one order of magnitude faster than state-of-the-art algorithms.
  • Wikipedia: On Wikipedia, CODICIL consistently outperforms Sampled Topo by a large margin and is on par with or better than Original Topo.The result holds for experiments using MLR-MCL and Metis while varying the desired number of clusters.
  • Flickr: On Flickr, SA-Cluster-Inc, LDA, and K-means never exceed F-score 0.2, whereas CODICIL is often higher alongside Original and Sampled Topo.Link-PLSA-LDA takes more than 30 hours on this dataset.

4.6 Scalability

CODICIL combines content-aware edge sampling with graph clustering to reduce runtime while preserving or improving clustering quality. Experiments show strong scalability benefits across datasets, with performance depending on the content–topology weighting and neighborhood constraints.

  • Flickr scalability: Content-aware clustering on Flickr requires less than 8 seconds, three to four orders of magnitude faster than SA-Cluster-Inc, PCL-DC, and LDA.Original Topo takes more than 10 seconds, while Sampled Topo is slightly faster than CODICIL methods.
  • Flickr scalability: CODICIL is at least one order of magnitude faster than topology-only clustering with MLR-MCL and more than four times faster with Metis.The reported running time includes edge sampling and clustering for CODICIL methods.
  • Parameter sensitivity: F-scores are greatest around α = 0.5 on Wikipedia and CiteSeer, whereas Flickr F-score continuously improves as α increases toward greater topological weight.The experiments vary α from 0.1 to 0.9 in increments of 0.1.
  • Neighborhood constraint: On Wikipedia, searching within a 2-hop neighborhood yields results nearly identical to a full search, indicating a sufficiently strong content signal under that constraint.The figure compares full, 1-hop, and 2-hop constraints for the content-neighbor search.
  • Sampling trade-off: Content-conscious edge sampling improves running time across all three datasets while maintaining accuracy near the best-performing methods; topology-only sampling loses accuracy.The reported benefit combines lower computational cost with stronger clustering quality than sampling based only on topology.
  • Scalability trend: CODICIL running time suggests a logarithmic increase with the number of clusters, unlike competing probabilistic and K-means methods whose running time is at least linear in that number.The paper identifies the linear dependence on the desired cluster count as a critical drawback for large-scale workloads.

5 Case Studies

Case studies on Wikipedia show that CODICIL removes peripheral links while preserving semantically relevant neighbors. It can also add content-supported edges absent from the original network.

  • Machine Learning: CODICIL replaces many peripheral neighbors of “machine learning” with semantically relevant pages such as “AdaBoost”, “ensemble learning”, and “pattern recognition”.The topology-only sample retains 119 neighbors but still preserves several peripheral entries.
  • Machine Learning: CODICIL adds “neural network” to the “machine learning” neighborhood even though that edge is absent from the original network.The framework can add edges when content similarity reveals relationships overlooked by the original topology.
  • Graph (Mathematics): For “Graph (Mathematics)”, CODICIL removes peripheral entries while retaining “clique (graph theory)”, “Hamiltonian path”, and “connectivity (graph theory)”.These relevant entries would otherwise be removed by topology-only sampling.

6 Conclusion

The paper concludes that CODICIL fuses content and link similarity, samples locally relevant edges, and then applies standard content-agnostic clustering. Experiments report better quality and much lower runtime, including on very large graphs.

  • Conclusion: CODICIL fuses content and link similarity, retains highly relevant local edges, and clusters the resulting backbone graph with content-agnostic algorithms.The framework is designed as a graph simplification stage followed by standard clustering.
  • Conclusion: CODICIL outperforms state-of-the-art methods in clustering quality while running orders of magnitude faster on moderately sized datasets.The paper also reports efficient handling of graphs with millions of nodes and hundreds of millions of edges.
Loading 1212.0146v1…