线性代数教学中网络科学问题的渗透

汤龙坤

摘  要：特征值和特征向量问题是线性代数课程中的一个重要学习内容。为了让学生了解科学前沿问题并提高学习兴趣，在讲授矩阵特征值与特征向量的概念、计算方法和几何意义时，引入复杂网络中节点重要性的排序和同步问题，举例说明特征值和特征向量在其中的应用，以此将网络科学中的研究问题渗透到线性代数的教学中。

关键词：线性代数;特征值;特征向量;复杂网络;PageRank算法

中图分类号：G642 文献标志码：A 文章编号：2096-000X（2019）05-0059-03

Abstract： The eigenvalue and eigenvector problem is an important learning content in the course of linear algebra. In order to let students understand the frontier issues of science and improve their interest in learning， when introducing the concepts， calculation methods and geometric meanings of matrix eigenvalues and eigenvectors， the problem of ordering and synchronization of node importance in complex networks is introduced， and eigenvalues and eigenvectors are illustrated. In its application， the research problems in network science are infiltrated into the teaching of linear algebra.

Keywords： linear algebra; eigenvalue; eigenvector; complex network; PageRank algorithm

引言

線性代数是大学生一门必修的公共数学基础课程。不像高等数学课程，其中的概念和方法与中学数学有着紧密联系，而线性代数课程中的概念相对抽象，方法新颖，知识体系几乎完全不同于中学数学。对于刚入校的大学生来说，很难马上适应并学好该课程，更糟糕地还会出现厌学情绪。十几年的教学经验和与学生的接触，发现学生普遍觉得线性代数比高等数学更抽象更难理解，常常会问“线性代数到底有啥用？”。

线性代数在物理、生物、信息和工程以及最近新兴的网络科学领域有广泛地应用。复杂网络是近20年刚兴起并倍受关注的热点研究领域，目前已发展成为网络科学与工程学科，这是一个新兴的交叉学科，它涵盖了数学、物理、信息、计算机、生物和社会学等领域[1，2]。网络科学的研究仍处于起步阶段，许多前沿科学问题不需高深的数学理论，只要大学的数学知识就足够。本文就线性代数中的特征值和特征向量的内容，在基本概念和计算方法的基础上，通过几何意义以及一些注记加深对特征值和特征向量的理解后，借助复杂网络中节点重要性的排序和同步问题，将网络科学问题渗透到线性代数的教学中。

一、特征值与特征向量

线性变换x→Ax可能使得向量x向各个方向移动，但对于某些特殊的向量，A对向量的作用导致向量的旋转、伸缩和变向，这些简单的变化可由A的特征值和特征向量描述和刻画。

定义[3，4]：设A为n×n矩阵，x为非零向量，若存在数λ使得

Ax=λx（1）

成立，则λ称为A的特征值，而x称为A的对应于λ的特征向量。

（1）式也可以写成

（A-λE）x=0（2）

于是，特征值问题转化为线性方程组解的问题。由于x是非零向量，即（2）式有非零解，根据方程组解唯一性的充要条件，可得特征方程

|A-λE|=0（3）

由（3）式可求得矩阵A的特征值，进而求解（2）可得对应的特征向量，下面举个简单的例子。

例1：设A=1  43  2，求A的特征值和特征向量。

解：由特征方程|A-λE|=0，即λ2-3λ-10=0，可求得两个特征值λ1=5，λ2=-2。

为求对应的特征向量，分别将两个特征值代入（2）式并求解。

对于λ1=5， A-λE～-1  10   0，故（2）式的通解为c11， 且c≠0的向量是λ1=5对应的特征向量。

对于λ5=-2， A-λE～3  40  0，故（2）式的通解为c-4 3， 且c≠0的向量是λ2=-2对应的特征向量。

对应于λ的所有特征向量的集合称为λ的特征空间，因此，λ1=5的特征空间为过点（1，1）和原点的直线，而λ2=-2的特征空间为过点（-6，5）和原点的直线。在λ1=5（λ2=-2）的特征空间上去一个非零向量x作线性变换x→Ax，相当于该向量在相同（相反）的方向伸长5倍（2倍）。

