复杂网络理论在《运筹学》中的探究式应用研究——以图与网络分析为例-凯发国际一触即发

1. 引言

《关于实施高等学校本科教学质量与教学改革工程的意见》中指出：要改革“灌输式”以及在教学中过分偏重讲授的教学方法，探索和实践启发式、讨论式、研究式等教学方法。美国学者博耶认为“最好的教学不仅传授知识，同时也改造和扩展知识。” [1] 大学教师的教学活动不仅具有自由性和学术性，还应具有开放性和探究性。学生学习不仅要知道是什么，还应知道需要学习什么，从哪里学和怎样学，最重要的是其是否能够运用所学理论知识解决现实问题。探究式教学模式是在教学活动中以问题为中心、学生在教师指导下通过发现问题、分析问题、提出解决问题方案、解决问题而进行学习的教学模式。” [2] 探究式教学模式更注重学生在学习过程中的亲身体验，而且能够将探究过程中所获得的知识、情感和方法等迁移到实际生活中以解决现实问题。探究式教学模式自新课改以来一直作为中小学教育中的热点问题受到人们的广泛关注，而在大学教学改革中也逐步得到重视。

运筹学，是现代管理学的一门重要专业基础课。它是20世纪30年代初发展起来的一门新兴学科，其主要目的是在决策时为管理人员提供科学依据，是实现有效管理、正确决策和现代化管理的重要方法之一。该学科应用于数学和形式科学的跨领域研究，利用统计学、数学模型和算法等方法，去寻找复杂问题中的最佳或近似最佳的凯发国际一触即发的解决方案。运筹学中把一些研究对象用节点表示，对象之间的关系用连线边表示。用点、边的集合构成图。图论是研究有节点和边所组成图形的数学理论和方法。图是网络分析的基础，根据具体研究的网络对象(如：铁路网、电力网、通信网等)，赋予图中各边某个具体的参数，如时间、流量、费用、距离等，规定图中各节点代表具体网络中任何一种流动的起点，中转点或终点，然后利用图论方法来研究各类网络结构和流量的优化分析。网络分析还包括利用网络图形来描述一响工程中各项作业的进度和结构关系，以便对工程进度进行优化控制。

本文以图与网络分析为例，结合现实生活中常见的大而复杂的网络结构为例，开展复杂网络理论在《运筹学》中的探究式应用研究。本文工作能够对《运筹学》探究式教学提供具体思路和引导过程，以此激发学生的学习兴趣，培养学生探索与研究的能力。

2. 《运筹学》课程中图与网络分析的教学内容分析

2.1. 学生情况

以上海理工大学管理学院为例，运筹学是学院的基本课程，所有专业的学生都需要学习，基本上均是大二上学期的必修课程。具体开设运筹学课程的专业有：财政税务系、工商管理系、工业工程系、公共管理系、国际经济与贸易系、会计系、交通系统工程系、金融系、系统科学系、信息管理与信息系统系。另外，需要指出的是，这里仅统计了《运筹学》课程。其他课程也可能涵盖图论与网络问题，如离散数学课程。

2.2. 学习内容

图与网络理论在近数十年里是运筹学领域发展非常活跃的分支之一，特别是随着计算机的出现和发展，其理论与应用得到了巨大的推进，现已成为管理科学、计算机科学、通信理论、自动控制、系统工程与运筹学，以及军事科学等学科领域中的一种重要的数学方法和工具，这些领域中的许多问题都可以用图论及网络模型加以描述和求解。图与网络理论之所以能够得到广泛的应用与发展，主要是因为它有适应性很强的构模能力，对实际问题的描述很直观，其模型易于计算机实现，而且能够很方便地将一些复杂问题分解或转化为一系列能够用一些有效方法求解的子问题 [3] 。

2.3. 学习任务

掌握图与网络分析的基本知识，理解树的定义及最小树的求解原理、最短路问题及其求解算法、最大流问题及其求解算法、最小费用流问题求解原理等。在现实问题的图或网络的表示、问题分析、问题求解、形成结论的过程中，引导学生体验在解决问题不断探究中掌握科学原理的过程．教学重点是图与网络的表示、最小生成树算法、最短路求解算法、最大流求解算法、并真实应用到实际案例中并得到准确求解。

3. 复杂网络理论

