基于马尔科夫链的流网络分析 - 版本历史

2025年1月18日 (六) 01:44 Taoruyi

2025-01-18T01:44:10Z

2025年1月18日 (六) 01:42 Taoruyi

2025-01-18T01:42:44Z

Jake：/* 参考文献 */

2024-04-15T01:51:30Z

参考文献

薄荷：/* 集智课程 */

2021-11-11T02:28:02Z

集智课程

薄荷：/* 相关词条 */

2021-11-11T02:24:41Z

薄荷：/* 流量分析 */

2021-11-11T02:17:08Z

流量分析

思无涯咿呀咿呀：/* 从流网络到马尔科夫链的转换 */

2020-12-18T06:34:40Z

从流网络到马尔科夫链的转换

思无涯咿呀咿呀：/* 从流网络到马尔科夫链的转换 */

2020-12-18T06:29:41Z

从流网络到马尔科夫链的转换

思无涯咿呀咿呀：/* 从流网络到马尔科夫链的转换 */

2020-12-18T06:25:24Z

从流网络到马尔科夫链的转换

2020年12月18日 (五) 06:18 思无涯咿呀咿呀

2020-12-18T06:18:49Z

@@ 第13行： / 第13行： @@
 i到j的总流记为：<math>t_{i,j}=T_0\frac{u_{0,i}u_{i,j}}{u_{i,i}}</math>。
-i到j的首达流记为：<math> \phi_{i,j}=T_0 \frac{u_{0,i}u_{i,j}}{u_{i,i}u_{j,j}}</math>。 其中T<sub>0</sub>为从源输入到整个网络的流量，也就是IS（参看[[流动网络]]）。根据这两个公式，可以计算任意网络任意节点对的总流和首达流。
+i到j的首达流记为：<math> \phi_{i,j}=T_0 \frac{u_{0,i}u_{i,j}}{u_{i,i}u_{j,j}}</math>。 其中T<sub>0</sub>为从源输入到整个网络的流量，也就是IS（参看[[流网络]]）。根据这两个公式，可以计算任意网络任意节点对的总流和首达流。
 i到j的平均时间：<math>k_{i,j}=\frac{(MU^2)_{ij}}{(MU)_{ij}}</math>
@@ 第27行： / 第27行： @@
 对于平衡流动来说，我们总可以将整个流系统看作是一个多粒子沿着网络流动的系统。例如，对于图1所示网络，当某个处于1号节点的粒子往外流动的时候，它可能会跳到2号节点，也可能会跳到3号节点。可以想到，由于1到2号节点的流量比到3号的节点大，所以这个粒子更有可能跳到2号节点。我们不妨假设粒子跳转到某个节点的概率是与这条边上的流量成正比的。也就是说，粒子会以5/8=50/80的概率从1跳到2，而以3/8=30/80的概率从1到3。同样的道理，当粒子跳入到任何一个节点后，它都会继续沿着边以概率跳转。
-我们可以写出这个网络所对应的流矩阵（参见[[流动网络]]）如下：
+我们可以写出这个网络所对应的流矩阵（参见[[流网络]]）如下：

@@ 第1行： / 第1行： @@
 一个平衡的[[流网络]]可以自然地转变成[[马尔科夫链]]，而[[马尔科夫链]]是数学家们研究得非常深入而透彻的数学对象，因此这为我们更好地分析[[流网络]]提供了便利条件。
-下面给出基本计算简表。定义：流矩阵F，对应的马尔科夫链矩阵M
+下面给出基本计算简表。
-<math>
+定义：流矩阵F，对应的马尔科夫链矩阵M
-m_{ij}=\frac{f_{ij}}{\sum_{j=1}^{N+1}f_{ij}}
+M中的元素为：<math>m_{ij}=\frac{f_{ij}}{\sum_{j=1}^{N+1}f_{ij}}</math>
-基础矩阵<math>
+定义基础矩阵：<math>U=I+M+M^2+\cdot\cdot\cdot=(I-M)^{-1}</math>, 其中[math]I[/math]单位阵
 U=I+M+M^2+\cdot\cdot\cdot=(I-M)^{-1}
