Efficient-robust routing for single commodity network flows
Yongxin Chen Tryphon T. Georgiou Michele Pavon Allen Tannenbaum













Efficient-robust routing for single commodity network flowsThis project was supported by AFOSR grants (FA9550-15-1-0045 and FA9550-17-1-0435), grants from the National Center for Research Resources (P41-RR-013218) and the National Institute of Biomedical Imaging and Bioengineering (P41-EB-015902), National Science Foundation (ECCS-1509387), by the University of Padova Research Project CPDA 140897 and a postdoctoral fellowship through Memorial Sloan Kettering Cancer Center.

    Yongxin Chen, Tryphon T. Georgiou, Fellow IEEE, Michele Pavon, and Allen Tannenbaum, Fellow IEEE
Y. Chen is with the Department of Medical Physics, Memorial Sloan Kettering Cancer Center, NY; email: chen2468@umn.edu
T. T. Georgiou is with the Department of Mechanical and Aerospace Engineering, University of California, Irvine, CA; email: tryphon@uci.edu
M. Pavon is with the Dipartimento di Matematica “Tullio Levi Civita",
Università di Padova, 35121 Padova, Italy; email: pavon@math.unipd.it
A. Tannenbaum is with the Departments of Computer Science and Applied Mathematics & Statistics, Stony Brook University, NY; email: allen.tannenbaum@stonybrook.edu
    
======================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================



1

 We study single commodity network flows with suitable robustness and efficiency specs. An original use of a maximum entropy problem for distributions on the paths of the graph turns this problem into a steering problem for Markov chains with prescribed initial and final marginals. 

From a computational standpoint, viewing scheduling this way
is especially attractive in light of  the existence of an iterative algorithm to compute the solution. 

The present paper builds on <cit.> by introducing an  index of efficiency of a transportation plan and points, accordingly, to efficient-robust transport policies. In developing the theory, we establish two  new invariance properties of the solution (called bridge) 

– an iterated bridge invariance property and the invariance of the most probable paths. These properties, which were tangentially mentioned in our previous work, 

are fully developed here. We also show that the distribution on paths of the optimal transport policy, which depends on a “temperature” parameter, 

tends to the solution of the “most economical” but possibly less robust optimal mass transport problem as the temperature goes to zero.  The relevance of all of these properties for transport over networks is illustrated in an example.


.9
Index Terms— Transport over networks, maximum entropy problem, most probable path, temperature parameter
 
.97


§ INTRODUCTION

Consider a company owning a factory F and a warehouse W. The company wants to ship a certain quantity of goods from F so that they reach W in at most N time units. The flow must occur on the available road network connecting the two facilities. On the one hand, it is desirable that the transport plan utilizes as many different routes as possible so that most of the goods arrive within the prescribed time horizon even in the presence of road congestion, roadwork, etc. On the other hand, it is also important that shorter paths are used to keep the vehicles fuel consumption within a budgetary constraint. 

In this paper, continuing the research initiated in <cit.>, we provide a precise mathematical formulation of the above single commodity network flow problem. Normalizing the mass of goods to one, we formulate a maximum entropy problem for Markovian distributions on the paths of the network.  The optimal feedback control suitably modifies a prior transition mechanism thereby achieving robustness while limiting the cost. This is accomplished through an appropriate choice of the prior transition involving the adjacency matrix of the graph. The optimal scheduling, while spreading the mass over all feasible paths, assigns maximum probability to all minimum cost paths. 

Differently from the standard literature on controlled Markov chains, the optimal policy (Schrödinger bridge) is not computed through dynamic programming. The constraint on the final marginal (all the goods should be in the warehouse by day N) dictates a different approach. The solution is computed by solving iteratively a Schrödinger-Bernstein linear system with nonlinear coupling at the initial and final times. This algorithm, whose convergence was established in <cit.>, is related to recent work  in entropy regularization <cit.> and equilibrium assignement in economics <cit.> as well as to classical work in statistics <cit.>.

Our straightforward  approach also avoids altogether modelling cascading failures which is a complex and controversial task <cit.>. It is also worthwhile remarking that maximum entropy problems <cit.>

which constitute a powerful inference method, 

find here an alternative use as a tool to produce a desired flow in a network by exploiting the properties of the prior transition mechanism.

















Our intuitive notion of robustness of the routing policy should not be confused with other notions of robustness concerning networks which have been put forward and studied, see e.g. <cit.>.

In particular, in <cit.>, robustness has been defined through a fluctuation-dissipation relation involving the entropy rate. 

This latter notion captures relaxation of a process back to equilibrium after a perturbation and has been used to study both financial and biological networks <cit.>. Our study, inspired by  transportation and data networks, does not concern equilibrium or near equilibrium cases.

This paper features the following novel contributions:   a) it introduces an explicit index of efficiency of a transportation plan; b) The choice of the adjacency matrix as prior transition mechanism, which was justified in <cit.> on an intuitive basis, is here further motivated  trough a specific optimization problem; c) we derive an iterated bridge invariance property; d) we establish the invariance of the most probable paths. These two invariance properties, which were only briefly mentioned in <cit.> in some special cases, are here fully investigated. Their relevance for transport over networks is also illustrated. e) we study the dependence of the optimal transport on a temperature parameter. The possibility of employing the solution for near-zero temperature as an approximation of the solution to Optimal Mass Transport (OMT) is also discussed and illustrated through examples.

The outline of the 

paper is as follows. In Section <ref> we introduce 

generalized maximum entropy problems 

In Section <ref> we establish the iterated bridge property, and in Section <ref> the invariance of the most probable paths. 

Efficiency of a transport policy is introduced in Section <ref>. In Section <ref>, we introduce robust transport with fixed average path length. Section <ref> deals with efficient-robust transportation. In Section <ref>, the dependence of the optimal transport on the temperature parameter is 

investigated. The results are then illustrated through academic examples in Section <ref>.

 

§ GENERALIZED MAXIMUM ENTROPY PROBLEMS



We are given a directed, strongly connected (i.e., with a path in each direction between each pair of vertices), aperiodic graph G=(𝒳,ℰ) with vertex set 𝒳={1,2,…,n} and edge set ℰ⊆𝒳×𝒳.  We let  time vary in 𝒯={0,1,…,N}, and let ℱ𝒫_0^N⊆𝒳^N+1 denote the family of length N, feasible paths x=(x_0,…,x_N), namely paths such that x_ix_i+1∈ℰ for i=0,1,…,N-1. 

