Topology reveals universal features for
network comparison

arXiv:1705.05677v1 [stat.ME] 16 May 2017

Pierre-André G. Maugis, Sofia C. Olhede & Patrick J. Wolfe
University College London
Abstract
The topology of any complex system is key to understanding its structure
and function. Fundamentally, algebraic topology guarantees that any system
represented by a network can be understood through its closed paths. The
length of each path provides a notion of scale, which is vitally important
in characterizing dominant modes of system behavior. Here, by combining
topology with scale, we prove the existence of universal features which reveal
the dominant scales of any network. We use these features to compare several
canonical network types in the context of a social media discussion which
evolves through the sharing of rumors, leaks and other news. Our analysis
enables for the first time a universal understanding of the balance between
loops and tree-like structure across network scales, and an assessment of how
this balance interacts with the spreading of information online. Crucially, our
results allow networks to be quantified and compared in a purely model-free
way that is theoretically sound, fully automated, and inherently scalable.

Across the sciences, complex physical and biological systems are represented
by networks 1 . A fundamental challenge is to understand the structure of such
networks, and to compare them irrespective of their sizes and origins 2–5 . Closed
paths in a network (Fig. 1) are crucial to this understanding. They determine
the topology of any network through its mathematical symmetries 6 , and hence
its behavior as a dynamical system 7 . The shapes of these paths capture the full
range of scales intrinsic to any network: from local features reflecting small-scale
properties at the level of individual nodes, to global features revealing large-scale
aspects of system behavior such as diffusion and information flows 8 .
Shapes that are over-represented, termed motifs, play a key functional role in
networks 9–13 . They are equally fundamental to mathematical representations: In
the theory of large graph limits which has emerged over the past decade, motif densities correspond directly to moments of probability distributions 14–18 . However,
the question of precisely which shapes are essential to a unified understanding of
all networks has long remained open 19–22 . Here we show that the simplest shapes
1

Figure 1 | Closed walks at all scales in a network determine its topology. A
closed walk at scale k traces out a closed path, starting at a given node (here, the
center node, shown in black) and taking k steps to return to its origin. Highlighted
are walks at scales k = 3 (green), 6 (blue), and 8 (red), along with all possible closed
paths at each scale. Formally, all walks across all scales determine the fundamental
group of any connected network, and hence its classification as a topological space.
are uniquely essential: They reveal the dominant scales of any network. This discovery allows us to identify structural differences between networks in an entirely
model-free way, and to pinpoint exactly the scales at which these differences occur.
Figure 1 describes how walks traveling from node to node in a network determine its classification as a topological space. A closed walk has two essential
characteristics: its scale, which is the number of steps it takes before returning to
its starting node (Fig. 1, center); and its shape, which describes the closed path
it traces out (Fig. 1, periphery). By combining topology with scale, we prove a
fundamental result: Walks with the simplest shapes will predominate. This holds
universally across a vast range of network types 23–31 . As a consequence, we can
understand and articulate structural differences between networks obtained under
different experimental conditions or at different times.
2

Walks in a network govern not only its topology, but also its spectrum. This
is crucial when networks represent complex physical systems: Spectral properties
determine how phenomena diffuse and spread over networks, with walks describing propagation from node to node 32 . We prove that dominating walks exhibit a
sharp phase transition, changing from cycles to trees as networks becomes sparse.
By contrast, we show that non-backtracking walks 33 —which never traverse the
same network edge twice in succession, and thus form geodesics analogous to
those on a Riemann surface—are impervious to this phase transition. This is a
fundamental robustness result, which has broad implications for our understanding
of network dynamics 34,35 and control 36–38 . It reveals why techniques based on
the Perron–Frobenius operator, represented by the non-backtracking matrix of a
network 39 , have revolutionized algorithms for network community detection 40–42 .

Topology reveals dominant network features
Surprisingly, there is a natural progression to the shapes traced out by walks in a
network. Figure 1 shows how these shapes grow in complexity as scale increases.
Why then are the simplest shapes guaranteed to dominate all others? There are two
crucial reasons: one stemming from topology, the other from scale.
First, trees and cycles have the simplest topologies of all connected networks.
Their Euler characteristics as one-dimensional simplicial complexes—the differences between their numbers of nodes and edges—are as large as possible. Viewing
a connected network as a topological surface, one minus its Euler characteristic
counts its one-dimensional holes (its first Betti number; Fig. 2). Starting from any
tree that spans the entire network, each hole is formed by one network edge outside
this spanning tree, which completes a distinct cycle within the network.
Second, because of their fixed Euler characteristics, trees and cycles naturally
organize themselves by scale. Cycles maximize the number of nodes that can be
visited by a closed walk at any given scale, whereas trees minimize the number of
distinct edges that must be traversed. Scale then combines with topology to ensure
that trees and cycles predominate.
To see how topology reveals dominant network features, we begin with the simplest setting. Let G be a generalized random graph 29 , with P{edge in G} the probability that two randomly chosen nodes are connected, and call E #{copies of w in G}
the average number of walks in G tracing out the same shape as a walk w.
Then, as the number of nodes in G becomes large, the following simple and

3

6
3

6

10

1

81

5

4

3
2
4

2

3
12

5

6

3

4

8
3

9

2
5

6

1
5

4

2
5

7

1

7

2
7

4

Figure 2 | Repeatedly extending a walk simplifies its topology. Any closed walk
extends to either a tree or a cycle. Here the walk 1-2-1-3-2-4-1-2-5-1 extends fully
in four steps: Each extension adds one node to the shape traced out (1613241251,
1613247251, 1683247251, 1683247951) and can only reduce its first Betti number.
fundamental equation governs E #{copies of w in G}:
log E #{copies of w in G} ∼ constw
+ #{nodes visited by w} · log #{nodes in G}
− #{edges traversed by w} · |log P{edge in G}|. (1)
Equation (1) shows how E #{copies of w in G} depends on the shape traced
out by w, revealing a fundamental trade-off between its nodes and edges. This
determines which walks dominate at any given scale: As long as P{edge in G} >
1/#{nodes in G}, a walk that traverses an edge three times can never be dominant.
This is because the right-hand side of equation (1) could then be increased by
visiting a new node instead—even at the cost of traversing an additional edge.
Figure 2 shows how extending a walk in this manner simplifies its topology.
Specifically, call w0 an extension of w if both walks are at the same scale, but
the sequences of nodes they visit differ at exactly one entry, with w0 visiting one
additional node and traversing at most one additional edge. The key topological
property of an extension is that its shape cannot have a more negative Euler characteristic than that traced out by w. Consequently, repeated extensions lead to cycles
or trees (Supplementary Information, section 3.1). Walks tracing out these shapes
are fully extended: either they traverse all their edges once, or all their edges twice.
4

Prevalence and local variability

a
b

...

Scale 2k

c

log P{edge in G} / log #{nodes in G}
Figure 3 | Combining topology with scale enables network comparison. a, Extending a tadpole graph
leads to dominant walks: those traversing their edges
either once (cycles, purple) or twice (trees, orange). b, Consequently, measuring
the prevalence and local variability of trees and cycles across any network reveals
its dominant scales. c, A phase transition (Corollary 1) determines whether cycles
or trees dominate the structure of a graph G at a given scale, based on the number
of nodes in G and the probability that two randomly chosen nodes are connected.

Universal features for network comparison
Figure 3 shows how combining topology with scale yields universal features for
network comparison. To prove that walks tracing out trees and cycles dominate,
we recast equation (1) to hold for any network generating mechanism M :
log E #{copies of w in G} ∼ constw,M

+ #{nodes visited by w} · log #{nodes in G}
− |log PM {local copy of w in G}|.
(2)

Equation (2) replaces #{edges traversed by w} · |log P{edge in G}| in equa5

tion (1), which drove our earlier argument for walk dominance, with a more general
quantity |log PM {local copy of w in G}|, which captures local structure in G.
To define PM {local copy of w in G}, let G[u] be the graph G restricted to any
set of its nodes u, and K[u] the graph on u with all edges present. Consider a walk w
and a graph G generated via mechanism M . If we now let u be chosen at random
from all subsets of nodes of G of any fixed size, we may define
PM {local copy of w in G} =

E #{copies of w in G[u]}
.
#{copies of w in K[u]}

Here #{copies of w in K[u]} is the number of walks on the nodes of u tracing out
the same shape as w, while E #{copies of w in G[u]} is the number of such walks
present in a random subgraph G[u] on average.
Thus, PM {local copy of w in G} is the probability that a randomly selected
walk local to u is present in G[u]. The behavior of PM {local copy of w in G} when
w is extended to visit a single additional node drives our main result.
Theorem 1. Suppose for every closed walk w at scale k which is not fully extended,
there exists an extension w0 such that under network generating mechanism M ,
#{nodes in G} ·

PM {local copy of w0 in G}
→ ∞.
PM {local copy of w in G}

(3)

Then in networks generated by M , closed walks tracing out cycles on k nodes—
and also, if k is even, trees on k/2+1 nodes—dominate all closed walks at scale k:
E #{closed k-walks in G} ∼ E #{closed k-walks tracing out a k-cycle in G}
+ 1{k even} · E #{closed k-walks tracing out any (k/2 + 1)-tree in G}.
Theorem 1 (proved in the Supplementary Information) shows in greatest generality when walks tracing out trees and cycles will dominate all walks in a network.
Equation (3) is a universal requirement for walks to extend fully. For it to hold
in the setting of generalized random graphs, network degrees must grow. This in
turn implies the emergence of a giant component 26 , and so Theorem 1 links global
network structure to local walk properties.
Theorem 1 also leads to simple explicit forms for E #{copies of w in G}, depending on whether all network degrees grow uniformly 23,24,27,30 (Supplementary
Information, Proposition S.1), or at variable rates, as in a power-law network 25
with hubs and scale-free structure 43 (Supplementary Information, Proposition S.2).
6

This result points to a fundamental dichotomy: When networks are sufficiently
homogeneous that equation (1) applies, all trees are equally important, regardless of their degree sequence. But when networks are more heterogeneous and
equation (2) applies, as in the case of a power law, trees containing hubs dominate (Supplementary Information, Theorem S.4). In both cases a universal phase
transition regulates walk dominance.
Corollary 1. Consider the setting of generalized random graphs whose mechanism
M is either a bounded kernel or a power law. If network degrees grow fast enough,
then dominant closed walks exhibit the sharp phase transition shown in Fig. 3c:
E #{closed k-walks in G} ∼
(
E #{closed k-walks tracing out a k-cycle in G}
if k is odd or k > k∗,
E #{closed k-walks tracing out (k/2 + 1)-trees in G} otherwise.
The boundary between dominating regimes of trees and cycles occurs at
p
k∗ = log #{nodes in G}/log #{nodes in G} · P{edge in G}.

By contrast, dominant non-backtracking walks always trace out cycles:
E #{non-backtracking closed k-walks in G} ∼
E #{closed k-walks tracing out a k-cycle in G}.

Corollary 1 reveals a sudden shift in dominating regimes between trees and
cycles, driven entirely by P{edge in G}. This shift is scale-dependent and simple
to describe: the sparser the network, the more scales are dominated by trees. Fluctuations near the boundary k∗ , and the emergence of a regime dominated by star
trees when degrees grow slowly, can be quantified precisely (Supplementary Information, sections 5 and 6). Non-backtracking walks, by contrast, are robust to this
phase transition: They cannot backtrack and traverse the same network edge twice
in succession, and so cannot trace out shapes containing trees. Instead, Corollary 1
shows that non-backtracking walks are dominated by walks tracing out cycles.
Corollary 1 also quantifies the behavior of a network’s adjacency matrix A
relative to its non-backtracking matrix B. While A tabulates all paths of length
one, B tabulates all non-backtracking paths of length two. It follows in turn that
E λAk = E #{closed k-walks in G}, where E λAk is the average value of an eigenvalue
of A chosen at random, while E λBk = E #{non-backtracking closed k-walks in G}.
Corollary 1 pinpoints how λA shifts regimes as G becomes sparser, whereas λB
remains stable, effectively decoupling from P{edge in G}. This stability explains
why B rather than A governs the fundamental limits of network community detection 40–42 , and suggests that its optimality properties may hold much more widely.
7

Figure 4 | Comparing networks and their dominant scales. a, The C. elegans
metabolic network is dominated by tree-like structure characteristic of preferential attachment, which manifests at the smallest scale (cf. Fig. S3a). b, A power
grid network, by contrast, exhibits small-world connectivity (cf. Fig. S3b), and is
dominated by medium-range scales. c, A network of political weblogs has strong
community structure (cf. Fig. S3c), but surprisingly shows relatively uniform contributions from all scales. d, A random graph with triadic closure ( → ) shows
a single elevated scale. e, Adolescent friendship networks evolve across school
grades, maintaining triadic closure despite changes in connectivity (see main text).

Dominant scales in static and dynamic networks
Trees and cycles reveal a network’s dominant scales, thereby establishing a theoretical basis for network comparison. To implement this comparison, we sample
sub-networks at random and count the normalized proportions of trees and cycles
present (Supplementary Information, Algorithm 1). We characterize the distributions of these proportions using violin plots 44 (Figs. 3b and 4), to isolate and
quantify the heterogeneity of network structure locally at each scale. We determine the necessary size of sub-networks to sample by iteratively adapting to the
network under study (Supplementary Information, Algorithm 2).
Figure 4 shows a comparative analysis of networks with archetypical features:
preferential attachment characteristics 43 , small-world connectivity 45 , community
structure 46 , triadic closure ( → ) 47 , and assortative mixing 48 . Our analysis
8

Figure 5 | Evolution of dominant scales in an online discussion network. A
social media (Twitter) discussion about the release of a new consumer product
(iPhone 6 mobile device) begins early in April 2014 as rumors and leaks of the
new product are shared. The dynamics of this discussion manifest in time-localized
networks (top row), where edges form whenever two users broadcast similar messages within a 4-day window, as well as an aggregate network (middle and bottom
rows), where edges form whenever two users refer to the same online news article.
highlights the fundamental differences in network structure reflected by these features, distinct from differences in network size and sparsity. Not only can we detect
and visualize these structural differences in the context of network comparison,
but also we can identify changes in networks at the level of their individual scales.
To this end, Figure 4e compares adolescent friendship networks across different years (grades) in school. Among high school students (grades 9–12), overall
connectivity levels—known in this context as sociality 49 —increase with grade.
Yet at the same time, dominant scales persist across grades, even in the transition
from middle school (grades 7–8) to high school. These dominant scales reveal a
strong triadic closure effect (cf. Fig. 4d). Previous studies have shown that the
aggregate friendship network across grades shows evidence of selective mixing 49 ,
with a complex community structure based in part on gender, race, and grade 31 .
Despite this complexity, we see that scale-based structure in this setting persists
and appears robust to the many social changes taking place in adolescence.
Figure 5 shows the rich temporal dynamics of an evolving social media discussion, revealed through the archetypical features of Fig. 4. Initially, the corre9

sponding discussion network is simply structured and shows relatively uniform
contributions across scales (Figs. 5a and 5b; cf. Fig. 4c). As rumors of a new product and its manufacturer dominate the discussion, a large clique forms and connects
to several smaller, nearly disjoint clusters of users. This clique breaks apart after
April 15, when leaked product images appear online and are shared across the
network (Supplementary Information, section 8). In response, the network converges rapidly to small-world connectivity (Figs. 5c and 5f; cf. Fig. 4b)—known
to circulate information efficiently 50 —as its first, tree-like scale deprecates.
As the discussion shown in Fig. 5 progresses, we continue to recognize canonical signatures of fundamental network generating mechanisms. A rapid burst of
network activity follows the manufacturer’s earnings report, released on April 23.
This manifests as a sharp elevation of the first, tree-like network scale indicative
of preferential attachment (Fig. 5d; cf. Fig. 4a), along with increases in local and
global efficiency 50 relative to random and lattice graphs 45 . Star-like nodes appear
suddenly and dominate the network structure, then gradually recede as the network
consolidates (Fig. 5e), adding triangles and higher-order cycles to reflect smallworld connectivity properties. Overall, as the discussion network evolves through a
combination of growth and structural changes, the dynamics of its dominant scales
enable us to identify and describe different developmental phases in its life cycle.

Discussion
Here we have shown how algebraic topology leads naturally to a set of universal
features for network comparison. These features provide the first theoretically justified, automated, and scalable means to compare networks in a model-free way.
Critical to our discovery is Theorem 1, which shows that under very weak assumptions, certain shapes—trees and cycles—dominate at every network scale. These
shapes and scales arise from properties of non-backtracking closed walks, answering longstanding open questions in the field of network motif analysis 17,19–22 .
The need to characterize and compare networks is fundamental to many fields,
from the physical and life sciences to the social, behavioral, and economic sciences. This need is currently particularly significant in understanding information
cascades and spreading online. From sharing trees 51 to the role of cycles in the
strength of weak ties 47 , social networks modulate the diffusion of information
and influence. At the same time, advances in machine learning and artificial intelligence mean that the spread of contemporary news is strongly influenced by
the uniquely personalized online social context of each individual in a network 52 .
10

Consequently, understanding how structural network properties interact with the
dynamics of spreading processes is a more timely and important problem now than
ever before.
To this end, we have shown, through a comparative analysis of several rich and
varied examples, how our discovery enables new insights into the structure and
function of of static and dynamic networks. Our approach is sufficiently flexible
to permit the comparison of networks with different numbers of nodes and edges,
enabling scientists to extract common patterns and signatures from a variety of
canonical network types. Surprisingly, we observe that these same signatures appear in the analysis of a social media discussion which evolves through the sharing
of rumors, leaks and other types of news. This allows us to observe and quantify, in
a way never before possible, the direct and strong symbiosis between the dynamics
of an evolving network and the ways in which information spreads within it. The
discoveries we report are a crucial first step in disentangling the features that make
networks similar or different from those that facilitate the diffusion of information.

References
[1] Gao, J., Barzel, B. & Barabási, A.-L. Universal resilience patterns in complex
networks. Nature 530, 307–312 (2016).
[2] Ingalhalikar, M. et al. Sex differences in the structural connectome of the
human brain. Proc. Natl. Acad. Sci. USA 111, 823–828 (2014).
[3] Meda, S. A. et al. Multivariate analysis reveals genetic associations of the
resting default mode network in psychotic bipolar disorder and schizophrenia.
Proc. Natl. Acad. Sci. USA 111, E2066–E2075 (2014).
[4] Hudson, A., Calderon, D. P., Pfaff, D. W. & Proekt, A. Recovery of consciousness is mediated by a network of discrete metastable activity states.
Proc. Natl. Acad. Sci. USA 111, 9283–9288 (2014).
[5] Schieber, T. A. et al. Quantification of network structural dissimilarities. Nat.
Commun. 8, 13928 (2017).
[6] Stallings, J. R. Topology of finite graphs. Invent. Math. 71, 551–565 (1983).
[7] Kotani, M. & Sunada, T. Zeta functions of finite graphs. J. Math. Sci. Univ.
Tokyo 7, 7–25 (2000).
11

[8] Brockmann, D. & Helbing, D. The hidden geometry of complex, networkdriven contagion phenomena. Science 342, 1337–1342 (2013).
[9] Milo, R. et al. Network motifs: Simple building blocks of complex networks.
Science 298, 824–827 (2002).
[10] Maáyan, A. et al. Ordered cyclic motifs contribute to dynamic stability in
biological and engineered networks. Proc. Natl. Acad. Sci. USA 105, 19235–
19240 (2008).
[11] Angulo, M. T., Liu, Y.-Y. & Slotine, J.-J. Network motifs emerge from interconnections that favour stability. Nature Phys. 11, 848–852 (2015).
[12] Sorrells, T. R. & Johnson, A. D. Making sense of transcription networks.
Cell 161, 714–723 (2015).
[13] Benson, A. R., Gleich, D. F. & Leskovec, J. Higher-order organization of
complex networks. Science 353, 163–166 (2016).
[14] Janson, S. Random regular graphs: asymptotic distributions and contiguity.
Combin. Probab. Comput. 4, 369–405 (1995).
[15] Diaconis, P. & Janson, S. Graph limits and exchangeable random graphs.
Rend. Mat. Appl. 28, 33–61 (2008).
[16] Bollobás, B. & Riordan, O. Metrics for sparse graphs. In Surveys in Combinatorics 2009 (eds. Huczynska, S., Mitchell, J. D. & Roney-Dougal, C. M.),
211–287 (Cambridge Univ. Press, Cambridge, 2009).
[17] Bickel, P. J., Chen, A. & Levina, E. The method of moments and degree
distributions for network models. Ann. Statist. 39, 2280–2301 (2012).
[18] Lovász, L. Large Networks and Graph Limits (Amer. Math. Soc., Providence,
RI, 2012).
[19] Milo, R. et al. Superfamilies of evolved and designed networks. Science 303,
1538–1542 (2004).
[20] Alon, U. Network motifs: Theory and experimental approaches. Nature Rev.
Genet. 8, 450–461 (2007).

12

[21] Gerstein, M. B. et al. Architecture of the human regulatory network derived
from ENCODE data. Nature 489, 91–100 (2012).
[22] Boyle, A. P. et al. Comparative analysis of regulatory information and circuits
across distant species. Nature 512, 453–456 (2014).
[23] Holland, P. W., Laskey, K. B. & Leinhardt, S. Stochastic blockmodels: First
steps. Soc. Netw. 5, 109–137 (1983).
[24] Hoff, P. D., Raftery, A. E. & Handcock, M. S. Latent space approaches to
social network analysis. J. Amer. Statist. Assoc. 97, 1090–1098 (2002).
[25] Chung, F. R. K., Lu, L. & Vu, V. Spectra of random graphs with given
expected degrees. Proc. Natl. Acad. Sci. USA 100, 6313–6318 (2003).
[26] Bollobás, B., Janson, S. & Riordan, O. The phase transition in inhomogeneous random graphs. Random Structures Algorithms 31, 3–122 (2007).
[27] Airoldi, E. M., Blei, D. M., Fienberg, S. E. & Xing, E. P. Mixed membership
stochastic blockmodels. J. Mach. Learn. Res. 9, 1981–2014 (2008).
[28] Bickel, P. J. & Chen, A. A nonparametric view of network models and
Newman–Girvan and other modularities. Proc. Natl. Acad. Sci. USA 106,
21068–21073 (2009).
[29] Riordan, O. & Warnke, L. Explosive percolation is continuous. Science 333,
322–324 (2011).
[30] Zhao, Y., Levina, E. & Zhu, J. Consistency of community detection in networks under degree-corrected stochastic block models. Ann. Statist. 40, 2266–
2292 (2012).
[31] Olhede, S. C. & Wolfe, P. J. Network histograms and universality of blockmodel approximation. Proc. Natl. Acad. Sci. USA 111, 14722–14727 (2014).
[32] Morone, F. & Makse, H. A. Influence maximization in complex networks
through optimal percolation. Nature 524, 65–68 (2015).
[33] Angel, O., Friedman, J. & Hoory, S. The non-backtracking spectrum of the
universal cover of a graph. Trans. Amer. Math. Soc. 367, 4287–4318 (2015).

13

[34] Luscombe, N. M. et al. Genomic analysis of regulatory network dynamics
reveals large topological changes. Nature 431, 308–312 (2004).
[35] Barzel, B. & Barabási, A.-L. Universality in network dynamics. Nature Phys.
9, 673–681 (2013).
[36] Liu, Y.-Y., Slotine, J.-J. & Barabási, A.-L. Controllability of complex networks. Nature 473, 167–173 (2011).
[37] Ruths, J. & Ruths, D. Control profiles of complex networks. Science 343,
1373–1376 (2014).
[38] Yan, G. et al. Spectrum of controlling and observing complex networks.
Nature Phys. 11, 779–786 (2015).
[39] Fitzner, R. & van der Hofstad, R. Non-backtracking random walk. J. Stat.
Phys. 150, 264–284 (2013).
[40] Ahn, Y.-Y., Bagrow, J. P. & Lehmann, S. Link communities reveal multiscale
complexity in networks. Nature 466, 761–764 (2010).
[41] Krzakala, F. et al. Spectral redemption in clustering sparse networks. Proc.
Natl. Acad. Sci. USA 110, 20935–20940 (2013).
[42] Karrer, B., Newman, M. E. J. & Zdeborová, L. Percolation on sparse networks. Phys. Rev. Lett. 113, 208702 (2014).
[43] Barabási, A.-L. & Albert, R. Emergence of scaling in random networks.
Science 286, 509–512 (1999).
[44] Hintze, J. L. & Nelson, R. D. Violin plots: A box plot-density trace synergism.
Amer. Statist. 52, 181–184 (1998).
[45] Watts, D. J. & Strogatz, S. H. Collective dynamics of “small-world” networks.
Nature 393, 440–442 (1998).
[46] Adamic, L. A. & Glance, N. The political blogosphere and the 2004 US election: Divided they blog. In Proceedings of the 3rd International Workshop
on Link Discovery, 36–43 (ACM, New York, 2005).
[47] Granovetter, M. S. The strength of weak ties. Amer. J. Sociol. 78, 1360–1380
(1973).
14

[48] Resnick, M. D. et al. Protecting adolescents from harm: Findings from the
National Longitudinal Study on Adolescent Health. J. Amer. Med. Assoc.
278, 823–832 (1997).
[49] Goodreau, S., Kitts, J. A. & Morris, M. Birds of a feather, or friend of a
friend? Using exponential random graph models to investigate adolescent
social networks. Demography 46, 103–125 (2009).
[50] Latora, V. & Marchiori, M. Efficient behavior of small-world networks. Phys.
Rev. Lett. 87, 198701 (2001).
[51] Del Vicario, M. et al. The spreading of misinformation online. Proc. Natl.
Acad. Sci. USA 113, 554–559 (2016).
[52] Bakshy, E., Messing, S. & Adamic, L. A. Exposure to ideologically diverse
news and opinion on Facebook. Science 348, 1130–1132 (2015).
Supplementary Information begins on the following page.
Acknowledgements This work was supported in part by the US Army Research Office under Multidisciplinary University Research Initiative Award 58153MA-MUR; by the US Office of Naval Research under Award N00014-14-1-0819;
by the UK Engineering and Physical Sciences Research Council under Mathematical Sciences Leadership Fellowship EP/I005250/1, Established Career Fellowship EP/K005413/1, Developing Leaders Award EP/L001519/1, and Award
EP/N007336/1; by the UK Royal Society under a Wolfson Research Merit Award;
and by Marie Curie FP7 Integration Grant PCIG12-GA-2012-334622 and the European Research Council under Grant CoG 2015-682172NETS, both within the
Seventh European Union Framework Program. The authors thank FSwire for making available the data used to produce Figs. 3b and 5. This work was partially
supported by a grant from the Simons Foundation, and the authors simultaneously
acknowledge the Isaac Newton Institute for Mathematical Sciences, Cambridge,
UK, for support and hospitality during the program Theoretical Foundations for
Statistical Network Analysis (Supported by EPSRC award EP/K032208/1) where
a portion of the work on this article was undertaken.
Author Contributions All authors contributed to all aspects of the paper.
Author Information The authors declare no competing financial interests.
Correspondence should be addressed to P.J.W. (p.wolfe@ucl.ac.uk).

15

Supplementary Information:
Topology reveals universal features for
network comparison
Pierre-André G. Maugis, Sofia C. Olhede & Patrick J. Wolfe
University College London

Contents
1

Introduction

17

2

Preliminaries
2.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Counting closed walks . . . . . . . . . . . . . . . . . . . . . . .

21
21
22

3

Closed walks and extensions
26
3.1 Extensions and a partial order on walk-induced subgraphs . . . . . 26
3.2 Counting walks that induce isomorphic copies of subgraphs . . . . 34

4

Determining dominating closed walks
38
4.1 Defining asymptotically dominating walks . . . . . . . . . . . . . 38
4.2 Conditions when walks inducing trees and cycles dominate . . . . 42
4.3 Dominance of walks mapping out trees and cycles . . . . . . . . . 42

5 Dominating walks in kernel-based random graphs
5.1 Kernel-based random graphs . . . . . . . . . . . . . . .
5.2 Dominating closed walks in kernel-based random graphs
5.3 Expected number of walks mapping out trees and cycles
5.4 Domination of walks mapping out cycles . . . . . . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

45
45
47
51
56

6

Dominating walks in scale-free random graphs
62
6.1 Scale-free inhomogeneous random graphs . . . . . . . . . . . . . 62
6.2 Dominating closed walks in scale-free random graphs . . . . . . . 73

7

Methods and algorithms
7.1 Algorithm 1: Subsampling to summarize trees and cycles . . . . .
7.2 Algorithm 2: Selecting network sizes for subsampling . . . . . . .

8

Network datasets
84
8.1 Networks analyzed in Fig. 4 of the main text . . . . . . . . . . . . 84
8.2 Networks analyzed in Fig. 5 of the main text . . . . . . . . . . . . 86

9

Additional references

81
81
84

90
16

1

Introduction

In this Supplementary Information we provide proofs of all results from the main
text, along with details of the corresponding methods, algorithms, and datasets. It
is written as a self-contained document, with the remainder of this introductory
section relating the results and notation featured here to the main text.
A key driver of our proofs comes via the introduction of a walk extension,
which in turn permits us to compare the prevalence of any two walks of the same
length (Fig. 1, main text). We define as “simplest” precisely those walks that cannot be extended any further (Fig. 2, main text). We then show that the simplest
walks dominate other walks in terms of their expected prevalence. By the argument
of Fig. 3 in the main text, the simplest closed walks turn out to be those mapping
out either trees or cycles at maximal scales. Together these results lead to Theorem 1 in the main text, and are obtained in two steps. First, after providing basic
definitions in Section 2 of this Supplemental Information, we introduce the general
framework and necessary preliminary results in Section 3. Then, in Section 4, we
prove that under suitable conditions, the total number of closed walks in a network
is dominated in expectation by walks inducing trees or cycles.
We then show additional results which apply if we assume more about the
network of interest, leading to Corollary 1 in the main text. In Sections 5 and 6
of this Supplemental Information, we consider the setting of generalized random
graphs [1], generated either from a bounded kernel or from an unbounded kernel
giving rise to a power-law degree distribution. Applying Theorem 1 in these settings leads to the following two propositions, which hold respectively for the two
large families of graphs described by Definitions S.8 and S.17 in Sections 5 and 6.
Proposition S.1. Let {G} be a sequence of generalized random graphs generated from a bounded, symmetric kernel κ : (0, 1)2 → [0, ∞), with kκk1 = 1 and
#{nodes in G} → ∞. Assume edges in G form independently, conditionally upon
a random sample ξ of Uniform(0, 1) variates, and that there exists a sequence
{P{edge in G}} taking values in (0, kκk−1
∞ ) such that
P{edge connecting nodes i and j in G | ξ } = P{edge in G} · κ(ξi , ξ j ).
Then for any closed k-walk w, we recover equation (1), with
log P{local copy of w in G} = const
− #{edges traversed by w} · | log P{edge in G}|,
and if #{nodes in G} · P{edge in G} → ∞, then Theorem 1 applies.
17

Proposition S.2. Let {G} be a sequence of inhomogeneous random graphs generated from a rank one kernel yielding power-law degrees, with #{nodes in G} → ∞.
Specifically, assume that edges in G form independently, and that there exists a
constant γ ∈ (0, 1) and a monotone sequence {θ } taking values in (0, 1] such that
P{edge connecting nodes i and j in G} = θ 2 · (i j)−γ .

Then P{edge in G} ∼ (1 − γ)−2 θ 2 · #{nodes in G}−2γ , and if the average degree
tends to infinity faster than #{nodes in G}γ , then Theorem 1 applies, whence for
degrees d1 , . . . , dv of the shape traced out by any closed k-walk w,
v
log P{local copy of w in G} ∼ −∑t=1
min(1, dt γ) · log #{nodes in G}
− #{edges traversed by w} · | log θ 2 |. (S.1)

To prove these propositions, as well as Corollary 1 in the main text, we proceed
as follows. In Section 5, we prove for kernel-based random graphs (also known as
inhomogeneous or generalized random graphs) that closed walks are dominated
in expectation by walks inducing either trees or cycles, with a phase transition
between the two regimes. We additionally prove that non-backtracking closed
walks are dominated in expectation by walks inducing cycles. We derive error
rates, making these results more precise than the general results of Section 4,
which are based only on an assumption about how walk extensions scale. Next,
we show in Section 6 that for inhomogeneous random graphs with a power-law
degree distribution, closed walks are again dominated in expectation by walks
inducing either trees or cycles when Theorem 1 applies, and that non-backtracking
closed walks are again dominated by those inducing cycles. This provides a set
of developments parallel to Section 5, and establishes the above propositions as
well as Corollary 1 in the main text. We also establish dominant walks outside the
setting of Theorem 1, showing when stars and star-like graphs containing cycles
will dominate. Finally, in Section 7 we detail the methods and algorithms we
develop to make use of these results, and in Section 8 we provide details of the
network datasets we analyze in the main text.
To facilitate mapping results from the main text to the notation of this Supplementary Information, we detail the following relationship.
Definitions of walk densities and extensions The term introduced in the main
text as PM {local copy of w in G} corresponds to the graph walk density of
Definition S.5. The main text definition of a walk extension corresponds to
Definition S.3. We give the basic properties of the graph walk density and
of walk extensions in Lemma S.4 and in Remark S.3.
18

Theorem 1 We prove Theorem 1 in Section 4 as Theorem S.1. Proving the theorem requires Proposition S.3 from Section 4 and Lemma S.2 from Section 3.
The proof is made under Assumptions S.1 and S.2. The latter assumption is
equivalent to the condition of (3) in the main text.
Proposition S.1 This proposition is a consequence of Remark S.4. We show in
the remark that the conditions of Theorem 1 are satisfied for generalized
random graphs with bounded kernels. This then implies that the proposition
holds for generalized random graphs that are sufficiently dense and arise
from bounded kernels.
Proposition S.2 We prove this proposition in Section 6 as Proposition S.4. The
proof relies on Theorem 1.
Corollary 1, part 1 We prove this result by splitting it into two cases. First, for
the case of generalized random graphs with bounded kernels, we show the
result via Theorem S.2 in Section 5. Its proof relies on Lemmas S.6 and S.7.
Second, for an inhomogeneous random graph with an unbounded but separable kernel, we show the result via Proposition S.4.
Corollary 1, part 2 We also prove this result in two parts. First, for generalized
random graphs with bounded kernels, we establish the result via Theorem S.3
in Section 5. Its proof requires Lemma S.9. Second, for an inhomogeneous
random graph with an unbounded but separable kernel, we show the result
as above via Proposition S.4.
Methods and algorithms The methods and algorithms we use for all data analysis in the main text are described in Section 7.
Network datasets The datasets we study are described in Section 8.
Finally, Table S1 overleaf shows how the notation in this Supplementary Information maps to the notation we use in the main text.

19

Supplementary notation
Fw
v(Fw )
e(Fw )
n
ρ
µ(1 − n−1 )
Wk (G)
|Wk (G)|

Definition
S.2
S.1
-

Wk

S.2

Ck
indk (Fw , G)
XF (G)
E ϕ(w, G)
κ

S.3
S.4
S.5
S.7

G(n, ρκ)

S.8

|{w ∈ Wk (G) : Fw ≡ Ck }|

-

{w ∈ Wk (G) : Fw ∈ Tk/2+1 }

-

Wkb (G)

S.13

Wkb (G)

-

Set of unlabeled subgraphs
induced by non-backtracking,
tailless closed walks

Wkb

S.14

Number of non-backtracking,
tailless closed k-walks
inducing copy of F

indbk (F, G)

S.15

Main text notation
Shape traced out by walk w
#{nodes visited by w}
#{edges traversed by w}
#{nodes in G}
P{edge in G}
Average network degree
Set of closed k-walks in G
#{closed k-walks in G}
Set of unlabeled subgraphs
induced by closed k-walks
Subgraph extension
#{copies of w in G}
#{copies of F in G}
P{local copy of w in G}
Kernel
Generalized
random graph
#{closed k-walks visiting
a k-cycle in G}
#{closed k-walks visiting
any (k/2 + 1)-tree in G}
Set of non-backtracking
closed k-walks in G
#{non-backtracking closed
k-walks in G}