随着人类社会的发展及科技的进步，以internet为代表的信息技术随之获得了高速发展，使得人类社会逐步进入到网络互联时代 [4] 。随着社交软件的发展、人工智能的广泛应用、自动驾驶技术等基于网络的科技日益繁荣，人类社会的网络化正在深刻改变着人们的生活习惯和生活方式，对人们的日常生活、工作、学习等多个方面均产生了深远的影响。今天，人们已经生活在一个充满着各种不同类型的复杂网络的世界中。但是《运筹学》课程中的图和网络的结构通常很简单，节点数和边数通常很少。复杂网络通常结构复杂、网络进化、连接多样性、动力学复杂性、节点多样性、多重复杂性融合。现实社会中的网络结构通常具备上述一个或多个复杂性的特征。因此，研究现实社会中的事物间的连接关系，单纯性依赖《运筹学》中的图和网络知识不足与得到充分研究。因此，复杂网络理论成为探索研究现实世界间连接关系的必须工具。

复杂网络主要是以数学、统计物理学和计算机等为分析工具，将不同主体间的联系，以相对直观的模式来表示。研究发现复杂网络可以很好地刻画社会科学、自然科学、管理科学与工程等领域的复杂系统 [5] 。比如社交网络、交通网络、电力网络都是典型的现实复杂网络。在20多年的网络科学的研究发展，复杂网络为科研领域得到突破性的研究成果，比如社交网络呈现的幂律规律、高阶网络传播动力学中的双稳态等，网络科学促进了控制领域、预测领域的发展。复杂网络是21世纪发展较快的一门交叉学科，但是目前尚未有严格的定义。从字面意义上理解，复杂网络就是表现出高度复杂性的网络。钱学森曾概括出复杂网络即是具有自组织、自相似、吸引子、小世界、无标度中部分和全部性质的网络结构 [6] 。维基百科中给出，具有数量巨大的节点和节点间具有错综复杂关系的网络结构称为复杂网络 [7] 。

从图论的角度，一个网络可以表示为由有限个节点和连接这些节点间的边所构成的图 [4] ，记为 g ( v , e ) ，其中节点的个数记为 n = | v | ，边数记为 m = | e | 。 e 中每条边都是 v 中两个节点相对应。从数学角度，一个图通常可以用邻接矩阵的形式来表示 [4] 。例如对于无权无向图， g ( v , e ) 可以用 n × n 矩阵 a 来表示，其元素为 a i j ( i , j = 1 , ⋯ , n ) ，其中，当节点 i 与节点 j 相连时，元素 a i j 为1，相反，当节点 i 与节点 j 不相连时，元素 a i j 为0。所以对于无向网络，其邻接矩阵为对称矩阵并且其元素为1或0。对于无权有向图，如果节点 i 有指向节点 j 时，对应元素 a i j 为1，否则记为0。对于加权无向图，如果节点 i 与节点 j 有权值为 w i j 的边时，则 a i j 为 w i j ，否则记为0。类似的，对于加权有向图，如果节点 i 有指向节点 的权值为 w i j 的边时，则 a i j 记为 w i j ，否则为0。依据邻接矩阵的方法来表示一个图，可以很清楚的了解到网络中任意两个节点之间的连接情况。图的邻接矩阵表示的另一个用处是，可以使用矩阵分析的方法来研究图的很多性质。特别需要指出的是，这里复杂网络的数学语言与《运筹学》中的图和网络的概念一致。

4. 引入复杂网络理论的“图与网络分析”探究式教学实施过程

4.1. 探究式分析网络结构

首先由《运筹学》中“图与网络分析”的经典案例开始，即哥尼斯堡七桥问题。18世纪在哥尼斯堡城有一条河流(pregel河)流过，河中有两个小岛(见图1(a))，岛与岸及岛与之间共有七座桥相连。于是流传出了这样一个问题：一个人能否从一个地方出发通过每座桥一次且仅通过一次，最后回到出发点？

欧拉将两岸及两岛分别表示为节点(用a、b、c、d表示)，将连通两地之间的桥表示为连接两节点之间的连线(称之为边)，于是可以得到一个由节点与边组成的图(见图1(b))，该图即为哥尼斯堡七桥问题的图论模型，且问题转化为：从a、b、c、d中任意一点出发，可否找到一条路径通过每条边一次且仅一次，最后回到出发点。欧拉证明了这样的走法是不存在的，并给出了这类问题的一般结论：任何具有超过两个奇点(顶点的度(或次)为奇数的点)的图g必不能一笔画成。

探究性教学实施过程：通过课本中的典型例题，拓展到现实世界中的网络，引导学生如何解决现实网络的结构问题、最短路径问题等。涉及的教学方法：探究性引导为主、集体讨论、展示法等。教学资源：现实网络的数据、电脑平台和软件安装等。

探究性问题1 对于有 n 个节点构成的图或网络，其中 n 值较大或很大，如何快速求各个顶点的度呢？度的分布又会呈现出什么规律呢？