We seek a probability distribution  on ℱ𝒫_0^N with prescribed initial and final marginal probability distributions ν_0(·) and ν_N(·), respectively, and such that the resulting random evolution
is closest to a “prior” measure  on ℱ𝒫_0^N in a suitable sense.
The prior law  is induced by the Markovian evolution
 
    μ_t+1(x_t+1)=∑_x_t∈𝒳μ_t(x_t) m_x_tx_t+1(t)

with nonnegative distributions μ_t(·) over 𝒳, t∈𝒯, and weights m_ij(t)≥ 0 for all indices i,j∈𝒳 and all times. Moreover, to respect the topology of the graph, m_ij(t)=0 for all t whenever ij∉ℰ.  Often, but not always, the matrix

    M(t)=[ m_ij(t)]_i,j=1^n

does not depend on t.
The rows of the transition matrix M(t) do not necessarily sum up to one, so that the “total transported mass” is not necessarily preserved.  It occurs, for instance, when M simply encodes the topological structure of the network with m_ij being zero or one, depending on whether a certain link exists.
The evolution (<ref>) together with the measure μ_0(·), which we assume positive on 𝒳, i.e.,

    μ_0(x)>0x∈𝒳,

 induces
a measure  on ℱ𝒫_0^N as follows. It assigns to a path  x=(x_0,x_1,…,x_N)∈ℱ𝒫_0^N the value

    (x_0,x_1,…,x_N)=μ_0(x_0)m_x_0x_1⋯ m_x_N-1x_N,

and gives rise to a flow
of one-time marginals

    μ_t(x_t) = ∑_x_ℓ≠ t(x_0,x_1,…,x_N),    t∈𝒯.

 We denote by 𝒫(ν_0,ν_N) the family of probability distributions on ℱ𝒫_0^N having the prescribed marginals ν_0(·) and ν_N(·).


We seek a distribution in this set which is closest to the prior  in relative entropy where, for P and Q measures on 𝒳^N+1,  the relative entropy (divergence, Kullback-Leibler index) (PQ) is

    (PQ):={[ ∑_xP(x)logP(x)/Q(x),            (P)⊆ (Q),;                 +∞ ,            (P)⊈ (Q), ].

Here, by definition,  0·log 0=0.
Naturally, while the value of (PQ) may turn out negative due to miss-match of scaling (in case Q= is not a probability measure), the relative entropy is always jointly convex.
We consider the Schrödinger Bridge  Problem (SBP):


Determine
 
    ^*[ν_0,ν_N]:= argmin{(P) |  P∈𝒫(ν_0,ν_N)
    }.


The following result is a slight generalization (to time inhomogeneous prior) of <cit.>.
 Assume that the product M(N-1) M(N-2)⋯ M(1) M(0) has all entries positive.
Then there exist nonnegative functions  φ(·) and φ̂(·) on [0,N]×𝒳 satisfying


    φ(t,i)   =   ∑_jm_ij(t)φ(t+1,j),
    
    φ̂(t+1,j)   =   ∑_im_ij(t)φ̂(t,i),

for t∈[0,N-1], along with the (nonlinear) boundary conditions

    φ(0,x_0)φ̂(0,x_0)   =   ν_0(x_0)
    φ(N,x_N)φ̂(N,x_N)   =   ν_N(x_N),


for x_0, x_N∈𝒳.
Moreover, the solution ^*[ν_0,ν_N] to Problem <ref> is unique and obtained by

    ^*(x_0,…,x_N)=ν_0(x_0)π_x_0x_1(0)⋯π_x_N-1x_N(N-1),

where the one-step transition probabilities

    π_ij(t):=m_ij(t)φ(t+1,j)/φ(t,i)

are well defined.


The factors φ and φ̂ are unique up to multiplication of φ by a positive constant and division of φ̂ by the same constant.
Let φ(t) and φ̂(t) denote the column vectors with components φ(t,i) and φ̂(t,i), respectively, with i∈𝒳. In matricial form, (<ref>), (<ref>
) and (<ref>) read

    φ(t)=M(t)φ(t+1),   φ̂(t+1)=M(t)^Tφ̂(t),

and

    Π(t):=[π_ij(t)]=(φ(t))^-1M(t)(φ(t+1)).


Historically, the SBP was posed in 1931 by Erwin Schrödinger for Brownian particles with a large deviations of the empirical distribution motivation <cit.>, see <cit.> for a survey.

The problem was considered in the context of Markov chains and studied in  <cit.>, and some generalizations have been discussed in <cit.>. Important connections between SBP and OMT <cit.> have been discovered and developed in <cit.>.




 §.§ Iterated Bridges


In this section we explain a rather interesting property of Schrödinger bridges which is the following. If, after solving an SBP for a given set of marginals (ν_0,ν_N) and a Markovian prior  to obtain ^*[ν_0,ν_N], we decided to update the data (ν_0,ν_N) to another set of marginals (π_0,π_N) then, whether we use as prior  or ^*[ν_0,ν_N] for the SBP with the new marginals π_0 and π_N, we obtain precisely the same solution ^*[π_0,π_N]. The significance of this property will be discussed later on in the context of robust transportation.



Indeed, take  ^*[ν_0,ν_N] as prior and consider the corresponding new Schrödinger system (in matrix form)

    ψ(t)=Π(t)ψ(t+1),   ψ̂(t+1)=Π(t)^Tψ̂(t),

with boundary conditions


    ψ(0,x_0)ψ̂(0,x_0)   =   π_0(x_0),
    ψ(N,x_N)ψ̂(N,x_N)   =   π_N(x_N).


Note in the above Π(t)=(φ(t))^-1M(t)(φ(t+1)), therefore, it can be written as


    (φ(t))ψ(t)=M(t)(φ(t+1))ψ(t+1),
       (φ(t+1))^-1ψ̂(t+1)=M(t)^Tφ(t))^-1ψ̂(t).



The new transition matrix Q^* is given by

    Q^*(t)   =(ψ(t))^-1Π(t)(ψ(t+1))
       =(ψ(t))^-1(φ(t))^-1
       × M(t)(φ(t+1))(ψ(t+1)).

Let ψ_1(t)=(φ(t))ψ(t) and ψ̂_1(t)=(φ(t))^-1ψ̂(t), then

    Q^*(t)=(ψ_1(t))^-1M(t)(ψ_1(t+1)).