Table S1 | Notation used in the main text and Supplementary Information

20

2

Preliminaries

2.1

Notation

We begin by providing basic graph-theoretic definitions needed for our analysis.
All graphs throughout are assumed to be finite and simple (unweighted, undirected,
and without self-loops).
1. We write G for a simple graph with vertex set v(G) and edge set e(G). Often
we write n = |v(G)|.
2. We write F ⊂ G if F is a subgraph of G; i.e., v(F) ⊂ v(G) and e(F) ⊂ e(G).
3. We say that two simple graphs G and G0 are isomorphic and write G ≡ G0 if
there exists a bijection Φ : v(G) → v(G0 ) such that pq ∈ e(G) ⇔ Φ(p)Φ(q) ∈
e(G0 ).
4. By a labeled graph, we mean any finite, simple graph G. By an unlabeled
graph, we mean an element of the set of isomorphism classes of finite simple
graphs (or a representative thereof).
5. We write aut(G) for |{Φ ∈ Sym(v(G)) : pq ∈ e(G) ⇔ Φ(p)Φ(q) ∈ e(G)}|,
the order of the automorphism group of G; i.e., the number of adjacencypreserving permutations of v(G).
6. We denote by emb(F, G) for the number of embeddings (injective homomorphisms) of F into G; i.e., the number of labeled copies of F in G.

7. We denote by XF (G) = F 0 ⊂ G : F 0 ≡ F = emb(F, G)/aut(F) the number of subgraphs of G isomorphic to F; i.e., the number of unlabeled or
isomorphic copies of F in G.

8. We denote by Kn the complete graph on n vertices (i.e., with n2 edges).
9. A k-cycle Ck is the cycle graph on k vertices.
10. A k-tree is any tree on k vertices; i.e, any connected graph on k vertices
without cycles, or equivalently with k − 1 edges. We write Tk for the set of
all unlabeled k-trees.

21

11. A k-path Pk is the k-tree containing k −2 vertices of degree two and 2 vertices
of degree one (its endpoint vertices or leaves), for k ≥ 2. For k = 1, P1 = K1
(the singleton graph).
12. A (k, l − 1)-tadpole Ck Pl is the graph obtained by joining Ck to Pl by identifying a single vertex. It is also known in the literature as a balloon graph (and
sometimes even as a dragon, kite, canoe paddle or lollipop graph, though
often the last of these refers instead to a clique joined to a path).
13. A (k, l)-lemniscate CkCl is the graph obtained by joining Ck to Cl by identifying a single vertex. It is also known in the literature as a bouquet or flower
graph.

2.2

Counting closed walks

We begin by grouping closed walks of a given length k according to the subgraphs
they induce. We now introduce the sets Wk (G) and Wk necessary to implement
such a grouping.
Definition S.1 (The set Wk (G) of closed k-walks in a simple graph G). Fix a simple
graph G and k ∈ N. A walk w of length k in G is a sequence of adjacent vertices
in G:
w = v0 v1 · · · vk ,
where ∪ki=0 {vi } ⊂ v(G) and ∪k−1
i=0 {vi vi+1 } ⊂ e(G). If v0 = vk then the walk is
closed. We denote by Wk (G) the set of all closed k-walks in a given graph G and
write |w| for the length of w.

If A(G) is the adjacency matrix of a simple graph G, then |Wk (G)| = Tr(A(G)k )
for any k ∈ N.
Definition S.2 (Walk-induced subgraphs Fw ⊂ G and the set Wk of unlabeled
subgraphs induced by closed k-walks). Fix a simple graph G and a walk w in
G. We call Fw ⊂ G the labeled subgraph of G induced by the edges traversed
by w; i.e., the labeled subgraph with vertex set v(Fw ) = ∪ki=0 {vi } and edge set
e(Fw ) = ∪k−1
i=0 {vi vi+1 }. We denote by Wk the set of all unlabeled graphs induced
by closed walks of length k:
Wk = {F ⊂ Kk : ∃w ∈ Wk (Kk ) s.t. F = Fw }/ ≡ .
22

Thus, for any fixed k, Wk is a subset of the set of isomorphism classes of finite
simple graphs. When enumerating its elements, we will implicitly choose a representative of the corresponding equivalence class for each element, so that we may
treat each F ∈ Wk as an arbitrarily labeled graph.
Lemma S.1 (Properties of Wk ). For every integer k ≥ 2, the set Wk is non-empty
and satisfies the following properties:

1. For each F ∈ Wk , there exists a closed k-walk w = v0 v1 · · · vk−1 v0 in F for
which Fw = F.
2. Every F ∈ Wk is connected.
3. Any F ∈ Wk with |e(F)| < |v(F)| is a tree, and hence in this case |e(F)| =
|v(F)| − 1.
4. If w is a closed k-walk and Fw ∈ Wk is a tree, then every edge in Fw is
traversed at least twice by w.
5. Any tree T ∈ Wk has |e(T )| = |v(T )| − 1 ≤ k/2.
6. It holds that Wk ⊂ Wk+2 .
7. If k is odd, then Wk contains no trees. If k is even, then Wk contains all
unlabeled trees on 2 to k/2 + 1 vertices.
8. The k-cycle Ck is an element of Wk for all k ≥ 3, and is the only element of
Wk on k vertices.
9. The (k − 2, 1)-tadpole Ck−2 P2 is an element of Wk for all k ≥ 5, and is the
only element of Wk that is both on k − 1 vertices and with k − 1 edges.

Proof. We shall prove all items in order, using results from each part in turn.
Items 7 and 8, once proved, imply that Wk is non-empty for every integer k ≥ 2.
Proof of 1: Fix F ∈ Wk , recalling that we treat F as an arbitrarily labeled graph.
From Definition S.2, there exists F 0 ⊂ Kk such that: i) F 0 ≡ F; and ii) there exists
w0 ∈ Wk (Kk ) such that Fw0 = F 0 . We call φ the adjacency preserving bijection from
the vertex set of F 0 to the vertex set of F. Then, we write w0 = v0 v1 · · · vk , where
v0 = vk , and define the walk w as w = φ (v0 )φ (v1 ) · · · φ (vk ). Finally, we observe
that w ∈ Wk (F) and by construction,
Fw = ({φ (vt )}0≤t≤k , {φ (vt )φ (vt+1 )}0≤t<k )
23

= ({φ (x)}x∈v(F 0 ) , {φ (x)φ (y)}xy∈e(F 0 ) )

= F.

Proof of 2: Fix F ∈ Wk . Fix w such that Fw = F. Then, w contains a path
between any pair of nodes in F. Hence, F is connected.
Proof of 3: Suppose that there exists F ∈ Wk such that |e(F)| < |v(F)|. Recall
that by definition, trees are the only connected graphs with fewer edges than nodes.
Hence, since we have already established that F is connected, F must be a tree.
Proof of 4: Assume there exists a closed k-walk w = v0 v1 · · · vk−1 v0 such that Fw
is a tree. We will prove the claimed result by contradiction. Assume there exists at
least one edge traversed by w exactly once. Let o and t be the nodes corresponding
to such an edge. Since the composition of any cyclic permutation and reversal of
w will also induce Fw , as the walk is closed, we assume without loss of generality
that o and t are the two first steps of w; i.e., w = otv2 . . . vk−1 o.
Let w1 = ot and w2 = tv2 . . . vk−1 o. Then, w1 and w2 contain paths between
vertices o and t, and by assumption neither ot nor to appears in w2 . Thus, the paths
contained within w1 and w2 are edge disjoint. However, the existence of two edgedisjoint paths between a pair of vertices in Fw contradicts our assumption that Fw
is a tree. Thus we conclude that every edge in Fw is traversed at least twice by w.
Proof of 5: Fix a tree T ∈ Wk . Fix a closed k-walk w such that Fw = T . Then w
visits all edges of T at least twice, hence |e(T )| ≤ k/2. Since |e(T )| = |v(T )| − 1
for any tree T , we conclude |v(T )| − 1 ≤ k/2.

Proof of 6: Fix F ∈ Wk . We will show that F ∈ Wk+2 . Let w = v0 v1 · · · vk−1 v0
be a closed k-walk such that Fw = F. Then w0 = v0 v1 v0 v1 v2 · · · vk−1 v0 is a closed
(k + 2)-walk such that Fw0 = F. Hence Wk ⊂ Wk+2 .

Proof of 7: To prove the first point of the claim, note that any closed walk of
odd length must contain a cycle (of odd length). Trees contain no cycles, and so if
k is odd, then Wk contains no trees.
To prove the second part of the claim, assume that k is even and set k = 2r.
Recall that Tr denotes the set of unlabeled trees on r vertices. We will show by
induction that the statement
P(r) = {∀T ∈ Tr+1 , ∃w ∈ W2r (T ) s.t. Fw = T },

is true for all r ≥ 1. This directly yields that Tr+1 ⊂ W2r for any fixed r ≥ 1. Then,
noting that W2t ⊂ W2r for all t ≤ r, we conclude that Tt+1 ⊂ W2r for all t ≤ r. Thus,
24

we will have established our claim that all unlabeled trees on up to k/2 + 1 vertices
are elements of Wk . We now prove that P(r) is true for all r ≥ 1.

1. Set r = 1. Then, the only 2-tree is K2 , which is visited by any walk in W2 (K2 ).
Thus, P(1) is true.

2. Fix r > 1. Assume P(r − 1) is true and fix T ∈ Tr+1 . We now build a closed
2r-walk that induces T .
First, choose a leaf l of T and call o the unique node adjacent to l. Because
any finite tree on at least two nodes possesses at least two leaves, l always
exists. Then, let L be the graph given by L = ({l, o}, {lo}) and T 0 be the
graph given by T 0 = (v(T ) \ {l}, e(T ) \ {lo}). By construction, T = L ∪ T 0 ,
and T 0 is an r-tree.
Second, consider any closed 2(r − 1)-walk that induces T 0 . (Such a walk
exists by Item 1 of the current lemma, because we assume P(r − 1) to be
true.) Since the composition of any cyclic permutation and reversal of this
walk also induces T 0 , without loss of generality we may choose the walk
w0 = ov1 · · · v2(r−2) o such that Fw0 = T 0 .
Third, extend w0 to T by defining w = olov1 · · · v2(r−2) o, so that Fw = L∪T 0 =
T and |w| = |w0 | + 2 = 2r.

Thus, for any (r + 1)-tree T , we have exhibited a closed walk w in W2r (T )
such that Fw = T . Hence, P(r) is true.
Finally, since P(r − 1) ⇒ P(r) and P(1) holds, it follows by induction that P(r) is
true for all r ≥ 1.

Proof of 8: The closed walk w = 12 · · · k1 is in Wk (Kk ) and induces Fw ≡ Ck .
Hence, Ck ∈ Wk . For a closed k-walk to visit k nodes, it must visit a new node at
each step (apart from the last). Let w0 = v1 v2 · · · vk v1 be any such closed k-walk
in Wk (Kk ), where all elements v1 , v2 , . . . vk ∈ v(Kk ) are distinct. Then through the
vertex bijection vi 7→ i, we see that Fw0 ≡ Fw . Hence, we conclude that Ck is the
only element of Wk on k vertices.
Proof of 9: We show that Ck−2 P2 is the only element of Wk that is both on k − 1
vertices and with k − 1 edges. To begin, consider a closed k-walk that induces a
(k − 2)-cycle and then immediately traverses a pendant edge. In turn, this walk
induces a graph isomorphic to Ck−2 P2 , and so Ck−2 P2 ∈ Wk . Hence we may now
fix some F ∈ Wk on k − 1 vertices and with k − 1 edges, since we have shown at
least one such F to exist. We will show that F ≡ Ck−2 P2 for any choice of F.
25

First, by Item 1 of the current lemma, we may fix a closed k-walk w such
that Fw = F. Then, since F possesses k − 1 edges while w traverses k edges, we
conclude that there is exactly one edge in F traversed twice by w. Label this edge
ot, and assume without loss of generality (since the composition of any cyclic
permutation and reversal of w will also induce F) that w = otv2 v3 · · · vk−1 o.
Next, note that for ot to be traversed twice, one of its vertices must be visited
twice. However, since F possesses k − 1 vertices while w visits k vertices, we see
that exactly one vertex in F is visited twice. Without loss of generality, assume
this vertex to be o, in which case all vertices in v(F) \ {o} must be visited exactly
once.
Finally, observe that for t to be visited exactly once and ot traversed exactly
twice, the sequence oto must occur exactly once in w. Thus we conclude that
w = otov3 · · · vk−1 o. Furthermore, by construction neither o nor t can be otherwise visited by w. It follows that {o,t} ∩ {v3 , . . . , vk−1 } = 0,
/ and consequently that
|{v3 , . . . , vk−1 }| = k − 3.
To complete the proof, consider the graph F1 induced by oto and the graph F2
induced by ov3 · · · vk−1 o. We have Fw = F = F1 ∪ F2 , with {o,t} ∩ {v3 , . . . , vk−1 } =
0/ implying that v(F1 ) ∩ v(F2 ) = {o}. We see directly that F1 ≡ P2 . Furthermore,
we see that F2 ∈ Wk−2 , with |{v3 , . . . , vk−1 }| = k − 3 implying that |v(F2 )| = k − 2.
Hence F2 ≡ Ck−2 . It therefore follows that F ≡ Ck−2 P2 , since we have shown that,
up to isomorphism, F can be obtained by joining Ck−2 to P2 by identifying a single
vertex.

3

Closed walks and extensions

3.1

Extensions and a partial order on walk-induced subgraphs

We have introduced the set Wk , which organizes walk-induced graphs by scale. We
next construct a relation “Ck ” on each given set Wk .
Definition S.3 (Graph extension “Ck ” and corresponding walk extension). Fix an
integer k ≥ 2 and F, F 0 ∈ Wk . We call F 0 an extension of F and write F Ck F 0 if:
1. |v(F 0 )| − |v(F)| = 1,
2. |e(F 0 )| − |e(F)| ≤ 1,

26

3.

min

k

∑ 1{vi6=v0i} = 1.

w=v0 ···vk ∈W (Kk ) : Fw ≡F i=0
w0 =v00 ···v0k ∈W (Kk ) : Fw0 ≡F 0

Given two closed k-walks w = v0 v1 · · · vk−1 v0 and w0 = v00 v01 · · · v0k−1 v00 in a simple
graph G, we call w0 an extension of w in G if Fw Ck Fw0 and w0 has a Hamming
distance of exactly 1 from w.
From Item 3 of Definition S.3, we see directly that whenever F Ck F 0 for some
pair F, F 0 ∈ Wk , there exists a pair w, w0 of closed k-walks in Kk such that Fw ≡ F,
Fw0 ≡ F 0 , and w0 is an extension of w in Kk .
We now determine when any F ∈ Wk admits an extension.
Lemma S.2. Fix an integer k ≥ 2 and let F ∈ Wk . Then F admits an extension
unless either F ≡ Ck when k ≥ 3, or F is isomorphic to an element of Tk/2+1 when
k is even and k ≥ 2. In these latter two cases F admits no extension.
Furthermore, whenever F admits an extension, then at least one such extension
0
0
F has the following property: There exist orderings (d1 , . . . , dv ) and (d10 , . . . , dv+1
)
of the degrees of F and F 0 , respectively, such that exactly one of the following four
cases holds:
0
1. dt0 = dt for all t ≤ v − 1, dv0 = dv − 2, and dv+1
= 2;
0
0
2. dt0 = dt for all t ≤ v − 2, dv−1
= dv−1 − 1, dv0 = dv + 1, and dv+1
= 2;
0
0
3. dt0 = dt for all t ≤ v − 2, dv−1
≤ dv−1 , dv0 ≤ dv + 1, and dv+1
= 1; or
0
4. dt0 = dt for all t ≤ v − 1, dv0 = dv − 1, and dv+1
= 1.

Proof. We first show that F ∈ Wk admits no extension if either i) F ≡ Ck when
k ≥ 3; or ii) F is isomorphic to an element of Tk/2+1 when k ≥ 2 is even.
First, consider i) so that F ≡ Ck . Then it follows that |v(F)| = k. Assume there
exists F 0 ∈ Wk such that F Ck F 0 . Then |v(F 0 )| = |v(F)| + 1 by Definition S.3. But
no closed k-walk can visit more than k nodes, and since by construction every
element of Wk is induced by some closed k-walk, no element of Wk has more than
k nodes. Thus we obtain a contradiction, and so conclude that F ∈ Wk admits no
extension if F ≡ Ck when k ≥ 3.
Second, consider ii) so that F is isomorphic to some element of Tk/2+1 , implying that |v(F)| = k/2 + 1 and |e(F)| = k/2. Assume there exists F 0 ∈ Wk such that
F Ck F 0 . By Item 2 of Lemma S.1, any F 0 ∈ Wk is necessarily a connected graph.
27

