# 流距离

### 任意点i到汇的平均时间

$\displaystyle{ l_i=1+\sum_{j=0}^{N}{m_{ij}l_j}, ~~~~\forall i\neq N+1 }$

(eq2)

$\displaystyle{ l_i=m_{i,N+1}\cdot 1+\sum_{j=0}^{N}{m_{ij}(1+l_j)}=m_{i,N+1}+\sum_{j=0}^{N}m_{ij}+\sum_{j=0}^{N}m_{ij}l_j=1+\sum_{j=0}^{N}m_{ij}l_j, ~~~~\forall i\neq N+1 }$

$\displaystyle{ L=\mu+M_{-(N+1)} L }$

$\displaystyle{ L=(I-M_{-(N+1)}^{-1})\cdot \mu=U_{-(N+1)}\cdot \mu=(\sum_{j=0}^{N}u_{ij})_{(N+1)\times 1} }$

(eq3)

### 从源到任意点i的平均首达时间

$\displaystyle{ l_i=m'_{0,i}+\sum_{j=1}^{N+1} m'_{ji}(l_j+1)=m'_{0,i}+\sum_{j=1}^{N+1} m'_{ji}+\sum_{j=1}^{N+1} m'_{ji}l_j=1+\sum_{j=1}^{N+1}m'_{ji}l_j,~~~~\forall i\neq 0 }$