By (<ref>), ψ and ψ̂ are vectors with positive components satisfying

    ψ_1(t)=M(t)ψ_1(t+1),   ψ̂_1(t+1)=M(t)^Tψ̂_1(t).

Moreover, they satisfy the boundary conditions


    ψ_1(0,x_0)ψ̂_1(0,x_0)   =   π_0(x_0)
    ψ_1(N,x_N)ψ̂_1(N,x_N)   =   π_N(x_N).


Thus, (ψ_1,ψ̂_1) provide the solution to Problem <ref> when  is taken as prior.

Alternatively, observe the transition matrix Q^*(t) resulting from the two problems is the same and so is the initial marginal. Hence,   the solutions of the SBP with marginals π_0 and π_N and prior transitions Π(t) and M(t) are identical.

Thus, “the bridge over a bridge over a prior" is the same as the “bridge over the prior,” i.e., iterated bridges produce the same result.
It is should be observed that this result for probability distributions is not surprising since the solution is in the same reciprocal class as the prior (namely, it has the same three times transition probability), cf. <cit.>. It could then be described as the fact that only the reciprocal class of the prior matters; this is can be seen from Schrödinger's original construction <cit.>, and also <cit.> for the case of Markov chains. This result, however, is more general since the prior is not necessarily a probability measure. 
 
 In information theoretic terms, the bridge (i.e., probability law on path spaces) corresponding to Q^* is the I-projection
in the sense of Cziszar <cit.> of the prior onto the set of measures that are consistent with the initial-final marginals. The above result, however, is not simply an “iterated information-projection" property, since  ^*[ν_0,ν_N] is the I-projection of  onto 𝒫(ν_0,ν_N) which does not contain 𝒫(π_0,π_N) being in fact disjoint from it.



 §.§ Invariance of most probable paths


Building on the logarithmic transformation of Fleming, Holland, Mitter and others, the connection between SBP and stochastic control was developed from the early nineties on <cit.>.  More recently Brockett studied steering of the Louiville equation <cit.>. In  <cit.>, Dai Pra established an interesting path-space  property of the Schrödinger bridge for diffusion processes, that the “most probable path" <cit.> of the prior and the solution are the same. Loosely speaking, a most probable path is similar to a mode for the path space measure P.  More precisely, if both drift b(·,·) and diffusion coefficient σ(·,·) of the Markov diffusion process

    dX_t=b(X_t,t)dt+ σ(X_t,t)dW_t

are smooth and bounded, with σ(x,t)σ(x,t)^T>η I, η>0, and {x(t) | 0≤ t≤ T} is a path of class C^2, then there exists an asymptotic estimate of the probability P of a small tube around x(t) of radius ϵ. It  follows from this estimate that the most probable path is the minimizer in a deterministic calculus of variations problem where the Lagrangian is an Onsager-Machlup functional, see <cit.> for the full story[The Onsager-Machlup functional was introduced in <cit.> to develop a theory of fluctuations in equilibrium and nonequilibrium thermodynamics. ].