Since |v(F 0 )| = |v(F)| + 1 = k/2 + 2 by Definition S.3, it follows that in order to
be connected, F 0 must necessarily have k/2 + 1 edges. This implies that F 0 is a
tree with |e(F 0 )| = |e(F)| + 1 = k/2 + 1. By Item 5 of Lemma S.1, however, any
tree in Wk contains no more than k/2 edges. Thus we obtain a contradiction, and
so conclude that F ∈ Wk admits no extension if F is isomorphic to an element of
Tk/2+1 when k ≥ 2 is even.
We next construct an extension of any F ∈ Wk that is i) not isomorphic to Ck
when k ≥ 3; and ii) not isomorphic to an element of Tk/2+1 when k ≥ 2 is even.
We consider two mutually exclusive and exhaustive cases, depending on whether
or not a closed walk inducing F traverses every edge in e(F) at least twice:
Claim 1 If for k ≥ 3 there exists a closed k-walk w inducing F ∈ Wk which traverses at least one edge in e(F) exactly once, then F admits an extension
whenever F 6≡ Ck .
Claim 2 If for k ≥ 2 there exists a closed k-walk w inducing F ∈ Wk which traverses every edge in e(F) at least twice, then F admits an extension whenever
k is odd, or whenever k is even and F is not isomorphic to an element of
Tk/2+1 .
For each of Claim 1 and Claim 2 in turn, we will exhibit an F 0 ∈ Wk such
that F Ck F 0 . To construct F 0 ⊂ Kk as a labeled graph, we must first ensure the
existence of an additional node in Kk to be visited by a closed k-walk w0 that is
a candidate extension of a closed k-walk inducing F ∈ Wk . To do so we must
exclude any F with |v(F)| = k. By Item 8 of Lemma S.1, the only element of Wk
on k nodes is Ck . We have shown that if F ≡ Ck , then F admits no extension. In
Claim 1, we assume F 6≡ Ck . In Claim 2, we assume all edges in F are traversed
at least twice, so |e(F)| ≤ bk/2c and hence F 6≡ Ck . Thus for both claims, clearly
it follows that F 6≡ Ck , which in turn implies |v(F)| < k. Therefore, we can fix a
new node l ∈ v(Kk ) \ v(F) to be visited by a closed k-walk w0 that is a candidate
extension of a closed k-walk inducing F ∈ Wk .
Furthermore, note that since the composition of any cyclic permutation and
reversal of any walk inducing F ∈ Wk will also induce F, we will choose from
among all such walks at our convenience throughout this proof, always without
loss of generality.
Proof of Claim 1: We first consider k ≥ 5, treating the cases k = 3 and k = 4
separately below. Fix F ∈ Wk \ {Ck } such that there exists a closed k-walk inducing
F ∈ Wk which traverses at least one edge in e(F) exactly once; for example, by
28

(1.1)

···

b1

···

b2

···

b1

l

a
···

···

b4
···

b
···

a

w1

b3

b4

···

···

b

···

c
b

···

···

(2.1)

w2

···

a

b3

(1.2)

b2

···
b

w2

a

a

w̄1

a

···

c

l

w2

···

b

bl w̄
1

a

(2.2)

a
w22
w21

a

b
w12
c

w11

a

b

w22

w̄12

w21

c

w̄11

b
bl w̄
12

w22
w21

c

w̄11

Figure S1 | Diagram showing the four different walk modifications used to prove
Lemma S.2. Note that new walk steps are marked gray, and arrows indicate the
direction of walk travel. Split arrows indicate that both directions are traveled.
Item 9 of Lemma S.1, we may choose the (k − 2, 1)-tadpole F ≡ Ck−2 P2 for any
k ≥ 5. To exhibit an extension F 0 ∈ Wk of F, we consider two mutually exclusive
and exhaustive cases for k ≥ 5:
1. Assume that k ≥ 5, and that all edges in e(F) are traversed exactly once by
some closed k-walk inducing F. Therefore this walk is an Eulerian circuit,
and so all vertices in F must have even degrees. If all vertices of F were to
have degree two, then we would conclude F ≡ Ck , since Ck is the only connected 2-regular graph on k vertices. However, since F 6≡ Ck by hypothesis,
we immediately conclude that F must possess at least one vertex of even
degree at least four.
Pick any such vertex of even degree d ≥ 4 and label it a. Since we assume
29

the existence of a closed k-walk inducing F with the property that every edge
is traversed exactly once, we may assign labels b1 , b2 , . . . , bd to all vertices
connected to a such that the segments b1 ab2 and b3 ab4 appear exactly once
in this walk, with b1 ab2 preceding b3 ab4 . The first diagram of Fig. S1.(1.1)
depicts an example for d = 4. Therefore (after an appropriate cyclic permutation if necessary to begin the walk at b1 ) we can write the assumed closed
k-walk inducing F as w = b1 ab2 · · · b3 ab4 · · · b1 .

Now, define another closed k-walk w0 = b1 lb2 · · · b3 ab4 · · · b1 , and refer to
the second diagram of Fig. S1.(1.1). By construction, Items 1 and 2 of
Definition S.2 are verified for Fw and Fw0 , since |v(Fw0 )| = |v(Fw )| + 1 and
|e(Fw0 )| = |e(Fw )|. To verify Item 3 of Definition S.2, note that w and w0
disagree in exactly one entry. Furthermore, no other walks inducing F and
Fw0 can disagree in fewer entries, since by Item 1 we have that v(F) 6= v(Fw0 ).
Therefore, F Ck Fw0 .
2. Assume that k ≥ 5, and that at least one edge in e(F) is traversed more
than once by some closed k-walk inducing F. Then at some point in this
walk, an edge traversed exactly once and an edge traversed more than once
must be traversed in immediate succession. Assume, reversing the walk if
necessary, that the former edge precedes the latter edge. Then, calling the
edge traversed exactly once ab, and the edge traversed more than once bc,
we may (after an appropriate cyclic permutation if necessary to begin the
walk at a) write the assumed closed k-walk inducing F as w = abc · · · a. An
example is depicted in the first diagram of Fig. S1.(1.2).
Now, define the closed k-walk w0 = alc · · · a, noting that |v(Fw0 )| = |v(F)| + 1
since the edge bc is traversed more than once by hypothesis and thus b ∈
v(Fw0 ), and refer to the second diagram of Fig. S1.(1.2). Observe that since
ab is traversed only one time by w, it follows that ab 6∈ Fw0 ; in contrast,
since bc is traversed multiple times by w, it follows that bc ∈ e(Fw0 ). Thus,
|e(Fw0 )| = |(e(F) \ {ab}) ∪ {al, lc}| = |e(F)| + 1. Therefore, Items 1 and 2
of Definition S.2 are verified for F and Fw0 . To verify Item 3, observe as
before that w and w0 disagree in exactly one entry.
It remains to consider k = 3 and k = 4. For k = 3, we have W3 \ {C3 } = 0.
/ For
k = 4, we have W4 \ {C4 } = {P2 , P3 }. No graphs of the form F ≡ P2 or F ≡ P3 may
be induced by a closed 4-walk which traverses at least one edge in e(F) exactly
once. Thus we have exhibited an extension of F under the hypothesis of Claim 1.
30

Proof of Claim 2: We first consider the cases k = 4, k = 6, and k ≥ 8, treating
the cases k = 2, k = 3, k = 5 and k = 7 separately below. Fix F ∈ Wk \ {Ck } if
k is odd, or F ∈ Wk \ ({Ck } ∪ Tk/2+1 ) if k is even, such that there exists a closed
k-walk traversing every edge in e(F) at least twice. To show that such an element
exists, note that if k is even, we may choose F ≡ P2 , while if k is odd we may
choose F ≡ C3 , with a walk traversing C3 three times and then repeatedly visiting
an adjacent node a total of (k − 9)/2 times.
To exhibit an extension F 0 ∈ Wk of F for k = 4, k = 6, or k ≥ 8, we consider
two mutually exclusive and exhaustive cases:
1. We let k = 4, k = 6, or k ≥ 8, and assume that at least one edge in e(F) is
traversed twice in the same direction by some closed k-walk inducing F.
Then there exists an edge ab such that we can (after an appropriate cyclic
permutation of the walk if necessary) begin the walk at a. Then, letting w1
and w2 be walk segments (sequences of adjacent nodes, possibly of length
zero), we may write w = abw1 abw2 a. The first diagram of Fig. S1.(2.1)
provides an illustration of this scenario.
Define w̄1 to be w1 in reversed order, such that if w1 = w11 w12 · · · w1|w1 | , then
w̄1 = w1|w1 | w1(|w1 |−1) · · · w11 ; if w1 = w11 then w̄1 = w11 ; and if w1 is empty
then w̄1 is in turn empty.
Now consider the closed k-walk w0 = abaw̄1 bw2 a. We note that Fw0 = Fw ,
and refer to the second diagram of Fig. S1.(2.1). Define w00 = alaw̄1 bw2 a,
and note that Items 1 and 2 of Definition S.2 are verified for F = Fw0 and
Fw00 by construction (refer to the third diagram of Fig. S1.(2.1)). To verify
Item 3 of Definition S.2, we observe (as before) that w0 and w00 disagree in
exactly one entry. Therefore, we have exhibited w00 such that F Ck Fw00 .
2. We let k = 4, k = 6, or k ≥ 8, and assume that no edge in e(F) is traversed
twice in the same direction by some closed k-walk inducing F. No element
of W4 verifies this assumption, since W4 \ ({C4 } ∪ T3 ) = {P2 }, and P2 is
induced only by walks traversing all edges in both directions. Therefore we
may assume that k = 6 or k ≥ 8.

In this setting, all edges in F are traversed at least twice but none twice in the
same direction. Thus all the edges in e(F) must be traversed by w exactly
once in each direction. This means all edges are traversed exactly twice, and
importantly, it therefore follows that k is even and |e(F)| = k/2.
31

We begin by showing (by contradiction) that F is not a tree. If F were
a tree, then F would be a tree over k/2 edges, and therefore F would be
isomorphic to an element of Tk/2+1 . Since we have already assumed that F
is not isomorphic to an element of Tk/2+1 , this cannot hold.
We now use that F is not a tree to build a walk w0 inducing F. First, since
F is connected and not a tree, F contains at least one cycle. We fix C to
be any cycle in F and fix ab as any edge in e(C). Then, we can (after an
appropriate cyclic permutation if necessary), begin the walk at a and can
write w = abw1 baw2 a, where w1 and w2 are walk segments. Either w1 or
w2 could be empty, but since k ≥ 6, at least one of the two segments is not
empty. We distinguish two mutually exclusive and exhaustive cases:
(a) If neither w1 nor w2 is the empty walk, for C to be a subgraph of Fw ,
w1 and w2 must cross over at least one vertex; i.e., must both visit at
least one common vertex (see Fig. S1.(2.2)). To prove this, we proceed by contradiction. If w1 and w2 do not cross, then either w1 or w2
must induce C, and since ab is an edge of C, w1 or w2 must traverse
ab and therefore ab is traversed thrice by w. However, this contradicts the assumption that ab is traversed exactly twice. Therefore, call
without loss of generality c any of the possible vertices where w1 and
w2 cross. Then, writing w1 = w11 cw12 and w2 = w21 cw22 , we have
w = abw11 cw12 baw21 cw22 a (refer to the first diagram in Fig. S1.(2.2)
and note that w11 , w12 , w21 and w22 could be empty). Define w̄11
and w̄12 to be the walks w11 and w12 in reversed order and set w0 =
abaw21 cw̄11 bw̄12 cw22 a.
(b) If w1 (resp. w2 ) is the empty walk, then w = abaw2 a (resp. w = abw1 ba)
and w2 must visit b (resp. a) for ab to be an edge of C (and satisfy the
constraint of every edge being visited at least twice). We then write
w2 = w21 bw22 , and thus we may set w0 = abaw21 bw22 a (resp. w0 =
abaw̄11 bw̄12 a). Note a slight asymmetry in the proof, namely that w ≡
w0 if w1 is the empty walk, while w0 had been redefined if w2 is the
empty walk.
To simplify notation, in these two cases, we write w0 = abaw̃. Now we observe that: i) w0 is a closed walk of the same length as w and; ii) w0 is
such that Fw0 = Fw (refer to the second diagram in Fig. S1.(2.2)). Finally,
call w00 = alaw̃ and note that Items 1 and 2 of Definition S.2 are verified
32

for F = Fw0 and Fw00 by construction (as shown in the third diagram in
Fig. S1.(2.2)). To verify Item 3 of Definition S.2, we observe once again
that w0 and w00 disagree in exactly one entry. Therefore F Ck Fw00 .
We now treat the remaining cases of k = 2, k = 3, k = 5, and k = 7. If k = 2,
then P2 is the only possible walk-induced subgraph. Then W2 \ T2 = 0,
/ and so the
claim trivially holds. If k = 3, k = 5, or k = 7, then no closed k-walk w can traverse
every edge in the edge set of F at least twice. This is because every closed odd
walk must contain an odd cycle, and k is not large enough to traverse every edge
in the the smallest odd cycle C3 at least twice.
Thus, whenever F ∈ Wk \ ({Ck } ∪ Tk/2+1 ) if k is even, or F ∈ Wk \ {Ck } if k is
odd, we have exhibited an extension of F under the hypothesis of Claim 2.
Having shown the first part of the lemma, we now show that its second statement is a consequence of the constructive proof above. We fix F ∈ Wk and assume
that F admits at least one extension, implying that k ≥ 4. Thus we may appeal to
the four methods illustrated in Fig. S1 to construct an extension F 0 of F. As we
now show, these four methods enable us to directly verify that there exists order0
ings (d1 , . . . , dv ) and (d10 , . . . , dv+1
) of the degrees of F and F 0 , respectively, such
that exactly one of the four cases stated in the lemma holds. We write the degree
of the node labeled x in F as dx , and that of the node labeled y in F 0 as dy0 .
1. We begin by considering F 0 as constructed in Item 1 of Claim 1 in the proof
above, referring to Fig. S1.(1.1) for an illustration. With the labeling of
Fig. S1.(1.1), we observe directly that dl0 = 2 and da0 = da − 2, while dx = dx0
for x ∈ v(F) \ {a}. It follows that if we relabel the vertex labeled l as v + 1,
the vertex labeled a as v, and the other vertices arbitrarily, then F 0 obeys
the first case stated in the lemma: dt0 = dt for all t ≤ v − 1, dv0 = dv − 2, and
0
dv+1
= 2.
2. We then consider F 0 as constructed in Item 2 of Claim 1 in the proof above.
Referring to Fig. S1.(1.2), we observe directly that dl = 2, dc0 = dc + 1, and
db0 = db − 1 (because the edge ab is traversed exactly once, and so there is
no edge between a and b in F 0 , reducing the degree of b by 1), while dx = dx0
for x ∈ v(F) \ {b, c}. It follows that if we relabel the vertex labeled l as v + 1,
the vertex labeled c as v, the vertex labeled b as v − 1, and the other vertices
arbitrarily, then F 0 obeys the second case stated in the lemma: dt0 = dt for all
0
0
t ≤ v − 2, dv−1
= dv−1 − 1, dv0 = dv + 1, and dv+1
= 2.
33

3. We next consider F 0 as constructed in Item 1 of Claim 2, referring here to
Fig. S1.(2.1) to illustrate the change in the degree sequence of F 0 relative to
F. We observe directly that dl = 1, da0 ≤ da + 1, and db0 ≤ db , while dx = dx0
for x ∈ v(F) \ {a, b}. It follows that if we relabel the vertex labeled l as v + 1,
the vertex labeled a as v, the vertex labeled b as v − 1, and the other vertices
arbitrarily, then F 0 obeys the third case stated in the lemma: dt0 = dt for all
0
0
t ≤ v − 2, dv−1
≤ dv−1 , dv0 ≤ dv + 1, and dv+1
= 1.

4. Finally, we consider F 0 as constructed in Item 2 of Claim 2, referring to
Fig. S1.(2.2)) to illustrate how the degrees of F and F 0 are respectively
modified. We observe directly that dl = 1, da0 = da and db0 = db − 1 (because
the edge ab is traversed exactly twice), while dx = dx0 for x ∈ v(F) \ {a, b}.
It follows that if we relabel the vertex labeled l as v + 1, the vertex labeled b
as v, and the other vertices arbitrarily, then F 0 obeys the fourth and final case
0
stated in the lemma: dt0 = dt for all t ≤ v − 1, dv0 = dv − 1, and dv+1
= 1.

Remark S.1. As defined above, “Ck ” is a binary relation over Wk . By Items 1
and 2 of Definition S.3, the edge density |e(·)|/|v(·)| is non-increasing in “Ck ,”
while the Euler characteristic |v(·)|− |e(·)| is non-decreasing in “Ck .” Furthermore,
“Ck ” naturally induces a finer partial ordering than the edge density or the Euler
characteristic. To see this, consider the directed graph Wk = (Wk , {(F, F 0 ) : F Ck
F 0 }). This graph can be extended into a partial ordering of Wk by writing F Ek F 0
if there exists a directed path between F and F 0 in Wk ; i.e., if F = F 0 , F Ck F 0 , or
there exists p ≥ 1 and F1 , . . . , Fp ∈ Wk such that F Ck F1 Ck · · · Ck Fp Ck F 0 .
With this definition, (Wk , Ek ) is a poset; i.e., a partially ordered set. We see
directly that if k ≥ 2 is even, then a minimal element of Wk according to this
partial ordering is K2 , while if k ≥ 3 is odd, a minimal element is C3 . This follows
because both K2 and C3 have in-degrees of zero when they are present in Wk . A
direct consequence of Lemma S.2 is that if k ≥ 3 is odd, then Ck is the greatest
element of (Wk , Ek ), while if k ≥ 4 is even, then {Ck }∪Tk/2+1 is the set of maximal
elements of (Wk , Ek ).

3.2 Counting walks that induce isomorphic copies of subgraphs
The set Wk and the isomorphism relation “≡” allow us to partition the set of all
closed k-walks Wk (G) in any simple graph G. Letting t denote the disjoint union,
we have directly from Definition S.1 that
Wk (G) =

G
F∈Wk

{w ∈ Wk (G) : Fw ≡ F}.
34

(S.2)

With this partition it is natural to count the number of closed k-walks in G that
induce a given unlabeled graph F.
Definition S.4 (Number indk (F, G) of closed k-walks in G inducing an isomorphic
copy of F). Fix a walk length k and two simple graphs F, G. We write
indk (F, G) = |{w ∈ Wk (G) : Fw ≡ F}|

for the number of closed k-walks in G inducing a subgraph of G isomorphic to F.
It follows from (S.2) that for any k ∈ N,


Tr A(G)k = |Wk (G)| =
Next we relate indk (F, G) to XF (G) =
phic copies of F in G.

∑

F∈Wk

indk (F, G).

 0
F ⊂ G : F0 ≡ F

, the number of isomor-

Lemma S.3. Fix a walk length k and two simple graphs F, G. Then
indk (F, G) = indk (F, F) XF (G).
Proof. Recall from Definition S.1 that Wk (G) is the set of all closed k-walks in G.
By Definition S.4,
indk (F, G) =

∑

w∈Wk (G)

=
0

1{Fw ≡F}

∑0

∑

0

F ⊂G : F ≡F w∈Wk (F )

=

∑0

F 0 ⊂G : F ≡F

1{Fw ≡F}

indk (F, F 0 )

= indk (F, F) · |{F 0 ⊂ G : F 0 ≡ F}|,

since each F 0 is isomorphic to F. The relation F 0 ⊂ G : F 0 ≡ F
pletes the proof.

= XF (G) com-

Remark S.2. The growth rate of indk (F, F) with k can vary substantially, depending on the structure of F. For example, we have indk (Ck ,Ck ) = 2k = aut(Ck ),
whereas indk (F, F) = 2(k/2)! = 2aut(F) for the (k/2 + 1)-star F = K1,k/2 . The
structure of F, or indeed the parity of k, can also imply that indk (F, F) = 0. For example, since every closed walk of odd length contains an odd cycle, indk (F, F) = 0
whenever F is a tree and k is odd. More generally, independently of the parity of
k, indk (F, F) = 0 if F is not connected, or if |v(F)| or |e(F)| exceeds k.
35

Lemma S.3 shows how indk (Fw , G), the number of copies of w in G, relates to
XFw (G). Similarly, we may count the number of copies of w in any vertex-induced
subgraph of G. Averaging over all such subgraphs of fixed order leads to the notion
of a graph walk density.
Definition S.5 (Graph walk density ϕ(w, G)). Fix an integer k ≥ 2, a closed kwalk w ∈ Wk (Kk ), a graph G, and a neighborhood size |u| such that |v(Fw )| ≤
|u| ≤ |v(G)|. We let u ⊂ v(G) be chosen uniformly at random from amongst all
|u|-subsets of v(G) and take the expectation with respect to the randomized choice
of subset u. Then we define the graph walk density of w in G to be
ϕ(w, G) =

E ind|w| (Fw , G[u])
ind|w| (Fw , K|u| )

=

E XFw (G[u])
XFw (K|u| )

,

where K|u| is the complete graph on |u| vertices, and G[u] = (u, e(G) ∩ u(2) ) is the
subgraph of G induced by u ⊂ v(G), with u(2) the set of all unordered pairs of
elements of u.
We see that ϕ(w, G) takes values between 0 and 1, and so we are justified
in referring to ϕ(w, G) as a density. Furthermore, as we shall show, ϕ(w, G) is
independent of the choice of neighborhood size |u|. Setting |u| = |v(G)| immediately allows us to recognize the walk density ϕ(w, G) as a graph homomorphism
density [1, 2].
Lemma S.4. Let F, G be finite graphs with |v(F)| ≤ |v(G)|, and fix 1 ≤ |u| ≤ |v(G)|.
Then for u ⊂ v(G) chosen uniformly at random from among all |u|-subsets of v(G),
E XF (G[u]) =

XF (K|u| )

XF (K|v(G)| )

XF (G).

Proof. For notational convenience, let n = |v(G)| and s = |u|. We begin by expressing the expectation sum associated to E XF (G[u]) directly:

∑

u⊂v(G) : |u|=s

XF (G[u]) =
=

∑

∑

u⊂v(G) : |u|=s F 0 ⊂G[u]

∑

∑

u⊂v(G) : |u|=s F 0 ⊂G[u]

36

1{F 0 ≡F}
XF (G)

∑

i=1

1{F 0 =F } ,
i

(S.3)

where F1 , . . . , FXF (G) enumerate all copies of F in G. Rearranging the order of these
three sums, each of which is finite for finite G, and subsequently fixing i and u to
focus on the summation in F 0 , we have

∑

F 0 ⊂G[u]

1{F 0 =F } =
i

=

∑

∑

u0 ⊂v(G[u]) t 0 ⊂e(G[u])∩u0(2)

∑
0

∑

0

0

u ⊂u t ⊂e(G[u ])

=

i

1{u0 =v(F )} ∑
∑
i
0
0

∑

∑

0

t ⊂e(G[u ])

0

∑

v(Fi )⊂u t ⊂e(G[v(Fi )])

=

i

1{(u0 ,t 0 )=F }

u ⊂u

=

1{(u0 ,t 0 )=F }

1{t 0 =e(F )}
i

1{t 0 =e(F )}
i

1,

(S.4)

v(Fi )⊂u

since e(Fi ) ⊂ e(G[v(Fi )]). We next count how many s-subsets of v(G) contain each
v(Fi ) in turn, whence from (S.3) and (S.4) we obtain
XF (G)

∑

i=1

∑

∑

1=

u⊂v(G) : |u|=s v(Fi )⊂u

XF (G) 

∑

i=1


n − |v(Fi )|
.
s − |v(Fi )|

Since |v(Fi )| = |v(F)| for all i, we obtain the intermediate result that


n − |v(F)|
∑ XF (G[u]) = s − |v(F)| XF (G).
u⊂v(G) : |u|=s

Now, if we select u with probability 1/ ns , the claimed result follows immediately
upon noting that XF (Km ) = (m)|v(F)| /aut(F) for any positive integer m, and thus
n−|v(F)| n
/ s = XF (Ks )/XF (Kn ).
s−|v(F)|
A direct consequence of Lemma S.4 is that for a closed k-walk w in Kk , a fixed
G, and subsets t, u ⊂ v(G) of sizes |t|, |u|, each chosen uniformly at random and
with |v(Fw )| ≤ |t|, |u| ≤ |v(G)|, we have
E XFw (G[u])
XFw (K|u| )

=

37

E XFw (G[t])
XFw (K|t| )

.

Thus, using Lemma S.3, we find that
ϕ(w, G) =

E indk (Fw , G[u]) E indk (Fw , G[t])
=
,
indk (Fw , K|u| )
indk (Fw , K|t| )

verifying that ϕ(w, G) does not depend on the choice of neighborhood size |u|.
Remark S.3. Fix a graph G and two closed k-walks w and w0 where Fw Ck Fw0 . In
this setting, ϕ(w0 , G)/ϕ(w, G) governs indk (Fw , G[u])/indk (Fw0 , G[u]), and therefore determines which of w and w0 has a larger number of copies. To see this,
observe that the number of copies of w0 over the number of copies of w takes the
form:
indk (Fw0 , G) indk (Fw0 , Kn ) indk (Fw0 , G)/indk (Fw0 , Kn )
=
indk (Fw , G)
indk (Fw , Kn ) indk (Fw , G)/indk (Fw , Kn )
indk (Fw0 , Kn ) ϕ(w0 , G)
=
.
indk (Fw , Kn ) ϕ(w, G)
Since for F ⊂ G ⊂ Kn , indk (F, Kn ) = (n)|v(F)| indk (F, F)/aut(F), and as |v(Fw0 )| =
|v(Fw )| + 1 whenever Fw Ck Fw0 , we recover
indk (Fw0 , G) (n)|v(Fw0 )| indk (Fw0 , Fw0 )/aut(Fw0 ) ϕ(w0 , G)
=
indk (Fw , G)
(n)|v(Fw )| indk (Fw , Fw )/aut(Fw ) ϕ(w, G)