注：（1）特征值对应的特征向量并非唯一的，甚至无穷多个，但他们之间属于同一个特征空间。（2）低阶方阵的特征值容易由特征方程求得，但对于高阶方阵，很难从特征方程求出，往往求助于数值计算的方法，比如幂法和反幂法等求特征值和特征向量的数值解法。（3）一般说，特征值的模大于1表示向量经过变换后，向量的长度是伸长的，而模小于表示经过变换后，向量的长度缩小了。

二、图的邻接矩阵和拉普拉斯矩阵

信息科学、交通运输以及社会经济等领域中的单元（或个体）间的关系往往可以用几何图来描述，进一步地还可以用邻接矩阵来表示。例如，万维网可定义为一个图，利用图的邻接矩阵可研究网页的重要性，寻找网页的枢纽。

例2. 设有4个网页的图如图1，其中，节点表示网页，连接（或边）表示超链接。图1-（a）为无向图表示网页间彼此有超级链接，是双向的（这里用不带箭头的边来表示），而图1-（b）表示为有向图，网页到网页的连接有出链和入链之分。

对于无向图，若第i个网页与第j个网页有边记aij=1，否則aij=0。对于有向图，若第j个网页有边指向第i个网页记aij=1，否则aij=0。那么图1-（a）和图1-（b）的邻接矩阵分别为

A1=0 0 1 10 0 0 11 0 0 11 1 1 0和A2=0 0 1 11 0 0 01 1 0 11 1 0 0

（a）无向图          （b）有向图

图1 4个网页间的超级链接图

拉普拉斯矩阵定义为L=D-A， 其中A为图的邻接矩阵，而D为各个节点的度（有向图为入度）构成的对角矩阵。那么，图1-（a）和图1-（b）的拉普拉斯矩阵分别为

L1= 2  0 -1  -1 0  1  0  -1-1  0  2  -1-1 -1 -1   3和L2=2  0 -1 -1-1 1  0  0-1 -1 3 -1-1 -1 0  2

利用图的邻接矩阵和拉普拉斯矩阵的特征值或特征向量（矩阵中的最小和最大非零特征值及特征向量在实际问题中有广泛应用），我们可以研究网页重要性的排序问题，传输网络的边负载问题，社团的划分问题以及网络同步能力等问题。

三、复杂网络中的科学问题

（一）节点重要性的排序问题

网络中的重要节点对网络的结构和功能有重要的影响。比如，微博中的几个最有影响的节点所发的微博能迅速传遍整个微博网络;全球1%的公司控制了40%的全球经济;少量的几个重要节点受蓄意攻击后导致整个电网的崩塌等[5]。所以，对网络中节点重要性的排序和重要节点的挖掘有重要的理论和实际意义。

网络时代的今天，百度和Google等搜索引擎已经融入到人们的生活中。在Google的搜索页面搜索框输入关键词，为什么能在短短零点几秒的时间内找到百万条甚至千万条的相关页面，并按最相关或感兴趣（节点重要性）的排序排好？

1998年斯坦福大学计算机科学院的新博士生拉里·佩奇和博士二年级的谢尔盖·布林发明了PageRank算法后，编写了PageRank搜索工具用于相关性（节点重要性）排序。命名为Google，这是 Googol的变体，Googol是一个数字名词，表示10的100次方。正是PageRank搜索算法革命性的改变网络世界，而隐藏在这个算法背后的数学就是矩阵的特征值和特征向量的问题[6，7]。下面举一个仅有4个网页的简单例子，网页链接关系如图1-（b）。

设4个网页的重要性指标分别为x1，x2，x3，x4，而网页的重要性与网页三个因素有关，即网页的入度数、入度链接是否来自重要的网页以及入度链接源网页的链接数。那么，对于网页1，链接到网页1的有网页3和网页4，而网页3的出度为1，网页4的出度为2。因此，网页1的重要性指标可表示为

同理，其他3个网页的重要性指标也可写出，联合网页1的表达式可得4个网页的重要性指标的方程组：

方程（4）可改写为矩阵形式：x=Ax，其中x=（x1，x2，x3，x4）T，

A= 0   0  1  1/21/3   0   0   01/3  1/2  0  1/21/3  1/2  0   0

其实，矩阵A为图1-（b）的邻接矩阵A2经列和归一化（列元素除以对应结点的出度）后的邻接矩阵，即A=A2*

diag-1（3，2，1，2）。由特征方程：