对于大规模的图或网络，简称复杂网络，可以分析其多个网络属性。以如下真实某高校的邮件关系网络为例 [8] ，网络节点代表个体，网络间的连边代表个体间通过邮箱互相联系。该网络的结构见图2，基本属性见表1。

对于节点数很少的图或网络，可以通过手动方式可以计算其网络节点中各个节点的度，网络度的分布等情况，但是对于节点数很大的复杂网络，现实世界中所面临的网络大多是结构复杂的复杂网络，因此对于现实网络的分析就需要借助复杂网络的分析工作。目前分析复杂网络结构属性的工作有很多，常见的有matlab，python，networksx，gephi，pajek，r等工作，本文以matlab为例来探究复杂网络的分析工作。还以图2的复杂网络为例，借助于matlab工具展示其其他方面的结构属性。其网络度分布结果见图3。通过图3的度分布，发现该网络的度分布呈现出类似幂律的分布特征。通过本例题，同时可以引导同学们呈现幂律分布特征的网络并不是一种特殊情况，反而在现实世界中大多数的网络结构都呈现出此特征。

4.2. 探究式研究最短路问题

最短路问题的定义描述为：设 g = ( v , e ) 为连通图，图中各边 ( v i , v j ) 有权 l i j ，( l i j = ∞ 表示 v i , v j 间无边)， v s , v t 为图中任意两点，求一条路径 μ ，使它是从 v s 到 v t 的所有路径中总权最小的路。即： l ( μ ) = ∑ ( v i , j ) ∈ μ l i j 最小。

最短路径问题作为图论和网络研究的基础内容之一，其计算算法已经历了半个多世纪的研究和发展。其中具有开创性代表的包括dijkstra算法、bellman-ford算法，这两个算法属于目前研究和应用都比较成熟的标号类算法 [9] 。算法思想是为网络中每个节点 v i 设置标号 p ( v i ) 用于存储维护节点 v s 到节点 v t 的路径长度；设置前驱标号 λ ( v i ) 用于存储该节点的前驱节点，算法迭代过程通过不断修改这些标号来计算最短路径。dijkstra算法和bellman-ford算法的区别在于，dijkstra算法不能应用于负权的网络，而bellman-ford算法的优势在于可以识别网络中的负权环，但是这两种算法的计算效率都不是很好。除此之外，目前使用较多的还有基于这两种算法的改进算法即johnson’s算法，而且经过改进的johnson’s算法比较适合于稀疏图的所有节点对最短路径的计算，适用于计算密集图的所有节点对最短路径的计算的floyd-warshall算法。

经典算法在搜索过程中会重复遍历和计算路径长度，搜索方式具有盲目性，造成计算资源的严重浪费，经典算法的低效严重制约了其在复杂网络中的应用。现有绝大数最短路径算法都是基于经典算法的基础上，使用不同的数据结构、节点选取策略以及各类加速技术进而改进和延展出来的算法。尽管这些近似算法能够在一些复杂网络中高效计算最短路径，但该项研究仍处于发展阶段、提升空间很大，需要研究者不断创新和提高。

探究性问题2 对于有 n 个节点构成的图或网络，其中 n 值较大或很大，如何快速求解两点对或任意两点间的最短路问题？

由于现实网络大多结构复杂，经典算法因其计算复杂度高的普遍特性，无法适用于规模巨大、结构复杂的各类真实复杂网络。《运筹学》课本中的基本算法已无法真正应用到实际网络的最短路问题求解过程中。以如下果蝇的基因功能连接网络为例 [8] ，网络节点代表某基金，网络间的连边代表基因之间互相存在联系。该网络的结构图见图4，该图中边的权重通过边的连线粗细来直观展示，其中权重越大边的连线越粗。基本属性见表2。

借助于matlab工具中的shortestpath函数，对于该网络其实际调用为dijkstra算法，展示节点1到节点1000的路径长为20.7909，路径为1→3→871→889→947→42→1107→1602→597→578→1000。对于该算法计算时间较短，但如果网络庞大时，其效率就会明显降低。在权衡最短路径的计算效率和计算准确率的前提下，近似计算复杂网络中的最短路径成为了一个有效解决途径。下面列出几类常用的适合现实复杂网络的改进最短路求解算法，其通常具有高效和较为准确的特征。

1) a*算法–最佳优先的搜索策略

该算法在搜索过程中引入估价函数来评估网络中节点的重要性，节点估价值越小则该节点出现在最短路径上的可能性越大。区别于dijkstra 算法，a*算法使用估价函数作为距离标号。所以其算法的优略关键在于选取一个恰当的估价函数，估价函数选取的优劣直接影响到算法的搜索效率和准确率 [10] 。

