{'fraction_non_alphanumeric': 0.050235125741157224, 'fraction_numerical': 0.01200163565732979, 'mean_word_length': 3.8808502145494463, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 28, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Shift-Coupling of Random Rooted Graphs and Networks

In this paper, we present a result similar to the shift-coupling result of Thorisson (1996) in the context of random graphs and networks. The result is that a given random rooted network can be obtained by changing the root of another given one if and only if the distributions of the two agree on the invariant sigma-field. Several applications of the result are presented for the case of unimodular networks. In particular, it is shown that the distribution of a unimodular network is uniquely determined by its restriction to the invariant sigma-filed. Also, the theorem is applied to the existence of an invariant transport kernel that balances between two given (discrete) measures on the vertices. An application is the existence of a so called extra head scheme for the Bernoulli process on an infinite unimodular graph. Moreover, a construction is presented for balancing transport kernels that is a generalization of the Gale-Shapley stable matching algorithm in bipartite graphs. Another application is on a general method that covers the situations where some vertices and edges are added to a unimodular network and then, to make it unimodular, the probability measure is biased and then a new root is selected. It is proved that this method provides all possible unimodularizations in these situations. Finally, analogous existing results for stationary point processes and unimodular networks are discussed in detail.


Introduction
This paper deals with random rooted graphs, which are possibly infinite, but finite-degree connected graphs with a distinguished vertex called the root. Roughly speaking, each vertex and edge of a graph can be equipped with marks to form a network. Unimodular random rooted networks have been of great interest in the last two decades. They satisfy a formulation of the heuristic property that all vertices are equally likely to be the root, although there may be infinitely many vertices. The formulation, called the mass transport principle, will be recalled in Section 2. This concept is introduced in [4] and developed further in [1] to generalize some properties of Cayley graphs, which are highly homogeneous, to more general classes of graphs and random graphs. It also arises in the study of limits of sequences of finite graphs, which is the novel work of [2], and also in stationary point processes. Many concepts and results in stationary point processes have analogues in the context of unimodular networks. This analogy will be addressed many times in this paper.
To introduce the idea of this work, we get help from the following general construction method. Let   Note that the question is not limited to the setting of the above example. In general, no special relation is assumed between the two random rooted networks and they might be given only by two probability distributions. The answer to this question is not straightforward since the space of non-rooted networks is nonstandard. Several definitions of unrooted-equivalence are provided in Section 3 as answers to this question, where some of the definitions are shown to be equivalent. It will be shown that in the above example, [G ′ , o ′ ] and [G, o] are weakly unrootedequivalent, to be defined later. The strong sense in our definition is that (the distribution of) the second one can be obtained from the first by a root-change (note that there is a biasing in the above definition of [G ′ , o ′ ] before changing the root). Another definition is that the two random rooted networks agree on the invariant sigma-field ; i.e. any event that does not depend on the root occurs with equal probabilities. Some other definitions will also be given (Definition 7).
The main theorem (Theorem 1) in this work is that the last two definitions mentioned above are equivalent; namely, if two random rooted networks agree on the invariant sigma-field, then they can be obtained from each other by a root-change. This theorem, in its spirit, is similar to a well known result by Thorisson [19] that studies shift-coupling of random elements in a space equipped with a group action.
In Section 4, we discuss applications of the main theorem in the unimodular case. Theorem 3 says that the distribution of a unimodular network is uniquely determined by the distribution of its non-rooted network, or equivalently, by its restriction to the invariant sigma-field. Theorem 4 deals with invariant balancing transport kernels, which are transport kernels that transport a given measure to another given one. In the context of stationary random measures and point processes, this concept has been studied by many authors recently. In this context, under suitable assumptions, the existence of a (random) balancing transport kernel that is invariant under translations is implied by the result of [19] (proved in the general case in [14]). Based on this abstract result, several constructions have been provided, starting from [15] and [10], where the latter provides a transport kernel balancing between (a multiple of) the Lebesgue measure and the counting measure of the Poisson point process. Here, in the context of unimodular networks, we consider two discrete measures on the vertices of the random network. In Theorem 4, it will be proved that, roughly speaking, a balancing transport kernel between them exists if and only if the measures have equal sample intensities; i.e. have the same expectation conditioned on the invariant sigma-field. A construction of such transport kernels is discussed in Section 6 (Theorem 7) based on the construction of stable transports in [8], which is by itself based on [10]. It is a generalization of the Gale-Shapley stable matching algorithm in bipartite graphs [7].
In Section 5, we describe a general method for constructing unimodular networks. In some of the examples in the literature, such a network is constructed by the following steps: Adding some vertices and edges to another unimodular network (called a network extension here), then biasing the probability measure and finally applying a root-change. These examples are unified in the method presented in Theorem 5. It is also proved in Theorem 6 that this method gives all possible ways to unimodularize the extension (to be defined more precisely later).
Many of the definitions and results in this paper have analogues in the context of point processes and random measures, which are discussed in Section 8.
This paper is structured as follows. The definition and basic properties of unimodular random networks are given in Section 2. The definition of unrootedequivalence and the main shift-coupling theorem are presented in Section 3. The applications of the theorem to the unimodular case are studied in Section 4. Section 5 deals with extensions of unimodular networks. Section 6 presents a construction of balancing transport kernels using stable transports. The proofs of some results are moved to Section 7 to help to focus on the main thread of the paper. Finally, Section 8 reviews the analogous results in the context of point processes.

Random Rooted Graphs and Networks
In this section, we recall the concepts of random networks and unimodularity mainly from [1]. A network is a (multi-) graph G = (V, E) equipped with a complete separable metric space Ξ, called the mark space and with two maps from V and {(v, e) : v ∈ V, e ∈ E, v ∼ e} to Ξ, where the symbol ∼ is used for adjacency of vertices or edges. The image of v (resp. (v, e)) in Ξ is called its mark. The degree of a vertex v is denoted by d(v) and the graph-distance of vertices v and w is denoted by d(u, v). The symbol N r (v) is used for the closed ball centered at v with radius r; i.e. the set of vertices with distance at most r to v.
In this paper, all networks are assumed to be locally finite; that is, the degrees of every vertex is assumed to be finite. Moreover, a network is assumed to be connected except when explicitly mentioned. An isomorphism between two networks is a graph isomorphism that also preserves the marks. A rooted network is a pair (G, o) in which G is a network and o is a distinguished vertex of G called the root. An isomorphism of rooted networks is a network isomorphism that takes the root of one to that of the other. Let G denote the set of isomorphism classes of connected networks and G * the set of isomorphism classes of connected rooted networks. The set G * * is defined similarly for doubly-rooted networks; i.e. those with a pair of distinguished vertices. The isomorphism class of a network G (resp.
The sets G * and G * * can be equipped with natural metrics that make them a complete separable metric space and equip them with the corresponding Borel sigma-fields. The distance of two rooted networks is defined based on the similarity of finite neighborhoods of their roots. See [1] for the precise definition. There are two natural projections π 1 , π 2 : G * * → G * obtained by forgetting the second and the first root respectively. These projections are continuous and measurable. In contrast, there is no useful metric on G. However, as will be defined in Definition 4, the natural projection π : G * → G of forgetting the root induces a sigma-field on G. This sigma-field is extensively used in this paper although it does not make G a standard space. Definition 1. A random rooted network is a random element in G * and is represented in either of the following ways.
• A probability measure µ on G * .
• A measurable function from some probability space to G * that is denoted by bold symbols [G, o]. Here, G and o represent the network and the root respectively.
Note that the whole symbol [G, o] represents one random object, which is a random equivalence class of rooted networks. Therefore, any formula using G and o should be well defined for equivalence classes of rooted networks; i.e. should be invariant under rooted isomorphisms. Moreover, bold symbols are used only in the random case.
The relation between the two representations is expressed by the equation µ is the distribution of the random object. These representations are mostly treated equally in this paper. Therefore, all definitions and results expressed for random rooted networks [G, o] also make sense for probability measures on G * .
For a measurable function g : G * * → R ≥0 , a network G and u, v ∈ V (G), let where brackets [·] are used as a short form of ([·]). Also, for o ∈ V (G), let , where the expectations may be finite or infinite. The term unimodular network is used as an abbreviation for unimodular random rooted network. A probability measure on G * is called unimodular when, by considering it as a random rooted network, one gets a unimodular network.
Remark 1. For a function g as above, g G (·, ·) can be regarded as a function on V (G) × V (G) (or a transport kernel on V (G)) defined for all networks G. One can interpret g G (u, v) as the amount of mass that is transported from u to v. Using this intuition, g + G (o) (resp. g − G (o)) can be seen as the amount of mass that goes out of (resp. comes into) o and (2.1) expresses some conservation of mass in expectation. It is referred to as the mass transport principle in the literature. With this analogy, a measurable function g : G * * → R ≥0 is also called an invariant transport kernel in this paper.
The invariant sigma-field I on G * is the family of events in G * that are invariant under changing the root; i.e., events A ⊆ G * such that for every rooted network (G, o) and The following definition is borrowed from [3].
Definition 3. A covariant subset (of the vertices) is a function S which associates to each network G a set S G ⊆ V (G) such that [G, o] → 1 {o∈SG} is a well-defined and measurable function on G * . By an abuse of notation, we use the same symbols for the subnetwork induced by S G (i.e. the restriction of G to S G ) for all networks G. This is called a covariant subnetwork.
Note that in this definition, S should be covariant under network isomorphisms, that is, for all isomorphisms ρ : This easily implies that covariant subsets are in one-to-one correspondence with measurable subsets of G * .
The following lemma is straightforward and its proof is skipped. See [3] or [1].

Shift-Coupling of Random Rooted Networks
In this section, different formulations of unrooted-equivalence are defined and the main theorem of this paper is presented, which studies the implications between these formulations. The proofs of most of the results are moved to Section 7 to help to focus on the main thread. The reader can either see the proofs first or proceed to the next results with no problem. Proposition 1. The measurable space (G, J) is not a standard Borel space. More precisely, there is no metric on G that makes it a Polish space whose Borel sigma-field is J.
Due to non-standardness, several classical tools of probability theory may fail for random non-rooted networks; e.g. conditional expectation. However, it poses no problem for the arguments in this paper; e.g. equality of distributions, pull-back and push-forward of distributions, etc.
Note also that the map π −1 corresponds J bijectively to the invariant sigmafield I on G * . Therefore, probability measures on (G, J) are in one-to-one correspondence with probability measures on (G * , I).
Definition 5. Let µ be a probability measure on G * and w : G * → R ≥0 be a measurable function. Assume 0 < G * wdµ < ∞. By biasing µ by w we mean the following measure on G * .
The choice of the denominator ensures that the result is a probability measure. It is the unique probability measure on G * whose Radon-Nikodym derivative w.r.t. µ is proportional to w. Biasing a probability measure on G is defined similarly.
It can be seen that biasing µ by w is equal to µ if and only if w is essentially constant (w.r.t. µ); i.e. for some constant c one has w = c, µ-a.s. Note that This lemma is straightforward and we skip its proof.
Any random rooted network with this distribution is called the root-change of We are now ready to present the main definition. As mentioned in the introduction, the definition with Condition (B) is used heuristically in some examples in the literature, some of which will be mentioned in Section 5.

Main Theorems.
Here, we study the implications between the conditions in Definition 7. At first sight, Condition (F) may seem weaker than the other ones, because the other conditions assume the existence of a third object. But this is not the case as shown below.  It should be noted that Condition (B) does not imply the other conditions (see Remark 2 below). Theorem 2 allows us to define the following. Remark 2. According to Condition (F), when two random rooted networks are weakly unrooted-equivalent, the distributions of the corresponding non-rooted networks may be different (but are always mutually absolutely continuous by Lemma 2). This difference can be seen clearly in Example 6.    The condition of being infinite is necessary in this proposition as explained in Remark 3. See also [5] for the precise definition of adding i.i.d. marks to the vertices. The name extra head scheme is borrowed from an analogous definition in [12] as will be explained in Section 8.
This equation for all A ∈ I implies that E [m(o) |I ] = p a.s. So P [m(o) = 1 |I ] = p a.s. and the claim is proved.
The following lemma is used in the proof of Proposition 3 and is interesting in its own. It is similar to the ergodicity of the Bernoulli point process on Z d or the Poisson point process in R d (see Section 8).    (3.2). Also, the same property holds in any root-change of the network, contradicting the claim of Proposition 3.
3.4. Notes. The name shift-coupling for Theorem 1 is borrowed from the analogous result of [19]. This result studies when two random elements in a space equipped with some group action have a coupling such that the second one is obtained from the first by a shift corresponding to a random element of the group, called a shift-coupling in the literature. Here, instead of a group action, we have root-changes as in Condition (C) of Definition 7, which don't form a group. In Section 7, a proof of Theorem 1 is presented by mimicking that of [19]. A second proof is also presented using the result of [19]. With this proof, one can generalize Theorem 1 to the context of Borel equivalence relations as follows.
The following definitions are borrowed from [6]. An equivalence relation R on a Polish space X is a countable Borel equivalence relation if when considered as a subset of X × X, it is a Borel subset and each equivalence class is countable. The R-invariant sigma-field on X consists of Borel subsets of X which are formed by unions of R-equivalence classes. In the following result, a Borel automorphism Theorem 1'. Let R be a countable Borel equivalence relation on X and Y 1 and Y 2 be random elements in X. Then there exists a random R-stabilizing Borel automorphism F such that F (Y 1 ) has the same distribution as Y 2 if and only if the distributions of Y 1 and Y 2 agree on the R-invariant sigma-field.
In fact, in the converse, F can be chosen to be supported on countably many automorphisms. As mentioned above, the proof of this theorem is similar to one of the proofs given for Theorem 1 and is skipped here.
A Borel equivalence relation R is smooth if the quotient space X/R with the induced Borel structure is a standard Borel space. Therefore, Proposition 1 just claims that the equivalence relation on G * induced by π (see the proof of Theorem 1) is not smooth, which is implied by Corollary 1.3 of [9]. A direct proof is also presented in Section 7.

The Unimodular Case and Balancing Transport Kernels
In this section, some applications of Theorem 1 are presented for the case of unimodular networks. The main results are theorems 3 and 4 whose proofs are postponed to the end of the section after presenting some minor results.
Theorem 3 (Uniqueness). The distribution of a unimodular network [G, o] is uniquely determined by its restriction to the invariant sigma-field (or equivalently, by the distribution of the non-rooted network [G]). In other words, if two unimodular networks are strongly unrooted-equivalent, then they are identically distributed.
Theorem 3 is a precise formulation of a comment in [1] saying that 'intuitively, the distribution of the root is forced given the distribution of the unrooted network'. Note also that if we replace 'strongly' with 'weakly' in this theorem, the claim no longer holds. This case will be considered in Lemma 7 and Proposition 4 below.
Theorem 4 (Balancing Transport Kernel). Let [G, o] be a unimodular network and w i : G * → R ≥0 be measurable functions for i = 1, 2. Assume E [w 1 |I ] < ∞ a.s. Then, the following are equivalent.
(i) There is an invariant transport kernel that almost surely balances between the functions w 1 [G, ·] and w 2 [G, ·] on the vertices; i.e. a measurable function T : Theorem 4 is analogous to similar results for stationary point processes and random measures ( [12] and [14]). This analogy will be explained in Section 8.
However, the existence of a balancing transport kernel as in Theorem 4 is only proved for the unimodular case.
Before proving the above theorems, we present some other minor results in the unimodular case.

Proof. (i). Given an event
(ii). By part (i) and Definition 8, [G 2 , o 2 ] is obtained by biasing [G 1 , o 1 ] by a composition of two biasings, say by functions w 1 and w 2 . It is easy to show that the result is just biasing by w 1 w 2 and the claim is proved.
On the other hand, for all v ∈ V (G). So, the claim is proved.
be random rooted networks which are weakly unrooted-equivalent. If at least one of them is an extremal unimodular network, then they are also strongly unrooted-equivalent.
We are now ready to prove the main theorems of this section.
By the assumption, one gets that almost surely, g + . By considering this for all A ∈ I, one obtains (4.1). ( is used (which holds by (4.1)) to cancel out the denominators. Define an invariant transport kernel T by So the theorem is proved.

Network Extension and Unimodularization
In this section, the method of network extension is introduced and the shiftcoupling theorem is applied to it. This method unifies some of the examples in the literature to construct unimodular networks. First, in Subsection 5.1 we study unimodularizations of a random non-rooted network in general. Then, network extension is studied in Subsection 5.2.

Unimodularizations of a Non-Rooted Network.
Definition 9. Let µ 0 be a probability measure on (G, J) (or similarly, on (G * , I)). We say that a random rooted network and µ 0 are mutually absolutely continuous. If in addition [G ′ , o ′ ] is unimodular, we say it is a (weak or strong) unimodularization of µ 0 and µ 0 can be unimodularized.
Heuristically, unimodularization means to choose a random root for a given random non-rooted network to obtain a unimodular network.
To see why the weak sense is ever defined here, it will turn out that some  This lemma is straightforward and we skip its proof.
Proposition 5. Under the assumptions of Definition 9, if µ 0 can be unimodularized (either weakly or strongly), then there is a unique strong unimodularization of µ 0 .
is a strong unimodularization of µ 0 . Now, Theorem 3 implies that this is the unique strong unimodularization of µ 0 .
Note that some probability measures on (G, J) (i.e. some random non-rooted networks) cannot be unimodularized; e.g. a deterministic semi-infinite path.
Example 1 (Planar Dual I). Let [G, o] be a unimodular plane graph (see Example 9.6 of [1] for how to regard a plane graph as a network and define its dual). With no need to select a vertex of the dual graph as a root, [G * ] makes sense as a random non-rooted network. In [1], a unimodular network is constructed based on the dual graph, which in our language, is a weak unimodularization of [G * ]. This construction will be discussed in Example 8.
Example 2 (Subnetwork). Let [G, o] be a unimodular network and S be a covariant subnetwork (Definition 3). Assume S G is nonempty and connected a.s. Therefore, [S G ] is a random non-rooted network; i.e. a random element in (G, J) (note that S G doesn't need to contain o and no root is chosen for S G ).
Considering P ′ as a random rooted network, we claim that it is a weak unimodularization of (the distribution of) [S G ]. Let µ := π * P ′ be the distribution of the non-rooted network under P ′ . By taking conditional expectation w.r.t. I, one obtains for any measurable function In other words, µ is just biasing the distribution of [ where the latter is considered as a function on (G, J). Similar to Lemma 1, one can deduce from S G = ∅ a.s. that P [o ∈ S G |I ] > 0 a.s., thus, µ and the distribution of [S G ] are mutually absolutely continuous. On the other hand, it is easy to use (2.1) directly to see that P ′ is unimodular. Thus, P ′ is a weak unimodularization of (the distribution of) [S G ].
To The method presented here needs that the original network can be reconstructed from the extension, as explained in the following definition. In applications, to ensure the reconstruction is possible, one may add extra marks to the newly added vertices and edges (e.g. see Example 5). Nevertheless, after a new unimodular network is successfully constructed using the method, one may forget the extra marks and unimodularity will be preserved.  We are now ready to state the results of this section. All proofs are postponed to the end of the subsection. Theorem 5 provides a general method to construct unimodularizations of a given proper extension. Moreover, part (i) of the theorem gives a criteria for verifying existence or non-existence of a unimodularization.
s., then the following probability measure gives the unique strong unimodularization of [G].  In Theorem 5, the function T is assumed to be given. In the following theorem, the existence of T is studied using Theorem 1. Remark 6 (Comparison of P T vs P ′ T ). The unimodularization P T in Theorem 5 has some advantages comparing to P ′ T and the other unimodularizations. One advantage is that it is easier to use since there is no division in the term under expectation and no conditional expectation w.r.t. I. Another is that the numerator in the definition of P T [·] (which is E [M ] × P T [·]) is a linear function of the distribution of [G, o]. Another one is shown in the following proposition. In contrast, an advantage of P ′ T is that it is the strong unimodularization and thus, it doesn't change the distribution of the underlying non-rooted network (see Condition (F) in Definition 7 and Example 6). Moreover, in some cases P ′ T is defined but P T is not, as shown in Example 6.  [G] has at least two different unimodularizations, then by taking convex combinations of the probability measures one finds infinitely many unimodularizations. So, Corollary 2 implies that there are unimodularizations which cannot be obtained by parts (ii) and (iii) of Theorem 5 (note that a further biasing is enough as described in part (ii) of Theorem 6).
Remark 8. There is a special case of the construction in Theorem 5 which is sometimes easier to imagine and use, if possible. In the theorem, assume that for all vertices v, the function T G (v, ·) is concentrated on a single vertex, namely τ G (v). Such a mapping τ can be called an allocation (or a vertex-shift in [3]). Then, the assumptions for T , apart from measurability, are reduced to τ G (·) ∈ S G a.s. Also, M is equal to #τ −1 G (o). However, In the setting of Theorem 6, existence of such an allocation is not guaranteed in general.
The following are some basic examples for applications of the definitions and results, although they are not new.  With similar arguments, one can append a rooted network to each vertex of G 0 and use the method of Theorem 5 to obtain another unimodular network.
By passing to G * 0 as a subnetwork of G as in Example 2, one can obtain a weak unimodularization of the dual random non-rooted graph [G * 0 ]. This is obtained by replacing M by M − 1 in the above formula and deleting the term 1 A [G, o]. This is identical to the one constructed in Example 9.6 of [1]. Similarly, the following is the strong unimodularization of [G * 0 ].
Similar to this example, one can add a new vertex for each edge-crossing of G 0 with its dual. With similar arguments, the method of Theorem 5 gives the unimodularization of this new network given in Example 9.6 of [1]. Now, the proofs of the results of this section are presented. First, we start with the following lemma. Proof of Theorem 5. We prove the parts of the theorem in a different order. (iii) The assumptions imply that almost surely, for some vertex v ∈ S G , T − G (v) > 0. By (5.1) and an argument similar to Lemma 1, one can obtain that > 0 a.s. Therefore, P ′ T is well-defined. It can be seen that P ′ T is a probability measure. Now, let [ G, o] be a random rooted network with distribution P ′ T . Let g : G * * → R ≥0 be a measurable function. By the definition of P ′ T and conditioning on I, one gets v, u] and in the second equality, the equation z∈SG T G (u, z) = 1 a.s. is used, which holds by the assumptions. It can be seen thatĝ is well-defined and measurable. One obtains a similar equation by swapping the two roots in all instances of g andĝ. To summarize, Let A ∈ I be an invariant event. By (5.1), one gets Since this holds for all A ∈ I, it follows that the right hand sides of (5. Therefore The latter is shown above to be finite a.s. This implies that E [M |I ] < ∞ a.s. Proof of Corollary 1. By the strong sense in part (iii) of Theorem 5, one obtains that P ′ T also satisfies the assumption on [G, o], which implies that P ′ T is extremal. Therefore, Proposition 4 implies that any weak unimodularization of [G] is also strongly unrooted-equivalent to P ′ T . Now, Theorem 3 implies that P ′ T is the unique weak unimodularization of [G].
Proof of Theorem 6. (i) Let [G ′ , o ′ ] be a strong unimodularization of the extension. Define w : Since S G = ∅ a.s. and this property doesn't depend on the root, the same holds for G ′ . Similar to Lemma 1 one can deduce that the above denominator is nonzero a.s. and w is well-defined up to an event of measure zero. One has E w[G ′ , o ′ ] |I = 1 a.s. Therefore, Theorem 4 implies that there is a measurable function T : where in the third equality (5.1) is used. Therefore, Proof of Corollary 2. Lemma 9 and Proposition 6 imply the claim.

A Construction Using Stable Transports
In some results in this paper, the existence of specific objects are proved based on Theorem 1, including propositions 2 and 3 and theorems 4 and 6. However, Theorem 1 does not help to construct such root-changes by looking only at a realization of the given networks. In this section, we present an algorithm to construct a balancing transport kernel as described in Theorem 4. Special cases of this algorithms will provide the desired constructions in the other results mentioned above.
The algorithm is based on the one in [8], which is by itself based on [10]. It is a generalization of the Gale-Shapley stable matching algorithm for bipartite graphs [7]. In fact, it is similar to the many-to-many stable matching algorithm. We should note that by the terms construction and algorithm we do not mean a computational algorithm, but an explicit definition using formulas that might be defined iteratively.
Fix a rooted network (G, o) and measurable functions w i : G * → R ≥0 for i = 1, 2. We will use two names sites and centers for the vertices and use Roman letters for centers for better readability. Given a measurable function T : G * * → R ≥0 , we say a site x ∈ V (G) sends mass T G (x, ξ) to the center ξ ∈ V (G). Here is an overview of Algorithm 1. It will finally produce a measurable function T : (the goal is equality which will hold under some conditions). T G (x, ξ) will be defined as the mass x applies to ξ minus the mass ξ rejects from x. The algorithm consists of infinitely many stages and each stage has two steps. At stage n, each site x 0 applies to the closest possible centers with weight A n (x 0 , ·). A constraint is chosen for the applications, which is 0 ≤ A n (x 0 , ·) ≤ w 2 [G, ·]. Then, each center ξ 0 rejects some of the weights applied to ξ 0 if the sum of the incoming applications exceeds w 2 [G, ξ 0 ]. The amount of rejection is denoted by R n (·, ξ 0 ). The functions A n and R n at stage n are chosen such that each site prefers to apply to the closest possible centers and each center prefers to reject (if necessary) the applications of the farthest possible sites.
Algorithm 1 (Stable Transport). Let (G, o) be a given deterministic rooted network and w 1 , w 2 : G * → R ≥0 be measurable. Let R 0 (x, ξ) = 0 for all x, ξ ∈ V (G). For each n ≥ 1, stage n consists of the following two steps.
(i) For each site x 0 , define its application radius at stage n by a n (x 0 ) := min{a ≥ 0 : Define the n-th application function by where in the case a n (x 0 ) < ∞, c = c n (x 0 ) is chosen in [0, 1] such that (ii) For each center ξ 0 , define its rejection radius at stage n by r n (ξ 0 ) := min{r ≥ 0 : Define the n-the rejection function by where in the case r n (ξ 0 ) < ∞, c ′ = c ′ n (ξ 0 ) is chosen in [0, 1] such that Here are some basic facts about this algorithm. The proofs are similar to [8] and are skipped here for brevity. The sequences of functions A n , R n and a n are non-decreasing w.r.t n and r n is non-increasing. So, the limit function T is well defined. Moreover, It is shown below that T is stable in a sense similar to [8] (and many-to-many stable matchings) defined as follows: There is no site x 0 and center ξ 0 such that both desire each other, where site x 0 desires center ξ 0 if T G (x 0 , ξ 0 ) < w 2 [G, ξ 0 ] and either x 0 is unexhausted or T G (x 0 , ξ 1 ) > 0 for some farther center ξ 1 . Similarly, center ξ 0 desires site x 0 if T G (x 0 , ξ 0 ) < w 2 [G, ξ 0 ] and either ξ 0 is unsated or T G (x 1 , ξ 0 ) > 0 for some farther site x 1 . Stronger than stability, the following holds.
Lemma 11. In Algorithm 1, if a site x 0 desires a center ξ 0 (defined above), then ξ 0 is sated and doesn't desire x 0 . Therefore, T is stable.
Proof. By definition, either x 0 is unexhausted or T G (x 0 , ξ 1 ) > 0 for some farther center ξ 1 . In both cases, x 0 has applied to some center farther than ξ 1 at some stage. The definition of A n implies that A n (x 0 , ξ 0 ) = w 2 [G, ξ 0 ] for large enough n. Therefore, by T G (x 0 , ξ 0 ) < w 2 [G, ξ 0 ], ξ 0 has rejected a positive fraction of the application of x 0 at some stage. By the definition of the rejection function, ξ 0 is sated from that stage on. Moreover, ξ 0 has fully rejected the applications of the sites farther than x 0 . So, ξ 0 doesn't desire x 0 and the claim is proved. Proof. First, it is easy to see that T defines a measurable function on G * * . We should prove there is no unexhausted site and no unsated center a.s. Let A be the event that there is an unexhausted site. If P [A] > 0, then by conditioning on A, one may assume P [A] = 1 (notice that A ∈ I and thus the assumptions are not changed after conditioning on A). Therefore, by Lemma 12, there is no unsated centers a.s.
This contradicts (2.1). Therefore, all sites are exhausted a.s. One can prove similarly that all centers are sated a.s. So, the proof is complete.
The following is an application of Theorem 7 to Proposition 2 (see also Remark 9 below). Unimodularity is a crucial assumption to ensure that Algorithm 1 works here. The author is not aware of any general construction for the non-unimodular case of Proposition 2.
. By Theorem 7, T G ′ (·, ·) balances between w 1 [G ′ , ·] and w 2 [G ′ , ·] a.s. as defined in Theorem 4. Now, the proof of Theorem 6 shows that T satisfies the assumptions of Theorem 5 and P ′ T is defined. Remark 9. One may ask how to construct λ G in the above corollary by looking only at a realization of [G, o].
, then λ is the sample intensity of S in G ′ defined in Example 2. One may also ask the same question in Corollary 3 on how to construct P [o ∈ S G ]. Note that averaging on a large ball like #(S G ∩N r (o))/#N r (o) and taking limit does not work in general. In fact, it works only for the so called amenable unimodular networks [1]. For general unimodular networks, one construction for the sample intensity can be done by frequency of visits to S G of the delayed simple random walk in [G] (see [16] and [1] for the details). Another construction is the following.
In Corollary 5, replace λ G by an arbitrary constant λ > 0. Then, it can be seen that given any (G, v), the value T + G (v) is non-increasing in terms of λ (see [13] and also [8] and [10]). Then, one can let λ G be the supremum value of λ such that T + G (v) = 1 for all v ∈ V (G). It can be proved that this construction works in Corollary 5. The proof is similar to the arguments in [8] and [10] and is skipped for brevity.

Proofs
This sections is devoted to the proofs of some of the results of Section 3.
Definition 11. Let µ be a measure (not necessarily a probability measure) on G * and T : G * * → R ≥0 be a measurable function. Define the measures T ↑ µ and T → µ on G * * and G * respectively by for measurable subsets A ⊆ G * * and B ⊆ G * . It can be seen that , then π 1 * T ↑ µ = µ. If in addition, µ is a probability measure, then T → µ is just the root-change of µ by kernel T as in Definition 6. It is also worthy to mention that when T + (·) is always 1, there is a Markov kernel on G * that transports µ to T → µ, which is defined by Proof of Proposition 1. Assume (G, J) is a standard Borel space. Let µ be an arbitrary extremal unimodular probability measure on G * and let ν := π * µ. Since µ is extremal, one gets ν(A) ∈ {0, 1} for any event A ∈ J. The assumption of standardness of (G, J) implies that ν is concentrated on one atom. Therefore, there should be a network G such that µ is concentrated on {[G, v] : v ∈ V (G)}. But this is clearly false for general µ (see for instance the example in Lemma 4).
Proof of Lemma 2. Denote by [G ′ , o ′ ] the random rooted network obtained by biasing the probability measure by w. Let B ∈ J be an event in G and A := π −1 (B). One has (C)⇒ (R). Let µ be such a probability measure on G * × G * as assumed. Fix a rooted network (G 1 , o 1 ) and let µ (G1,o1) be the conditional distribution of the second rooted network given that the first rooted network is [G 1 , o 1 ]. Note that µ (G1,o1) is defined and is supported on In the (zero-probability) cases where this doesn't hold, let µ (G1,o1) be concentrated on . This set is a finite subset of V (G 1 ). Finally, from the measure µ (G1,o1) on A, one can construct a measure T G1 (o 1 , ·) on V (G 1 ) defined by for v ∈ V (G 1 ). It is easy to see that T is an invariant transport kernel and T + G1 (o 1 ) = 1. Moreover, by choosing a new root in V (G 1 ) with distribution T G1 (o 1 , ·), the resulting network has distribution µ (G1,o1) . By the definition of µ (G1,o1) and choosing (G 1 , o 1 ) randomly with distribution P 1 , one gets that T → P 1 = P 2 . So, T gives the desired root-change. (⇐, First Proof ). The proof mimics that of [19]. Here is a summary of the proof. The idea is to find two root-changes for [G 1 , o 1 ] and [G 2 , o 2 ] such that the resulting random rooted networks have the same distribution. Then, one can combine them to find the desired root-change. We start with an arbitrary rootchange such that every vertex has positive probability to be chosen. Then, update it step by step as will be described. However, in the next steps probability measures will be replaced by finite measures.
Starting from P 1 and P ′ 1 , construct the sequences of finite measures Q n , Q ′ n , P n , P ′ n and λ n for n ≥ 1 as follows. The first two are one G * * and the other three on G * . Here, the symbol ∧ is used for the minimum of measures.
• λ n := (S → P n ) ∧ (S → P ′ n ). • Q n is the probability measure constructed in Lemma 14 for λ n , S ↑ P n and i = 2. Q ′ n is defined similarly by Lemma 14 for λ n , S ↑ P ′ n and i = 2. • P n+1 := P n − π 1 * Q n and P ′ n+1 := P ′ n − π 1 * Q ′ n . By the definition of Q n and Q ′ n and Lemma 14, one has Q n ≤ S ↑ P n , π 2 * Q n = λ n , Q ′ n ≤ S ↑ P ′ n , π 2 * Q ′ n = λ n .

(7.2)
Since π 1 * S ↑ P n = P n and π 1 * S ↑ P ′ n = P ′ n , this implies inductively that all above measures are non-negative (and justifies validity of using Lemma 14 inductively). Define The limits are well defined since P n and P ′ n are decreasing sequences and the sums of Q n and Q ′ n over n are convergent, where the symbol · is used for the total mass of a measure (note that Q n = P n − P n+1 ). This also shows that Q is a finite measure. Now, one has π 1 * Q = n (P n − P n+1 ) = P 1 − P ∞ , π 1 * Q ′ = n (P ′ n − P ′ n+1 ) = P ′ 1 − P ′ ∞ (7.3) and (7.4) π 2 * Q = π 2 * Q ′ .
As a result, Q and Q ′ are probability measures. By part (D)⇒(R) of Theorem 2 (proved in Lemma 13 above), one finds a root-change, say by kernel T , that transports P 1 to α := π 2 * Q = π 2 * Q ′ . Similarly, by the same argument and Lemma 3, one finds a root-change, say by kernel T ′ , that transports α to P 2 . Now, let t be the composition of T and T ′ defined by . It can be seen that t gives a root-change of P 1 (as in Definition 6) and t → P 1 = P ′ 1 . Therefore, by Definition  ]. This provides a coupling of P and P ′ that satisfied Condition (C) of Definition 7. Therefore, by part (C)⇒(R) of Theorem 2 (proved in Lemma 13 above), [G 2 , o 2 ] can be obtained from [G 1 , o 1 ] by a root-change and the claim is proved.
The following lemma is used in the proof of Theorem 1 above. Note that all measures are assumed to be non-signed in this paper.
Lemma 14. Let P and Q be finite measures on G * and G * * respectively and i ∈ {1, 2}. If π i * Q ≥ P , then there is a measure Q ′ ≤ Q such that π i * Q ′ = P .
Proof. The claim is a direct consequence of Lemma 1 in [19].
Proof of Theorem 2. According to Lemma 13 and Theorem 1 proved above, the only remaining part is (R)⇒ (B), which is trivial. For any measurable function g :  In other words, f does not depend on the root a.s. Consider the root-change of changing the root to a uniformly at random neighbor of the root and compose it with its dual given by Lemma 3. This can be explicitly written by It is straightforward that when G is not a single vertex, for all vertices v ∈ V (G), one has T + G (v) = T − G (v) = 1. Moreover, if u, v have a common neighbor, then T G (u, v) > 0. Let k ∈ N and t be the k-fold composition of T with itself. One can see T as the law of (the first step of) a random walk on the vertices that preserves the distribution of [G, o] and t as the law of the k'th step of the random walk. By infiniteness of G, it can be seen that almost surely, when k → ∞, t G (·, ·) → 0 point-wise. We also have t + G (·) = t − G (·) = 1 a.s. For an arbitrary ǫ > 0, there exist n ∈ N and an event A n that depends only on the ball with radius n centered at the root such that P [G ′ , o] ∈ A∆A n < ǫ.
Therefore, by the above inequalities and the mentioned independence, one gets by conditioning on [G, o] that Using this and unimodularity two times, the above inequality implies where in the last equation, (7.7) is used. Since 0 ≤ f ≤ 1 and ǫ is arbitrary, this implies that f [G, o] ∈ {0, 1} a.s. So, (3.2) is proved and the proof is complete.

Bibliography of Analogous Results for Point Processes
In this section, we discuss a similarity between unimodular networks and stationary point processes (and random measures). Then, some of the concepts and results for random networks in this paper will be related to existing ones for point processes in the literature.
8.1. General Analogies. Let us recall Palm distributions and the mass transport principle for stationary point processes briefly. A stationary point processes is, roughly speaking, a random configuration Φ of points in R d such that its distribution is invariant under the translations of R d . The Palm distribution P Φ of Φ is defined by , where B is an arbitrary measurable set and θ x (Φ) is just Φ translated by the vector −x. In words, to obtain the Palm distribution, one should bias the probability measure by #Φ ∩ B and then move the origin to a uniformly at random point in Φ ∩ B. Notice the similarity of this sentence with the examples in the introduction and Subsection 5.2. Another equivalent definition of the Palm distribution can obtained by clarifying the idea of conditioning Φ to have a point at the origin. The mass transport principle for stationary point processes is for any (measurable) function g that is translation-invariant (see [11] or [10]). A result of Mecke [17] gives an extension of this property for stationary random measures (see [14]). Notice the similarity of the above mass transport principle with the one in Definition 2. This implies that, roughly speaking, any graph that is constructed from Φ in a translation-invariant manner is unimodular [1]. Mecke's formula [17] may also look related to (2.1), but all points of the space are taken into account: for all measurable functions h(x, y) = h(Φ, x, y) that are invariant under the translations. Here, λ is the intensity of Φ.
A difference of the two concepts is that in point processes, there is a group action (that of translations) for moving the origin to another point, but for rooted networks, there is no natural group for changing the root. However, like the above similarities, one can transfer some concepts and results for point processes to analogous ones for random networks. We will discuss in the next subsection that some of the results in sections 3, 4 and 6 have analogous results for point processes in the literature. See also [3] for other results and examples of this analogy including Mecke's point-stationarity theorem and Neveu's exchange formula.
Finally, as mentioned in [1], the invariant sigma-field I is analogous to the sigma-field of invariant events under translations and the notion of extremal unimodular networks is analogous to ergodic point processes.

Analogies
Regarding the Present Paper. Let [G, o] be a unimodular network. A covariant subset S (Definition 3) can be considered analogous to a subprocess of (or thinning) a stationary point process. Then, conditioning the probability measure on o ∈ S G in Example 2 is analogous to the Palm distribution of a subprocess (similarly, biasing by 1 {o∈SG} /P [o ∈ S G |I ] in Example 2 is analogous to the modified Palm distribution [14] of a stationary point process). Even fancier, one can think of [G, o] and S G as discrete objects analogous to the space and a point process respectively. With this analogy, Proposition 2 is analogous to a result of [19] which states that the Palm distribution of a stationary point process Φ can be obtained from Φ by moving the origin to a random point of Φ if and only if the sample intensity of Φ, defined by E [#Φ ∩ B |I ] for an arbitrary set B with unit volume, is essentially constant (here, I is used for the sigma-field of invariant events under translations). This notion of sample intensity is also analogous to that of Proposition 2 and Example 2 which is equal to E [#S G ∩ {o} |I ].
The special case of the result of [19] (mentioned above) for a Poisson point process Φ has been of special interest. The result implies that one can move the origin to a random point of Φ such that (the distribution of) the resulting point process is the same as Φ except that a point is added at the origin (see Slivnyak's theorem in [18]). Such a change of origin is introduced by Thorisson [19] and is called an extra head scheme in [12]. The same holds for the Bernoulli point process in Z d and is analogous to Proposition 3.
More general to a stationary point process and its Palm version, [19] also studies when two (not necessarily stationary) point processes Φ and Ψ can be obtained from each other by changing the origin (and covers even more general cases). This gives a coupling of Φ and Ψ that is called a shift-coupling in the literature. It is proved in [19] that a shift-coupling exists if and only if the distributions of Φ and Ψ agree on the invariant sigma-field. Theorem 1 in the present paper is its analogous result in the context of random networks.
To obtain a shift-coupling of a stationary point process Φ and its Palm version, one can use a translation-invariant balancing transport kernel between (a multiple of) the Lebesgue measure and the counting measure on Φ (see [12] and [14]). A transport kernel is, roughly speaking, a function T (x, y) depending on Φ that shows how much of the mass at each point x of the space goes to each point y in Φ. It is balancing when the sum of the outgoing mass is 1 and the integral of the incoming mass is constant for all points. The existence of such a transport kernel is proved in [12] and [14] using the result of [19] and also by an explicit construction. Analogously, Theorem 4 proves the existence of balancing transport kernels in the context of unimodular networks with similar conditions. Invariant transport kernels are analogous to measurable functions on G * * as mentioned in Remark 1. See also [14] for similar results for stationary random measures.
Assume ([G, o], S) is a proper extension of a unimodular network as in Section 5. According to the analogy of subnetworks and Palm distributions mentioned earlier, [G, o] is analogous to a Palm distribution. In fact, (5.1) is analogous to the mass transport principle for point-stationary point processes (see [14]); which are more general than Palm distributions (when dealing with probability measures, as assumed here). Unimodularization of [G, o] is analogous to reconstructing the stationary version of the point process from the Palm version [17]. The unimodularization P T in Theorem 5 is analogous to the inversion formula of [17] for the reconstruction. If the sample intensity of a point process is essentially constant, one can do the reconstruction by a shift-coupling as mentioned above. This is analogous to Theorem 6.
The existence results of [14] and [19] are abstract results and cannot be used to construct a balancing transport kernel given realizations of the two point processes. However, several constructions are provided in the literature motivated mainly by [10] for point processes, which is motivated by the construction in [15] and the stable marriage algorithm. This work is generalized in [8] to cover the general case of stationary random measures. Analogously, Theorem 4 doesn't provide a construction of the balancing transport kernel in the context of unimodular networks. Theorem 7 is a construction which is analogous to the one in [8].