The concept of most probable path is, of course, much less delicate in our discrete setting. We define it for general positive measures on paths. Given a positive measure  as in Section <ref> on the feasible paths of our graph G, we say that x=(x_0,…,x_N)∈ℱ𝒫_0^N is of maximal mass if for all other feasible paths y∈ℱ𝒫_0^N we have (y)≤(x). Likewise we consider paths of maximal mass connecting particular nodes. It is apparent that paths of maximal mass always exist but are, in general, not unique. If  is a probability measure, then the maximal mass paths - most probable paths are simply the modes of the distribution. We establish below that the maximal mass paths joining two given nodes under the solution of a Schrödinger Bridge problem as in Section <ref> are the same as for the prior measure.

 
Consider marginals ν_0 and ν_1 in Problem <ref>. Assume that ν_0(x)>0 on all nodes 
x∈𝒳 and that the product M(N-1)· M(N-2)⋯ M(1)· M(0) of transition probability matrices of the prior has all positive elements (cf. with M's as in (<ref>)). Let  x_0 and x_N be any two nodes. Then, under the solution ^*[ν_0,ν_N] of the SBP, the family of maximal mass paths joining x_0 and x_N in N steps is the same as under the prior measure .

Suppose path y=(y_0=x_0,y_1,…, y_N-1,y_N=x_N) has maximal mass under the prior . In view of (<ref>) and (<ref>) and assumption (<ref>), we have

    ^*[ν_0,ν_N](y)   =   ν_0(y_0)π_y_0y_1(0)⋯π_y_N-1y_N(N-1)
    
       =   ν_0(x_0)/μ_0(x_0)φ(N,x_N)/φ(0,x_0)(y_0,y_1,…,y_N).

Since the quantity

    ν_0(x_0)/μ_0(x_0)φ(N,x_N)/φ(0,x_0)

is positive and does not depend on the particular path joining x_0 and x_N, the conclusion follows.



The calculation in the above proof actually establishes the following stronger result. 
 Let  x_0 and x_N be any two nodes in 𝒳.

Then, under the assumptions of Proposition <ref>, the measures  and ^*[ν_0,ν_N], restricted on the set of paths that begin at x_0 at time 0 and end at x_N at time N, are identical.






§ ROBUST TRANSPORT


In this section, we first discuss notions of efficiency of a transportation plan and then introduce entropy as a surrogate for robustness.



 §.§ Efficiency of a transport plan

Inspired by the celebrated paper  <cit.>, we introduce below a measure of efficiency of a  transportation plan over a certain finite-time horizon and a given network.


For the case of undirected and connected graphs,
 small-world networks <cit.> were identified as networks being highly clustered but with small characteristic path length L, where 

    L:= 
    1/n(n-1)∑_i≠ jd_ij

and d_ij is the shortest path length between vertices i and j. The inverse of the characteristic path length L^-1 is an index of efficiency  of G. There are other such indexes, most noticeably the global efficiency E_ glob introduced in <cit.>. This is defined as E_ glob=E( G)/E( G_ id) where

    E( G)=1/n(n-1)∑_i≠ j1/d_ij

and G_ id is the complete network with all possible edges in place.  Thus, 0≤ E_ glob≤ 1.
However, as argued on <cit.>, it is 1/L which “measures the efficiency of a sequential system (i.e., only one packet of information goes along the network)". E_ glob, instead, measures the efficiency of a parallel system, namely one in which all nodes  concurrently exchange packets of information.  Since we are interested in the efficiency of a specific transportation plan, we define below efficiency by a suitable adaptation of the index L.

Consider a strongly connected, aperiodic, directed graph G=(𝒳,ℰ) as in Section <ref>.  To each edge ij is now associated a length l_ij≥ 0. If ij∉ℰ, we set l_ij=+∞. The length may represent distance, cost of transport/communication/etc. Let 𝒯={0,1,…,N} be the time-indexing set. For a path x=(x_0,…,x_N)∈𝒳^N+1, we define the length of x to be

    l(x)=∑_t=0^N-1l_x_tx_t+1.

We consider the situation where initially at time t=0 the mass is distributed on 𝒳 according to ν_0(x) and needs to be distributed according to ν_N(x) at the final time t=N.           These masses are normalized to sum to one, so that they are probability distributions.  A transportation plan P is a probability measure on the (feasible) paths of the network having the prescribed marginals ν_0 and ν_N at the initial and final time, respectively. A natural adaptation of the characteristic path length is to consider the average path length of the transportation plan P, which we define as

    L(P)=∑_x∈𝒳^N+1l(x)P(x)

with the usual convention +∞× 0=0. This is entirely analogous to a thermodynamic quantity, the internal energy, which is defined as the expected value of the Hamiltonian observable in state P. Clearly, L(P) is finite if and only if the transport takes place on actual, existing links of G. Moreover, only the paths which are in the support of P enter in the computation of L(P). One of the goals of a transportation plan is of course to have small average path length since, for instance, cost might simply be proportional to length. Determining the probability measure that minimizes (<ref>) can be seen to be an OMT problem.



 §.§ Problem formulation


 Besides efficiency, another desirable property of a transport strategy is to ensure robustness with respect to links/nodes failures, the latter being due possibly to malicious attacks. We therefore seek a transport plan in which the mass spreads, as much as it is allowed by the network topology, before reconvening at time t=N in the sink nodes. We achieve this by selecting a transportation plan P that has a suitably high entropy S(P), where

    S(P)=-∑_x∈𝒳^N+1P(x)ln P(x).

Thus, in order to attain a level of robustness while guaranteeing a relatively low average path length (cost), we formulate below a constrained optimization problem that weighs in both S(P) as well as L(P).





We begin by letting L̅ designate a suitable bound on the average path length (cost) that we are willing accept. Clearly, we need that


    l_m:=min_x∈𝒳^N+1 l(x)≤L̅.

We will also assume that

    L̅≤1/|ℱ𝒫_0^N|∑ _x∈ℱ𝒫_0^Nl(x).


The rationale behind the latter, i.e., requiring an upper bound as stated, will be explained in Proposition <ref> below.

Let 𝒫 denote the family of probability measures on 𝒳^N+1. The probability measure that maximizes the entropy S(P) subject to a path-length constraint L(P)=L̅ is the Boltzmann distribution

    P_T^*(x)=Z(T)^-1exp[-l(x)/T],  Z(T)=∑_xexp[-l(x)/T],

where the parameter (temperature) T depends on L̅. To see this, 









consider the Lagrangian

    L(P,λ):=S(P)+λ(L̅- L(P)),





and observe that the Boltzman distribution (<ref>) satisfies the first order optimality condition of  with T=1/λ.
Clearly, the Boltzmann distribution has support on the feasible paths ℱ𝒫_0^N.
Hence, we get a 
version of Gibbs' variational principle that the Boltzmann distribution P_T^* minimizes the free energy functional

    F(P,T):=L(P)-TS(P)

over 𝒫. An alternative way to establish the minimizing property of the Boltzmann's distribution is to observe that

    F(P,T)=T(PP_T^*)-Tlog Z,

and therefore, minimizing the free energy over 𝒫 is equivalent to minimizing the relative entropy (PP_T^*) over P∈𝒫,



which ensures that the minimum is unique. The following properties of P_T^* are noted, see e.g. <cit.>.

  The following hold:


  i) For T↗+∞, P_T^* tends to

the uniform distribution on all feasible paths.

  ii) For T↘ 0, P_T^* tends to concentrate on the set of feasible paths having minimal length.

  iii) Assuming that l(·) is not constant over ℱ𝒫_0^N then, for each value L̅ satisfying the bounds (<ref>), there exists a unique nonnegative value of T=λ^-1∈ [0, ∞] such that P_T^* maximizes S(P) subject to L(P)=L̅.




We also

observe the Markovian nature of the measure P_T^*. 
Indeed, recall that a positive measure  on 𝒳^N+1 is Markovian if it can be expressed as in (<ref>).
Since

    P_T^*(x_0,x_1,…,x_N)=Z(T)^-1∏_t=0^N-1exp[-l_x_tx_t+1/T],

which is exactly in the form (<ref>), we conclude that P_T^* is (time-homogeneous) Markovian  with uniform initial measure μ(x_0)≡ Z(T)^-1  and time-invariant transition matrix given by

    M_T=[exp(-l_ij/T)]_i,j=1^n.

Observe however that, in general, M_T is not stochastic (rows do not sum to one). Moreover, observe that, after suitable normalization, M_T represents the transition matrix of a chain where probabilities of transition between nodes are inversely proportional to the length of the links.

Consider now ν_0 and ν_N distributions on 𝒳.  These are the “starting” and “ending” concentrations of resources for which we seek a transportation plan. We denote by 𝒫(ν_0,ν_N) the family of probability distributions on paths x∈𝒳^N+1 having ν_0 and ν_N as initial and final marginals, respectively, and we
consider the problem to maximize the entropy subject to marginal and length constraints:

 Maximize S(P) subject to P∈𝒫(ν_0,ν_N) and



L(P)=L̅.   




Note that the solution to Problem <ref> depends on L̅ as well as the two marginals ν_0, ν_N and that when L̅ is too close to l_m, the problem may be infeasible.


Once again, bringing in the Lagrangian (<ref>), which now needs to be minimized over 𝒫(ν_0,ν_N), we see that Problem <ref> is equivalent to solving the following Schrödinger Bridge problem for a suitable value of the parameter T.


minimize   {(PP_T^*)| P∈𝒫(ν_0,ν_N)}.



Thus, employing path space entropy as a measure of robustness,  the solution to Problem <ref>, denoted by ^*_T(ν_0,ν_N)  and constructed in accordance with Theorem <ref>, minimizes a suitable free energy functional with the temperature parameter 
specifying the tradeoff between
efficiency and robustness.
 Thus, Problem <ref> can be viewed as an SBP as in Section <ref> where the “prior" measure P_T^* is Markovian.



