Kronecker Graphs: An Approach to Modeling Networks

Abstract

How can we model networks with a mathematically tractable model that allows for rigorous analysis of network properties? Networks exhibit a long list of surprising properties: heavy tails for the degree distribution; small diameters; and densification and shrinking diameters over time. Most present network models either fail to match several of the above properties, are complicated to analyze mathematically, or both. In this paper we propose a generative model for networks that is both mathematically tractable and can generate networks that have the above mentioned properties. Our main idea is to use the Kronecker product to generate graphs that we refer to as "Kronecker graphs". First, we prove that Kronecker graphs naturally obey common network properties. We also provide empirical evidence showing that Kronecker graphs can effectively model the structure of real networks. We then present KronFit, a fast and scalable algorithm for fitting the Kronecker graph generation model to large real networks. A naive approach to fitting would take super- exponential time. In contrast, KronFit takes linear time, by exploiting the structure of Kronecker matrix multiplication and by using statistical simulation techniques. Experiments on large real and synthetic networks show that KronFit finds accurate parameters that indeed very well mimic the properties of target networks. Once fitted, the model parameters can be used to gain insights about the network structure, and the resulting synthetic graphs can be used for null- models, anonymization, extrapolations, and graph summarization.

References in corpus (15)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The diameter of the world wide web
• Hierarchical organization of modularity in metabolic networks
• Hierarchical structure and the prediction of missing links in networks
• Hierarchical Organization in Complex Networks
• How Popular is Your Paper? An Empirical Study of the Citation Distribution
• Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
• Highly Optimized Tolerance: Robustness and Power Laws in Complex Systems
• Extracting the hierarchical organization of complex systems
• Pseudofractal Scale-free Web
• Spectra of "Real-World" Graphs: Beyond the Semi-Circle Law
• Deterministic Scale-Free Networks
• Highly clustered scale-free networks
• Core-periphery organization of complex networks

Cited by in corpus (163)

