Structural sparsity of complex networks: bounded expansion in random models and real-world graphs
type: Item
instance of: scholarly article
title: Structural sparsity of complex networks: bounded expansion in random models and real-world graphs
zbMATH Open document ID: 1425.05149
author: Erik D. Demaine
author: Felix Reidl
author: Peter Rossmanith
author: Fernando F. S. Sánchez Villaamil
author: Somnath Sikdar
author: Blair D. Sullivan
published in: Journal of Computer and System Sciences
publication date: 2019-08-07T00:00:00Z
full work available at URL: https://arxiv.org/abs/1406.2587
full work available at URL: 27714.pdf
Mathematics Subject Classification ID: 05C82
zbMATH DE Number: 7089552
zbMATH Keywords: structural sparsity
zbMATH Keywords: bounded expansion
zbMATH Keywords: complex networks
zbMATH Keywords: random graphs
zbMATH Keywords: motif counting
zbMATH Keywords: centrality measures
describes a project that uses: GraphBase
describes a project that uses: plfit
describes a project that uses: SNAP
MaRDI profile type: Publication
OpenAlex ID: W2962853920
arXiv ID: 1406.2587
cites work: Statistical mechanics of complex networks
cites work: Q4845256
cites work: Threshold behaviour and final outcome of an epidemic on a random network with household structure
cites work: Emergence of Scaling in Random Networks
cites work: The asymptotic number of labeled graphs with given degree sequences
cites work: On the scaling of the chemical distance in long-range percolation models
cites work: The phase transition in inhomogeneous random graphs
cites work: The degree sequence of a scale-free random graph process
cites work: The diameter of a scale-free random graph
cites work: A faster algorithm for betweenness centrality*
cites work: Generating simple random graphs with prescribed degree distribution
cites work: Probabilistic Graphlet Transfer for Photo Cropping
cites work: The average distances in random graphs with given expected degrees
cites work: Connected components in random graphs with given expected degree sequences
cites work: Q3370774
cites work: Power-Law Distributions in Empirical Data
cites work: Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
cites work: Q5417628
cites work: Contraction decomposition in h-minor-free graphs and algorithmic applications
cites work: Testing first-order properties for subclasses of sparse graphs
cites work: Bidimensionality and Geometric Graphs
cites work: Q3057276
cites work: Kernelization Using Structural Parameters on Sparse Graph Classes
cites work: Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs
cites work: Community structure in social and biological networks
cites work: Deciding First-Order Properties of Nowhere Dense Graphs
cites work: The probability that a random multigraph is simple. II
cites work: Compact topological minors in graphs
cites work: Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
cites work: The small-world phenomenon
cites work: Machine Learning: ECML 2004
cites work: Q3140399
cites work: Network Analysis
cites work: Smoothed Analysis on Connected Graphs
cites work: Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
cites work: A note on the graph isomorphism counting problem
cites work: A critical point for random graphs with a given degree sequence
cites work: The Size of the Giant Component of a Random Graph with a Given Degree Sequence
cites work: Grad and classes with bounded expansion. I: Decompositions
cites work: Grad and classes with bounded expansion. II: Algorithmic aspects
cites work: Sparsity. Graphs, structures, and algorithms
cites work: Characterisations and examples of graph classes with bounded expansion
cites work: The Structure and Function of Complex Networks
cites work: The structure of scientific collaboration networks
cites work: A Faster Parameterized Algorithm for Treedepth
cites work: The centrality index of a graph
cites work: Stochastic Blockmodels for Directed Graphs
cites work: Collective dynamics of ‘small-world’ networks
Wikidata QID: Q127822932
DOI: 10.1016/J.JCSS.2019.05.004
Recommended article: The dynamics of sparse random networks
Recommended article: Sparsity of weighted networks: measures and applications

Structural sparsity of complex networks: bounded expansion in random models and real-world graphs (Recommended article)
Recommended article: Sparse graphs: Metrics and random models
Similarity Score: 0.8874103
Recommender Run: Recommender Run 3

Structural sparsity of complex networks: bounded expansion in random models and real-world graphs (Recommended article)
Recommended article: Analysis of Networks via the Sparseβ-model
Similarity Score: 0.8827983
Recommender Run: Recommender Run 3

Structural sparsity of complex networks: bounded expansion in random models and real-world graphs (Recommended article)
Recommended article: Empirical spectral distributions of sparse random graphs
Similarity Score: 0.8786513
Recommender Run: Recommender Run 3

Structural sparsity of complex networks: bounded expansion in random models and real-world graphs (Recommended article)
Recommended article: Asymptotic behavior of common connections in sparse random networks
Similarity Score: 0.8735173
Recommender Run: Recommender Run 3

Structural sparsity of complex networks: bounded expansion in random models and real-world graphs (Recommended article)
Recommended article: On the use of random graphs as null model of large connected networks
Similarity Score: 0.87153447
Recommender Run: Recommender Run 3

Structural sparsity of complex networks: bounded expansion in random models and real-world graphs (Recommended article)
Recommended article: Asymptotics for sparse exponential random graph models
Similarity Score: 0.870701
Recommender Run: Recommender Run 3