indk (Fw0 , Fw0 ) aut(Fw ) ϕ(w0 , G)
,
= (n − |v(Fw0 )|)
indk (Fw , Fw ) aut(Fw0 ) ϕ(w, G)

and the asymptotic behavior of the number of copies of an extension w0 over the
number of copies of the original walk w is the same as that of nϕ(w0 , G)/ϕ(w, G).

4
4.1

Determining dominating closed walks
Defining asymptotically dominating walks

Above we have defined two key quantities for any simple graph G: indk (F, G), the
number of closed k-walks in G inducing an isomorphic copy of F, and ϕ(w, G),
the corresponding graph walk density. Recalling (S.2), it is then natural to ask how

38

different walks contribute to the set Wk (G) of closed k-walks in G; i.e, whether
one or more terms of the form indk (F, G) dominate the sum


Tr A(G)k = |Wk (G)| = ∑ indk (F, G).
(S.5)
F∈Wk

In the theory of dense graph limits (see, e.g., [2]), it is well known that k-walks
inducing cycles will dominate all other walks in number.
To understand which terms are significant in (S.5), we will study its dominating
terms. To do so, we define an asymptotic regime corresponding to a sequence of
random graphs {Gn } whose number of nodes tends to infinity. We assume that
for all n sufficiently large, E|Wk (Gn )| > 0. This fact implies that eventually in
n, the ratio E indk (F, Gn )/ E|Wk (Gn )| is well defined. From this, appealing to the
compactness of [0, 1] and the monotone convergence theorem, we define
γk,F ({Gn }) = lim inf
n→∞

E indk (F, Gn )
.
E|Wk (Gn )|

(S.6)

The quantity |Wk (Gn )| in (S.6) is a sum of non-negative counts, as shown
by (S.5), and furthermore this sum is over a finite set. This in turns implies that we
may exchange the order of expectation and summation, and so γk,F ({Gn }) ∈ [0, 1].

Definition S.6 (Set Wk∗ ({Gn }) of asymptotically dominating walk-induced subgraphs). Fix a walk length k ∈ N. Let {Gn } be a sequence of random simple graphs
whose number of nodes tends to infinity and such that for all n sufficiently large,
E|Wk (Gn )| > 0. We then define the set Wk∗ ({Gn }) of asymptotically dominating
walk-induced subgraphs as follows:

Wk∗ ({Gn }) = F ∈ Wk : γk,F ({Gn }) > 0 .
We next exhibit four key properties of Wk∗ ({Gn }).

Proposition S.3. Consider a sequence {Gn } of random simple graphs whose number of nodes tends to infinity. Under the condition that for all n sufficiently large,
E|Wk (Gn )| > 0, the set of asymptotically dominating walk-induced subgraphs
Wk∗ ({Gn }), verifies the following four properties:
1. Wk∗ ({Gn }) is non-empty for all k ≥ 2.

2. Wk∗ ({Gn }) fully determines E|Wk (Gn )| asymptotically, in the sense that
E|Wk (Gn )| ∼

∑

F∈Wk∗ ({Gn })

39

E indk (F, Gn ).

(S.7)

3. Any element of Wk∗ ({Gn }) dominates all elements of Wk \Wk∗ ({Gn }), so that
for any F ∗ ∈ Wk∗ ({Gn }),
lim

n→∞

0
∑F 0 ∈Wk \Wk∗ ({Gn }) E indk (F , Gn )

E indk (F ∗ , Gn )

= 0.

4. Every element of Wk∗ ({Gn }) is of the same order of magnitude. Specifically,
for F1∗ , F2∗ ∈ Wk∗ ({Gn }), there exist positive constants C1 and C2 such that
for all sufficiently large n
C1 E indk (F2∗ , Gn ) ≤ E indk (F1∗ , Gn ) ≤ C2 E indk (F2∗ , Gn ).
Then, as for any fixed k the number of closed k-walks are finite, for all F ∗ ∈
Wk∗ ({Gn }) we have E indk (F ∗ , Gn ) = Θ(E|Wk (Gn )|).
Proof. We will prove the four results in order.
Proof of 1: Since for n large enough E|Wk (Gn )| > 0, directly from (S.5) it
follows
E ind (F, G )
∑ E|Wkk (Gn)|n = 1.
F∈W
k

Thus, as Wk is a finite set, by taking the inferior limit on both sides of the above
equation we obtain ∑F∈Wk γk,F ({Gn }) = 1. This implies that at least one γk,F ({Gn })
is strictly positive, and so Wk∗ ({Gn }) is non-empty.

Proof of 2: We prove that the limit superior and the limit inferior of the ratio of
the two quantities in (S.7) are both tending to one. Therefore, the limit exists and is
equal to one, yielding the desired result. First, by Item 1 of the current proposition,
lim infn→∞

∑F∈Wk∗ ({Gn }) E indk (F, Gn )
= 1.
E|Wk (Gn )|

Furthermore, by (S.5), the ratio of the two quantities in (S.7) is smaller than one,
and therefore
∑F∈Wk∗ ({Gn }) E indk (F, Gn )
lim supn→∞
≤ 1.
E|Wk (Gn )|
Consequently, we conclude that
limn→∞

∑F∈Wk∗ ({Gn }) E indk (F, Gn )
= 1.
E|Wk (Gn )|
40

(S.8)

Proof of 3: Fix F ∗ ∈ Wk∗ ({Gn }). We first rewrite the ratio of interest as follows:
0
∑F 0 ∈Wk \Wk∗ ({Gn }) E indk (F , Gn )

E indk (F ∗ , Gn )
=

∑F∈Wk∗ ({Gn }) E indk (F, Gn )
1−
E|Wk (Gn )|

!

E indk (F ∗ , Gn )
E|Wk (Gn )|

−1

. (S.9)

The first term in the product comprising the right-hand side of (S.9) admits a limit
of zero by (S.8) (Item 2 of the current proposition). To conclude that the product
itself is tending to zero, we will show that its second term has a finite superior
limit. To this end, we use both the monotonicity and the continuity of the function
g(x) = x−1 for all x > 0, yielding

!−1 

−1
∗
∗


E indk (F , Gn0 )
E indk (F , Gn )
lim sup
= lim sup
n→∞ 0 

E|Wk (Gn )|
E Wk (Gn0 )
n→∞
n >n
(
)!−1
E indk (F ∗ , Gn0 )
= lim inf
n→∞ n0 >n
E Wk (Gn0 )
(
)!−1
E indk (F ∗ , Gn0 )
= lim inf
n→∞ n0 >n
E Wk (Gn0 )
−1

E indk (F ∗ , Gn )
= lim inf
n→∞
E|Wk (Gn )|
= γk,F ∗ ({Gn })−1 ,
whence from (S.6) and Definition S.6 we observe that γk,F ∗ ({Gn })−1 is finite and
greater than 1. Thus we have shown that the limit of the first term in the product
comprising the right-hand side of (S.9) is zero, and that the superior limit of the
second term is finite and strictly positive. Now, the left-hand side of (S.9), being a
ratio of non-negative terms, is itself non-negative. Therefore we conclude that its
limit is zero as claimed.
Proof of 4: Fix F1∗ , F2∗ ∈ Wk∗ ({Gn }), and consider the ratio
E indk (F1∗ , Gn ) E indk (F1∗ , Gn )/|Wk (Gn )|
=
.
E indk (F2∗ , Gn ) E indk (F2∗ , Gn )/|Wk (Gn )|
41

(S.10)

The inferior limits of both the numerator and denominator in the right-hand side
of (S.10) (i.e., γk,F1∗ ({Gn }) and γk,F2∗ ({Gn }), respectively) are finite and strictly positive, while the superior limits of both are upper bounded by unity. Using the same
arguments as in the proof of Item 3 of the current proposition, it follows that: i) the
−1
superior limit of the left-hand side of (S.10) is upper bounded by γk,F
∗ ({Gn }) ∈
2
[1, ∞) and ii) its inferior limit is lower bounded by γk,F1∗ ({Gn }) ∈ (0, 1]. These two
bounds justify the claimed result and the use of the Θ notation.

4.2

Conditions when walks inducing trees and cycles dominate

We now characterize the set Wk∗ ({Gn }) of asymptotically dominating walk-induced subgraphs under mild conditions on sequences {Gn } of random simple graphs
whose number of nodes tends to infinity. To do so we will use the graph walk
density ϕ(·, ·). This density can be related to classical concepts: For example, the
assumption underpinning the theory of dense graph limits is that any ϕ(w, Gn ) has
a strictly positive limit [2]. For generalized random graphs with bounded kernels,
the corresponding assumption is that there exists a sequence {ρ} taking values in
−|e(Fw )|
(0, kκk−1
ϕ(w, Gn ) always has a strictly positive limit [1, 3].
∞ ) such that ρ
Recalling the notion of walk extensions from Definition S.3, we introduce the
following assumptions.
Assumption S.1. {Gn } is a sequence of random simple graphs whose number of
nodes tend to infinity and such that for n sufficiently large,
E|Wk (Gn )| > 0.
Assumption S.2. For all w ∈ Wk (Kk ) such that for n sufficiently large E ϕ(w, Gn ) >
0, if any extensions of w exist in Wk (Kk ), then at least one of them—say w0 —satisfies
|v(Gn )| E ϕ(w0 , Gn )
→ ∞.
E ϕ(w, Gn )
This allows us to characterize which walks dominate in expectation.

4.3

Dominance of walks mapping out trees and cycles

Theorem S.1. Let {Gn } be a sequence of random simple graphs satisfying Assumptions S.1 and S.2. Then, for k = 2 we have W2∗ ({Gn }) = W2 = {K2 }. Furthermore,
if k ≥ 3 is odd,
Wk∗ ({Gn }) = {Ck },
42

while if k ≥ 4 is even,
Wk∗ ({Gn }) ⊂ {Ck } ∪ Tk/2+1 .
Proof. First, we appeal to Item 1 of Proposition S.3 (which holds under Assumption S.1), and conclude that Wk∗ ({Gn }) is not empty for all k ≥ 2. Therefore, as W2
is the singleton {K2 }, we have W2∗ ({Gn }) = W2 = {K2 }. Similarly, W3∗ ({Gn }) =
W3 = {C3 }.
Having established that the set Wk∗ ({Gn }) is non-empty and having determined
W2∗ ({Gn }) and W3∗ ({Gn }), we next show that for all k ≥ 4, if F ∈ Wk admits at
least one extension, then F 6∈ Wk∗ ({Gn }). The result will then follow immediately
from Lemma S.2, which asserts that every F ∈ Wk not isomorphic either to Ck
when k ≥ 3, or to an element of Tk/2+1 when k ≥ 2 is even, admits an extension.
Thus, we fix k ≥ 4 and F ∈ Wk such that F admits at least one extension.
To show that F 6∈ Wk∗ ({Gn }), we will appeal to the definition of Wk∗ ({Gn }) in
Definition S.6, whereby F ∈ Wk∗ ({Gn }) if and only if
lim inf
n→∞

E indk (F, Gn )
> 0.
E|Wk (Gn )|

(S.11)

Note that this ratio is always well defined under Assumption S.1 since for all n
sufficiently large, E|Wk (Gn )| > 0. We distinguish two (exhaustive) cases, namely
the case where E indk (F, Gn ) is positive but becomes negligble in comparison to
E|Wk (Gn )|, or when we allow E indk (F, Gn ) to be zero for large n. Then:
1. Suppose E indk (F, Gn ) > 0 for all n sufficiently large. First, since F admits at least an extension, we can fix w ∈ Wk (Gn ) such that Fw ≡ F and
w admits at least one extension (see Definition S.3). Then, by construction,
E indk (Fw , Gn ) = E indk (F, Gn ) > 0, so that E ϕ(w, Gn ) > 0. Therefore, we
can appeal to Assumption S.2, and fix w0 ∈ Wk (Gn ) to be an extension of w
such that
|v(Gn )| E ϕ(w0 , Gn )
lim
= ∞.
(S.12)
n→∞
E ϕ(w, Gn )
We now use (S.12) to show that E indk (F, Gn )/E|Wk (Gn )| is tending to zero.
To this end we first lower-bound the ratio and note that by construction
0≤

E indk (F, Gn )
.
E|Wk (Gn )|
43

(S.13)

Next we upper bound this ratio. To this end we note that since E|Wk (Gn )| is
larger than E indk (Fw0 , Gn ), we have
E indk (F, Gn )
E indk (F, Gn )
≤
.
E|Wk (Gn )|
E indk (Fw0 , Gn )

(S.14)

Then, as for any w00 , E indk (Fw00 , Gn ) = Θ(|v(Gn )||v(Fw00 )| E ϕ(w00 , Gn )) (see
Definition S.5), we obtain from (S.14) that
!
E indk (F, Gn )
|v(Gn )||v(Fw )| E ϕ(w, Gn )
=O
E|Wk (Gn )|
|v(Gn )||v(Fw0 )| E ϕ(w0 , Gn )


E ϕ(w, Gn )
=O
,
(S.15)
|v(Gn )| E ϕ(w0 , Gn )

since as w0 is an extension of w it visits exactly one more vertex than w,
and therefore |v(Fw0 )| = |v(Fw )| + 1. We recognize on the right hand side
of (S.15) the inverse of the term on the left hand side of (S.12). Therefore,
jointly with (S.13), we recover
0≤

E indk (F, Gn )
= o(1),
E|Wk (Gn )|

and therefore that
lim inf

n→∞
∗
6 Wk ({Gn })
∈

This shows that F
presented in (S.11).

E indk (F, Gn )
= 0.
E|Wk (Gn )|
as it does not verify the necessary condition

2. Alternatively, assume there exists no n such that E indk (F, Gn0 ) > 0 for all
n0 > n. Then, for all n we have that infn0 >n {E indk (F, Gn0 )} = 0. It follows
that for all n, infn0 >n {E indk (F, Gn )/E|Wk (Gn )|} = 0. Therefore
(
)
E indk (F, Gn0 )
E indk (F, Gn )
lim inf
= lim inf
n→∞
n→∞ n0 >n
E|Wk (Gn )|
E Wk (Gn0 )
= lim 0 = 0.
n→∞

As F does not verify the necessary condition presented in (S.11), this shows
that F 6∈ Wk∗ ({Gn }).

To conclude, in both cases we have shown that F 6∈ Wk∗ ({Gn }). As explained above,
this yields the result.
44

5 Dominating walks in kernel-based random graphs
5.1

Kernel-based random graphs

We now undertake a detailed analysis of walk dominance within kernel-based
random graphs [1, 4], assuming that the kernel is bounded.
Definition S.7 (Kernel κ). A kernel κ is a bounded symmetric map from (0, 1)2 to
[0, ∞), normalized to integrate to unity so that kκk1 = 1.
Definition S.8 (Kernel-based random graph G(n, ρκ)). Fix a kernel κ and a scalar
ρ ∈ (0, kκk−1
∞ ). We call G(n, ρκ) the kernel-based random graph whose symmetric adjacency matrix A ∈ {0, 1}n×n is obtained from a sequence x = (xi )ni=1 of n
independent Uniform(0, 1) variates by independently setting
P(Ai j = 1 | xi , x j ) = ρ · κ(xi , x j )
for all 1 ≤ i < j ≤ n. The matrix A is completed by taking A ji = Ai j for 1 ≤ i < j ≤ n,
and Aii = 0 for 1 ≤ i ≤ n, yielding a simple random graph G = G(n, ρκ) with vertex
labels 1, 2, . . . , n and P(Ai j = 1) = ρ.
By construction, under the model of Definition
F0
 0S.8, whenever graphs F and
are defined on the same vertex set as G, then P F ⊂ G = P{F ⊂ G} if F 0 ≡ F.
In particular, for v(F) ⊂ {1, 2, . . . , n},
(
P{F ⊂ G} = E

∏

i j∈e(F)

Ai j = Ex

)

∏

i j∈e(F)

=ρ

|e(F)|

ρκ(xi , x j )

Z

∏

[0,1]|v(F)| i j∈e(F)

κ(xi , x j )

∏

i∈v(F)

dxi . (S.16)

Equipped with (S.16), we may state the following classical result. It allows
us to deduce E indk (F, G), which is necessary to characterize walks within kernelbased random graphs.
Lemma S.5. Fix a graph F, assume without loss of generality that v(F) is a subset
of {1, 2, . . . , n}, and let G = G(n, ρκ) in accordance with Definition S.8. Then the
expected number of copies of F in G is
E XF (G) = XF (Kn ) P{F ⊂ G}.
45

 0
F ⊂ G : F 0 ≡ F , we obtain

Proof. From the definition XF (G) =
E XF (G) = E
=E

∑

1{F 0 ≡F}

∑

1{F 0 ≡F} 1{F 0 ⊂G}

F 0 ⊂G
0

F ⊂Kn

=

∑
0


1{F 0 ≡F} P F 0 ⊂ G

∑

1{F 0 ≡F} P{F ⊂ G},

F ⊂Kn

=

F 0 ⊂Kn


where the final equality follows since P F 0 ⊂ G is constant for all F 0 ≡ F.
Thus we deduce the form of E indk (F, G) under the model of Definition S.8 as
we shall now show.
Lemma S.6. Fix a graph F, and let G = G(n, ρκ) in accordance with Definition S.8. Then
E indk (F, G) = indk (F, Kn ) P{F ⊂ G}.
Proof. Lemma S.3 shows that for fixed graphs F, G and k ∈ N, it follows that
indk (F, G) = indk (F, F)XF (G). Taking expectations under the model of Definition S.8 and then applying Lemma S.5 for E XF (G), we have
E indk (F, G) = indk (F, F) E XF (G)
= indk (F, F) XF (Kn ) P{F ⊂ G}.
Applying Lemma S.3 again via indk (F, Kn ) = indk (F, F)XF (Kn ), we obtain the
claimed result.
The ratios indk (F, G)/indk (F, Kn ) = XF (G)/XF (Kn ) = emb(F, G)/emb(F, Kn )
are natural empirical counterparts to P{F ⊂ G}, as we have E XF (G)/XF (Kn )
= E indk (F, G)/indk (F, Kn ) = P{F ⊂ G} by Lemmas S.5 and S.6, and in turn
XF (G) = emb(F, G)/aut(F) for any graph G. This leads to the following standard
definitions of embedding densities.
Definition S.9 (Embedding densities sρ (F, G) and s(F, κ) [5]). Fix a graph F,
assume without loss of generality that v(F) ⊂ {1, 2, . . . , n}, and let G = G(n, ρκ)
in accordance with Definition S.8. Then, we denote the ρ-normalized embedding
46

density of F in G by sρ (F, G) and its expectation under the model of Definition S.8,
the kernel embedding density, by s(F, κ):
sρ (F, G) =
s(F, κ) = E sρ (F, G) =

XF (G)
,
|e(F)|
ρ
XF (Kn )
Z

∏

[0,1]|v(F)| i j∈e(F)

κ(xi , x j )

∏

i∈v(F)

dxi .

From Definition S.9, we may use Lemma S.6 and that emb(F, Kn ) = (n)|v(F)| ,
with (n)|v(F)| = n!/(n − |v(F)|)! the falling factorial, and conclude that
E indk (F, G) = indk (F, Kn ) P{F ⊂ G}

= indk (F, Kn )ρ |e(F)| s(F, κ)
= indk (F, F)XF (Kn )ρ |e(F)| s(F, κ)
ind (F, F)s(F, κ)
= (n)|v(F)| ρ |e(F)| k
.
aut(F)

(S.17)

Inspecting (S.17), we quantify the order of magnitude of the expected number
of walk-induced copies of F in the random graph model of Definition S.8 as
follows.
Definition S.10 (Order ΨF of the expected number of walks inducing F [6]). Fix
a graph F, a network size n and a kernel κ. Let ΨF be such that
ΨF = n|v(F)| ρ |e(F)| .

5.2

Dominating closed walks in kernel-based random graphs

When considering sequences {Gn } of kernel-based random graphs, it is convenient
to work only with the sequence {ρ}, rather than with the sequences {E indk (F, G)}
for F ∈ Wk , as we now show.

Remark S.4. Fix a walk length k and a sequence of random graphs {Gn } where
each Gn is generated in accordance with G(n, ρκ) from Definition S.8 for some
sequence {ρ} taking values in (0, kκk−1
∞ ). In this setting, if nρ = ω(1), then Assumptions S.1 and S.2 are satisfied, and so Theorem S.1 applies to the sequence
of graphs {Gn }. To see this, first observe that from (S.5) and (S.17), we have
E|Wk (Gn )| =

∑

F∈Wk

E indk (F, Gn )
47

=

∑ (n)|v(F)|ρ |e(F)|

F∈Wk

indk (F, F)s(F, κ)
aut(F)

> 0,
as s 6= 0 by construction, Wk is non-empty and ρ > 0 by assumption. Therefore,
we see directly that Assumption S.1 is satisfied. Second, for w and w0 two closed
k-walks such that w0 is an extension of w (see Definition S.3), from Lemma S.5
and recalling from Definition S.3 that |e(Fw0 )| − |e(Fw )| ≤ 1, we obtain
|v(Gn )| E ϕ(w0 , Gn ) n E XFw0 (Gn )/XFw0 (Kn )
=
E ϕ(w, Gn )
E XFw (Gn )/XFw (Kn )
=

nXF 0 (Kn ) ρ |e(Fw0 )| E sρ (Fw0 , Gn )/XF 0 (Kn )
w

w

XFw (Kn ) ρ

|e(Fw )|

E sρ (Fw , Gn )/XFw (Kn )