-</math>
+[math]U[/math]中的元素[math]u_{i,j}[/math]表示i到j所有可能路径的影响，包括直接路径和间接路径。
-i到j的总流：<math>
-t_{i,j}=T_0\frac{u_{0,i}u_{i,j}}{u_{i,i}}
+而流网络中一些关键的量可以由流矩阵M和基础矩阵U定义出来。
-</math>，i到j的首达流：<math>
- \phi_{i,j}=T_0 \frac{u_{0,i}u_{i,j}}{u_{i,i}u_{j,j}}
+i到j的总流记为：<math>t_{i,j}=T_0\frac{u_{0,i}u_{i,j}}{u_{i,i}}</math>。
 </math>
-其中T<sub>0</sub>为从源输入到整个网络的流量，也就是IS（参看[[流动网络]]）。根据这两个公式，可以计算任意网络任意节点对的总流和首达流。
+i到j的平均时间：<math>k_{i,j}=\frac{(MU^2)_{ij}}{(MU)_{ij}}</math>
-−
-i到j的平均时间：<math>
+i到j的首达平均时间：<math>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}}</math>。其中<math>M_{-j}</math>表示将M的第i行全置为0，<math>U_{-j}=I+M_{-j}+M_{-j}^{2}+\cdot\cdot\cdot=(I-M)^{-1}</math>。

@@ 第688行： / 第688行： @@
 历史上，经济学家最早给出了U矩阵（也称为Leontief矩阵）的定义，请参照[[投入产出分析]]。后来生态学家Finn将这种分析方法引入到<ref name="finn"/>了生态流网络中用于分析能量流网络。Patten、Ulanowicz等人将这套方法系统化，提出了Environ理论<ref name="environ">{{cite journal | last = Patten| first = Bernard C.| date = 1982 | title = Environs: Relativistic elementary particles for ecology| journal = The American Naturalist| volume = 119| pages =  179-219}}</ref><ref>{{cite journal | last = Patten| first = Bernard C.| date = 1985 | title = Energy Cycling in the Ecosystem| journal = Ecological Modelling| volume = 28| pages =1-71}}</ref><ref>{{cite journal | last = Ulanowicz| first = Roberte E.| last2= Wolff | first2=Wilfried F.| date = 1990 | title = Ecosystem Flow Networks: Loaded Dice?| journal = Mathematical Biosciences| volume = 103| pages =45-68}}</ref>。随后，这些人又将这套方法进一步扩展以讨论能量流的循环与存储问题<ref>{{cite journal | last = Patten| first =  Bernard C.| last2= Higashi| first2=Masahiko| last3= Burns | first2=Thomas P.| date = 1990 | title = Trophic Dynamics in Ecosystem Networks: Significance of Cycles and Storage| journal = Ecological Modelling| volume = 51| pages =41-28}}</ref>以及能量流的节律等问题<ref>{{cite journal | last2 = Burns| first2 =  Thomas P.| last= Higashi| first=Masahiko| last3= Patten| first2=Bernard C.| date = 1993 | title = Network trophic dynamics: the tempo of energy movement and availability in ecosystems| journal = Ecological Modelling| volume = 66| pages =43-64}}</ref>。
-将流网络建模成马尔科夫链不仅仅可以讨论流量、时间等问题，还可以讨论如电导经过某点中转的平均首达时间等问题。<ref>{{cite journal | last = Hilfer| first =  R.| last1= Blumen| first=A.| date = 1988| title = Probabilistic interpretation of the Einstein relation| journal = Physical Review A| volume = 37| pages =578-581}}</ref>
+将流网络建模成马尔科夫链不仅仅可以讨论流量、时间等问题，还可以讨论如电导经过某点中转的平均首达时间等问题。<ref name="Einstein">{{cite journal | last = Hilfer| first =  R.| last2= Blumen| first2=A.| date = 1988| title = Probabilistic interpretation of the Einstein relation| journal = Physical Review A| volume = 37| pages =578-581}}</ref>
 <references/>

