線性代數(shù)教學(xué)中網(wǎng)絡(luò)科學(xué)問題的滲透

湯龍坤

摘? 要：特征值和特征向量問題是線性代數(shù)課程中的一個(gè)重要學(xué)習(xí)內(nèi)容。為了讓學(xué)生了解科學(xué)前沿問題并提高學(xué)習(xí)興趣，在講授矩陣特征值與特征向量的概念、計(jì)算方法和幾何意義時(shí)，引入復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的排序和同步問題，舉例說明特征值和特征向量在其中的應(yīng)用，以此將網(wǎng)絡(luò)科學(xué)中的研究問題滲透到線性代數(shù)的教學(xué)中。

關(guān)鍵詞：線性代數(shù);特征值;特征向量;復(fù)雜網(wǎng)絡(luò);PageRank算法

中圖分類號(hào)：G642 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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

引言

線性代數(shù)是大學(xué)生一門必修的公共數(shù)學(xué)基礎(chǔ)課程。不像高等數(shù)學(xué)課程，其中的概念和方法與中學(xué)數(shù)學(xué)有著緊密聯(lián)系，而線性代數(shù)課程中的概念相對(duì)抽象，方法新穎，知識(shí)體系幾乎完全不同于中學(xué)數(shù)學(xué)。對(duì)于剛?cè)胄５拇髮W(xué)生來說，很難馬上適應(yīng)并學(xué)好該課程，更糟糕地還會(huì)出現(xiàn)厭學(xué)情緒。十幾年的教學(xué)經(jīng)驗(yàn)和與學(xué)生的接觸，發(fā)現(xiàn)學(xué)生普遍覺得線性代數(shù)比高等數(shù)學(xué)更抽象更難理解，常常會(huì)問“線性代數(shù)到底有啥用？”。

線性代數(shù)在物理、生物、信息和工程以及最近新興的網(wǎng)絡(luò)科學(xué)領(lǐng)域有廣泛地應(yīng)用。復(fù)雜網(wǎng)絡(luò)是近20年剛興起并倍受關(guān)注的熱點(diǎn)研究領(lǐng)域，目前已發(fā)展成為網(wǎng)絡(luò)科學(xué)與工程學(xué)科，這是一個(gè)新興的交叉學(xué)科，它涵蓋了數(shù)學(xué)、物理、信息、計(jì)算機(jī)、生物和社會(huì)學(xué)等領(lǐng)域[1，2]。網(wǎng)絡(luò)科學(xué)的研究仍處于起步階段，許多前沿科學(xué)問題不需高深的數(shù)學(xué)理論，只要大學(xué)的數(shù)學(xué)知識(shí)就足夠。本文就線性代數(shù)中的特征值和特征向量的內(nèi)容，在基本概念和計(jì)算方法的基礎(chǔ)上，通過幾何意義以及一些注記加深對(duì)特征值和特征向量的理解后，借助復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的排序和同步問題，將網(wǎng)絡(luò)科學(xué)問題滲透到線性代數(shù)的教學(xué)中。

一、特征值與特征向量

線性變換x→Ax可能使得向量x向各個(gè)方向移動(dòng)，但對(duì)于某些特殊的向量，A對(duì)向量的作用導(dǎo)致向量的旋轉(zhuǎn)、伸縮和變向，這些簡(jiǎn)單的變化可由A的特征值和特征向量描述和刻畫。

定義[3，4]：設(shè)A為n×n矩陣，x為非零向量，若存在數(shù)λ使得

Ax=λx（1）

成立，則λ稱為A的特征值，而x稱為A的對(duì)應(yīng)于λ的特征向量。

（1）式也可以寫成

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

于是，特征值問題轉(zhuǎn)化為線性方程組解的問題。由于x是非零向量，即（2）式有非零解，根據(jù)方程組解唯一性的充要條件，可得特征方程

|A-λE|=0（3）

由（3）式可求得矩陣A的特征值，進(jìn)而求解（2）可得對(duì)應(yīng)的特征向量，下面舉個(gè)簡(jiǎn)單的例子。

例1：設(shè)A=1? 43? 2，求A的特征值和特征向量。

解：由特征方程|A-λE|=0，即λ2-3λ-10=0，可求得兩個(gè)特征值λ1=5，λ2=-2。