§ STRUCTURE OF ROBUST TRANSPORT



We now address in detail
Problem <ref>, namely, to identify a probability distribution P on ℱ𝒫_0^N that minimizes (·P_T^*) over 𝒫(ν_0,ν_N) where P^*_T is the Boltzmann distribution (<ref>)–the minimizing law being denoted by ^*_T[ν_0,ν_N] as before.





We show below that the two invariant properties discussed in the previous two sessions can be used to determine 
an optimal
 transport policy. We also show that the ^*_T[ν_0,ν_N] inherits from the Boltzmann distribution P^*_T properties as dictated by Proposition <ref>.

Initially, for simplicity, we consider the situation where at time t=0 the whole mass is concentrated on node 1 (source) and at time t=N it is concentrated on node n (sink), i.e., ν_0(x)=δ_1(x) and ν_N(x)=δ_n(x). We want to allow (part of) the mass to reach the end-point “sink” node, if this is possible, in less than N steps and then remain there until t=N. In order to ensure that is possible, we assume that there exists a self-loop at node n, i.e., M_Tnn>0.  Clearly, ^*_T(δ_1,δ_n)(·)=P^*_T[·| Y_0=1, Y_N=n]. The Schrödinger bridge theory provides transition probabilities so that,
for a path y=(y_0,y_1,…,y_N),


    ^*_T(δ_1,δ_n)(y)   =δ_1(y_0)∏_t=1^N-1exp(-l_y_ty_t+1/T)φ_T(t+1,y_t+1)/φ_T(t,y_t)
       =δ_1(y_0)φ_T(N,y_N)/φ_T(0,y_0)[exp(-l(y)/T)],


cf.  (<ref>) and (<ref>).
Here l(y)=∑_t=0^N-1l_y_ty_t+1 is the length of path y and φ_T satisfies together with φ̂_T the Schrödinger system (<ref>) with m_ij(t)=exp(-l_ij/T) and ν_0(x)=δ_1(x), ν_N(x)=δ_n(x).

In <cit.>, Problem <ref> was first studied with a prior measure _l having certain special properties. To introduce  this particular measure, we first recall (part of) a fundamental result from linear algebra <cit.>.


Let A=(a_ij) be an n× n matrix with nonnegative entries. Suppose there exists N such that A^N has only positive entries,

and let λ_A be its spectral radius. Then



  i) λ_A>0 is an eigenvalue of A;

  ii) λ_A is a simple eigenvalue;

  iii) there exists an eigenvector v corresponding to λ_A with strictly positive entries.



Consider now the weighted adjacency matrix B=M_T in (<ref>) 
(where we dropped the subscript T as it will be fixed throughout this section). Assume that B^N has all positive elements so that we can apply the Perron-Frobenius theorem. Let u and v be the left and right eigenvectors with positive components of the matrix B corresponding to the spectral radius λ_B. We have

    B^Tu=λ_Bu,    Bv=λ_Bv.

We assume throughout that u and v are chosen so that ∑_iu_iv_i=1.
Then, for y_0=i and y_t=j, define

    _l(i,y_1,…,_t-1,j):=λ_B^-tu_iv_je^-∑_k=0^t-1l_y_ky_k+1.

The corresponding transition matrix is

    R_l=λ_B^-1(v)^-1B(v).

It admits the invariant measure

    μ_l(i)=u_i v_i.

Note that _l and the Boltzmann distribution P_T^* have the same transition matrix but different initial distributions. In <cit.>, to which we refer for motivation and more details, the following problem was studied. 
minimize   {(P_l)| P ∈𝒫(ν_0,ν_N)}.


Under the assumption that B^N has all positive entries, this Schrödinger bridge problem has a unique solution ^*_l. In <cit.>, it was also shown that _l is itself the solution of a Schrödinger bridge problem with equal marginals and the Boltzmann distribution (<ref>) as prior. Thus, by the iterated bridge property of Section <ref>, ^*_l coincides with the solution of Problem <ref> for any choice of the initial-final marginals ν_0 and ν_N.

We recall the following rather surprising result <cit.> which includes the invariance of the most probable paths in Problem <ref> (Proposition <ref>).
 ^*_l gives equal probability to paths y∈𝒳^N+1 of equal length between any two given nodes. In particular, it assigns maximum and
equal probability to minimum length paths. 


This result is relevant when the solution of Problem <ref> for low temperature is used as an approximation to OMT, see Remark <ref> in the next section.
Finally, an important special case occurs when l_ij=0 for existing links and +∞ for non-existing. Then the matrix B reduces to the unweighted adjacency matrix A and the measure _l to the so-called Ruelle-Bowen random walk _RB. The only concern in the transport policy is in maximizing path family entropy to achieve robustness, see <cit.> for details.






§ DEPENDENCE OF
ROBUST TRANSPORT ON T

Below we study how the solution ^*_T[δ_x_0,δ_x_N] to  Problem <ref>  varies with the temperature parameter T. Here, x_0, x_N are specified nodes where mass is concentrated at the start and end times, and δ_x^'(x)=1 when x=x^' and zero otherwise. It should be noted that similar results hold for general marginal distributions as well, which are not necessarily Dirac.

 Consider the solution ^*_T[δ_x_0,δ_x_N]=:^*_T to Problem <ref> with ν_0(x)=δ_x_0(x) and ν_N(x)=δ_x_N(x). Let l_m(x_0,x_N)=min_y∈𝒳^N+1(x_0,x_N) l(y), i.e., the minimum length of N-step paths originating in x_0 and terminating in x_N. Then



  i) For T↘ 0, ^*_T tends to concentrate itself on the set of feasible, minimum length paths joining x_0 and x_N in N steps. Namely, if y=(y_0=x_0,y_1,…,y_N-1,y_N=x_N) is such that l(y)>l_m(x_0,x_N), then ^*_T(y)↘ 0 as T↘ 0.

  ii) For T↗+∞, ^*_T tends to the uniform distribution on all feasible paths joining x_0 and x_N in N steps.

  iii) Suppose 𝒳^N+1(x_0,x_N) is not a singleton and that l(·) is not constant over it. Then, for each value L̅ satisfying the bounds

    l_m(x_0,x_N)≤L̅≤1/|𝒳^N+1(x_0,x_N)|∑ _y∈𝒳^N+1(x_0,x_N)l(y)

