  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.