= nρ |e(Fw0 )|−|e(Fw )| s(Fw0 , κ)/s(Fw , κ)
= Ω(nρ),
since ρ < kκk−1
∞ ≤ 1. Therefore {Gn } verifies Assumption S.2 if nρ = ω(1).
A uniform scaling of network edge probabilities is implicit to the model of
Definition S.8. This uniform scaling will permit us to derive explicit error rates
ek∗ , which for every
for the remainder terms in Theorem S.1. We now introduce W
∗
fixed n plays a role analogous to Wk ({Gn }) but is constructed directly from ΨF .
This simplification enables us to introduce Wk0 , which contains second-order or
sub-dominating walk-induced subgraphs, and will be crucial to obtaining error
rates in Theorem S.1.
ek∗ ,Wk0 of dominating walk-induced subgraphs). Fix a walk
Definition S.11 (Sets W
ek∗ , and
length k ∈ N. Define the set of dominating walk-induced subgraphs to be W
the set of sub-dominating walk-induced subgraphs to be Wk0 , where the two sets
satisfy the following equations
ek∗ = {F ∈ Wk : ΨF = max Ψ 0 },
W
F
0
Wk0

= {F

∈ Wk∗

F ∈Wk

: ΨF = max ΨF 0 };
F 0 ∈Wk∗

48

ek∗ .
Wk∗ = Wk \ W

Lemma S.7. Consider the setting of Definition S.8. Fix an integer k > 3 and a
scalar ρ ∈ (0, kκk−1
∞ ) such that nρ > 1 for all integers n > k. Set
k∗ =

log n
√ ,
log nρ

and recall that Ck is the k-cycle, Ck Pl is the (k, l)-tadpole and Tk is the set of
unlabeled trees on k vertices. Then for every fixed n > k,


if k is odd, or if k is even and k > k∗ ,
{Ck }
ek∗ = {Ck } ∪ Tk/2+1 if k is even and k = k∗ for k∗ an integer,
W


Tk/2+1
if k is even and k < k∗ .


{Ck−2 P2 }
if k is odd, or if k is even and k > k∗ + 2,





{Ck−2 P2 } ∪ Tk/2+1 if k is even and k = k∗ + 2 for k∗ an integer,





if k is even and k ∈ (k∗ , k∗ + 2),
Tk/2+1
Wk0 = {Ck−2 P2 } ∪ Tk/2
if k is even and k = k∗ for k∗ an integer,



{Ck }
if k is even and k ∈ (k∗ − 2, k∗ ),





{Ck } ∪ Tk/2
if k is even and k = k∗ − 2 for k∗ an integer,



T
if k is even and k < k∗ − 2.
k/2
(S.18)
Proof. First, observe that maxF∈Wk ΨF exists, since Wk is finite and non-empty for
all k ≥ 2. Now write
ΨF = (nρ)|v(F)| ρ |e(F)|−|v(F)| .
We draw two conclusions from the above equation: First, the hypothesis nρ > 1
implies that ΨF is monotone increasing in |v(F)| for fixed |e(F)| − |v(F)|. Second,
the hypothesis 0 < ρ < kκk−1
∞ ≤ 1 implies that ΨF is monotone decreasing in
|e(F)| − |v(F)| for fixed |v(F)|. Using these two facts we proceed as follows:
1. Suppose |e(F)| = |v(F)|. Then ΨF = (nρ)|v(F)| . By monotonicity, we have
maxF∈Wk :|e(F)|=|v(F)| ΨF = (nρ)k , achieved uniquely by the k-cycle Ck , since
no other closed k-walk visits k vertices.
2. Suppose |e(F)| > |v(F)|. Then ΨF = (nρ)|v(F)| ρ |e(F)|−|v(F)| < (nρ)|v(F)| ≤
(nρ)k for Ck , since ρ < 1.
49

3. Suppose |e(F)| < |v(F)|. Since an odd closed walk contains an odd cycle, F ∈ Wk=2r+1 ⇒ |e(F)| ≥ |v(F)|. By Lemma S.1, F ∈ Wk=2r ⇔ F ∈
∪ri=1 Ti+1 , implying that |e(F)| = |v(F)| − 1 ≤ k/2. Thus
ΨF = (nρ)|v(F)| ρ |e(F)|−|v(F)| = (nρ)|v(F)| ρ −1 ≤ (nρ)k/2+1 ρ −1
by monotonicity, with
max

F∈Wk=2r : |e(F)|<|v(F)|

ΨF = (nρ)k/2+1 ρ −1

achieved by all (k/2 + 1)-trees F ∈ Tk/2+1 for k even; this shape is not
achievable for k odd.
Thus, if k is odd we only compare Cases 1 and 2 to determine the maximizer of
ΨF over Wk . We see that Case 1 always dominates Case 2. If k is even, we may still
discard Case 2 in favor of Case 1, leaving us to compare which of Cases 1 and 3
∗
∗
dominates. Setting (nρ)k = (nρ)k /2+1 ρ −1 and solving for k∗ , we determine the
ek∗ as claimed.
two forms of W
ek∗ :
Our next step is to determine the maximizer of ΨF over Wk \ W
1. If k ≥ 5 is odd, we repeat the above arguments mutatis mutandis, with the
(k − 2, 1)-tadpole Ck−2 P2 replacing the cycle Ck in Case 1. This follows by
Lemma S.1, which asserts that it is the unique F ∈ Wk such that |v(F)| =
|e(F)| = k − 1. Hence maxF∈Wk \{Ck } ΨF = (nρ)k−1 .
2. If k is even and greater than k∗ we must compare Cases 1 and 3. In this
ek∗ and Ck−2 P2 replaces Ck in Case 1, so that it is sufficient
setting, Ck ∈ W
to compare ΨCk−2 P2 = (nρ)k−1 to ΨF = (nρ)k/2+1 ρ −1 for F any (k/2 + 1)∗
∗
tree. Since we have that (nρ)(k +2)−1 = (nρ)(k +2)/2+1 ρ −1 , we obtain the
first three lines of (S.18).
3. If k is even and equal to k∗ , for k∗ an integer, we must compare Cases 1
ek∗ and Tk/2+1 ⊂ W
ek∗ , hence Ck−2 P2 replaces
and 3. In this setting, Ck ∈ W
Ck in Case 1 and Tk/2 replaces Tk/2+1 in Case 3 so that it is sufficient to
compare ΨCk−2 P2 = (nρ)k−1 to ΨF = (nρ)k/2 ρ −1 for F any (k/2)-tree. Since

we have that (nρ)k

∗

−1

= (nρ)k

∗

/2 −1

ρ

50

, we obtain the fourth line of (S.18).

4. If k is even and smaller than k∗ we must compare Cases 1 and 3. In this
ek∗ and Tk/2 replaces Tk/2+1 in Case 3, so that it is
setting case Tk/2+1 = W

sufficient to compare ΨCk = (nρ)k to ΨF = (nρ)k/2 ρ −1 for F a (k/2)-tree.
Since we have that (nρ)(k
lines of (S.18).

∗

−2)

= (nρ)(k

∗

−2)/2 −1

ρ

, we obtain the last three

ek∗ and Wk0 in the setting of Definition S.8.
We have now fully described the sets W
In this way Lemma S.7 will allow us to show that the number of k-walks inducing
ek∗ dominates (in expectation) the number of k-walks inducing
the elements of W
any other graph.

5.3

Expected number of walks mapping out trees and cycles

Definition S.12 (Walk embedding density νk (F, κ)). Fix a graph F, a walk length
k, and a generalized random graph kernel κ. In analogy to the kernel embedding
density of Definition S.9, define
νk (F, κ) =

indk (F, F)
s(F, κ).
aut(F)

Recalling ΨF = n|v(F)| ρ |e(F)| from Definition S.10, we see that νk (F, κ) is the
limit of E indk (F, G)/ΨF . Furthermore, νk (F, κ) > 0 whenever indk (F, F) > 0.
Theorem S.2. Fix k > 3 and n ∈ N such that n > k. Let G be a random graph
distributed according to the kernel-based random graph model G(n, ρκ) as given
√
by Definition S.8. Set µ = nρ and assume that µ > 1. Then, with k∗ = log n/log µ,
1. If k is odd or k is even and k > k∗ + 2:
E|Wk (G)|
1
= 1+
E|{w ∈ Wk (G) : Fw ≡ Ck }|
µ




νk (Ck−2 P2 , κ)
+ ε1 (n; k, κ) .
νk (Ck , κ)

2. If k is even and k = k∗ + 2 for k∗ an integer:
E|Wk (G)|
=1
E|{w ∈ Wk (G) : Fw ≡ Ck }|
!
1 νk (Ck−2 P2 , κ) + ∑T ∈Tk/2+1 νk (T, κ)
+
+ ε2 (n; k, κ) .
µ
νk (Ck , κ)
51

3. If k is even and k ∈ (k∗ , k∗ + 2):
1
E|Wk (G)|
= 1+ √
∗
E|{w ∈ Wk (G) : Fw ≡ Ck }|
µ k−k

∑T ∈Tk/2+1 νk (T, κ)
νk (Ck , κ)

!
+ ε3 (n; k, κ) .

4. If k is even and k = k∗ for k∗ an integer:
E|Wk (G)|
E {w ∈ Wk (G) : Fw ∈ {Ck } ∪ Tk/2+1 }

=1

νk (Ck−2 P2 , κ) + ∑T ∈Tk/2 νk (T, κ)

1
+
µ

νk (Ck , κ) + ∑T ∈Tk/2+1 νk (T, κ)

!
+ ε4 (n; k, κ) .

5. If k is even and k ∈ (k∗ − 2, k∗ ):
E|Wk (G)|

=1

E {w ∈ Wk (G) : Fw ∈ Tk/2+1 }
+√

1
µk

∗

−k

!
νk (Ck , κ)
+ ε5 (n; k, κ) .
∑T ∈Tk/2+1 νk (T, κ)

6. If k is even and k = k∗ − 2 for k∗ an integer:
E|Wk (G)|
E {w ∈ Wk (G) : Fw ∈ Tk/2+1 }
1
+
µ

=1

νk (Ck , κ) + ∑T ∈Tk/2 νk (T, κ)
∑T ∈Tk/2+1 νk (T, κ)

!
+ ε6 (n; k, κ) .

7. If k is even and k < k∗ − 2:
1
= 1+
µ
E {w ∈ Wk (G) : Fw ∈ Tk/2+1 }
E|Wk (G)|

∑T ∈Tk/2 νk (T, κ)

∑T ∈Tk/2+1 νk (T, κ)

!
+ ε7 (n; k, κ) .

Error terms {εi (n; k, κ)} for 1 ≤ i ≤ 7 are upper bounded by the quantity
n ∑F∈W \We ∗ νk (F, κ)/(n)k ∑F∈We ∗ νk (F, κ). Each error term is positive, and furtherk
k
k
more is such that if µ diverges, then lim εi (n; k, κ) = 0.
k

n→∞

52

Proof. Combining Definition S.11 with (S.5) and taking expectations, we have
E|Wk (G)| =

E indk (F ∗ , G) + ∑
∑
∗
∗

ek
F ∈W

E indk (F, G).

(S.19)

ek∗
F∈W

Then, from Definition S.9 and Lemma S.6, we obtain directly that E indk (F, G) =
ΨF νk (F, κ)(n)|v(F)| /n|v(F)| . Thus, from (S.19) we recover
E|Wk (G)|

= 1+

ek∗ }
E {w ∈ Wk (G) : Fw ∈ W

= 1+

∑F∈We ∗ E indk (F, G)
k

∗
∑F ∗ ∈Wek∗ E indk (F , G)

∑F∈We ∗ ΨF νk (F, κ)

(n)|v(F)|

k

∑F

∗

ek∗
∈W

n|v(F)|
(n)|v(F ∗ )|

ΨF ∗ νk (F ∗ , κ)

n|v(F

∗

·

)|

ek∗ and Wk0 . Thus, for any fixed
From Lemma S.7, we know that Ψ is constant over W
∗
∗
0
0
ek and F ∈ Wk , we may write
F ∈W
!
0
ΨF 0 ∑F 0 ∈Wk0 νk (F , κ)
E|Wk (G)|
+ ε(n; k, κ) ,
= 1+
ΨF ∗ ∑F ∗ ∈We ∗ νk (F ∗ , κ)
e ∗}
E {w ∈ W (G) : F ∈ W
k

w

k

k

(S.20)

where


0

(n)|v(F)|

0



∑F 0 ∈Wk0 νk (F , κ) 
 ∑F 0 ∈Wk0 νk (F , κ) n|v(F)|
ε(n; k, κ) = 
−

(n)|v(F ∗ )|
∗
∗
∑F ∗ ∈Wek∗ νk (F , κ) |v(F ∗ )|
∑F ∗ ∈Wek∗ νk (F , κ)
n

Ψ

+

∑F∈Wk \(Wek∗ ∪Wk0 ) Ψ F0 νk (F, κ)
F

∗

∑F ∗ ∈Wek∗ νk (F , κ)

(n)|v(F)|
n|v(F)|

(n)|v(F ∗ )|
n|v(F

∗

. (S.21)

)|

We first consider the second term in (S.20). A direct consequence of Lemma S.7
ek∗ , we have
is that for k > 3 and any pair F 0 , F ∗ ∈ Wk0 × W
 ∗
ΨF −1


if k is odd or k is even and either |k − k∗ | ≥ 2 or k = k∗ ,
Ψ 0 µ → 1
F
∗
∗
Ψ


 F µ −|k−k |/2 → 1 if k is even and 0 < |k − k∗ | < 2.
ΨF 0
53

Then, enumerating the cases of Lemma S.7 in the context of (S.20), we match the
first- and second-order terms of the expressions in the statement of Theorem S.2.
Next, we consider ε(n; k, κ) from (S.21), which is the general form of the
εi (n; k, κ) in the statement of Theorem S.2. The upper bound follows from noting
that: i) all terms are positive; ii) ΨF /ΨF 0 < 1 by construction; and iii) the map
x :7→ (n)x /nx is decreasing with x, and bounded above by unity.
We finally consider the limit of ε(n; k, κ) as n tends to infinity when µ diverges.
The first term in parentheses in (S.21) is tending to zero, as (n)x /nx → 1 as n → ∞
for any fixed x. The last term in (S.21) is of order maxF∈W \(We ∗ ∪W 0 ) ΨF /ΨF 0 . Let
k

k

k

F 00 ∈ argmaxF∈W \(We ∗ ∪W 0 ) ΨF . Using the argument of Lemma S.7, F 00 is either a
k

k

k

tree or has the same order of magnitude Ψ as a tadpole. If F 0 and F 00 are both
trees or tadpoles, we directly have ΨF 0 /ΨF 00 ≥ nρ = µ → ∞, since F 0 must contain more edges than F 00 . If instead F 0 is a tree and F 00 is a tadpole, we have
ΨF 0 /ΨF 00 = (nρ)l /n for some l > 0, since the tadpole must then contain more
edges than the tree. On the other hand, if F 0 is a tadpole and F 00 is a tree, we have
√ ∗
ΨF 0 /ΨF 00 = n/(nρ)l , again for some l > 0. Recalling that µ k = n, we recover
∗

that in both cases ΨF 0 /ΨF 00 = µ |l−k /2| → ∞. The case 2l = k∗ is impossible, since
then ΨF 0 = ΨF 00 and F 00 would be an element of Wk0 , which is in contradiction
with the definition of F 00 . Finally, in all cases considered ΨF 00 /ΨF 0 = o(1), so that
lim ε(n; k, κ) = 0, which concludes the proof.
n→∞

Theorem S.2 describes how the total number of closed walks of even length
shorter than k∗ is dominated (in expectation) by trees or by cycles. The balance
between trees and cycles that we describe within generalized random graphs extends a number of known results [5, 7, 8]: √
i) Bollobás & Riordan [5, Lemma 3.10]
show that if the degrees grow faster than n, cycles dominate for all k, which is
consistent with our result, since then k∗ < 4; ii) Bollobás et al. [7, Lemma 2.10]
show that the number of cycles is influenced more strongly by increased sparsity
than is the number of trees; and iii) Bollobás & Riordan [8, Eq. 7] establish that
generalized random graphs are tree-like when µ = O(1). Finally, in the dense
graph regime, Lovász [2, p. 63] relates counts of k-cycles to the sum of the kth
power of the eigenvalues of a graph’s adjacency matrix, and hence the expected
number of closed k-walks (see (S.5)).
Remark S.5. If k = 2, E|W2 (G)| = E|{w ∈ W2 (G) : Fw ≡ K2 }|, while if k = 3 we
ek∗ does
have E|W3 (G)| = E|{w ∈ W3 (G) : Fw ≡ K3 }|. Thus, in these two cases, W
not depend on either the size or the density of the graph G.
54

1
Predicted rate
Estimated rate

0.9

Rate of convergence

0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

0

0.2

0.4

0.6

0.8

1

α

Figure S2 | Predicted asymptotic rates of convergence β (α; 4) (solid blue line)
and rates of convergence estimated in a simulation experiment (green stars).
The relative magnitudes of different terms presented in Theorem S.2 are driven
by the growth of µ. The rate at which dominance occurs depends on how quickly
µ = nρ grows relative to n. To emphasize this point, we fix k = 4 and consider the
case where µ = 2nα > 1 for α ∈ [0, 1]. From Theorem S.2 we know that the rate
ek∗ }|—
of convergence towards unity of the ratio E |Wk (G)|/E |{w ∈ Wk (G) : Fw ∈ W
which we here denote by β (α; k) for convenience—is
β (α; k) = α min(1, |k − k∗ |/2).
Figure S2 shows an example of β (α; 4) as a function of α ∈ [0, 1], and compares it to the rate of convergence observed in simulations. For the purposes of
this figure, we first fix a kernel κ matching a mixed membership model with
three communities [9, 10], in accordance with Definition S.8. We then let Gi j
be a random graph distributed according to G(2 j , 2(2 j )α−1 κ). Then, for α ∈
{0, 1/20, 2/20, . . . , 1}, we evaluate through repeated simulation the slope of the
following set of points:
(
!!)
E |Wk (Gi j )|
j
log(2 ), log
−1
.
∑F∈W4∗ E indk (F, Gi j )
j∈[7,12]

We then see from Fig. S2 that the asymptotic rates presented in Theorem S.2 show
reasonable alignment with those estimated through simulation.
55

5.4

Domination of walks mapping out cycles

We now determine dominating sets of non-backtracking, tailless closed walks in the
generalized random graph setting. We will see that in this setting cycles dominate,
independently of the sparsity the graph, up to the point where the network is no
longer connected. As noted in the main text, this result quantifies the observations
of [11] for community detection, where non-backtracking, tailless closed walks
are observed to improve spectral methods in the sparse graph setting.
We first give definitions for non-backtracking, tailless closed walks that mirror
those we have already shown to hold for closed walks in general. We begin by
adapting Definition S.1 to non-backtracking, tailless closed walks. We recall that a
closed walk is non-backtracking if it never visits the same edge twice in succession.
It is tailless if the first and last edges it traverses are different. We then proceed to
adapt all the definitions and results presented in the previous section.
Definition S.13 (Set Wkb (G) of non-backtracking, tailless closed k-walks). Fix a
simple graph G and k ∈ N. A non-backtracking, tailless closed walk w of length k
in G is a sequence of adjacent vertices in G satisfying
∀0 ≤ i ≤ k,

vi 6= v(i+2) mod k ,

b
where ∪ki=0 {vi } ⊂ v(G), v0 = vk and ∪k−1
i=0 {vi vi+1 } ⊂ e(G). We denote by Wk (G)
the set of all non-backtracking, tailless closed k-walks.

In analogy to Definition S.2, we introduce the set of subgraphs induced by
non-backtracking, tailless closed walks.
Definition S.14 (Set Wkb of unlabeled graphs induced by non-backtracking, tailless
closed k-walks). We denote by Wkb the set of all unlabeled graphs induced by
non-backtracking, tailless closed walks of length k:
Wkb = {F ∈ Wk : ∃w ∈ Wkb (Kk ), F ≡ Fw }.
We start by introducing three basic properties of such walks.
Lemma S.8 (Properties of Wkb ). Fix k > 2. Then, Wkb is non-empty, and any F ∈ Wkb
verifies the following properties:
1. Every node in F has degree at least 2, and hence |e(F)| ≥ |v(F)|.
2. If |e(F)| = |v(F)|, then F ≡ C|v(F)| and |v(F)| is a divisor of k greater than
or equal to 3.
56

3. If |e(F)| = |v(F)| + 1 = k, then k ≥ 6 and there exists p ∈ {3, 4, . . . , bk/2c}
such that F ≡ C pCk−p .
Proof. We prove the stated results in succession.
Proof of 1: Since a non-backtracking, tailless closed walk is a walk and therefore the graph it induces connected, we immediately conclude by Lemma S.1 that
all nodes in F have positive degree. We proceed to establish the result by contradiction. Assume F contains a node of degree one, and call it o. Furthermore call t the
only node connected to o. Fix w to be any non-backtracking, tailless closed walk
such that Fw = F. Then tot must be part of w, otherwise w cannot be a closed walk
such that Fw = F. However, since w is non-backtracking, this is not permitted, and
we obtain a contradiction. We can therefore conclude that no node can have degree unity; i.e., in a graph where every node can be visited by a non-backtracking,
tailless closed walk, no pendant nodes can be present. Hence, since every F ∈ Wkb
is connected, and F cannot be a tree, it follows that |e(F)| ≥ |v(F)|.
Proof of 2: We call di the degree of the node labeled i in F. Since |e(F)| =
|v(F)|, we have
2|e(F)|
|v(F)|−1 ∑ di =
= 2.
(S.22)
|v(F)|
i∈v(F)

On the other hand, from Item 1 of Lemma S.8, for all i ∈ v(F), di ≥ 2. Thus, the
equality of (S.22) is possible only if for all i, di = 2. Then all nodes in F have
degree two, and since F is connected by Item 2 of Lemma S.1, we conclude that
F ≡ C|v(F)| . Finally, for a non-backtracking, tailless closed k-walk to induce C|v(F)| ,
it must traverse C|v(F)| one or more times. Hence, |v(F)| must divide k.

Proof of 3: Fix w to be any non-backtracking, tailless closed walk such that
Fw = F. Since |v(F)| = k − 1, w must visit one node in v(F) exactly twice, and
all the other nodes in v(F) exactly once. Call o the twice visited node. As cyclic
permutations of w are still non-backtracking, tailless closed walks, assume without
loss of generality that w starts at o and write w = ov1 · · · vk−1 o. Let t ∈ {3, . . . , k −3}
be such that vt = o. Since w visits o exactly twice, and a non-backtracking, tailless
closed walk cannot return to o in less than three steps, t exists and is unique. Since
t exists, k − 3 ≥ 3, and hence k ≥ 6.
Let w1 = ov1 · · · vt−1 o and w2 = ovt+1 · · · vk−1 o. Then, w1 and w2 are two nonbacktracking, tailless closed walks. Since |e(F)| = k, w visits a different edge at
each step, w1 and w2 also visit different edges at each step. Thus, |e(Fw1 )| = t =
|v(Fw1 )|, and by Item 2 of Lemma S.8, Fw1 ≡ Ct . By the same argument, Fw2 ≡ Ck−t .
57

Since Fw1 ∩ Fw2 = ({o}, 0),
/ we have that F ≡ Ct Ck−t . Finally, we conclude that
t ∈ {3, . . . , bk/2c}, since 3 ≤ min{t, k − t} ≤ bk/2c.

In the same fashion as for Wk in the case of closed k-walks, Wkb allows us to
partition the set of all non-backtracking, tailless closed k-walks Wkb (G) in any
simple graph G as follows:
o
G n
Wkb (G) =
w ∈ Wkb (G) : Fw ≡ F .
(S.23)
F∈Wkb

This leads naturally to the following definitions, mirroring Definitions S.4 and S.6.
Definition S.15 (Number indbk (F, G) of non-backtracking, tailless closed k-walks
in G inducing an isomorphic copy of F). Fix a walk length k and two simple graphs
F and G. We write
n
o
indbk (F, G) = w ∈ Wkb (G) : Fw ≡ F
for the number of non-backtracking, tailless closed walks of length k in G that
induce a subgraph of G isomorphic to F.
In analogy to Definition S.11, we introduce the sets of dominating non-backtracking, tailless walk-induced subgraphs in generalized random graphs. Recall
from Definition S.10 that for fixed n and ρ, the map Ψ is such that for a graph F,
ΨF = n|v(F)| ρ |e(F)| .
ekb∗ ,Wkb 0 of dominating subgraphs induced by non-backDefinition S.16 (Sets W
tracking, tailless closed walks). Fix a walk length k ∈ N and let
ekb∗ = {F ∈ Wkb : ΨF = max Ψ 0 },
W
F
F 0 ∈Wkb

ekb∗ : ΨF = max Ψ 0 };
Wkb 0 = {F ∈ W
F
F

0

ekb∗
∈W

ekb∗ .
ekb∗ = Wkb \ W
W

From (S.23) we recover the partition
Wkb (G) =

∑

ekb∗
F∈W

indbk (F, G) +

∑

indbk (F, G).

(S.24)

ekb∗
F∈W

ekb∗ ,Wkb 0 so as to control the two terms on the rightWe now characterize the sets W
hand side of (S.24). The following result is analogous to Lemma S.7.
58

Lemma S.9. Consider the setting of Definition S.8. Fix an integer k > 3 and a
scalar ρ ∈ (0, kκk−1
) such that nρ > 1 for all integers n > k. As in Lemma S.7, set
√ ∞
k∗ = log n/ log nρ, Recall that Ck is the k-cycle and CkCl is the (k, l)-lemniscate.
Finally, denote by hk the largest divisor of k in {3, 4, . . . , max(3, bk/2c}, and if
there is no such divisor (i.e., if k is prime or equal to 4), then set hk to −∞. Then
ekb∗ = {Ck }
W

0/



{C }
hk
Wkb 0 =

{C

 hk } ∪ {C pCk−p : p ∈ {3, 4, . . . , bk/2c}}

{C pCk−p : p ∈ {3, 4, . . . , bk/2c}}

if k ≤ 5,
if k − hk < k∗ /2,
if k − hk = k∗ /2,
otherwise.

(S.25)

Proof. The proof parallels that of Lemma S.7. The key observation is that ΨF is
monotone increasing in |v(F)| for fixed |e(F)| − |v(F)|, and monotone decreasing
in |e(F)| − |v(F)| for fixed |v(F)|. We enumerate the possible cases as follows:
1. Suppose |e(F)| = |v(F)|. Then ΨF = (nρ)|v(F)| . By monotonicity, we have
max

F∈Wkb :|e(F)|=|v(F)|

ΨF = (nρ)k ,

achieved uniquely by the k-cycle Ck , since no other non-backtracking, tailless
closed k-walk visits k vertices.
2. Suppose |e(F)| > |v(F)|. Then, since ρ < kκk−1
∞ ≤ 1,
ΨF = (nρ)|v(F)| ρ |e(F)|−|v(F)| < (nρ)|v(F)| ≤ (nρ)k .
This last upper bound is not attained, as |e(F)| > |v(F)| and ρ < 1.
Finally, in contrast to Lemma S.7, we need not consider the case in which |e(F)| <
|v(F)|. This follows from the observation discussed in Item 1 of Lemma S.8: A
closed walk inducing a tree will backtrack at each of this tree’s leaves, since these
have degree 1. Hence, a non-backtracking, tailless closed walk cannot induce a
tree, and thus |e(Fw )| ≥ |v(Fw )| for any non-backtracking, tailless closed walk w.
ekb∗ = {Ck } as claimed.
Thus we conclude W
ekb∗ = 0,
We now consider Wkb 0 . First, if k ≤ 5, then Wkb = {Ck }. Thus, Wkb \ W
/
b0
and Wk = 0,
/ as per Definition S.16, and so we obtain the first case in (S.25).
59

Now, if instead k > 5, we show that there are only two subgraphs to consider.
Paralleling Case 1 above, we must consider the largest cycle different from Ck
that can be induced by a non-backtracking, tailless closed k-walk. From Item 2
of Lemma S.8, we know that this subgraph is Chk . As for Case 2, since |e(F)| −
|v(F)| ≥ 1 and |v(F)| < k, we have
ΨF = (nρ)|v(F)| ρ |e(F)|−|v(F)| ≤ (nρ)|v(F)| ρ ≤ (nρ)k−1 ρ.

By Item 3 of Lemma S.8, this upper bound is attained solely by ΨCpCk−p for p ∈
{3, 4, . . . , bk/2c}. Thus, we only need to consider and compare ΨCh = (nρ)hk and
∗
∗
k
ΨCpCk−p = (nρ)k−1 ρ. Since (nρ)k /2 = n, we have equality if (nρ)k−hk = (nρ)k /2 ,
and we obtain the last three items in (S.25). This completes the proof.
We are now equipped to describe how non-backtracking, tailless closed walks
are dominated by cycles, paralleling Theorem S.2. Here we will prove that the
ratio E |Wkb (G)|/E |{w ∈ Wkb (G) : Fw ≡ Ck }| tends to 1. It is straightforward to
show that for k ∈ {3, 4, 5} we have exact equality—i.e., Wkb (G) is equal to the set
{w ∈ Wkb (G) : Fw ≡ Ck }—and thus in what follows we assume k ≥ 6.

Theorem S.3. Fix a walk length k ≥ 6 and a network size n > k. Let G be distributed according to the generalized random graph model G(n, ρκ) from Definition S.8, and assume nρ > 1. Set µ = nρ and let hk be the largest divisor of k in
{3, 4, . . . , bk/2c}. If there is no such divisor, i.e., if k is prime, set hk to −∞. Then:
E Wkb (G)
E

{w ∈ Wkb (G) : Fw

= 1+

≡ Ck }



νk (Chk , κ)
1

b

+ ε1 (n; k, κ)
if k − hk < k∗ /2,


k−hk
ν
(C
,
κ)

µ
k k






ν (C , κ) + ∑ p∈{3,4,...,bk/2c} νk (C pCk−p , κ)

 1 k hk

n
νk (Ck , κ)



b

if k − hk = k∗ /2,
+ε2 (n; k, κ)










1 ∑ p∈{3,4,...,bk/2c} νk (C pCk−p , κ)
b


+ ε3 (n; k, κ)
otherwise.
n
νk (Ck , κ)

In all cases εib (n; k, κ) is bounded by nk ∑F∈W b \We b∗ νk (F, κ)/(n)k ∑F∈We b∗ νk (F, κ),
k
k
k
and if µ diverges in n, then lim εib (n; k, κ) = 0.
n→∞

60

Proof. The proof proceeds in the same fashion as that of Theorem S.2. We express
the ratio E |Wkb (G)|/E |{w ∈ Wkb (G) : Fw ≡ Ck }| using the partition induced by
ekb∗ and Wkb 0 , and then control the error terms by using Lemma S.9.
W
To proceed we introduce the following notation:
νkb (F, κ) =

indbk (F, F)
s(F, κ).
aut(F)

This notation will only be used in this proof, and parallels the introduction of
νk (F, κ) in Definition S.12. To write the theorem statement using only νk notation,
we will use that νkb (Ck , κ) = νk (Ck , κ) and that νkb (C pCk−p , κ) = νk (C pCk−p , κ)
for p ∈ {3, 4, . . . , bk/2c}.
We first write E |Wkb (G)|/E |{w ∈ Wkb (G) : Fw ≡ Ck }| using (S.24), which we
recall here:
Wkb (G) = ∑ indbk (F, G) + ∑ indbk (F, G).
ekb∗
F∈W

ekb∗
F∈W

By taking expectations and considering the ratio of the terms on the right-hand
side of this expression, we obtain:
b

E Wkb (G)
E {w ∈ Wkb (G) : Fw ≡ Ck }

= 1+

∑F∈We b∗ E indk (F, G)
k

E indbk (Ck , G)
b

= 1+

∑F∈We b∗ ΨF νk (F, κ)
k

ΨCk νkb (Ck , κ)

.

(S.26)

Then, we use Lemma S.9 to control ΨF ∗ /ΨF 0 for all pairs of subgraphs F ∗ ∈
ekb∗ and F 0 ∈ Wkb 0 . This parallels our use of Lemma S.7 in the proof of Theorem S.2.
W
ekb∗ and F 0 ∈ Wkb 0 ,
From Lemma S.9, we have that for all pairs of subgraphs F ∗ ∈ W
the ratio ΨF ∗ /ΨF 0 is determined by the number of edges and vertices of F ∗ and
F 0 . We note from Lemma S.9 (referring back to the definition of hk ) that it follows
that |v(Fw )| = |e(Fw )| = k. For k ≥ 6, if k < k∗ /2 + hk then |v(Fw0 )| = |e(Fw0 )| = hk ,
while if k > k∗ /2 + hk then |v(Fw0 )| = k − 1 and |e(Fw0 )| = k. In conjunction with
the form of ΨF , this implies that
 ∗
ΨF hk −k


→ 1 if k < k∗ /2 + hk ,
Ψ 0 µ
F
(S.27)
∗ −1
Ψ

F


n →1
otherwise.
ΨF 0
61

ekb∗ and F 0 ∈ Wkb 0 . Using both (S.26) and (S.27) yields—in
We then fix F ∗ ∈ W
the same fashion as in (S.20) and (S.21)—the following expression:


b 0
E Wkb (G)
ν
(F
,
κ)
0
b
0
∑
k
∗
Ψ
F ∈Wk
= 1+ F 
+ ε b (n; k, κ),
b
b
ΨF 0
νk (Ck , κ)
E {w ∈ W (G) : F ≡ C }
k

w

k

(S.28)

where


(n)|v(F 00 )|
b 00
ν
(F
,
κ)
00
b
0
∑
00
k
 F ∈Wk
n|v(F )|
ε b (n; k, κ) = 

(n)
νkb (Ck , κ) k k
n



b 00
∑F 00 ∈W b 0 νk (F , κ) 
k
+
−

b
νk (Ck , κ)
Ψ

b

∑F∈W k \({C } S W b 0 ) Ψ F0 νk (F, κ)
b

k

k

F

νkb (Ck , κ)

(n)k
nk

(n)|v(F)|
n|v(F)|

. (S.29)

This is the general form of the εib (n; k, κ) in the statement of Theorem S.3. We
ekb∗
note that (S.28) provides all of the cases of Theorem S.3, using the forms of W
and Wkb 0 provided in Lemma S.9.
We now bound ε b (n; k, κ) and compute its order in the case where µ → ∞. Our
method of bounding exactly parallels that of ε(n; k, κ) in the proof of Theorem S.2.
The upper bound follows from noting that: i) all terms are positive; ii) ΨF /ΨF 0 < 1
by construction for F ∈ Wbk \ ({Ck } ∪Wkb 0 ); and iii) the map x 7→ (n)x /nx is decreasing in x > 0, and bounded above by unity. Now consider the order of ε b (n; k, κ) as
n tends to infinity when µ diverges. The first ratio in (S.29) tends to zero, since
(n)x /nx → 1 as n → ∞ for any fixed x > 0. The last term in (S.29) has the same
order of magnitude as maxF∈W k \({C } S W b 0 ) ΨF /ΨF 0 . Following the arguments of
b
k
k
Lemma S.9, in the same fashion as in Theorem S.2, this ratio is smaller than µ −1 .
Thus we obtain the claimed order of ε b (n; k, κ), thereby concluding the proof.