there exists a unique value of T∈ [0,+∞] such that ^*_T satisfies the constraint 
L(^*_T)=L̅ and therefore solves  Problem <ref>.



Observe first that, since ^*_T is a probability measure on 𝒳^N+1, it must satisfy by (<ref>)

    1=∑_y∈𝒳^N+1^*_T(y)   =∑_y∈𝒳^N+1δ_1(y_0)φ_T(N,y_N)/φ_T(0,y_0)[exp(-l(y)/T)]
       =
    ∑_y∈𝒳^N+1(x_0,x_N)δ_1(y_0)φ_T(N,x_N)/φ_T(0,x_0)[exp(-l(y)/T)],


where we have used the fact that the initial and final marginals of ^*_T are δ_1 and δ_n, respectively. It follows that

    φ_T(0,x_0)/φ_T(N,x_N)   =∑_y∈𝒳^N+1(x_0,x_N)δ_1(y_0)[exp(-l(y)/T)]
       =∑_y∈𝒳^N+1(x_0,x_N)[exp(-l(y)/T)],


where again 𝒳^N+1(x_0,x_N) denotes the family of paths joining x_0 and x_N in N time periods.


Proof of i): Let y=(y_0=x_0,y_1,…,y_N-1,y_N=x_N) be such that l(y)>l_m(x_0,x_N). Then

    ^*_T(y)=φ_T(N,x_N)/φ_T(0,x_0)[exp(-l(y)/T)].

By (<ref>), we have
φ_T(0,x_0)/φ_T(N,x_N)≥exp(-l_m(x_0,x_N)/T).
Hence,

    ^*_T(y)   =φ_T(N,x_N)/φ_T(0,x_0)e^-l(y)/T≤ e^-l(y)-l_m(x_0,x_N)/T.

Since l(y)-l_m(x_0,x_N)>0, the right-hand side  tends to zero as T↘ 0.

Proof of ii): For T↗ +∞, exp(-l(y)/T) tends to 1 for all paths y∈𝒳^N+1(x_0,x_N). Since φ_T(N,x_N)/φ_T(0,x_0) does not depend on the specific path in 𝒳^N+1(x_0,x_N) (it is just a normalization like the partition function), we conclude that  as T tends to infinity, ^*_T tends to the uniform distribution on 𝒳^N+1(x_0,x_N).

Proof of iii): Note that Problem <ref> is feasible when l_m(x_0,x_N)≤L̅ 
holds. By standard Lagrangian duality theory, there exists a Lagrangian multiplier λ∈ [0, ∞] such that the maximizer of the corresponding Lagrangian (<ref>) over 𝒫(ν_0,ν_N) is the solution of Problem <ref>[Actually, using (<ref>), it is easy to see that L(^*_T)= _^*_T[l(Y)] is a strictly increasing function of T. Indeed, 
    ∂_^*_T[l(Y)]/∂ T=1/T^2_^*_T[l(Y)]
 where l(Y)=∑_t=0^N-1l_Y_tY_t+1 and Y=(Y_0, Y_1,…,Y_N) is the Markov chain. In view of Points 1 and 2, we conclude that  _^*_T[l(Y)] bijectively maps [0,+∞] onto

    [l_m(x_0,x_N),1/|𝒳^N+1(x_0,x_N)|∑ _y∈𝒳^N+1(x_0,x_N)l(y)].
].
On the other hand, maximizing (<ref>) over 𝒫(ν_0,ν_N) is equivalent to solving Problem <ref> with T=1/λ. This completes the proof.



















 
Let us interpret l_ij as the cost of transporting a unit mass over the link ij.  Then L(P) is the expected cost corresponding to the transport plan P. For T=0, the free energy functional reduces to L(P) as our problem amounts to a discrete OMT problem <cit.>. In this, one seeks minimum cost paths –a combinatorial problem which can also be formulated as a linear programming problem <cit.>.

Precisely as in the diffusion case <cit.>, we also see that when the “heat bath" temperature is close to 0, the solution of the Schrödinger bridge problem is close to the solution of the discrete OMT problem (claim i) of Theorem <ref>). Since for the former an efficient iterative algorithm is available <cit.>, we see that also in this discrete setting the SBP provides a valuable computational approach to solving OMT problems. This is illustrated in the next section through an academic example. It should also be observed that the measure ^*_T(δ_1,δ_n) is just a “Boltzmann measure" on the subset of 𝒳^N+1 of paths originating in x_0 and terminating in x_N. 
Thus the above proof is analogous to the classical one for P^*_T.



§ EXAMPLES




Consider the graph in Figure <ref>. 
We seek to transport a unit mass from node 1 to node 9 in N =3 and 4 steps. We first consider the case where the costs of all the edges are equal to 1. Here we add a zero cost self-loop at 9, i.e., l_99=0. The shortest path from node 1 to 9 is of length 3 and there are three such paths, which are
1-2-7-9, 1-3-8-9 and 1-4-8-9. If we want to transport the mass with a minimum number of  steps, we may end up using one of these three paths. To achieve robustness, we apply the Schrödinger bridge framework. Since all the three feasible paths have equal length, we get a transport plan with equal probabilities using all these three paths, regardless of the choice of temperature T. The evolution of mass distribution is given by
 
    [
           
           1     0     0     0     0     0     0     0     0
    
           0     1/3     1/3     1/3     0     0     0     0     0
    
           0     0     0     0     0     0     1/3     2/3     0
    
           0     0     0     0     0     0     0     0     1
           ],

where the four rows of the matrix show the mass distribution at time step t=0, 1, 2 ,3 respectively. As we can see, the mass spreads out first and then goes to node 9. When we allow for more steps N=4, the mass spreads even more before reassembling at node 9, as shown below, for T=1,
 
    [
           
           1     0     0     0     0     0     0     0     0
    
           0     0.4705     0.3059     0.2236     0     0     0     0     0
    
           0     0     0.0823     0.0823     0.1645     0     0.2236     0.4473     0
    
           0     0     0     0     0     0.0823     0.0823     0.1645     0.6709
    
           0     0     0     0     0     0     0     0     1
           ].

There are 7 feasible paths of length 4, which are 1-2-7-9-9, 1-3-8-9-9, 1-4-8-9-9, 1-2-5-6-9, 1-2-5-7-9, 1-3-4-8-9 and 1-2-3-8-9. The amount of mass traveling along these paths are 
	
    0.2236, 0.2236, 0.2236, 0.0823, 0.0823, 0.0823, 0.0823.

