湯龍坤

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

關鍵詞：線性代數;特征值;特征向量;復雜網絡;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

引言

線性代數是大學生一門必修的公共數學基礎課程。不像高等數學課程，其中的概念和方法與中學數學有著緊密聯系，而線性代數課程中的概念相對抽象，方法新穎，知識體系幾乎完全不同于中學數學。對于剛入校的大學生來說，很難馬上適應并學好該課程，更糟糕地還會出現厭學情緒。十幾年的教學經驗和與學生的接觸，發(fā)現學生普遍覺得線性代數比高等數學更抽象更難理解，常常會問“線性代數到底有啥用？”。

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

一、特征值與特征向量

線性變換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，其中，節(jié)點表示網頁，連接（或邊）表示超鏈接。圖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為各個節(jié)點的度（有向圖為入度）構成的對角矩陣。那么，圖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

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

三、復雜網絡中的科學問題

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

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

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

1998年斯坦福大學計算機科學院的新博士生拉里·佩奇和博士二年級的謝爾蓋·布林發(fā)明了PageRank算法后，編寫了PageRank搜索工具用于相關性（節(jié)點重要性）排序。命名為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的頁面等問題。對于百億級的網頁數，面臨著百億階的矩陣特征向量的計算，需要快速的計算方法，比如冪法及其改進的方法。具體詳細的內容和更多的節(jié)點重要性排序方法請參考文獻[5-7]。

（二）復雜網絡的同步問題

同步現象在現實世界中隨處可見。比如，掛在墻上的兩個鐘的同步擺動、夜間的螢火蟲同時閃光和同時不閃光、鳥群的同步飛行和人類心臟中無數心臟細胞同步震蕩等。

科學研究發(fā)現，同步行為除了與個體的動力學機制有關，還與耦合連接個體的網絡結構有關系。拋開個體的動力學，不同的耦合連接方式導致不同的強弱的同步行為。有的網絡結構使網絡容易同步（或者說網絡同步能力強），有的網絡結構使網絡不那么容易同步（或者說網絡同步能力弱）。其實，網絡同步能力的強弱是由網絡拓撲結構對應的拉普拉斯矩陣的最小非零特征值λ2和最大特征值λN刻畫。λ2越大或者比值R=λN/λ2越小，網絡的同步能力越強[8]。

例3：4個節(jié)點的全連接網絡和鏈狀網絡，如圖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?？芍溄拥摩?=4，R=1，而鏈狀的λ2=0.5858，R=5.8283。比較這兩個指標，可得全鏈接結構網絡比鏈狀結構網絡有更強的同步能力，這個結論也可以推廣到任意N個節(jié)點的網絡。從直觀上，很容易理解這個全鏈接網由于節(jié)點間的連接更緊密從而同步能力更強。

但對于大多數網絡，很難憑直觀判別它們的同步能力。就舉圖1這個簡單例子，從它們的結構看，很難區(qū)分兩個網絡中的哪一個網絡的同步能力更強，但隱藏在網絡結構背后的特征值可以準確地刻畫并區(qū)分它們的同步能力。

四、結束語

總之，在特征值和特征向量的概念和計算方法的基礎上，通過網絡科學中網頁排序的簡單算例和復雜網絡的中同步問題，展現了矩陣的特征值和特征向量的實際應用，同時也將復雜網絡中的科學問題滲透到線性代數的教學中，增進學生對科學研究的接觸和了解。

參考文獻：

[1]方錦清，汪小帆，鄭志剛，等.一門嶄新的交叉學科：網絡科學（上）[J].物理學進展，2007，27（3）：239-343.

[2]汪小帆，李翔，陳關榮.復雜網絡理論及其應用[M].北京：清華大學出版社，2006.

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

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

[5]任曉龍，呂琳媛.網絡重要節(jié)點排序方法綜述[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].郭斯宇，譯.機械工業(yè)出版社，2014.

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