Efficient community detection in large networks using content and links

By Yiye Ruan, D. Fuhry, Srinivasan Parthasarathy. 2012

332 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Statistical and Nonlinear Physics

Citations in the corpus

Debiasing Community Detection: The Importance of Lowly Connected Nodes (2019, background): “ing for densely-connected groups of nodes in the graph [14]. More recently, attributed approaches go beyond merely the links to cluster nodes based upon their attributes and their network connections [18]. Existing community detection approaches suffer from a major flaw: the inability to assign lowl”
Clustering attributed graphs: Models, measures and methods (2015, methodology): “With more integrated methods, such as subspace approaches or the one proposed by Ruan et al. (2013), the clustering process can reach a high complexity—quadratic and more.”
Community Detection in Networks with Node Attributes (2013, methodology): “Based on Table I we select one algorithm from each model type: Block-LDA [4] represents soft-membership approaches, while the CODICIL [35] represents heuristics for non-overlapping communities, and the EDCAR [18] represents heuristics for ﬁnding dense subgraphs.”
Effective Community Search for Large Attributed Graphs (2016, methodology): “Ruan et al. [23] proposed a method called CODICIL.”
ArchRAG: Attributed Community-based Hierarchical Retrieval-Augmented Generation (2025, unknown): “We propose an iterative LLM-based hierarchical clustering framework that supports arbitrary graph augmentation (e.g., KNN connections and CODI-CIL [53]) and graph clustering algorithms (e.g., weighted Leiden [62], weighted spectral clustering, and SCAN [73]).”