Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication

By Jure Leskovec, Deepayan Chakrabarti, Jon M. Kleinberg, Christos Faloutsos. European Conference on Principles of Data Mining and Knowledge Discovery, 2005

400 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/82dbac4f046d626420c238a65b121266b122378f

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 Computational Theory and Mathematics

In Statistical and Nonlinear Physics

Citations in the corpus

Kronecker Graphs: An Approach to Modeling Networks (2008, methodology): “…DBLP co-authorship network (Backstrom et al., 2006) CA-GR-QC 5,242 28,980 4,158 0.79 0.66 17 6.1 Co-authorship network ingr-qc category of ArXiv (Leskovec et al., 2005b) CA-HEP-PH 12,008 237,010 11,204 0.93 0.69 13 4.71 Co-authorship network inhep-ph category of ArXiv (Leskovec et al., 2005b)…”
Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks (2009, neutral): “trix [26], which models scale-free graphs, is generated by using repeated”
A Survey of Statistical Network Models (2009, background): “What started as yet another generative procedure [192]”
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].”
Center-piece subgraphs: problem definition and fast solutions (2006, methodology): “To study CePS from the point view of generative model, such as Kronecker graph [23], mixed-membership model [2], infinite relational model [21] etc.”
The GAP Benchmark Suite (2015, methodology): “If the graph is anyhow transformed or converted from the format used for the other kernels, the graph conversion time must be included in the trial time.”
PEGASUS: A Peta-Scale Graph Mining System Implementation and Observations (2009, methodology): “For the performance and scalability experiments, we used synthetic Kronecker graphs [37] since we can generate them with any size, and they are one of the most realistic graphs among synthetic graphs.”
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].”
Networks beyond pairwise interactions: structure and dynamics (2020, methodology): “[254] Jurij Leskovec, Deepayan Chakrabarti, Jon Kleinberg, and Christos Faloutsos.”
Protecting privacy when mining and sharing user data (2012, background): “The model of [120] aims to account for all of the commonly found patters in graphs.”
TensorCast: forecasting and mining with coupled tensors (2018, background): “…degree distribution of big communities can be well approximated by a power-law across several domains [2], that eigenvectors of Kronecker graphs exhibit a multinomial distribution [22], Theorem 3 and multiple generative models where power-law communities arise have been proposed [29,42,45].”