ANF: a fast and scalable tool for data mining in massive graphs

By Christopher R. Palmer, Phillip B. Gibbons, Christos Faloutsos. Knowledge Discovery and Data Mining, 2002

315 citations recorded by the source corpus.

Subfields: Information Systems, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/4b5eac412054c6f19e52796a43026cde4f301d94

How researchers see this paper

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

In Information Systems

In Statistical and Nonlinear Physics

Citations in the corpus

Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and Experiments (2005, methodology): “For example, [Palmer et al. 02] Random walks were used earlier to compute various web statistics, mostly focused on sampling the web (uniformly or according to static PR) [Henzinger et al. 00, Rusmevichientong et al. 01, The lower bounds of Section 4 show that precise PPR requires a signiﬁcantly…”
Synopsis diffusion for robust aggregation in sensor networks (2004, methodology): “However, in transmitting multiple bit-vectors, we reduce the size of the synopsis by interleaving the bit-vectors and applying run-length encoding [24].”
Handbook of Big Data (2016, methodology): “Generating an accurate estimate of the effective diameter is possible in O(n) time and memory using a simple algorithm with a sophisticated analysis [24,25].”
Ligra: a lightweight graph processing framework for shared memory (2013, unknown): “[37].”
Graphs over time: densification laws, shrinking diameters and possible explanations (2005, methodology): “In particular, we applied the Approximate Neighborhood Function (ANF) approach [27] (in two different implementations), which can estimate effective diameters for very large graphs, as well as a basic sampling approach in which we ran exhaustive breadth-first search from a subset of the nodes chosen”
An efficient algorithm for discovering frequent subgraphs (2004, background): “For this reason, a considerable amount of work has been focused on approximate algorithms [46], [23], [28], [35] that use various heuristics to prune the search space.”
Kronecker Graphs: An Approach to Modeling Networks (2008, background): “They correspond exactly toa significant portion of what we want to prove: heavy-tailed distributions for in-degree, out-degree, eigenvalues, and eigenvectors.”
Approximate aggregation techniques for sensor databases (2004, methodology): “SKETCH uses 20 bitmaps and the compression techniques of [18] with group size of 2 (the uncompressed size is 36000 bytes).”
R-MAT: A Recursive Model for Graph Mining (2004, unknown): “Apart from these, there are many other measures such as clustering coefficient, expansion, resilience, prestige, influence, stress and so on [7, 12, 22, 18].”
Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication (2005, background): “Apart from these, several other patterns have been found, including the “stress” [14,9], “resilience” [2,22], “clustering coefficient” and many more.”
Adversarial Web Search (2011, methodology): “Among the features used by these classifiers, a particularly useful set are neighborhood sizes at short link-distances [19, 184], different variants of PageRank [183], and TrustRank [94] which is described in Section 5.”
Mining of Massive Datasets (2011, methodology): “The ANF Algorithm was first investigated in [13].”
Analysis of topological characteristics of huge online social networking services (2007, background): “The eﬀective diameter is the 90th-percentile of the path length distribution, and is a better metric than the maximum diameter in estimating the network size, as the maximum diameter can be an outlier from a small number of nodes forming a chain.”
Graph mining: Laws, generators, and algorithms (2006, background): “…researchers have found that while a large number of randomly chosen nodes and edges can be removed from the Internet graph without appreciable disruption in service, attacks targeting important nodes can disrupt the network very quickly and dramatically [Palmer et al. 2002; Albert et al. 2000].”