6
6.1

Dominating walks in scale-free random graphs
Scale-free inhomogeneous random graphs

We next determine the set of dominating closed walks for the case of inhomogeneous random graphs with power-law degree distributions [12, 13].
62

Definition S.17 (Inhomogeneous random graph with power-law degrees). Fix an
exponent γ > 0 and a scalar θ ∈ (0, 1]. Let G be the simple random graph whose
adjacency matrix A has elements generated independently according to
P(Ai j = 1) = θ 2 · (i j)−γ ,

1 ≤ i < j ≤ n,

with A ji = Ai j for 1 ≤ i < j ≤ n, and Aii = 0 for 1 ≤ i ≤ n.

The following proposition describes the expected number of unlabeled copies
of a fixed graph in networks generated according to Definition S.17.
Proposition S.4. Fix an exponent γ > 0 and a sequence {θn } taking values in (0, 1].
Consider a sequence of random graphs {Gn } on n nodes, generated according to
Definition S.17. Fix a graph F on v vertices with strictly positive degrees d =
(d1 , . . . , dv ) enumerated in non-decreasing order, with


/
dt γ < 1 for t ∈ {1, . . . , q}, setting q = 0 if {t : dt γ < 1} = 0,
dt γ = 1 for t ∈ {q + 1, . . . , h}, setting h = q if {t : dt γ = 1} = 0,
/


dt γ > 1 for t ∈ {h + 1, . . . , v}, setting v = h if {t : dt γ > 1} = 0.
/
Then, the expected number of unlabeled copies of F in Gn takes the following form:

1
q
v
Cγ (dh+1 , . . . , dv ) {h<v}
h−q 
∑i=1 di q−∑t=1 dt γ
θ
E XF (Gn )=
n
(log
n)
1+εγ (d) ,
 q
n
1
aut(F) ∏t=1 (1 − dt γ) {q>0}
with a multiplicative error term given by


εγ (d) = O 1{q>0} n−(1−dq γ) + 1{h<v} n−(dh+1 γ−1) + 1{q<h<v} (log n)−1 .
Whenever h < v, Cγ (·) is defined inductively, with ζ (·) the Riemann zeta function:
Cγ (dh+1 ) = ζ (dh+1 γ),
Cγ (dh+1 , . . . , dv ) = Cγ (dh+1 , . . . , dv−1 )ζ (dv γ)
v−1

−
Proof. Since XF (Gn ) =

∑

j=h+1

Cγ (dh+1 , . . . , d j−1 , d j + dv , d j+1 , . . . , dv ).

 0
F ⊂ Gn : F 0 ≡ F
XF (Gn ) =

∑

0

F ⊂Kn

63

for any fixed graph F, we may write

1{F 0 ≡F} 1{F 0 ⊂G

n}

⇒ E XF (Gn ) =

∑0

0

F ⊂Kn : F ≡F

P(F 0 ⊂ Gn ),

(S.30)

with Kn the complete graph on v(Gn ). As in the case of generalized random graphs
with bounded kernels, we calculate P(F 0 ⊂ Gn ) using the fact that edges form
independently under the assumed model of Definition S.17.
Specifically, if we label the vertex set of F 0 ≡ F as {i1 , . . . , iv }, so as to correspond to our chosen ordering (d1 , . . . , dv ) of the degrees of F, then for n ≥ |v(F)|,
P(F 0 ⊂ Gn ) =

∏

is it ∈e(F 0 )

θn2 (is it )−γ

v

∑ j=1 d j

= θn

v

∑ j=1 d j

= θn

∏

(is it )−γ

is it ∈e(F 0 )
v

−γ

∏ ∏

t=1 s : i i ∈e(F 0 )
t s
v
v
d
∑
−d γ
= θn j=1 j
it t .
t=1

it

∏

Summing P(F 0 ⊂ Gn ) over all F 0 ⊂ Kn : F 0 ≡ F as per (S.30), we obtain
v

d

θn j=1 j
E XF (Gn ) =
aut(F)
∑

v

∑

∑

...

−di γ

∏ ri

∑

.

(S.31)

rv ∈[n]/{r1 ,...,rv−1 } i=1

r1 ∈[n] r2 ∈[n]/{r1 }

To derive from (S.31) the stated result of the proposition, we establish by induction the following result:
Sγ (d1 , . . . , dv ) =
=

v

∑

∑

r1 ∈[n] r2 ∈[n]/{r1 }

...

∑

−dt γ

∏ ri

rv ∈[n]\{r1 ,...,rv−1 } i=1

!
1

Cγ (dh+1 , . . . , dv ) {h<v} q−∑q d γ
h−q 
1 + εγ (d) ,
 q
1{q>0} n t=1 t (log n)
∏t=1 (1 − dt γ)
(S.32)

where εγ (d) is defined in the statement of the proposition.
To prove (S.32) by induction, we define the statement P(v) to be the following:
Sγ (d1 , . . . , dv ) takes the form of (S.32) for any tuple (d1 , . . . , dv ) of v strictly positive
integers in non-decreasing order.
64

We start by proving P(1). From [13, Equation 3.5],

(1 − d1 γ)−1 n1−d1 γ + O(1) if d1 γ < 1,



 

−d1 γ
log
n
+
γ
+
O
n−1
if d1 γ = 1,
Sγ (d1 ) = ∑ r1
=
E




r1 ∈[n]

ζ (d γ) + O n−(d1 γ−1)
if d1 γ > 1;
1

(S.33)

where γE is the Euler–Mascheroni constant and ζ (·) is the Riemann zeta function.
Thus we conclude from (S.33) directly that P(1) holds.
To make the general form of our inductive argument clear, we show how P(1)
implies P(2). To do so, we first express P(2) as follows:
"
#
Sγ (d1 , d2 ) =
=

∑

r1 ∈[n]

∑

r1 ∈[n]

−d1 γ

r1

−d γ
r1 1

"

=

∑

r1 ∈[n]

∑

r ∈[n]\{r1 }

"2

−d γ
r1 1

−d2 γ

∑

r2 ∈[n]

r2

−d γ
r2 2

#"

∑

r2 ∈[n]

#
−d2γ
− r2

−d γ
r2 2

#

"
−

∑

r3 ∈[n]

−(d +d )γ
r3 1 2

We now apply (S.33) to each term to obtain:
"
n
o
−1 1−d1 γ
Sγ (d1 , d2 ) = (1 − d1 γ) n
+ O(1) 1{d1 γ<1}
n

 o
+ log n + γE + O n−1 1{d1 γ=1}
n

o
+ ζ (d1 γ) + O n−(d1 γ−1) 1{d1 γ>1}

#

"
n
o
· (1 − d2 γ)−1 n1−d2 γ + O(1) 1{d2 γ<1}
n
o
+ log n + γE + O(n−1 ) 1{d2 γ=1}
n

o
+ ζ (d2 γ) + O n−(d2 γ−1) 1{d2 γ>1}
65

#

#
.

"
n
o
− (1 − (d1 + d2 )γ)−1 n1−(d1 +d2 )γ + O(1) 1{(d1 +d2 )γ<1}
n
 o
+ log n + γE + O n−1 1{(d1 +d2 )γ=1}
#
n

o
+ ζ ((d1 + d2 )γ) + O n−((d1 +d2 )γ−1) 1{(d1 +d2 )γ>1} .
Since d1 ≤ d2 by hypothesis, when multiplying the terms above we may reduce
the number of distinct cases to six. We then obtain that Sγ (d1 , d2 ) is equal to

n

o
−1
−1 2−(d1 +d2 )γ
−(1−d2 γ)


(1
−
d
γ)
(1
−
d
γ)
n
1
+
O
n
if d1 γ < 1, d2 γ < 1,
1
2



n

o


(1 − d γ)−1 n1−d1 γ log n 1 + O (log n)−1

if d1 γ < 1, d2 γ = 1,
1



n

o



(1 − d1 γ)−1 n1−d1 γ ζ (d2 γ) 1 + O nd1 γ−1 + n−(d2 γ−1)
if d1 γ < 1, d2 γ > 1,
o
n



(log n)2 1 + O (log n)−1
if d1 γ = 1, d2 γ = 1,



n

o




if d1 γ = 1, d2 γ > 1,
(log n)ζ (d2 γ) 1 + O (log n)−1








ζ (d1 γ)ζ (d2 γ) − ζ ((d1 + d2 )γ) + O n−(d1 γ−1)
if d1 γ > 1, d2 γ > 1.
By inspection, this expression agrees with the hypothesized form of (S.32), establishing that P(1) implies P(2). Our general inductive step will follow the same
logic as this argument.
We now assume that (S.32) holds for P(v), and will show that this implies in
turn that P(v + 1) is also true. We begin by rewriting Sγ (d1 , . . . , dv+1 ) in terms of
Sγ (d1 , . . . , dv ) as follows:
Sγ (d1 , . . . , dv+1 ) =
=

v+1

∑

...

∑

...

r1 ∈[n]

∏ ri

∑

∏ ri

rv+1 ∈[n]\{r1 ,...,rv } i=1
v

r1 ∈[n]



·

rv ∈[n]\{r1 ,...,rv−1 } i=1

∑

rv+1 ∈[n]

−dt γ

∑

−dt γ


n
o
−d γ
−d γ
−d γ
rv+1v+1 − r1 v+1 + · · · + rv v+1 

66


=



∑

rv+1 ∈[n]

−d γ
rv+1v+1 Sγ (d1 , . . . , dv )
v

− ∑ Sγ (d1 , . . . , d j−1 , d j + dv+1 , d j+1 , . . . , dv ).
j=1

−d

γ

We may now apply (S.33) to each term in ∑rv+1 ∈[n] rv+1v+1 , leading to the expression
"
n
o
Sγ (d1 , . . . , dv+1 ) = (1 − dv+1 γ)−1 n1−dv+1 γ + O(1) · 1{dv+1 γ<1}
n

 o
+ log n + γE + O n−1 · 1{dv+1 γ=1}
#
n

o
−(dv+1 γ−1)
+ ζ (dv+1 γ) + O n
· 1{dv+1 γ>1} Sγ (d1 , . . . , dv )
v

− ∑ Sγ (d1 , . . . , d j−1 , d j + dv+1 , d j+1 , . . . , dv ).

(S.34)

j=1

To evaluate the right-hand side of (S.34), we replace Sγ (d1 , . . . , dv ) with the
form given by our inductive assumption that (S.32) holds for P(v). We simplify
the result for three exhaustive cases as follows, thereby completing the proof:
Case 1) We first assume that dv+1 γ < 1. Then by hypothesis, dt γ < 1 for all
t ≤ v + 1, and h = q = v. Combining (S.32) with (S.34), it follows that the first term
v+1

v+1

in (S.34) is of order nv+1−∑t=1 dt γ , while the last term is at most of order nv−∑t=1 dt γ :
Sγ (d1 , . . . , dv+1 )
n
o


v+1
= (1 − dv+1 γ)−1 n1−dv+1 γ + O(1) Sγ (d1 , . . . , dv )+O nv−∑t=1 dt γ
n

o
= (1 − dv+1 γ)−1 n1−dv+1 γ Sγ (d1 , . . . , dv ) 1 + O n−(1−dv+1 γ) .
Substituting (S.32) for Sγ (d1 , . . . , dv ) in this expression and comparing to the
claimed result of the proposition, we see that


−(1−dv+1 γ)
εγ (d1 , . . . , dv+1 ) = O n
,
and so our claimed result is directly verified for the case in which h = q = v.
67

Case 2) We next assume that dv+1 γ = 1, whence from (S.34) we conclude that
n
 o
Sγ (d1 , . . . , dv+1 ) = log n + γE + O n−1 Sγ (d1 , . . . , dv )
v

− ∑ Sγ (d1 , . . . , d j−1 , d j + dv+1 , d j+1 , . . . , dv ).
j=1

To determine the dominant error term in this expression, we note that since dv+1 γ =
1, it follows from our inductive assumption that (S.32) holds for P(v) that
Sγ (d1 , . . . , d j−1 , d j + dv+1 , d j+1 , . . . , dv ) = Sγ (d1 , . . . , d j−1 , d j , d j+1 , . . . , dv )
n 
o
· Θ 1{d j γ=1} (log n)−1 + 1{d j γ<1} nd j γ−1 .
Therefore, the Euler–Mascheroni constant γE dominates the error, and


−1
εγ (d1 , . . . , dv+1 ) = O (log n)
.
Comparing to the claimed result of the proposition, we then see that it is directly
verified for the case in which dv+1 γ = 1.
Case 3) We finally assume that dv+1 γ > 1, and from (S.34) we see that
n

o
Sγ (d1 , . . . , dv+1 ) = ζ (dv+1 γ) + O n−(dv+1 γ−1) Sγ (d1 , . . . , dv )
v

− ∑ Sγ (d1 , . . . , d j−1 , d j + dv+1 , d j+1 , . . . , dv ). (S.35)
j=1

Recalling our inductive assumption that (S.32) holds for P(v), we note that:

Sγ d1 , . . . , d j−1 , d j + dv+1 , d j+1 , . . . , dv

 
−(1−d j γ )

Θ
n
if q > 0 and j ∈ [q],

 

= Sγ (d1 , . . . , dv ) · Θ (log n)−1
if h > q and j ∈ [h] \ [q],



Θ(1)
if v > h and j ∈ [v] \ [h],
and therefore we may simplify (S.35) to
n
Sγ (d1 , . . . , dv+1 ) = Sγ (d1 , . . . , dv ) · ζ (dv+1 γ)+
68


o
O n−(dv+1 γ−1) + 1{q>0} n−(1−dq γ ) + 1{q<h<v} (log n)−1
v

−

∑

j=h+1

Sγ (d1 , . . . , d j−1 , d j + dv+1 , d j+1 , . . . , dv ).

Finally, by substituting (S.32) for Sγ (d1 , . . . , dv ) in this last expression, we recover
the claimed result.
It follows from Proposition S.4 that in the setting of Definition S.17, the degree
sequence of any fixed graph can affect its expected number of unlabeled copies
in Gn . In particular, as we will now show, for all γ ∈ (0, 1], the number of copies
of the (e + 1)-star K1,e grows at least as quickly as that of any other (e + 1)-tree.
Noting that the 2-star or 2-path K1,1 ≡ P2 is the only element of T2 , and the 3-star
or 3-path K1,2 ≡ P3 is the only element of T3 , we formalize this result as follows.
Corollary S.1. Fix a number of edges e ≥ 3 and a tree T 6≡ S ∈ Te+1 , where
S = K1,e is the (e + 1)-star. Then, for all γ ∈ (0, 1] in the setting of Proposition S.4:

Θ(1)






−1


Θ
(log
n)

 

E XT (Gn ) 
d ∗ − min{γ,eγ−1}
= O (log n) n


E XS (Gn ) 

d ∗ −1


O
(log
n)
n




 
−1

O (log n)

0 < γ < 1/e,
γ = 1/e,
1/e < γ < 1/2,
1/2 ≤ γ < 1,
γ = 1;

where d ∗ is the number of degrees of T equal to γ −1 .
Proof. Let (d1 , . . . , de+1 ) be the degrees of T 6≡ S, enumerated in non-decreasing
order. If γ = 1, then all degrees of T and S are at least as large as γ −1 = 1, and so
from Proposition S.4, we deduce that only logarithmic growth terms are present:




E XT (Gn ) = Θ θn2e (log n)|{t : dt =1}| vs. E XS (Gn ) = Θ θn2e (log n)e+1{e=1} .
Then, since for e ≥ 3, the (e + 1)-star S = K1,e is distinct in having the maximum
number e of leaves among all trees of order e + 1, we recover the claimed result.
By this same reasoning, if 1/2 < γ < 1, then E XT (Gn )/ E XS (Gn ) = O n−1 :




E XT (Gn ) = Θ θn2e n|{t : dt =1}| vs. E XS (Gn ) = Θ θn2e ne+1{e=1} ,
69

and if γ = 1/2, then E XT (Gn ) will gain an extra factor of (log n)|{t : dt =2}| .
If 1/e < γ < 1/2, then we consider two cases. First, assume thatde+1 γ < 1. By
Proposition S.4 we deduce that E XT (Gn )/ E XS (Gn ) = Θ n−(eγ−1) , since:




2e e(1−2γ)+1
2e e(1−2γ)+eγ
E XT (Gn ) = Θ θn n
vs. E XS (Gn ) = Θ θn n
.
If de+1 γ ≥ 1, then for q = |{t : dt γ < 1}| ∈ {2, . . . , e} and d ∗ = |{t : dt γ = 1}|,


q
2e q−γ ∑t=1 dt
d∗
E XT (Gn ) = Θ θn n
(log n)

∗
q(1−γ)−γ ·1{d ≥2}
q
= O θn2e n
(log n)d .
q

q

where the lower bound ∑t=1 dt ≥ q + 1{dq ≥2} follows since ∑t=1 dt = q if dq = 1,
q
whereas if dq ≥ 2, then ∑t=1 dt ≥ q + 1.
∗
(q−e)(1−γ)−γ ·1{d ≥2}
q
Thus we have that E XT (Gn )/ E XS (Gn ) = O n
(log n)d .
∗
As a result, if 2 ≤ q ≤ e − 1, this rate is O(n−(1−γ) (log n)d ). If instead q ∗= e,
then we must have dq ≥ 2 (otherwise T ≡ S), yielding the rate O(n−γ (log n)d ).
Finally, if 0 < γ ≤ 1/e, then all degrees of T 6≡ S and S are strictly less than γ −1 ,
except possibly the largest degree e of S. From Proposition S.4 we then deduce:




E XT (Gn ) = Θ θn2e ne(1−2γ)+1 vs. E XS (Gn ) = Θ θn2e ne(1−2γ)+1 (log n)1{eγ=1} .
Thus if γ < 1/e, then E XT (Gn )/ E XS (Gn ) = Θ(1), recovering the bounded kernel

setting as γ → 0. If γ = 1/e, then E XT (Gn )/ E XS (Gn ) = Θ (log n)−1 .
The following result, analogous to Corollary S.1, holds for unicyclic graphs.
Corollary S.2. Fix a number of edges e ≥ 4 and a connected graph U 6≡ C3 K1,e−3
containing exactly one cycle, where C3 K1,e−3 is the graph obtained by identifying
any node of the 3-cycle C3 with the unique node of degree e − 3 in the (e − 2)-star
K1,e−3 . Then, for all γ ∈ (0, 1/2] in the setting of Proposition S.4:


Θ(1)




−1


Θ
(log
n)
E XU (Gn )


=
d ∗ − min{γ,1−2γ,(e−1)γ−1}
E XC3 K1,e−3 (Gn ) 
O (log n) n






O (log n)−1
70

0 < γ < 1/(e − 1),
γ = 1/(e − 1),

1/(e − 1) < γ < 1/2,
γ = 1/2;

where d ∗ is the number of degrees of U equal to γ −1 . Furthermore, if U3e−3 is the
set of unlabeled graphs formed by attaching e−3 edges to C3 to form e−3 pendant
nodes, then for U 0 6∈ U3e−3 and F, F 0 ∈ U3e−3 , E XF 0 (Gn )/ E XF (Gn ) = Θ(1) and
  
−1
1/2 < γ < 1,
E XU 0 (Gn ) O n


=
E XF (Gn ) O (log n)−1
γ = 1.
Proof. Let (d1 , . . . , de ) be the degrees of U 6≡ C3 K1,e−3 in non-decreasing order. If
γ = 1, then all degrees of U and C3 K1,e−3 are at least as large as γ −1 = 1, and so
from Proposition S.4, we deduce that only logarithmic growth terms are present:




E XU (Gn ) = Θ θn2e (log n)|{t : dt =1}| vs. E XC3 K1,e−3 (Gn ) = Θ θn2e (log n)e−3 .
Attaching e − 3 pendant nodes to C3 will satisfy E XU (Gn ) = Θ E XC3 K1,e−3 (Gn ),
whereas attaching e − 4 pendant nodes
to C4 will lose a power of log n. Thus
−1 
E XU 0 (Gn )/ E XF (Gn ) = O (log n)
for U 0 6∈ U3e−3 and F ∈ U3e−3 as claimed.
By this same reasoning, if 1/2 < γ < 1, then E XU 0 (Gn )/ E XF (Gn ) = O n−1 :




E XU 0 (Gn ) = Θ θn2e n|{t : dt =1}| vs. E XF (Gn ) = Θ θn2e ne−3 .
If γ = 1/2, then E XC3 K1,e−3 (Gn ) will gain an extra log n factor relative to any other
F ∈ U3e−3 , since C3 K1,e−3 is unique in U3e−3 in containing two nodes of degree 2.
If 1/(e − 1) < γ < 1/2, then we consider two cases. First, assume that de γ <1.
By Proposition S.4 we deduce that E XU (Gn )/ E XC3 K1,e−3 (Gn ) = Θ n−[(e−1)γ−1] :




E XU (Gn ) = Θ θn2e ne(1−2γ) vs. E XC3 K1,e−3 (Gn ) = Θ θn2e ne(1−2γ)+(e−1)γ−1 .
(S.36)
If de γ ≥ 1, then for q = |{t : dt γ < 1}| ∈ {3, . . . , e − 1} and d ∗ = |{t : dt γ = 1}|,

q
∗
E XU (Gn ) = Θ θn2e nq−γ ∑t=1 dt (log n)d


2e q(1−γ)−γ(dq −1)·1{dq ≥2} −γ(dq−1 −1)·1{dq−1 ≥2}
d∗
= O θn n
(log n) , (S.37)
q

where the lower bound ∑t=1 dt ≥ q + (dq − 1) · 1{dq ≥2} + (dq−1 − 1) · 1{dq−1 ≥2} follows from that fact that dq ≥ 1. If dq = 1, then comparing (S.37) and (S.36) yields

∗
E XU (Gn )
= O n(q−e)(1−γ)+γ+1 (log n)d .
E XC3 K1,e−3 (Gn )
71

By hypothesis, U contains exactly one cycle, each vertex of which is of degree at
least 2. Therefore U must possess at least three vertices of degree larger than 1,
and so if dq = 1, then we must have q ≤ e − 3. Consequently,


