%%%%%%%%%%%%%%%%%%%%%%% file template.tex %%%%%%%%%%%%%%%%%%%%%%%%% % % This is a general template file for the LaTeX package SVJour3 % for Springer journals. Springer Heidelberg 2010/09/16 % % Copy it to a new file with a new name and use it as the basis % for your article. Delete % signs as needed. % % This template includes a few options for different layouts and % content for various journals. Please consult a previous issue of % your journal as needed. % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % First comes an example EPS file -- just ignore it and % proceed on the \documentclass line % your LaTeX will extract the file if required \begin{filecontents*}{example.eps} %!PS-Adobe-3.0 EPSF-3.0 %%BoundingBox: 19 19 221 221 %%CreationDate: Mon Sep 29 1997 %%Creator: programmed by hand (JK) %%EndComments gsave newpath 20 20 moveto 20 220 lineto 220 220 lineto 220 20 lineto closepath 2 setlinewidth gsave .4 setgray fill grestore stroke grestore \end{filecontents*} % \RequirePackage{fix-cm} % %\documentclass{svjour3} % onecolumn (standard format) %\documentclass[smallcondensed]{svjour3} % onecolumn (ditto) \documentclass[twocolumn]{svjour3} % onecolumn (second format) %\documentclass[twocolumn]{svjour3} % twocolumn % \smartqed % flush right qed marks, e.g. at end of proof % \usepackage{graphicx} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{cite} \usepackage{pictex} \usepackage{subfigure} % % \usepackage{mathptmx} % use Times fonts if available on your TeX system % % insert here the call for the packages your document requires %\usepackage{latexsym} % etc. % % please place your own definitions here and don't use \def but % \newcommand{}{} % % Insert the name of "your journal" with % \journalname{myjournal} % \begin{document} \def \x{{\mbox{\boldmath $x$}}} \def \y{{\mbox{\boldmath $y$}}} \def \z{{\mbox{\boldmath $z$}}} \def \u{{\mbox{\boldmath $u$}}} \def \hxi{{\mbox{\boldmath $\xi$}}} \def \intd{{\rm d}} \def \Ch{{\rm Ch}} \font\euler=eusm10 \def \M{\mbox{\euler M}} \def \varr{\mbox{VaR}} \def \tvar{\mbox{TVaR}} \font\euler=eusm10 \def \M{\mbox{\euler M}} \def \L{\mbox{\euler L}} \def \Z{\mbox{\euler Z}} \def \N{\mbox{\euler N}} \def \F{\mbox{\euler F}} \def \Ch{\mbox{Ch}} \def \R{\Re} \def \intd{{\rm d}} \def \x{{\mbox{\boldmath $x$}}} \def \v{{\mbox{\boldmath $v$}}} \def \y{{\mbox{\boldmath $y$}}} \def \z{{\mbox{\boldmath $z$}}} \def \bxi{{\mbox{\boldmath $\xi$}}} \def \E{{\rm E}} \def \tx{\tilde{x}} \def \ty{\tilde{y}} \def \g{\gamma_{1}} \def \gg{\gamma_{2}} %\newtheorem{theorem}{Theorem} \newtheorem{exm}{Example} \newtheorem{axi}{axiom} \newtheorem{alg}{Algorithm} \newtheorem{ste}{Step} \newtheorem{lem}{Lemma} \newtheorem{cor}{Corollary} %%\newtheorem{definition}{Definition} %%\newtheorem{proposition}{Proposition} \newtheorem{rem}{Remark} \title{On the Shortest Path Problem of Uncertain Random Digraphs%\thanks{Grants or other notes %about the article that should go on the front page should be %placed here. General acknowledgments should be placed at the end of the article.} } %\titlerunning{Short form of title} % if too long for running head \author{Hao Li \and Kun Zhang$^{*}$ %etc. } %\authorrunning{Short form of author list} % if too long for running head \institute{ Hao Li \at School of Mathematics, Renmin University of China, Beijing, 100872, China \\ \email{hlimath@ruc.edu.cn} \and * Corresponding author: Kun Zhang \at School of Mathematics, Renmin University of China, Beijing, 100872, China\\ \email{zk-math2020@ruc.edu.cn} } %\date{Received: date / Accepted: date} \date{} % The correct dates will be entered by the editor \maketitle \begin{abstract} In the field of graph theory, the shortest path problem is one of the most significant problems. However, since varieties of indeterminated factors appear in complex networks, determining of the shortest path from one vertex to another in complex networks may be a lot more complicated than the cases in deterministic networks. To illustrate this problem, the model of uncertain random digraph will be proposed via chance theory, in which some arcs exist with degrees in probability measure and others exist with degrees in uncertain measure. The main focus of this paper is to investigate the main properties of the shortest path in uncetain random digraph. Methods and algorithms are designed to calculate the distribution of shortest path more efficiently. Besides, some numerical examples are presented to show the efficiency of these methods and algorithms. \keywords{Shortest path problem \and Distance \and Uncertain random digraph \and Chance theory \and Uncertainty theory} % \PACS{PACS code1 \and PACS code2 \and more} % \subclass{MSC code1 \and MSC code2 \and more} \end{abstract} \section{Introduction} Graph theory originated from the Seven Bridges Problem of K\"onigsberg in 18th century. After hundreds of years' development, the fields of the graph theory can be briefly divided into two parts: undirected graph theory and directed graph theory. The basic theories and classical algorithms in graph theory have been widely applied to different fields of management, computer science and engineering. In our world, communication is of great significance, and different kinds of networks are proposed and rea-\\searched. Since each processor of a network can be view-\\ed as a vertex in digraph, and every communication links from one to the other can be modeled as an arc in digraph. Therefore, networks could be viewed as digraphs. However, practical networks are always changing instead of keeping static. For example, in a wireless network, the connections change frequently. Therefore, to satisfy the need of network changes, inderministic factors such as random and uncertain factors have been taken into consideration in the research of graph theory. To deal with the problems of indeterminacy, Kolmogorov \cite{Kolm33} established the systems of probability theory in 1933. After more than 70 years, uncertainty theory was founded by Liu \cite{Liu07} in 2007. As we all know, probability needs a lot of historical data to make sure the statistical rules can be sufficiently generated. In 1959, two models of random graphs were proposed by Erd\"os and R\'enyi \cite{ErRe59}. Of course, the theory of probability is never a master key to deal with all the problems in the field of indeterminacy. Just as what we mentioned above, probability theory is data-dependent, i.e. if there's no sufficient data to estimate the distribution, the theory will be invalid to solve the practical problems. In 2013, uncertain graph was proposed by Gao and Gao \cite{GaGa13}. Some of uncertain graphs were soon discussed, such as Euler index \cite{ZhPe12}, diameter index \cite{GaGa13}, cycle index \cite{Gao13}, regularity index \cite{Gao14}, tree index \cite{Gao16}. In 2020, Guo and Li propossed the model of the uncertain digraph. In addition, some traditional problems of graph theory were discussed in uncertain graphs. More information can be found in \cite{LiZP18, RPCW18, ZhYW14, GYLK15, GaQi16}. In recent years, neworks became more and more complex. Different kinds of indeterminate factors appear at the same time. Random and uncertain factors in particular, appear in most cases. In oredr to solve this problem, Liu \cite{Liuq13} proposed the chance theory in 2013 which includes concepts of uncertain random variable and chance measure. In addition, expected value and variance of an uncertain random variable were proposed. Chance theory has been applied to many optimization networks problems, such as uncertain random programming \cite{Liuq13-2}, goal programming \cite{Qin18}, multi-objective programming \cite{ZhYW14-2}. Uncertain random graph was proposed by Liu \cite{Liu14} in 2014. In an uncertain random graph, all edges are independent, and some edges exist with degrees in probability measure while other edges exist with degrees in uncertain measure. In 2014, Liu \cite{Liu14} discussed the diameter index of an uncertain random graph. In 2016, the Euler index of an uncertain random graph was discussed by Zhang, Peng and Li \cite{ZhPL17}. In 2018, the cycle index of an uncertain random graph was discussed by Chen et al. \cite{CPRR18}. In 2020, Li and Zhang discussed the edge-connectivity of uncertain random graph, and the vertex-connectivity of uncertain random graph was investigated by Li and Gao. In this paper, we will propose the model of uncertain random digraph, and discuss the shortest path problem. Definition of distance from one vertex to another in an random uncertain digraph will be given. Then we will discuss the shortest path distribution and give an efficient algorithm to calculated the distribution. And we will use the method of this paper to establish the spreading model of COVID-19 in social networks. The reminder of the paper is organized as follows. In Section 2, we will introduce some necessary notations of digraph, and give a brief introduction of chance theory. In Section 3 and 4, we will discuss the shortest path problem in uncertain digraph and uncertain random digraph respectively, including the form of the distribution of shortest path and algorithms of simplifying the process of calculation. Examples will be shown to illustrate the efficiency of these algorithms. The last section will conclude this paper with a brief summary. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Preliminaries} In this section, we first introduce some necessary definitions and notations of digraph. Then we introduce some preliminary knowledge about chance theory. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Notations of Digraphs} A digraph $D$ is an ordered pair $(V,A)$ consisting of a set $V$ of vertices and a set $A$ of arcs (directed edges). Without loss of generality, in the rest of this paper, we assume $V=\{1,2,3,\dots,n\}$. An ordered pair $(i,j)\in A$ means there exist an arc from vertex $i$ to $j$, where $i$ and $j$ are called the tail and the head of arc $(i,j)$, respectively. Here, we will only consider simple digraphs. A directed walk with length $k$ is an alternating sequence $W=i_1i_2\cdots i_ki_{k+1}$ such that $\{i_1,i_2,\dots,i_k\}\subset V$ and $(i_j,i_{j+1})\in A$ for $j=1,2,\cdots, k$. If all the vertices of $W$ are distinct, then $W$ is called a directed path. The adjacency matrix of digraph $D$, denoted by $M(D)$, is a $n\times n$ matrix such that \begin{equation} M(D)=\left(\begin{array}{ccccc} \alpha_{11}&\alpha_{12}&\alpha_{13}&\dots&\alpha_{1n}\\[1mm] \alpha_{21}&\alpha_{22}&\alpha_{23}&\dots&\alpha_{2n}\\[1mm] \alpha_{31}&\alpha_{32}&\alpha_{33}&\dots&\alpha_{3n}\\[1mm] \vdots&\vdots&\vdots&&\vdots\\[1mm] \alpha_{n1}&\alpha_{n2}&\alpha_{n3}&\dots&\alpha_{nn} \end{array}\right),\nonumber \end{equation} where \begin{equation} \alpha_{ij}=\left\{\begin{aligned} &1,\ if\ (i,j)\in A\\ &0,\ otherwise. \end{aligned}\right.\nonumber \end{equation} And if there is an arc from vertex $i$ to $j$, then $\alpha_{ij}=1$, otherwise $\alpha_{ij}=0$. A well-known proposition is proposed in the following to find out whether there exists a directed walk of length $k$($k=1,2,3,\dots,n-1$) from $i$ to $j$. \begin{proposition} Let $D$ be a digraph and let $X$ be the adjacency matrix of $D$. For two distinct vertices $i$, $j$, there exists a directed walk of length $k$ from $i$ to $j$ if and only if $a_{ij}(X^k)\geq 1$, where $a_{ij}(X^k)$ is the $(i,j)$ entry of matrix $X^k$. \end{proposition} For any vertices $i,j\in V$, if there exist a directed path from vertex $i$ to vertex $j$, then the distance from $i$ to $j$, denoted by $d(i,j)$, is the minimal length of all the directed paths from $i$ to $j$. If there is no directed path from $i$ to $j$, which means $i$ and $j$ are in different components, then $d(i,j)$ is usually defined as $\infty$. In the field of graph theory, $d(i,j)$ can be calculated by Dijkstra Algorithm\cite{BoMu08}, the complexity of which is $O(n^2)$. As all directed paths are directed walks, a proposition can be proposed in the following. \begin{proposition}\label{xk} Let $D$ be a digraph and $X$ be the adjacency matrix of $D$. For two distinct vertices $i$, $j$ and $k=1,2,3,\dots,n-1$, $$d(i,j)\leq k\ if \ and \ only \ if \ \alpha_{ij}(I+X+X^2+\dots+X^k) > 0,$$ where $\alpha_{ij}$ is the $(i,j)$-entry of matrix $I+X+X^2+\dots+X^k$. \end{proposition} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Chance Theory} Let $(\Gamma, \mathcal{L}, \mathcal{M})$ and $(\Omega, \mathcal{A}, \mbox{Pr})$ be an uncertainty space and a probability space, respectively. The product\\ $(\Gamma, \mathcal{L}, \mathcal{M})\times (\Omega, \mathcal{A}, \mbox{Pr})$ is called a chance space. The product $\sigma$-algebra $\mathcal{L}\times \mathcal{A}$ is the smallest $\sigma$-algebra containing all measurable rectangles of the form $\Lambda\times A$, where $\Lambda \in \mathcal{L}$ and $A\in \mathcal{A}$. For each $\Theta\in \mathcal{L}\times \mathcal{A}$, $\Theta$ is called an event of the chance space. The chance measure of event $\Theta$ was defined by Liu \cite {Liuq13} as $$\mbox{Ch}\{\Theta\}=\int_0^1\mbox{Pr}\{\omega\in \Omega | \mathcal{M}\{\gamma\in \Gamma | (\gamma, \omega)\in \Theta\}\ge x\}dx.$$ An uncertain random variable is a function $\eta$ from a chance space $(\Gamma, \mathcal{L}, \mathcal{M})\times (\Omega, \mathcal{A}, \mbox{Pr})$ to the set of real numbers such that $\{\eta \in B\}$ is an event in $\mathcal{L}\times \mathcal{A}$ for any Borel set $B$. A random variable is called a Boolean random variable if it takes values from $\{0,1\}$. Similarly, an uncertain variable or an uncertain random variable is called a Boolean uncertain variable or a Boolean uncertain random variable, respectively, if it takes values from $\{0,1\}$. A function with $n$ variables is called a Boolean function if it is a mapping from $\{0,1\}^n$ to $\{0,1\}$. \begin{theorem} \cite{Liuq13-2} \label{chance} Assume that $\eta_1, \eta_2, \cdots, \eta_m$ are independent Boolean random variables, i.e. \begin{equation} \eta_i=\left\{\begin{array}{ll} 1\qquad\mbox{with probability measure }a_i\\ 0\qquad\mbox{with probability measure }1-a_i \end{array}\right.\nonumber \end{equation} for $i=1,2,\cdots, m$, and the variables $\tau_1, \tau_2, \cdots, \tau_n$ are independent Boolean uncertain variables, i.e. \begin{equation} \tau_j=\left\{\begin{array}{ll} 1\qquad\mbox{with uncertain measure }b_j\\ 0\qquad\mbox{with uncertain measure }1-b_j \end{array}\right.\nonumber \end{equation} for $j=1,2,\cdots, n$. If $f$ is a Boolean function, then $\eta=f(\eta_1, \eta_2, \cdots, \eta_m,\tau_1, \tau_2, \cdots, \tau_n)$ is a Boolean uncertain random variable such that $$\mbox{Ch}\{\eta=1\}=\displaystyle \sum_{(x_1, \ldots, x_m)\in \{0,1\}^m} \Big(\prod_{i=1}^m\mu_i(x_i)\Big)f^{\ast}(x_1, \ldots, x_m),$$ where \begin{eqnarray} &&f^{\ast}(x_1, \ldots, x_m)\nonumber\\ &=& \left\{\begin{array}{ll} \displaystyle\sup_{f(x_1,\ldots, x_m, y_1, \dots, y_n)=1} \min_{1\le j \le n}v_j(y_j),\\[5mm]\qquad\qquad\mbox{if }\displaystyle\sup_{f(x_1,\ldots, x_m, y_1, \dots, y_n)=1} \min_{1\le j \le n}v_j(y_j)<0.5\\[5mm] 1-\displaystyle\sup_{f(x_1,\ldots, x_m, y_1, \dots, y_n)=0} \min_{1\le j \le n}v_j(y_j),\\[5mm]\qquad\qquad\mbox{if }\displaystyle\sup_{f(x_1,\ldots, x_m, y_1, \dots, y_n)=1} \min_{1\le j \le n}v_j(y_j)\ge 0.5, \end{array}\right.\nonumber \end{eqnarray} \begin{equation} \mu_i(x_i)=\left\{\begin{array}{ll} a_i\qquad&\mbox{if }x_i=1\\ 1-a_i\qquad&\mbox{if }x_i=0 \end{array}\right.\nonumber (i=1, 2, \dots, m), \end{equation} \begin{equation} v_j(y_j)=\left\{\begin{array}{ll} b_j\qquad&\mbox{if }y_j=1\\ 1-b_j\qquad&\mbox{if }y_j=0 \end{array}\right.\nonumber (j=1, 2, \dots, n). \end{equation} \end{theorem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{The Shortest Path Problem in Uncertain Digraphs} In this section, we will introduce the definition of uncertain digraph. Then we will discuss the shortest path problem in uncertain digraphs and give the distribution of shortest path. \subsection{Uncertain Digraphs} We first give the definition of uncertain digraph and some necessary notations. \begin{definition}\label{undi} Let $\mathcal{V}$ be a set of $n$ vertices, and write $\mathcal{V}=\{1,2, \cdots, n\} .$ We call $$ \mathcal{A}=\left(\begin{array}{cccc} \alpha_{11} & \alpha_{12} & \cdots & \alpha_{1 n} \\ \alpha_{21} & \alpha_{22} & \cdots & \alpha_{2 n} \\ \vdots & \vdots & \cdots & \vdots \\ \alpha_{n 1} & \alpha_{n 2} & \cdots & \alpha_{n n} \end{array}\right) $$ an uncertain adjacency matrix, if $\alpha_{i j}$ represent the uncertain measures that the $\operatorname{arcs}\ (i, j)$ exist, $i, j=$ $1,2, \cdots,\\ n,$ respectively. The ordered pair $(\mathcal{V}, \mathcal{A})$ is called an uncertain digraph, which is denoted by $\mathbb{D}$. \end{definition} \begin{rem} Since $\mathbb{D}$ is simple, $\alpha_{ii}=0,\ for\ i=1,2,\dots,\\n$. Note that $\mathcal{A}$ is normally asymmetric, i.e. it's possible that $\alpha_{ij}\neq\alpha_{ji}$. \end{rem} Write \begin{equation*} X=\left(\begin{array}{cccc} x_{11} & x_{12} & \cdots & x_{1 n} \\ x_{21} & x_{22} & \cdots & x_{2 n} \\ \vdots & \vdots & \cdots & \vdots \\ x_{n 1} & x_{n 2} & \cdots & x_{n n} \end{array}\right) \end{equation*}\\ and \begin{equation}\label{Xma} \mathbb{X}=\left\{X \mid \begin{array}{l} x_{i j}=0 \text { or } 1, i, j=1,2, \cdots, n \\ x_{i i}=0, i=1,2, \cdots, n \end{array}\right\}. \end{equation} As an uncertain digraph $\mathbb{D}$ has $n$ vertices, there are $n(n-1)$ uncertain arcs. Then there are $2^{n(n-1)}$ possible realizations of arcs. Each realization of arcs and corresponding vertices form a deterministic digraph $D$. Since a digraph could be fully characterized by its adjacency matrix. Once a realization of arcs is given, there exists an unique matrix $X$ in $\mathbb{X}$ satisfying such that $X$ is the adjacency matrix of $D$. By the product axiom of uncertain measure\cite{Liu07}, the uncertain measure of the event that $D$ appears is $$\displaystyle \min_{1\leq i,j \leq n}\ \mu_{ij}(X) ,$$ where \begin{equation} \mu_{ij}(X)=\left\{\begin{array}{ll} \alpha_{ij}\qquad&\mbox{if }x_{ij}=1\\ 1-\alpha_{ij}\qquad&\mbox{if }x_{ij}=0. \end{array}\right.\nonumber \end{equation} \subsection{Distribution of Shortest Path in Uncertain Digraph} Recall that in a digraph, the distance between vertex $i$ and $j$, denoted by $d(i,j)$, is the shortest path from vertex $i$ to $j$. However, in an uncertain digraph, the distance between two vertices is not a fixed number. The distance between them varies in different realization digraphs. Therefore, the distance between two vertices is an uncertain variable. \begin{definition} In an uncertain digraph $\mathbb{D}$, let $V=\{1,2,\\ \dots,n\}$. For any two vertices $i$ and $j$ in $\mathbb{D}$, the length of the shortest path from vertex $i$ to $j$, denoted by $d(i,j)$, is an uncertain variable, taking values from $\{1,2,\dots,n-1,\infty\}$. Note that $d(i,j)=\infty$ if and only if vertex $i$ and $j$ are in different connected components. \end{definition} \begin{lem} (Oparational Law of Boolean System)\cite{Liuq13-2} \label{unop} Assume that the variables $\xi_1, \xi_2, \cdots, \xi_n$ are independent Boolean uncertain variables, i.e. \begin{equation} \xi_j=\left\{\begin{array}{ll} 1\qquad\mbox{with uncertain measure }b_j\\ 0\qquad\mbox{with uncertain measure }1-b_j \end{array}\right.\nonumber \end{equation} for $j=1,2,\cdots, n$. If $f$ is a Boolean function, then $\xi=f(\xi_1, \xi_2, \cdots, \xi_n)$ is a Boolean uncertain variable such that \begin{equation} \mbox{\euler M}\{\xi=1\}=\left\{\begin{array}{ll} \displaystyle\sup_{f(y_1, \dots, y_n)=1} \min_{1\le j \le n}v_j(y_j),\\[5mm]\qquad\mbox{if }\displaystyle\sup_{f(y_1, \dots, y_n)=1} \min_{1\le j \le n}v_j(y_j)<0.5\\[5mm] 1-\displaystyle\sup_{f(y_1, \dots, y_n)=0} \min_{1\le j \le n}v_j(y_j),\\[5mm]\qquad\mbox{if }\displaystyle\sup_{f(y_1, \dots, y_n)=1} \min_{1\le j \le n}v_j(y_j)\ge 0.5, \end{array}\right.\nonumber \end{equation} where $y_j$ take values either 0 or 1, and $v_j$ are defined by \begin{equation} v_j(y_j)=\left\{\begin{array}{ll} b_j\qquad&\mbox{if }y_j=1\\ 1-b_j\qquad&\mbox{if }y_j=0 \end{array}\right.\nonumber (j=1, 2, \dots, n) \end{equation} for $i=1,2,\dots,n$, respectively. \end{lem} According to Proposition \ref{xk}, the property $d(i,j)\leq k$ can be fully characterized by the adjacency matrix of a digraph. So we give the characteristic function of this property in the following. For any $n\times n$ boolean matrix $X$ and any integer $k$ ($k=1,2,\dots,n-1$), we define \begin{equation}\label{de0} f_k(X)=\left\{\begin{array}{ll} 1, \ \mbox{if }\ \alpha_{ij}(I+X+\dots+X^k) > 0 \\ 0, \ \mbox{otherwise}, \end{array}\right.\quad \end{equation}\\ where $\alpha_{ij}$ is the $(i,j)$-entry of matrix $I+X+X^2+\dots+X^k$. And by Lemma \ref{unop}, we have the following Theorem. \begin{theorem}\label{shortest1} Let $\mathbb{D}=(\mathcal{V},\mathcal{A})$ be an uncertain digraph. For distinct vertices $i$, $j$ $\in$ $\mathcal{V}$, the uncertain measure that the distance from $i$ to $j$ is no more than $k$ is denoted by $\eta_{ij}^k(\mathbb{D})$. And we have \begin{equation*}\label{de1} \eta_{ij}^k(\mathbb{D})=\left\{\begin{array}{ll} \displaystyle\sup_{X\in \mathbb{X}, f_k(X)=1}\min_{1\leq i,j\leq n}\mu_{ij}(X),\\ \qquad\mbox{if} \displaystyle\sup_{X\in \mathbb{X}, f_k(X)=1}\min_{1\leq i,j\leq n}\mu_{ij}(X)<0.5\\ 1-\displaystyle\sup_{X\in \mathbb{X}, f_k(X)=0}\min_{1\leq i,j\leq n}\mu_{ij}(X),\\ \qquad\mbox{if} \displaystyle\sup_{X\in \mathbb{X}, f_k(X)=0}\min_{1\leq i,j\leq n}\mu_{ij}(X)\ge 0.5. \end{array}\right. \end{equation*} where \begin{equation}\label{de2} \mu_{ij}(X)=\left\{\begin{array}{ll} \alpha_{ij},\qquad&\mbox{if }x_{ij}=1\\ 1-\alpha_{ij},\qquad&\mbox{if }x_{ij}=0 \end{array}\right. \end{equation} and $\mathbb{X}$ is the set of matrices satisfying (\ref{Xma}). \end{theorem} \begin{rem} According to the duality axiom, the uncertain measure that $i$ and $j$ are in two different components is denoted by $\eta_{ij}^{\infty}(\mathbb{D})$. And we have $\eta_{ij}^{\infty}(\mathbb{D})=1-\eta_{ij}^{n-1}(\mathbb{D})$. \end{rem} According to Theorem \ref{shortest1} above, it is easy to calculate the distribution function of $d(i,j)$. \begin{theorem}\label{distri} Let $\mathbb{D}=(\mathcal{V},\mathcal{A})$ be an uncertain digraph. For two distinct vertices $i$ and $j$, let $\Phi_{(i,j)}(x)$ be the distribution function of uncertain variable $d(i,j)$. Then $$\Phi_{(i,j)}(x)=\left\{\begin{array}{ll} 0, & \qquad\mbox{if}\ x<1\\ \eta_{ij}^{[x]}(\mathbb{D}), & \qquad\mbox{if}\ 1\leq x < n-1\\ \eta_{ij}^{n-1}(\mathbb{D}), & \qquad\mbox{if}\ x \geq n-1. \end{array}\right. \nonumber$$ \end{theorem} \subsection{Maximum $d_{ij}^k$-Digraph} In $\mathbb{D}$, given distinct vertices $i$ and $j$, the uncertain distribution function of $d(i,j)$ was given by Theorem \ref{shortest1} and \ref{distri}. However, it's impractical to calculate the distribution function by Theorem \ref{shortest1} and \ref{distri} , as we have to concern all the realization digraphs. For examples, if $\mathbb{D}$ has $n$ uncertain arcs, then it has $2^{\frac{n(n-1)}{2}}$ uncertain uncertain arcs and $2^{\frac{n(n-1)}{2}}$ realization digraphs. The complexity of computing $f_k$ is $O(n^3)$. So the complexity is $2^{\frac{n(n-1)}{2}}O(n^3)$ in total, which is not polynomial. In next part, we will propose a more efficient method to culculate $\eta_{ij}^k(\mathbb{D})$, and present a polynomial algorithm. \begin{definition}\label{maximumdijk} Let $\mathbb{D}=(\mathcal{V}, \mathcal{A})$ be an uncertain digraph. A digraph $D$ is called a maximum $d_{ij}^k$ digraph if all the following hold. \mbox{(1)} \quad $V(D)=\mathcal{V};$ \mbox{(2)} \quad $d(i,j)\leq k;$ \mbox{(3)} \quad $\displaystyle \min_{(i,j)\in A(D)}\alpha_{ij}$ is maximum. \end{definition} Maximum $d_{ij}^k$ digraph given by Definition \ref{maximumdijk} could be used to calculated uncertain measure $\eta_{ij}^k(\mathbb{D})$, which is shown in the following Theorem. \begin{theorem}\label{mdij} Let $\mathbb{D}=(\mathcal{V}, \mathcal{A})$ be an uncertain digraph and $i$, $j$ be the two vertices in $\mathcal{V}$. Let $D=(V,A)$ be a maximum $d_{ij}^k$ digraph of $\mathbb{D}$. Then $$\eta_{ij}^k(\mathbb{D})=\min_{(i,j)\in A(D)}\alpha_{ij}.$$ \end{theorem} \noindent{\textbf{Proof.}} We assume $\displaystyle \min_{(i,j)\in A(D)}\alpha_{ij}=a_0.$ Let $\mathbb{D}_0=(\mathcal{V},\mathcal{A}_0)$ be an uncertain digraph, where $\mathcal{A}_0=(b_{ij})_{n\times n}$ and \begin{equation} b_{ij}=\left\{\begin{array}{ll} \alpha_{ij}, & \mbox{if } (i,j)\in A(D)\\ 0, & \mbox{if } (i,j)\notin A(D) \end{array} \quad for\ 1\leq i,j\leq n\right..\nonumber \end{equation} We will first prove $\eta_{ij}^k(\mathbb{D})\geq a_0$. Note that $D$ could be viewed as a realization digraph of $\mathbb{D}_0$, and the uncertain measure that it appears is $a_0$. We have $\eta_{ij}^k(\mathbb{D})\geq \displaystyle \min_{(i,j)\in A(D)}\alpha_{ij}=a_0$. As $\mathbb{D}$ has more arcs than $\mathbb{D}_0$, it's easier to find a directed path from $i$ to $j$. Then we have \begin{equation}\label{geqq} \eta_{ij}^k(\mathbb{D})\geq \eta_{ij}^k(\mathbb{D}_0)\geq\displaystyle \min_{(i,j)\in A(D)}\alpha_{ij}=a_0. \end{equation} We then show that $\eta_{ij}^k(\mathbb{D})\leq a_0$. As the number of realization digraphs is finite, there exists a realization digraph $D_1$ of $\mathbb{D}$ whose adjacency matrix $X_1$ satisfies $f_k(X_1)=1$ and \begin{equation*} \displaystyle\sup_{X\in \mathbb{X}, f_k(X)=1}\min_{1\le i,j \le n}\mu_{ij}(X)=\min_{1\le i,j \le n }\mu_{ij}(X_1). \end{equation*} %where $\mathbb{X}$ is the set of matrices satisfying (\ref{Xma}), $f_k$ and $\mu_{ij}$ are defined by (\ref{de0}) and (\ref{de2}), respectively. By the difinition of $D$, $\displaystyle \min_{(i,j)\in A(D_1)}\mu_{ij}\leq a_0$. Thus, \begin{equation}\label{de3} \begin{aligned} \quad &\displaystyle\sup_{X\in \mathbb{X}, f_k(X)=1}\min_{1\le i ,j \le n}\mu_{ij}(X)\\ &=\min_{1\le i,j \le n }\mu_{ij}(X_1)\\ &\leq \min_{(i,j)\in A(D_1)}\mu_{ij}\\ &=(\min_{(i,j)\in A(D_1)}\alpha_{ij})\land(\min_{(i,j)\notin A(D_1)}(1-\alpha_{ij}))\\ &\leq \min_{(i,j)\in A(D_1)}\alpha_{ij}\\ &\leq a_0. \end{aligned} \end{equation} Let $D_2=(V,A_2)$ be a a realization digraph of $\mathbb{D}$ such that $A_2=A(D)\cup\{(i,j)|\alpha_{ij}>a_0\}\backslash \{(i,j)|\alpha_{ij}= a_0\}$. Let $X_2$ be the adjacency matrix of $D_2$. Therefore, $\displaystyle \min_{(i,j)\in A(D_2)}\alpha_{ij}>a_0$. By the choice of digraph $D_2$, $d(i,j)>k$ holds in $D_2$, i.e. $f_k(X_2)=0$.\\ If $\displaystyle\sup_{X\in \mathbb{X}, f_k(X)=1}\min_{1\le i,j \le n}\alpha_{ij}(X)<0.5$, according to Theorem \ref{shortest1} and (\ref{de3}), then we have \begin{equation}\label{a01} \eta_{ij}^k(\mathbb{D})=\displaystyle\sup_{X\in \mathbb{X}, f_k(X)=1}\min_{1\le i,j \le n}\mu_{ij}(X)\leq a_0. \end{equation}\\ If $\displaystyle\sup_{X\in \mathbb{X}, f_k(X)=1}\min_{1\le i,j \le n}\alpha_{ij}(X)\geq 0.5$, then by (\ref{de3}), $a_0\geq 0.5$. Accroding to Theorem \ref{shortest1}, \begin{equation*} \begin{aligned} \eta_{ij}^k(\mathbb{D})&=1-\displaystyle\sup_{X\in \mathbb{X}, f_k(X)=0}\min_{1\le i,j \le n}\mu_{ij}(X)\\ &\leq 1-\min_{1\le i ,j \le n}\mu_{ij}(X_2)\\ &=1-\displaystyle(\min_{(i,j)\in A(D_2)}\alpha_{ij})\land (\min_{(i,j)\notin A(D_2)}(1-\alpha_{ij}))\\ &\leq 1-\displaystyle(\min_{(i,j)\in A(D_2)}\alpha_{ij})\land (1-a_0)\\ &\leq 1-a_0\land(1-a_0). \end{aligned} \end{equation*} Since $a_0\geq0.5\geq 1-a_0,$ we have \begin{equation}\label{a02} \eta_{ij}^k(\mathbb{D})\leq 1-(1-a_0)=a_0. \end{equation} By inequalities (\ref{a01}) and (\ref{a02}), $\eta_{ij}^k(\mathbb{D})\leq a_0.$ And by inequalities (\ref{geqq}), $\eta_{ij}^k(\mathbb{D})=a_0$ is proved to be correct.\qed \subsection{Algorithm and Example} By Theorem \ref{mdij}, in an uncertain digraph $\mathbb{D}=(\mathcal{V}, \mathcal{A})$, once $i,j,k$ are given, the uncertain measure $\eta_{ij}^k(\mathbb{D})$ can be calculated by finding a maximum $d_{ij}^k$ digraph of $\mathbb{D}$. Although such a maximum digraph may not be unique, we can always use a greedy algorithm to find a maximum $d_{ij}^k$ digraph of $\mathbb{D}$. \begin{alg}\label{aud} \noindent{\bf Greedy Algorithm for calculating $\eta_{ij}^k(\mathbb{D})$}.\\ Note that $\mathbb{D}=(\mathcal{V}, \mathcal{A})$ be an uncertain digraph. Let $A(\mathbb{D})$ be the set of uncertain arcs. Let $i$ and $j$ be the vertices in $\mathcal{V}$ and $k$ be a constant taking values from $\{1,2,\dots n-1\}$. \\ \noindent{\bf Step 1.} Set $A=\emptyset$.\\ \noindent{\bf Step 2.} Choose $(i, j) \in A(\mathbb{D})$ such that $\alpha_{ij}$ is maximum. Set $A=A \cup\{(i,j)\}$, and $A(\mathbb{D})=$ $A(\mathbb{D}) \backslash\{(i,j)\}$. Calculate $d(i,j)$ using Dijkstra Algorithm(if there's no path from $i$ to $j$, return to $n$) in $D=(V,A)$.\\ \noindent{\bf Step 3.} If $d(i,j)\leq k$, stop the iteration. The digraph $D=(\mathcal{V}, A)$ is a maximum $d_{ij}^k$ digraph. Thus by Theorem \ref{mdij}, $\eta_{ij}^k(\mathbb{D})=\alpha_{ij}$. Otherwise, go to Step 4.\\ \noindent{\bf Step 4.} If $A(\mathbb{D}) \neq \emptyset$, then go to Step 2. If $A(\mathbb{D})=\emptyset$, then stop and $\eta_{ij}^k(\mathbb{D})=0$. \end{alg} Using algorithm \ref{aud} and Theorem \ref{distri}, distribution function $\Phi_{(i,j)}(x)$ could be calculated easily by the following Algorithm. \begin{alg}\label{distrii} \noindent{\bf Algorithm for calculating $\Phi_{(i,j)}(x)$}.\\ Note that $\mathbb{D}=(\mathcal{V}, \mathcal{A})$ be an uncertain digraph. Let $A(\mathbb{D})$ be the set of uncertain arcs. Let $i$ and $j$ be the vertices in $\mathcal{V}$.\\ \noindent{\bf Step 1.} Set $A=\emptyset$, $k=n-1$.\\ \noindent{\bf Step 2.} Choose $(i, j) \in A(\mathbb{D})$ such that $\alpha_{ij}$ is maximum. Set $A=A \cup\{(i,j)\}$, and $A(\mathbb{D})=$ $A(\mathbb{D}) \backslash\{(i,j)\}$. Calculate $d(i,j)$ using Dijkstra Algorithm(if there's no path from $i$ to $j$, return to $n$) in $D=(V,A)$.\\ \noindent{\bf Step 3.} If $d(i,j)\leq k$, then the digraph $D=(\mathcal{V}, A)$ is a maximum $d_{ij}^k$ digraph. Thus by Theorem \ref{mdij}, $\eta_{ij}^k(\mathbb{D})=\alpha_{ij}$. Let $k=k-1$ and then go to Step $3 ;$ otherwise, go to Step 4.\\ \noindent{\bf Step 4.} If $A(\mathbb{D}) \neq \emptyset$, then go to Step 2. If $A(\mathbb{D})=\emptyset$, then stop and $\eta_{ij}^k(\mathbb{D})=0$.\\ \noindent{\bf Step 5.} According to Theorem \ref{distri}, we could calculate the distribution function $\Phi_{(i,j)}(x)$. \end{alg} Next, we will discuss the complexity of Algorithm \ref{distrii}. Let $m$ be the number of different uncertain values with which arcs exist. In Step $2,$ we need to calculate $d(i,j)$ by Dijkstra Algorithm, which the complexity is $O(n^2)$. As the Algorithm has $m$ interations of Step 2, the complexity of Algorithm \ref{aud} is $O(mn^2)$. When the number of vertices is small, the algorithm is quite efficient. Here is an example. \begin{exm} Let $\mathbb{D}=\{\mathcal{V},\mathcal{A}\}$ be an uncertain digraph. $\mathcal{V}=\{1,2,3,4,5\}$ and $$ \mathcal{A}=\left(\begin{array}{ccccc} 0 & 0 & 0 & 0.9 & 0.4 \\ 1 & 0 & 0.9 & 0 & 0.3\\ 1 & 0.3 & 0 & 0.6 & 0\\ 0 & 0 & 0 & 0 & 0.8\\ 0 & 0 & 0 & 0.3 & 0 \end{array}\right). $$ We calculate the value of $\eta_{25}^k$, $k\in\{1,2,3,4\}$ using the Algorithm \ref{aud}. The uncertain measures of all arcs are listed from high to low as follows: $1,\ 0.9,\ 0.8,\ 0.6,\ 0.4,\ 0.3.$ \begin{figure}[t] \centering \includegraphics[width=0.48\textwidth]{ud1.jpg} \caption{Iterations in Example 1} \end{figure} In the first iteration, $k=4$, and then we add the arcs with uncertain measure $1$. It can be easily verified that $d(2,5)=+\infty>4$. According to the algorithm, we continue the iteration. In the second iteration, $k=4$ ,then we add the arcs with uncertain measure $0.9$. It can be found that $d(2,5)=+\infty>4$. We continue the iteration. In the third iteration, $k=4$, then we add the arcs with uncertain measure $0.8$. We find it that $d(2,5)=3\leq 4$. $D$ is the maximum $d_{25}^4$ digraph, thus $\eta_{25}^4=0.8$. Let $k=3$ and we find that $d(2,5)\leq 3$ still holds. So $\eta_{25}^3=0.8$. Let $k=2$, and we continue the iteration. In the fourth iteration, $k=2$, then we add the arcs with uncertain measure $0.6$. By Dijkstra Algorithm, $d(2,5)=3>2$, so we continue. In the fifth iteration, $k=2$, then we add the arcs with uncertain measure $0.4$. We find that $d(2,5)=2\leq 2$, so $\eta_{25}^2=0.4$. Let $k=1$, and we continue the iteration. In the sixth iteration, $k=1$, then we add the arcs with uncertain measure $0.3$. $d(2,5)=1\leq 1$, so $\eta_{25}^1=0.3$. All the directed edges have been added, so we stop the iteration. By the iteration process, distribution function of $d(2,5)$ is \begin{equation*} \Phi_{(2,5)}(x)=\left\{\begin{array}{ll} 0, & \qquad\mbox{if}\ x<1\\ 0.3, & \qquad\mbox{if}\ 1\leq x < 2\\ 0.4, & \qquad\mbox{if}\ 2\leq x < 3\\ 0.8, & \qquad\mbox{if}\ x \geq 3, \end{array}\right. \end{equation*} whose image is shown in Fig.\ref{distri1}. \begin{figure}[h] \centering \includegraphics[width=0.35\textwidth]{distri1.jpg} \caption{Distribution Function of $d(2,5)$} \label{distri1} \end{figure} \end{exm} \subsection{Numerical Simulation of The Shortest Path Model on COVID-19 Transmission in Social Networks}. The transmission of COVID-19 has severely threatened people's lives since 2019. Therefore, researchs about the transmission of COVID-19 has its theoretical and practical significance. According to the World Health Organization(WHO), COVID-19 has distinct community transmission characteristics. It can easily spread through the social network and the spreading rate of COVID-19 is much higher than the other viruses. In this part, We simulate the spread of viruses in social networks. We use a vertex to represent a person. For any two person $i$ and $j$, if COVID-19 is transmitted from $i$ to $j$, there is an arc between the corresponding verteices, otherwise it does not exist. Since the virus transmission is affected by indeterminate factors, the arc $(i,j)$ exists with a certain measure. As the measures that COVID-19 transmit from $i$ to $j$ and from $j$ to $i$ are different, it can only be characterized by directed graphs instead of undirected graphs. At the same time, due to the lack of historical data of interpersonal communication, it is difficult for us to build a model by probability theory. As a result, we assume all the arcs exist with degree of uncertain measure. When a small number of infected people appear in a social network, they have infected some people around because of the incubation period. At this time, the distance of uncertain digraph can be used to estimate the required isolation range. One reason why random graphs are not suitable here is that the probability measures of arcs in the graph are difficult to be obtained objectively. The other reason is that according to the independence of probability measure, the probability measure of a product event is equal to the product of all the probability measures. According to the little probability event principle, the transmission range is generally very small. However, this estimation is sometimes inconsistent with the reality, since the transmission range will be much larger due to the incubation period of the virus. \begin{figure}[t] \centering \includegraphics[width=0.5\textwidth]{100NODES.jpg} \caption{Social Network of 100 Nodes} \label{100nodes} \end{figure} Then we simulate how a person infects others around him. We assume the number of vertices in the transmission networks is 100. According to sociological research, we assume that the out-degrees and in-degrees of each vertex are around 25 originally. We consider the transmission range of infected person 1. Choose one of the remaining 99 healthy people, assuming the 100th one. We will explore how many people the virus needs to transmit from the first person to the 100th person. This is equivalent to calculating the distance between them in an uncertain digraph. Let $\mathbb{D}=\{\mathcal{V},\mathcal{A}\}$ be an uncertain digraph with 100 vertices. All the arcs exist with degree of uncertain measure that two people have close contact. We calculate the value of $\eta_{1,100}^k$ and the distribution function of uncertain variable $d(1,100)$ using Algorithm \ref{aud} and \ref{distrii}. The original social network of 100 vertices is shown in Fig. \ref{100nodes}. By algorithm \ref{aud}, the value of $\eta_{1,100}^2$ is 0.1250. The same is true of the calculation of $\eta_{1,100}^k$. So we can get distribution function of $d(1,100)$. Distribution function of $d(1,100)$ is \begin{equation*} \Phi_{(1,100)}(x)=\left\{\begin{array}{ll} 0, & \qquad\mbox{if}\ x<1\\ 0.1250, & \qquad\mbox{if}\ 1\leq x < 2\\ 0.3631, & \qquad\mbox{if}\ 2\leq x < 3\\ 0.5781, & \qquad\mbox{if}\ 3\leq x < 4\\ 0.8340, & \qquad\mbox{if}\ 4\leq x < 5\\ 0.9006, & \qquad\mbox{if}\ 5\leq x < 6\\ 0.9580, & \qquad\mbox{if}\ 6\leq x < 7\\ 0.9681, & \qquad\mbox{if}\ x \geq 7, \end{array}\right. \end{equation*} whose image is shown in Fig. \ref{distri2}. Through calculation, we find that $d(1,100)$ does not exceed 7 with an uncertain measure of 0.9580. In other words, patient 1 will infect the healthy person 100 through up to six times of transmission. In fact, if we choose other healthy people, the calculation result is almost the same, which means that an infected person will infect the whole community by seven rounds of transmission at most. \begin{figure}[h] \centering \includegraphics[width=0.35\textwidth]{distri2.jpg} \caption{Distribution Function of $d(1,100)$} \label{distri2} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Shortest Path Problem in Uncertain Random Digraph} In this section, we will propose the model of uncertain random digraph, and discuss the shortest path problem in uncertain random digraphs. \subsection{Uncertain Random Digraphs} In an uncertain random digraph with $n$ vertices, all arcs are independent, and some arcs exist with degrees in probability measure while other arcs exist with degrees in uncertain measure. We define two disjoint collections of arcs, \begin{equation} \mathcal{U}=\{(i,j)\,|\,1\le i,j\le n\mbox{ and $(i,j)$ are uncertain arcs}\},\nonumber \end{equation} \begin{equation} \mathcal{R}=\{(i,j)\,|\,1\le i,j\le n\mbox{ and $(i,j)$ are random arcs}\},\nonumber \end{equation} with $\mathcal{U}\cup\mathcal{R}=\{(i,j)\,|\,1\le i,j\le n\}$. Note that deterministic arcs are regarded as special uncertain ones which exist with degrees in uncertain measure $1$. The {\em adjacency matrix} is an $n\times n$ matrix \begin{equation} \mathcal{A}=\left(\begin{array}{cccc} \alpha_{11}&\alpha_{12}&\cdots&\alpha_{1n}\\[1mm] \alpha_{21}&\alpha_{22}&\cdots&\alpha_{2n}\\[1mm] \vdots&\vdots&\ddots&\vdots\\[1mm] \alpha_{n1}&\alpha_{n2}&\cdots&\alpha_{nn} \end{array}\right),\nonumber \end{equation} where $\alpha_{ij}$ represent the truth values in uncertain measure or probability measure if the arc from $i$ to $j$ exist, $i,j=1,2,\cdots,n$. As digraphs considered in this paper are simple, $\alpha_{ii}=0$, for $i=1,2,\dots,n$, and $\mathcal{A}$ is normally asymmetric matrix, i.e. $\alpha_{ij}\neq\alpha_{ji}$, for $i\neq j$. \begin{definition} Assume $\mathcal{V}$ is the colleciton of vertices, $\mathcal{U}$ is the collection of uncertain arcs, $\mathcal{R}$ is the collection of random arcs, and $\mathcal{A}$ is the adjacency matrix. Then the quartette $\mathbb{D}=(\mathcal{V}, \mathcal{U},\mathcal{R},\mathcal{A})$ is said to be an uncertain random digraph. \end{definition} For an uncertain random digraph $\mathbb{D}=(\mathcal{V}, \mathcal{U},\mathcal{R},\mathcal{A})$, write \begin{equation} X=\left(\begin{array}{cccc} x_{11}&x_{12}&\cdots&x_{1n}\\[1mm] x_{21}&x_{22}&\cdots&x_{2n}\\[1mm] \vdots&\vdots&\ddots&\vdots\\[1mm] x_{n1}&x_{n2}&\cdots&x_{nn} \end{array}\right)\nonumber \end{equation} and \begin{equation}\label{ecX} \mathbb{X}=\left\{X\,\Big|\!\begin{array}{l}x_{ij}=0 \mbox{ or }1,\,\mbox{ if }(i,j)\in \mathcal{R}\\ x_{ij}=0,\,\mbox{ if }(i,j)\in \mathcal{U}\\ x_{ii}=0,\, i=1,2,\cdots,n \end{array}\!\!\right\}. \end{equation} For any $X\in \mathbb{X}$, the {\em extension class} of $X$ is defined by \begin{equation}\label{Xstar} X^\ast=\left\{Y\,\Big|\!\begin{array}{l}y_{ij}=x_{ij},\,\mbox{ if }(i,j)\in \mathcal{R}\\ y_{ij}=0\mbox{ or }1,\,\mbox{ if }(i,j)\in \mathcal{U}\\ y_{ii}=0,\, i=1,2,\cdots,n \end{array}\!\!\right\}. \end{equation} As there are $n(n-1)$ possible arcs, there are $2^{n(n-1)}$ posible realization of arcs. Each one of them could be represented by a deterministic digraph, which is called a realization digraph. Since a digraph could be fully characterized by its adjacency matrix. For every $X\in \mathbb{X}$ and $Y\in X^\ast$, such that $Y$ is the adjacency matrix of a realization digraph $H$. The chance measure of the event that the realization digraph $H$ appears, is \begin{equation} \displaystyle \left(\prod_{(i,j)\in\mathcal{R}}w_{ij}(Y)\right)\left(\min_{(i,j)\in\mathcal{U}}w_{ij}(Y)\right), \nonumber \end{equation} where \begin{equation} w_{ij}(Y)=\left\{\begin{array}{cl}\alpha_{ij},&\mbox{if }y_{ij}=1\\ 1-\alpha_{ij},&\mbox{if }y_{ij}=0. \end{array}\right.\nonumber \end{equation} \begin{figure}[htbp] \centering \subfigure[$\mathbb{D}$]{\includegraphics[width=0.12\textwidth]{1_1.jpg}}\\ \subfigure[$H_1$]{\includegraphics[width=0.12\textwidth]{1_2.jpg}}\quad \subfigure[$H_2$]{\includegraphics[width=0.12\textwidth]{1_3.jpg}}\quad \subfigure[$H_3$]{\includegraphics[width=0.12\textwidth]{1_4.jpg}} \caption{Uncertain random digraph $\mathbb{D}$ and its realization digraphs} \label{realization} \end{figure} \noindent{\bf Example 2.} Let $\mathbb{D}=(\mathcal{V}, \mathcal{U},\mathcal{R},\mathcal{A})$ be an uncertain random digraph (shown in Fig.\ref{realization}), $A=\{(1,2),(1,3),(1,5),\\ (2,3),(3,1),(3,4),(4,5),(5,2)\}$. where $\mathcal{V}=\{1,2,3,4,5\}$, $\mathcal{R}=\{(1,2),(1,3),(3,4)\}$, $\mathcal{U}=\{(1,5),(2,3),(3,1),\\(4,5),(5,2)\}$, and \begin{equation} \mathcal{A}=\begin{pmatrix} 0 & 0.2 & 0.9 & 0 & 0.8\\ 0 & 0 & 0.4 & 0 & 0\\ 0.1 & 0 & 0 & 0.7 & 0\\ 0 & 0 & 0 & 0 & 0.3\\ 0 & 0.4 & 0 & 0 & 0 \end{pmatrix}.\nonumber \end{equation} As $\mathbb{D}$ has 8 edges, it has $2^8$ realizations graphs, three of which are shown in Fig.\ref{realization}. The chance measure of the event that $H_1$ appears is \begin{eqnarray} 0.2\times 0.9\times 0.7\times \min\{0.6,0.9,0.4,0.8,0.3\}=0.0378.\nonumber \end{eqnarray} Similarly, the chance measure of the events that $H_2$ and $H_3$ appear are 0.0504 and 0.0014 repectively. \begin{rem} If $\mathcal{U}=\emptyset$, an uncertain random digraph $\mathbb{D}=(\mathcal{V}, \mathcal{U},\mathcal{R},\mathcal{A})$ becomes a {\em random digraph}. Then \begin{equation}\label{remark3} \mathbb{X}=\left\{X\,\Big|\!\begin{array}{l} x_{ij}=0\mbox{ or }1,\, i,j=1,2,\cdots,n\\ x_{ii}=0,\, i=1,2,\cdots,n \end{array}\!\!\right\}. \end{equation} For any $X\in \mathbb{X}$, $X$ is the adjacency matrix of a realization digraph, which appears with probability $$ \prod_{1\le i,j \le n }w_{ij}(X).$$ If $\mathcal{R}=\emptyset$, an uncertain random digraph $\mathbb{D}=(\mathcal{V}, \mathcal{U},\mathcal{R},\mathcal{A})$ becomes an {\em uncertain digraph} in Definition \ref{undi}. \end{rem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Distribution of Shortest Path in Uncertain Random Digraph} Just as the situation in an uncertain digraph, the distance between two vertices is not a fixed number in an uncertain random digraph. The distance between them varies in different realization digraphs. Therefore, the distance between two vertices is an uncertain random variable. \begin{definition} In an uncertain random digraph $\mathbb{D}$, let $\mathcal{V}=\{1,2,\dots,n\}$. For any two vertices $i$ and $j$ in $\mathbb{D}$, the length of the shortest path from vertex $i$ to $j$, denoted by $d(i,j)$, is an uncertain random variable, taking values from $\{1,2,\dots,n-1,\infty\}$. Note that $d(i,j)=\infty$ if and only if vertex $i$ and $j$ are in different connected components. \end{definition} Accoding to Theorem \ref{chance}, we have the following theorem. \begin{theorem}\label{shortest} Let $\mathbb{D}=(\mathcal{V},\mathcal{U},\mathcal{R}, \mathcal{A})$ be an uncertain random digraph. For any vertices $i$, $j$ $\in$ $\mathcal{V}$, $\mathbb{X}$ is the class of matrices satisfying (\ref{ecX}), $X^{\ast}$ is the extension class of $X$ satisfying (\ref{Xstar}). The chance measure that the distance from $i$ to $j$ is at most $k$ is denoted by $\eta_{ij}^k(\mathbb{D})$. And we have \begin{equation} \eta_{ij}^k(\mathbb{D})=\displaystyle \sum_{X\in \mathbb{X}}\Big(\prod_{(i,j)\in \mathcal{R}}w_{ij}(X)\Big)f_k^\ast(X),\nonumber \end{equation} where \begin{equation} f_k^{\ast}(X)=\left\{\begin{array}{ll} \displaystyle\sup_{Y\in X^{\ast}, f_k(Y)=1}\min_{(i,j)\in \mathcal{U}}w_{ij}(Y),\\ \qquad\qquad\mbox{if} \displaystyle\sup_{Y\in X^{\ast}, f_k(Y)=1}\min_{(i,j)\in \mathcal{U}}w_{ij}(Y)<0.5\\ 1-\displaystyle\sup_{Y\in X^{\ast}, f_k(Y)=0}\min_{(i,j)\in \mathcal{U}}w_{ij}(Y),\\ \qquad\qquad\mbox{if} \displaystyle\sup_{Y\in X^{\ast}, f_k(Y)=1}\min_{(i,j)\in \mathcal{U}}w_{ij}(Y)\ge 0.5. \end{array}\right. \nonumber \end{equation} and \begin{equation}\label{wij} w_{ij}(X)=\left\{\begin{array}{ll} \alpha_{ij}, & \mbox{if } x_{ij}=1\\ 1-\alpha_{ij}, & \mbox{if } x_{ij}=0. \end{array}\right. \end{equation} \end{theorem} \begin{rem} According to the duality axiom, the chance measure that $i$ and $j$ are in two different components is denoted by $\eta_{ij}^\infty$. And we have $\eta_{ij}^\infty=1-\eta_{ij}^k(\mathbb{D})$. \end{rem} \begin{cor} Let $\mathbb{D}=(\mathcal{V}, \mathcal{A})$ be a random digraph. $\mathbb{X}$ is the class of matrices satisfying (\ref{ecX}), $X^{\ast}$ is the extension class of $X$ satisfying (\ref{Xstar}). $w_{ij}$ satisfies (\ref{wij}). For any vertices $i$, $j$ $\in$ $\mathcal{V}$, we have\\ 1. the probability measure that the distance from $i$ to $j$ is at most $k$ is $$ P\{d(i,j)\leq k\}=\sum_{X \in \mathbb{X}, g_k(Y)=1}\left(\prod_{1 \leq i,j \leq n} w_{ij}(X)\right). $$\\ 2. the probability measure that $i$ and $j$ are in two different components is $$ P\{d(i,j)=\infty\}=1-P\{d(i,j)\leq n-1\}, $$ \end{cor} According to the Theorem \ref{shortest} above and the definition of distribution function, it is easy to calculate the distribution function of $d(i,j)$ by the following theorem. \begin{theorem} Let $\mathbb{D}=(\mathcal{V},\mathcal{U},\mathcal{R}, \mathcal{A})$ be an uncertain random digraph. For any two distinct vertices $i$ and $j$, $\Phi_{(i,j)}(x)$ is the chance distribution function of uncertain random variable $d(i,j)$, and we have $$\Phi_{(i,j)}(x)=\left\{\begin{array}{ll} 0, & \qquad\qquad\mbox{if}\ x<1\\ \eta_{ij}^{[x]}(\mathbb{D}), & \qquad\qquad\mbox{if}\ 1\leq x < n-1\\ \eta_{ij}^{n-1}(\mathbb{D}), & \qquad\qquad\mbox{if}\ x \geq n-1. \end{array}\right. \nonumber$$ \end{theorem} Although the method of formulating chance distribution function has been given, it seems to be theoretical and quite complicated because we have to concern all the realization digraphs. So we need a simpified formula to calculate final result. According to the Theorem \ref{shortest}, after random arcs are fixed, the uncertain random digraph will become an uncertain digraph. As a result, we can calculated $f^\ast$ by Algorithm \ref{aud}. In next part, we will propose an efficient method to culculate $\eta_{ij}^k(\mathbb{D})$. \subsection{Algorithm and Example} According to Algorithm \ref{aud} and Theorem \ref{shortest}, we give an efficient Algorithm to calculate $\eta_{ij}^k(\mathbb{D})$ of an uncertain random digraph. \begin{alg}\label{adij} \noindent{\bf Algorithm for calculating the $\eta_{ij}^k(\mathbb{D})$ of an uncertain random digraph} \noindent{\bf Step 1.} Divide the realization digraph of uncertain random digraph $\mathbb{D}=(\mathcal{V},\mathcal{U},\mathcal{R},\mathcal{A})$ into $l$ parts by the arcs with degree of random measure, where $l=2^{|\mathcal{R}|}$. For each part of the $\mathbb{D}$, we assume there exist only arcs with degree of random measure from the beginning. Let $j=1$.\\ \noindent{\bf Step 2.} Calculate $f_k^\ast$ by Algorithm \ref{aud}. Let $j=j+1$. \\ \noindent{\bf Step 3.} If $j=l$, stop and calculate the $\eta_{ij}^k(\mathbb{D})$ by Theorem \ref{shortest}; if $j