• Analyzing and Modeling Real-World Phenomena with Complex Networks: A Survey of Applications
• Learning Deep Generative Models of Graphs
• Uncovering the Temporal Dynamics of Diffusion Networks
• Constrained Graph Variational Autoencoders for Molecule Design
• Community structure and scale-free collections of Erdös-Rényi graphs
• Learning Discrete Structures for Graph Neural Networks
• A Scalable Generative Graph Model with Community Structure
• Multiplicative Attribute Graph Model of Real-World Networks
• Modeling Information Propagation with Survival Theory
• SNAP: A General Purpose Network Analysis and Graph Mining Library
• Network Archaeology: Uncovering Ancient Networks from Present-day Interactions
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Counting Triangles in Massive Graphs with MapReduce
• Influence Maximization in Continuous Time Diffusion Networks
• Kernel-Based Structural Equation Models for Topology Identification of Directed Networks
• Semi-Blind Inference of Topologies and Dynamical Processes over Graphs
• Tensor Decompositions for Identifying Directed Graph Topologies and Tracking Dynamic Networks
• Asymptotic behavior and distributional limits of preferential attachment graphs
• Local Differential Privacy and Its Applications: A Comprehensive Survey
• Optimal modularity and memory capacity of neural reservoirs
• An In-Depth Analysis of Stochastic Kronecker Graphs
• A maximum entropy framework for non-exponential distributions
• Modeling Social Networks with Node Attributes using the Multiplicative Attribute Graph Model
• Tracking Switched Dynamic Network Topologies from Information Cascades
• Evolution of Social-Attribute Networks: Measurements, Modeling, and Implications using Google+
• Submodular Inference of Diffusion Networks from Multiple Trees
• Degree Relations of Triangles in Real-world Networks and Models
• Neural Ordinary Differential Equation Control of Dynamics on Graphs
• Inference of Spatio-Temporal Functions over Graphs via Multi-Kernel Kriged Kalman Filtering
• Unbiased Graph Embedding with Biased Graph Observations
• Dimensionality of social networks using motifs and eigenvalues
• Data Sketching for Large-Scale Kalman Filtering
• Splines and Wavelets on Circulant Graphs
• Inferring Graphs from Cascades: A Sparse Recovery Framework
• Statistical validation of high-dimensional models of growing networks
• Power Grid Network Evolutions for Local Energy Trading
• Time-Varying Graphs and Social Network Analysis: Temporal Indicators and Metrics
• Capturing Dynamics of Information Diffusion in SNS: A Survey of Methodology and Techniques
• Back to the Past: Source Identification in Diffusion Networks from Partially Observed Cascades
• Permutation Invariant Graph Generation via Score-Based Generative Modeling
• BioCode: A Data-Driven Procedure to Learn the Growth of Biological Networks
• Learning multifractal structure in large networks
• Multiscale Network Generation
• Corona graphs as a model of small-world networks
• Graphlet decomposition of a weighted network
• Time-Varying Graphs and Dynamic Networks
• Scalable Realistic Recommendation Datasets through Fractal Expansions
• Generative Model Selection Using a Scalable and Size-Independent Complex Network Classifier
• On converting community detection algorithms for fuzzy graphs in Neo4j
• KoPA: Automated Kronecker Product Approximation
• Darwini: Generating realistic large-scale social graphs
• Quantum Walk Search on Kronecker Graphs
• BDGS: A Scalable Big Data Generator Suite in Big Data Benchmarking
• Benchmarks for Graph Embedding Evaluation
• Accurate, Efficient and Scalable Training of Graph Neural Networks
• Disentangling Interpretable Generative Parameters of Random and Real-World Graphs
• Community Detection in Partially Observable Social Networks
• Authorship Attribution Using Word Network Features
• Mathematical and Algorithmic Analysis of Network and Biological Data
• To Push or To Pull: On Reducing Communication and Synchronization in Graph Computations
• Popularity Prediction on Social Platforms with Coupled Graph Neural Networks
• On Large-Scale Graph Generation with Validation of Diverse Triangle Statistics at Edges and Vertices
• Deep Generative Graph Distribution Learning for Synthetic Power Grids
• On the motifs distribution in random hierarchical networks
• A Generative Model of Software Dependency Graphs to Better Understand Software Evolution
• Spectra, hitting times, and resistance distances of $q$-subdivision graphs
• Modeling Graphs with Vertex Replacement Grammars
• Efficient Generation ε-close to G(n,p) and Generalizations
• Optimal Quantum Walk Search on Kronecker Graphs with Dominant or Fixed Regular Initiators
• SCGG: A Deep Structure-Conditioned Graph Generative Model
• Spatio-Temporal Modeling of Users' Check-ins in Location-Based Social Networks
• In-Network Neighborhood-Based Node Similarity Measure: A Unified Parametric Model
• Predicting Graph Categories from Structural Properties
• StratLearner: Learning a Strategy for Misinformation Prevention in Social Networks
• Modular Networks for Validating Community Detection Algorithms
• Building LEGO Using Deep Generative Models of Graphs
• DeepGG: a Deep Graph Generator
• Learning Product Graphs Underlying Smooth Graph Signals
• Log(Graph): A Near-Optimal High-Performance Graph Representation
• EvoNet: A Neural Network for Predicting the Evolution of Dynamic Graphs
• Automatic Discovery of Families of Network Generative Processes
• Asynchronous adaptive networks
• Fully Dynamic Single-Source Reachability in Practice: An Experimental Study
• Fast Path Localization on Graphs via Multiscale Viterbi Decoding
• Stochastic Kronecker Graph on Vertex-Centric BSP
• Learning Graph Topological Features via GAN
• Graph Distance from the Topological View of Non-backtracking Cycles
• Inference for Network Structure and Dynamics from Time Series Data via Graph Neural Network
• Asynchronous Adaptation and Learning over Networks - Part II: Performance Analysis
• Emergence through Selection: The Evolution of a Scientific Challenge
• Continuous Graph Flow
• F-FADE: Frequency Factorization for Anomaly Detection in Edge Streams
• The Infinity Mirror Test for Graph Models
• Network Diffusions via Neural Mean-Field Dynamics
• Distributed Edge Partitioning for Trillion-edge Graphs
• DeepNC: Deep Generative Network Completion
• Revisiting Non-Progressive Influence Models: Scalable Influence Maximization
• Reciprocal versus Parasocial Relationships in Online Social Networks
• Decompositions of Triangle-Dense Graphs
• Self-Coordinated Corona Graphs: a model for complex networks
• The HyperKron Graph Model for higher-order features
• SepNE: Bringing Separability to Network Embedding
• Modeling and Analysis of Information Communities
• Structural Diversity and Homophily: A Study Across More than One Hundred Big Networks
• Auto-decoding Graphs
• Product Measure Approximation of Symmetric Graph Properties
• The Infinity Mirror Test for Analyzing the Robustness of Graph Generators
• Scaling Up Collaborative Filtering Data Sets through Randomized Fractal Expansions
• Structure and Dynamics of Information Pathways in Online Media
• Deep Generative Modeling in Network Science with Applications to Public Policy Research
• Hitting times and resistance distances of $q$-triangulation graphs: Accurate results and applications
• DRONE: a Distributed Subgraph-Centric Framework for Processing Large Scale Power-law Graphs
• USCO-Solver: Solving Undetermined Stochastic Combinatorial Optimization Problems
• Bayesian Model Selection with Graph Structured Sparsity
• Using Graph Properties to Speed-up GPU-based Graph Traversal: A Model-driven Approach
• Extended corona product as an exactly tractable model for weighted heterogeneous networks
• Modeling Graphs Using a Mixture of Kronecker Models
• Priority Attachment: a Comprehensive Mechanism for Generating Networks
• Evaluating the Cost of Atomic Operations on Modern Architectures
• A Heuristic for Direct Product Graph Decomposition
• Ego-CNN: Distributed, Egocentric Representations of Graphs for Detecting Critical Structures
• Using Bayesian Network Representations for Effective Sampling from Generative Network Models
• Breadth First Search Vectorization on the Intel Xeon Phi
• Latent Network Embedding via Adversarial Auto-encoders
• On the Power of Edge Independent Graph Models
• Efficiently Sampling Multiplicative Attribute Graphs Using a Ball-Dropping Process
• Community Structures in Information Networks for a Discrete Agent Population
• Detecting Anomalous Activity on Networks with the Graph Fourier Scan Statistic
• Learning an Integrated Distance Metric for Comparing Structure of Complex Networks
• DINE: A Framework for Deep Incomplete Network Embedding
• Transforming Graph Representations for Statistical Relational Learning
• More Parallelism in Dijkstra's Single-Source Shortest Path Algorithm
• On the diameter of the Kronecker product graph
• Evolution of Real-world Hypergraphs: Patterns and Models without Oracles
• The Evolution of the Cuban HIV/AIDS Network
• Spectral Estimation of Conditional Random Graph Models for Large-Scale Network Data
• Edge corona product as an approach to modeling complex simplical networks
• A stopping criterion for Markov chains when generating independent random graphs
• Tensor-generated fractals: Using tensor decompositions for creating self-similar patterns
• Accelerating Irregular Computations with Hardware Transactional Memory and Active Messages
• The thickness of the Kronecker product of graphs
• DegreeSketch: Distributed Cardinality Sketches on Massive Graphs with Applications
• A Parallel Sparse Tensor Benchmark Suite on CPUs and GPUs
• Consensus Networks over Finite Fields
• On Privacy of Socially Contagious Attributes
• Multi-View Treelet Transform
• Operator Autoencoders: Learning Physical Operations on Encoded Molecular Graphs
• Further results on structured regression for multi-scale networks
• Differentially Private Link Prediction With Protected Connections
• On the diameter of Kronecker graphs
• Social Graph Restoration via Random Walk Sampling
• Vectorization of Hybrid Breadth First Search on the Intel Xeon Phi
• Large Graph Models: A Review
• Kronecker Product Least Squares
• Influence Estimation and Maximization via Neural Mean-Field Dynamics
• Learning to maximize global influence from local observations
• SlimSell: A Vectorizable Graph Representation for Breadth-First Search
• Connectivity and giant component in random distance graphs
• Citations, Sequence Alignments, Contagion, and Semantics: On Acyclic Structures and their Randomness
• Learning and Optimization with Submodular Functions
• The Fraïssé limit of matrix algebras with the rank metric
• A New Perspective of Graph Data and A Generic and Efficient Method for Large Scale Graph Data Traversal
• Controllability of Kronecker Product Networks