text:
\section{Nonlinear Higher-order Label Spreading}\label{sec:nhols}
Now we develop our nonlinear higher-order label spreading (NHOLS) technique.
We will assume that we have a $3$-regular hypergraph $H = (V, \mathcal E, \tau)$ capturing higher-order information on the same set of nodes as a
weighted graph $G = (V, E, \omega)$, where $\mathcal E \subseteq V\times V \times V$ and $\tau$ is a hyperedge weight function $\tau(ijk)>0$.
In our experiments, we will usually derive $H$ from $G$ by considering the hyperedges of $H$ to be the set
of triangles (i.e., 3-cliques) of $G$. However, in principle we could use any hypergraph. We also do not need
the associated graph $G$, but we keep it for greater generality and find it useful in practice.
Finally, we develop our methodology for $3$-regular hypergraphs for simplicity and notational sanity, but our ideas generalize to arbitrary hypergraphs (Theorem~\ref{thm:general-convergence}).

\subsection{Nonlinear Second-order Label Spreading with Mixing Functions}
We represent $H$ via the associated third-order adjacency tensor $\A$, defined by $\A_{ijk} = \tau(ijk)$ if $ijk\in \mathcal E$ and $\A_{ijk}=0$ otherwise.
Analogous to the graph case, let $D_H=\mathrm{Diag}(\delta_1,\dots, \delta_n)$ be the diagonal matrix of the hypergraph node degrees, where
$\delta_i = \sum_{j,k :\,  ijk\in\mathcal E}\tau(ijk) = \sum_{jk}\A_{ijk}$.
Again, we assume that $H$ has no isolated nodes so that $\delta_i>0$ for all $i\in V$.

As noted in the introduction, we will make use of nonlinear \emph{mixing functions},
which we denote by $\sigma\colon\RR^2\to \RR$.
For a tensor $T=T_{ijk}$, we define the tensor map $T\sigma \colon \RR^n\to\RR^n$ entrywise:
\begin{equation}
T\sigma(f)_{i} = \sum_{jk}T_{ijk}\, \sigma(f_j,f_k). \label{eq:contraction}
\end{equation}
Hence, in analogy with the matrix case, we denote by $\S:\RR^n\to\RR^n$ the map
$$
\S(f) = D_H^{-1/2} \, \A\sigma(D_H^{-1/2}f)
$$
This type of tensor contraction will serve as the basis for our NHOLS technique.

We need one additional piece of notation that is special to the higher-order case,
which is a type of energy function that will be used to normalize iterates in order to guarantee convergence.
Let $B$ be the matrix with entries $B_{ij} = \sum_{k}\A_{kij}$. Define $\varphi \colon \RR^n \to \RR$ by
\begin{equation}\label{eq:varphi}
\varphi(f)  = \frac 1 2 \sqrt{\,\sum_{ij}B_{ij}\,  \sigma(\, f_i/\sqrt{\delta_i}\, ,\, f_j/\sqrt{\delta_j}\, )^2 }.
\end{equation}

Finally, we arrive at our nonlinear higher-order label spreading ({\algname}) method.
Given an initial vector $f^{(0)}\in \RR^n$, we define the NHOLS iterates by
\begin{equation}\label{eq:NLS}
g^{(r)} = \alpha \S(f^{(r)}) + \beta Sf^{(r)} + \gamma y,\quad
f^{(r+1)} = g^{(r)} / \varphi(g^{(r)}),\quad
r=0,1,2,\dots,
\end{equation}
where $\alpha,\beta,\gamma \geq 0$, $\alpha+\beta+\gamma = 1$, and
$y$ is an initial label membership vector.
Provided that $\sigma$ is positive (i.e., $\sigma(a,b) > 0$ for any $a, b > 0$)
and the initial vector $f^{(0)}$ is nonnegative, then all iterates
are nonnegative. This assumption on the mixing function will be crucial
to prove the convergence of the iterates.
We perform this iteration with one initial vector per label class,
analogous to standard Label Spreading.
Algorithm~\ref{alg:N2LS} gives the overall procedure.