2) 基于缩略网络的最短路近似算法

对于基于缩略网络的算法中，首先会选择部分顶点作为路标(landmark)放入集合l中，然后计算出集合l中每个landmark节点到图g中任意节点的最短路径长度。顶点u的缩略可以简单表示为 { ( w , d ( u , w ) ) | w ∈ l } ，其中 d ( u , w ) 表示 u 和 w 之间的最短路径长度。对于任意节点 u 和 v ，它们之间的最短路径长度估计值都可以表示为 d ( u , w ) d ( w , v ) (其中 w ∈ l ) [11] 。landmark的选择通常分为两种，一种是随机抽取，一种是按特征抽取。不同的选取方式直接影响算法的效率。有研究发现抽取中心性高的节点作为landmark比随机选取节点的效率更高。其次另一个重要问题是广度优先搜索(breadth-first search，简称bfs)，在landmark集合确定后，下一步需要对大量节点进行广度优先搜索来计算landmark到任意点的最短路径。

3) 基于空间坐标的算法

在基于坐标coordinates的算法中，首先将网络嵌入到一个几何空间中，保持嵌入几何空间新图中的节点间的最短距离与原图的最短路径长度相同。然后通过计算几何空间中节点的坐标值来计算图中任意节点间的最短路径长度。将图嵌入到几何空间的过程决定此类算法的好坏 [11] 。

4) 基于区域中心点的最短路径近似算法

区域中心点距离的最短路径(centers distance of zone，简称cdz)算法主要是利用网络中度值较大的节点会有更多的最短路径通过的思想，首先将网络中的节点依据度值进行排序，再选取其中的10%作为局部区域的中心点，从各个中心开始进行宽度优先遍历整个网络，计算网络中每个节点到各个局部中心点之间的距离，将距离各个中心点较近的节点与其中心点一起划分为一个区域，然后将各个中心点映射为一个新的网络，通过原网络中一条实际存在的路径计算新网络中各个中心点之间的距离 [12] 。但是该算法在区域划分时需要遍历整个网络，当网络规模较大时，算法的时间复杂度和空间复杂度都很高。

5) 基于最优覆盖策略和路标宽度遍历的最短路径近似算法

最优覆盖策略和路标宽度遍历的最短路径近似算法(landmarks-bfs, lbfs)，利用最优覆盖策略对网络中的节点对进行随机选取，然后采用dijkstra算法计算节点之间的最短路径，将在最短路径求解中出现频率最高的节点加入到路标landmarks集合，并删除当前最短路径中所有经过该节点的路径，重复这个操作直到路标集合中的节点数量满足设定的阈值。然后通过路标集合中的节点将整个网络划分为若干个子网络，并继续求得网络中的每个节点到各个路标的路径，其中距离路标节点最短的路径即为所求的近似最短路径 [13] 。

6) 基于其他网络属性的方法

除上述几类算法之外，还有基于其他网络属性的方法，包括最大度搜索策略算法(high degree strategy，简称hds)，k-shell的最短路径近似算法等。hds最初有adamic等人提出 [14] ，但由于基于节点度值只考虑了节点的局部特性，其计算准确率并不高，后来经过kim等人对路径序列进行改进，包括删除路径上的圈以及原路返回的步数改进等，提高了最短路径的计算准确率 [15] 。基于k-shell的最短路径近似算法，利用节点的k-shell值进行网络划分并引导搜索路径，利用超点聚合处理k-shell子网来降低路径搜索中节点和连边的规模，通过在路径搜索过程使用双向搜索树方法提高算法的计算效率和准确率 [16] 。

5. 总结

探究性教学对培养学生创新思维和创新能力具有重要作用。《运筹学》课程在传统教学模式中，教师一般采用板书或者ppt的方式。在讲解“图与网络优化”章节时，除讲授基本知识外，主要讲授其中涉及的基本经典算法。但是，随着现代社会的发展，所面临的现实问题更为复杂，仅仅依靠这些基本算法往往并不能真正解决现实问题，或者效率低或无法直接采用。因此，本文以“图与网络优化”章节为例，将复杂网络理论引入到《运筹学》中开展探究性教学。首先通过对图与网络分析课程内容和探究性教学的重要性进行分析，其次介绍了复杂网络理论及其重要应用性进行介绍，然后，重点介绍引入复杂网络理论到“图与网络分析”探究式教学实施过程，最后做出结论。以此激发学生的学习兴趣，培养学生探索与研究的能力。

基金项目

2023年“上海理工大学本科课程思政示范课程建设项目”专项资助。

notes

^*通讯作者。

参考文献