format: text

text:
# A Tractable Complex Network Model Based on the Stochastic Mean-Field Model of Distance

## 1 Introduction

The topic of complex networks, more precisely the design and theoretical analysis of stochastic models of large graphs which differ from the classical Erdős - Rényi model, has attracted intense recent attention, surveyed from a statistical physics viewpoint in  and from a rigorous mathematical viewpoint in .

Let us frame one aspect of this topic, by analogy. In freshman statistics we learn that bivariate data (e.g. heights and weights of $`n`$ individuals) can be summarized by $`5`$ summary statistics: average height, standard deviation of height, average weight, standard deviation of weight, correlation coefficient. And there is a $`5`$-parameter probability model, the bivariate Normal, which (in several precise senses) exactly corresponds to these particular summary statistics. In the context of real-world graphs (where we will always regard the number $`n`$ of vertices as large), one could analogously seek a crude statistical description by reporting a set of summary statistics. An evident choice is

* $`=`$ average vertex-degree

and recently popular extra choices include

* an exponent $`\gamma `$ characterizing power-law tail behavior of degree distribution
* a “clustering coefficient” $`\kappa `$ measuring relative density of triangles
* the average distance $`\overline{\mathrm{}}`$ between vertex-pairs.

These choices reflect and seek to quantify three qualitative features claimed to hold in many interesting graphs (from WWW links to human social networks): power-law degree distribution, local clustering of edges, and diameter growing as $`O(\mathrm{log}n)`$. So from the viewpoint of classical mathematical statistics, it would be natural to seek a several-parameter stochastic model of random graphs whose parameters could be readily identified with summary statistics of the kind above. In more detail, we propose three desiderata111From an applied viewpoint, one could regard “fitting empirical data” as the single criterion; we are of course taking a theoretical viewpoint for a satisfactory model, beyond possessing the three qualitative features mentioned above:

* mathematical tractability: one can find reasonably explicit formulas for a variety of quantities of interest
* fitting flexibility: by varying model parameters one can vary summary statistics (like the 4 listed above) broadly through their possible ranges
* naturalness: the qualitative properties emerge from some simple underlying mathematical structure rather than being forced by fiat.

Unfortunately no satisfactory such models are known. The statistical physics literature surveyed in  starts with a few elementary model-construction ideas (such as the proportional attachment and small worlds models mentioned in section 6) and then explores numerous variations. Our purpose in this paper is to introduce a new class of model we call metric copying,222We use mathematical terminology: a metric is a distance function. Confusingly, some engineers use “metric” to mean “summary statistic” and to study a particular two-parameter model (mean-field simple copying, MFSC) within this class. The description and analysis of the MFSC model involve somewhat more sophisticated mathematical visualization than has been used in previous complex networks literature. So let us first address the first two desiderata by listing results for the model (section 2), and only later (section 3) describe the model. Section 4 derives most of the formulas in section 2, and section 5 exhibits further calculations. A briefer account of the model, aimed at mathematicians, appears in .

### 1.1 Some notation

$`P()`$ denotes probability, $`E()`$ denotes expectation, and $`\mathrm{var}()`$ denotes variance. We assume familiarity with elementary probability notions of random variables and their distributions. We write $`\text{Geo}(p),\text{Bin}(m,p),\text{Exp}(\mu ),\text{Poi}(\eta )`$ for the geometric, binomial, exponential and Poisson distributions in their usual parametrizations, reviewed below. We employ a “blackboard shorthand” of also writing $`\text{Geo}(p)`$ etc for a random variable with that distribution. Thus the elementary reproductive property of the binomial distribution could be written as

$$\text{Bin}(m_1+m_2,p)\stackrel{d}{=}\text{Bin}(m_1,p)+\text{Bin}(m_2,p)$$

where the random variables on the right are independent, and where $`\stackrel{d}{=}`$ means equality in distribution. The point of this notation is that, analogous to “composition of functions” in which we interpret $`\mathrm{exp}((x1)^2)`$ as the composition of the two functions $`\mathrm{exp}(x)`$ and $`(x1)^2`$, we can “compose” (statisticians say “mix”) distributions. For instance (cf. (8) below), given a random variable $`\mathrm{\Lambda }`$ with values in $`(0,1)`$ we can write $`\text{Geo}(\mathrm{\Lambda })`$ for a random variable whose conditional distribution given $`\mathrm{\Lambda }=p`$ is the $`\text{Geo}(p)`$ distribution.

Review of elementary distributions.

$`P(\text{Geo}(p)=i)`$ $`=`$ $`(1p)^{i1}p,i=1,2,\mathrm{}`$
$`E\text{Geo}(p)`$ $`=`$ $`p^1`$
$`P(\text{Bin}(m,p)=i)`$ $`=`$ $`\left({\displaystyle \genfrac{}{}{0pt}{}{m}{i}}\right)p^i(1p)^{mi},i=0,1,\mathrm{},m`$
$`E\text{Bin}(m,p)`$ $`=`$ $`mp`$ (1)
$`\mathrm{var}\text{Bin}(m,p)`$ $`=`$ $`mp(1p)`$ (2)
$`P(\text{Poi}(\eta )=i)`$ $`=`$ $`e^\eta \eta ^i/i!,i=0,1,2,\mathrm{}`$
$`E\text{Poi}(\eta )`$ $`=`$ $`\eta .`$
The $`\text{Exp}(\mu )`$ distribution has probability density function and expectation

$`f(x)`$ $`=`$ $`\mu e^{\mu x},0<x<\mathrm{}`$
$`E\text{Exp}(\mu )`$ $`=`$ $`\mu ^1.`$
A Poisson process of rate $`1`$, say $`(0<\xi _1<\xi _2<\xi _3<\mathrm{})`$, is defined by the property

$$\xi _1,\xi _2\xi _1,\xi _3\xi _2,\mathrm{}\text{ are independent with }\text{Exp}(1)\text{ distribution}$$

and has the property

$$P(\text{some }\xi _i[x,x+dx])=1dx,0<x<\mathrm{}.$$
(3)
### 1.2 Organization of paper

Because the precise definition and a priori motivation of the model are lengthy to explain, we start by emphasising the a posteriori motivation, the fact that the model permits many explicit calculations. In first reading the formulas in section 2, focus on the left sides of equations, indicating what quantities can be calculated. The formulas on the right sides will be derived in section 4.

## 2 Formulas

### 2.1 Key methodology

Like other models involving vertices arriving and creating edges to existing vertices, the MFSC model defines a directed acyclic (no directed cycles) random graph $`𝒢_n`$ on $`n`$ vertices. A key feature of the model is that there exists a well-defined limit infinite rooted graph $`𝒢_{\mathrm{}}^{}`$ which represents the $`n\mathrm{}`$ limit of $`𝒢_n`$ rooted at a uniform random (we say “typical”) vertex. So for “local” statistics of $`𝒢_n`$, one can give “exact formulas in the $`n\mathrm{}`$ limit” by doing calculations within the limit structure $`𝒢_{\mathrm{}}^{}`$, and this methodology is how we will derive (section 4) and interpret the formulas in sections 2.22.6 below.

Note that “rooting” is introduced merely as a convenient technical way to deal with infinite graphs. By analogy, one could study two-dimensional space without introducing the origin point (cf. Euclidean geometry) but for many purposes an origin and induced coordinate system are helpful.

The MFSC model has two parameters: $`\alpha ,\lambda `$. In explicit formulas, we distinguish between a low clustering region defined by parameter ranges

$$0<\alpha <1,0<\lambda 1/\alpha \text{[low]}$$
(4)
and the complementary high clustering region defined by $`\alpha \lambda >1`$; in the latter case it is convenient to reparametrize by using $`\eta :=\lambda ^1\mathrm{log}(\alpha \lambda )`$ in place of $`\alpha `$, and the parameter ranges are

$$0<\eta <1,\eta +1/\lambda <1.\text{[high]}$$
(5)
This distinction is purely notational; there is no intrinsic “non-analyticity” in the model’s properties.

### 2.2 The two parameters control mean degree and clustering

(a). First consider $`D_{\text{in}}`$ and $`D_{\text{out}}`$, the random in-degree and out-degree of a typical vertex. Then