\begin{algorithm}[t]
  \DontPrintSemicolon
	\caption{NHOLS: Nonlinear Higher-Order Label Spreading}\label{alg:N2LS}
        \KwIn{Tensor $\A$; matrix $A$; mixing function $\sigma:\RR^2\to\RR$;
          label matrix $Y \in \{0,1\}^{n \times c}$;
          scalars $\alpha,\beta,\gamma \geq 0$ with $\alpha+\beta+\gamma=1$;
          smoothing parameter $0 < \ep < 1$; stopping tolerance $\textnormal{tol}$}
	\KwOut{Predicted labels $\hat{Y} \in \{1,\dots, c\}^{n}$}
        $\tilde{F} \in \RR^{n \times c}$ \quad \texttt{\# Store approximate solutions} \;
        \For{$\ell=1,\dots,L$}{
          $y_{\ep} \gets (1-\ep)Y_{:,\ell} + \ep \mathbf{1}$\;
          $f^{(0)} \gets y_{\ep}$ \quad \texttt{\# Initialize with label smoothing}\;
    	 \Repeat{$\|f^{(r+1)}-f^{(r)}\|/\|f^{(r+1)}\| < \textnormal{tol}$}{
    	        $g \gets  \alpha \S(f^{(r)}) + \beta Sf^{(r)} + \gamma y_\ep$ \quad\phantom{xxx!!!!} \texttt{\# Following \eqref{eq:contraction} and \eqref{eq:NLS}}\;
    	        $f^{(r+1)} \gets g / \varphi(g)$ \quad \phantom{xxxxxxxxxxxxxx!!!!} \texttt{\# Following \eqref{eq:varphi} and \eqref{eq:NLS}}\;
    	 }
    	 $\tilde{F}_{:,\ell} \gets f^{(r+1)}$
	}
    \lFor{$i = 1,\ldots,n$}{$\hat{Y}_i = \arg\max_{\ell} \tilde{F}_{i,\ell}$}
\end{algorithm}

The parameters $\alpha,\beta,\gamma$ allow us to tune the contributes of the
first-order local consistency, second-order local consistency, and global
consistency. For $\beta = 0$ we obtain a purely second-order method, which can
be useful when we do not have access to first-order data (e.g., we only have a
hypergraph). The case of $\alpha=0$ reduces to a normalized version of the standard LS as in \eqref{eq:LS}.
Furthermore, we can compute the iteration in \eqref{eq:NLS} efficiently.  Each
iteration requires one matrix-vector product and one ``tensor-martix'' product,
which only takes a single pass over the input data with computational cost
linear in the size of the data.
Finally, Algorithm~\ref{alg:N2LS} uses label smoothing in the initialization (the parameter $\ep$).
This will be useful for proving convergence results and can also improve generalization~\cite{muller2019does}.

\xhdr{The special case of a linear mixing function}

The mixing function $\sigma$ is responsible for the nonlinearity of the method.
The linear mixing function $\sigma(a,b) = a+b$ reduces \algname{} to a clique-expansion approach, which corresponds to a normalized version of~\cite{zhou2007hypergraph} for $\beta=0$.
To see this, let $K$ be the $n \times|\mathcal E|$ incidence matrix of the hypergraph $H$, where $K_{i,e} = 1$ if node $i$ is in the hyperedge $e$ and $K_{i,e}=0$ otherwise;
furthermore, let $W$ be the diagonal matrix of hyperedge weights $\tau(e)$, $e\in \mathcal E$.
Then $2 \big(KWK^\top\big)_{ij}  = \sum_k \A_{ijk} + \A_{ikj}$.
Thus, for $\sigma(a,b) = a+b$,
\begin{align}
\S(f)_i =  \delta_i^{-1/2}\! \sum_{jk} \A_{ijk}\delta_j^{-1/2}\!f_j + \A_{ijk}\delta_k^{-1/2}f_k =  \delta_j^{-1/2} \!\sum_{j}(\sum_k \A_{ijk}+\A_{ikj})\delta_j^{-1/2}f_j = \big( \Theta f \big)_i,
\end{align}
where  $\Theta = 2 D_H^{-1/2} KWK^T D_H^{-1/2}$ is the normalized adjacency of the clique expansion graph~\cite{zhou2007hypergraph}.

\subsection{Global convergence and optimization framework}

Our \algname{} method extends standard LS in a natural way.  However, with the
nonlinear mixing function $\sigma$, it is unclear if the iterates even converge
or to what they might converge. In this section, we show that, remarkably,
\algname{} is globally convergent for a broad class of mixing functions
and is minimizing a regularized objective similar to \eqref{eq:LS_loss}.
Lemmas used in the proofs are provided in Appendix~\ref{app:lemmas}.

\def\map{\mathit \Phi}
For convergence, we only require the mixing function to be positive and one-homogeneous. We recall below these two properties for a general map $\map$:
\begin{align}
  \text{\emph{Positivity}:}\; & \text{$\map(x)>0$ for all $x>0$}. \\
  \text{\emph{One-homogeneity}:}\; & \text{$\map(c \cdot x)= c \cdot \map(x)$ for all coefficients $c >0$ and all $x$}.
\end{align}
For technical reasons, we require entry-wise positive initialization. This is the reason for the smoothed membership vectors
$y_\ep = (1-\ep)Y_{:,\ell}+\ep\mathbf{1}$ in Algorithm~\ref{alg:N2LS}.
This assumption is not restrictive in practice as $\ep$ can be chosen fairly small, and we
can also interpret this as a type of label smoothing~\cite{muller2019does,szegedy2016rethinking}.

The following theorem says that the \algname{} iterates converge
for a broad class of mixing functions. This is a corollary of a more general result that we prove later (Theorem~\ref{thm:general-convergence}).
\begin{theorem}\label{thm:convergence}
  Let $f^{(r)}$ be the iterates in Algorithm~\ref{alg:N2LS}.
  If $\sigma$ is positive and one-homogeneous, then the sequence $\{f^{(r)}\}_{r}$ converges to a unique stationary point $f^*>0$ with $\varphi(f^*)=1$.
\end{theorem}

Even if the iterates converge, we would still like to know to what they converge.
We next show that for differentiable mixing functions $\sigma$,
a scaled version of $f^*$ minimizes a regularized objective
that enforces local and global consistency.
For a smoothed membership vector $y_\ep = (1-\ep)Y_{:,\ell}+\ep \mathbf{1}$ with $0 < \ep < 1$, consider the loss function:
\begin{equation}\label{eq:loss}
    \vartheta(f)  = \frac 12 \bigg\{ \Big\| f - \frac{y_\ep}{ \varphi(y_\ep)} \Big\|_2^2 + \lambda \sum_{ij}A_{ij}\Big(\frac{f_i}{ \sqrt{d_i} }-\frac{f_j}{ \sqrt{d_j}}\Big)^2 + \mu   \sum_{ijk}\A_{ijk} \Big(\frac{f_i}{ \sqrt{\delta_i}}- \frac12 \sigma\Big(\frac{f_j}{ \sqrt{\delta_j}},\frac{f_k}{ \sqrt{\delta_k}}\Big) \Big)^2  \bigg\}
\end{equation}
As for the case of standard LS, $\vartheta$ consists of a global consistency
term regularized by a local consistency term. However, there are two main
differences. First, the global consistency term now considers a normalized
membership vector $\tilde y_\ep = y_\ep/\varphi(y_\ep)$.  As $\varphi(\tilde y_\ep)=1$,
we seek for a minimizer of $\vartheta$ in the slice $\{f:\varphi(f)=1\}$.
Second, the regularizer now combines the normalized
Laplacian term with a new tensor-based term that accounts for higher-order interactions.

Analogous to standard LS, \algname{} can be interpreted as a projected diffusion
process that spreads the input label assignment via the nonlinear gradient flow
corresponding to the energy function $\tilde \vartheta(f) = \vartheta(f) - \frac \mu 2 \varphi(f)^2$. In fact, for $y_\ep$ such that $\varphi(y_\ep)=1$, we have that
\begin{equation}\label{eq:EulerNLS}
    f-h\nabla\tilde \vartheta(f) = (1-h-\lambda h +\mu h)f  + h\lambda Sf + h \mu \S(f) + h y_\ep \, .
\end{equation}
(A proof of this identity is the proof of Theorem~\ref{thm:loss}.)
Thus, our \algname{} iterates in \eqref{eq:NLS} correspond to projected gradient descent applied to $\tilde\vartheta$, with step length $h$ chosen so that $(1-h)/h = \lambda + \mu$.
This is particularly useful in view of \eqref{eq:loss}, since $\tilde \vartheta$ and $\vartheta$ have the same minimizing points on $\{f:\varphi(f)=1\}$. Moreover, as  $\nabla \psi$ in \eqref{eq:ODE} can be interpreted as a discrete Laplacian operator on the graph~\cite{zhou2004learning},
we can interpret $\nabla \tilde \vartheta$, and thus $\S$,  as a hypergraph Laplacian operator,
which adds up to the recent literature on (nonlinear) Laplacians on hypergraphs~\cite{chan2018spectral,louis2015hypergraph}.

Unlike the standard label spreading, the loss functions $\vartheta$ and $\tilde \vartheta$ are not convex in general.
Thus, the long-term behavior $\lim_{t\to\infty}f(t)$ of the gradient flow $\dot f(t) = -\nabla \tilde \vartheta(f(t))$ is not straightforward.
Despite this, the next Theorem \ref{thm:loss} shows that the \algname{} can converge to a unique global minimizer of $\vartheta$ over the set of nonnegative vectors.
For this result, we need an additional assumption of differentiability on the mixing function $\sigma$.
\begin{theorem}\label{thm:loss}
  Let $f^{(r)}$ be the sequence generated by Algorithm~\ref{alg:N2LS}.
  If $\sigma$ is positive, one-homogeneous, and differentiable, then the sequence $\{f^{(r)}\}_{r}$
  converges to the unique global solution of the constrained optimization problem
   \begin{equation}\label{eq:constrained_loss}
   \min \vartheta(f) \; \text{s.t. }f> 0 \text{ and } \varphi(f)=1.
  \end{equation}
\end{theorem}
\begin{proof}
Let
$$
E_1(f) = \sum_{ij}A_{ij}(f_i/\sqrt{d_i}-f_j/\sqrt{d_j})^2, \qquad  E_2(f) = \sum_{ijk}\A_{ijk}(f_i/\sqrt{\delta_i}-\sigma(f_j/\sqrt{\delta_j},f_k/\sqrt{\delta_k})/2)^2
$$
and consider the following modified loss
\begin{equation*}
   \tilde  \vartheta(f)  = \frac 12 \Big\{ \Big\| f - \frac y{\varphi(y)} \Big\|^2 + \lambda E_1(f) + \mu E_2(f)  - \mu \varphi(f)^2 \Big\}, .
\end{equation*}
Clearly, when subject to $\varphi(f)=1$, the minimizing points of $\tilde\vartheta$ and those of $\vartheta$ in \eqref{eq:loss} coincide. We show that the gradient of the loss function $\tilde \vartheta$  vanishes on $f^*>0$ with $\varphi(f^*) = 1$ if and only if $f^*$ is a fixed point for the iterator of Algorithm \ref{alg:N2LS}.

For simplicity, let us write $\tilde y = y/\varphi(y)$ with $y>0$.  We have $\nabla \|f-\tilde y\|^2 = 2(f-\tilde y)$ and  $\nabla E_1(f) = 2\L f=2(I-D_G^{-1}AD_G^{-1})f$. As for $E_2$, observe that from $\sum_{jk}\A_{ijk}=\delta_i$,we get
\begin{align*}
    f^\top (D_H f-\A \sigma(f)) &= \sum_{i}\delta_i f_i^2 - \sum_{ijk}f_i \A_{ijk} \sigma(f_j,f_k) = \sum_{ijk} \A_{ijk} \big(f_i^2 - f_i\sigma(f_j,f_k)\big) \\
    &= \sum_{ijk} \A_{ijk} \Big(f_i - \frac{\sigma(f_j,f_k)}{2}\Big)^2 - \frac 1 4 \sum_{jk}B_{jk} \sigma(f_j,f_k)^2
\end{align*}
with $B_{jk} = \sum_i \A_{ijk}$. Thus, it holds that
$$
f^\top (D_H f-\A \sigma(f)) = E_2(D_H^{1/2}f) - \varphi(D_H^{1/2}f)^2\, .
$$
Now, since $\sigma(f)$ is one-homogeneous and differentiable, so is $F(f) = \P\sigma(f)$, and  using Lemma \ref{lem:Euler} we obtain $\nabla \{E_2(D_H^{1/2}f)-\varphi(D_H^{1/2}f)^2\} = 2(D_Hf - \A \sigma(f))$ which, with the change of variable $f\mapsto D_H^{-1/2}f$, yields
$$
\nabla \{E_2(f)-\varphi(f)^2\} = f-D_H^{-1/2}\A\sigma(D_H^{-1/2}f)
$$

Altogether we have that
\begin{align*}
    \nabla \tilde \vartheta (f)  &= f-\tilde y + \lambda (I-D_G^{-1/2}AD_G^{-1/2})f + \mu \{ f-D_H^{-1/2}\A\sigma(D_H^{-1/2}f) \}\\
    &=(1+\lambda+\mu)f - \lambda D_G^{-1/2}AD_G^{-1/2}f - \mu D_H^{-1/2}\A\sigma(D_H^{-1/2}f) - \tilde y,
\end{align*}
which implies  that $f^*\in \RR^n_{++}/\varphi$ is such that  $\nabla \tilde \vartheta (f^*) = 0$ if and only if $f^*$ is a fixed point of \algname{}, i.e.\
$$
 f^* = \alpha D_H^{-1/2}\A\sigma(D_H^{-1/2}f^*) + \beta  D_G^{-1/2}AD_G^{-1/2}f^* +\gamma  \tilde y
$$
with $\lambda = \beta/\gamma$, $\mu=\alpha/\gamma$ and $\alpha+\beta+\gamma=1$.

Finally, by Theorem \ref{thm:convergence} we know that the \algname{} iterations in Algorithm \ref{alg:N2LS} converge to $f^*>0$, $\varphi(f^*)=1$ for all positive starting points $f^{(0)}$. Moreover, $f^*$ is the unique fixed point in the slice $\RR^n_{++}/\varphi = \{f>0:\varphi(f) =1\}$. As $\vartheta$ and $\tilde \vartheta$ have the same minimizing points on that slice, this shows that $f^*$ is the global solution of $\min \{ \vartheta(f) : f\in \RR^n_{++}/\varphi\}$, concluding the proof.
\end{proof}

\subsection{Main convergence result and extension to other orders} \label{sec:fo_nonlin}
Theorem~\ref{thm:convergence} is a direct consequence of our main convergence theorem below,
where $F(f) = \alpha D_H^{-1/2}\A\sigma(D_H^{-1/2}f)+\beta D_G^{-1/2}AD_G^{-1/2}f$ and $y = \gamma y_\ep$.
By Lemma~\ref{lem:upper-bound} all of the assumptions for Theorem~\ref{thm:general-convergence} are satisfied, and the convergence follows.

\begin{theorem}\label{thm:general-convergence}
    Let $F:\RR^n\to\RR^n$ and $\varphi:\RR^n\to\RR$ be positive and one-homogeneous mappings, and let $y$ be a positive vector. If there exists $C>0$ such that $F(f)\leq Cy$,  for all $f$ with $\varphi(f)=1$, then, for any $f^{(0)}>0$, the sequence
  $$
  g^{(r)} = F(f^{(r)}) + y \qquad f^{(r+1)} = g^{(r)}/\varphi(g^{(r)})
  $$
  converges to $f^*>0$, unique fixed point of $F(f)+y$ such that $\varphi(f^*)=1$.
\end{theorem}

This general convergence result makes it clear how to transfer the second-order setting discussed in this work to hyperedges of any order.
For example, nonlinearities could be added to the graph term as well. A nonlinear purely first-order label spreading has the general form
$f^{(r+1)} = \beta M \sigma(f^{(r)}) + \gamma y$,
where $M \sigma(f)$ is the vector with entries $M\sigma(f)_i = \sum_j M_{ij}\sigma(f_j)$, $\sigma$ is a nonlinear map and $M$ is a graph matrix. This
formulation is quite general and provides new convergence results for
nonlinear graph diffusions recently proposed by Ibrahim and Gleich~\cite{ibrahim2019nonlinear}.
For simplicity and in the interest of space, we do not use this extension in our
experiments, but out of theoretical interest we note that Theorem~\ref{thm:general-convergence} would allow us to take this additional nonlinearity into account.

\begin{proof}
  Let $\varphi:\RR^n\to\RR$ and $F:\RR^n\to\RR^n$ be one-homogeneous and positive maps. Let $\RR^n_+$ and $\RR^n_{++}$ denote the set of entrywise nonnegative and entrywise positive vectors in $\RR^n$, respectively. Also, let $\RR^n_{++}/\varphi = \{f \in \RR^n_{++} : \varphi(f) = 1\}$.
This result falls within the family of Denjoy-Wolff type theorems for  nonlinear mappings on abstract cones, see e.g., Lemmens et
al.~\cite{lemmens2018denjoy}. Here we provide a simple and self-contained proof. Define
\[
G(f) = F(f) + y \qquad \text{and}\qquad \tilde G(f) = \frac{G(f)}{\varphi(G(f))}\, .
\]
Notice that $f^{(r+1)}=\tilde G(f^{(r)})$, $r=0,1,2,\dots$ and that, by assumption, $G(f)>0$ for all $f>0$. Thus $\varphi(G(f))>0$ and $\tilde G(f)$ is well defined on $\RR^n_{++}$. Moreover, $\tilde G$ preserves the cone slice $\RR^n_{++}/\varphi$ i.e.\ $\tilde G(f)\in \RR^n_{++}/\varphi$ for all $f\in \RR^n_{++}/\varphi$. For two points $u,v \in \RR^n_{++}$ let
$$
d(u,v) = \log\Big(\frac{M(u/v)}{m(u/v)}\Big)
$$
be the Hilbert distance,
where $M(u/v) = \max_{i}u_i/v_i$ and $m(u/v) = \min_i u_i/v_i$.
As  $\sigma$ is one-homogeneous also $\varphi$ is one-homogeneous and thus $\RR^n_{++}/\varphi$ equipped with the Hilbert distance is a complete metric space,  \cite{gautier2019perron} e.g. In order to conclude the proof it is sufficient to show that  $\tilde G$ is a contraction with respect to such metric. In fact, the sequence $f^{(r)}$ belongs to $\RR^n_{++}/\varphi$ for any $f^{(0)}$ and since $(\RR^n_{++}/\varphi,d)$ is complete, the sequence $f^{(r)}$ converges to the unique fixed point $f^*$ of $\tilde G$ in $\RR^n_{++}/\varphi$.

We show below that  $\tilde G$ is a contraction. To this end, first note that by definition we have
$
d(\tilde G(u),\tilde G(v)) = d(G(u),G(v))
$.
Now note that, as $\sigma$ is homogeneous and order preserving, for any $u,v\in \RR^n_{++}$ we have $m(u/v)F(v)=F(m(u/v)v)\leq F(u)$, $M(u/v)F(v)=F(M(u/v)v)\geq F(u)$, $m(u/v)\varphi(v)=\varphi(m(u/v)v)\leq \varphi(u)$ and $M(u/v)\varphi(v)=\varphi(M(u/v)v)\geq \varphi(u)$. Moreover, for any $u,v\in \RR^n_{++}/\varphi$ it holds
$$
m(u/v) = \varphi(u)m(u/v)\leq \varphi(v) = 1 \leq \varphi(u)M(u/v) = M(u/v),
$$
thus $m(u/v)\leq 1 \leq M(u/v)$.
By assumption there exists $C>0$ such that $F(u)\leq Cy$, for all $u\in \RR^n_{++}/\varphi$. Therefore, for any $u,v\in \RR^n_{++}/\varphi$, we have
\begin{align*}
(m(u/v)C &+ 1)(F(v)+ y)= (m(u/v)C+ m(u/v)- m(u/v)+1)F(v)+(m(u/v)C + 1) y \\
&= m(u/v)CF(v) +  m(u/v)F(v) + (1-m(u/v))F(v) + (m(u/v)C + 1) y\\
&\leq CF(u) +  F(u) + (1-m(u/v))Cy + (m(u/v)c + 1) y \\
&= (C+1)(F(u)+ y)
\end{align*}
where we used the fact that $(1-m(u/v))\geq 0$ to get $(1-m(u/v))F(v)\leq (1-m(u/v))Cy$. Thus
$$
m(G(u)/G(v)) = m\big((F(u)+ y) / (F(v)+ y)\big) \geq (m(u/v)C+1)/(C+1)\, .
$$
Similarly, as $(1-M(u/v))\leq 0$,  we have
\begin{align*}
(M(u/v)C + 1)(F(v)+ y)&\geq C F(u) + F(u) + (1-M(u/v))Cy + (M(u/v)C + 1) y \\
&= (C+1)(F(u)+ y)
\end{align*}
which gives $M(G(u)/G(v)) \leq (M(u/v)C+1)/(C+1)$. Therefore,
$$
d(G(u),G(v)) = \log\Big(\frac{M(G(u)/G(v))}{m(G(u)/G(v))} \Big) \leq \log\Big( \frac{M(u/v)C+1}{m(u/v)C+1}\Big) = \log\Big( \frac{M(u/v)+\delta}{m(u/v)+\delta} \Big)
$$
with $\delta = 1/C$. Finally, using Lemma \ref{lem:logarithm} we get
$$
d(\tilde G(u),\tilde G(v)) = d(G(u),G(v)) \leq \left(\frac{M(u/v)}{M(u/v)+\delta}\right) d(u,v) < d(u,v)
$$
which shows that $\tilde G$ is a contraction in the complete metric space $(\RR^n_{++}/\varphi,d)$.
\end{proof}

config: arxiv


TITLE: Properties of Logarithms
QUESTION [1 upvotes]: How do you simplify the following expression? $$\log\left(3^{(5^7)}\right)$$ I know that logarithms are like the inverse of exponents, but are there any tricks to simplify powers inside logarithms?
Edit: There are five answer choices:

(A) $7\log(3^5)$
(B) $35\log(3)$
(C) $7(\log(3))(\log(5))$
(D) $7(\log(3)+\log(5))$
(E) $5^7\log(3)$

REPLY [6 votes]: As $\displaystyle  \log(a^m)=m\log a$ where both $\log$ remain defined
Here $a=3, m=5^7$

REPLY [5 votes]: $\log 3^{(5^7)}=5^7\log 3$
The power on the inside become multiplication on the outside, and becomes the simplest form (unless you want to turn $5^7$ into a single long number instead of that power)


TITLE: No supersymmetric particles have been found in the LHC. Isn't this proof that Supersymmetry doesn't exist?
QUESTION [3 upvotes]: The LHC can reach energies from $7(TeV)$ to $13(TeV)$ (see here) and the question of which this is supposed a duplicate. Which I think it isn't, because in that question (which has been asked already eight years ago) there is nothing asked (which obviously just couldn't) about the current situation. In an answer to it, it is said that until 2020 (which is just a guess) the lower bound of SUSY particles will be reached. Now the lightest sparticle is the neutralino with a supposed mass of about $300(GeV).$, which is 40(!) times as high as the energy the LHC can supposedly reach and I think (correct me if I'm wrong) that there are sparticles which have a mass lower than this. I couldn't find the mass though of the next lightest sparticle (after the neutralino) predicted by any theory that incorporates SUSY. For sure, the neutralino hasn't been found though. Maybe that's because it's difficult to find them, Which I don't know. Wouldn't (in the light of this) the next sparticle (with respect to mass) have been found yet?
So isn't this proof that the search for supersymmetric particles is a search in the dark for nothing and supersymmetry is non-existing?

REPLY [1 votes]: No, it is not proof. There are supersymmetric models in which supersymmetry would not be detectable at LHC energies. For an example, see this paper.
Do not confuse the general idea of supersymmetry with a particular supersymmetric model such as MSSM, the Minimal Supersymmetric Standard Model, which does now seem to be untenable.


TITLE: finding the shortest distance between a point and a set i.e $d(x,A)$
QUESTION [1 upvotes]: $X = C[0,1]$ with sup metric.
$A$ is the set of all functions $z\in X$ with $z(0)=0$. $x$ is the function $x(t) = t^2$ ,$y(t)=\cos(2\pi t)$ . Find $d(x,A)$ and $d(y,A)$
Attempt: as $x(t) = t^2$ is continuous and $x(0) = 0$ so $x\in A$ then $d(x,A) = 0$
for $y(t)$ we can see that $\sup |\cos(2\pi t) - z(t)| \leq \sup [t + |z(t)|] = 1 + \sup|z(t)|$ for $t\in [0,1]$, it can get the infimum value $1$ only when $z = 0$.
since $d(y,A) = \inf${ $1 + \sup |z(t)|: z\in A$}
so $d(y,A) = 1$.
Is my reasoning for the last part correct?
I just learned this concept and I want to see if I learned it correctly.

REPLY [1 votes]: Yes, if $x\in  A$ then, $$\mbox{dist} (x,A)  =0$$ in any metric space.
For any $z \in A $ we have $$||z-y||_{\infty} \geq |x(0)-y(0)|=1$$
hence $$\mbox{dist} (y,A)\geq 1$$ but for the function $A\ni z_0 (t) \equiv 0$ on $[0,1].$ We get $$||z_0-y||_{\infty} =\sup_{t\in [0,1]} |0-\cos (2\pi t )|=1$$ hence $$\mbox{dist} (y,A)  =1$$


TITLE: Expectation of an increment of standard Brownian motion cubed
QUESTION [2 upvotes]: Suppose that $W$ is standard Brownian motion and that process $X$ is defined via $X_t = W_t^3 - 3tW_t$. I need to show $X$ is a martingale by calculating $\mathbb E[X_t|F_s]$, where $s<t$. It's all going fine except I'm not sure how to calculate $$\mathbb E[(W_t-W_s)^3|F_s] = \mathbb E[(W_t-W_s)^3].$$
Can anyone give me a hint?

REPLY [1 votes]: You want to prove that $\mathbb{E}[ W_t^3 - 3tW_t |\mathcal{F}_s   ] \overset{d}=  W_s^3 - 3sW_s  $, right?
It's not so clear to me where you've got the $\mathbb{E}[ (W_t - W_s)^3|\mathcal{F}_s] $ term from (maybe you could explain this if you still need more help), but you could try expanding the cubed expression into $W_t^3 + 3W_t^2 W_s + 3W_tW_s^2 + W_s^3$, and use standard properties of the normal distribution, and the fact that $W_s$ is just a fixed number when you're using the conditioning on knowing $\mathcal{F}_s$.
I hope this helps - good luck! :)


TITLE: Why induction is defined as an implication instead of an "if and only if" statement?
QUESTION [2 upvotes]: The formal definition of induction, taken from wikipedia, is written as
$$\forall P.\,[[P(0)\land \forall (k\in \mathbb {N} ).\,[P(k)\implies P(k+1)]]\implies \forall (n\in \mathbb {N} ).\,P(n)]$$
But then, it is this version true?
$$\forall P.\,[[P(0)\land \forall (k\in \mathbb {N} ).\,[P(k)\implies P(k+1)]]\iff \forall (n\in \mathbb {N} ).\,P(n)]\tag{1}$$
If it is not true can you show me why? (I cant found a counterexample.) Thank you.

The background of this question is that if $(1)$ is true then the proof for the equivalence of weak induction ($W$) and strong induction ($S$) is really trivial.
Let the shortened theorem of strong induction to be $$S\implies \forall (n\in \mathbb {N} ).\,P(n)$$
and by $(1)$ the definition of weak induction $$W\iff \forall (n\in \mathbb {N} ).\,P(n)$$
The case $S\implies W$ is trivial but now the case $W\implies S$ is trivial too because we can verify that
$$\forall (n\in \mathbb {N} ).\,P(n)\implies S$$

REPLY [1 votes]: Induction is 1/2 of the definition of $\forall$ for natural numbers.  It is the rule that let's you introduce $\forall$.  It is:
$$\frac{P(0),~ (P(n) \vdash P(n + 1))}{\forall m~P(m)}$$
Note that it is not $\forall n P(n) \implies P(n+1)$.  In induction, $n$ is treated as a free variable.  How exactly would you prove $\forall n P(n) \implies P(n+1)$ if you don't already have a rule for introducing $\forall$?  Induction is the rule for introducing $\forall$ so it can't depend on it already being introduced.
The rule for eliminating $\forall$ is (roughly) :
$$\frac{\forall m~P(m)}{P(n)}$$
So there are 2 reasons it is not an equivalence:  first, induction is (usually) an inference, not an axiom, and inferences are 1 directional.  Second, the reverse direction isn't useful, the elimination rule is what you want for the reverse direction.


TITLE: Show if $\lim_{x \rightarrow 0} \frac{\sin(\sin(x))}{x}$ exists, with product/quotient/substitution rules
QUESTION [2 upvotes]: Show if $\lim_{x \rightarrow 0} \frac{\sin(\sin(x))}{x}$ exists, if so determine its value.
We have to use the product-rule and quotient-rule etc. to show this.
I thought this didn't exist, but my solution book says it does(without any explanation).
Here's why I thought it wouldn't exist:
Since $\lim_{x \rightarrow 0} \sin(x)=0$ and $\lim_{y \rightarrow 0} \sin(y)=0$ , using the substitution-rule gives us $\lim_{x \rightarrow 0} \sin(\sin(x))=0$.
We also know $\lim_{x \rightarrow 0} \frac{1}{x}$ diverges.
So when using the product rule, we find  $\lim_{x \rightarrow 0} \frac{\sin(\sin(x))}{x}$ doesn't exist.
I don't know where I went wrong here.

REPLY [0 votes]: You are allowed to use the product rule when the limits of the factors exist, which is not the case here. Your use of the rule is invalid.
Actually, this is a $\dfrac00$ undeterminate form that you may not rewrite as $$\lim\frac00=\lim0\cdot\lim\frac10.$$

On the opposite, the solution given by Miguel Atencia is valid because in
$$\lim\frac{\sin(\sin(x))}{x}=\lim\frac{\sin(\sin(x))}{\sin(x)}\cdot\lim\frac{\sin(x)}{x}$$ both limits exist (and are $1$).


TITLE: Closed form of $I(a)=\int_{0}^a {(e^{-x²})}^{\operatorname{erf}(x)}dx $ and is it behave similar with error function?
QUESTION [3 upvotes]: $\newcommand{\erf}{\operatorname{erf}}$
The computation of $\int_{0}^{a}{(e^{-x²})}^{\erf(x)}dx$ for large $a$ gives $0.972106...$ by wolfram alpha, but
according to  JJacquelin comments which claimed that $I(a)=\int_{0}^{a}{(e^{-x²})}^{\erf(x)}dx$  is a  non-standard special function ,and according to the comments of yuriy which showed that is a just a constant , then it must to ask about closed form of
$$I(a)=\int_{0}^a {(e^{-x²})}^{\operatorname{erf}(x)}dx $$ if it exists with $a$ positive real number , and also to know if this special function behave as the same with Error function or exponontial function since it is a composition of them ? and what about it's application in probability and in differential equation area ? In addition of that what about  representation of it's hypergeometric function ?
Edit 01:  I have edited the question according to the below comments and to know the closed form of this special function since it is not standard .
Edit 02 I have added some detaill in my question according to the good answer which is gaven by yuriy in order to know more about this new function
Edit: I have added other question which seking for the hypergeometric function of the titled function .
Note (01):$\erf(x) = \frac{2}{\sqrt{\pi}} \int_0^x e^{-t^2}dt.$
Note (02): The motivation of this function is to look for the behavior of integral of some functions where they are represented as a function power it's antiderivative function however the example we take here is :$\int ({f'})^{kf}$ .

REPLY [6 votes]: $\newcommand{\erf} {\operatorname{erf}}$I hope this will be helpful to you.
First, abandon the search for closed form. It's not likely it exists.
Now, if you really need a simple expression for $I(a)$ in some range of values, there are ways to get various approximations.
The function is very nice. It goes to its limit at $\infty$ very very fast. Here's the plot of $I(a)$ for $a \in [0,10]$:

So (depending on the accuracy you need) you can easily take $I(a)=I(\infty)$ for $a > a_0$ with $a_0$ around $3$ or $4$.
Mathematica gives for the first $100$ digits:
$$I(\infty)=0.972106992769178593151077875442391175554272\\1833855699009722910408441888759958220033410678218401258734$$

Now, what to do for small $a$?
The function is so nice, you can just use the Taylor expansion around $a =0$. The first term is:
$$I(a) \approx a$$
Here's the plot for $a \in [0,1]$:

The proof is simple. The Taylor series look like this:
$$I(a)=I(0)+I'(0) a+\frac{I''(0)}{2!} a^2+\frac{I'''(0)}{3!} a^3+\dots$$
We can see that:
$$I(0)=0$$
$$I'(0)=e^{-a^2 \erf (a) } \bigg| _{a=0}=1$$
Now let's find a better approximation by computing the higher derivatives:
$$I''(a)=\left( e^{-a^2 \erf (a) } \right)'=-\frac{2}{\sqrt{\pi}} a e^{-a^2 (\text{erf}(a)+1)} \left(\sqrt{\pi } e^{a^2} \text{erf}(a)+a\right)$$
$$I''(0)=0$$