為求對(duì)應(yīng)的特征向量，分別將兩個(gè)特征值代入（2）式并求解。

對(duì)于λ1=5， A-λE～-1? 10? ?0，故（2）式的通解為c11， 且c≠0的向量是λ1=5對(duì)應(yīng)的特征向量。

對(duì)于λ5=-2， A-λE～3? 40? 0，故（2）式的通解為c-4 3， 且c≠0的向量是λ2=-2對(duì)應(yīng)的特征向量。

對(duì)應(yīng)于λ的所有特征向量的集合稱為λ的特征空間，因此，λ1=5的特征空間為過點(diǎn)（1，1）和原點(diǎn)的直線，而λ2=-2的特征空間為過點(diǎn)（-6，5）和原點(diǎn)的直線。在λ1=5（λ2=-2）的特征空間上去一個(gè)非零向量x作線性變換x→Ax，相當(dāng)于該向量在相同（相反）的方向伸長(zhǎng)5倍（2倍）。

注：（1）特征值對(duì)應(yīng)的特征向量并非唯一的，甚至無窮多個(gè)，但他們之間屬于同一個(gè)特征空間。（2）低階方陣的特征值容易由特征方程求得，但對(duì)于高階方陣，很難從特征方程求出，往往求助于數(shù)值計(jì)算的方法，比如冪法和反冪法等求特征值和特征向量的數(shù)值解法。（3）一般說，特征值的模大于1表示向量經(jīng)過變換后，向量的長(zhǎng)度是伸長(zhǎng)的，而模小于表示經(jīng)過變換后，向量的長(zhǎng)度縮小了。

二、圖的鄰接矩陣和拉普拉斯矩陣

信息科學(xué)、交通運(yùn)輸以及社會(huì)經(jīng)濟(jì)等領(lǐng)域中的單元（或個(gè)體）間的關(guān)系往往可以用幾何圖來描述，進(jìn)一步地還可以用鄰接矩陣來表示。例如，萬維網(wǎng)可定義為一個(gè)圖，利用圖的鄰接矩陣可研究網(wǎng)頁的重要性，尋找網(wǎng)頁的樞紐。

例2. 設(shè)有4個(gè)網(wǎng)頁的圖如圖1，其中，節(jié)點(diǎn)表示網(wǎng)頁，連接（或邊）表示超鏈接。圖1-（a）為無向圖表示網(wǎng)頁間彼此有超級(jí)鏈接，是雙向的（這里用不帶箭頭的邊來表示），而圖1-（b）表示為有向圖，網(wǎng)頁到網(wǎng)頁的連接有出鏈和入鏈之分。

對(duì)于無向圖，若第i個(gè)網(wǎng)頁與第j個(gè)網(wǎng)頁有邊記aij=1，否則aij=0。對(duì)于有向圖，若第j個(gè)網(wǎng)頁有邊指向第i個(gè)網(wǎng)頁記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個(gè)網(wǎng)頁間的超級(jí)鏈接圖

拉普拉斯矩陣定義為L(zhǎng)=D-A， 其中A為圖的鄰接矩陣，而D為各個(gè)節(jié)點(diǎn)的度（有向圖為入度）構(gòu)成的對(duì)角矩陣。那么，圖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

利用圖的鄰接矩陣和拉普拉斯矩陣的特征值或特征向量（矩陣中的最小和最大非零特征值及特征向量在實(shí)際問題中有廣泛應(yīng)用），我們可以研究網(wǎng)頁重要性的排序問題，傳輸網(wǎng)絡(luò)的邊負(fù)載問題，社團(tuán)的劃分問題以及網(wǎng)絡(luò)同步能力等問題。

三、復(fù)雜網(wǎng)絡(luò)中的科學(xué)問題

（一）節(jié)點(diǎn)重要性的排序問題

網(wǎng)絡(luò)中的重要節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)的結(jié)構(gòu)和功能有重要的影響。比如，微博中的幾個(gè)最有影響的節(jié)點(diǎn)所發(fā)的微博能迅速傳遍整個(gè)微博網(wǎng)絡(luò);全球1%的公司控制了40%的全球經(jīng)濟(jì);少量的幾個(gè)重要節(jié)點(diǎn)受蓄意攻擊后導(dǎo)致整個(gè)電網(wǎng)的崩塌等[5]。所以，對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的排序和重要節(jié)點(diǎn)的挖掘有重要的理論和實(shí)際意義。

