Random Graphs with Prescribed $K$-Core Sequences: A New Null Model for Network Analysis

Abstract

In the analysis of large-scale network data, a fundamental operation is the comparison of observed phenomena to the predictions provided by null models: when we find an interesting structure in a family of real networks, it is important to ask whether this structure is also likely to arise in random networks with similar characteristics to the real ones. A long-standing challenge in network analysis has been the relative scarcity of reasonable null models for networks; arguably the most common such model has been the configuration model, which starts with a graph $G$ and produces a random graph with the same node degrees as $G$. This leads to a very weak form of null model, since fixing the node degrees does not preserve many of the crucial properties of the network, including the structure of its subgraphs. Guided by this challenge, we propose a new family of network null models that operate on the $k$-core decomposition. For a graph $G$, the $k$-core is its maximal subgraph of minimum degree $k$; and the core number of a node $v$ in $G$ is the largest $k$ such that $v$ belongs to the $k$-core of $G$. We provide the first efficient sampling algorithm to solve the following basic combinatorial problem: given a graph $G$, produce a random graph sampled nearly uniformly from among all graphs with the same sequence of core numbers as $G$. This opens the opportunity to compare observed networks $G$ with random graphs that exhibit the same core numbers, a comparison that preserves aspects of the structure of $G$ that are not captured by more local measures like the degree sequence. We illustrate the power of this core-based null model on some fundamental tasks in network analysis, including the enumeration of networks motifs.

References in corpus (15)

• Random graphs with arbitrary degree distributions and their applications
• Mixing patterns in networks
• New Model of Internet Topology Using k-shell Decomposition
• MEDUSA - New Model of Internet Topology Using k-shell Decomposition
• k-core organization of complex networks
• The ground truth about metadata and community detection in networks
• Temporal motifs in time-dependent networks
• On the uniform generation of random graphs with prescribed degree sequences
• Quantifying randomness in real networks
• Systematic Topology Analysis and Generation Using Degree Correlations
• Construction of and efficient sampling from the simplicial configuration model
• Deciphering the global organization of clustering in real complex networks
• Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition
• Random Graph Modeling: A survey of the concepts
• Percolation on random networks with arbitrary k-core structure

Cited by in corpus (2)

• Scale-Invariant Strength Assortativity of Streaming Butterflies
• Social Graph Restoration via Random Walk Sampling