@@ 第699行： / 第699行： @@
 ==编者推荐==
 ===集智课程===
 ====[https://campus.swarma.org/course/3533 复杂网络的数学建模与应用 | 网络科学第三期]====
 网络科学已经跨过了二十个年头迎来了第三个十年。其发展历程大致如下:

@@ 第695行： / 第695行： @@
 [[流网络]]
 [[category:流网络]]
 [[Category:旧词条迁移]]

@@ 第266行： / 第266行： @@
 如果从i到j的所有路径中不存在着循环，如下图所示的树状结构：
-[[File:simpletreeill.PNG|300px]]
+[[File:simpletreeill.png|300px]]
 我们很容易计算出从1到4的总流量为：

@@ 第38行： / 第38行： @@
 我们可以写出这个网络所对应的流矩阵（参见[[流动网络]]）如下：
-[[File:fluxmatrix.png||示例网络的流量矩阵]]
 其中，矩阵外围的数字为对节点的编码。0对应源，6对应汇。阴影区域对应网络的实线部分，为我们关注的节点主体。

@@ 第32行： / 第32行： @@
 ==从流网络到马尔科夫链的转换==
-[[File:exampleflownetwork.PNG|500px|framed|图1：一个示例流网络]]
+[[File:exampleflownetwork.png|500px|framed|图1：一个示例流网络]]
 对于平衡流动来说，我们总可以将整个流系统看作是一个多粒子沿着网络流动的系统。例如，对于图1所示网络，当某个处于1号节点的粒子往外流动的时候，它可能会跳到2号节点，也可能会跳到3号节点。可以想到，由于1到2号节点的流量比到3号的节点大，所以这个粒子更有可能跳到2号节点。我们不妨假设粒子跳转到某个节点的概率是与这条边上的流量成正比的。也就是说，粒子会以5/8=50/80的概率从1跳到2，而以3/8=30/80的概率从1到3。同样的道理，当粒子跳入到任何一个节点后，它都会继续沿着边以概率跳转。

←上一版本		2020年12月18日 (五) 06:18的版本
第1行：		第1行：
	一个平衡的[[流网络]]可以自然地转变成[[马尔科夫链]]，而[[马尔科夫链]]是数学家们研究得非常深入而透彻的数学对象，因此这为我们更好地分析[[流网络]]提供了便利条件。		一个平衡的[[流网络]]可以自然地转变成[[马尔科夫链]]，而[[马尔科夫链]]是数学家们研究得非常深入而透彻的数学对象，因此这为我们更好地分析[[流网络]]提供了便利条件。
		+	下面给出基本计算简表。定义：流矩阵F，对应的马尔科夫链矩阵M
		+	<math>m_{ij}=\frac{f_{ij}}{\sum_{j=1}^{N+1}f_{ij}}</math>
		+	基础矩阵:<math>
		+	U=I+M+M^2+\cdot\cdot\cdot=(I-M)^{-1}
		+	</math>
		+
		+	<math>
		+	m_{ij}=\frac{f_{ij}}{\sum_{j=1}^{N+1}f_{ij}}
		+	</math>，
		+
		+	基础矩阵<math>
		+	U=I+M+M^2+\cdot\cdot\cdot=(I-M)^{-1}
		+	</math>
		+	i到j的总流：<math>
		+	t_{i,j}=T_0\frac{u_{0,i}u_{i,j}}{u_{i,i}}
		+	</math>，i到j的首达流：<math>
		+	\phi_{i,j}=T_0 \frac{u_{0,i}u_{i,j}}{u_{i,i}u_{j,j}}
		+	</math>
		+
		+	其中T<sub>0</sub>为从源输入到整个网络的流量，也就是IS（参看[[流动网络]]）。根据这两个公式，可以计算任意网络任意节点对的总流和首达流。
		+
		+	i到j的平均时间：<math>
		+	k_{i,j}=\frac{(MU^2)_{ij}}{(MU)_{ij}}
		+	</math>，i到j的首达平均时间：<math>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}}
		+	</math>
		+
		+	其中<math>M_{-j}</math>表示将M的第i行全置为0，<math>U_{-j}=I+M_{-j}+M_{-j}^{2}+\cdot\cdot\cdot=(I-M)^{-1}</math>。

−	~~下面给出基本计算简表。定义：流矩阵F，对应的马尔科夫链矩阵M~~
−	~~<math>m_{ij}=\frac{f_{ij}}{\sum_{j=1}^{N+1}f_{ij}}</math>~~