I use Mathematica as a shortcut, but it's easy to do it by hand, if you remember:
$$\erf' (x)=\frac{2}{\sqrt{\pi}} e^{-x^2}$$

$$I'''(0)=0$$
$$I^{ IV} (0)=-\frac{12}{\sqrt{\pi}}$$

So our next approximation is:
$$I(a) \approx a-\frac{ 1}{2\sqrt{\pi}} a^4$$
The plot with both approximations (orange, green) and the function itself (blue) is given below:

You can continue in the same way for higher derivatives.

Now I admit that it's possible you need the values of $I(a)$ for all the possible $a$ and with high precision, so the approximations won't do. Then you need to turn to numerical integration (as Mathematica did for me to plot the function).

Another way to approximate the function is using its derivative:
$$\frac{d I}{da}=e^{-a^2 \erf (a) }$$
But this is an ordinary differential equation, which can be solved numerically.
As an illustration, here's a simple explicit Euler scheme for the step size $h$:
$$\frac{I(a+h)-I(a)}{h}=e^{-a^2 \erf (a) }$$
$$I(a+h)=I(a)+h e^{-a^2 \erf (a) }$$
We can use an initial value $I(0)=0$.
For $h=\frac{1}{10}$ we have the following result (red dots) compared to the exact function (blue line):

For $h=\frac{1}{50}$:

This way can serve as a good alternative to numerical integration (depending on the context and the application of course).


TITLE: Explanation about proof of a continuity theorem for the inverse of a function.
QUESTION [1 upvotes]: Theorem: Let $ D\subset \mathbb{R} $ a compact subset and  a continuous  injective function $f$. Then the inverse function of $ f, f^{-1}: f(D)\rightarrow D $ define by $ f^{-1}(f(x))= x$ is a continuous function.
Proof: Only need proof $ f(V) $ is open set $ \forall x\in D$
Let $ V\subset D $ open, then $ D-V $ is closed set
As $ D $ is compact, then $ D-V $ is compact\
As $ f $ is continuous function then $ f(D-V) $ is closed set
As $ D $ is compact, then $ D-V $ is compact.
As $ f $ is continuous then $ f(D-V) $ is compact.
As $ f $ is injective, then $ f(D-V)=f(V^{c})=(f(V))^{c} $ then $ f(V) $ is open.
My question is this, because is sufficient prove $ f(V) $ is open set?

REPLY [2 votes]: The argument starts out well, but then develops some gaps (and has some repetitions).
Since $D-V$ is closed and $D$ is compact, $D-V$ is compact (good so far).
Since $f$ is a continuous function and $D-V$ is compact, $f(D-V)$ is compact.
Since compact subsets of $\mathbb{R}$ are closed, $f(D-V)$ is closed.
Since $f$ is injective, $f(D-V)=f(V^c)=(f(V))^c$. Therefore $f(V)$ is open.
This completes the proof that "if $V$ is open then $f(V)$ is open".
Since $f$ is injective we can reword this to say "if $V$ is open then $(f^{-1})^{-1} (V)$ is open", which by definition means that $f^{-1}$ is continuous.


text:
\begin{document}

\title{First passage percolation on sparse random graphs with boundary weights}

\ifarxiv
\author{Lasse \Leskela \and Hoa Ngo}
\maketitle
\fi
\ifapt
\authornames{LASSE LESKEL\"A AND HOA NGO}
\shorttitle{First passage percolation with boundary weights}
\authorone[Aalto University]{Lasse Leskel\"a}
\emailone{lasse.leskela@aalto.fi, hoa.ngo@aalto.fi}
\authorone[Aalto University]{Hoa Ngo}
\addressone{Department of Mathematics and Systems Analysis, Aalto University, Otakaari 1, 02015 Espoo, Finland}
\fi

\begin{abstract}
A large and sparse random graph with independent exponentially distributed link weights can be used to model the propagation of messages or diseases in a network with an unknown connectivity structure. In this article we study an extended setting where also the nodes of the graph are equipped with nonnegative random weights which are used to model the effect of boundary delays across paths in the network. Our main results provide approximative formulas for typical first passage times, typical flooding times, and maximum flooding times in the extended setting, over a time scale logarithmic with respect to the network size.
\end{abstract}

\ifarxiv
\noindent
{\bf Keywords}: sparse random graph, percolation, flooding, broadcasting, rumor spreading, SI epidemic model, configuration model, incubation time \\[2ex]
\noindent
{\bf AMS subject classification}: 60K35; 91D30 \\[2ex]
\fi
\ifapt
\keywords{sparse random graph; percolation; flooding; broadcasting; rumor spreading; SI epidemic model; configuration model; incubation time}
\ams{60K35}{91D30}
\fi

\section{Introduction}

Classical first passage percolation theory, initiated about a half century ago in \cite{Hammersley_Welsh_1965}, studies a connected undirected graph $G$ where each adjacent node pair $e$ is attached a weight $W(e) > 0$. When the weights are independent and identically distributed random variables, then
\[
 W_G(u,v)
 \weq \inf_{\Gamma} \, \sum_{e \in \Gamma} W(e),
\]
where the infimum is taken over all paths $\Gamma$ in graph $G$ from $u$ to $v$, defines a natural random metric which has been intensively studied in a wide variety of settings, especially integer lattices \cite{Auffinger_Damron_Hanson_2015}. The quantity $W_G(u,v)$ may be interpreted as the \emph{first passage time} from $u$ to $v$, when the link weights are considered as transmission times. A relevant quantity of interest in modern social and information networks is the \emph{flooding time} $\max_v W_G(u, v)$, which corresponds to the time it takes for a message or disease to spread from a single root node $u$ to all other nodes along the paths of the graph. Alternatively, the link weights can be viewed as economic costs, congestion delays, or carrying capabilities that can be encountered in various real networks \cite{Newman_2010,VanMieghem_2014}.

In this paper we study a generalized version of the above setting where in addition to link weights, each node is assigned two weights $X_0(v) \ge 0$ and $X_1(v) \ge 0$, and we define
\[
 W(u,v)
 \weq X_0(u) + W_G(u,v) + X_1(v).
\]
When the weights are considered as transmission times, $W(u,v)$ can be interpreted as the first passage time from $u$ to $v$ in a setting where $X_0(u)$ represents the entry delay and $X_1(v)$ the exit delay along a path from $u$ to $v$ in a network modeled by the graph $G$. The above formulation can also corresponds a generalization of the SI epidemic model \cite{Andersson_Britton_2000} with incubation times by setting $X_0(v) = 0$ and letting $X_1(v)$ represent the length of the time period during which an infected individual $v$ spreads a disease while displaying no symptoms of illness. In this case $W_G(u,v)$ represents the time until node $v$ becomes infected, and $W(u,v)$ the time until node $v$ becomes acutely ill in a population where initially node $u$ is ill and all other nodes are susceptible.

The main result\cred{s} of the paper \cred{are} approximative formulas for $W(u,v)$, $\max_v W(u,v)$, and $\max_{u,v} W(u,v)$ in a large and sparse random graph $G$, when the link weights $(W(e))_{e \in E(G)}$ and the node weights $(X_0(v), X_1(v))_{v \in V(G)}$ are mutually independent collections of independent random numbers, such that $W(e)$ is exponentially distributed with rate parameter $\lambda > 0$, and the distribution of $X_i(v)$ has an exponential tail with rate parameter $\lambda_i \in (0,\infty]$ in the sense that
\begin{equation}
 \label{eq:ExpTail}
 \lim_{t \to \infty} \frac{-\log \pr(X_i(v) > t)}{t}
 \weq \lambda_i,
 \qquad i=0,1.
\end{equation}
The case $\lambda_i = \infty$ includes distributions with bounded support, for example the uniform distribution on $[0,1]$, and the degenerate case with $X_i(v)=0$ almost surely.  No restrictions about the joint distribution of $X_0(v)$ and $X_1(v)$ are required for the main results.

\paragraph{Notations.} A large network is modeled as a sequence of graphs indexed by a scale parameter $n=1,2,\dots$ Hence most scalars, probability distributions, and random variables depend on $n$, but this dependence is often omitted for clarity. Especially, we write $\pr$ instead of $\pr_n$ for the probability measure characterizing events related the model with scale parameter $n$. An event depending on $n$ is said to occur \emph{with high probability} if its probability tends to one as $n \to \infty$. The symbol $\prto$ refers to convergence in probability. We write $f(n) = o(g(n))$ if $\lim_{n \to \infty} f(n)/g(n) = 0$, and $f(n) = O(g(n))$ if $\limsup_{n \to \infty} f(n)/g(n) < \infty$. We write $X \eqd Y$ when random variables $X$ and $Y$ have the same distribution. \cred{The positive part of a number $x$ is denoted $(x)_{+} = \max\{x,0\}$.}

\section{Main results}
\label{sec:MainResults}
Given a list of nonnegative integers $d = (d_1, \dots, d_n)$, let $G = G(n,d)$ be a random graph, which is uniformly distributed in the set $\cG(n,d)$ of all undirected graphs on node set $[n] = \{1,\dots,n\}$ such that node $v$ has degree $d_v$ for all $v$. We assume that the degree list $d$ satisfies the \Erdos--Gallai condition \cite[Theorem C.7]{Marshall_Olkin_Arnold_2011}, so that $\cG(n,d)$ is nonempty. A stochastic model for a sparse large graph is obtained by considering a sequence of random graphs $G = \cG(n,d^{(n)})$ with degree lists $d^{(n)} = (d_1^{(n)}, \dots, d^{(n)}_n)$ indexed by $n=1,2,\dots$ such that the empirical degree distribution
\[
 f_n(k)
 \weq \frac{1}{n} \sum_{v=1}^n 1(d^{(n)}_v = k)
\]
converges to a limiting probability distribution $f$ with a nonzero finite mean $\mu = \sum_k k f(k)$ according to
\begin{equation}
 \label{eq:DegreeLim}
 f_n(k) \ \to \ f(k)
 \quad \text{for all $k \ge 0$}.
\end{equation}
Throughout we will also assume that for all $n$,
\begin{equation}
 \label{eq:DegreeVariance}
 \sum_k k^{2+\epsilon} f_n(k)
 \wle c
\end{equation}
and
\begin{equation}
 \label{eq:DegreeMinMax}
 \min_v d^{(n)}_v
 \wge \delta
\end{equation}
for some constants $c, \epsilon > 0$ and $\delta \ge 3$ such that $f(\delta) > 0$. Condition~\eqref{eq:DegreeVariance} implies that the family of probability measures $(f_n)_{n \ge 1}$ is relatively compact in the 2-Wasserstein topology \cite{Leskela_Vihola_2013} and guarantees that the mean and the variance of the empirical degree distribution converge to finite values which are equal to the mean and variance of the limiting distribution. Condition~\eqref{eq:DegreeMinMax} in turn implies that $G$ is connected with high probability \cite{Amini_Draief_Lelarge_2013,VanDerHofstad_2018}.

The following theorem summarizes the main results of the paper. Here $u^*$ and $v^*$ represent uniformly and independently randomly chosen nodes, corresponding to typical values of the quantities of interest.

\begin{theorem}
\label{the:DelayedFloodingTime}
Let $G = G(n,d^{(n)})$ be a random graph satisfying the regularity conditions \eqref{eq:DegreeLim}--\eqref{eq:DegreeMinMax}. Then for independent and uniformly random nodes $u^*$ and $v^*$,
\begin{align}
 \label{eq:DelayedPassageTypical}
 \frac{W(u^*,v^*)}{\log n}
 &\wprto \frac{1}{\lambda(\nu-1)}, \\
 \label{eq:DelayedFloodingTypical}
 \frac{\max_v W(u^*,v)}{\log n}
 &\wprto \frac{1}{\lambda(\nu-1)} + \frac{1}{\lambda \delta \wedge \lambda_1}, \\
 \label{eq:DelayedFloodingMax}
 \frac{\max_{u,v} W(u,v)}{\log n}
 &\wprto \frac{1}{\lambda \delta \wedge \lambda_0} + \frac{1}{\lambda(\nu-1)} + \frac{1}{\lambda \delta \wedge \lambda_1},
\end{align}
where $\nu = \sum_k k(k-1) f(k) / \sum_k k f(k)$.
\end{theorem}

\section{Discussion and applications}

\subsection{Earlier work}
The results of Section~\ref{sec:MainResults} are structurally similar to the main result in \cite{Janson_1999} which states that for the complete graph $K=K_n$ on $n$ nodes, the weighted distances (without boundary weights) satisfy
\begin{align}
 \label{eq:UndelayedPassageTypicalK}
 \frac{ W_K(u^*,v^*)}{\log n / n}
 &\wprto \frac{1}{\lambda}, \\
 \label{eq:UndelayedFloodingTypicalK}
 \frac{\max_v W_K(u^*,v)}{\log n / n}
 &\wprto \frac{2}{\lambda}, \\
 \label{eq:UndelayedFloodingMaxK}
 \frac{\max_{u,v} W_K(u,v)}{\log n / n}
 &\wprto \frac{3}{\lambda}.
\end{align}
The above results have more recently been extended to sparse random graphs. For a random graph $G = G(n,d^{(n)})$ satisfying the regularity conditions \eqref{eq:DegreeLim}--\eqref{eq:DegreeMinMax}, the weighted distances (without boundary weights) satisfy
\begin{align}
 \label{eq:UndelayedPassageTypical}
 \frac{W_G(u^*,v^*)}{\log n}
 &\wprto \frac{1}{\lambda(\nu-1)}, \\
 \label{eq:UndelayedFloodingTypical}
 \frac{\max_v W_G(u^*,v)}{\log n}
 &\wprto \frac{1}{\lambda(\nu-1)} + \frac{1}{\lambda \delta}, \\
 \label{eq:UndelayedFloodingMax}
 \frac{\max_{u,v} W_G(u,v)}{\log n}
 &\wprto \frac{1}{\lambda(\nu-1)} + \frac{2}{\lambda \delta }.
\end{align}
Formulas \eqref{eq:UndelayedPassageTypical}--\eqref{eq:UndelayedFloodingMax} agree with \eqref{eq:UndelayedPassageTypicalK}--\eqref{eq:UndelayedFloodingMaxK} because $\nu \approx n$ and $\delta \approx n$ for the complete graph on $n$ nodes. Formula \eqref{eq:UndelayedPassageTypical} was proved in \cite{Ding_Kim_Lubetzky_Peres_2010} for degenerate degree distributions (random regular graph),  in~\cite{Bhamidi_VanDerHofstad_Hooghiemstra_2010} for power-law degree distributions (when $\tau\in (2,3)$), and in \cite{Amini_Draief_Lelarge_2013} for general limiting degree distributions with a finite variance. Formulas \eqref{eq:UndelayedFloodingTypical}--\eqref{eq:UndelayedFloodingMax} have been proved in \cite{Ding_Kim_Lubetzky_Peres_2010} for random regular graphs and in \cite{Amini_Draief_Lelarge_2013,Amini_Lelarge_2015} for general limiting degree distributions with a finite variance. Sparse random graphs where the limiting degree distribution has infinite variance have in general a completely different behavior with typical passage times of order $o(\log n)$ \cite{Baroni_VanDerHofstad_Komjathy_2017,Bhamidi_VanDerHofstad_Hooghiemstra_2010} and they are not discussed further in this paper. The constant $\nu$ appearing in the above formulas can be recognized as the mean of the downshifted size biasing \cite{Leskela_Ngo_2017} of the limiting degree distribution $f$, and $\nu$ is finite if and only if the second moment of $f$ is finite.

Theorem~\ref{the:DelayedFloodingTime} generalizes formulas \eqref{eq:UndelayedPassageTypical}--\eqref{eq:UndelayedFloodingMax} to the setting where nodes have nonnegative random weights $X_0(v)$ and $X_1(v)$ with exponential tail. The main qualitative findings are that the boundary weights have no effect on the typical passage time $W(u^*, v^*)$, but they may affect the typical flooding time $\max_v W(u^*,v)$ and the maximum flooding time $\max_{u,v} W(u,v)$. \cred{All boundary weight effects can be ignored on the $\log n$ time scale when the tails of the node weight distributions decay sufficiently fast $(\lambda_0,\lambda_1 > \lambda\delta)$.}

A notable feature of the results in Theorem~\ref{the:DelayedFloodingTime} is that the leading role of the node weight distributions is the behavior of $\pr(X_i(v) > t)$ as $t \to \infty$, whereas the leading role of link weight distribution is in many cases \cite{Baroni_VanDerHofstad_Komjathy_2017,Janson_1999} governed by the behavior of $\pr( W(e) > t )$ as $t \to 0$.

\cred{
\begin{remark}
The distribution of the node weight $X_i(v)$ is heavy-tailed if the limit in \eqref{eq:ExpTail} is zero. For heavy-tailed node weight distributions, it is easy to check that $\max_{u\in V}X_i(u)$ grows to infinity faster than logarithmically. Hence Theorem \ref{the:DelayedFloodingTime} remains formally valid also when $\lambda_0 = 0$ or $\lambda_1 = 0$, using the convention that $\frac{1}{0} = \infty$.
\end{remark}
}

\subsection{Application: Broadcasting on random regular graphs}

As an application, we discuss a continuous-time version of a message transmission and replication model operating in a \emph{push} mode \cite{Aalto_Leskela_2015,Amini_Draief_Lelarge_2013,Pittel_1987}. Let $G$ be a random $\delta$-regular graph on $n$ nodes, where each node has a state in $\{0,1,2\}$.
Initially one of the nodes called \emph{root} is in state 1, and all other nodes are in state 0.  Each node activates at random time instants according to a Poisson process of rate $\kappa > 0$, independently of other nodes and the underlying graph structure. When a node activates, it contacts a random target among its neighbors. The states of the nodes are updated in two ways:
\begin{itemize}
\item $0 \mapsto 1$: If the initiator of a contact is in state 1 or 2, and the target node is in state 0, then the state of the target node changes from 0 to 1; otherwise nothing happens during the contact.
\item $1 \mapsto 2$: Having entered state 1, node $v$ remains in this state for a random time period of length $X_1(v)$, and then the state of node $v$ changes into~2.
\end{itemize}
We can interpret the model in the context of computer or biological viruses as follows: State 0 refers to nodes which are vulnerable of receiving a virus. State~1 refers to nodes carrying and spreading the virus but displaying no symptoms. State~2 refers to nodes carrying and spreading the virus and displaying symptoms. We denote by $\flood_1(G)$ the time until every node in the graph has received the virus, and by $\flood_2(G)$ the time until every node displays symptoms.

The above model can be analyzed using the weighted random graph where all links have a random exponentially distributed weight of rate parameter $\lambda = \kappa/\delta$ with $X_0(v) = 0$, and $X_1(v)$ modeling the delay until an infected node displays symptoms.
Then for a random root node $u^*$,
\begin{align*}
 \flood_1(G)
 &\weqd \max_v W_G(u^*,v), \\
 \flood_2(G)
 &\weqd \max_v \Big( W_G(u^*,v) + X_1(v) \Big).
\end{align*}
\cred{
Applying formula \eqref{eq:DelayedFloodingTypical} in Theorem~\ref{the:DelayedFloodingTime} with $\lambda_1 = \infty$ corresponding to $X_{1}(v) = 0$, we have \whp,
\begin{align}
\label{eq:flood1}
 \flood_1(G)
 &\weq \left(\frac{1}{\lambda(\nu-1)} + \frac{1}{\lambda\delta}\right) \log n + o(\log n).
\end{align}
Note that the same formula can also be obtained from \eqref{eq:UndelayedFloodingTypical}. Applying \eqref{eq:DelayedFloodingTypical} again, we have \whp,
\begin{align}
 \label{eq:flood2}
 \flood_2(G)
 &\weq \left(\frac{1}{\lambda(\nu-1)} + \frac{1}{\lambda\delta\wedge\lambda_1}\right) \log n + o(\log n).
\end{align}
These two formulas lead to the following results.
}
\begin{corollary}
\label{the:Broadcasting}
For a random $\delta$-regular graph $G$ on $n$ nodes with $\delta \ge 3$, when the distribution of $X_1(v)$ has an exponential tail of rate $\lambda_1$ according to \eqref{eq:ExpTail},
\[
 \flood_1(G)
 \weq \frac{2}{\kappa} \left( \frac{\delta-1}{\delta-2} \right) \log n + o(\log n)
\]
and
\[
 \flood_2(G)
 \weq \left( \frac{\delta}{\kappa(\delta-2)} + \frac{1}{\kappa \wedge \lambda_1} \right) \log n + o(\log n)
\]
with high probability as $n \to \infty$.
\end{corollary}
\cred{
\begin{proof}
The results follow directly by substituting $\lambda = \delta/ \kappa$ and $\nu = \delta -1$ into \eqref{eq:flood1} and \eqref{eq:flood2}. The coefficient in \eqref{eq:flood1} simplifies by direct calculation into
\begin{align*}
 \frac{1}{\lambda(\nu-1)} + \frac{1}{\lambda\delta} = \frac{\delta}{\kappa(\delta-2)}+ \frac{1}{\kappa}  = \frac{2}{\kappa}\left(\frac{\delta-1}{\delta-2}\right).
\end{align*}
\end{proof}
}
\begin{figure}[h]
\centering
\includegraphics{FloodingTimes.eps}
\caption{\label{fig:FloodingTimes} Flooding times on random $\delta$-regular graphs with $\delta = 3$, $\kappa = 1$, and $\lambda_1=1/2$. Blue circles represent simulated values of $\flood_1(G)$. Red triangles represent simulated values of $\flood_2(G)$. The blue solid line and the red dashed line correspond to the limiting formulas of Corollary~\ref{the:Broadcasting}. (Color online.)}
\end{figure}

Figure~\ref{fig:FloodingTimes} illustrates how the limiting approximations of Corollary~\ref{the:Broadcasting} relate to simulated values of the flooding times on 3-regular graphs. The sizes of the fluctuations around the theoretical values appear to be of constant order with respect to $n$. A constant order of fluctuations corresponds to the well-known fact in statistical extreme value theory that the maximum of $n$ independent exponential random numbers is approximately Gumbel-distributed around a value of size $\log n$. However, the additional randomness induced by the underlying random graph may cause the fluctuations to grow slowly with respect to $n$. Whether or not the fluctuations grow with $n$ is not possible to detect from simulations of modest size, because the growth rate of the fluctuations is at most $o(\log n)$.

Figure~\ref{fig:FloodingDynamics} describes simulated trajectories of node counts in different states in a random 3-regular graph of 1000 nodes. The trajectories are approximately S-shaped, with random horizontal shifts caused by the initial and final phases of the process.

\begin{figure}[h]
\centering
\includegraphics{FloodingDynamics.eps}
\caption{\label{fig:FloodingDynamics} Simulated trajectories of the number of nodes in state~1 or state~2 (blue, solid) and the number of nodes in state 2 (red, dashed) for a random $\delta$-regular graph with $n=1000$, $\delta = 3$, $\kappa = 1$, and $\lambda_1=1/2$. (Color online.)}
\end{figure}

\section{Proofs}
\label{Proof of the main result}

\subsection{Configuration model}

A standard method for studying the random graph $G = G(n, d^{(n)})$ is to investigate a related random multigraph. A \emph{multigraph} is a triplet $G = (V, E, \phi)$, where $V$ and $E$ are finite sets and $\phi: E \to \binom{V}{1} \cup \binom{V}{2}$. Here $\phi(e)$ refers to the set of one (loop) or two (non-loop) nodes incident to $e \in E$. A multigraph is called \emph{simple} if $\phi$ is one-to-one (no parallel links) and $\phi(E) \subset \binom{V}{2}$ (no loops). The degree of a node $i$ is defined by $\sum_{e \in E} \cred{\big(} 1( i \in \phi(e)) + 1( \{i\} = \phi(e) )\cred{\big)}$, that is, the number of links incident to $i$, with loops counted twice. A path of length $k \ge 0$ from $x_0$ to $x_k$ is a set of distinct nodes $\{x_0,x_1, \dots, x_k\}$ such that $\{x_{j-1}, x_j\} \in \phi(E)$ for all $j$. For a multigraph $G$ weighted by $W: E \to (0,\infty)$, we denote
\[
 W_G(u,v) \weq \inf_{\Gamma} \, \sum_{e \in \Gamma} W(e),
\]
where $\Gamma$ is the set of paths from $u$ to $v$. When $G$ is connected, the above formula defines a metric on $G$.

\cred{
Let us recall the usual definition of the configuration model in \cite{Bollobas_1980}. Let $n$ be a positive integer and $d = (d_1,d_2,...,d_n)$ be a sequence of nonnegative integers. For each node $i\in [n]$ we attach $d_i$ distinct elements called half-edges. A pair of half-edges is called an edge. To obtain a random multigraph $G^*$, it is required that the sum of half-edges $d = (d_1,d_2,...,d_n)$ is even $\sum_{i=1}^{n}d_i = 2m$, where $m$ refers to the number of edges. Let $D_i$ be the set of half-edges of node $i$. Then the size of the set $D_i$ is $d_i$ and the sets $D_1,D_2,...,D_n$ are disjoint. Let $D= \bigcup_{i= 1}^{n}D_i$ be the collection of all the half-edges and let $E$ be a pairing of $D$ (partition into $m$ pairs) selected uniformly at random. The configuration model $G^* = G^*(n, d)$ is the multigraph $([n],E, \phi)$, where the function $\phi:E\to \binom{n}{1}\cup\binom{n}{2}$ is defined by $\phi(e) = \{i \in [n]: D_i \cap e \ne \emptyset\}$.
}
A key feature of the configuration model is that the conditional distribution of $G^*(n,d)$ given that $G^*(n,d)$ is simple equals the distribution of the random graph $G(n, d)$. Moreover, for a sequence of degree lists $d^{(n)}$ satisfying the regularity conditions \eqref{eq:DegreeLim}--\eqref{eq:DegreeVariance}, the probability that $G^*(n, d^{(n)})$ is simple is bounded away from zero \cite{Janson_Luczak_2009}. Therefore, any statement concerning $G^*(n, d^{(n)})$ which holds with high probability, also holds for $G(n, d^{(n)})$ with high probability. This is why in the sequel, we write $G$ in place of $G^*$ and the analysis of weighted distances will be conducted on the configuration model.

\subsection{Notations}

For a node $u$ in the weighted multigraph, we denote by $B(u,t) = \{W_G(u,v) \le t\}$ the set of nodes within distance $t \in [0,\infty]$ from $u$. For an integer $k \ge 0$, we define
\[
 T_{u}(k)
 \weq \min\{t \ge 0: \abs{B(u,t)} \ge k+1\},
\]
with the convention that $\min \emptyset = \infty$. We also denote by $S_{u}(k)$ the number of outgoing links from set $B(u,T_{u}(k))$. Then for any $k$ less than the component size of $u$:
\begin{itemize}
\item $T_{u}(k)$ equals the distance from $u$ to its $k$-th nearest neighbor, and
\item $S_u(k)$ equals the number of outgoing links from the set of nodes consisting of $u$ and its $k$ nearest neighbors.
\end{itemize}
Moreover, $T_u(k) = \infty$ and $S_u(k) = 0$ for all $k$ greater or equal to the component size of $u$.

Throughout in the sequel, we assume that $G$ satisfies the regularity conditions \eqref{eq:DegreeLim}--\eqref{eq:DegreeMinMax}. We introduce the scale parameters
\begin{align*}
 \alpha_n &= \lfloor \log^3 n \rfloor,\\
 \beta_n &=\Big\lfloor 3\sqrt{\tfrac{\mu}{\nu-1}n\log n} \Big\rfloor
\end{align*}
and, with high probability, \cite[Proposition 4.2]{Amini_Draief_Lelarge_2013} (see alternatively \cite[Lemma 3.3]{Ding_Kim_Lubetzky_Peres_2010} or \cite[Proposition 4.9]{Bhamidi_VanDerHofstad_Hooghiemstra_2010})
\begin{equation}
 \label{eq:DistanceUpper}
 W_G(u,v)
 \wle T_{u}(\beta_n) + T_v(\beta_n)
\end{equation}
for all nodes $u$ and $v$ in the graph $G$. We will next analyze the behavior of $T_{u}(\beta_n)$ and $T_v(\beta_n)$ in typical (uniformly randomly chosen node) and extremal cases.

\subsection{Upper bound on weighted distances}

The following upper bound on the weighted distances is a sharpened version of \cite[Lemmas 4.7, 4.12]{Amini_Draief_Lelarge_2013}. Below we assume that $X \ge 0$ is an arbitrary random number and $u^*$ is a uniformly randomly chosen node, such that $X$, $u^*$, and the graph $G$ are mutually independent, and independent of the weights $(W(e))_{e \in E(G)}$, where weights $W(e)$ are exponentially distributed with rate $\lambda > 0$. We use $\cF_{S_{u^*}}$ to denote the sigma-algebra generated by $S_{u^*} = (S_{u^*}(0), \dots, S_{u^*}(n-1))$.

\begin{lemma}
\label{the:UpperBoundDistancesGen}
Fix integers $0 \le a < b < n$ and numbers $c_1, c_2 \ge 0$, and let $\cR$ be an $\cF_{S_{u^*}}$-measurable event on which $S_{u^*}(k) \ge c_1 + c_2 k$ for all $a \le k \le b-1$. \cred{For any $0 < \theta <  \lambda (c_1+c_2 a)$},
\begin{multline}
 \label{eq:UpperBoundDistancesZero}
 \cred{
 \E(e^{\theta (T_{u^*}(b) - T_{u^*}(a) + X)}\mid \cR)
 }\\
 \wle M_X(\theta) \exp \left( \frac{\theta}{\theta_1 - \theta}
 + \frac{\theta}{\theta_0} \left( \frac{1}{a+1} + \log \frac{b-1}{a+1} \right) \right),
\end{multline}
where $M_X(\theta) = \E e^{\theta X}$, $\theta_0 = \lambda c_2 - \frac{(\theta - \lambda c_1)_+}{a+1}$ and $\theta_1 = \lambda (c_1+c_2 a)$.
\end{lemma}
\begin{proof}
A key property of the model is that conditionally on $S_{u^*}$, the random numbers  $T_{u^*}(k+1) - T_{u^*}(k)$
are independent and exponentially distributed with rates $\lambda S_{u^*}(k)$.  On the event $\cR$, we see that $\lambda S_{u^*}(a) \ge \theta_1$, and for all $a+1 \le k \le b-1$,
\begin{align*}
 \lambda S_{u^*}(k) - \theta \wge \lambda c_1 + \lambda c_2 k - \theta  \wge \left( \lambda c_2 - \frac{(\theta - \lambda c_1)_+}{k} \right) k \wge \theta_0 k.
\end{align*}
\cred{As a consequence,}
\begin{align*}
 \E(e^{\theta (T_{u^*}(b) - T_{u^*}(a) + X)}\mid \cred{\cF_{S_{u^*}}})
 &\weq M_X(\theta) \prod_{k=a}^{b-1} \frac{\lambda S_{u^*}(k)}{\lambda S_{u^*}(k) - \theta} \\
 &\weq M_X(\theta)
 \prod_{k=a}^{b-1} \left( 1 + \frac{\theta}{\lambda S_{u^*}(k) - \theta} \right) \\
 &\wle M_X(\theta)
 \exp \left( \sum_{k=a}^{b-1} \frac{\theta}{\lambda S_{u^*}(k) - \theta} \right).
\end{align*}
\cred{Separating the first term from the sum and by the choice of the event $\cR$, we obtain
\begin{align*}
 \E(e^{\theta (T_{u^*}(b) - T_{u^*}(a) + X)}\mid \cR)
 &\wle M_X(\theta)
 \exp \left( \frac{\theta}{\theta_1 - \theta} + \frac{\theta}{\theta_0} \sum_{k=a+1}^{b-1} \frac{1}{k} \right).
\end{align*}
By integration we have $\sum_{k = m}^{n}\frac{1}{k}\le \log(\frac{n}{m-1})$ for any integers $2\le m<n$. Hence, separating the first term again from the sum, we have the desired result,
\begin{align*}
 \E(e^{\theta (T_{u^*}(b) - T_{u^*}(a) + X)}\mid \cR)
 &\wle M_X(\theta)
 \exp \left( \frac{\theta}{\theta_1 - \theta} + \frac{\theta}{\theta_0} \left( \frac{1}{a+1} + \log \frac{b-1}{a+1} \right) \right).
\end{align*}
}
\end{proof}

\subsection{Upper bounds on nearest neighbor distances}

\begin{proposition}
\label{the:InitialGrowth}
For any $0 \le p \le 1$ and $\epsilon > 0$, any random variable $X \ge 0$ independent of $G$,
\begin{align*}
 \pr\left( T_{u^*}(\alpha_n) + X > \Big( \frac{p}{\lambda \delta \wedge \theta^*} + \epsilon \Big) \log n \right)
 \weq o(n^{-p}),
\end{align*}
where $\theta^* = \sup\{ \theta \ge 0: \E e^{\theta X} < \infty\} > 0$.
\end{proposition}
\begin{proof}
Let $t_n = (\frac{p}{\lambda \delta \wedge \theta^*} + \epsilon ) \log n$. An upper bound for the event under study $\cA_n = \{T_{u^*}(\alpha_n) + X > t_n\}$ is obtained by
\begin{equation}
\label{eq:UpperSplit}
\begin{aligned}
 \pr\left( \cA_n \right)
 &\wle \cred{\pr(\cA_n\mid\cR_1)} + \cred{\pr(\cA_n\mid\cR_2\cap\cR_1^c)} \, \pr(\cR_1^c) + \pr(\cR_2^c),
\end{aligned}
\end{equation}
where
\begin{align*}
 \cR_1 &\weq \left\{ S_{u^*}(k) \ge \delta + (\delta-2)k \quad \text{for all $0 \le k \le \alpha_n -1$} \right\}, \\
 \cR_2 &\weq \left\{ S_{u^*}(k) \ge 1 + (\delta-2)k \quad \text{for all $0 \le k \le \alpha_n -1$} \right\}.
\end{align*}
\if
fa
\cred{
In these both events we require that, whenever a new nearest neighbor of $u^*$ is found, at least $\delta-2$ new outgoing half-edges are reached. Event $\cR_1$ holds when each outgoing half-edge leads to a new nearest neighbor of $u^*$ until the last $(\alpha_n-1)$ new nearest neighbor is found. While, event $\cR_2$ occurs when at most $\delta-1$ half-edges does not lead to a new nearest neighbor of $u^*$ for each step $0\le k \le \alpha_n -1$.
}
\fi
We will next analyze the conditional probabilities in \eqref{eq:UpperSplit}.

(i) To obtain an upper bound of $\cred{\pr(\cA_n\mid\cR_1)}$, by applying Lemma~\ref{the:UpperBoundDistancesGen} with $a=0$, $b = \alpha_n$, $c_1= \delta$, and $c_2 = \delta-2$ and  Markov's inequality, we find that
\[
 \cred{\pr(\cA_n\mid\cR_1)}
 \wle M_X(\theta) \exp \left( \frac{\theta}{\theta_1 - \theta}
 + \frac{\theta}{\theta_0} \left( 1 + \log \alpha_n \right) - \theta t_n \right) \\
\]
for all $0 < \theta < \theta_1 \wedge \theta^*$\cred{
, where $\theta_0 = \lambda (\delta-2)$ and $\theta_1 =\lambda\delta$
}. Now we may choose
\cred{
$\theta\ge (1-\frac{\lambda\delta\wedge\theta^{*}}{2(p+\epsilon(\lambda\delta\wedge\theta^{*}))}\epsilon)(\lambda\delta\wedge\theta^{*})$
to have} $\theta t_n \ge (p + \frac12 \epsilon (\theta_1 \wedge \theta^*))\log n$.
\cred{Note that $\theta$ can be arbitrary close to its maximum value $\lambda\delta\wedge\theta^{*}$ if we choose $\epsilon>0$ to be sufficiently small.
Since the constant term $\frac{\theta}{\theta_1-\theta}$ is negligibly small compared to $\log\alpha_n = \Theta(\log\log n)$, we have for large values of $n$,
}
\[
 \frac{\theta}{\theta_1 - \theta}
 + \frac{\theta}{\theta_0} \left( 1 + \log \alpha_n \right)
 \wle \frac14 \epsilon (\theta_1 \wedge \theta^*) \log n.
\]
\cred{
These two inequalities imply that
}
\begin{equation}
\label{eq:UpperSplit1}
 \cred{\pr(\cA_n\mid\cR_1)}
 \wle M_X(\theta) n^{-(p+\frac14 \epsilon (\lambda \delta \wedge \theta^*))}
 \weq o(n^{-p}).
\end{equation}

(ii) For an upper bound of $\pr_{\cR_2 \setminus \cR_1}( \cA_n)$,
we apply Lemma~\ref{the:UpperBoundDistancesGen} with $a=0$, $b = \alpha_n$, $c_1= 1$, and $c_2 = \delta-2$ and Markov's inequality to conclude that
\[
 \cred{\pr(\cA_n\mid\cR_2\cap\cR_1^c)}
 \wle M_X(\theta) \exp \left( \frac{\theta}{\lambda - \theta}
 + \frac{\theta}{\lambda (\delta-2)} \left( 1 + \log \alpha_n \right) - \theta t_n \right)
\]
for all $0 < \theta < \lambda \wedge \theta^*$. For any such $\theta$, we see that
$
 \theta t_n \ge \epsilon_1 \log n
$
with $\epsilon_1 = \theta (\frac{p}{\lambda \delta \wedge \theta^*} + \epsilon ) > 0$.
Because
\[
 \frac{\theta}{\lambda - \theta}
 + \frac{\theta}{\lambda (\delta-2)} \left( 1 + \log \alpha_n \right)
 \wle \frac12 \epsilon_1 \log n
\]
for all large $n$, it follows that
\begin{equation}
\label{eq:UpperSplit2}
 \cred{\pr(\cA_n\mid\cR_2\cap\cR_1^c)}
 \weq O(n^{- \epsilon_1/2}).
\end{equation}

\cred{
Note that our $S_u(k)$ has the same distribution as the exploration process in \text{Section $4.1$} in \cite{Amini_Draief_Lelarge_2013}. Hence}
 by \cite[Lemma 4.6]{Amini_Draief_Lelarge_2013}, $\pr\cred{(\cR_1^c)} = o(n^{-1} \log^{10} n)$ and $\pr\cred{(\cR_2^c)} = o(n^{-3/2})$. Hence by substituting the bounds \eqref{eq:UpperSplit1} and \eqref{eq:UpperSplit2} into \eqref{eq:UpperSplit} it follows that
\[
 \pr\left( \cA_n \right)
 \wle o(n^{-p}) + O(n^{- \epsilon_1/2})  o(n^{-1} \log^{10} n) + o(n^{-3/2})
 \weq o(n^{-p}).
\]
\end{proof}

\subsection{Upper bounds on moderate distances}

\begin{proposition}
\label{the:ModerateGrowth}
For any $\epsilon > 0$,
\begin{align*}
 \pr\left(T_{u^*}(\beta_n) - T_{u^*}(\alpha_n) > (\frac{1}{2\lambda(\nu-1)}+\epsilon)\log n \right)
 \weq o(n^{-1}).
\end{align*}
\end{proposition}
\begin{proof}
Denote $c = \frac{1}{2\lambda(\nu-1)}$ and  $t_n = (c + \epsilon) \log n$. Set $c_1=0$ and $c_2 = 1/\lambda c$. Fix a number $\theta > \frac{2}{\epsilon}$, and set $\theta_0 = \lambda c_2 - \frac{\theta}{\alpha_n+1}$ and $\theta_1 = \lambda c_2 \alpha_n$. Then for all sufficiently large values of $n$, we see that $0 < \theta < \theta_1$. When we apply Lemma~\ref{the:UpperBoundDistancesGen} with $X=0$, $a = \alpha_n$, and $b = \beta_n$ and Markov's inequality, we find that on the event $\cR_3$ that $S_{u^*}(k) \ge c_2 k$ for all $\alpha_n \le k \le \beta_n -1$,
\begin{align*}
 &\cred{\pr(T_{u^*}(\beta_n) - T_{u^*}(\alpha_n) > t_n\mid \cR_3)} \\
 &\wle \exp \left( \frac{\theta}{\theta_1 - \theta}
 + \frac{\theta}{\theta_0} \left( \frac{1}{\alpha_n} + \log \frac{\beta_n}{\alpha_n} \right) - \theta t_n \right) \\
 &\weq \exp \left( \frac{\theta}{\lambda c_2 \alpha_n - \theta}
 + \frac{\theta}{\lambda c_2 - \frac{\theta}{\alpha_n+1}} \left( \frac{1}{\alpha_n} + \log \frac{\beta_n}{\alpha_n} \right)
 - (c + \epsilon)\theta \log n \right).
\end{align*}
Note that $\beta_n/\alpha_n \wle n$. Because $\alpha_n \to \infty$, we see that
\begin{align*}
\cred{\pr(T_{u^*}(\beta_n) - T_{u^*}(\alpha_n) > t_n\mid \cR_3)} &\wle \exp \Big(
 (c + \epsilon/2) \theta \log n
 - (c + \epsilon)\theta \log n\Big)\\
 &\weq \exp \left(-\frac{\epsilon}{2}\theta \log n \right).
\end{align*}
Due to our choice of $\theta$, the right side is $o(n^{-1})$. The claim follows from this because $\pr(\cR_3^c) =  o(n^{-3/2})$ by \cite[Lemma 4.9]{Amini_Draief_Lelarge_2013}.
\end{proof}

\subsection{Proof Theorem~\ref{the:DelayedFloodingTime}: Upper bounds}
\label{Proof of the upper bound}

Observe that $\E e^{\theta X_i(v)}$ is finite for $\theta < \lambda_i$ and infinite for $\theta > \lambda_i$ due to our assumption on exponential tails \eqref{eq:ExpTail}.  Hence by applying Proposition~\ref{the:InitialGrowth} with $p=1$,
\begin{align*}
 \pr\left( T_{v^*}(\alpha_n) + X_i(v^*) > \left( \frac{1}{\lambda \delta \wedge \lambda_i} +\epsilon \right) \log n \right)
 \weq o(n^{-1}),
\end{align*}
so that by applying the generic union bound
\begin{equation}
 \label{eq:GenericUnion}
 \pr( \max_v X(v) > t )
 \wle \sum_v \pr(X(v) > t)
 \weq n \pr(X(v^*) > t)
\end{equation}
it follows that
\begin{equation}
 \label{eq:UpperFirst}
 \max_v (T_v(\alpha_n) + X_i(v))
 \wle \left( \frac{1}{\lambda \delta \wedge \lambda_i} +\epsilon \right) \log n
 \qquad \whp
\end{equation}
Furthermore, by applying Proposition~\ref{the:InitialGrowth} with $p=0$, it follows that
\begin{equation}
 \label{eq:UpperSecond}
 T_{v^*}(\alpha_n)
 \wle T_{v^*}(\alpha_n) + X_i(v^*)
 \wle \epsilon \log n
 \qquad \whp,
\end{equation}
and by Proposition~\ref{the:ModerateGrowth} and the generic union bound \eqref{eq:GenericUnion}, \whp,
\begin{equation}
 \label{eq:UpperThird}
 T_{v^*}(\beta_n) - T_{v^*}(\alpha_n)
 \wle \max_v \Big( T_v(\beta_n) - T_v(\alpha_n) \Big)
 \wle \left( \frac{1}{2\lambda(\nu-1)} + \epsilon \right) \log n
\end{equation}
By combining \eqref{eq:UpperFirst} and \eqref{eq:UpperSecond} with \eqref{eq:UpperThird}, we conclude that \whp,
\begin{equation}
 \label{eq:MaxBetaUB}
 \max_v (T_v(\beta_n) + X_i(v))
 \wle \left( \frac{1}{\lambda \delta \wedge \lambda_i} + \frac{1}{2\lambda(\nu-1)} + 2 \epsilon \right) \log n
\end{equation}
and
\begin{equation}
 \label{eq:AvgBetaUB}
 T_{v^*}(\beta_n)
 \wle \left( \frac{1}{2\lambda(\nu-1)} + 2\epsilon \right) \log n.
\end{equation}

To prove an upper bound for \eqref{eq:DelayedPassageTypical}, observe that the distribution of $X_i(v^*)$ does not depend on the scale parameter $n$. Therefore, $X_i(v^*) \le \epsilon \log n$ with high probability. In light of \eqref{eq:DistanceUpper} and \eqref{eq:AvgBetaUB}, it follows that, \whp,
\begin{align*}
 W(u^*, v^*)
 &\weq X_0(u^*) + W_G(u^*, v^*) + X_1(v^*) \\
 &\wle X_0(u^*) + T_{u^*}(\beta_n) + T_{v^*}(\beta_n) + X_1(v^*) \\
 &\wle \left( \frac{1}{\lambda(\nu-1)} \log n + 6 \epsilon \right) \log n.
\end{align*}

To prove an upper bound for \eqref{eq:DelayedFloodingTypical}, observe that by applying \eqref{eq:DistanceUpper}, \eqref{eq:MaxBetaUB} and \eqref{eq:AvgBetaUB}, with high probability,
\begin{align*}
 \max_{v} W(u^*, v)
 &\weq \max_{v} \Big( X_0(u^*) + W_G(u^*, v) + X_1(v) \Big) \\
 &\wle \max_{v} \Big( X_0(u^*) + T_{u^*}(\beta_n) + T_v(\beta_n) + X_1(v) \Big) \\
 &\weq X_0(u^*) + T_{u^*}(\beta_n) + \max_{v} \Big( T_v(\beta_n + X_1(v)) \Big) \\
 &\wle \left( \frac{1}{2\lambda(\nu-1)} + 3 \epsilon \right) \log n
  + \left( \frac{1}{\lambda \delta \wedge \lambda_1} + \frac{1}{2\lambda(\nu-1)} + 2 \epsilon \right) \log n \\
 &\weq \left( \frac{1}{\lambda \delta \wedge \lambda_1} + \frac{1}{\lambda(\nu-1)} + 5 \epsilon \right) \log n.
\end{align*}

Finally, for an upper bound for \eqref{eq:DelayedFloodingMax}, observe that by \eqref{eq:DistanceUpper}, with high probability,
\begin{align*}
 \max_{u,v} W(u, v)
 &\weq \max_{u,v} \Big( X_0(u) + W_G(u, v) + X_1(v) \Big) \\
 &\wle \max_{u,v} \Big( X_0(u) + T_{u}(\beta_n) + T_v(\beta_n) + X_1(v) \Big) \\
 &\weq \max_u \Big( X_0(u) + T_u(\beta_n) \Big) + \max_v \Big( X_1(v) + T_v(\beta_n) \Big).
\end{align*}
And hence by \eqref{eq:MaxBetaUB}, it follows that, with high probability,
\begin{align*}
 \max_{u,v} W(u, v)
 &\wle \left( \frac{1}{\lambda \delta \wedge \lambda_0} + \frac{1}{\lambda (\nu-1)} + \frac{1}{\lambda \delta \wedge \lambda_1}  + 4 \epsilon \right) \log n.
\end{align*}
The above inequalities are sufficient to confirm the upper bounds in Theorem~\ref{the:DelayedFloodingTime} because $\epsilon > 0$ can be chosen arbitrarily small.

\subsection{Proof Theorem~\ref{the:DelayedFloodingTime}: Lower bounds}
\label{Proof of the lower bound}
The lower bounds are relatively straightforward generalizations of analogous results \eqref{eq:UndelayedPassageTypical}--\eqref{eq:UndelayedFloodingMax} for the model without node weights, which imply that for an arbitrarily small $\epsilon > 0$, the weighted graph distance $W_G$ satisfies \whp,
\begin{align}
 \label{eq:PassageTypical}
 \frac{W_G(u^*,v^*)}{\log n}
 &\wge \frac{1}{\lambda(\nu-1)} - \epsilon \\
 \label{eq:FloodingTypical}
 \frac{\max_v W_G(u^*,v)}{\log n}
 &\wge \frac{1}{\lambda(\nu-1)} + \frac{1}{\lambda \delta} - \epsilon \\
 \label{eq:FloodingMax}
 \frac{\max_{u,v} W_G(u,v)}{\log n}
 &\wge \frac{1}{\lambda(\nu-1)} + \frac{2}{\lambda \delta} - \epsilon.
\end{align}
\cred{
We first prove the following lemma and we apply it later in the proof of the lower bounds.
}
\begin{lemma}
\label{the:MaxSumLB}
For every integer $n \ge 1$, let $A_n(i)$ and $B_n(i)$ be random numbers indexed by a finite set $i \in I_n$. Assume that
$(A_n(i))_{i \in I_n}$ are independent and identically distributed, and
\[
 \abs{I_n} \, \pr(A_n(i) > a_n)
 \ \to \ \infty,
\]
and that $B_n(i^*) > b_n$ with high probability, where $i^*$ is a uniformly random point of $I_n$, independent of $(B_n(i))_{i \in I_n}$. Assume also that $A_n(i)$ and $B_n(i)$ are independent for every $i \in I_n$. Then
\[
 \max_{i \in I_n} \left( A_n(i) + B_n(i) \right)
 \ > \ a_n + b_n
\]
with high probability.
\end{lemma}
\begin{proof}
Let
\[
 M_n
 \weq \abs{\{ i \in I_n: A_n(i) > a_n \}}
\]
and
\[
 N_n
 \weq \abs{\{ i \in I_n: A_n(i) > a_n, \, A_n(i) + B_n(i) > a_n + b_n \}}.
\]
Observe that $M_n$ is binomially distributed with $\abs{I_n}$ trials and rate parameter $p_n = \pr(A_n(i) > a_n)$.
Then $\E M_n = \abs{I_n} p_n$ and $\Var(M_n) \le \E M_n$, and because $\abs{I_n} p_n \to \infty$, it follows that $M_n \ge \frac12 \abs{I_n} p_n$ with high probability. Moreover,
\begin{align*}
 \E (M_n - N_n)
 &\weq \sum_{i \in I_n} \pr \left( A_n(i) > a_n, \, A_n(i) + B_n(i) \le a_n + b_n \right) \\
 &\wle \sum_{i \in I_n} \pr \left( A_n(i) > a_n, \, B_n(i) \le b_n \right) \\
 &\weq \sum_{i \in I_n} \pr ( A_n(i) > a_n ) \pr  (B_n(i) \le b_n ) \\
 &\weq \abs{I_n} p_{n} \, \pr( B_n(i^*) \le b_n ).
\end{align*}
Because $\pr( B_n(i^*) \le b_n ) = o(1)$, Markov's inequality implies that $M_n - N_n \le \frac14 \abs{I_n} p_n$ with high probability. We conclude that, with high probability,
\[
 N_n
 \weq M_n - (M_n-N_n)
 \wge \frac12 \abs{I_n} p_n - \frac14 \abs{I_n} p_n
 \weq \frac14 \abs{I_n} p_n
 \wge 1,
\]
and $\max_{i \in I_n} (A_n(i) + B_n(i)) > a_n + b_n$.
\end{proof}

(i) A suitable lower bound for \eqref{eq:DelayedPassageTypical} follows immediately from \eqref{eq:PassageTypical} because $W(u^*, v^*) \ge W_G(u^*, v^*)$ almost surely.

(ii) To prove a lower bound for \eqref{eq:DelayedFloodingTypical}, note that the exponential tail assumption \eqref{eq:ExpTail} implies that
\[
 n \, \pr \left( X_1(v) > \big( \frac{1}{\lambda_1} - \epsilon \big) \log n \right)
 \ \to \ \infty.
\]
Then by applying Lemma~\ref{the:MaxSumLB} (with $A_n(v) = X_1(v)$, $B_n(v) = W_G(u^*,v)$, and $I_n = [n]$), recalling \eqref{eq:PassageTypical}, we find that, \whp,
\begin{equation}
\label{eq:FloodingTypicalLB}
\begin{aligned}
 \max_v W(u^*,v)
 &\weq \max_v \Big( X_0(u^*) + W_G(u^*, v) + X_1(v) \Big) \\
 &\wge \max_v \Big( W_G(u^*, v) + X_1(v) \Big) \\
 &\wge \left( \frac{1}{\lambda(\nu-1)} + \frac{1}{\lambda_1} - 2\epsilon \right) \log n.
\end{aligned}
\end{equation}
By noting that $\max_v W(u^*,v) \ge \max_v W_G(u^*, v)$ and applying \eqref{eq:FloodingTypical}, we also obtain
\[
 \max_v W(u^*,v)
 \wge \left( \frac{1}{\lambda(\nu-1)} + \frac{1}{\lambda \delta} - 2\epsilon \right) \log n,
\]
and hence \whp,
\[
 \max_v W(u^*,v)
 \wge \left( \frac{1}{\lambda(\nu-1)} + \frac{1}{\lambda \delta \wedge \lambda_1} - 2\epsilon \right) \log n.
\]

(iii) To prove a lower bound for \eqref{eq:DelayedFloodingMax}, note that for any $u \ne v$,
\begin{align*}
 &\pr \left( \frac{X_0(u) + X_1(v)}{\log n} > \frac{1}{\lambda_0} + \frac{1}{\lambda_1} - 2 \epsilon \right) \\
 &\wge \pr \left( \frac{X_0(u)}{\log n} > \frac{1}{\lambda_0} - \epsilon , \
 \frac{X_1(u)}{\log n} > \frac{1}{\lambda_1} - \epsilon \right) \\
 &\weq \pr \left( \frac{X_0(u)}{\log n} > \frac{1}{\lambda_0} - \epsilon \right)
 \pr \left( \frac{X_1(u)}{\log n} > \frac{1}{\lambda_1} - \epsilon \right).
\end{align*}
Then the exponential tail assumption \eqref{eq:ExpTail} implies that
\[
 n(n-1) \pr \left( \frac{X_0(u) + X_1(v)}{\log n} > \frac{1}{\lambda_0} + \frac{1}{\lambda_1} - 2\epsilon \right)
 \ \to \ \infty.
\]

Observe next that if $u^*$ and $v^*$ are independent uniformly random elements of $[n]$, and $i^*$ is a uniformly random event in $I_n = \{ (u,v) \in [n]^2: u \ne v\}$, then
\begin{align*}
 \pr( W_G(u^*, v^*) \in F)
 &\weq \frac{1}{n^2} \sum_u \sum_v \pr( W_G(u, v) \in F) \\
 &\weq \frac{1}{n} \pr( W_G(u^*, u^*) \in F) + \frac{n-1}{n} \pr( W_G(i^*) \in F)
\end{align*}
for all measurable sets $F \subset \R$. Hence \eqref{eq:PassageTypical} implies that, \whp,
\[
 W_G(i^*)
 \ > \ \left( \frac{1}{\lambda(\nu-1)} - \epsilon \right) \log n.
\]
Then we may apply Lemma~\ref{the:MaxSumLB} with $A_n(u,v) = X_0(u) + X_1(v)$ and $B_n(u,v) = W_G(u,v)$, to conclude that, \whp,
\[
 \max_{u,v} W(u,v)
 \wge \left( \frac{1}{\lambda_0} + \frac{1}{\lambda(\nu-1)} + \frac{1}{\lambda_1} - 3\epsilon \right) \log n.
\]

We will next apply Lemma~\ref{the:MaxSumLB} again, this time with $I_n = [n]$, and $A_n(v) = X_1(v)$ and $B_n(v) = \max_u (X_0(u) + W_G(u,v))$, recalling \eqref{eq:FloodingTypical},  to conclude that, \whp,
\[
 \max_{u,v} W(u,v)
 \wge \left( \frac{1}{\lambda \delta} + \frac{1}{\lambda(\nu-1)} + \frac{1}{\lambda_1} - 3\epsilon \right) \log n.
\]
By a symmetrical argument, we also find that, \whp,
\[
 \max_{u,v} W(u,v)
 \wge \left( \frac{1}{\lambda_0} + \frac{1}{\lambda(\nu-1)} + \frac{1}{\lambda \delta} - 3\epsilon \right) \log n.
\]
By combining the three above inequalities with \eqref{eq:FloodingMax}, we may conclude that, \whp,
\[
 \max_{u,v} W(u,v)
 \wge \left( \frac{1}{\lambda \delta \wedge \lambda_0}
 + \frac{1}{\lambda(\nu-1)}
 + \frac{1}{\lambda \delta \wedge \lambda_1} - 3\epsilon \right) \log n.
\]

\ifarxiv
\bibliographystyle{alpha}
\fi
\ifapt
\bibliographystyle{apt}
\fi
\bibliography{lslReferences}
\end{document}