Network science studies complex systems by representing them as networks. This approach has proven quite fruitful because in many cases the network representation achieves a practically useful balance between simplicity and realism: while always grand simpli cations of real systems, networks often encode some crucial information about the system. Represented as a network, the system structure is fully speci ed by the network adjacency matrix, or the list of connections, perhaps enriched with some additional attributes. This list is then a starting point of research in network science.
In the network representation of a system, subgraphs,their frequency and convergence are the most natural and basic building blocks of the system, among other things forming the basis of the rigorous theoryof graph family limits known as graphons [20], while the degree is the most natural and basic property of individual nodes in the network. Combining the subgraph- and degree-based characteristics leads to dk-series.
In dk-series (see figure) properties Yd are dk-distributions. The dk-distribution of a given network G is de ned as the number of G's subgraphs of size d in which the information about node degrees in G is preserved.
Thus de ned the dk-series subsumes all the basic degree-based characteristics of networks. Indeed, the zero-th element of the dk-series, the "0k-distribution," is just the average degree in G. The fi rst element, the 1k-distribution, is the standard degree distribution, which is the number of nodes/subgraphs of size 1 of degree k in the network. The second element, the 2k-distribution, is the joint degree distribution, which the number of subgraphs of size 2-links between nodes of degrees k1 and k2. The 2k-distribution thus de nes 2-node-degree correlations and network's assortativity. For d = 3, the subgraphs are triangles and wedges, composed of nodes of degrees k1, k2, and k3, which de nes clustering, and so on. For arbitrary d the dk-distribution characterizes the `degree `k' correlations in d-sized subgraphs, thus including, on the one hand, the correlations of degrees of nodes located at hop distances below d, and, on the other hand, the statistics of d-cliques in G.
The dk-series is inclusive because the (d + 1)k- distribution contains the same information about the network as the dk-distribution, plus some additional information. In the simplest d = 0 case for example, the degree distribution P(k) (1k-distribution) de notes the average degree k (0k-distribution) via
<k>.
The dk-series illustrated. Panel (a) shows the dk-distributions for a graph of size 4. The 4k-distribution is the graph itself. The 3k-distribution consists of its three subgraphs of size 3: one triangle connecting nodes of degrees 2, 2, and 3, and two wedges connecting nodes of degrees 2, 3, and 1. The 2k-distribution is the joint degree distribution in the graph. It speci es the number of links (subgraphs of size 2) connecting nodes of di erent degrees: one link connects nodes of degrees 2 and 2, two links connect nodes of degrees 2 and 3, and one link connects nodes of degree 3 and 1. The 1k-distribution is the degree distribution in the graph. It lists the number of nodes (subgraphs of size 1) of di erent degree: one node of degree 1, two nodes of degree 2, and one node of degree 3. The 0k-distribution is just the average degree in the graph, which is 2. Panel (b) illustrates the inclusiveness and convergence of dk-series by showing the hierarchy of dk-graphs, which are graphs that have the same dk-distribution as a given graph G of size n. The
black circles schematically shows the sets of dk-graphs. The set of 0k-graphs, i.e., graphs that have the same average degree as G, is largest. Graphs in this set may have a structure drastically di erent from G's. The set of 1k-graphs is a subset of 0k-graphs, because each graph with the same degree distribution as in G has also the same average degree as G, but not vice versa. As a consequence, typical 1k-graphs, i.e., 1k-random graphs, are more similar to G than 0k-graphs. The set of 2k-graphs is a subset of 1k-graphs, also containing G. As d increases, the circles become smaller because the number of di erent dk-graphs decreases. Since all the dk-graph sets contain G, the circles \zoom-in" on it, and while their number decreases, dk-graphs become increasingly more similar to G. In the d = n limit, the set of nk-graphs consists of only one element, G itself.