∗
∗
E XU (Gn )
= O n3(γ−1)+γ+1 (log n)d = O n4(γ−1/2) (log n)d .
E XC3 K1,e−3 (Gn )
q

By this same reasoning, if q = e − 2, then dq ≥ 2 and so ∑t=1 dt ≥ q + 1. Thus,


∗
∗
E XU (Gn )
= O n2(γ−1)−γ+γ+1 (log n)d = O n2(γ−1/2) (log n)d .
E XC3 K1,e−3 (Gn )
q

Likewise, if q = e − 1, then dq ≥ 2 and dq−1 ≥ 2. If dq ≥ 3 then ∑t=1 dt ≥ q + 3. If
instead dq = 2, then necessarily dq−1 = 2. In this case, since C3 K1,e−3 is the only
unicyclic graph with de−2 = de−1 = 2 and de = e − 1, it follows that de ≤ e − 2,
q
and so again we conclude that ∑t=1 dt = 2e − de ≥ q + 3. Thus we obtain




E XU (Gn )
−γ
d∗
(γ−1)−3γ+γ+1
d∗
= O n (log n) .
=O n
(log n)
E XC3 K1,e−3 (Gn )
Finally, if 0 < γ ≤ 1/(e−1), then all degrees of U 6≡ C3 K1,e−3 and C3 K1,e−3 are
strictly less than γ −1 , except possibly the largest degree e − 1 of C3 K1,e−3 . Thus:




E XU (Gn ) = Θ θn2e ne(1−2γ) vs. E XC3 K1,e−3(Gn ) = Θ θn2e ne(1−2γ) (log n)1{(e−1)γ=1} .
If γ < 1/(e−1), E XU (Gn )/ E XC3 K1,e−3 (Gn ) = Θ(1), recovering the bounded kernel

setting as γ → 0. If γ = 1/(e − 1), E XU (Gn )/ E XC3 K1,e−3 (Gn ) = Θ (log n)−1 .
We next establish the form of the logarithm of the expected graph walk density
in the setting of Proposition S.4.
Corollary S.3. Fix an integer k ≥ 2 and a closed k-walk w ∈ Wk (Kk ) whose induced subgraph has degrees (d1 , . . . , dv ). Then, in the setting of Proposition S.4,
the graph walk density ϕ(w, Gn ) satisfies
"
!
!
#
log E ϕ(w, Gn ) = −

v

∑ min{1, diγ}

i=1

72

log n +

v

∑ di

i=1

|log θn | {1 + o(1)}.

Proof. We first recall Definition S.5, and combine it with Lemma S.3 to obtain
E ϕ(w, Gn ) =

E indk (Fw , Gn ) indk (Fw , Fw ) E XFw (Gn )
=
indk (Fw , Kn )
indk (Fw , Fw )XFw (Kn )
=

E XFw (Gn )
(n)v /aut(Fw )

= aut(Fw ) n

−v

n
 o
E XFw (Gn ) 1 + O n−1 . (S.38)

Then, replacing E XFw (Gn ) in (S.38) with the result of Proposition S.4, we obtain
1

Cγ (dh+1 , . . . , dv ) {h<v} ∑v d −v+q−∑q d γ
t=1 t (log n)h−q
E ϕ(w, Gn ) =  q
1{q>0} θn i=1 i n
∏t=1 (1 − dt γ)
n
 
o
−1
· 1+O n
+ εγ (d) . (S.39)
The logarithm of (S.39) will yield the claimed result, after noting θn ∈ (0, 1] and
q

−v + q − ∑ dt γ = −
t=1

v

∑

t=q+1

q

v

1 − ∑ dt γ = − ∑ min(1, dt γ).
t=1

t=1

These substitutions allow us to write log E ϕ(w, Gn ), following on from (S.39), as
!

1
v
Cγ (dh+1 , . . . , dv ) {h<v}
− ∑ min{1, di γ} log n
log E ϕ(w, Gn ) = log  q
1
∏t=1 (1 − dt γ) {q>0}
i=1
!

 

v
−1
− ∑ di |log θn | + (h − q) log log n + log 1 + O n
+ εγ (d) . (S.40)
i=1

Noting that ∑vi=1 min{1, di γ} ≥ 2γ > 0 for k ≥ 2, we conclude by absorbing the first,
fourth, and fifth terms of (S.40) into a multiplicative {1 + o(1)} error term.

6.2

Dominating closed walks in scale-free random graphs

Above we have compared the expected numbers of unlabeled copies of trees (Corollary S.1) and unicylic graphs (Corollary S.2) in the setting of Proposition S.4. We
now characterize dominant walks in this setting. To do so we will study the model
of Definition S.17 for a sequence {Gn } of random graphs, in conjunction with a
73

scaling sequence {θn } taking values in (0, 1]. We therefore define a measure of the
speed of decay of θn in n as follows, recalling from Definition S.17 that θn ∈ (0, 1]:
βn =

|log θn |
.
log n

(S.41)

Thus θn = n−βn , and so βn measures the rate of decay of log θn relative to log n.
Theorem S.4. Fix a walk length k ≥ 2, and consider the setting of Proposition S.4
with the additional assumption that limn→∞ βn = β ≥ 0 exists. If β + γ < 1/2, so
that a randomly chosen degree in this setting will grow in expectation, then the set
of asymptotically dominating walk-induced subgraphs (Wk∗ ({Gn })) is as follows.
If β +γ < (1−γ)/2, then Theorem S.1 holds, and with k∗ = [1/2 − (βn + γ)]−1 ,


E indk (Ck , Gn )
if k is odd or if k > k∗ ,



E ind (C , G )
k k
n
E |Wk (Gn )| ∼
(S.42)
∗
+

∑T ∈Tk/2+1 E indk (T, Gn ) if k is even and k = k ,



∑
E ind (T, G )
if k is even and k < k∗ .
T ∈Tk/2+1

k

n

If β + γ = (1 − γ)/2, then k∗ = 2/γ, and


if k is odd,
{Ck }
∗
Wk ({Gn }) = Tk/2+1
if k is even and k < k∗ ,


{Ck , K1,k/2 } if k is even and k ≥ k∗ .

(S.43)

1/2−γ
If (1 − γ)/2 < β + γ < 1/2, then with k† = 2γ , k◦ = 2 β +γ−(1−γ)/2
+ 3, and

k+ = max{k◦ , k† + 1},

{Ck }





{Ck }



{C ,C K
k 3 1,(k−3)/2 }
Wk∗ ({Gn }) =

{C3 K1,(k−3)/2 }





Tk/2+1



{K1,k/2 }

if k is odd and k < k+ ,
if k is odd, k = k+ and k+ ≤ k† + 1,
if k is odd, k = k+ and k+ > k† + 1,
(S.44)
if k is odd and k > k+ ,
if k is even and k < k† ,
if k is even and k ≥ k† .

Furthermore, for all k ≥ 3, non-backtracking, tailless closed k-walks are dominated by the k-cycle:
E |Wkb (Gn )| ∼ E indk (Ck , Gn ),
74

(S.45)

if and only if β + γ < 1/2 or γ = 1/2 and βn log n/ log log n < 1/2 eventually in n.
Proof. We will prove each of (S.42)–(S.45) in order. To begin, note that for F = K2 ,
Proposition S.4 immediately
implies that

 for γ ∈ (0, 1), the probability of an edge
satisfies E XK2 (Gn )/ n2 = Θ n−2(βn +γ) , and thus the expected value E XK2 (Gn )/n
of a randomly chosen degree diverges if and only if βn + γ < 1/2.
Proof of (S.42): We begin by showing that Assumptions S.1 and S.2 are satisfied, and thus that Theorem S.1 holds, whenever βn + γ < (1 − γ)/2. Proposition S.4, specifically (S.31), implies that E XF (Gn ) is strictly positive for any F
with strictly positive degrees whenever |v(F)| ≤ n. Thus E|Wk (Gn )| > 0 eventually
in n for all k ≥ 2, and so Assumption S.1 is satisfied.
If we can show that if βn + γ < (1 − γ)/2, then Assumption S.2 is satisfied, then
we can apply Theorem S.1. To this end, we fix w to be an arbitrary closed k-walk
that admits an extension, and is such that for n sufficiently large, E ϕ(w, Gn ) > 0.
To satisfy Assumption S.2, it is sufficient to exhibit an extension w0 of w such that


n E ϕ(w0 , Gn )
= ω(1).
(S.46)
log
E ϕ(w, Gn )
Let w0 be any extension of w, and denote the degree sequences of Fw and Fw0
0
by d = (d1 , . . . , dv ) and d 0 = (d10 , . . . , dv+1
), respectively. We write
v

λ=

∑ min(1, dt γ)

and

t=1

0

λ =

v+1

∑ min(1, dt0γ).

t=1

Then, since Fw0 has one more vertex and up to one more edge than Fw , it follows
from Corollary S.3 that





n E ϕ(w0 , Gn )
log
= 1 − 2βn |e(Fw0 )| − |e(Fw )| − λ 0 − λ log n{1 + o(1)}
E ϕ(w, Gn )

≥ 1 − 2βn + λ − λ 0 log n{1 + o(1)}.
Thus, (S.46) will hold if w and w0 are such that, eventually in n,
λ + 1 − 2βn − λ 0 > 0.

(S.47)

We now appeal to Lemma S.2 to exhibit a w0 such that (S.47)—and consequently (S.46)—is satisfied. Lemma S.2 characterizes the degree sequence of Fw0
75

as a function of that of Fw through four exhaustive cases. First, by inspection of
each case in Lemma S.2, we see that dt = dt0 for t ≤ v − 2, as we have added one
node and at most one edge, and therefore
0
λ − λ 0 = [min(1, dv−1 γ) − min(1, dv−1
γ)]

0
+ [min(1, dv γ) − min(1, dv0 γ)] − min(1, dv+1
γ).

0
Again by inspection of each case, we see that dv−1
≤ dv−1 and dv0 ≤ dv + 1, so that
0
min(1, dv−1 γ) − min(1, dv−1
γ) ≥ 0,

min(1, dv γ) − min(1, dv0 γ) ≥ min(1, dv γ) − min(1, (dv + 1)γ).

Finally, since min(1, dv γ) − min(1, (dv + 1)γ) ≥ −γ, we conclude that

− min(1, 2γ)
Case 1 of Lemma S.2,



−γ − min(1, 2γ) Case 2 of Lemma S.2,
λ −λ0 ≥

−γ − min(1, γ) Case 3 of Lemma S.2,



− min(1, γ)
Case 4 of Lemma S.2.
The bound λ − λ 0 ≥ −3γ therefore holds in all four cases. Then, since β =
limn→∞ βn exists by hypothesis, we see that the condition β + γ < (1 − γ)/2 ensures that (S.47) holds eventually in n—and thus that Assumption S.2 holds.
We now establish (S.42) under the hypothesis βn + γ < (1 − γ)/2. Since Assumptions S.1 and S.2 hold under this condition, Theorem S.1 is in force, and we
may use it to deduce that walks mapping out trees and cycles at maximal scales are
dominant. In particular, combining Theorem S.1 with Item 2 of Proposition S.3
yields directly that
E |Wk (Gn )| ∼ E indk (Ck , Gn ) + 1{k even}

∑

T ∈Tk/2+1

E indk (T, Gn ).

This result, along with Proposition S.3, implies (S.42) when k = 2 or when k ≥ 3 is
odd. When k ≥ 4 is even, we must instead compare the behavior of trees and cycles.
Corollary S.1 establishes that the expected number of closed walks inducing the
(k/2 + 1)-star K1,k/2 grows at least as quickly as that of any other tree in Tk/2+1 ,
and thus it is sufficient to compare the expected counts of walks inducing the kcycle Ck and the (k/2 + 1)-star K1,k/2 . Corollary S.1 then asserts that if k < 2/γ,
all trees in Tk/2+1 will exhibit the same rate of growth.
76

Since βn + γ < (1 − γ)/2 implies γ < 1/2, Proposition S.4 implies that
E XK1,k/2 (Gn )
E XCk (Gn )



k
= Θ nmax{1,kγ/2}− 2 (1−2βn −2γ) (log n)1{kγ=2} .

(S.48)

The map k 7→ max{1, kγ/2} − k(1 − 2βn − 2γ)/2 is monotone decreasing in k
if βn + γ < (1 − γ)/2, and also admits a unique zero at k∗ = [1/2 − (βn + γ)]−1 .
Therefore, when k ≥ 4 is even, we conclude the following:

∗

o(1) if k < k ,
E XCk (Gn )
= Θ(1) if k = k∗ ,
E XK1,k/2 (Gn ) 

ω(1) if k > k∗ .
Finally, the hypothesis βn + γ < (1 − γ)/2 implies that k∗ < 2/γ, and so by Corollary S.1, we conclude that all trees in Tk/2+1 exhibit the same rate of growth
whenever k ≤ k∗ . Together with Proposition S.3, these results imply (S.42) when
k ≥ 4.

Proof of (S.43) and (S.44): We now treat the case (1 − γ)/2 ≤ βn + γ < 1/2.
Fix F ∈ Wk , let v = |v(F)| and e = |e(F)|, write (d1 , . . . , dv ) for the degree sequence
of F, enumerated in non-decreasing order, and set v(s) = |{t : dt = s}|.
First, assume that e − v ≥ 0. Fix F ∈ Wk \ {Ck ,C3 K1,(k−3)/2 }, where the graph
C3 K1,(k−3)/2 is obtained by identifying any node of the 3-cycle C3 with the unique
node of degree (k − 3)/2 in the [(k − 3)/2 + 1]-star K1,(k−3)/2 .
To bound E XF (Gn ), we start from the expression for E XF (Gn ) in Proposition S.4, with its definitions of q and h. Then, with v(s) = |{t : dt = s}|, we have
q

q − ∑ dt γ =
t=1

v

dv

t=1

s=1

∑ max{1 − dt γ, 0} = ∑ v(s) max{1 − sγ, 0},

v = v(1) + v(2) + · · · + v(dv ) .

(S.49)
(S.50)

We may use (S.49) and (S.50), along with the fact that γ < 1/2, to obtain

1
q
Cγ (dh+1 , . . . , dv ) {h<v}
2e q−∑t=1 dt γ
h−q 
θ
n
(log
n)
1+εγ (d)
E XF (Gn ) =
 q
n
1
aut(F) ∏t=1 (1 − dt γ) {q>0}


dv
−2eβn +∑s=1
v(s) max{1−sγ,0}
v(1/γ)
=Θ n
(log n)
77



dv
v(s) max{1−sγ,0}−2βn v−2βn (e−v)
v(1/γ)
v(1) (1−γ)+v(2) (1−2γ)+∑s=3
(log n)
=Θ n


dv
v(s) [max{1−sγ,0}−2βn ]−2βn (e−v)
v(1/γ)
v(1) (1−2βn −γ)+v(2) (1−2βn −2γ)+∑s=3
(log n)
.
=Θ n
Then, as we have assumed (1 − γ)/2 ≤ βn + γ, or equivalently 1 ≤ 2βn + 3γ, it
follows that max{1 − 2βn − sγ, −2βn } ≤ 0 for s ≥ 3. As a consequence, we obtain


E XF (Gn ) = O nv(1) (1−2βn −γ)+v(2) (1−2βn −2γ)−2βn (e−v) (log n)v(1/γ) .

(S.51)

Now suppose that v = v(1) + v(2) . Then, since e ≥ v, we deduce that 2e =
v(1) + 2v(2) ≥ 2v = 2v(1) + 2v(2) . Thus, v(1) = 0, and it follows that v(2) = v. The
only graphs in Wk satisfying these constraints are Cv , for v ∈ {3, . . . , k}. Since
F 6≡ Ck by hypothesis, it follows by Item 8 of Lemma S.1 that v(2) ≤ k − 1, and
hence, since β + γ < 1/2, we conclude that E XF (Gn )/ E XCk (Gn ) = o(1), since


E XCk (Gn ) = Θ nk(1−2βn −2γ) (log n)v(1/γ) .
If instead v ≥ v(1) + v(2) + 1, then


E XF (Gn ) = O nv(1) (1−2βn −γ)+(v−v(1) −1)(1−2βn −2γ)−2βn (e−v) (log n)v(1/γ) .
We now bound v, using the fact that F ∈ Wk \ {Ck ,C3 K1,(k−3)/2 } is induced by
a closed k-walk. To this end, observe that at least 2v(1) walk steps are used to
traverse all v(1) edges attached to pendant nodes, and at least v − v(1) steps are used
to visit the remaining vertices. Combining these observations, we conclude that
v + v(1) ≤ k. Thus:


v(1) (1−2βn −γ)+(k−2v(1) −1)(1−2βn −2γ)−2βn (e−v)
v(1/γ)
E XF (Gn ) = O n
(log n)


= O nv(1) (−1+2βn +3γ)+(k−1)(1−2βn −2γ)−2βn (e−v) (log n)v(1/γ) . (S.52)
Next, we bound v(1) in (S.52) using the fact that F is induced by a closed kwalk. To this end, first observe that since F is not a tree, it must contain a cycle.
It follows that at least three walk steps are required to traverse the edges of this
cycle. At the same time, 2v(1) steps are required to traverse all v(1) edges attached
to pendant nodes. Thus 2v(1) ≤ k − 3, with equality only if k is odd.
78

If 2v(1) ≤ k − 4, then since −1 + 2βn + 3γ ≥ 0, we obtain from (S.52) that
 k−4

E XF (Gn ) = O n 2 (−1+2βn +3γ)+(k−1)(1−2βn −2γ)−2βn (e−v) (log n)v(1/γ)
 k−4

(S.53)
= O n 2 (1−2βn −γ)+2(1−2βn −2γ)−2βn (e−v) (log n)v(1/γ) .
Comparing with the expression for E XC3 K1,(k−3)/2 (Gn ) from Proposition S.4:
 k−3

E XC3 K1,(k−3)/2 (Gn ) = Θ n 2 (1−2βn −γ)+2(1−2βn −2γ)+max{1−(k+1)γ/2,0} (log n)v(1/γ) ,
(S.54)
we see that E XF (Gn )/ E XC3 K1,(k−3)/2 (Gn ) = o(1) if k is odd. If k is even, then
similarly E XF (Gn )/ E XK1,k/2 (Gn ) = o(1), since
 k

(1−2βn −γ)+max{1−kγ/2,0}
v(1/γ)
2
E XK1,k/2 (Gn ) = Θ n
(log n)
.
If instead 2v(1) = k − 3, then F must take the form of a triangle with (k −
3)/2 pendant nodes and degree sequence (1, . . . , 1, 2 + l1 , 2 + l2 , 2 + l3 ) for natural
numbers l1 , l2 , l3 such that l1 + l2 + l3 = (k − 3)/2. Proposition S.4 then asserts
that (S.53) holds unless l1 = l2 = 0, in which case F ≡ C3 K1,(k−3)/2 and we obtain
a contradiction.
From the above, we conclude that if F ∈ Wk \ {Ck ,C3 K1,(k−3)/2 } and furthermore F satisfies e ≥ v, then


E XF (Gn ) = o E XCk (Gn ) + E XK1,k/2 (Gn ) + E XC3 K1,(k−3)/2 (Gn ) .
If F is such that e < v, then Lemma S.1 asserts that e = v − 1 and that k must be
even. By Corollary S.1, the expected number of unlabeled copies in Gn of a tree
with e edges is bounded by that of the star K1,e . If e < 1/γ, then all trees T ∈ Te+1
will exhibit similar behavior; otherwise, if e ≥ 1/γ, then E XK1,e (Gn ) will dominate.
Furthermore, Proposition S.4 shows that E XT (Gn ) increases in e and n whenever
βn + γ < 1/2, implying that dominant trees must have e = k/2 edges.
We now turn to comparing the rates of growth of Ck , K1,k/2 , and C3 K1,(k−3)/2 .
If kγ/2 < 1, then by Corollary S.1, all trees in Tk/2+1 grow at the same rate as
K1,k/2 . This leads to the same comparison as in the case of Lemma S.7, and so
trees dominate cycles if k is even and k < k∗ = [1/2 − (βn + γ)]−1 . If k is odd and
(k + 1)γ/2 < 1, then once again replicating the calculations of Lemma S.7, we
conclude that cycles dominate.
79

If kγ/2 ≥ 1 and if k is even, then we compare E XK1,k/2 (Gn ) to E XCk (Gn ), as
per (S.48). Then, if (1 − γ)/2 < βn + γ, the map k 7→ max{1, kγ/2} − k(1 − 2γ −
2βn )/2 is monotone increasing, and for all k ≥ 3, E XK1,k/2 /E XCk (Gn ) = ω(1). If
(1 − γ)/2 = βn + γ, then E XK1,k/2 /E XCk (Gn ) = ω(1) for k ≤ k† , and otherwise
E XK1,k/2 /E XCk (Gn ) = Θ(1). This recovers the last two lines of (S.43).
Finally, if (k + 1)γ/2 ≥ 1 and k is odd, then we compare
 k−3

(1−2βn −γ)+2(1−2βn −2γ)+max{1−(k+1)γ/2,0}
(log n)v(1/γ)
E XC3 K1,(k−3)/2 (Gn ) Θ n 2


=
E XCk (Gn )
Θ nk(1−2βn −2γ)

 k−3
(−1+2βn +3γ)−(1−2βn −2γ)
v(1/γ)
2
(log n)
.
(S.55)
=Θ n
When 1 < 2βn + 3γ, then we observe that C3 K1,(k−3)/2 dominates whenever k >
3 + 2(1 − 2βn − 2γ)/(−1 + 2βn + 3γ). Otherwise, or if (1 − γ)/2 = βn + γ, then
Ck dominates.
Proof of (S.45): Finally, we show that (S.45) holds if and only if γ + βn < 1/2
or γ = 1/2 and βn log n/ log log n < 1/2 eventually in n. We recast the result of
Proposition S.4 to refine (S.51) as follows, where again we write v(i) as the number
v
of nodes of F having degree i. We use the identity 2e = ∑t=1
dt = ∑v−1
i=1 iv(i) :
 v

t 0 : dt 0 γ=1| −2eβn
∑t=1 max{1−dt γ,0}
|
E XF (Gn ) = Θ n
(log n)
n
 d

v v max{1−iγ,0}−2eβ
v(1/γ)
∑i=1
(i)
n
=Θ n
(log n)

 d
v v
∑i=1
(i) [max{1−iγ,0}+xn ·1{i=1/γ} ]−2eβn
=Θ n
 d v

v (i) max{1−iγ,0}+x ·1
v ∑i=1
[
n {i=1/γ} −iβn ]
v
=Θ n
,
(S.56)
where xn = log log n/ log n = o(1). For
is
 any fixed v, the summation in (S.56)

a convex combination of the values max{1 − iγ, 0} + xn 1{i=1/γ} − iβn for i ∈
{1, . . . , dv }. These values are strictly decreasing in i (until i exceeds 1/γ if βn = 0).
Now, suppose that v(1) = 0 and that 0 < γ ≤ 1/2. Since the values in the summation of (S.56) are then strictly decreasing in i until at least i = 3, the maximum
of this sum over the entire standard (v − 3)-simplex is attained uniquely by the extreme point v(2) = v. This point is achieved by F ≡ Cv for any fixed v ∈ {3, 4, . . .},
and so E XCv (Gn ) = Θ nv[max{1−2γ,0}+xn ·1{γ=1/2} −2βn ] . Thus E XCv (Gn ) → ∞ if and
80

only if γ + βn < 1/2 eventually in n or γ = 1/2
 and βn < xn /2 eventually in n, implying then that E XFv (Gn ) = o E XCv (Gn ) for any graph Fv on v vertices with
strictly positive degrees and no pendant nodes.
Therefore, if we consider non-backtracking, tailless closed k-walks inducing
elements of Wkb in this setting, we see that E XCk (Gn ) = max{v :C ∈W b } E XCv (Gn )
v
k
grows strictly more quickly than any other element of Wkb . Thus we conclude that
k-walks inducing Ck will grow in prevalence and uniquely dominate amongst all
non-backtracking, tailless closed k-walks whenever βn + γ < 1/2 or γ = 1/2 and
βn /xn < 1/2 eventually in n.

7

Methods and algorithms

The approach we use to calculate network summaries in this study is described in
Algorithms 1 and 2. It is based on repeatedly subsampling the network of interest,
and then determining the prevalence and local variability of trees and k-cycles
within each sub-network. The number of sub-network replicates sampled in this
manner is set via Algorithm 1, and the range of replicate sizes via Algorithm 2.

7.1

Algorithm 1: Subsampling to summarize trees and cycles

Given an input graph G, Algorithm 1 randomly subsamples its nodes, yielding for
each replicate r a set of nodes ur and a corresponding node-induced subgraph G[ur ].
Summaries of trees and cycles in each G[ur ] are then calculated via operations on
the adjacency matrix of G[ur ] [16, 17]. This procedure is repeated independently,
and the resulting samples are used to form kernel density estimates [15] summarizing the prevalence and local variability of trees and cycles throughout G. These
density estimates comprise the violin plots [14] in Figs. 3–5 in the main text.
Algorithm 1 summarizes trees in G[ur ] through the ratio of the following quantities, with |ur | the number of nodes in G[ur ] and d[ur ] its degree sequence:
1 |ur |
#{ in G[ur ]} = ∑ d[ur ]i (d[ur ]i − 1),
2 i=1

(S.57a)

|ur | − 2 |ur |
in G[ur ]} =
∑ d[ur ]i.
2 i=1

(S.57b)

#{

Algorithm 1 summarizes k-cycles in G[ur ] as the kth root of the proportion of
81

Algorithm 1: Network summarization routine used in the main text
Input: Simple graph G on n nodes; Ns subgraph sizes 1 < s1 , . . . , sNs < n;
maximal scale 2 < kmax < minl sl ; level 0 < α < 1.
Output:
on
{tk (r)}Rr=1 for each k ∈ {2, . . . , kmax }.

n Violinplots [14] based
o2
−1
α
1
Φ
1
−
, for Φ(·) the CDF of a standard normal;
R←
2α
2(k −1)
max

