设计机分类系统：基于马尔科夫过程和图论的实现。

为确定上文提到的各种理论的类别，我们从马尔科夫过程的特性出发，然后应用图论，建立一套设计机的分类系统。在讨论有限马尔科夫过程或马尔科夫链的类型时，一个有用的概念与不同状态之间是否可达相关。可达的状态，即互相可以到达的状态，构成了一条不可再分的链——不能分解，而且它的状态被认为是不变的（Feller，1957）。相反，不可达的状态被称为临时状态，从这个意义上说，一旦过程离开这些状态，就不会回来。如果只有一个状态是不变的，所有其他状态都会是临时的，那么这个状态被称为吸收态，而链则被称作吸收马尔科夫链。

一个直观上更吸引人的链的分类是通过图论来分类。众所周知，方程组可以表示为有向的线性图，其中变量被表示为图中的节点或顶点，而方程系数则表示为连接节点的弧或者线段。确实，在特定的案例中用图论的概念来解决方程组问题比较简单。正如我们在上一章中提到的，可以用有向图来表达方程11.2或11.19中给出的马尔科夫过程，如图11.1。哈拉里和利普斯坦（Harary and Lipstein，1962）称这个结构为马尔科夫有向图，这些作者也展示了图论可以用于将马尔科夫链分类。而且，用图论展示的马尔科夫过程可以被比作一个通信系统，其中节点代表信息发射器和接收器，边代表通信频道。这里描述的设计过程和社会权力结构的类比起源于这个解释（French，1956；Harary，1959；Lambiotte et al.，2011），而图论同样把这一过程与前面的设计方法联系起来，如第10章。

上文曾间接提到，图11.1可以很好地体现马尔科夫链中的可达性概念。如果像图11.1一样，存在一条从一个节点到另一个节点的可能路径，这条路径可以是有向的或无向的，那么这个节点或状态对于其他节点或状态来说是可达的。这种可达性实际上是对连通性的一种测度，图形分类最为完善也为本书所一直使用，因而马尔科夫链使用了这些概念。

对于不可约链，所有状态均不变且相互可达，可以分为“完全连接链”和“强连接链”。在完全连接链中，所有状态都互相直接可达，即：矩阵［ajk］和［pjk］的所有单元均为正值。强连接链包含了不直接可达但间接可达的状态，当矩阵的指数m＜n，整个均为正值。(www.xing528.com)

我们也从连通性的角度将不可约链分为三种类型。在“单方面连接链”中，一条链可以分为一个具有不变状态的不可再分集和其他临时状态集。“弱连接链”可以被分为两个或两个以上的不可再分集，“无连接链”可以完全分为两条或两条以上的链，然后再按照上述方法分类。图11.2给出了这种分类方法的图示，可视化地展示了这些可达性和连通性概念的含义。

图11.2　设计问题作为马尔科夫有向图的分类

就马尔科夫过程而言，不可约链能够达成所有要素真正协调的解决方案，然而在可约链中，所有要素都不能协调。在单方面连接链中，一个要素或一个要素集占主导地位，而与临时状态相关联的要素没有作用。然而，在弱连接链中，不会达成单一解决方案，因为两个或两个以上的要素集显示了独立解决方案，而且由于不可达性，永远不会融合。真正的协调得到的结果只能使用不可约链。在本章剩下的部分将只讨论强连接链和完全连接链，因为只有这些链才能得出非凡的解决方案。在现实中，可约链可能与许多无法解决或只能部分解决的设计问题相匹配。从根本上说，只有当每个节点或行动者之间有直接或间接的连接才能实现真正的协调。