網(wǎng)絡(luò)時(shí)代的今天，百度和Google等搜索引擎已經(jīng)融入到人們的生活中。在Google的搜索頁面搜索框輸入關(guān)鍵詞，為什么能在短短零點(diǎn)幾秒的時(shí)間內(nèi)找到百萬條甚至千萬條的相關(guān)頁面，并按最相關(guān)或感興趣（節(jié)點(diǎn)重要性）的排序排好？

1998年斯坦福大學(xué)計(jì)算機(jī)科學(xué)院的新博士生拉里·佩奇和博士二年級(jí)的謝爾蓋·布林發(fā)明了PageRank算法后，編寫了PageRank搜索工具用于相關(guān)性（節(jié)點(diǎn)重要性）排序。命名為Google，這是 Googol的變體，Googol是一個(gè)數(shù)字名詞，表示10的100次方。正是PageRank搜索算法革命性的改變網(wǎng)絡(luò)世界，而隱藏在這個(gè)算法背后的數(shù)學(xué)就是矩陣的特征值和特征向量的問題[6，7]。下面舉一個(gè)僅有4個(gè)網(wǎng)頁的簡(jiǎn)單例子，網(wǎng)頁鏈接關(guān)系如圖1-（b）。

設(shè)4個(gè)網(wǎng)頁的重要性指標(biāo)分別為x1，x2，x3，x4，而網(wǎng)頁的重要性與網(wǎng)頁三個(gè)因素有關(guān)，即網(wǎng)頁的入度數(shù)、入度鏈接是否來自重要的網(wǎng)頁以及入度鏈接源網(wǎng)頁的鏈接數(shù)。那么，對(duì)于網(wǎng)頁1，鏈接到網(wǎng)頁1的有網(wǎng)頁3和網(wǎng)頁4，而網(wǎng)頁3的出度為1，網(wǎng)頁4的出度為2。因此，網(wǎng)頁1的重要性指標(biāo)可表示為

同理，其他3個(gè)網(wǎng)頁的重要性指標(biāo)也可寫出，聯(lián)合網(wǎng)頁1的表達(dá)式可得4個(gè)網(wǎng)頁的重要性指標(biāo)的方程組：

方程（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

其實(shí)，矩陣A為圖1-（b）的鄰接矩陣A2經(jīng)列和歸一化（列元素除以對(duì)應(yīng)結(jié)點(diǎn)的出度）后的鄰接矩陣，即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為一特征值，對(duì)應(yīng)的特征向量為c（0.7210，0.2403，

0.5408，0.3605）T，c≠0，將該特征向量各個(gè)分量之和歸一，則得到唯一的特征向量（0.3871，0.1290，0.2903，0.1935）T。根據(jù)各個(gè)分量的從大到小排序，4個(gè)網(wǎng)頁的排序應(yīng)為：1→3→4→2。

因此，網(wǎng)頁重要性的排序問題轉(zhuǎn)化為：求鄰接矩陣A對(duì)應(yīng)于特征值λ=1的特征向量x，并將x的各個(gè)分量排序，便得到相關(guān)網(wǎng)頁重要性（PageRank值）的一個(gè)排序。然而，這個(gè)樸素的PageRank模型與實(shí)際的Google搜索算法還有差距，還存在一些問題，比如，排序不唯一和存在出度為0的頁面等問題。對(duì)于百億級(jí)的網(wǎng)頁數(shù)，面臨著百億階的矩陣特征向量的計(jì)算，需要快速的計(jì)算方法，比如冪法及其改進(jìn)的方法。具體詳細(xì)的內(nèi)容和更多的節(jié)點(diǎn)重要性排序方法請(qǐng)參考文獻(xiàn)[5-7]。

（二）復(fù)雜網(wǎng)絡(luò)的同步問題

同步現(xiàn)象在現(xiàn)實(shí)世界中隨處可見。比如，掛在墻上的兩個(gè)鐘的同步擺動(dòng)、夜間的螢火蟲同時(shí)閃光和同時(shí)不閃光、鳥群的同步飛行和人類心臟中無數(shù)心臟細(xì)胞同步震蕩等。

