Discovering Large Dense Subgraphs in Massive Graphs

By David Gibson, Ravi Kumar, Andrew Tomkins. Very Large Data Bases Conference, 2005

452 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/6e99e31a250bd6147f78b5fb2568c6cdc332b3b6

How researchers see this paper

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

Citations in the corpus

Community Detection and Mining in Social Media (2010, background): “Thus, Gibson et al. (2005) present an”
Efficient semi-streaming algorithms for local triangle counting in massive graphs (2008, methodology): “In [20], the authors use the techniques of shingles and linear hashing to”
Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees (2013, unknown): “In the Web graph, dense subgraphs may correspond to thematic groups or even spam link farms, as observed by Gibson et al. [18].”
The Algorithm Design Manual (2020, background): “See [GKT05] for an interesting application of densest subgraph, namely detecting link spam on the Web.”
Efficient similarity joins for near duplicate detection (2008, background): “include document clustering [6], finding replicated Web collections [9], detecting plagiarism [20], community mining in a social network site [25], collaborative filtering [3] and discovering large dense graphs [15].”
The community-search problem and how to plan a successful cocktail party (2010, methodology): “Discovering communities in graphs and social networks has drawn a large amount of attention in recent years [9, 13, 15, 16, 25].”
GADDI: distance index based subgraph matching in biological networks (2009, background): “However, the large database graph of interests is more likely to be generally sparse and locally dense (as noted in [14]).”
Adversarial Web Search (2011, methodology): “The algorithm in [79] works as follows: first, the graph is represented as an adjacency list, and groups of n nodes from each adjacency list are converted into a hash sketch.”
Scalable Temporal Latent Space Inference for Link Prediction in Dynamic Social Networks (2014, background): “[32] concluded that realworld networks are generally globally very sparse, where most of nodes have a relatively small number of neighbors.”
On Finding Dense Subgraphs (2009, background): “Finding a dense subgraph also acts as a useful primitive for discovering communities in web and social networks, for compressed representation of a graph and for spam detection [9, 7, 12].”
Truncated power method for sparse eigenvalue problems (2011, methodology): “In particular, they have been used to select features for ranking (Geng et al., 2007), to identify cores of communities (Kumar et al., 1999), and to combat link spam (Gibson et al., 2005).”
Querying k-truss community in large and dynamic graphs (2014, methodology): “…including clique [3, 5, 22, 24], quasi-clique [19], k -core [2, 4], k -truss [7, 21, 26], dense neighborhood graph [23], dense bipartite subgraph [12], etc. Clique and quasi-clique enumeration methods include the classical algorithm [3], the external-memory H ∗ -graph algorithm [5],…”
Graph summarization with bounded error (2008, background): “In a very different setting, [20, 12] devise algorithms to extract large dense subgraphs from the Web graph, since these typically correspond to online communities or link spam.”