The first three are the most probable paths. This is consistent with Proposition <ref> since they are the paths with minimum length. If we change the temperature T, the flow changes. The set of most probable paths, however, remains invariant. In particular, when T=0.1, the flow concentrates on the most probable set (effecting OMT-like transport), as shown below
 
    [
           
           1     0     0     0     0     0     0     0     0
    
           0     0.3334     0.3333     0.3333     0     0     0     0     0
    
           0     0     0     0     0     0     0.3334     0.6666     0
    
           0     0     0     0     0     0     0     0     1
    
           0     0     0     0     0     0     0     0     1
           ].


Now we change the graph by setting the length of edge (7, 9) as 2, that is, l_79=2. When N=3 steps are allowed to transport a unit mass from node 1 to node 9, the evolution of mass distribution for the optimal transport plan, for T=1, is given by
 
    [
           
           1     0     0     0     0     0     0     0     0
    
           0     0.1554     0.4223     0.4223     0     0     0     0     0
    
           0     0     0     0     0     0     0.1554     0.8446     0
    
           0     0     0     0     0     0     0     0     1
           ].

The mass travels through paths 1-2-7-9, 1-3-8-9 and 1-4-8-9, but unlike the first case, the transport plan doesn't take equal probability for these three paths. Since the length of the edge (7, 9) is larger, the probability that the mass takes this path becomes smaller. The plan does, however, assign equal probability to the two paths 1-3-8-9 and 1-4-8-9 with minimum length, that is, these are the most probable paths. The evolutions of mass for T=0.1 and T=100 are 

    [
           
           1     0     0     0     0     0     0     0     0
    
           0     0     1/2     1/2     0     0     0     0     0
    
           0     0     0     0     0     0     0     1     0
    
           0     0     0     0     0     0     0     0     1
           ]

and

    [
           
           1     0     0     0     0     0     0     0     0
    
           0     0.3311     0.3344     0.3344     0     0     0     0     0
    
           0     0     0     0     0     0     0.3311     0.6689     0
    
           0     0     0     0     0     0     0     0     1
           ]

respectively. We observe that, when T=0.1 the flow assigns almost equal mass to the three available paths, while, when T=100, the flow concentrate on the most probable paths 1-3-8-9 and 1-4-8-9. This is clearly a consequence of Theorem <ref>.





§ CONCLUSIONS AND OUTLOOK

In the present paper, we considered transportation over strongly connected, directed graphs. The development built on our earlier work <cit.>. More specifically, we introduced as measure of efficiency for a given transportation plan the average path length (cost) in e.g., (<ref>), and as a measure of robustness the entropy (<ref>). This allowed us to 
explore efficient-robust transport plans via solving corresponding optimization problems. Important insights gained in the present work include the results on certain invariances of the Schrödinger's bridges – the “iterated bridge” invariance property and the invariance of the “most probable path”. We explained their relevance for efficient-robust transport over networks. We also considered the dependence of the optimal transportation schedule on the temperature parameter following similar ideas from statistical physics.  In this, we highlighted the connection between the Schrödinger's bridge problem and OMT. Specifically, the solution of the Schrödinger bridge problem near-zero temperature is an approximation to the solution of the corresponding OMT problem. The relevance of the conceptual framework developed here for assessing robustness of real world networks (e.g., communication networks <cit.>, biological <cit.>, and financial <cit.>) will be the subject of future work.

.97

99

Albertetal2000 R. Albert, H. Jeong and  A.-L. Barabási, Error and attack tolerance of complex networks, Nature, 406, pp. 378–382, 2000.

Alon U. Alon, An Introduction to Systems Biology: Design Principles of Biological Circuits, Chapman and Hall, 2006.

AGS L. Ambrosio, N. Gigli and G. Savaré, Gradient Flows in Metric Spaces and in the Space of Probability Measures, Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel, 2nd ed. 2008.

bazaraa2011linear
M. S. Bazaraa, J. J. Jarvis, and H. D. Sherali, Linear programming and
  network flows, John Wiley & Sons,
  2011.

bara2014robustness
A.-L. Barabàsi, Network Science, 2014.




olver2010robust
N. K. Olver, Robust Network Design.1em plus 0.5em minus
  0.4emPh.D. Dissertation, Department of Mathematics and Statistics,
  McGill University, 2010.

arnoldetal1994 L. Arnold, V. M. Gundlach and L. Demetrius, Evolutionary formalism for products of positive random matrices, The Annals of Applied Probability, 4, 3, pp. 859–901, 1994.
    


blaquiere1992controllability
A. Blaquière, Controllability of a Fokker-Planck equation, the
  Schrödinger system, and a related stochastic optimal control (revised
  version), Dynamics and Control, vol. 2, no. 3, pp. 235–253, 1992.

brockett2012notes
R. Brockett, Notes on the control of the Liouville equation, in
  Control of Partial Differential Equations.1em plus 0.5em minus
  0.4emSpringer, 2012, pp. 101–129.
  




CGP1 Y. Chen, T.T. Georgiou and M. Pavon, On the relation between optimal transport and Schrödinger bridges: A stochastic control viewpoint, J. Optim. Theory and Applic., 169 (2), 671-691, 2016.

CGP2 Y. Chen, T.T. Georgiou and M. Pavon, Optimal transport over a linear dynamical system,  IEEE Trans. Aut. Contr., 62 (5), 1558-2523, 2017.

CGP3 Y. Chen, T.T. Georgiou and M. Pavon, Entropic and displacement interpolation:
a computational approach using the Hilbert metric, SIAM Journal on Applied Mathematics, 76 (6), 2375-2396, 2016.

chen2016networks
Y. Chen, T. T. Georgiou, M. Pavon, and A. Tannenbaum, “Robust transport over
  networks,” IEEE Trans. Aut. Contr., 62, n.9, 4675-4682, 2017.
  
  COVER_THOMAS
T. M. Cover and J. A. Thomas.
Elements of Information Theory.
Wiley, New York, 1991.


  
csiszar Csiszár, Imre. "Sanov property, generalized I-projection and a conditional limit theorem." The Annals of Probability: 768-793, 1984.

Cuturi M.Cuturi, “Sinkhorn Distances: Lightspeed Computation of
Optimal Transport", Advances in Neural Information Processing Systems,
2292-2300, 2013.

Dai91
P. Dai Pra, A stochastic control approach to reciprocal diffusion
  processes, Applied mathematics and Optimization, vol. 23, no. 1, pp.
  313–329, 1991.


