R-MAT: A Recursive Model for Graph Mining

By Deepayan Chakrabarti, Yiping Zhan, Christos Faloutsos. SDM, 2004

1,267 citations recorded by the source corpus.

How does a ‘normal’ computer (or social) network look like? How can we spot ‘abnormal’ sub-networks in the Internet, or web graph? The answer to such questions is vital for outlier detection (terrorist networks, or illegal money-laundering rings), forecasting, and simulations (“how will a computer virus spread?”). The heart of the problem is finding the properties of real graphs that seem to persist over multiple disciplines. We list such “laws” and, more importantly, we propose a simple, parsimonious model, the “recursive matrix” (R-MAT) model, which can quickly generate realistic graphs, capturing the essence of each graph in only a few parameters. Contrary to existing generators, our model can trivially generate weighted, directed and bipartite graphs; it subsumes the celebrated Erdős-Renyi model as a special case; it can match the power law behaviors, as well as the deviations from them (like the “winner does not take it all” model of Pennock et al. [20]). We present results on multiple, large real graphs, where we show that our parameter fitting algorithm (AutoMAT-fast) fits them very well.

Subfields: Computer Vision and Pattern Recognition, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/01c1f0e97ce5c74c714dc7aa43cb064f45cc3b04

How researchers see this paper

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

In Computer Vision and Pattern Recognition

In Statistical and Nonlinear Physics

Citations in the corpus

Efficient aggregation for graph summarization (2008, methodology): “Therefore, we use the R-MAT model [8] in the GTgraph suites [2] to generate graphs with power-law degree distributions and small-world characteristics.”
Preserving Privacy in Social Networks Against Neighborhood Attacks (2008, background): “The degrees of vertices in a large social network often follow the power law distribution [20].”
Statistical properties of community structure in large social and information networks (2008, background): “, models in which a hierarchy is given and the linkage probability between pairs of nodes decreases as a function of their distance in the hierarchy [136, 135, 30, 6, 109, 47, 156, 110].”
Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters (2008, background): “, models in which a hierarchy is given and the linkage probability between pairs of nodes decreases as a function of their distance in the hierarchy [139, 138, 31, 6, 110, 48, 159, 111].”
Big data analytics on Apache Spark (2016, methodology): “To alleviate this problem, GraphX offers the GraphGenerators utility which contains random edges generator and several other generators for generating specific types of graphs such as log normal graph (a graph whose vertex out degree distribution is log normal), R-MAT graph [17], grid graph and star”
A Survey of Statistical Network Models (2009, neutral): “Alternative graph generation mechanisms appear every day—R–MAT [60],‘winners don’t take all’ [242],‘forest fire’ [194],‘butterfly’ [212] and RTG [10], to name a few.”
Efficient Parallel Graph Exploration on Multi-Core CPU and GPU (2011, methodology): “As an illustration, Table I shows the number of nodes in each BFS level, obtained from a typical BFS execution on a synthetic graph with 32 million nodes and 256 million edges generated by RMAT model [23] .”
Scalable modeling of real graphs using Kronecker multiplication (2007, background): “Power law (or power law tail) distributions occur in the Web (Kleinberg et al., 1999), in the Internet (Faloutsos et al., 1999), in citation graphs (Redner, 1998), in on-line social networks (Chakrabarti et al., 2004), and many more.”
Green-Marl: a DSL for easy and efficient graph analysis (2012, background): “In the .g (a) RMAT (b) Uniform Figure 7.”
Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication (2005, methodology): “In addition to the degree distribution and scree plot, we also show two typical plots [9]: the distribution of network values (principal eigenvector components, sorted, versus rank) and the hop-plot (the number of reachable pairs P (h) within h hops or less, as a function of the number of hops h).”