$\displaystyle{ L=\mu+M'_{-0}L }$

$\displaystyle{ L=(I-M'_{-0})^{-1}\mu=U'_{-0}\mu }$

### 任意节点i到任意节点j的平均首达时间（流距离）

$\displaystyle{ l_{i,j}=\sum_{k=1}^{\infty}kp^{k}_{i,j} }$

$\displaystyle{ (M_{-j})_{p,q}=\left\{\begin{array}{ll} m_{p,q} & \mbox {if } p\neq j, \\ 0 & \mbox {if } p = j\end{array}\right. }$

$\displaystyle{ p^{k}_{i,j}=\frac{\phi_{0i}(M_{-j}^k)_{i,j}}{\phi_{i,j}} }$

$\displaystyle{ l_{i,j}=\sum_{k=0}^{\infty}k\frac{\phi_{0i}(M_{-j}^k)_{i,j}}{\phi_{i,j}}=\frac{\phi_{0i}(\sum_{k=1}^{\infty}kM_{-j}^k)_{ij}}{\phi_{i,j}} }$

$\displaystyle{ XM_{-j}=\sum_{k=1}^{\infty}kM_{-j}^{k+1}=M_{-j}^2+2M_{-j}^3+\cdot\cdot\cdot }$

$\displaystyle{ XM_{-j}-X=-(M_{-j}+M_{-j}^2+M_{-j}^3+\cdot\cdot\cdot)=-M_{-j}U_{-j} }$

$\displaystyle{ X=M_{-j}U_{-j}^2 }$

$\displaystyle{ l_{i,j}=\frac{\phi_{0i}(M_{-j}U_{-j}^2)_{ij}}{\phi_{i,j}}=\frac{\phi_{0i}(M_{-j}U_{-j}^2)_{ij}}{\frac{\phi_{0i}u_{ij}}{u_{jj}}}=\frac{u_{jj}(M_{-j}U_{-j}^2)_{ij}}{u_{ij}} }$

$\displaystyle{ l_{i,j}=\frac{u_{jj}(M_{-j}U_{-j}^2)_{ij}}{u_{ij}}=\frac{(MU^2)_{ij}}{u_{ij}}-\frac{(MU^2)_{jj}}{u_{jj}} }$

$\displaystyle{ L= \left( \begin{array}{ccccccc} 0 & 1 & 88/41 & 373/164 & 7218/2255 & 557/164 & 63/16 \\ \infty & 0 & 47/41 & 209/164 & 4963/2255 & 393/164 & 47/16 \\ \infty & \infty & 0 & 9/4 & 58/55 & 5/4 & 175/82 \\ \infty & \infty & 1 & 0 & 113/55 & 9/4 & 66/41 \\ \infty & \infty & 3 & 2 & 0 & 1 & 525/328 \\ \infty & \infty & 2 & 1 & 168/55 & 0 & 197/164 \\ \infty & \infty & \infty & \infty & \infty & \infty & 0 \end{array} \right) }$

### 平均时间

$\displaystyle{ k_{i,j}=\sum_{k=1}^{\infty}kp^{k}_{i,j} }$

$\displaystyle{ p^{k}_{i,j}=\frac{\phi_{0i}(M^k)_{i,j}}{T'_{i,j}} }$

$\displaystyle{ T'_{i,j}=\phi_{0,i}(MU)_{ij} }$

$\displaystyle{ p_{i,j}^k=\frac{(M^k)_{i,j}}{(MU)_{ij}} }$

$\displaystyle{ k_{i,j}=\frac{(MU^2)_{ij}}{(MU)_{ij}} }$

$\displaystyle{ K= \left( \begin{array}{ccccccc} \infty & 1 & 365/164 & 193/82 & 529/164 & 285/82 & 63/16 \\ \infty & \infty & 201/164 & 111/82 & 365/164 & 203/82 & 47/16 \\ \infty & \infty & 273/82 & 191/82 & 177/164 & 109/82 & 175/82 \\ \infty & \infty & 177/164 & 273/82 & 341/164 & 191/82 & 66/41 \\ \infty & \infty & 505/164 & 341/164 & 669/164 & 177/164 & 525/328 \\ \infty & \infty & 341/164 & 177/164 & 505/164 & 273/82 & 197/164 \\ \infty & \infty & \infty & \infty & \infty & \infty & \infty \end{array} \right) }$

$\displaystyle{ k_{i,i}=(\infty,\infty,273/82,273/82,669/164,273/82,\infty) }$

$\displaystyle{ K-L= \left( \begin{array}{ccccccc} & 0 & 13/164 & 13/164 & 223/9020 & 13/164 & 0 \\ & & 13/164 & 13/164 & 223/9020 & 13/164 & 0 \\ & & 273/82 & 13/164 & 223/9020 &13/164 & 0 \\ & & 13/164 & 273/82 & 223/9020 &13/164 & 0 \\ & & 13/164 & 13/164 & 669/164 &13/164 & 0 \\ & & 13/164 & 13/164 & 223/9020 &273/82 & 0 \\ & & & & & & \end{array} \right) }$

## 流距离算法

import numpy as np
import networkx as nx
# 计算流矩阵
def getFlowMatrix(G, nodelist=None):
if nodelist is None:
FM = nx.to_numpy_matrix(G)

FM = nx.to_numpy_matrix(G, nodelist)
return FM

# 使用函数：FlowMatrix = getFlowMatrix(G,nodelist)

# 计算M矩阵
def getMarkovMatrix(m):
n = len(m)
mm = np.zeros((n, n), np.float)
for i in range(n):
for j in range(n):
if m[i, j] > 0:
mm[i, j] = float(m[i, j]) / float((m[i, 0:].sum()))

return mm

# 使用函数：MarkovMatrix = getMarkovMatrix(FlowMatrix)

# 计算U矩阵
def getUMatrix(m):
I = np.eye(n)
mm = np.linalg.inv(I - m)
return mm

# 使用函数：UMatrix = getUMatrix(FlowMatrix)

# 计算L矩阵
def getLMatrix(m,u):
l = np.zeros((n,n))
mu_square = m.dot(u).dot(u)
for i in range(n):
for j in range(n):
l[i][j] = mu_square[i][j]/u[i][j] - mu_square[j][j]/u[j][j]
return l

#使用函数：getLMatrix(MarkovMatrix,UMatrix)

G=nx.DiGraph()
G.add_edge('source',1,weight=80)
G.add_edge(1,2,weight=50)
G.add_edge(1,3,weight=30)
G.add_edge(3,2,weight=10)
G.add_edge(2,4,weight=20)
G.add_edge(2,5,weight=30)
G.add_edge(4,5,weight=10)
G.add_edge(5,3,weight=5)
G.add_edge(2,'sink',weight=10)
G.add_edge(4,'sink',weight=10)
G.add_edge(3,'sink',weight=25)
G.add_edge(5,'sink',weight=35)
nodelist = ['source',1,2,3,4,5,'sink']
n = G.number_of_nodes()

FlowMatrix = getFlowMatrix(G,nodelist)

MarkovMatrix = getMarkovMatrix(FlowMatrix)

UMatrix = getUMatrix(MarkovMatrix)

LMatrix = getLMatrix(MarkovMatrix,UMatrix)

## 流网络根据流距离嵌入空间

1. 引用错误：无效<ref>标签；未给name属性为levine的引用提供文字