$$ED_{\text{in}}=ED_{\text{out}}(=,\text{ say})=\{\begin{array}{cc}\frac{\alpha }{1\alpha }& \text{[low]}\\ \frac{\eta +1/\lambda }{1\eta 1/\lambda }& \text{[high]}.\end{array}$$
(6)
(b). Second, define a normalized clustering coefficient $`\kappa _{\mathrm{cluster}}`$ in words as

> The proportion of directed $`2`$-paths $`v_1v_2v_3`$ for which $`v_1v_3`$ is also an edge.

(see (46) for a more precise definition and derivation of (7)). Then

$$\kappa _{\mathrm{cluster}}=\{\begin{array}{cc}\frac{\alpha (1\alpha )\lambda }{2\alpha ^2\lambda }& \text{[low]}\\ \frac{(\eta +\frac{1}{2\lambda })(1\eta \frac{1}{\lambda })}{(\eta +\frac{1}{\lambda })(1\eta \frac{1}{2\lambda })}& \text{[high]}.\end{array}$$
(7)
By solving (6,7) we find (section 4.6) that every pair of values of $`,\kappa _{\mathrm{cluster}}`$ in the complete range

$$0<<\mathrm{},0<\kappa _{\mathrm{cluster}}<1$$

occurs for a unique parameter pair $`(\alpha ,\lambda )`$ or $`(\eta ,\lambda )`$. Moreover the two regions can be specified as

$`0<<\mathrm{},`$ $`0<\kappa _{\mathrm{cluster}}\frac{1}{+2}`$ \[low\]
$`0<<\mathrm{},`$ $`\frac{1}{+2}<\kappa _{\mathrm{cluster}}<1`$ \[high\]
explaining our low and high clustering terminology. So the two model parameters $`\alpha ,\lambda `$ have fairly direct interpretations in terms of mean degree and clustering; of course we could re-parametrize the model in terms of $``$ and $`\kappa _{\mathrm{cluster}}`$, but the internal mathematical structure is more conveniently expressed using the given parameters.

### 2.3 Distributions of in- and out-degrees

(a). The distribution of $`D_{\text{in}}`$ is specified as

$$1+D_{\text{in}}\stackrel{d}{=}\text{Geo}(e^{\beta T})\text{ where }T\stackrel{d}{=}\text{Exp}(1)$$
(8)
and where

$$\beta =\{\begin{array}{cc}\alpha & \text{[low]}\\ \eta +1/\lambda & \text{[high]}.\end{array}$$
(9)
This works out explicitly as

$$P(D_{\text{in}}d)=\frac{\mathrm{\Gamma }(d+1)\mathrm{\Gamma }(1/\beta )}{\beta \mathrm{\Gamma }(d+1+\frac{1}{\beta })},d0$$
(10)
$$P(D_{\text{in}}=d)=\frac{\mathrm{\Gamma }(d+1)\mathrm{\Gamma }(1/\beta )}{\beta ^2\mathrm{\Gamma }(d+2+\frac{1}{\beta })},d0$$
(11)
with asymptotics

$$P(D_{\text{in}}=d)\beta ^2\mathrm{\Gamma }(1/\beta )d^{1{\scriptscriptstyle \frac{1}{\beta }}}.$$

Formula (11) appears as a special case of recent results in two-parameter proportional attachment models , but in fact is a famous 80-year old calculation – see section 4.2.

(b). The distribution of $`D_{\text{out}}`$ is determined by the distributional equation

$$D\stackrel{d}{=}\{\begin{array}{cc}_{i=1}^{\mathrm{}}\text{Bin}(1+D_i,\alpha \lambda e^{\lambda \xi _i})& \text{[low]}\\ _{i=1}^{\text{Poi}(\eta )}(1+D_i^{})+_{i=1}^{\mathrm{}}\text{Bin}(1+D_i,e^{\lambda \xi _i})& \text{[high]}\end{array}$$
(12)
where $`D,D_i,D_i^{},i1`$ are i.i.d. random variables distributed as $`D_{\text{out}}`$ and where $`0<\xi _1<\xi _2<\mathrm{}`$ are the points of a rate-$`1`$ Poisson point process on $`(0,\mathrm{})`$.

We do not know how to extract a useful explicit formula from (12) but we can compute moments. For instance

$$\mathrm{var}D_{\text{out}}=\{\begin{array}{cc}\frac{\alpha (1\alpha +\alpha ^2\lambda /2)}{(1\alpha )^2(1\frac{1}{2}\alpha ^2\lambda )}& \text{[low]}\\ \frac{(\eta +\frac{1}{2\lambda })(2\eta \frac{1}{\lambda })}{(1\eta \frac{1}{2\lambda })(1\eta \frac{1}{\lambda })^2}& \text{[high]}\end{array}$$
(13)
In the case $`\lambda =1/\alpha `$ and in the limits $`\lambda 0,\lambda \mathrm{}`$ we get explicit formulas for the distribution of $`D_{\text{out}}`$ – see section 4.3 – which show in particular that the tail of $`D_{\text{out}}`$ has geometric rather than power-law decay.

(c).

$`D_{\text{in}}`$ and $`D_{\text{out}}`$ are independent.  (14)
Because both $`D_{\text{out}}`$ and $`D_{\text{in}}`$ can take the value $`0`$, we see that $`P(D_{\text{in}}+D_{\text{out}}=0)>0`$, implying that $`𝒢_n`$ will typically not be connected (see section 2.7 for further comments).

### 2.4 Densities of induced subgraphs

One of the major advantages of the model is that, for a fixed “small” graph $`G`$, one can (in principle, and often in practice) calculate explicitly an “asymptotic density” $`\mathrm{dens}_{\mathrm{}}(G)`$ interpreted as the limit

$$\underset{n\mathrm{}}{lim}\frac{\text{number of copies of }G\text{ in }𝒢_n}{n}=\mathrm{dens}_{\mathrm{}}(G).$$

Precise definitions are fussy, and are deferred to section 4.4, which also records the explicit formulas we have found. Here let us point out the formula for triangles $`K_3`$:

$$\mathrm{dens}_{\mathrm{}}(K_3)=\{\begin{array}{cc}\frac{\alpha ^3\lambda }{(1\alpha )(2\alpha ^2\lambda )}& \text{[low]}\\ \frac{(\eta +\frac{1}{\lambda })(\eta +\frac{1}{2\lambda })}{(1\eta \frac{1}{\lambda })(1\eta \frac{1}{2\lambda })}& \text{[high]}.\end{array}$$
(15)
The formula above is the key ingredient in the formula for $`\kappa _{\mathrm{cluster}}`$. Recall the verbal description of $`\kappa _{\mathrm{cluster}}`$:

> The proportion of directed $`2`$-paths $`v_1v_2v_3`$ for which $`v_1v_3`$ is also an edge.

It is intuitively clear (and formalized at (42) that the asymptotic density for occurrence of directed $`2`$-paths $`v_1v_2v_3`$, if one does not look whether or not a third edge $`v_1v_2`$ is present, equals $`^2`$ (because of independence of in-degree and out-degree at $`v_2`$). So the verbal definition translates to

$$\kappa _{\mathrm{cluster}}=\frac{\mathrm{dens}_{\mathrm{}}(K_3)}{^2}$$

and then (15) immediately gives formula (7) for $`\kappa _{\mathrm{cluster}}`$.

### 2.5 Triangle density as a function of degree

The parameter $`\kappa _{\mathrm{cluster}}`$ gives an overall measure of triangle density. A more detailed description is provided by statistics $`C(k),k2`$ defined by

$$C(k)=\frac{E(\text{number of triangles containing a random degree-}k\text{ vertex})}{\left(\genfrac{}{}{0pt}{}{k}{2}\right)}.$$

In principle the methods of this paper could be used to obtain an exact formula for $`C(k)`$, but we shall be content with outlining (section 5.5) the tail property

$$C(k)\frac{2\beta _2}{\beta \beta _2}\times \frac{1}{k}\text{ as }k\mathrm{}.$$
(16)
See section 6 for further comments.

### 2.6 Edge-lengths

Our model has a “metric structure”, in that there is a distance $`d_{\text{metric}}(v,w)`$ between any two vertices which does not involve the realization of edges in the random graph. So each edge $`(v,w)`$ of the graph has a real-valued length $`d_{\text{metric}}(v,w)`$, and so a typical edge has a random length $`L`$. The probability density function for $`L`$ is given by the formula

$$f(x)=\frac{1\alpha }{\alpha }\underset{i=0}{\overset{\mathrm{}}{}}\frac{(i+1)\mathrm{\Gamma }(\alpha +3)(\lambda x)^i}{\mathrm{\Gamma }(i+\alpha +3)},0<x<\mathrm{}\text{[low]}.$$
(17)
Mathematica gives an equivalent expression as a sum of incomplete hypergeometric functions. One can readily observe that $`f(x)=\mathrm{exp}((\lambda \pm o(1))x)`$ as $`x\mathrm{}`$. In the underlying metric space, the number of vertices within distance $`x`$ of a typical vertex grows as $`e^x`$. So the tail behavior of $`f(x)`$ suggests

> the chance that a vertex has an edge to its $`k`$’th nearest neighbor should scale as $`k^{\lambda 1}`$

though we have not attempted detailed calculations to verify this suggestion. Note this property appears without being explicitly built into the model.

### 2.7 Other local statistics

There are further questions, concerning exact behavior in the $`n\mathrm{}`$ limit, which are in principle solvable in terms of the limit network $`𝒢_{\mathrm{}}^{}`$, but where we have been unable to obtain usefully explicit answers. A major question concerns the percolation probability

$$p_{\text{perc}}(\alpha ,\lambda )=P(\text{typical vertex is in infinite connected component of }𝒢_{\mathrm{}}^{})$$
(18)
By analogy with classical facts about the Erdős - Rényi model, we expect that above the percolation threshold, that is when $`p_{\text{perc}}(\alpha ,\lambda )>0`$, the random graph $`𝒢_n`$ will have a giant component whose size $`C_n(\alpha ,\lambda )`$ satisfies

$$n^1EC_n(\alpha ,\lambda )p_{\text{perc}}(\alpha ,\lambda ).$$

Unfortunately we do not see how to write $`p_{\text{perc}}(\alpha ,\lambda )`$ as a solution of any simple equation. By studying an easier-to-analyze directed percolation problem, it is not hard to show (section 5.3)

$$\text{if }2\beta \beta _2>1\text{ then }p_{\text{perc}}(\alpha ,\lambda )>0.$$
(19)
### 2.8 Average distance

In any graph, write $`d_{\text{graph}}(v,w)`$ for the minimal number of edges in any path from $`v`$ to $`w`$. The diameter $`\mathrm{\Delta }`$ and the average vertex-vertex distance $`\mathrm{\Lambda }`$ are defined by

$$\mathrm{\Delta }=\underset{v,w}{\mathrm{max}}d_{\text{graph}}(v,w),\mathrm{\Lambda }=\text{ave}_{v,w}d_{\text{graph}}(v,w).$$

In the context of a simple proportional attachment model it is known  that

$$E\mathrm{\Delta }_n,E\mathrm{\Lambda }_n=\frac{(1+o(1))\mathrm{log}n}{\mathrm{log}\mathrm{log}n}\text{ as }n\mathrm{}.$$

It is natural to conjecture, but hard to prove, the same result for our model (above the percolation threshold and restricted to the giant component). On the other hand it seems likely that standard techniques of abstract mathematical probability would be enough to show the weaker bound $`E\mathrm{\Lambda }_n=O(\mathrm{log}n)\text{ as }n\mathrm{}`$. Such questions cannot in principle be answered completely using $`𝒢_{\mathrm{}}^{}`$.

### 2.9 Summary of advantages and disadvantages of the model

The previous sections convey some advantages of the model:

* it has the three qualitative features desired in a complex network model (power-law degree distribution, clustering, small diameter);
* it fits the complete possible range of mean degree (or scaling exponent) and clustering parameters;
* it permits a broad range of explicit calculations.

So to be fair let us list some disadvantages from a modeling viewpoint.

* $`𝒢_n`$ is not connected (for large $`n`$); cf. section 2.7;
* there is no power law for distribution of out-degree;
* in-degree and out-degree are independent;
* the scaling exponent for in-degree is determined by the mean degree; one might prefer a model where these could be specified separately;
* in the $`n\mathrm{}`$ limit not every finite graph is possible as an induced subgraph (section 4.5).

## 3 The model

### 3.1 Metric copying models

Let us briefly outline a general modeling framework, metric copying models. Each vertex $`v`$ is a point in a metric space; that is, there is some real-valued distance $`d(v,w)`$ between any two vertices $`v,w`$. Given some rule for the positions of successive vertices $`1,2,\mathrm{}`$, and given a function $`p:[0,\mathrm{})[0,1]`$, we can construct random directed graphs $`𝒢_n`$ inductively on $`n`$ as follows. When vertex $`n`$ arrives, then
(i) for each directed edge $`(i,j)`$ of $`𝒢_{n1}`$, a “copied” edge $`(n,j)`$ is created with probability $`p(d(n,i))`$;
(ii) for each vertex $`i`$ ($`1i<n`$), a new edge $`(n,i)`$ is created with probability $`p(d(n,i))`$;
(iii) the events above are independent, except that repeat edges are censored.

Imagine $`p()`$ to be rapidly decreasing. A moment’s thought shows how this model resembles proportional attachment models. An existing vertex $`v`$ with in-degree $`d`$ has $`d+1`$ opportunities to acquire an in-edge, due to the next arriving vertex being close to $`v`$ or close to one of the $`d`$ vertices with edges to $`v`$.

In principle one could study such models based on random points in $`d`$-dimensional space, but within such settings it is notoriously hard to do explicit calculations (see e.g.  for different models of random graphs based on $`d`$-dimensional random points), and the choice of $`d`$ is arbitrary. We will avoid both problems by using a well known (in other contexts) model which is loosely interpretable as “random points in infinite-dimensional space”. Note that in $`d`$-dimensional space, the number of points within distance $`r`$ of a typical point grows as $`r^d`$; what will make our model “infinite-dimensional” is that this number grows as $`e^r`$.

For later use recall that a pre-metric $`\overline{d}(i,j)`$ is symmetric and strictly positive for $`ji`$. A pre-metric can be used to specify a metric $`d(v,w)`$ as the minimum, over paths $`v=i_0,i_1,\mathrm{},i_k=w`$, of $`\overline{d}(i_0,i_1)+\overline{d}(i_1,i_2)+\mathrm{}+\overline{d}(i_{k1},i_k)`$.

### 3.2 A $`d`$-dimensional analogy

As a final preliminary, the following analogy may be helpful. In $`d`$-dimensional space $`R^d`$, take a cube $`[n^{1/d}/2,n^{1/d}/2]^d`$ of volume $`n`$, and put $`n`$ uniform random points in that cube. This structure has a $`n\mathrm{}`$ limit, the Poisson point process in $`R^d`$ with mean intensity $`1`$ point per unit volume. Moreover the limit process, which is a spatial point process on all of $`R^d`$, can be represented as the distribution, at any fixed time, of a time-evolving process of points on all of $`R^d`$, where the evolution rules are
(i) points move away from the origin as deterministic motion with exponential rate $`1/d`$; a point at position $`x`$ at time $`t`$ will be at position $`xe^{(t^{}t)/d}`$ at times $`t^{}>t`$.
(ii) New points arrive throughout $`R^d`$ as a rate-$`1`$ space-time Poisson process; that is, the chance of a point arriving in a cube of volume $`dx`$ during a time interval $`dt`$ equals $`1dxdt`$.
Thus if one takes a volume-$`1`$ region of space at time $`t_0`$, this space expands to become volume $`e^t`$ at time $`t_0+t`$, and the arrival rate per unit time within this expanding volume is $`e^t`$ at time $`t_0+t`$.

In the limit process, one may regard the “present time” as time $`0`$, and regard the process as having evolved333This model is reminiscent of the steady-state theory of the Universe advocated by Fred Hoyle in the 1950s over time $`\mathrm{}<t0`$. Particles at the present time have ages which are independent $`\text{Exp}(1)`$ random variables independent of present positions; from the present configuration of positions and ages one can deterministically reconstruct the past evolution of the process.

### 3.3 The stochastic mean-field model of distance

Our model of an underlying metric space is specified by three rules.
(i) Point $`n`$ arrives at time $`t_n=\mathrm{log}n`$.
(ii) At the arrival time $`t_n`$, define the pre-distances $`(\overline{D}(n,j;t_n),1jn1)`$ from $`n`$ to the earlier-arriving points to be independent random variables with exponential, mean $`n`$, distribution.
(iii) Distances grow exponentially with time; $`\overline{D}(n,j;t)=e^{tt_n}\overline{D}(n,j;t_n)`$ for $`t>t_n`$.
So at time $`t`$ there are $`n=e^t`$ points, and the $`\left(\genfrac{}{}{0pt}{}{n}{2}\right)`$ pre-distances $`\overline{D}(i,j;t),1i<jn)`$ are independent random variables with exponential, mean $`e^t`$, distribution. These particular pre-distances are an instance of a pre-metric, and this pre-metric specifies a metric $`D(i,j;t),1i<jn)`$. Write $`(𝒟_t,0t<\mathrm{})`$ for this process of arriving points and distances.

Here is a key feature of this construction. At time $`t`$ pick a uniform random point $`V_t`$ as a “root”. Then there is a $`t\mathrm{}`$ limit (in distribution) structure, which is a metric space on a countable infinite number of points, one being distinguished as the root. The limit structure, called the PWIT, is described below. The meaning of “limit” is that, for arbitrary fixed $`r<\mathrm{}`$, the configuration of points in $`𝒟_t`$ within distance $`r`$ of $`V_t`$ converges in distribution to the configuration of points of the PWIT within distance $`r`$ of the root (this is local weak convergence of random networks ).

### 3.4 The PWIT

The PWIT is defined by a construction, illustrated in Figure 1444Our figures are illustrations of the definitions, rather than honest Monte Carlo simulations. Start with a single root vertex $`\mathrm{}`$. This root vertex is then given an *infinite* number of near neighbors, and the edges from the root to the near neighbors are assigned lengths according to a realization of a Poisson process $`(\xi _i^{\mathrm{}}:1i<\mathrm{})`$ of rate $`1`$ on $`(0,\mathrm{})`$. Now, recursively, each vertex $`v`$ arising as a near neighbor of a previous vertex is given an infinite number of near neighbors, and the edges to these near neighbors of $`v`$ are again assigned lengths according to an independent realization of a Poisson process $`(\xi _i^v:1i<\mathrm{})`$ of rate $`1`$. This procedure is then continued *ad infinitum*. The resulting rooted infinite tree is a well defined random object, called the *Poisson weighted infinite tree* (PWIT).

Figure 1. The PWIT. Illustration of the vertices of the PWIT within a window of radius $`3`$ centered on the root $`\mathrm{}`$. Lines indicate the near neighbor relationship, but are drawn only when both end-vertices are within the window. Thus the four near neighbors of $`\mathrm{}`$ shown are at distances $`0<\xi _1^{\mathrm{}}<\xi _2^{\mathrm{}}<\xi _3^{\mathrm{}}<\xi _4^{\mathrm{}}<3`$ from $`\mathrm{}`$, while there are an infinite number of near neighbors of $`\mathrm{}`$ at distances greater than $`3`$. Orientation of lines in pictures is arbitrary. Labels $`a,b,c`$ are included for later comparisons.

The distance $`D(v,w)`$ between two vertices of the PWIT is just the sum of edge-lengths along the path from $`v`$ to $`w`$. Though we have drawn a tree in Figure 1, the lines merely indicate the near neighbor relationships; it is better to think of the edges as absent while retaining the distances $`D(v,w)`$. In this way we may regard the vertices of the PWIT as an infinite-dimensional analog of the $`d`$-dimensional Poisson point process in section 3.2. Formula (31) later provides one formalization of “infinite-dimensional”.

The survey  gives a careful explanation of how the PWIT arises as a limit of finite models such as $`𝒟_t`$, and gives some applications to combinatorial optimization555See also  for novel scaling exponents arising in the study of the mean-field traveling salesman problem.. The key point is that, for an arriving vertex $`V_t`$ in $`𝒟_t`$, the existing vertices at smallest $`\overline{D}`$-distances correspond in the limit to the near neighbors in the PWIT. (Recall the section 3.3 construction; we are repeating the “key feature” from the last paragraph of that section.)

In the present setting, each point $`v`$ of $`𝒟_t`$ has an “age” at time $`t`$, and in the limit PWIT these ages are (exactly as in section 3.2) independent $`\text{Exp}(1)`$ random variables, $`A_v`$ say. Thus if we write $`𝒟_0^{}`$ for the PWIT and $`A_{\text{root}}`$ for the age of the root, then (given the other ages $`A_v`$ also) we can reconstruct the time-evolution of a backwards space-time PWIT process $`(𝒟_s^{},A_{\text{root}}s0)`$. Precisely, as $`s`$ runs backwards
(a) the edge-lengths $`\xi `$ decrease exponentially; at time $`s<0`$ the length is $`\xi e^s`$;
(b) a vertex $`v`$ and its incident edges are deleted at $`s=A_v`$.
Then $`𝒟_s^{}`$ is defined as the connected component containing the root at time $`s`$. This limit process relates to the finite process as follows. Let $`\stackrel{~}{A}_t`$ be the age (at time $`t`$) of the randomly-chosen vertex $`V_t`$ at time $`t`$. Then

$$(𝒟_{t+s}^{(t)},\stackrel{~}{A}_ts0)\stackrel{d}{}(𝒟_s^{},\stackrel{~}{A}_{\text{root}}s0)\text{ as }t\mathrm{}$$
(20)
where $`𝒟_{t+s}^{(t)}`$ is the configuration $`𝒟_{t+s}`$ rooted at $`V_t`$.

There is also a forwards space-time PWIT process $`(𝒟_s^{},0s<\mathrm{})`$ specified as follows. Start with the PWIT $`𝒟_0^{}`$. At time $`s`$ increases, all inter-vertex distances increase at exponential rate $`1`$. For each vertex $`v`$ present at time $`s`$, and each $`0<r<\mathrm{}`$, there is (as explained below) chance $`1drds`$ that during $`[s,s+ds]`$ a new vertex $`v^{}`$ will appear at distance $`[r,r+dr]`$ from $`v`$ as a near neighbor of $`v`$. Along with this vertex (which has current age $`0`$) is an independent copy of the PWIT rooted at $`v^{}`$, whose other vertex-ages are independent $`\text{Exp}(1)`$. The relation between the finite-$`t`$ and the limit process is analogous to (20):

$$(𝒟_{t+s}^{(t)},0s<\mathrm{})\stackrel{d}{}(𝒟_s^{},0s<\mathrm{})\text{ as }t\mathrm{}.$$
(21)
Here is the calculation leading to the coefficient “$`1`$” in

there is chance $`1drds`$ that during $`[s,s+ds]`$ a new vertex $`v^{}`$
$`\text{will appear at distance }[r,r+dr]\text{ from }v\text{ as a near neighbor of }v\text{ }.`$ (22)
In the process $`(𝒟_t)`$, during time $`[t+s,t+s+ds]`$ about $`e^{t+s}ds`$ vertices arrive; for each existing vertex, the chance an arriving vertex is within $`\overline{D}`$-distance $`[r,r+dr]`$ equals $`e^{(t+s)}\mathrm{exp}(re^{(t+s)})dr`$. So the chance in (22) equals

$$e^{t+s}ds\times e^{(t+s)}\mathrm{exp}(re^{(t+s)})dr1\times drds.$$

#### Recursive self-similarity.

Implicit in the model is the fact that the “geometry” of the space seen by a newly-arriving particle $`v^{}`$ is statistically the same as the geometry seen by a typical existing particle. This is the familiar PASTA (Poisson arrivals see time averages) property in queuing theory. In particular, at the arrival time of $`v^{}`$ the geometric components containing the different near neighbor vertices $`v_1,v_2,\mathrm{}`$ are independent copies of the PWIT. This recursive self-similarity property of the PWIT process is fundamental to its analytic tractability.

Figure 2 and its legend may be helpful.

Figure 2. The space-time PWIT process. Regarding Figure 1 as showing the PWIT at a time $`t_+`$, Figure 2 shows the space-time PWIT at an earlier time $`t_{}`$ at which only three vertices $`a,b,c`$ of the vertices in the Figure 1 window have arrived. Figure 2 shows smaller windows centered on $`a`$ and on $`c`$. The other vertices in Figure 2, and the near neighbor relation shown by lines, are still present at time $`t_+`$, but are not visible in Figure 1 because the expansion of distances has placed them outside the Figure 1 window.

### 3.5 The MFSC model

The process $`(𝒟_{t_n},n=1,2,3,\mathrm{})`$ of arrivals and inter-point distances described in section 3.3 defines an “underlying geometry”; we now define the random graph process $`(𝒢_n,n=1,2,3,\mathrm{})`$ which is the subject of this paper. Fix two parameters $`0<\alpha <\mathrm{}`$ and $`0<\lambda <\mathrm{}`$. Write

$$p(x)=\mathrm{min}(1,\alpha \lambda e^{\lambda x}),0x<\mathrm{}.$$
(23)
We now implement a version of the “metric copying” idea from section 3.1. $`𝒢_1`$ consists of vertex $`1`$ and no edges. When vertex $`n`$ arrives at time $`t_n=\mathrm{log}n`$, then
(i) for each directed edge $`(i,j)`$ of $`𝒢_{n1}`$, a “copied” edge $`(n,j)`$ is created with probability $`p(\overline{D}(n,i;t_n))`$;
(ii) for each vertex $`i`$ ($`1i<n`$), a new edge $`(n,i)`$ is created with probability $`p(\overline{D}(n,i;t_n))`$;
(iii) the events above are independent, except that repeat edges are censored.

Note that we use $`\overline{D}`$ instead of $`D`$ in determining attachment probabilities (because $`\overline{D}`$-near vertices at finite time correspond to the near neighbors in the limit PWIT). We call $`(𝒢_n,n=1,2,3,\mathrm{})`$ the mean-field simple copying (MFSC) model.

Figure 3. The graph process $`𝒢_{\mathrm{}}^{}(t_{})`$ on the realization of the space-time PWIT at time $`t_{}`$ in Figure 2. For the graph process we show all edges with either end-vertex within the window. The following figures show the evolution of $`𝒢_{\mathrm{}}^{}(t)`$ over $`t_{}<tt_+`$.

Figure 4. Figures 4 – 6 build up the graph $`𝒢_{\mathrm{}}^{}(t_+)`$ on the time-$`t_+`$ PWIT in Figure 1. Figure 4 here shows only the edges that were present at time $`t_{}`$, that is the edges shown in Figure 3. Some edges crossing outside the window have been redrawn at different angles for later convenience.

Figure 5. Suppose in Figure 1 that the center vertex $`\mathrm{}`$ arrives at time $`t_+`$; Figure 5 illustrates the graph just before that arrival. Since the time-$`t_{}`$ configuration in Figure 3, more vertices have arrived and formed edges, and distances have expanded.

Figure 6. Vertex $`\mathrm{}`$ arrives at time $`t_+`$ with near neighbors $`d,e,a,f,\mathrm{}`$. Out-edges from $`\mathrm{}`$ appear according to the metric copying scheme of section 3.1 with $`p(x)`$ given by (23). So for each near neighbor $`v`$ and each existing edge $`(v,w)`$, an edge $`(\mathrm{},v)`$ or $`(\mathrm{},w)`$ appears with probability $`p(D(\mathrm{},v))`$. In this realization, edges appeared to the near neighbors $`d`$ and $`a`$, and two other edges (one from $`d`$ and one from $`e`$) were copied.

Our focus in this paper is the study of the MFSC model using its limit structure. Just as the $`t\mathrm{}`$ limit of the time-$`t`$ “geometry” $`𝒟_t`$ is the PWIT, we can consider $`𝒢_t`$ as a structure built over $`𝒟_t`$, and we get a limit random directed graph $`𝒢_{\mathrm{}}^{}`$ as a structure built over the PWIT. The structure of $`𝒢_{\mathrm{}}^{}`$ near the root is exactly the $`t\mathrm{}`$ limit structure of $`𝒢_t`$ relative to a random (“typical”) vertex $`V_t`$, and so we can obtain (in principle) a wide variety of asymptotic results about $`𝒢_t`$ by doing calculations upon $`𝒢_{\mathrm{}}^{}`$. The only difficulty in this methodology is that we don’t have a useful explicit description of $`𝒢_{\mathrm{}}^{}`$. Instead, we can consider the space-time limits (20,21) jointly with $`(𝒢_t)`$; then in the limit we get the space-time PWIT processes existing jointly with a random graph process $`(𝒢_{\mathrm{}}^{}(s))`$, where now $`𝒢_{\mathrm{}}^{}(0)=𝒢_{\mathrm{}}^{}`$. The process $`(𝒢_{\mathrm{}}^{}(s))`$ evolves with $`s`$ and the space-time PWIT process by the rules implied by (i)-(iii) above.

Precisely, the evolution rules (illustrated by Figures 3 – 6) are

> when a new vertex $`v^{}`$ arrives in the forwards space-time PWIT process at time $`s`$, it has near neighbors $`(v_1,v_2,\mathrm{})`$ at distances $`(\xi _1,\xi _2,\mathrm{})`$, and $`𝒢_{\mathrm{}}^{}(s)`$ has put a random graph structure on the geometric component containing each $`v_i`$. For each $`i`$ and each directed edge $`(v_i,w)`$, a new edge $`(v^{},v_i)`$ or $`(v^{},w)`$ is created with probability $`p(D(v^{},v_i))`$, independently for different possible edges.

#### Recursive self-similarity.

What makes this process tractable is that the recursive self-similarity property of the PWIT extends to the random graph process; each $`v_i`$ defines a geometric component and a random graph on that component, and these are independent copies of the joint distribution of the PWIT and $`𝒢_{\mathrm{}}^{}`$. This property is used extensively in the calculations in section 4.

### 3.6 Reparametrization and extreme cases

Although the MFSC model makes sense for the full range ($`0<\alpha ,\lambda <\mathrm{}`$) of parameters, we will only consider the ranges (4,5) for which the limit mean degree is finite.

Note that definition (23) of $`p(x)`$ can be rewritten as

$`p(x)`$ $`=`$ $`\alpha \lambda e^{\lambda x},0<x<\mathrm{}\text{[low]}`$ (24)
$`p(x)`$ $`=`$ $`\{\begin{array}{cc}1\hfill & 0<x\eta \hfill \\ e^{\lambda (x\eta )}\hfill & \eta <x<\mathrm{}\hfill \end{array}\text{[high]}`$ (27)
where the reparametrization $`\eta :=\lambda ^1\mathrm{log}(\alpha \lambda )`$ when $`\alpha \lambda >1`$ is used in (27). In the two extremes of clustering, our model simplifies in different ways. For fixed $`\alpha `$, when $`n`$ is large and $`\alpha `$ is small, the model resembles the following variant of the proportional attachment model:

> An arriving vertex has a $`\text{Poi}(\alpha )`$ number of out-edges, whose end-vertices are chosen with probabilities proportional to $`1+`$ in-degree.

At the other extreme, for fixed $`\eta `$ our model makes sense with $`\lambda =\mathrm{}`$, interpreting (27) to mean $`p(x)=0,x>\eta `$. In this case the model becomes, for large $`n`$,

> An arriving vertex $`v^{}`$ chooses at random a $`\text{Poi}(\eta )`$ number of neighbors $`v_j`$, and creates edges $`(v^{},v_j)`$, and also copies each existing edge $`(v_j,w)`$ to a new edge $`(v^{},w)`$.

Clearly in the former limit we have $`\kappa _{\mathrm{cluster}}=0`$ and in the latter limit we have $`\kappa _{\mathrm{cluster}}=1`$.

## 4 Calculations

In section 4 we derive the formulas stated in sections 2.2 \- 2.6. As described in section 3.5, our methodology is to regard $`D_{\text{in}}`$ and $`D_{\text{out}}`$ as the (random) in-degree and out-degree of the root in $`𝒢_{\mathrm{}}^{}`$, and to study this using the time-dynamics of $`𝒢_{\mathrm{}}^{}(s)`$ derived from the space-time PWIT process and the evolution rules of the graph process.

### 4.1 Two helpful calculations

We will make frequent use of the next lemma.

###### Lemma 1

For integers $`u1`$ write

$$Z^{(u)}=\underset{i=1}{\overset{\mathrm{}}{}}p^u(\xi _i)=\underset{i=1}{\overset{\mathrm{}}{}}\left[\mathrm{min}(1,\alpha \lambda e^{\lambda \xi _i})\right]^u.$$

Then

$$\beta _u:=EZ^{(u)}=\{\begin{array}{cc}u^1\alpha ^u\lambda ^{u1}& [\mathrm{low}]\\ \eta +\frac{1}{u\lambda }& [\mathrm{high}]\end{array}$$
(28)
$$\mathrm{var}Z^{(1)}=\{\begin{array}{cc}\frac{1}{2}\alpha ^2\lambda & [\mathrm{low}]\\ \eta +\frac{1}{2\lambda }& [\mathrm{high}].\end{array}$$
(29)
In particular, $`\beta :=\beta _1<1`$ for all parameter values.

Proof. We will do the low clustering density case – the high density case is similar. By (3) the chance that some $`\xi _i`$ falls into an interval $`[x,x+dx]`$ is $`dx`$, so

$$\beta _u=_0^{\mathrm{}}(\alpha \lambda e^{\lambda x})^u𝑑x=\alpha ^u\lambda ^u_0^{\mathrm{}}e^{u\lambda x}𝑑x=\alpha ^u\lambda ^u/(u\lambda ).$$

Moreover, there is a general formula for variance of a sum over a Poisson (rate $`1`$) process $`(\xi _i)`$:

$$\mathrm{var}(\underset{i}{}w(\xi _i))=_0^{\mathrm{}}w^2(x)𝑑x$$

and applying this formula for $`Z^{(1)}`$ gives

$$\mathrm{var}Z^{(1)}=_0^{\mathrm{}}(\alpha \lambda e^{\lambda x})^2𝑑x=\alpha ^2\lambda ^2/(2\lambda ).$$

We next recall a classical result. Fix $`0<\theta <\mathrm{}`$. Set $`N(0)=1`$ and let $`(N(t),t0)`$ be the Yule process of rate $`\theta `$, that is the Markov process which changes only by $`+1`$ steps and for which

$$P(N(t+dt)=n+1|N(t)=n)=\theta ndt.$$

A textbook result (e.g.  sec. 5.3) says

$$N(t)\stackrel{d}{=}\text{Geo}(e^{\theta t}).$$
(30)
Note that in the PWIT, if $`N(r)`$ is the number of vertices within distance $`r`$ from the root (counting the root itself), then the process $`(N(r),r0)`$ is a Yule process of rate $`1`$, because for a vertex $`v`$ at distance $`r^{}<r`$, the chance of $`v`$ having a near neighbor at distance $`[rr^{},rr^{}+dr]`$ equals $`1dr`$. So in particular,

$$EN(r)=E\text{Geo}(e^r)=e^r.$$
(31)
### 4.2 Distribution of in-degree

We start by giving the derivation of

$$1+D_{\text{in}}\stackrel{d}{=}\text{Geo}(e^{\beta T})\text{ where }T\stackrel{d}{=}\text{Exp}(1)(\text{8})$$

for $`\beta =EZ^{(1)}`$. In the forwards space-time PWIT process, let $`N(t)`$ be $`1+`$ the in-degree of the root, when the root has age $`t`$. Thus $`N(t)`$ counts the set of vertices $`v`$ for which $`v\text{root}`$ is an edge, or $`v=\text{root}`$. When a new vertex $`v^{}`$ arrives with some $`v`$ in this set as a near neighbor, at distance $`r`$, there is chance $`p(r)`$ for the root’s in-degree to increase by $`1`$, and so from the dynamics (22) of the forwards space-time PWIT process we see that $`N(t)`$ is the Yule process of rate

$$\beta =_0^{\mathrm{}}p(r)𝑑r.$$

Use formula (30) and the fact that the age of the root of the PWIT has $`\text{Exp}(1)`$ distribution to obtain (8).

We can quickly use (8) to calculate $`ED_{\text{in}}`$.

$`1+ED_{\text{in}}`$ $`=`$ $`E(E(\text{Geo}(e^{\beta T})|T))`$
$`=`$ $`Ee^{\beta T}\text{ because }E\text{Geo}(p)=p^1`$
$`=`$ $`{\displaystyle _0^{\mathrm{}}}e^{\beta t}e^t𝑑t={\displaystyle \frac{1}{1\beta }}`$
giving $`ED_{\text{in}}=\frac{\beta }{1\beta }`$ as at (6). We now calculate the distribution of $`D_{\text{in}}`$ in the same way. Because $`P(\text{Geo}(p)i+1)=(1p)^i,i0`$ we have

$`P(D_{\text{in}}i)`$ $`=`$ $`EP(D_{\text{in}}i|T)`$
$`=`$ $`EP(1+D_{\text{in}}i+1|T)`$
$`=`$ $`E\left(1e^{\beta T}\right)^i`$
$`=`$ $`{\displaystyle _0^{\mathrm{}}}(1e^{\beta t})^ie^t𝑑t`$
$`=`$ $`\frac{1}{\beta }{\displaystyle _0^1}(1s)^is^{{\scriptscriptstyle \frac{1}{\beta }}1}𝑑s\text{ setting }s=e^{\beta t}`$
$`=`$ $`{\displaystyle \frac{1}{\beta }}{\displaystyle \frac{\mathrm{\Gamma }(i+1)\mathrm{\Gamma }(\frac{1}{\beta })}{\mathrm{\Gamma }(i+1+\frac{1}{\beta })}}\text{ using the Beta integral formula}.`$
This is (10), and (11) follows.

Historical note. Yule  introduced what we now call the Yule process in 1924 in the context of a model for evolution of new species. It is interesting that his central mathematical results are the Geometric distribution (30) \[his (5)\] and the calculation starting from our (8) \[representing, for Yule, a distribution of numbers of species in a typical genus\] of the explicit distribution (11) \[his (12)\]. After 80 years we have slicker notation but the argument is the same! Moreover Yule’s motivation was to find a simple model yielding a power-law distribution for number of species per genus, just as the motivation for the recent literature on proportional attachment models was to find a simple model yielding power-law degree distributions.

### 4.3 Distribution of out-degree

We will first derive (12). Because the out-edges are formed on arrival, we may suppose the root of the PWIT has just arrived. Consider a near neighbor $`v^{}`$ at distance $`r`$. For each out-edge of $`v^{}`$, and for $`v^{}`$ itself, there is chance $`p(r)`$ that a corresponding out-edge is created at the root, giving a total number $`\text{Bin}(1+D(v^{}),p(r))`$ of out-edges, where $`D(v^{})`$ is the out-degree of $`v^{}`$. The recursive self-similarity property (end of section 3.5) implies that the $`(D(v^{}):v^{}\text{ near neighbor of root})`$ are i.i.d. random variables distributed as $`D_{\text{out}}`$, and independent of their distances $`(\xi _i)`$ from the root. Rewriting $`(D(v^{}))`$ as $`(D^{(i)})`$ in increasing order of distance from root,

$$D_{\text{out}}=\underset{i=1}{\overset{\mathrm{}}{}}\text{Bin}(1+D^{(i)},p(\xi _i))$$
(32)
which becomes (12).

We now turn to the issue of using (32) to get information about the distribution of $`D_{\text{out}}`$. Because a directed edge contributes equally to total in-degree and to total out-degree, we know a priori that $`ED_{\text{out}}`$ must equal $`ED_{\text{in}}`$, but let us first check that we can indeed use (12) to show $`ED_{\text{out}}=\beta /(1\beta )`$. Because (1) $`E\text{Bin}(n,p)=np`$ we see

$$E\text{Bin}(1+D_i,p(\xi _i))=(1+ED_{\text{out}})Ep(\xi _i).$$

So (32) gives

$$ED_{\text{out}}=(1+ED_{\text{out}})EZ^{(1)}=(1+ED_{\text{out}})\beta $$

giving $`ED_{\text{out}}=\beta /(1\beta )`$.

Variance. The calculation of the variance $`\mathrm{var}D_{\text{out}}`$ provides a textbook illustration of the utility of the general conditional variance formula

$$\mathrm{var}X=E\mathrm{var}(X|Y)+\mathrm{var}E(X|Y).$$

We give the details in the low density case; the high density case is similar. In the defining equation (12) write $`D`$ for $`D_{\text{out}}`$ and write $`𝐃`$ and $`\mathrm{\Xi }`$ for the random sequences $`(D_i)`$ and $`(\xi _i)`$. Because (2) $`\mathrm{var}\text{Bin}(n,p)=np(1p)`$ we have

$$\mathrm{var}(D|𝐃,\mathrm{\Xi })=\underset{i}{}(1+D_i)\alpha \lambda e^{\lambda \xi _i}(1\alpha \lambda e^{\lambda \xi _i}).$$

Recursive self-similarity, as used above, implies independence of the i.i.d. sequence $`(D_i,i1)`$ and the Poisson process $`(\xi _i,i1)`$. So

$`E\mathrm{var}(D|𝐃,\mathrm{\Xi })`$ $`=`$ $`(1+ED)(EZ^{(1)}EZ^{(2)})`$ (33)
$`=`$ $`{\displaystyle \frac{\alpha (1\frac{\alpha \lambda }{2})}{1\alpha }}\text{ using (}\text{6}\text{) and (}\text{28}\text{)}.`$
Next consider the conditional expectation

$$E(D|𝐃,\mathrm{\Xi })=\underset{i}{}(1+D_i)\alpha \lambda e^{\lambda \xi _i}=W,\text{say}.$$

We will calculate $`\mathrm{var}W`$ by using the conditional variance formula. Because

$$\mathrm{var}(W|\mathrm{\Xi })=\underset{i}{}(\mathrm{var}D)\alpha ^2\lambda ^2e^{2\lambda \xi _i}$$

we have

$$E\mathrm{var}(W|\mathrm{\Xi })=(\mathrm{var}D)EZ^{(2)}=(\mathrm{var}D)\alpha ^2\lambda /2.$$
(34)
And since $`E(W|\mathrm{\Xi })=(1+ED)Z^{(1)}=\frac{1}{1\alpha }Z^{(1)}`$ we have

$$\mathrm{var}E(W|\mathrm{\Xi })=\frac{1}{(1\alpha )^2}\mathrm{var}Z^{(1)}=\frac{\alpha ^2\lambda }{2(1\alpha )^2}.$$
(35)
Using the conditional variance formula twice

$`\mathrm{var}D`$ $`=`$ $`E\mathrm{var}(D|𝐃,\mathrm{\Xi })+\mathrm{var}W`$
$`=`$ $`E\mathrm{var}(D|𝐃,\mathrm{\Xi })+E\mathrm{var}(W|\mathrm{\Xi })+\mathrm{var}E(W|\mathrm{\Xi })`$
$`=`$ $`{\displaystyle \frac{\alpha (1\frac{\alpha \lambda }{2})}{1\alpha }}+(\mathrm{var}D)\alpha ^2\lambda /2+{\displaystyle \frac{\alpha ^2\lambda }{2(1\alpha )^2}}.`$
Solving gives the equation (13) for $`\mathrm{var}D_{\text{out}}`$.

Special cases. (a). Fix $`\alpha `$. Because $`p(x)\alpha \lambda `$, in the $`\lambda 0`$ limit we can apply the Poisson limit of Binomials result to the defining equation (12) to obtain (cf. section 3.6)

$$\text{(in }\lambda 0\text{ limit)}D_{\text{out}}\stackrel{d}{=}\text{Poi}(\alpha ).$$
(36)
(b). Fix $`\eta `$. In the $`\lambda \mathrm{}`$ limit we can use the limit process of section 3.6 to show that $`1+D_{\text{out}}`$ has the distribution of the total population size in a Galton-Watson branching process666A population process starting with one individual in generation $`0`$, individuals having i.i.d. random numbers of offspring in successive generations with $`\text{Poi}(\eta )`$ offspring distribution. This is (see e.g. ) the Borel-Tanner$`(\eta )`$ distribution

$$\text{(in }\lambda \mathrm{}\text{ limit)}P(1+D_{\text{out}}=d)=\frac{(\eta d)^{d1}e^{\eta d}}{d!},d1.$$
(37)
(c). In the case $`\alpha \lambda =1`$ it turns out (an argument is sketched in section 5.4)

$$1+D_{\text{out}}\stackrel{d}{=}\text{Geo}(1\alpha ).$$
(38)
Independence of in-degree and out-degree. This independence, noted at (14), follows from the fact that in the forwards space-time PWIT process the out-degree of the root is determined at the arrival time of the root vertex; the subsequent evolution of the process of in-edges is clearly independent of the state of the graph immediately after arrival.

### 4.4 Densities of induced subgraphs

Here we give details of the definition and interpretation of “density of induced subgraphs” mentioned in section 2.4, and list explicit formulas.

Let $`G`$ and $`𝒢`$ be finite directed acyclic graphs; think of $`G`$ as small and $`𝒢`$ as large. Define “density of $`G`$ as an induced subgraph of $`𝒢`$” by

$$\mathrm{dens}(G|𝒢)=\frac{\mathrm{\#}\{V𝒢:V\text{ isomorphic to }G\}}{\mathrm{\#}\{\text{ vertices of }𝒢\}}$$

where $`\mathrm{\#}`$ denotes cardinality (“number of”) and $`V`$ denotes a vertex-subset of $`𝒢`$ with its induced subgraph. See Figure 7, where there are 3 such vertex-subsets $`\{a,b,e\},\{b,c,e\},\{c,d,e\}`$ and so where $`\mathrm{dens}(G|𝒢)=3/5`$.

Figure 7. Two rootings $`G_1^{},G_2^{}`$ of a graph $`G`$.

We want to study $`n\mathrm{}`$ limits of $`\mathrm{dens}(G|𝒢_n)`$ in our MFSC random graph model $`(𝒢_n)`$, for fixed $`G`$. To use our methodology we must first rephrase the definition of $`\mathrm{dens}(G|𝒢)`$ in terms of the rooted graph $`𝒢^{}`$ obtained by giving $`𝒢`$ a uniform random root. For such $`𝒢^{}`$, and for an arbitrarily-rooted directed graph $`G^{}`$, define a random variable

> $`𝐗(G^{}|𝒢^{})=`$ number of vertex-subsets $`V`$ of $`𝒢^{}`$ including the root such that $`𝒢^{}`$ restricted to $`V`$ is isomorphic to $`G^{}`$ via a root-preserving isomorphism.

The randomness arises only from choice of root of $`𝒢^{}`$; notation $`𝐗`$ has no special significance except to distinguish this from simpler random variables.

It is an easy fact that

$$\mathrm{dens}(G|𝒢)=\frac{E𝐗(G^{}|𝒢^{})}{\iota (G^{})}$$
(39)
where $`G^{}`$ is $`G`$ with an arbitrary choice of root, and where $`\iota (G^{})1`$ is the number of different root-choices which would give a rooted graph isomorphic to this particular choice. Rather than write a formal proof, let us just illustrate identity (39) using Figure 7. For the choice of root giving $`G_1^{}`$, the number of isomorphic vertex-subsets $`V`$ of $`𝒢^{}`$ equals $`2`$ (resp. $`1`$) if the root of $`𝒢^{}`$ chances to be $`b`$ (resp. $`d`$), and so $`E𝐗(G_1^{}|𝒢^{})=3/5`$. For the choice of root giving $`G_2^{}`$, the number of isomorphic vertex-subsets $`V`$ of $`𝒢^{}`$ equals $`1`$ (resp. $`2,3`$) if the root of $`𝒢^{}`$ chances to be $`a`$ (resp. $`c,e`$), and so $`E𝐗(G_2^{}|𝒢^{})=6/5`$. Since $`\iota (G_1^{})=1`$ while $`\iota (G_2^{})=2`$, we have checked identity (39) in this example.

Note that in Figure 7, the induced subgraph on $`\{a,b,c\}`$ is not isomorphic to $`G`$ because of the extra edge $`ac`$. Obviously we can make parallel definitions allowing extra edges (pedantically: replace “isomorphism” by “vertex-bijection and edge-surjection”) and we write $`\stackrel{\mathrm{\_}\mathrm{\_}\mathrm{\_}\mathrm{\_}}{\mathrm{dens}}(G|𝒢)`$ and $`\overline{𝐗}(G^{}|𝒢^{})`$ in this setting. For instance, in Figure 7 we have $`\stackrel{\mathrm{\_}\mathrm{\_}\mathrm{\_}\mathrm{\_}}{\mathrm{dens}}(G|𝒢)=4/5`$ and $`E\overline{𝐗}(G_1^{}|𝒢^{})=4/5`$.

The point of all this is that the definition of $`𝐗(G^{}|𝒢^{})`$ makes sense when $`𝒢^{}`$ is a rooted infinite graph. The key methodology in our analysis of the MFSC model $`(𝒢_n)`$ is that the randomly-rooted $`𝒢_n^{}`$ converge locally to a limit random infinite rooted graph $`𝒢_{\mathrm{}}^{}`$, implying via (39) that

$$\mathrm{dens}(G|𝒢_n)\frac{E𝐗(G^{}|𝒢_{\mathrm{}}^{})}{\iota (G^{})}:=\mathrm{dens}_{\mathrm{}}(G),\text{ say}.$$
(40)
In parallel.

$$\stackrel{\mathrm{\_}\mathrm{\_}\mathrm{\_}\mathrm{\_}}{\mathrm{dens}}(G|𝒢_n)\frac{E\overline{𝐗}(G^{}|𝒢_{\mathrm{}}^{})}{\iota (G^{})}:=\underset{\mathrm{}}{\overset{\mathrm{\_}\mathrm{\_}\mathrm{\_}\mathrm{\_}}{\mathrm{dens}}}(G),\text{ say}.$$
(41)
In sections 4.5 and 5.2 we calculate $`\mathrm{dens}(G)`$ for several cases of $`G`$; let us record the formulas below. Note that limit densities may be infinite, in which cases we will point out the conditions on parameters needed for finiteness.

(a). For a directed path $`\pi _r`$ with $`r1`$ edges,

$$\underset{\mathrm{}}{\overset{\mathrm{\_}\mathrm{\_}\mathrm{\_}\mathrm{\_}}{\mathrm{dens}}}(\pi _r)=^r.$$
(42)
(b). For the complete directed acyclic graph $`K_r`$ on $`r2`$ vertices, (that is, vertices $`\{1,2,\mathrm{},r\}`$ and edges $`ij`$ for $`1i<jr`$),

$$\mathrm{dens}_{\mathrm{}}(K_r)=\underset{u=1}{\overset{r1}{}}\frac{\beta _u}{1\beta _u}$$
(43)
where $`\beta _1=\beta `$ and for general $`u1`$

$$\beta _u:=\{\begin{array}{cc}u^1\alpha ^u\lambda ^{u1}& [\mathrm{low}]\\ \eta +\frac{1}{u\lambda }& [\mathrm{high}].\end{array}$$
(44)
In particular, for the case of triangles $`K_3`$ we have explicitly

$$\mathrm{dens}_{\mathrm{}}(K_3)=\{\begin{array}{cc}\frac{\alpha ^3\lambda }{(1\alpha )(2\alpha ^2\lambda )}& \text{[low]}\\ \frac{(\eta +\frac{1}{\lambda })(\eta +\frac{1}{2\lambda })}{(1\eta \frac{1}{\lambda })(1\eta \frac{1}{2\lambda })}& \text{[high]}.\end{array}$$
(45)
As already mentioned in section 2.4, the formula above is the key ingredient in the formula for $`\kappa _{\mathrm{cluster}}`$. Recall its verbal description

> The proportion of directed $`2`$-paths $`v_1v_2v_3`$ for which $`v_1v_3`$ is also an edge.

This becomes

$$\kappa _{\mathrm{cluster}}=\frac{\mathrm{dens}_{\mathrm{}}(K_3)}{\underset{\mathrm{}}{\overset{\mathrm{\_}\mathrm{\_}\mathrm{\_}\mathrm{\_}}{\mathrm{dens}}}(\pi _2)}$$
(46)
and then (42,46) immediately give the formula (7).

(c). For a directed path $`\pi _r`$ with $`r1`$ edges,

$$\mathrm{dens}_{\mathrm{}}(\pi _r)=\delta \left(\frac{\beta _1\beta _2}{(1\beta _1)(1\beta _2)}\right)^{r1}.$$
(47)
(d). For the complete bipartite directed graph $`K_{2,2}`$, for $`\beta _2<\frac{1}{2}`$ (which always holds in the low density case)

$$\underset{\mathrm{}}{\overset{\mathrm{\_}\mathrm{\_}\mathrm{\_}\mathrm{\_}}{\mathrm{dens}}}(K_{2,2})=\frac{\beta _2(\beta _2+\frac{1}{2}\beta )}{(12\beta _2)(1\beta _2)}.$$
(48)
(e). In principle one can calculate $`\mathrm{dens}_{\mathrm{}}(G^{})`$ for any $`G^{}`$, but in practice it is not clear to what extent useful explicit formulas can be found – see section 4.5 for further discussion, and for the observation that certain graphs $`G^{}`$ have $`\mathrm{dens}_{\mathrm{}}(G^{})=0`$, “asymptotically negligible density”.

### 4.5 Densities of induced subgraphs: easy explicit formulas

Recall the basic result (40) on subgraph density:

$$\mathrm{dens}(G|𝒢_n)\frac{E𝐗(G^{}|𝒢_{\mathrm{}}^{})}{\iota (G^{})}:=\mathrm{dens}_{\mathrm{}}(G)$$

where $`G^{}`$ is an arbitrary rooting of $`G`$. In calculating the right side, to simplify notation we write

$$\chi (G^{})=E𝐗(G^{}|𝒢_{\mathrm{}}^{})$$

and similarly for $`\overline{\chi }()`$ and $`\overline{𝐗}()`$ and $`\stackrel{\mathrm{\_}\mathrm{\_}\mathrm{\_}\mathrm{\_}}{\mathrm{dens}}(G)`$.

First consider $`\pi _r`$, the directed path with $`r`$ edges, rooted at the last-arriving vertex, which we will call the head. Clearly $`\chi (\pi _1)=ED_{\text{out}}=`$. Let us write out the (rather obvious) inductive argument for calculating $`\overline{\chi }(\pi _r)`$. Whether or not the root vertex of $`𝒢_{\mathrm{}}^{}`$ is the head of a $`r`$-path is determined at its arrival time. Consider a near neighbor $`v_i`$ of the root, at distance $`\xi _i`$. The expected number of $`r1`$-paths headed by $`v_i`$ equals $`\overline{\chi }(\pi _{r1})`$. So the expected number of $`r`$-paths of the form $`\text{root}v_i\mathrm{}`$ equals $`\overline{\chi }(\pi _{r1})\times P((\text{root},v_i)\text{ is edge of }𝒢_{\mathrm{}}^{})`$. Summing over $`i`$ gives

$$\overline{\chi }(\pi _r)=\overline{\chi }(\pi _{r1})\times ED_{\text{out}}=\overline{\chi }(\pi _{r1})\times $$

and so $`\overline{\chi }(\pi _r)=^r`$ by induction. This is formula (42).

The result for the complete directed graph $`K_r`$ on $`r`$ vertices is similar. For $`r=2`$ we have $`\chi (K_2)=\chi (\pi _1)=`$ and so to establish formula (43) by induction it is enough to show

$$\chi (K_{r+1})=\chi (K_r)\times \frac{\beta _r}{1\beta _r}.$$
(49)
In the forwards space-time PWIT process, consider a vertex-set $`S_r`$ isomorphic to $`K_r`$, headed by its latest-arriving vertex $`v_{}`$. At time $`t`$ after the arrival of $`v_{}`$, let $`N_t=1+`$ the number of $`K_{r+1}`$-subgraphs of the forwards space-time PWIT process which are of the form $`\{v\}S_r`$ for some $`v`$; regard the “$`+1`$” as counting $`S_r`$ itself. Then $`N_t`$ is a Yule process of rate

$$E\underset{i}{}p^r(\xi _i)=\beta _r$$
(50)
because for each vertex $`v`$ counted in $`N_t`$, a new vertex $`v^{}`$ arriving with near neighbor $`v`$ at distance $`x`$ has chance $`\left[p(x)\right]^r`$ to create the $`r`$ edges needed to make $`\{v^{}\}S_r`$ be a $`K_{r+1}`$ subgraph. Moreover these are the only ways in which a new $`K_{r+1}`$ of the form $`\{v^{}\}S_r`$ can be formed. By the Yule formula (31) $`N_t\stackrel{d}{=}\text{Geo}(\mathrm{exp}(t\beta _r))`$. Now regard $`K_{r+1}`$ as rooted by its second-latest arriving vertex. In $`𝒢_{\mathrm{}}^{}`$ the root has age $`T\stackrel{d}{=}\text{Exp}(1)`$. At its arrival time the root headed some random number of $`K_r`$’s, with mean $`\chi (K_r)`$, so by considering the mean number of $`K_{r+1}`$’s at the present time

$`\chi (K_{r+1})`$ $`=`$ $`\chi (K_r)\times (EN_T1)`$
$`=`$ $`\chi (K_r)\times (E\mathrm{exp}(T\beta _r)1)`$
$`=`$ $`\chi (K_r)\times \left({\displaystyle \frac{1}{1\beta _r}}1\right)`$
giving (49).

Other subgraphs. The derivations of formulas (47,48) dealing with paths and $`K_{2,2}`$ are relegated to sections 5.1 and 5.2.

For the graph $`\mathrm{out}\mathrm{star}_r`$ consisting of $`r`$ out-edges at a root, it is clear that

$$\overline{\chi }(\mathrm{out}\mathrm{star}_r)=E\left(\genfrac{}{}{0pt}{}{D_{\text{out}}}{r}\right)$$

and similarly

$$\overline{\chi }(\mathrm{in}\mathrm{star}_r)=E\left(\genfrac{}{}{0pt}{}{D_{\text{in}}}{r}\right),$$

and these can in principle be evaluated using (12,8).

Some subgraphs have density zero.

It is easy to see that the graph $`G^{}`$ above (where no “vertical” edge is present) has $`\chi (G^{})=0`$.

### 4.6 Reparametrization

Writing $`\alpha ,\lambda `$ in terms of $`,\kappa =\kappa _{\mathrm{cluster}}`$ by solving (6,7) gives the formulas

$$\begin{array}{ccc}\alpha & =& \frac{}{+1}\\ \lambda & =& \frac{2(1+\frac{1}{})^2}{1+\frac{1}{\kappa }}\end{array}\}0<\kappa \frac{1}{+2}$$
(51)
$$\begin{array}{ccc}\eta & =& \frac{((+2)\kappa 1)}{(+1)(1+\kappa )}\\ \lambda & =& \frac{(+1)(1+\kappa )}{2(1\kappa )}\end{array}\}\frac{1}{+2}<\kappa <1.$$
(52)
### 4.7 Edge-lengths

The previous calculations have not made very extensive use of the time-dynamics of the forwards space-time PWIT process, and in particular have not used the fact that edge-lengths grow exponentially at rate $`1`$. To derive the formula (17) for edge length density we do need to exploit such time-dynamics. We consider only the low-density case; the high density case is more complicated because the distribution in (ii) below is no longer exponential.

Consider the lengths of the in-edges at a particular vertex $`v_0`$. Following a tradition in mathematical probability, we visualize an in-edge of length $`\mathrm{}`$ as a “particle” at position $`\mathrm{}`$ on a line; we also put a particle at position $`0`$ to represent the vertex $`v_0`$ itself. If we start time $`\tau `$ with $`\tau =0`$ at the arrival time of $`v_0`$, then the evolution of the “particle process” can be specified as follows.

(i) There is a particle at position $`0`$ at all times $`\tau 0`$.

(ii) For each particle (at position $`x`$ at time $`\tau `$, say), at stochastic rate $`\alpha `$ per unit time a new particle appears at position $`x+\text{Exp}(\lambda )`$.

(iii) particle positions increase deterministically at exponential(1) rate: a particle at $`x`$ at time $`\tau `$ will be at $`xe^{\tau _0\tau }`$ at time $`\tau _0>\tau `$.

Rule (ii) derives from (22): for an existing edge $`(v^{},v_0)`$, a new vertex arriving at distance $`r`$ from near neighbor $`v^{}`$ creates an edge to $`v_0`$ with probability $`p(r)`$, so the rate at which each existing edge is copied equals $`_0^{\mathrm{}}p(x)𝑑x=\alpha `$; moreover conditional on copying, the distance $`r`$ has $`\text{Exp}(\lambda )`$ distribution, and so the length of the new edge equals the length of the old edge $`+\text{Exp}(\lambda )`$.

To analyze this particle process of edge lengths, define

$$G(\tau ,x)=E(\text{number of edges of length }>x\text{ at time }\tau )$$

so that

$$g(\tau ,x)=\frac{d}{dx}G(\tau ,x)=\text{mean edge-length density at time }\tau .$$

We shall study

$$f(x)dx=E(\text{number of in-edges at a typical vertex with length }[x,x+dx]).$$

Because the age of a typical vertex has $`\text{Exp}(1)`$ distribution, $`f(x)`$ can be written as

$$f(x)=_0^{\mathrm{}}g(\tau ,x)e^\tau 𝑑\tau .$$

The verbal description of the particle process leads to the equation

$$\frac{d}{d\tau }G(\tau ,x)=xg(\tau ,x)+\alpha _0^xg(\tau ,y)e^{\lambda (xy)}𝑑y+\alpha e^{\lambda x}.$$

Here the first term on the right expresses the deterministic exponential growth, the second term expresses birth of particles to parents not at $`0`$ (copying of existing edges) and the third expresses births to the $`0`$-particle (new edge to $`v_0`$). Multiply the terms of the equation by $`e^\tau `$ and integrate out $`\tau `$; noting

$$_0^{\mathrm{}}\frac{d}{d\tau }G(\tau ,x)e^\tau 𝑑\tau =_0^{\mathrm{}}G(\tau ,x)e^\tau 𝑑\tau =F(x),\text{say},$$

we obtain

$$F(x)=xf(x)+\alpha _0^xf(y)e^{\lambda (xy)}𝑑y+\alpha e^{\lambda x}.$$
(53)
Differentiate: $`f=(xf)^{}+\alpha f\lambda \alpha _0^xf(y)e^{\lambda (xy)}𝑑y\lambda \alpha e^{\lambda x}`$.
Rewrite with the integral term on the left, and then substitute the integral term by the expression implied in (53):

$$\lambda (xf\alpha e^{\lambda x}+F)=f+(xf)^{}+\alpha f\lambda \alpha e^{\lambda x}.$$

Differentiate: $`\lambda ((xf)^{}+\lambda \alpha e^{\lambda x}f)=f^{}+(xf)^{\prime \prime }+\alpha f^{}+\lambda ^2\alpha e^{\lambda x}`$.
Tidy: $`(xf)^{\prime \prime }+\lambda (xf)^{}+(1+\alpha )f^{}+\lambda f=0`$.
Look for a series solution $`f(x)=_{n=0}^{\mathrm{}}a_nx^n`$. Equating coefficients of $`x^n`$:

$$(n+2)(n+1)a_{n+1}+\lambda (n+1)a_n+(1+\alpha )(n+1)a_{n+1}+\lambda a_n=0.$$

That is,

$$\frac{a_{n+1}}{a_n}=\frac{\lambda (n+2)}{(n+1)(n+3+\alpha )}$$

and so

$$a_n=\frac{(\lambda )^n(n+1)\mathrm{\Gamma }(3+\alpha )}{\mathrm{\Gamma }(n+3+\alpha )}a_0.$$

One can directly check that $`f(0+)=1`$, identifying $`a_0=1`$. Because the mean in-degree is $`\alpha /(1\alpha )`$, the probability density function of a typical edge-length must be $`\frac{1\alpha }{\alpha }f(x)`$, establishing (17).

## 5 Further calculations

### 5.1 Yule arguments for subgraph density

The next Lemma abstracts the Yule process arguments used in section 4.5. Recall the reformulation there of limit subgraph density in terms of $`\chi (G)`$ and $`\overline{\chi }(G)`$.

Figure 8. Illustration of Lemma 2.

###### Lemma 2

Let $`G_0`$ be a rooted directed acyclic graph such that each vertex is a descendant of the root. Let $`q`$ be the out-degree of the root. Let $`G_1`$ be a directed acyclic graph obtained from $`G_0`$ by adding an extra vertex $`w`$ and edges $`(w,\text{root})`$ and $`c`$ further edges from $`w`$ to some children of the root (so $`0cq`$). Then

$`\overline{\chi }(G_1)/\overline{\chi }(G_0)`$ $`=`$ $`{\displaystyle \frac{\beta _{c+1}}{1\beta _{c+1}}}.`$ (54)
$`\chi (G_1)/\chi (G_0)`$ $`=`$ $`{\displaystyle \underset{j=0}{\overset{qc}{}}}(1)^j\left({\displaystyle \genfrac{}{}{0pt}{}{qc}{j}}\right){\displaystyle \frac{\beta _{c+1+j}}{1\beta _{c+1+j}}}.`$ (55)
In particular, if $`q=c`$ then

$$\chi (G_1)/\chi (G_0)=\frac{\beta _{c+1}}{1\beta _{c+1}}.$$
(57)
As a quick application let us derive formula (47) for $`\chi (\pi _r)`$ for the directed path $`\pi _r`$ on $`r`$ edges. Applying (55) with $`q=1,c=0`$,

$$\chi (\pi _{r+1})/\chi (\pi _r)=\frac{\beta _1}{1\beta _1}\frac{\beta _2}{1\beta _2}=\frac{\beta _1\beta _2}{(1\beta _1)(1\beta _2)}.$$

Because $`\chi (\pi _1)=`$ and $`\iota (\pi _r)=1`$ we obtain formula (47).

Proof of Lemma 2. We will do the harder case (55). Consider a copy of $`G_0`$ (i.e. an isomorphic subgraph) at the root of the PWIT. In the space-time PWIT process, let $`M(t)`$ be the number of copies of $`G_1`$ which contain the given copy of $`G_0`$, at time $`t`$ after the arrival of the root. Since the age $`T`$ of the root has $`\text{Exp}(1)`$ distribution,

$$\chi (G_1)/\chi (G_0)=EM(T).$$

Write $`S`$ for the set of children of the root in $`G_0`$ and write $`A`$ for a subset of $`S`$.

Consider the process of arriving vertices $`v`$ which form an edge to the root. Such a $`v`$ has a near neighbor $`v^{}`$, where either $`v^{}=\text{root}`$ or $`(v^{},\text{root})`$ is already an edge. Writing $`A(v^{})S`$ for the set of children of the root to which $`v^{}`$ creates an edge, then $`A(v)A(v^{})`$. We can now write

$$M(t)=\mathrm{\#}\{v:(v,\text{root})\text{ is an edge, }A(v)=A_1\}$$

where $`A_1`$ is the set of children of the root of $`G_1`$ to which $`w`$ has an edge. In representing $`M(t)`$ as above, we are using the hypothesis “each vertex is a descendant of the root” to ensure that, in a subgraph of the space-time PWIT isomorphic to $`G_1`$, the last-arriving vertex must be $`w`$.

Consider a sequence $`\text{root}=v_{(0)},v_{(1)},\mathrm{},v_{(i)}`$ of arriving vertices such that each vertex $`v_{(k)}`$ arrives at distance $`x_k`$ from its near neighbor $`v_{(k1)}`$. The chance that each $`v_{(k)}`$ makes an edge to the root and to each child in $`A_1`$ equals $`_{k=1}^ip^{c+1}(x_k)`$. The chance that furthermore no other child in $`S`$ acquires an edge to $`v_{(i)}`$ equals $`(1_{k=1}^ip(x_k))^{qc}`$. By considering the times $`0<t_1<t_2<\mathrm{}<t_i<t`$ of arrivals of $`v_{(i)}`$,

$$EM(t)=\underset{i=1}{\overset{\mathrm{}}{}}_{0<t_1<\mathrm{}<}_{t_i<t}𝑑t_1\mathrm{}𝑑t_i_0^{\mathrm{}}\mathrm{}_0^{\mathrm{}}𝑑x_1\mathrm{}𝑑x_i𝐩^{c+1}(𝐱)(1𝐩(𝐱))^{qc}$$

where $`𝐩(𝐱)=_{k=1}^ip(x_i)`$. Because $`𝐩^{c+1}(𝐱)(1𝐩(𝐱))^{qc}=_{j=0}^{qc}(1)^j\left(\genfrac{}{}{0pt}{}{qc}{j}\right)𝐩^{c+1+j}(𝐱)`$ and $`_0^{\mathrm{}}p^{c+1+j}(x_k)𝑑x_k=\beta _{c+1+j}`$,

$`EM(t)`$ $`=`$ $`{\displaystyle \underset{i=1}{\overset{\mathrm{}}{}}}{\displaystyle \frac{t^i}{i!}}{\displaystyle \underset{j=0}{\overset{qc}{}}}(1)^j\left({\displaystyle \genfrac{}{}{0pt}{}{qc}{j}}\right)\beta _{c+1+j}^i`$
$`=`$ $`{\displaystyle \underset{j=0}{\overset{qc}{}}}(1)^j\left({\displaystyle \genfrac{}{}{0pt}{}{qc}{j}}\right)(\mathrm{exp}(\beta _{c+1+j}t)1).`$
Calculating $`EM(T)=_0^{\mathrm{}}e^tEM(t)𝑑t`$ establishes (55).

### 5.2 Subgraph density of $`K_{2,2}`$

We have not pursued general methods for induced subgraph density beyond Lemma 2, but the argument that follows for the particular case of $`K_{2,2}`$, based on splitting into two cases, could clearly be applied somewhat more widely.

We first quote

###### Lemma 3

$`E\left({\displaystyle \genfrac{}{}{0pt}{}{\mathrm{Geo}(p)}{2}}\right)`$ $`=`$ $`p^2p^1`$ (58)
$`E\left({\displaystyle \genfrac{}{}{0pt}{}{\mathrm{Geo}(p)1}{2}}\right)`$ $`=`$ $`p^22p^1+1.`$ (59)
Next consider the graph $`G^{}`$ on the left of Figure 9.

Figure 9. Graphs related to $`K_{2,2}`$.

We will show

$$\overline{\chi }(G^{})=\frac{2\beta _2^2}{(12\beta _2)(1\beta _2)}$$
(60)
where $`\beta _2=EZ^{(2)}`$.

We start by repeating the argument in the $`r=2`$ case of (49). In the forwards space-time PWIT process, consider the newly-arrived root and an edge $`(\text{root},v_1)`$. At time $`t`$ after the arrival of the root, let $`N_t=1+`$ the number of vertices $`v`$ such that $`(v,\text{root})`$ and $`(v,v_1)`$ are both edges of the graph process; regard the “$`+1`$” as counting the root itself. Then $`N_t`$ is a Yule process of rate $`\beta _2=_0^{\mathrm{}}p^2(x)𝑑x`$. Thus at time $`t`$ there are $`\left(\genfrac{}{}{0pt}{}{N_t1}{2}\right)`$ graphs of the desired form containing the edge $`(\text{root},v_1)`$. Because the age $`T`$ of the root has $`\text{Exp}(1)`$ distribution, we see

$$\overline{\chi }(G^{})=E\left(\genfrac{}{}{0pt}{}{N_T1}{2}\right)$$

where $`=ED_{\text{out}}`$ is the expected number of edges of the form $`(\text{root},v_1)`$. Using (30) and (59),

$`\overline{\chi }(G^{})`$ $`=`$ $`E\left(e^{2\beta _2T}2e^{\beta _2T}+1\right)`$
$`=`$ $`\left(\frac{1}{12\beta _2}\frac{2}{1\beta _2}+1\right)`$
leading to (60).

Next, in $`𝒢_{\mathrm{}}^{}`$ consider

> $`Q:=\text{ number of unordered pairs }(v_1,v_2)\text{ such that}`$ $`(\text{root},v_1)`$ and $`(\text{root},v_2)`$ are edges, and $`v_1`$ and $`v_2`$ were in different geometric components at the arrival time of the root.

By considering distances $`r_1,r_2`$ from the root to the near neighbors of the geometric components containing $`v_1,v_2`$,

$$EQ=\frac{1}{2}p(r_1)p(r_2)𝑑r_1𝑑r_2\times ^2=\beta ^2^2/2.$$

Now consider in $`𝒢_{\mathrm{}}^{}`$ configurations $`\stackrel{~}{G}`$ as on the right of Figure 9, where there is no edge between $`v_1`$ and $`v_2`$, and where the root is the first-arriving vertex to have edges to both $`v_1`$ and $`v_2`$; these requirements are equivalent to saying that at the arrival time of the root, $`v_1`$ and $`v_2`$ were in different geometric components. Reuse a now-familiar argument. At time $`t`$ after the arrival of the root, let $`N_t=1+`$ the number of vertices $`v\text{root}`$ such that $`(v,v_2)`$ and $`(v,v_1)`$ are both edges of the graph process; regard the “$`+1`$” as counting the root itself. Then $`N_t`$ is a Yule process of rate $`\beta _2=_0^{\mathrm{}}p^2(x)𝑑x`$. Thus at time $`t`$ the number of possible unordered pairs $`\{v_1,v_2\}`$ which give the configuration in the figure, where we allow one of $`\{v_1,v_2\}`$ to be the root, equals $`\left(\genfrac{}{}{0pt}{}{N_t}{2}\right)`$. Because the age $`T`$ of the root has $`\text{Exp}(1)`$ distribution, we see

$$\overline{\chi }(\stackrel{~}{G})=E\left(\genfrac{}{}{0pt}{}{N_T}{2}\right)\times EQ$$

where $`\overline{\chi }(\stackrel{~}{G})`$ is the density of graphs as on the right of Figure 9, perhaps with extra edges, but subject to the requirement that the root is the first-arriving vertex to have edges to both $`v_1`$ and $`v_2`$. Using (30) and (59),

$$E\left(\genfrac{}{}{0pt}{}{N_T}{2}\right)=E\left(e^{2\beta _2T}e^{\beta _2T}\right)=\frac{1}{12\beta _2}\frac{1}{1\beta _2}=\frac{\beta _2}{(12\beta _2)(1\beta _2)}.$$

One can now write

$$\stackrel{\mathrm{\_}\mathrm{\_}\mathrm{\_}\mathrm{\_}}{\mathrm{dens}}(K_{2,2})=\frac{1}{2}\overline{\chi }(K_{2,2})=\overline{\chi }(G^{})+\overline{\chi }(\stackrel{~}{G})$$

because a $`4`$-vertex graph in $`𝒢_{\mathrm{}}^{}`$ containing $`K_{2,2}`$ is either of the form $`G^{}`$ or is the restriction of a graph of the form $`\stackrel{~}{G}`$, in which the extra root is specified by the requirement stated above (the factor $`1/2`$ reflects the fact $`\iota (K_{2,2})=2`$). Combining the formulas above gives

$$\frac{1}{2}\overline{\chi }(K_{2,2})=\frac{\beta _2^2}{(12\beta _2)(1\beta _2)}+\beta ^2^2/2\times \frac{\beta _2}{(12\beta _2)(1\beta _2)}$$

which simplifies to (48).

### 5.3 Directed percolation

Here we record some calculations without detailed explanation. In the context of the space-time PWIT and the evolving random graph process $`𝒢_{\mathrm{}}^{}(s)`$, we can seek to grow a “core” graph $`𝒞(s)`$ inside $`𝒢_{\mathrm{}}^{}(s)`$ via a greedy rule:

> a newly-arriving vertex is included in $`𝒞(s)`$ if it creates an edge to some vertex already in $`𝒞(s)`$, in which case all such edges are included in $`𝒞(s)`$.

If this construction works, we expect the process $`(𝒞(s))`$ to have a a stationary distribution $`𝒞(0)`$, say, where $`𝒞(0)𝒢_{\mathrm{}}^{}`$. Consider

$`q`$ $`=`$ $`P(\text{root}𝒞(0))`$
$`Y`$ $`=`$ $`\text{out-degree of }\text{root}\text{ in }𝒞(0)\text{, given }\text{root}𝒞(0).`$
Consider the relation

$$\stackrel{~}{Y}=\underset{i=1}{\overset{\mathrm{}}{}}\text{Ber}_i(q)\text{Bin}_i(1+Y_i,p(\xi _i))$$

where we write $`\text{Ber}(p)`$ for a Bernoulli$`(p)`$ r.v. (taking value $`1`$ with probability $`p`$ and value $`0`$ otherwise). Using the recursive structure of the limit random graph process, we see that $`q`$ and $`Y`$ solve the equations (for unknown $`0<q<1`$ and an unknown distribution $`Y`$ on $`\{1,2,3,\mathrm{}\}`$)

$$Y\stackrel{d}{=}\text{dist}(\stackrel{~}{Y}|\stackrel{~}{Y}1);q=P(\stackrel{~}{Y}1).$$
(61)
Define $`p_{\text{dir-perc}}(\alpha ,\lambda )`$ to be the solution $`q`$ if it exists, and to be $`0`$ otherwise. The interpretation of this quantity in terms of the finite random graph process $`(𝒢_n,n1)`$ is that

$$n^1E𝐓p_{\text{dir-perc}}(\alpha ,\lambda )$$

where $`𝐓`$ is the maximal size of a tree in $`𝒢_n`$ directed toward some root. So in particular, for $`p_{\text{perc}}(\alpha ,\lambda )`$ defined at (18),

$$p_{\text{dir-perc}}(\alpha ,\lambda )p_{\text{perc}}(\alpha ,\lambda ).$$

Equation (61) in principle determines $`p_{\text{dir-perc}}(\alpha ,\lambda )`$, but to get an explicit bound we reuse an underlying idea. Because $`1+Y_i2`$,

$$\stackrel{~}{Y}\underset{i=1}{\overset{\mathrm{}}{}}\text{Ber}_i(q)\text{Bin}_i(2,p(\xi _i))=Y^{},\text{ say.}$$

If the equation

$$q=P(Y^{}1)$$
(62)
has a solution $`q>0`$ then one can argue $`p_{\text{dir-perc}}(\alpha ,\lambda )q`$. But (62) is an explicit equation

$$1q=\mathrm{exp}\left((2p(x)p^2(x))q𝑑x\right)=\mathrm{exp}((2\beta \beta _2)q).$$

If $`2\beta \beta _2>1`$ there is a solution $`q>0`$, establishing (19).

### 5.4 Out-degree in the case $`\alpha \lambda =1`$

The special property of this case is that $`p(x)=e^{\lambda x}`$. On the PWIT consider

$$Y=\underset{v\text{root}}{}\text{Ber}(e^{\lambda d(v,\text{root})}).$$

This satisfies the same recursion (in the special case) as does $`D_{\text{out}}`$. But there is another way to study $`Y`$, which we sketch briefly. Either the root of the PWIT has no children within a small distance $`\delta `$; or it does have a child, and the distances to the other descendants of the root and of this child are independent copies of the PWIT distances. Because the effect on $`Y`$ of increasing distances by $`\delta `$ is to censor each Bernoulli success with probability $`\lambda \delta `$, we see that $`Y`$ is the stationary distribution of the continuous-time Markov chain on states $`\{0,1,2,\mathrm{}\}`$ with dynamics

$`yy1`$ $`:`$ $`\text{rate }\lambda y`$
$`yy+\widehat{Y}+1`$ $`:`$ $`\text{rate }1`$
where $`\widehat{Y}`$ is an independent copy of $`Y`$. One can now check algebraically that

$$P(Y=y)=(1\frac{1}{\lambda })(\frac{1}{\lambda })^y,y0$$

solves the balance equations for this chain. That is, $`1+D_{\text{out}}`$ has $`\text{Geo}(1\frac{1}{\lambda })=\text{Geo}(1\alpha )`$ distribution, as asserted in (38).

Remark. Antar Bandyopadhyay (personal communication) has given a purely analytic verification of (38).

### 5.5 Triangle density of a function of degree

Here we outline an argument for (16). Because $`D_{\text{in}}`$ has power-law tail and $`D_{\text{out}}`$ has geometric tail, when $`D=D_{\text{in}}+D_{\text{out}}`$ is large, say $`k`$, then $`D_{\text{out}}=O(1)`$ and $`D_{\text{in}}=kO(1)`$. It is then not hard to argue that the large-$`k`$ behavior for $`C(k)`$ will be the same as for

$$C^{}(k)=\frac{E(\text{number of triangles with in-vertex }v_0|v_0\text{ has in-degree }k)}{\left(\genfrac{}{}{0pt}{}{k}{2}\right)}$$

where the in-vertex of a triangle is the vertex with two in-edges.

Recall from section 4.2 that

> $`N(t)=`$ number of in-edges at a typical vertex $`v_0`$ at time $`t`$ after its arrival

is the Yule process of rate $`\beta `$. Write $`v_1,v_2,v_3,\mathrm{}`$ for the successive arriving vertices which create edges to $`v_0`$, and for $`i2`$ write

$$M_i=\text{ number of edges from }v_i\text{ to }\{v_{i1},v_{i2},\mathrm{},v_1\}.$$

After $`v_k`$ arrives there are $`M_2+M_3+\mathrm{}+M_k`$ triangles with in-vertex $`v_0`$. If we can show

$$EM_kb\text{ as }k\mathrm{}$$

then we will have

$$C(k)\frac{kb}{\left(\genfrac{}{}{0pt}{}{k}{2}\right)}\frac{2b}{k}.$$
(63)
Here we are sliding over the fact that $`1+D_{\text{in}}`$ is the Yule process evaluated at an independent $`\text{Exp}(1)`$ time $`T`$; conditioning this to take a value $`k`$ does not affect the properties used in the argument below.

Suppose vertices $`v_1,\mathrm{},v_{k1}`$ have arrived and consider what edges will be created when $`v_k`$ arrives. The dynamics (22) of the space-time PWIT say

> the rate of arrival of new vertices with some one of $`v_0,v_1,\mathrm{},v_{k1}`$ as near neighbor and at distance $`[x,x+dx]`$ from that near neighbor equals $`kdx`$. The index $`I`$ of that near neighbor $`v_I`$ is uniform on $`\{0,1,\mathrm{},k1\}`$.

Such an arriving vertex creates an edge to $`v_0`$ with probability $`p(x)`$. So conditional on that event (meaning the arriving vertex is $`v_k`$), the distance $`\widehat{\xi }`$ from the near neighbor $`v_I`$ and the index $`I=I_k`$ of that near neighbor satisfy
(i) $`\widehat{\xi }`$ has probability density function $`\widehat{p}(x)=\frac{p(x)}{{\scriptscriptstyle p(u)𝑑u}}`$;
(ii) $`I`$ is uniform on $`\{0,1,\mathrm{},k1\}`$.
Because $`v_k`$ will copy each of the $`M_I`$ out-edges from $`v_I`$ with probability $`p(\xi )`$ each, and create an edge to $`V_I`$ with the same probability, we obtain the recursion

$$M_k\stackrel{d}{=}\text{Bin}(1+M_I,p(\widehat{\xi }))$$

where $`M_1=0`$ and where we interpret the right side as $`0`$ when $`I=0`$. So the limit $`lim_kEM_k=b`$ solves $`b=(1+b)Ep(\widehat{\xi })`$ and so $`b=\frac{Ep(\widehat{\xi })}{1Ep(\widehat{\xi })}`$. Finally,

$$Ep(\widehat{\xi })=p(x)\widehat{p}(x)𝑑x=\beta _2/\beta .$$

So $`b=\frac{\beta _2}{\beta \beta _2}`$ and (16) follows from (63).

## 6 Comparison with other models

Recent complex networks models fall into two categories. In the small worlds models popularized by Strogatz and Watts, vertices are points in $`d`$-dimensional space, which automatically provides a metric distance between vertices, and the model uses some rule to create a random graph with short-range and long-range edges. In purely graph-theoretical models, such as the basic proportional attachment model popularized by Albert and Barabási777but really just a minor variation of Yule’s idea: see Lecture 4 of  the vertices have no “intrinsic structure” other than that provided by the graph; we visualize this as saying that each pair of vertices is metric distance $`1`$ apart. In a metric copying model we visualize vertices as points in some abstract metric space, representing (in the case of web pages, say) the difference between the content of the pages, or (for people) some notion of “social distance” based on location, education, profession, interests etc of the individuals. In detail the mean-field model of distance model is used for mathematical tractability rather than any claimed realism. But the exponential growth of number of vertices with metric distance is intermediate between, and surely in many contexts more plausible than, the alternatives implicit in the two standard categories of model above.

Within graph-theoretic models, the idea of distance preferences in attachment has been explored (see  and citations therein). But the general idea of combining proportional attachment with metric geometry has scarcely been explored888 gives a simulation study of an explicitly power-law model, as well as interesting empirical study of a notion of lexical distance between web pages, and the specific use of the mean-field model is novel.

As a technical note, the mean-field model is a zero-parameter999Zero dimensionless parameters, to be pedantic model of distance. Our full network model has the two parameters $`(\alpha ,\lambda )`$; in contrast a typical small-worlds network model has four parameters (dimension, number of short-range links, constant and exponent for probability of long-range edges).

As another technical note, the property (cf. (16)) $`C(k)c/k`$ has been proposed  as a criterion for identifying networks which are “hierarchical” in some sense. But in our finite-$`n`$ model (recall section 3.5) each vertex has qualitatively the same behavior, rather than different vertices being a priori assigned different hierarchical roles. So our model is non-hierarchical, and we are inclined to regard the criterion as ineffective101010One could alternatively regard it as indicating some subtle emergent hierarchical structure; cf. .

The specific model studied in this paper is intended as a “general purpose” model rather than being tuned to some particular subclass of real-world networks. Having as one ingredient the now-familiar proportional attachment feature, one could look at the many existing variant models in the literature and explore them within our platform. In other words, there are many ways to add a third parameter intended to express some presumed real-world feature or some theoretical desideratum. For instance

* One can impose connectivity by requiring that a new vertex always links to its nearest neighbor.
* one can add rules allowing a new vertex to immediately acquire in-edges, or for edges to randomly appear between existing edges. Such rules can be designed (as in e.g.  section 11) to produce power law distributions for in-degree.

### 6.1 Concluding remarks

In this paper we have focused on

* describing the model and its conceptual background (section 3)
* listing explicit formulas (sections 2.22.6) and exhibiting the calculations which lead to these formulas (sections 4 and 5).

We are postponing to a later paper consideration of

* technical issues in the relation between the finite-$`n`$ model and its infinite limit $`𝒢_{\mathrm{}}^{}`$
* the open problems indicated in sections 2.72.8, whose study requires the “bounding” techniques of theoretical mathematical probability rather than explicit calculations.

#### Acknowledgement

I thank an anonymous referee for detailed constructive comments.


text:
# Radio Observations of the Magnetic Fields in Galaxies

## 1. Introduction or What do we get from Radio Observations?

Radio observations of the continuum emission are best suitable to study the magnetic fields in galaxies. The total intensity of the synchrotron emission gives the strength of the total magnetic field. The linearly polarized intensity reveals the strength and the structure of the resolved regular field in the plane of the sky. However, the observed polarization vectors suffer Faraday rotation and depolarization (i.e. a decrease of the degree of linear polarization when compared to the intrinsic one) on the way from the radiation’s origin to us. Correction for Faraday rotation is possible with observations at two or better more wavelengths by determining the rotation measure RM (being proportional to $`n_\mathrm{e}B_{}𝑑l`$). The rotation measure itself is a measure of the magnetic field strength parallel to the line of sight, whereas its sign gives the direction of this magnetic field component. The field strength of both components, parallel and perpendicular to the line of sight, together with the information of the intrinsic polarization vectors enables us in principle to perform a ‘tomography’ of the magnetic field.

## 2. Faraday Rotation and Depolarization Effects

Figure 1 gives an example of observations of M51 at 4 different wavelengths, all smoothed to the same linear resolution of $`75^{\prime \prime }`$ HPBW. The vectors are rotated by $`90^{}`$ but not corrected for Faraday rotation. The figure illustrates nicely the different effects of Faraday rotation and depolarization effects depending on the observing wavelength: the observed vectors at $`\lambda `$2.8 cm and $`\lambda `$6 cm are mainly parallel to the optical spiral arms as expected in spiral galaxies (see below), Faraday rotation is small at centimeter wavelengths. However, the pattern looks very different at $`\lambda `$18/20 cm where Faraday rotation is expected to be strong. Further, we see a region in the northeastern part of M51 with complete depolarization.

After substraction of the thermal fraction of the emission we distinguish between beam-dependent and wavelength-dependent depolarization. The difference in depolarization at different wavelengths in maps with the same linear resolution should be purely wavelength dependent where two different wavelength-dependent depolarization effects are important to consider: the differential Faraday rotation and Faraday dispersion as despcribed by Burn (1966) and Sokoloff et al. (1998). The latter effect is due to turbulent magnetic fields within the source and between the source and us, whereas the Faraday rotation depends on the regular magnetic field within the emitting source. The differential Faraday rotation has a strong wavelength dependence as shown e.g. in Fig. 1 in Sokoloff et al. (1998) leading to a complete depolarization at $`\lambda `$20 cm already at a $`\mathrm{RM}40\mathrm{rad}/\mathrm{m}^2`$, with again decreasing depolarization for higher RMs. Such an effect has first been detected in small isolated areas in M51 (Horellou et al. 1992). At $`\lambda `$6 cm the depolarization is much smaller, increasing smoothly to zero at $`\mathrm{RM}400\mathrm{rad}/\mathrm{m}^2`$ (the first zero point is at $`\mathrm{RM}=\pi /(2\lambda ^2)`$).

Hence, the galaxies may not be transparent in linear polarization at decimeter wavelengths so that we may observe just an upper layer of the whole disk. At centimeter wavelengths we do not expect complete depolarization even in galaxies viewed edge-on, i.e. centimeter wavelengths are best suitable to trace the magnetic field structure.

## 3. Magnetic Field Strength and Structure

The total magnetic field strength in a galaxy can be estimated from the nonthermal radio emission under the assumption of equipartition between the energies of the magnetic field and the relativistic particles (the so called energy equipartition). The degree of linear polarization and some assumptions of the geometry of the magnetic field give the strength of the magnetic field that has a uniform direction within the beam size. The estimates are based on the formulae given by e.g. Pacholczyk (1970) and Segalowitz et al. (1976), and are described e.g. by Krause et al. (1984) and Beck (1991).

### 3.1. … in Spiral Galaxies

The magnetic field has been found to be mainly parallel to the galactic disk and to show a large spiral pattern similar to that of the optical spiral arms. The total magnetic field strength is generally highest at the positions of the optical spiral arms, whereas the highest regular fields are found offset of the optical arms and in the interarm region.

The mean equipartition value for the total magnetic field strength for a sample of 74 spiral galaxies observed by Niklas (1995) is on average $`8\mu `$G with a standard deviation of $`3\mu `$G. It can however reach values of about $`20\mu `$G within spiral arm regions as e.g. in NGC 6946 (Beck 1991). Strongly interacting galaxies or galaxies with a strong central radio emission tend to have generally stronger total magnetic fields. The strengths of the regular fields are typically 1–5 $`\mu `$G in the interarm regions in nearby spirals but reach locally $`13\mu `$G in NGC 6946 (Beck & Hoernes 1996).

### 3.2. Regular Magnetic Fields and Dynamo Action

The large-scale magnetic field is generally thought to be amplified and maintained by the action of a large-scale dynamo. According the mean field dynamo theory (e.g. Ruzmaikin et al. 1988; Wielebinski & F. Krause 1993; Beck et al. 1996; Lesch & Chiba 1997) the structure of the large-scale field is also given by the dynamo action. It is generally of spiral shape with different azimuthal field directions and symmetries. The mode that can be excited most easily is the axisymmetric mode (ASS) followed by higher modes as the bisymmetric (BSS), etc. The field configurations can be either symmetric (quadrupole type) or asymmetric (dipole type) with respect to the galactic plane. According to the dynamo theory the pitch angle of the magnetic field spiral is determined by the dynamo numbers, not by the pitch angle of the gaseous spiral arms.

ASS and BSS field configurations can be distinguished observationally by analyzing the rotation measures or – more sophisticated – by analyzing directly the observed polarization vectors at different wavelengths (as has been described e.g. in Sokoloff et al. (1992) and Berkhuijsen et al. (1997)). It has been found that only M31 and IC342 show clear ASS fields (Beck 1982; Krause et al. 1989a), whereas many other galaxies seem to have a superposition of different modes.

A special case is M81 as it has a dominating BSS field field (Krause et al. 1998b; Sokoloff et al. 1992). The dominance of the BSS field structure requires additional physical mechanism to be invoked that can occur only in rare cases. For M81 a three-dimensional, nonlinear dynamo model has been developed including the disturbed velocity field due to the encounter with its companion NGC 3077 (Moss et al. 1993) or alternatively, parametric resonance with the spiral density wave as has been proposed by Chiba & Tosa (1990) and investigated numerically by Moss (1996).

Most other spiral galaxies observed so far indicate a mixture of magnetic modes. The analysis of the observations at all 4 frequencies of M51 (Fig. 1) revealed even two different magnetic field configurations for the disk and the halo resp. (Berkhuijsen et al. 1997): a halo with an axisymmetric field configuration parallel to the disk with magnetic field lines pointing inwards and a superposition of an axisymmetric and a bisymmetric field with about equal weights in the disk. The magnetic field lines in the disk are spirals generally directed outwards except in a few sectors in the inner northwestern part of M51 as shown in Fig. 2.

It is clear that such a global description of the regular magnetic field cannot describe local effects that become more and more visible with increasing linear resolution of the observations. Further, in grand-design galaxies the magnetic field lines follow quite often the dust lanes. In M51 e.g. one dust lane in the eastern part crosses the optical spiral arm, so does the regular magnetic field (visible in Fig. 1 at in the short wavelengths observations).

### 3.3. Magnetic Arms

The regular interarm field in M81 fills the whole interarm region. Different to this some galaxies host so-called magnetic arms. Long, highly polarized arms disconnected from the optical spiral arms were first discovered in IC342 (Krause et al. 1989a; Krause 1993). Two symmetric magnetic arms running right in the interarm region parallel to the optical spiral arms were found in NGC 6946. Their width is less than 1 kpc, hence they do not fill the whole interarm region. Magnetic arms have also been found in NGC 2997 (Han et al. 1999) and M83 (Beck, Ehle & Sukumar in prep.).

Several models have been developed to explain these magnetic arms. Slow MHD waves have been proposed by Fan & Lou (1996) and Lou & Fan (1998) to explain the generation of magnetic arms shifted with respect to the optical spiral arms. These MHD waves occur only in an almost rigidly rotating disk. However, all galaxies with magnetic arms are found to rotate differentially beyond 1–2 kpc from the center, different to older measurements with lower angular resolution. Han et al. (1999) found some correlation between the magnetic arms and interarm gas features generated at the 4:1 resonances in numerical models of Patsis et al. (1997).

In the framework of dynamo theory the generation of magnetic arms can be described if one considers that the turbulent velocity of the gas is higher in the optical arms (Moss 1998; Shukurov 1998), or that turbulent diffusion is larger in the arms (Rohde et al. 1999). Both effects reduce the dynamo number in the spiral arms when compared to the interarm regions and hence allow to generate magnetic arms preferently in the interarm region.

### 3.4. … in Flocculent and Irregular Galaxies

Regular magnetic fields have also been detected in flocculent galaxies like M33 (Buczilowski & Beck 1991) and NGC 4414 (Soida et al. 2002). These are galaxies with a flocculent spiral structure without signs of the action of density waves. The mean degree of polarization (corrected for different angular resolution) is similar between flocculent and grand-design galaxies (Knapik et al. 2000). As expected from classical $`\alpha \mathrm{\Omega }`$ dynamo models the dynamo works well without the assistance of density waves.

Even in a dwarf irregular galaxy with weak rotation and non-systematic gas motion like NGC 4449 a large-scale (partly spiral) regular magnetic field has been observed (Chyzy et al. 2000). The strength of the regular field reaches $`7\mu `$G and that of the total field $`14\mu `$G, which is high even in comparison with fields strengths of radio-bright spirals. The absence of ordered differential rotation requires a different kind of dynamo action in this galaxy. A fast field amplification is predicted by a dynamo e.g. driven by magnetic buoyancy and sheared Parker instabilities (e.g. Moss et al. 1999; Hanasz & Lesch 1998, 2000) or without any $`\alpha `$ effect at all (Blackman 1998).

### 3.5. … in Barred Galaxies and Other Shocked Areas

A sample of 20 barred galaxies has been observed extensively in total power and linear polarization (Beck et al. 2002). They found that the total radio emission (and hence the total magnetic field) is strongest along the bar and correlates with the bar length. The regular magnetic field is enhanced upstream of the shock fronts in the bar. The upstream field lines are at large angle to the bar, but turn sharply towards the bar about 1 kpc upstream from the dust lanes as observed in NGC 1097 (Beck et al. 1999). According to these authors similar effects have also been observed in NGC 1365, NGC 1672, and NGC 7552.

Indications for a compression of the galactic magnetic field possibly by gas tidally stripped during an interaction with the neighbouring galaxy have been observed in NGC 3627 (Soida et al. 2001) where the observed regular field apparently crosses the dust lanes at a large angle in the east. Another example for such a compression is the wind-swept galaxy NGC 4254 (Soida et al. 1996).

### 3.6. Edge-on Galaxies and Vertical Fields

Several galaxies seen edge-on have been observed in radio continuum and polarization. Most of them have regular magnetic fields that are parallel to the galactic disks (Dumke et al. 1995), only a few are found with large-scale vertical fields like M82 (Reuter et al. 1994), NGC 4631 (Golla & Hummel 1994), NGC 4666 (Dahlem et al. 1997), and NGC 5775 (Tüllmann et al. 2000).

The apparent disk thicknesses vary quite a lot among the galaxies with plane-parallel field as well as their intensities does. Interferometer observations of edge-on galaxies have to be combined with single-dish observations in order to correct for the missing zero-spacings before the scale heights of the emission perpendicular to the disk (in z-direction) can be determined. We found that the emission in z-direction can best be fitted with two exponential functions, whose scale heights are about equal for all four galaxies with plane-parallel fields that have been analyzed so far, namely NGC 891, NGC 3628, NGC 4565, NGC 5907 (Dumke & Krause 1998; Dumke et al. 2000). The scale height for the thin disk is $`300`$ pc and that of the thick disk/halo is $`1.8`$ kpc for these galaxies, independent of the star-forming activity and interaction state.

Recent $`\lambda `$3.6 cm observations of NGC 4631 obtained with the Effelsberg 100-m telescope are presented in Fig. 3. Faraday rotation could be determined between this wavelength and $`\lambda `$6.2 cm observations with the VLA and revealed $`300\mathrm{rad}/\mathrm{m}^2<\mathrm{RM}<300\mathrm{rad}/\mathrm{m}^2`$. The vectors shown in Fig. 3 give the intrinsic magnetic field orientation. NGC 4631 has a large-scale vertical magnetic field in the central 7 kpc. Outside this radius the field is plane parallel in the western half but still has vertical field components in the eastern half. The RM does not show a typical symmetric pattern as expected from a dipole or quadrupole field. Hence we conclude that the vertical field is rather wind-driven and related to the high star-forming activity in this galaxy. The exponential scale heights for NGC 4631 are about 50% larger than those found for galaxies with plane-parallel fields which may also be related to the galactic winds and vertical fields.

Another edge-on galaxy is M104, the Sombrero galaxy, classified as an Sa galaxy and known for its huge bulge. We observed M104 at $`\lambda `$6.2 cm with the VLA in D array and detected that the observed E+90 vectors are surprisingly regular and mainly parallel to the galactic disk as shown in Fig. 4. Unfortunately, the observations could not yet be corrected for Faraday rotation because we have no observations at another wavelength. The regularity of the vectors at $`\lambda `$6.2 cm may indicate that Faraday rotation is rather small. Hence it seems that the regular magnetic field in M104 is mainly disk parallel, also inside the central 6 kpc where the rotation curve is still rising. The radio emission in z-direction can best be fitted by a one-component Gaussian rather than an exponential function with a scale height of $`3`$ kpc. According to Combes (1991) a Gaussian z-distribution is just expected for a thin disk inside a self-gravitating mass distribution, i.e. the huge bulge in M104.

## References

Beck, R. 1982, A&A, 106, 121

Beck, R. 1991, A&A, 251, 15

Beck, R., & Hoernes, P. 1996, Nature, 379, 47

Beck, R., Brandenburg, A., Moss, D., Shukurov, A., & Sokoloff, D. 1996, ARA&A, 34, 155

Beck, R., Ehle, M., Shoutenkov, V., Shukurov, A., & Sokoloff, D. 1999, Nature, 397, 324

Beck, R., Shoutenkov, V., Ehle, M., Harnett, J. I., Haynes, R. F., Shukurov, A., Sokoloff, D. D., & Thierbach, M. 2002, A&A, 391 83

Berkhuijsen, E. M., Horellou, C., Krause, M., Neininger, N., Poezd, A. D., Shukurov, A., & Sokoloff, D. 1997, A&A, 318, 700

Blackman, E. G. 1998, ApJ, 496, L17

Buczilowski, U. R., & Beck, R. 1991, A&A, 241, 47

Burn, B. J. 1966, MNRAS, 133, 67

Chiba, M., & Tosa, M. 1990, MNRAS, 244, 714

Chyzy, K. T., Beck, R., Kohle, S., Klein, U., & Urbanik, U. 2000, A&A, 355, 128

Combes, F. 1991, ARA&A, 29, 195

Dahlem, M., Petr, M. G., Lehnert, M. D., Heckman, T. M., & Ehle, M. 1997, A&A, 320, 731

Dumke, M., Krause, M., Wielebinski, R., & Klein, U. 1995, A&A, 302, 691

Dumke, M., & Krause, M. 1998, in IAU Coll. 166, The Local Bubble and Beyond, ed. D. Breitschwerdt & M. Freyberg, Lecture Notes in Physics 506, Springer Verlag, Berlin, 555

Dumke, M., & Krause M. 2000, A&A, 355, 512

Fan, Z., & Lou, Y.Q. 1996, Nature, 383, 800

Golla, G., & Hummel, E. 1994, A&A, 284, 777

Han, J. L., Beck, R., Ehle, M., Haynes, R. F., & Wielebinski, R. 1999, A&A, 348, 40

Hanasz, M., & Lesch, H. 1998, A&A, 332, 77

Hanasz, M., & Lesch, H. 2000, ApJ, 543, 235

Horellou, C., Beck, R., Berkhuijsen, E. M., Krause, M., & Klein, U. 1992, A&A, 265, 417

Knapik, J., Soida, M., Dettmar, R.-J., Beck, R., & Urbanik, M. 2000, A&A, 362, 910

Krause, M. 1990, in IAU Symp. 140, Galactic and Intergalactic Magnetic Fields, ed. R. Beck, P. P. Kronberg, & R. Wielebinski, Kluwer, Dordrecht, 187

Krause, M. 1993, in IAU Symp. 157, The Cosmic Dynamo, ed. F. Krause et al., Kluwer, Dordrecht, 305

Krause, M., Beck, R., & Klein U., 1984, A&A, 138, 385

Krause, M., Hummel, E., & Beck, R. 1989a, A&A, 217,4

Krause, M., Beck, R., & Hummel, E. 1989b, A&A, 217, 17

Lesch, H., & Chiba, M. 1997, Fund. Cosmic Phys., 18, 273

Lou, Y. Q., & Fan, Z. 1998, ApJ, 493, 102

Moss, D. 1996, A&A, 308, 381

Moss, D. 1998, MNRAS, 297, 860

Moss, D., Brandenburg, A., Donner, K. J., & Thomasson, M. 1993, ApJ, 409, 179

Moss, D., Shukurov, A., & Sokoloff, D. 1999, A&A, 343, 120

Niklas, S. 1995, PhD thesis, University of Bonn

Pacholczyk, A. G. 1970, Radio Astrophysics, Freeman, San Francisco

Patsis, P. A., Grosbøl, P., & Hiotelis, N. 1997, A&A, 323, 762

Reuter, H.-P., Klein, U., Lesch, H., Wielebinski, R., & Kronberg P.P. 1994, A&A, 282, 724

Rohde, R., Beck, R., & Elstner, D. 1999, A&A, 350, 423

Ruzmaikin, A. A., Shukurov, A. M., & Sokoloff, D. D. 1988, Magnetic Fields of Galaxies, Kluwer, Dordrecht

Segalovitz, A., Shane, W.W., & de Bruyn, A. G. 1976, Nature, 264, 222

Shukurov, A. 1998, MNRAS, 299, L21

Soida, M., Urbanik, M., & Beck, R. 1996, A&A, 312, 409

Soida, M., Urbanik, M., Beck, R., Wielebinski, R, & Balkowski, C. 2001, A&A, 378, 40

Soida, M., Beck, R., Urbanik, M., & Braine, J. 2002, A&A, 394, 47

Sokoloff, D., Shukurov, A., & Krause, M. 1992, A&A, 264, 396

Sokoloff, D. D., Bykov, A. A., Shukurov, A., Berkhuijsen, E. M., Beck, R., & Poezd, A. D. 1998, MNRAS, 299, 189

Tüllmann, R., Dettmar, R.-J., Soida, M., Urbanik, M., & Rossa, J. 2000, A&A, 364, L36

Wielebinski, R., & Krause, F. 1993, A&AR, 4, 449