DaiPav90
P. Dai Pra and M. Pavon, On the Markov processes of Schrödinger, the
  Feynman–Kac formula and stochastic control, in Realization and
  Modelling in System Theory.1em plus 0.5em minus 0.4emSpringer,
  1990, pp. 497–504.
  
  demetrius2005 L. Demetrius and T. Manke, Robustness and network evolution: an entropic principle, Physica A: Statistical Mechanics and its Applications, 346, 3, pp. 682–696, 2005.

  
 

DB  D. Durr and A. Bach, The Onsager-Machlup functional as Lagrangian for the most probable path of a diffusion process, Comm. Math. Phys. 60, 1978, 153-170.



FilHonStr08
R. Filliger, M.-O. Hongler, and L. Streit, Connection between an exactly
  solvable stochastic optimal control problem and a nonlinear
  reaction-diffusion equation, JOTA, 137, no. 3, 497–505, 2008.






georgiou2015positive
T. T. Georgiou and M. Pavon, “Positive contraction mappings for classical and
  quantum Schrödinger systems,” J.  Math. Physics,
  vol. 56, no. 3, p. 033301, 2015.
  
GKW A. Galichon, S. Kominers and S. Weber, The Nonlinear Bernstein-Schrödinger Equation in Economics, Proceedings of the Second Conference “Geometric Science of Information", F. Nielsen and F. Barbaresco, eds., Springer Lecture Notes in Computer Sciences 9389, 51-59, 2015. 

horn2012matrix
R. Horn and C. Johnson, Matrix analysis, Cambridge Univ. Press, 2012.
  
IW N. Ikeda and S. Watanabe, Stochastic differential equations and diffusion processes, 2nd Ed., North-Holland, 1989.

IK C. T. Ireland and S. Kullback, “Contingency tables with given marginals", Biometrika,  55, 179-188, 1968.

Jam74 B. Jamison, Reciprocal processes, Probability Theory and Related Fields 30.1 (1974), 65-86.








latora2001efficient
V. Latora and M. Marchiori, “Efficient behavior of small-world networks,”
  Physical Review Letters, vol. 87, no. 19, p. 198701, 2001.

leo C. Léonard, From the Schrödinger problem to the Monge-Kantorovich problem, J. Funct. Anal., 2012, 262, 1879-1920.

leo2 C. Léonard, A survey of the Schroedinger problem and some of its connections with optimal transport, Discrete Contin. Dyn. Syst. A, 2014, 34 (4): 1533-1574.

levy1990modeling
B. C. Levy, R. Frezza, and A. J. Krener, “Modeling and estimation of
  discrete-time gaussian reciprocal processes,” Automatic Control, IEEE
  Transactions on, vol. 35, no. 9, pp. 1013–1023, 1990.

Mik T. Mikami, Monge's problem with a quadratic cost by the zero-noise limit of h-path processes, Probab. Theory Relat. Fields, 129, (2004), 245-260.

MT T. Mikami and M. Thieullen, Optimal Transportation Problem by Stochastic Optimal Control, SIAM Journal of Control and Optimization, 47, N. 3, 1127-1139 (2008).

OM L. Onsager, S. Machlup, “Fluctuations and irreversible proceses, I-II",  Phys. Rev. , 91 (1953) pp. 1505-1512; 1512-1515.

MicheleNotes  M. Pavon, Lecture Notes, University of Padova, <http://www.math.unipd.it/ pavon/Teaching_files/notes.pdf>

pavon2010discrete
M. Pavon and F. Ticozzi, “Discrete-time classical and quantum markovian
  evolutions: Maximum entropy problems on path space,” J.
  Math. Physics, vol. 51, no. 4, p. 042104, 2010.
  
PavWak91
M. Pavon and A. Wakolbinger, On free energy, stochastic control, and
  Schrödinger processes, in Modeling, Estimation and Control of
  Systems with Uncertainty.1em plus 0.5em minus 0.4emSpringer,
  1991, pp. 334–348.

rachev1998mass
S. T. Rachev and L. Rüschendorf, Mass Transportation Problems: Volume
  I: Theory, Springer Science &
  Business Media, 1998, vol. 1.

ruelle2004thermodynamic
D. Ruelle, Thermodynamic formalism: the mathematical structure of
  equilibrium statistical mechanics.1em plus 0.5em minus 0.4emCambridge University Press, 2004.

Sandhu R.Sandhu, T. Georgiou, E. Reznik, L. Zhu, I. Kolesov,
Y. Senbabaoglu, and A. Tannenbaum1, “Graph curvature for differentiating cancer networks,” Scientific Reports (Nature), vol. 5, 12323; doi: 10.1038/srep12323 (2015).

Sandhu1 R. Sandhu, T. Georgiou, and A. Tannenbaum, “Ricci curvature: An economic indicator for market
fragility and systemic risk,” Science Advances, vol. 2, doi: 10.1126/sciadv.1501495, 2016.

savla2014robust
K. Savla, G. Como, and M. A. Dahleh, “Robust network routing under cascading
  failures,” IEEE Trans. on Network Science and Engineering, vol. 1,
  no. 1, pp. 53–66, 2014.
  
S1 E. Schrödinger, Über die Umkehrung der Naturgesetze, Sitzungsberichte der Preuss Akad. Wissen. Berlin, Phys. Math. Klasse (1931), 144-153.




TWY. Takahashi and S. Watanabe, The Probability Functionals (Onsager-Machlup Functions) of Diffusion Processes, Lecture Notes in Mathematics, Vol. 851, Springer-Verlag, Berlin, 1980, pp. 433-463.

Vil C. Villani, Topics in optimal transportation, AMS, 2003, vol. 58.

Vil2 C. Villani, Optimal transport: old and new, Vol. 338. Springer, 2008.
 


Jonck C.Wang, E. Jonckheere, and R. Banirazi, “Wireless network capacity versus Ollivier-Ricci curvature under Heat
Diffusion (HD) protocol,” Proceedings of ACC, 2013.

watts1998collective
D. J. Watts and S. H. Strogatz, “Collective dynamics of 'small-world'
  networks,” Nature, vol. 393, pp. 440–442, 1998.

WC L.B. White and F. Carravetta, Optimal smoothing for finite state hidden
reciprocal processes, IEEE Trans. Automatic Control, v. 56, no. 9, 2011, pp. 2156-2161.