for r ← 1 to R do // Subsample independently in parallel
Sample ur uniformly at random over all sdNs r/Re -subsets of nodes of G;
Construct the node-induced subgraph G[ur ] on |ur | nodes of G;
t2 (r) ← #{ in G[ur ]}/#{ in G[ur ]} as defined in (S.57);
for k ← 3 to kmax do // Iterate over matrix powers
1/k
tk (r) ← #{Ck in G[ur ]}/#{Ck in K|ur | }
as defined in (S.58);
end
end
for k ← 2 to kmax do // Construct density estimates
Form a kernel density estimate from the set {tk (r) : tk (r) > 0} using any
user-defined automatic bandwidth selection method (see, e.g., [15]);
if #{tk (r) : tk (r) = 0}/R > α then
Re-weight the kernel density estimate by #{tk (r) : tk (r) > 0}/R;
Add a mass at zero of height #{tk (r) : tk (r) = 0}/R;
end
end
Display all kmax − 1 kernel density estimates together as violin plots.

cycles present, recalling that (|ur |)k = |ur |!/(|ur | − k)! is the falling factorial:
#{Ck in G[ur ]} = the number of k-cycles in G[ur ],
1
#{Ck in K|ur | } = (|ur |)k .
2k

(S.58a)
(S.58b)

To determine the total number of replicates R, Algorithm 1 relies on the following idea. Consider the cumulative distribution function (CDF) Ftk (·) of a given
tk (r). Conditionally upon the observed graph of interest G, it follows from the
central limit theorem that when R is sufficiently large, the corresponding empirical CDF
 F̂tk (·) behaves like a normal distribution with mean Ftk (·) and variance
Ftk (·) 1 − Ftk (·) /R. To constrain departures of F̂tk (·) from Ftk (·) greater than α
to occur with probability bounded by α, simultaneously taking into account via
82

Algorithm 2: Automatic selection routine for network subsampling sizes
Input: Simple graph G on n nodes; maximal scale 2 < kmax < n/2; level
0 < α < 1, number of subgraph sizes Ns , size increment δ > 0.
Output: Multiset of Ns subgraph sizes 1 < s1 , . . . , sNs < n.
s∗ ← min{max{kmax + 1, min{bn/4c, 3(kmax + 1)}}, n}/(1 + δ );
K ∗ ← {2, . . . , kmax };
smax ← n;
for i ← 1 to dlog n/ log(1 + δ )e do // Increment subgraph size
s∗ ← min{[(1 + δ )s∗ ], n};
{tk (r) : 2 ≤ k ≤ kmax }Rr=1 ← Algorithm 1 with inputs G, s∗ , kmax , α;
foreach k ∈ K ∗ do // Check summary separated from 0
if #{tk (r) : tk (r)> 0} > 0 then
q

2 
2
1
1
1
pk ← 1 − Φ R ∑r tk (r)/ R−1 ∑r tk (r) − R(R−1) ∑r tk (r) ;
else

pk ← 1/2;
end
end
p ← maxk∈K ∗ pk // Quantify least-separated summary
if p ≤ α/(kmax − 1) or s∗ ≥ smax then // Reset, then halt
if smax = b0.8nc then
Terminate and return Ns equispaced values s1 , . . . , sNs over the
range 0.9s∗ –1.1s∗ , rounding each to the nearest integer.
end
s∗ ← min{max{kmax + 1, min{bn/4c, 3(kmax + 1)}}, n}/(1 + δ );
K ∗ ← {k : pk < 1/2} // Ignore all-zero summaries
smax ← b0.8nc // Restrict maximum subgraph size
end
end
the Bonferroni correction that we wish this to hold for all kmax − 1 scales under
consideration, we may formulate the following requirement:


α
P F̂tk (·) − Ftk (·) > α ≤
.
(S.59)
kmax − 1

Replacingthe left-hand
 side of (S.59) by the corresponding normal CDF and noting
that Ftk (·) 1 − Ftk (·) ≤ 1/4, we obtain the expression for R given in Algorithm 1.
83

Algorithm 1 requires as input a set of subgraph sizes s1 , . . . , sNs , a maximal
scale kmax , and a level α. While it is possible to use just a single subgraph size, this
can lead to discretization effects in the values of the summaries obtained when G
is small. To avoid this eventuality, we vary subgraph sizes around an average value;
both the selection of this value and the variation around it are done automatically
in this study using Algorithm 2.

7.2

Algorithm 2: Selecting network sizes for subsampling

Algorithm 2 must determine subgraph sizes which are neither too small, in which
case k-cycles may be absent simply because of network edge sparsity [18]—nor
too large, in which case independently chosen subgraph replicates will overlap
significantly, and be highly correlated as a result. To automate this procedure,
Algorithm 2 steps through an increasing sequence of trial values for the number
of subgraph nodes s∗ . For each trial value, Algorithm 2 checks if summaries of
G obtained from Algorithm 1 have stabilized, using the fact that if k-cycles are
present, they will appear in the output of Algorithm 1 only after s∗ exceeds a
sparsity-dependent threshold [18].
If not all kmax − 1 summaries based on a given value of s∗ are sufficiently well
separated from zero, as determined by a one-sided Z-test at level α with Bonferroni
correction, then Algorithm 2 increments s∗ and the procedure repeats. Once all
summaries are sufficiently well separated from zero, or if eventually s∗ reaches
the full number of nodes in G, then the procedure restarts with the initial value
of s∗ —but any scales whose summaries were previously identically zero are then
excluded from testing. The remaining summaries are once again tested and s∗ is
incremented up to a maximum of b0.8nc, with Algorithm 2 returning equispaced
values s1 , . . . , sNs over the range 0.9s∗ –1.1s∗ , each rounded to the nearest integer.

8

Network datasets

We analyzed all networks in this study using Algorithms 1 and 2, with kmax = 9,
α = 0.01, Ns = 21, and δ = 0.05. We now describe these networks.

8.1

Networks analyzed in Fig. 4 of the main text

The networks analyzed in Fig. 5 of the main text are standard benchmark datasets
in the literature (save for Fig. 4d, synthetically generated to illustrate triadic clo84

(a)

(b)

(c)

Figure S3 | Summaries of synthetic networks. Generated according to archetypical network models: a, Preferential attachment model (1000 nodes, s∗ = 322). b
Watts–Strogatz model (500 nodes, s∗ = 150). c Blockmodel (100 nodes, s∗ = 33).
sure), which we now describe. Archetypical synthetic examples corresponding to
Figs. 4a–c are shown in Fig. S3 for comparison.
Figure 4a This 453-node metabolic network of C. elegans was introduced in [19]
as an example of a network with scale-free properties. It may be obtained from http:
//www.cise.ufl.edu/research/sparse/matrices/Arenas/. For purposes of comparison,
Fig. S3a shows the scale-based summary of a preferential attachment network (a
tree), generated with default parameter settings in the R package igraph [20].
Figure 4b This 4,941-node electrical power grid network of the western US was
introduced in [21] as an example of a network with small-world properties. It
may be obtained from http://www.cise.ufl.edu/research/sparse/matrices/Newman/
power. For comparison, Fig. S3b shows the scale-based summary of a synthetically
generated small-world network, generated using the R package igraph [20] by
perturbing a one-dimensional lattice to connect each group of five neighbors and
then rewiring at random with probability 0.05.
Figure 4c This 1,224-node network of political weblogs was introduced in [22]
as an example of network with known two-community structure. It may be obtained from http://www.cise.ufl.edu/research/sparse/matrices/Newman/polblogs.
Here we study the version analyzed in [3]. For comparison, Fig. S3b shows the
scale-based summary of a synthetically generated degree-corrected stochastic blockmodel with two communities.
85

Figure 4d These two 512-node networks demonstrate triadic closure. The first
network shown in Fig. 4d is formed by connecting pairs of nodes independently
with constant edge probability 0.0380. The second network is derived from the
first as follows. We select a triplet of nodes uniformly at random, mark one of the
three nodes, and then check if it is connected to the remaining two. If it is, and no
third edge is present, then we close the triangle and delete another edge chosen at
random from within the network—thus keeping the overall number of edges fixed.
We repeat this procedure independently, 10,000 times. As a result, from the first to
the second network, the number of triangles increases from 1303 to 3478.
Figure 4e This 1,117-node network of student friendships derives from the US
National Longitudinal Study of Adolescent Health (Add Health) [23]. We study
the version analyzed in [3], after removing an additional 5 students with missing
grade covariates. This yields six networks for middle school (grades 7–8) and high
school (grades 9–12): 209 nodes (grade 7), 242 nodes (grade 8), 237 nodes (grade
9), 161 nodes (grade 10), 137 nodes (grade 11), and 131 nodes (grade 12).

8.2

Networks analyzed in Fig. 5 of the main text

The social media discussion dataset analyzed in Fig. 5 of the main text was constructed by the now-defunct private company FSwire Limited [24] as follows. First,
from all tweets broadcasted via the social media platform Twitter over a given time
period, FSwire applied proprietary algorithms to retain only the most relevant
tweets “to extract content that impacts the capital markets” [25]. Then, FSwire
extracted the tweets related to Apple Inc., labeled using the AAPL ticker in its
database [26]. This dataset consisted of 10,000 tweets shared online between t1 =
4:18:19pm on April 8, 2014 and t2 = 9:54:45am on May 15, 2014. Finally, of these
10,000 tweets, only those containing the keyword “iPhone” were retained, yielding
N = 1986 tweets from 939 unique users.
We use these 1986 tweets to construct two types of time-varying networks. In
both cases, nodes in the networks are users broadcasting tweets. The differences
between the two constructions we consider lie in how and when edges are considered to be present between pairs of users. In both cases we remove nodes without
any connections to other users during the time period under consideration.
An aggregate network The first network we consider is one in which users
are connected if they broadcasted the same Uniform Resource Locator (URL) in
86

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

Figure S4 | Summaries of the aggregate network in Fig. 5 in the main text.
Constructed using Algorithm 2, starting from t1 = 4:18:19pm on April 8, 2014
through: a, April 14 (4:29:55pm). b April 19 (pm). c April 24 (pm). d, May 2
(4:29:55am). e, May 4 (pm). f, May 9 (pm). g, May 14 (pm). h, May 15 (am).
Summaries a and h also appear as Figs. 5b and 5f, respectively, in the main text.
tweets. The use of common URLs to determine edges in the network follows from
the observation that tweets often contain a URL linking to an article or blog post.
Thus, at time point t ∈ [t1 ,t2 ], two users are connected if they broadcasted any
tweets containing the same URL at any point in the time-window [t1 ,t]. Any edges
that appear then remain in the network, so that it accumulates edges over time.
Figure S4 shows scaled-based summaries of this aggregate network at eight
different time points. These summaries evolve quickly from a relatively uniform
set of contributions across scales (cf. Fig. 4c) to a steady state configuration which
is reminiscent of small-world connectivity (cf. Fig. 4b).
Time-localized networks We also consider a collection of time-localized networks, with edges based on the similarity of tweets broadcasted within four days
of one another. This leads to denser networks relative to the above aggregate network over similar time windows, since users may broadcast similar information
but point to different sources for it (see timeline below for examples). Here we consider two users to be connected if, within a given four-day window, they have sent
87

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

Figure S5 | Time-localized networks from Fig. 5 in the main text. Constructed
using Algorithm 2 and the following 4-day windows: a, April 11–15 (04:29:55am).
b, April 16–20 (am). c, April 21–25 (am). d, April 27–May 1 (am). e, April 28–
May 2 (am). f, May 1–5 (am). g, May 6–10 (am). h, May 11–15 (am). Summaries
a and e also appear as Figs. 5a and 5c, respectively, in the main text.
at least one pair of tweets whose edit distance distance is no greater than 29 (just
over 20% of the 140-character limit of a tweet). Thus an edge is present between
two users if, with at most 29 basic string modifications according to the restricted
Damerau–Levenshtein distance [27], one user’s tweet can be transformed into the
other’s tweet.
In this study we used the R package stringdist [28] to evaluate the edit distance between all pairs of tweets in a given four-day window. We experimented
with shorter and longer edit distances; in the former case, the networks obtained
become very sparse, whereas in the latter case, with an edit distance of 30–40,
we found many qualitative characteristics of the resulting networks to be similar.
Once the allowable edit distance is increased significantly past 40, a large proportion of tweets can be transformed into one another. We also experimented with
shorter and longer time windows (2, 3, and 5 days), selecting four-day windows in
half-day overlapping increments (66 in total between t1 and t2 ) as a compromise
between network size, proportion of nodes in the largest connected component,
and precision of time localization.
88

Figure S4 shows scaled-based summaries of eight of these time-localized networks, at approximately equally spaced time points but with a greater density following the rapid growth in network activity in late April (see Fig. 5). We see that after starting from a relatively uniform set of contributions across scales (cf. Fig. 4c),
these networks undergo a transition towards more dominant tree-like structure
(cf. Fig. 4a) before relaxing towards a configuration reflecting small-world characteristics (cf. Fig. 4b).
Timeline of events related to the social media discussion Finally, we consider
a timeline of iPhone-related news articles. As described in the main text, various
rumors, leaks and news releases impacted the social media discussion under study.
Google news single-day searches from March 30–May 30, 2014, first for “Apple”
and then separately for “iPhone,” yield the following timeline of relevant events:
March 31, 2014 First iPhone photos start leaking to Sina Weibo [29, 30].
April 1, 2014 Reuters reports iPhone suppliers to begin display production [31].
April 15, 2014 Leaks of iPhone part images reported around the world [32, 33].
April 21, 2014 Samsung begins its arguments in Apple patent infringement suit
(legal discussions ongoing for nearly two years) [34]. Apple releases video
with Tim Cook for Earth Day [35]. Taiwanese site Commercial Times discusses battery supplier issues with slimmer iPhone [36–38].
April 22, 2014 Apple releases green logo and employee shirts for Earth Day [39].
April 23, 2014 Apple reports fiscal second quarter results, announces stock split,
live streams analyst call [40].
Late April–early May Round-up of various rumors on iPhone design (e.g., [41]),
and on May 2, rumors said to “[turn] from a trickle to a torrent” [42].
April 30, 2014 iPhone mockup photos leaked to Italian site Macitynet [43].
May 2, 2014 Jury delivers verdict in Apple–Samsung patent case [44]. Macitynet
posts photos of new iPhone [45]; additional photos posted on May 4 [46].
May 5, 2014 Leak on 9to5Mac of iPhone upgrade event to clear out stock, said to
begin May 8, and subsequently announced [47].
89

May 7, 2014 Taiwanese site Commercial Times reports rumored information about
iPhone supplier orders [48], then reported by CNET on May 9 [49].
May 8, 2014 iPhone upgrade promotion email sent to customers [50].
May 10, 2014 iPhone schematics leaked to Wei Feng [51].
May 12, 2014 iPhone release date rumors reported by Tech Times [52].
May 14, 2014 Leak on 9to5Mac of iPhone screen resolution [53].
May 28, 2014 Apple confirms agreement to acquire the firm Beats by Dre [54].

9

Additional references

[1] Bollobás, B., Janson, S. & Riordan, O. The phase transition in inhomogeneous random graphs. Random Structures Algorithms 31, 3–122 (2007).
[2] Lovász, L. Large Networks and Graph Limits (Amer. Math. Soc., Providence,
RI, 2012).
[3] Olhede, S. C. & Wolfe, P. J. Network histograms and universality of blockmodel approximation. Proc. Natl. Acad. Sci. USA 111, 14722–14727 (2014).
[4] Bickel, P. J. & Chen, A. A nonparametric view of network models and
Newman–Girvan and other modularities. Proc. Natl. Acad. Sci. USA 106,
21068–21073 (2009).
[5] Bollobás, B. & Riordan, O. Metrics for sparse graphs. In Surveys in Combinatorics 2009 (eds. Huczynska, S., Mitchell, J. D. & Roney-Dougal, C. M.),
211–287 (Cambridge Univ. Press, Cambridge, 2009).
[6] Janson, S., Oleszkiewicz, K. & Ruciński, A. Upper tails for subgraph counts
in random graphs. Israel J. Math. 142, 61–92 (2004).
[7] Bollobás, B., Janson, S. & Riordan, O. The cut metric, random graphs, and
branching processes. J. Stat. Phys. 140, 289–335 (2010).
[8] Bollobás, B. & Riordan, O. Sparse graphs: Metrics and random models.
Random Structures Algorithms 39, 1–38 (2011).
90

[9] Airoldi, E. M., Blei, D. M., Fienberg, S. E. & Xing, E. P. Mixed membership
stochastic blockmodels. J. Mach. Learn. Res. 9, 1981–2014 (2008).
[10] Onnela, J.-P. et al. Taxonomies of networks from community structure. Phys.
Rev. E 86, 036104 (2012).
[11] Krzakala, F. et al. Spectral redemption in clustering sparse networks. Proc.
Natl. Acad. Sci. USA 110, 20935–20940 (2013).
[12] Söderberg, B. General formalism for inhomogeneous random graphs. Phys.
Rev. E 66, 066121 (2002).
[13] Olhede, S. C. & Wolfe, P. J. Degree-based network models. Preprint (2012).
URL http://arxiv.org/abs/1211.6537.
[14] Hintze, J. L. & Nelson, R. D. Violin plots: A box plot-density trace synergism.
Amer. Statist. 52, 181–184 (1998).
[15] Silverman, B. W. Density Estimation for Statistics and Data Analysis (Chapman and Hall, London, 1986).
[16] Alon, N., Yuster, R. & Zwick, U. Finding and counting given length cycles.
Algorithmica 17, 209–223 (1997).
[17] Perepechko, S. N. & Voropaev, A. N. The number of fixed length cycles in
an undirected graph: Explicit formulae in case of small lengths (in Russian).
Bull. Peoples’ Friendsh. Univ. Russia Ser. Math. Inform. Sci. Phys. 2, 5–11
(2012). URL http://flowproblem.ru/cycles/explicit-formulae.
[18] Rito, T., Wang, Z., Deane, C. M. & Reinert, G. How threshold behaviour
affects the use of subgraphs for network comparison. Bioinform. 26, i611–
i617 (2010).
[19] Jeong, H., Tombor, B., Albert, R., Oltvai, Z. N. & Barabási, A.-L. The largescale organization of metabolic networks. Nature 407, 651–654 (2000).
[20] Csardi, G. & Nepusz, T. The igraph software package for complex network
research. InterJournal Complex Systems 1695, 1695 (2006).
[21] Watts, D. J. & Strogatz, S. H. Collective dynamics of “small-world” networks.
Nature 393, 440–442 (1998).
91

[22] Adamic, L. A. & Glance, N. The political blogosphere and the 2004 US election: Divided they blog. In Proceedings of the 3rd International Workshop
on Link Discovery, 36–43 (ACM, New York, 2005).
[23] Resnick, M. D. et al. Protecting adolescents from harm: Findings from the
National Longitudinal Study on Adolescent Health. J. Amer. Med. Assoc.
278, 823–832 (1997).
[24] Companies House. FSwire Limited. Companies House Website (2015).
URL http://beta.companieshouse.gov.uk/company/08036480, UK registered
company number 08036480.
[25] S&P Global Market Intelligence. Company Overview of FSwire. Bloomberg
(2015). URL http://www.bloomberg.com/research/stocks/private/snapshot.
asp?privcapid=260252195.
[26] Hatzakis, S. Exclusive: FSwire, a Game-Changing Financial Services
News Wire for Twitter, Full Story. Finance Magnates (2013). URL
http://www.financemagnates.com/forex/analysis/exclusive-fswire-agame-changing-financial-services-news-wire-for-twitter-talks-to-forexmagnates.
[27] Damerau, F. J. A technique for computer detection and correction of spelling
errors. Commun. ACM 7, 171–176 (1964).
[28] van der Loo, M. The stringdist package for approximate string matching. R
J. 6, 111–122 (2014). URL http://CRAN.R-project.org/package=stringdist.
[29] Head, G. V. iPhone 6 pictures (in simplified Chinese). Sina Weibo (2014,
March 31). URL http://www.weibo.com/1870795791/ADyyblbnm.
[30] Mayo, B. Purported iPhone 6 pictures show protruding camera, rounded
edges. 9to5Mac (2014, March 31). URL https://9to5mac.com/2014/03/31/
purported-iphone-6-pictures-show-protruding-camera-rounded-edges/.
[31] Murai, R. New iPhone 6 screens to enter production as early as May.
Reuters (2014, April 1). URL http://www.reuters.com/article/us-appleiphone-display-idUSBREA3008020140401.
[32] Fuller, C. Apple iPhone 6 Leaked Photos: Possible Screen, Batteries and iOS
Screen Grab In Newest Leaks. International Business Times (2014, April
92

15). URL http://www.ibtimes.com/apple-iphone-6-leaked-photos-possiblescreen-batteries-ios-screen-grab-newest-leaks-1571936.
[33] Hemmerstoffer, S. iPhone 6: Picture of oversized iPhone screen?! (in French).
NowhereElse (2014, April 15). URL http://www.nowhereelse.fr/photofacade-iphone-6-blanc-96487.
[34] Tibken, S. Samsung kicks off infringement case against Apple with FaceTime
claim. CNET (2014, April 21). URL https://www.cnet.com/news/samsungkicks-off-infringement-case-against-apple-with-facetime-claim.
[35] AppleInsider Staff.
Apple launches “Better” environmental campaign with Tim Cook-narrated video.
AppleInsider (2014, April
21). URL http://appleinsider.com/articles/14/04/21/apple-launches-betterenvironmental-campaign-with-tim-cook-narrated-video.
[36] Zixian, Z.
New iPhone thin battery found in Taiwanese plant (in
simplified Chinese).
Commercial Times Electronic Edition (2014,
April 21).
URL http://ctee.com.tw/News/Content.aspx?id=514479&
yyyymmdd=20140421&f=9586020c7c19e6c3e26d7b8551ebcdb1&h=
1d37976b8f2475634ce463e729024bfe&t=tpp.
[37] Whitney, L. 5.5-inch iPhone 6 reportedly faces delay over battery. CNET
(2014, April 22). URL https://www.cnet.com/news/5-5-inch-iphone-6reportedly-faces-delay-over-battery-issues.
[38] Eadicicco, L. Apple’s 5.5-Inch iPhone 6 may be pushed back to 2015. Business Insider (2014, April 22). URL http://www.businessinsider.com/iphone6-reported-delayed-until-2015-2014-4?IR=T.
[39] AppleInsider Staff.
Apple store logos and employee uniforms
go green for Earth Day.
AppleInsider (2014, April 22).
URL
http://appleinsider.com/articles/14/04/22/apple-store-logos-and-employeeuniforms-go-green-for-earth-day.
[40] Apple Inc. Apple reports 2014 second quarter results. Apple Press Release (2014, April 23). URL http://www.apple.com/uk/pr/library/2014/04/
23Apple-Reports-Second-Quarter-Results.html.

93

[41] Mills, A. iPhone 6: Seven things buyers can expect. GottaBeMOBILE
(2014, April 30). URL http://www.gottabemobile.com/2014/04/30/iphone-67-things-buyers-can-expect/.
[42] Cuthbertson, A. iPhone 6 rumour round-up. International Business Times
(2014, May 2). URL http://www.ibtimes.co.uk/iphone-6-rumour-round1447072.
[43] Di Prodo, Y. iPhone 6 mockup: Here is the final version used by manufacturers (in Italian). Macitynet (2014, April 30). URL http://www.macitynet.it/
mockup-iphone-6-versione-definitiva-usata-dai-produttori-custodie/.
[44] Wakabayashi, D. & Sherr, I. Jury orders Samsung to Pay $119 Million to
Apple in patent case. Wall Street Journal (2014, May 2). URL http://www.
wsj.com/articles/SB10001424052702303678404579538422772168930.
[45] Prodo, Y. D. iPhone 6 vs Samsung Galaxy S5: Confrontation of the two
mockups (in Italian). Macitynet (2014, May 2). URL http://www.macitynet.
it/iphone-6-vs-samsung-galaxy-s5-i-mockup-confronto/.
[46] Mills, A. Samsung Galaxy S5 vs. iPhone 6: Photos show possible matchup.
GottaBeMobile (2014, May 4). URL http://www.gottabemobile.com/2014/
05/04/samsung-galaxy-s5-vs-iphone-6-photos/.
[47] Gurman, M. Apple plans “enormous” iPhone upgrade event this week to
boost sales. 9to5Mac (2014, May 5). URL https://9to5mac.com/2014/05/05/
apple-plans-enormous-iphone-upgrade-event-this-week-to-boost-sales/.
[48] Zixian, Z.
Apple iPhone 6 and Samsung to eat 15% (in simplified Chinese).
Commercial Times Electronic Edition (2014, May
7). URL http://ctee.com.tw/News/Content.aspx?id=518756&yyyymmdd=
20140507&f=0d427af3103c9091f4a9eb51c4c75dae.
[49] Reisinger, D. Apple’s iPhone 6 set for august unveiling, report says. CNET
(2014, May 9). URL http://www.cnet.com/uk/news/apples-iphone-set-foraugust-unveiling-new-report-claims/.
[50] Kahn, J. Apple kicks off its big in-store iPhone upgrade event. 9to5Mac
(2014, May 9). URL https://9to5mac.com/2014/05/09/apple-kicks-off-itsbig-in-store-iphone-upgrade-event/.
94

[51] Fam, V. Wei Feng network access to iPhone 6 design pictures from
informed sources (in simplified Chinese). Wei Feng (2014, May 9).
URL
http://www.feng.com/iPhone/news/2014-05-10/Wei%5FFeng%
5Fnetwork%5Faccess%5Fto%5FiPhone%5F6%5Fdesign%5Fpictures%
5Ffrom%5Finformed%5Fsources%5F584152.shtml.
[52] Lata, M. iPhone 6 release date rumors: Will Apple release 4.7-inch
and 5.5-inch devices this year? Tech Times (2014, May 9). URL
http://www.techtimes.com/articles/6864/20140512/apple-rumors-iphone6-upcoming-iphone-4-7-5-5-august-september-iphone-6-launch-augustlaunch-apple-rumors.htm.
[53] Gurman, M. iPhone 6 with larger, sharper 1704 x 960 resolution screen in testing. 9to5Mac (2014, May 14). URL https://9to5mac.com/2014/05/14/likelyiphone-6-with-sharper-larger-1704-x-960-resolution-screen-in-testing/.
[54] Apple Inc. Apple to acquire Beats Music & Beats Electronics. Apple Press
Release (2014, May 28). URL https://www.apple.com/pr/library/2014/05/
28Apple-to-Acquire-Beats-Music-Beats-Electronics.html.

95

