Structural sparsity of complex networks: bounded expansion in random models and real-world graphs

DOI10.1016/j.jcss.2019.05.004zbMath1425.05149arXiv1406.2587OpenAlexW2962853920WikidataQ127822932 ScholiaQ127822932MaRDI QIDQ2316938

Peter Rossmanith, Erik D. Demaine, Blair D. Sullivan, Somnath Sikdar, Felix Reidl, Fernando F. S. Sánchez Villaamil

Publication date: 7 August 2019

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1406.2587

zbMATH Keywords

random graphscomplex networkscentrality measuresbounded expansionstructural sparsitymotif counting

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Related Items (11)

Minimum vertex cover in generalized random graphs with power law degree distribution ⋮ Eccentricity queries and beyond using hub labels ⋮ A general purpose algorithm for counting simple cycles and simple paths of any length ⋮ Parameterized complexity of envy-free resource allocation in social networks ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ A color-avoiding approach to subgraph counting in bounded expansion classes ⋮ First-Order Model-Checking in Random Graphs and Complex Networks ⋮ Configuring Random Graph Models with Fixed Degree Sequences ⋮ Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size ⋮ Width, depth, and space: tradeoffs between branching and dynamic programming ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness

Uses Software

• GraphBase
• SNAP
• plfit

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs
• Sparsity. Graphs, structures, and algorithms
• Characterisations and examples of graph classes with bounded expansion
• Generating simple random graphs with prescribed degree distribution
• A note on the graph isomorphism counting problem
• The asymptotic number of labeled graphs with given degree sequences
• On the scaling of the chemical distance in long-range percolation models
• Connected components in random graphs with given expected degree sequences
• The diameter of a scale-free random graph
• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• The centrality index of a graph
• From the Cover: The structure of scientific collaboration networks
• The degree sequence of a scale-free random graph process
• A faster algorithm for betweenness centrality*
• Kernelization Using Structural Parameters on Sparse Graph Classes
• Smoothed Analysis on Connected Graphs
• Compact topological minors in graphs
• Statistical mechanics of complex networks
• Emergence of Scaling in Random Networks
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
• The small-world phenomenon
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Threshold behaviour and final outcome of an epidemic on a random network with household structure
• Power-Law Distributions in Empirical Data
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• The Structure and Function of Complex Networks
• Community structure in social and biological networks
• Deciding First-Order Properties of Nowhere Dense Graphs
• A critical point for random graphs with a given degree sequence
• Stochastic Blockmodels for Directed Graphs
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• A Faster Parameterized Algorithm for Treedepth
• The probability that a random multigraph is simple. II
• The phase transition in inhomogeneous random graphs
• Collective dynamics of ‘small-world’ networks
• Probabilistic Graphlet Transfer for Photo Cropping
• Testing first-order properties for subclasses of sparse graphs
• Bidimensionality and Geometric Graphs
• Contraction decomposition in h-minor-free graphs and algorithmic applications
• Machine Learning: ECML 2004
• The average distances in random graphs with given expected degrees
• Network Analysis

This page was built for publication: Structural sparsity of complex networks: bounded expansion in random models and real-world graphs