科學(xué)研究發(fā)現(xiàn)，同步行為除了與個(gè)體的動(dòng)力學(xué)機(jī)制有關(guān)，還與耦合連接個(gè)體的網(wǎng)絡(luò)結(jié)構(gòu)有關(guān)系。拋開個(gè)體的動(dòng)力學(xué)，不同的耦合連接方式導(dǎo)致不同的強(qiáng)弱的同步行為。有的網(wǎng)絡(luò)結(jié)構(gòu)使網(wǎng)絡(luò)容易同步（或者說網(wǎng)絡(luò)同步能力強(qiáng)），有的網(wǎng)絡(luò)結(jié)構(gòu)使網(wǎng)絡(luò)不那么容易同步（或者說網(wǎng)絡(luò)同步能力弱）。其實(shí)，網(wǎng)絡(luò)同步能力的強(qiáng)弱是由網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)應(yīng)的拉普拉斯矩陣的最小非零特征值λ2和最大特征值λN刻畫。λ2越大或者比值R=λN/λ2越小，網(wǎng)絡(luò)的同步能力越強(qiáng)[8]。

例3：4個(gè)節(jié)點(diǎn)的全連接網(wǎng)絡(luò)和鏈狀網(wǎng)絡(luò)，如圖2。哪個(gè)網(wǎng)絡(luò)結(jié)構(gòu)的同步能力強(qiáng)？

它們的拉普拉斯矩陣分別為

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。比較這兩個(gè)指標(biāo)，可得全鏈接結(jié)構(gòu)網(wǎng)絡(luò)比鏈狀結(jié)構(gòu)網(wǎng)絡(luò)有更強(qiáng)的同步能力，這個(gè)結(jié)論也可以推廣到任意N個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)。從直觀上，很容易理解這個(gè)全鏈接網(wǎng)由于節(jié)點(diǎn)間的連接更緊密從而同步能力更強(qiáng)。

但對(duì)于大多數(shù)網(wǎng)絡(luò)，很難憑直觀判別它們的同步能力。就舉圖1這個(gè)簡(jiǎn)單例子，從它們的結(jié)構(gòu)看，很難區(qū)分兩個(gè)網(wǎng)絡(luò)中的哪一個(gè)網(wǎng)絡(luò)的同步能力更強(qiáng)，但隱藏在網(wǎng)絡(luò)結(jié)構(gòu)背后的特征值可以準(zhǔn)確地刻畫并區(qū)分它們的同步能力。

四、結(jié)束語

總之，在特征值和特征向量的概念和計(jì)算方法的基礎(chǔ)上，通過網(wǎng)絡(luò)科學(xué)中網(wǎng)頁排序的簡(jiǎn)單算例和復(fù)雜網(wǎng)絡(luò)的中同步問題，展現(xiàn)了矩陣的特征值和特征向量的實(shí)際應(yīng)用，同時(shí)也將復(fù)雜網(wǎng)絡(luò)中的科學(xué)問題滲透到線性代數(shù)的教學(xué)中，增進(jìn)學(xué)生對(duì)科學(xué)研究的接觸和了解。

參考文獻(xiàn)：

[1]方錦清，汪小帆，鄭志剛，等.一門嶄新的交叉學(xué)科：網(wǎng)絡(luò)科學(xué)（上）[J].物理學(xué)進(jìn)展，2007，27（3）：239-343.

[2]汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京：清華大學(xué)出版社，2006.

[3]同濟(jì)大學(xué)數(shù)學(xué)系.工程數(shù)學(xué)：線性代數(shù)（第6版）[M].北京：高等教育出版社，2014.

[4] Lay， D.C..線性代數(shù)以及應(yīng)用（原書第3版）[M].劉深泉，等，譯.北京：機(jī)械工業(yè)出版社，2005.

[5]任曉龍，呂琳媛.網(wǎng)絡(luò)重要節(jié)點(diǎn)排序方法綜述[J].科學(xué)通報(bào)， 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. 網(wǎng)頁排名PR值及其他：搜索引擎排序的科學(xué)[M].郭斯宇，譯.機(jī)械工業(yè)出版社，2014.

[8]陸君安，劉慧，陳娟.復(fù)雜動(dòng)態(tài)網(wǎng)絡(luò)的同步[M].北京：高等教育出版社，2016.