|λE-A|=（λ-1）  1    1  1   1-1/3   ？姿  0   0-1/3 -1/2  ？姿 -1/2-1/3 -1/2  0   ？姿=0

得λ=1为一特征值，对应的特征向量为c（0.7210，0.2403，

0.5408，0.3605）T，c≠0，将该特征向量各个分量之和归一，则得到唯一的特征向量（0.3871，0.1290，0.2903，0.1935）T。根据各个分量的从大到小排序，4个网页的排序应为：1→3→4→2。

因此，网页重要性的排序问题转化为：求邻接矩阵A对应于特征值λ=1的特征向量x，并将x的各个分量排序，便得到相关网页重要性（PageRank值）的一个排序。然而，这个朴素的PageRank模型与实际的Google搜索算法还有差距，还存在一些问题，比如，排序不唯一和存在出度为0的页面等问题。对于百亿级的网页数，面临着百亿阶的矩阵特征向量的计算，需要快速的计算方法，比如幂法及其改进的方法。具体详细的内容和更多的节点重要性排序方法请参考文献[5-7]。

（二）复杂网络的同步问题

同步现象在现实世界中随处可见。比如，挂在墙上的两个钟的同步摆动、夜间的萤火虫同时闪光和同时不闪光、鸟群的同步飞行和人类心脏中无数心脏细胞同步震荡等。

科学研究发现，同步行为除了与个体的动力学机制有关，还与耦合连接个体的网络结构有关系。抛开个体的动力学，不同的耦合连接方式导致不同的强弱的同步行为。有的网络结构使网络容易同步（或者说网络同步能力强），有的网络结构使网络不那么容易同步（或者说网络同步能力弱）。其实，网络同步能力的强弱是由网络拓扑结构对应的拉普拉斯矩阵的最小非零特征值λ2和最大特征值λN刻画。λ2越大或者比值R=λN/λ2越小，网络的同步能力越强[8]。

例3：4个节点的全连接网络和链状网络，如图2。哪个网络结构的同步能力强？

它们的拉普拉斯矩阵分别为

3 -1 -1 -1-1  3 -1 -1-1 -1  3 -1-1 -1 -1  3和 1  -1   0   0-1   2  -1   0 0  -1   2  -1 1   1  -1   1

容易求得它們的特征值分别为0， 4， 4， 4和0，0.5858，2，3.4142。可知全链接的λ2=4，R=1，而链状的λ2=0.5858，R=5.8283。比较这两个指标，可得全链接结构网络比链状结构网络有更强的同步能力，这个结论也可以推广到任意N个节点的网络。从直观上，很容易理解这个全链接网由于节点间的连接更紧密从而同步能力更强。

但对于大多数网络，很难凭直观判别它们的同步能力。就举图1这个简单例子，从它们的结构看，很难区分两个网络中的哪一个网络的同步能力更强，但隐藏在网络结构背后的特征值可以准确地刻画并区分它们的同步能力。

四、结束语

总之，在特征值和特征向量的概念和计算方法的基础上，通过网络科学中网页排序的简单算例和复杂网络的中同步问题，展现了矩阵的特征值和特征向量的实际应用，同时也将复杂网络中的科学问题渗透到线性代数的教学中，增进学生对科学研究的接触和了解。

参考文献：

[1]方锦清，汪小帆，郑志刚，等.一门崭新的交叉学科：网络科学（上）[J].物理学进展，2007，27（3）：239-343.

[2]汪小帆，李翔，陈关荣.复杂网络理论及其应用[M].北京：清华大学出版社，2006.

[3]同济大学数学系.工程数学：线性代数（第6版）[M].北京：高等教育出版社，2014.

[4] Lay， D.C..线性代数以及应用（原书第3版）[M].刘深泉，等，译.北京：机械工业出版社，2005.

[5]任晓龙，吕琳媛.网络重要节点排序方法综述[J].科学通报， 2014，59：1175-1197.

[6]Kurt Bryan， Tanya Leise， The $25，000，000，000 Eigenvector： The Linear Algebra behind Google[J].SIAM Rev.， 2006，48（3）： 569-581.

[7]Amy N. Langville，Carl D. Meyer. 网页排名PR值及其他：搜索引擎排序的科学[M].郭斯宇，译.机械工业出版社，2014.

[8]陆君安，刘慧，陈娟.复杂动态网络的同步[M].北京：高等教育出版社，2016.