圖源：pixabay

撰文 ｜丁玖 朱慧堅(jiān)（廣州南方學(xué)院）

1998年9月4日，兩個(gè)25周歲的年輕小伙拉里·佩奇(Larry Page，生于1973年3月26日)和謝爾蓋·布林（Sergey Brin，生于1973年8月21日）在加利福尼亞州舊金山灣區(qū)圣馬特奧（San Mateo）縣的城市門洛帕克（Menlo Park）提交了谷歌公司的注冊(cè)文件。這個(gè)小城僅有三萬多居民，南面的近鄰是斯坦福大學(xué)，而他們正在那里攻讀計(jì)算機(jī)科學(xué)系的博士學(xué)位。

他們創(chuàng)辦的這家公司，四分之一個(gè)世紀(jì)后，其“谷歌搜索”成了全球訪問量最高的兩個(gè)網(wǎng)站之一。佩奇和布林最初將他們開辟的新搜索引擎昵稱為“背部按摩（BackRub）”，因?yàn)樵撓到y(tǒng)會(huì)檢查反向鏈接來評(píng)估網(wǎng)站的重要性。最終，他們將名稱改為Google，然而這是對(duì)古戈?duì)枺╣oogol）一詞的錯(cuò)誤拼寫。古戈?duì)柺且粋€(gè)巨大的數(shù)字10100（1后面跟著100個(gè)零），選擇這個(gè)數(shù)字是為了表明該搜索引擎旨在提供大量信息。不過，直到今天，全世界的網(wǎng)頁個(gè)數(shù)還遠(yuǎn)遠(yuǎn)低于這個(gè)已經(jīng)超過宇宙所有原子個(gè)數(shù)的大數(shù)；或許永遠(yuǎn)也達(dá)不到。

古戈?duì)栍擅绹鐐惐葋喆髮W(xué)數(shù)學(xué)系教授愛德華·卡斯納（Edward Kasner，1878-1955）的侄子、年僅9歲的米爾頓·西羅塔（Milton Sirotta）創(chuàng)造，用來表示一個(gè)難以想象的大數(shù)。卡斯納在其1940年出版的《數(shù)學(xué)與想象力》一書中推廣了古戈?duì)柕母拍睿蜗蟮卣故玖舜髷?shù)與無窮之間的尺度，想必谷歌的創(chuàng)始人受此啟發(fā)，給他們的搜索引擎新生兒起了這個(gè)拼錯(cuò)了一個(gè)字母的名字。順便一提，卡斯納最杰出的弟子是首屆菲爾茲獎(jiǎng)的兩名獲獎(jiǎng)?wù)咧弧⒚绹鴶?shù)學(xué)家杰西·道格拉斯（Jesse Douglas，1897-1965）。

無論佩奇還是布林，創(chuàng)辦公司后都沒有待在世界名校斯坦福美麗的校園，穩(wěn)穩(wěn)當(dāng)當(dāng)?shù)貓?jiān)持到最后，以獲一紙博士證書。他們最終的學(xué)位——碩士——仍然高于年長他們18歲的比爾·蓋茨（Bill Gates，1955-）；后者入學(xué)哈佛大學(xué)讀本科兩年后毅然退學(xué)，與合作伙伴開創(chuàng)了微軟公司，開啟了他一生的輝煌事業(yè)。佩奇和布林共同創(chuàng)辦的公司——谷歌——同樣也成了本世紀(jì)全世界最著名的高科技公司之一。沒有追求學(xué)位圓滿的他們?nèi)耍髞矶急贿x為美國國家工程院院士。

佩奇和布林都有猶太血統(tǒng)。兩人中，年輕半歲的布林有個(gè)數(shù)學(xué)家爸爸，佩奇的父親則是計(jì)算機(jī)科學(xué)家。布林之父米哈伊·布林（MihailBrin，1947-）是個(gè)國際知名的俄羅斯純粹數(shù)學(xué)家，專長為動(dòng)力系統(tǒng)與黎曼幾何，本科畢業(yè)于莫斯科大學(xué)，博士導(dǎo)師為蘇聯(lián)動(dòng)力系統(tǒng)大家德米特里·阿諾索夫（Dmitri Anosov（1936-2014）和阿納托爾·諾克（Anatole Katok，1944-2018）。布林教授在普林斯頓大學(xué)數(shù)學(xué)系編輯的純數(shù)學(xué)國際頂尖雜志《數(shù)學(xué)年刊》上發(fā)表過三篇論文，也出版過書籍，如與他后來的馬里蘭大學(xué)同事合著的《動(dòng)力系統(tǒng)引論》，2015年由劍橋大學(xué)出版社推出。

小布林6歲時(shí)隨全家從蘇聯(lián)移民到美國。1990年他追隨父親的腳步跨進(jìn)了馬里蘭大學(xué)，不過，父親是數(shù)學(xué)系的教授，他則在數(shù)學(xué)系和計(jì)算機(jī)科學(xué)系讀本科。三年后，他以數(shù)學(xué)與計(jì)算機(jī)科學(xué)雙專業(yè)榮譽(yù)畢業(yè)生的優(yōu)異成績獲得學(xué)士學(xué)位。馬里蘭大學(xué)數(shù)學(xué)系一直引以自豪的另一個(gè)本科畢業(yè)生是菲爾茲獎(jiǎng)獲得者查爾斯·費(fèi)弗曼（Charles Fefferman，1949-），他17歲就獲得數(shù)學(xué)與物理學(xué)的雙學(xué)位，于普林斯頓大學(xué)獲得數(shù)學(xué)博士后，22歲時(shí)成為芝加哥大學(xué)的正教授；他的同門博士師弟就是另一個(gè)菲爾茲獎(jiǎng)獲得者陶澤軒（Terence Tao，1975-）。

佩奇是個(gè)土生土長的美國人，他的父親卡爾·佩奇（Carl Page Sr.，1938-1996）是筆者之一博士母校密歇根州立大學(xué)的計(jì)算機(jī)科學(xué)教授。老佩奇博士畢業(yè)于密歇根州的首席大學(xué)、也是全美最負(fù)盛名的公立大學(xué)之一密歇根大學(xué)的計(jì)算機(jī)科學(xué)系，在其職業(yè)生涯中是美國人工智能研究的先驅(qū)之一。可惜佩奇教授英年早逝，未能像布林教授那樣目睹了兒子成長為業(yè)界巨人。

小佩奇也步了父親的后塵，一腳跨進(jìn)密歇根大學(xué)的校門，父子倆成為這所被譽(yù)為“美國公立大學(xué)之母”的中西部巨無霸大學(xué)的先后校友。在父母的直接影響下，兒子6歲時(shí)就對(duì)電腦產(chǎn)生了興趣，因?yàn)樗梢浴巴媾切┥⒙湓谥車臇|西”——他父母留下的第一代個(gè)人電腦。他成為“小學(xué)里第一個(gè)用文字處理器交作業(yè)的孩子”。可以說他是在電腦配件的叢林中長大的，“熟能生巧”這一中文成語可以恰如其分地形容佩奇從兒童走向青年對(duì)計(jì)算機(jī)世界的癡迷程度。后來他說：“從小我就意識(shí)到自己想發(fā)明創(chuàng)造。所以我對(duì)科技和商業(yè)產(chǎn)生了興趣。大概從12歲起，我就知道自己最終會(huì)創(chuàng)辦一家公司。”

在密歇根州立大學(xué)所在地東蘭辛高中畢業(yè)后，從1991年到1995年，佩奇在密歇根大學(xué)讀計(jì)算機(jī)工程，以榮譽(yù)稱號(hào)獲得工程學(xué)士學(xué)位，然后進(jìn)入西部學(xué)術(shù)重鎮(zhèn)斯坦福大學(xué)攻讀計(jì)算機(jī)科學(xué)博士學(xué)位，在他創(chuàng)業(yè)元年獲得碩士學(xué)位。

在尋找論文選題時(shí)，佩奇考慮探索萬維網(wǎng)的數(shù)學(xué)特性，將其鏈接結(jié)構(gòu)理解為一個(gè)龐大的有向圖。他的導(dǎo)師特里·維諾格拉德（Terry Winograd，1946-)鼓勵(lì)他繼續(xù)研究這個(gè)想法。2008年谷歌20周歲，佩奇以感恩之情回憶道：“這是我收到的最好建議。”

成功實(shí)現(xiàn)快速高效網(wǎng)頁搜索的好想法，不僅得益于有深遠(yuǎn)眼光學(xué)術(shù)導(dǎo)師的好建議，還需要背景類似、志同道合、互補(bǔ)長短的合作伙伴，這對(duì)應(yīng)用科學(xué)十分奏效。在斯坦福這個(gè)布滿才華橫溢年輕學(xué)者的校園內(nèi)，同在計(jì)算機(jī)科學(xué)疆場(chǎng)習(xí)武的布林加入到佩奇的行列，兩人結(jié)伴開始了對(duì)網(wǎng)頁搜索引擎的創(chuàng)新研究。卓有成效的共同努力導(dǎo)致“網(wǎng)頁排序（PageRank）”這個(gè)互聯(lián)網(wǎng)史上具有里程碑意義的新穎概念和術(shù)語的誕生。

在英文的語義下，兩個(gè)單詞的無空格組合PageRank可以有兩層含義；其一是與實(shí)施對(duì)象相關(guān)的如上翻譯“網(wǎng)頁排序”，其二是“佩奇排序”，理由為Page是佩奇的姓。事實(shí)上，“PageRank”這個(gè)名字是個(gè)雙關(guān)語，既指網(wǎng)頁排名算法，也指其開發(fā)者佩奇。該算法最初是作為一種基于鏈接流行度對(duì)搜索結(jié)果進(jìn)行排序的系統(tǒng)而開發(fā)的。

四分之一個(gè)世紀(jì)以來，世人盡知谷歌擁有史上最成功的搜索引擎，然而有幾人了解到是什么魔法使它進(jìn)入市場(chǎng)后迅速走紅，又有幾人通曉引導(dǎo)它成功的關(guān)鍵數(shù)學(xué)為何？今天是第七個(gè)國際數(shù)學(xué)日，正是每個(gè)數(shù)學(xué)愛好者甚至數(shù)學(xué)同情者可以借機(jī)接受數(shù)學(xué)普及的好日子。筆者受中國數(shù)學(xué)會(huì)的一則通知啟發(fā)，想到谷歌矩陣這個(gè)與國際人的日常生活、學(xué)習(xí)工作、職場(chǎng)發(fā)展都有關(guān)系的“全世界最大的矩陣”，覺得談?wù)勊蛟S是向國際數(shù)學(xué)日所獻(xiàn)的一朵艷麗之花。

由于網(wǎng)頁數(shù)量龐大（目前網(wǎng)站總數(shù)超過13億，但只有約六分之一的網(wǎng)站“被積極維護(hù)”。搜索引擎索引的實(shí)際網(wǎng)頁數(shù)量在40億至60億之間，而搜索引擎識(shí)別的網(wǎng)頁數(shù)量則超過130萬億），網(wǎng)絡(luò)信息檢索比傳統(tǒng)的信息檢索更具挑戰(zhàn)性。在網(wǎng)絡(luò)信息檢索研究中，每個(gè)網(wǎng)頁都被表示為一個(gè)超大型有向圖中的一個(gè)節(jié)點(diǎn)，連接這些節(jié)點(diǎn)的有向邊代表頁面之間的超鏈接。

這種超鏈接結(jié)構(gòu)可以通過三種信息檢索方法進(jìn)行探索，第一種是“超文本誘導(dǎo)主題搜索”，其代表性論文是J. Kleinberg于1999年在美國計(jì)算機(jī)協(xié)會(huì)雜志上發(fā)表的Authoritative Sources in a Hyperlinked Environment（超鏈接環(huán)境中的權(quán)威來源）；第二種是“鏈接結(jié)構(gòu)分析的隨機(jī)方法”；第三種是本文將重點(diǎn)介紹的網(wǎng)頁排序法，最初思想由佩奇和布林于1996年醞釀而生，他們對(duì)此的第一篇技術(shù)性文章由四人合寫，其中最后一位作者就是他們的導(dǎo)師維諾格拉德。這篇?dú)v史留名的論文于1999年以斯坦福大學(xué)計(jì)算機(jī)科學(xué)系技術(shù)報(bào)告1999-0120的方式公開問世，標(biāo)題是The PageRank Citation Ranking: Bringing Order to the Web（PageRank引用排名：為網(wǎng)絡(luò)帶來秩序）。盡管該文似乎從未在學(xué)術(shù)期刊上正式發(fā)表，迄今卻已被引用了兩萬余次。可見并非總是在名刊甚至期刊上發(fā)表的論文才會(huì)“推動(dòng)科技的進(jìn)步”。

在網(wǎng)頁排序概念出現(xiàn)兩年后橫空出世的谷歌公司，一開始就在官網(wǎng)聲明：

網(wǎng)頁排序是我們軟件的核心。

又過了以驚人速度壯大發(fā)展的四年，與公司員工共舞的其尺寸大得難以想象的那個(gè)矩陣——后被人們常掛在嘴邊的“谷歌矩陣”，引發(fā)出大型通用計(jì)算程序包Matlab的開發(fā)者克利夫·莫勒（Cleve Moler，1939-）的感慨，在自己公司MathWorks的《Matlab新聞和簡訊》上撰文《世界上規(guī)模最大的矩陣計(jì)算》。

那么，這個(gè)世間最大的矩陣是怎么定義出來的？

首先，它是一個(gè)非負(fù)矩陣，即矩陣的每個(gè)元素都是非負(fù)實(shí)數(shù)，并且它也是個(gè)方陣，即行數(shù)等于列數(shù)。其次，它的每一行的所有元素加起來都等于1。這種特殊的非負(fù)矩陣有個(gè)學(xué)名，叫隨機(jī)矩陣（stochastic matrix）。在線性代數(shù)這門應(yīng)用廣泛的數(shù)學(xué)學(xué)科，“非負(fù)矩陣?yán)碚摗睒?gòu)成了一個(gè)子學(xué)科，而隨機(jī)矩陣又是其中的核心部分。可惜的是，我們的本科教科書中一般不放進(jìn)這類東西。

要充分理解谷歌矩陣的定義基礎(chǔ)，先得從網(wǎng)頁排序的基本想法開始。

網(wǎng)頁排序的理念是：

來自重要頁面的鏈接應(yīng)該比來自不太重要頁面的鏈接權(quán)重更高，并且來自任何源頁面的鏈接的重要性應(yīng)該根據(jù)該源頁面鏈接到的頁面數(shù)量進(jìn)行縮放。

這個(gè)創(chuàng)新思想是容易想得通的。多年前，當(dāng)筆者之一在國內(nèi)高校做有關(guān)谷歌矩陣的演講時(shí)，向聽眾如此解釋它：國家領(lǐng)袖網(wǎng)頁上的內(nèi)容肯定比數(shù)學(xué)教授的網(wǎng)頁內(nèi)容在大眾眼里更加重要，而且前者的網(wǎng)頁會(huì)被更多的網(wǎng)頁鏈接到，因此它應(yīng)享有更加靠前的排名。如果采用數(shù)學(xué)語言來表達(dá)前述的意思，那么該想法是通過定義給定網(wǎng)頁P(yáng)的合理排名r(P)來實(shí)現(xiàn)的。r(P)定義為：

r(P) = ∑Q∈I(P)r(Q)/|Q|，

其中I(P)是所有指向P的那些網(wǎng)頁組成的集合，r(Q)是網(wǎng)頁Q的排名，|Q|表示從網(wǎng)頁Q發(fā)出的鏈接數(shù)。如上表達(dá)式說明，網(wǎng)頁P(yáng)的重要程度，首先依鏈接到它的其他網(wǎng)頁的多寡而定，越多越重要，且那些指向它的網(wǎng)頁Q越重要，則P也隨之越重要，可謂“水漲船高”；其次，若指向網(wǎng)頁P(yáng)的某個(gè)網(wǎng)頁Q也指向其他網(wǎng)頁，則被鏈接的網(wǎng)頁越多，P在Q眼中的重要性相應(yīng)就變低，這解釋了為何|Q|出現(xiàn)在分母。打個(gè)比方，如果閣下的網(wǎng)頁被某個(gè)名流鏈接到，不必太得意，或許該名流熱衷于社會(huì)交際，同時(shí)也鏈接了其他許多人的網(wǎng)頁，這樣的話你的網(wǎng)頁重要性并沒有因該名流的光顧而大增。

以上對(duì)單個(gè)網(wǎng)頁P(yáng)的排名r(P)雖然定義合理，但這是一個(gè)隱式定義，因此我們借用迭代法來找到上述“不動(dòng)點(diǎn)方程”的一個(gè)解，方法如下：

假設(shè)共有n個(gè)網(wǎng)頁P(yáng)1,P2,...,Pn。為每個(gè)網(wǎng)頁分配一個(gè)初始排名r0，最公平合理的初始排名是均勻排名

r0(Pi) = 1/n，i = 1,2,…,n。

然后對(duì)k = 1,2,3,...如下操作排名迭代：

rk(Pi) = ∑Pj∈I(Pi)rk?1(Pj)/|Pj|，i = 1,2,…,n。

現(xiàn)在定義n階方陣P = [pij]ni,j = 1：對(duì)于i, j = 1, 2,…, n，若網(wǎng)頁P(yáng)i鏈接到網(wǎng)頁P(yáng)j，則令

pij= 1/|Pi|；

否則的話，定義pij= 0。顯見，P是非負(fù)方陣且每行元素之和等于1。換言之，P是n階隨機(jī)矩陣。此外，對(duì)于行向量

πkT= (rk(P1), rk(P2), …, rk(Pn)),

上述的迭代過程可以用矩陣乘法的形式表示：

πkT=(πk-1)TP,k = 1,2,…。

如果下列極限存在的話，佩奇和布林將極限向量

πT= limk→∞πkT

定義為網(wǎng)頁排序向量，而它的第i個(gè)分量πi則成為網(wǎng)頁P(yáng)i的排名。

可是，要使得定義不被詬病，他們需要回答兩個(gè)問題：

1.這個(gè)原始的谷歌矩陣P是否存在對(duì)應(yīng)于特征值1的左特征向量πT？若πT存在，歸一化（目的讓所有分量之和變成1）后的πT是否唯一？

2.當(dāng)k趨于無窮大時(shí)，迭代向量序列πkT=(πk-1)TP的極限是否存在？若存在，那么迭代收斂得多快呢？

現(xiàn)在用一個(gè)簡單例子說明思想。考慮一個(gè)僅有六個(gè)網(wǎng)頁的微型網(wǎng)絡(luò)，并使用原始的谷歌矩陣。

注意到矩陣的第二行元素全為零，這是因?yàn)闆]有從第二個(gè)網(wǎng)頁（對(duì)應(yīng)的有向圖節(jié)點(diǎn)叫做懸空節(jié)點(diǎn)）發(fā)出的鏈接。所以P不是一個(gè)隨機(jī)矩陣！

為了補(bǔ)救，我們將第二行的每個(gè)元素加上1/6，便得到一個(gè)隨機(jī)矩陣S：

對(duì)于這個(gè)經(jīng)過改造的矩陣，非負(fù)矩陣?yán)碚撝凶罱?jīng)典的一個(gè)定理派上了大用場(chǎng)，它以兩個(gè)德國數(shù)學(xué)家的名字命名——佩龍-佛羅貝爾尼斯定理，年輕的前者佩龍（Oskar Perron，1880-1975）于1907年對(duì)正矩陣，即每個(gè)元素均為正數(shù)的矩陣證明了它，年長的后者佛羅貝爾尼斯（Ferdinand GeorgFrobenius，1849-1917）五年后對(duì)所謂的不可約非負(fù)矩陣推廣了佩龍的結(jié)果。一個(gè)方陣稱為是可約的，意思是說，可以將它的行和列以同樣的方式重新排列，其結(jié)果矩陣的右下角是個(gè)零方陣。譬如，2階及更高階的單位矩陣是可約非負(fù)矩陣。

即便上述的隨機(jī)矩陣S是可約的，一個(gè)經(jīng)典的不動(dòng)點(diǎn)定理——布勞威爾不動(dòng)點(diǎn)定理卻能保證，存在歸一化的非負(fù)左特征向量πT：

πT= πTS,πTe = 1。

這里按習(xí)慣用字母e代表特殊列向量(1,1,…,1)T。任意矩陣A乘以e，所得向量的各分量等于將A的那行元素加起來得到的和，故非負(fù)矩陣A為隨機(jī)矩陣當(dāng)且僅當(dāng)Ae = e。

遺憾的是，上例中的隨機(jī)矩陣S雖然確保了網(wǎng)頁排序向量πT的存在性，卻由于它是可約的（因?yàn)橛蚁陆鞘?階零矩陣），結(jié)果是歸一化的πT不能保證唯一且分量個(gè)個(gè)為正。如果網(wǎng)頁排名不唯一，至少會(huì)造成網(wǎng)頁排序算法迭代不收斂或計(jì)算結(jié)果混淆不清。當(dāng)今各種大學(xué)排名榜五花八門，結(jié)果千奇百怪，搞得大學(xué)當(dāng)局有時(shí)高興有時(shí)發(fā)愁，就是排名不唯一的后遺癥。

為解決這一棘手問題，布林和佩奇引入了S的由參數(shù)α∈(0,1)控制的一種“凸組合”擾動(dòng)；例如，取α = 0.9，得到一個(gè)新矩陣：

讀者一看就知道G是一個(gè)正矩陣。此外，它繼承了S是隨機(jī)矩陣的好性質(zhì)，這一點(diǎn)的證明簡潔而明快：

Ge=(0.9S + 0.1eeT/6)e = 0.9Se + 0.1eeTe/6

= 0.9e + 0.1(eTe)e/6 = 0.9e + 0.1(6)e/6 = 0.9e + 0.1e = e。

這樣，按照佩龍-佛羅貝爾尼斯的非負(fù)矩陣?yán)碚摚珿不僅存在唯一的歸一化左特征向量πT，其具體數(shù)值是

πT= (0.03721, 0.05396, 0.04151, 0.3751, 0.206, 0.2862)，

而且正因?yàn)檫@個(gè)網(wǎng)頁排序向量的所有分量均為正數(shù)，它實(shí)實(shí)在在地提供了所給微型網(wǎng)絡(luò)總共6個(gè)網(wǎng)頁的排名。更重要的是，取定初始向量π0T= (1/6, 1/6, 1/6, 1/6, 1/6, 1/6)，直接迭代法

πkT=(πk-1)TG，k = 1,2,...

計(jì)算出的歸一化向量序列{πkT}收斂到G的唯一歸一化左特征向量πT。

有了上面的具體例子墊底，我們可以敘述谷歌矩陣的一般定義及其相應(yīng)的網(wǎng)頁排序算法。如前，假設(shè)所有的網(wǎng)頁為P1,P2,...,Pn，其對(duì)應(yīng)的n階原始谷歌矩陣為P。選取一個(gè)固定的n維“概率向量”

v = (v1, v2, v3,…, vn)T，

即v的所有分量都是正數(shù)，并且其和等于1，即vTe = 1。

將矩陣P的所有零行替換為相同的行向量vT，得到隨機(jī)矩陣S。現(xiàn)在固定參數(shù)α∈(0,1)（早期谷歌公司使用過參數(shù)值α= 0.85），并將谷歌矩陣G定義為S和evT的凸組合：

G = αS + (1–α)evT。

G依然是個(gè)隨機(jī)矩陣：

Ge = [αS + (1–α)evT]e =αSe + (1–α)evTe

=αe + (1–α)(vTe)e=αe + (1–α)e = e。

更重要的是，由于S是非負(fù)矩陣，evT是正矩陣，它們的凸組合的系數(shù)小于1，這保證了G是個(gè)正矩陣。如此構(gòu)造的矩陣G被稱為谷歌矩陣。

萬事俱備只欠東風(fēng)，現(xiàn)在可以敘述（但不證明）已超過一百年歷史的佩龍-佛羅貝爾尼斯定理在正隨機(jī)矩陣時(shí)的特殊結(jié)論了。

正隨機(jī)矩陣譜定理.設(shè)A為一n階正隨機(jī)矩陣。則存在歸一化的所有分量均為正數(shù)的n維行向量πT，即

πT= πTA,πTe = 1；

滿足上述性質(zhì)的πT是唯一的。此外，A的所有特征值的最大模等于1，并且1是A在復(fù)平面單位圓上的唯一特征值。更進(jìn)一步，任給歸一化的n維非負(fù)初始向量π0T，迭代向量序列

πkT=(πk-1)TA =π0TAk，k = 1,2,...

收斂到πT。

譜定理告訴我們，對(duì)于佩奇和布林創(chuàng)造出的谷歌矩陣，上述這個(gè)被稱為“冪方法”的迭代程式總收斂到網(wǎng)頁排序向量。又因?yàn)楣雀杈仃囈?guī)模巨大，冪方法只能是給全球有效網(wǎng)頁快速排名的唯一實(shí)用辦法。

收斂性問題圓滿解決后，關(guān)注谷歌用于計(jì)算網(wǎng)頁排序基本算法效率的讀者自然會(huì)問到“收斂得多快”的應(yīng)用性問題。學(xué)過數(shù)值線性代數(shù)的人知道冪方法的收斂速率取決于矩陣所有特征值中的次大模。現(xiàn)在我們用矩陣特征多項(xiàng)式的技巧來尋找谷歌矩陣G所有的特征值。

首先，因?yàn)镾是隨機(jī)矩陣，1是它的特征值，特征向量是e。記S的所有特征值為1,λ2, λ3, ··· , λn。則αS的征值為α,αλ2,αλ3, …,αλn。為方便起見，令A(yù) = αS及u = (1–α)e。則G = A + uvT。

設(shè)λ不是A的特征值。從等式λI?G = (λI?A)?uvT，運(yùn)用著名的矩陣行列式引理，即若B為m階非奇異矩陣，且x和y為m維向量，則

det(B + xyT) =(1+ yTB-1x)detB，

得到G的特征多項(xiàng)式的表達(dá)式

det(λI?G) =[1–vT(λI?A)-1u]det(λI?A)。

由于

(λI?A)u = (1?α)(λI–αS)e = (1?α)(λ?α)e

= (λ?α)(1?α)e = (λ?α)u，

(λI?A)-1u =(λ–α)-1u，

隨即便有

1?vT(λI?A)-1u =1?(λ–α)-1vTu= (λ–α)-1[λ–(α+vTu)]。

從而得到

det(λI?G) =(λ–α)-1[λ–(α+vTu)]det(λI?A)。

因?yàn)棣?vTu=α+vT(1?α)e=α+(1?α) vTe =α+(1?α)= 1，便有

det(λI?G) =(λ–α)-1(λ–1)det(λI?A)

=(λ–α)-1(λ–1)(λ–α)(λ–αλ2) (λ–αλ3)…(λ–αλn)

= (λ–1)(λ–αλ2) (λ–αλ3)…(λ–αλn)。

這就證明了下列的定理：

谷歌矩陣譜定理.谷歌矩陣G=αS + (1–α)evT的所有特征值是

1,αλ2,αλ3, …,αλn。

由于每個(gè)λi位于單位圓的內(nèi)部，故

|αλi|<α < 1,i = 2,3,...,n，

因此冪方法的收斂速率取決于參數(shù)值α的大小。這個(gè)值如果取得靠近(0, 1)開區(qū)間的右端點(diǎn)，冪方法的迭代步伐就會(huì)慢下來；反之，若將它取得太小，甚至靠近(0, 1)的左端點(diǎn)，G又與折射出真實(shí)網(wǎng)絡(luò)世界各網(wǎng)頁之間“朋友關(guān)系”的S相距太遠(yuǎn)，這樣計(jì)算雖然快了，但結(jié)果或許有不能全方位反映真實(shí)世界之危險(xiǎn)。總之，選擇參數(shù)α的數(shù)值要顧及到準(zhǔn)確與速度的雙重思量。

就數(shù)學(xué)而言，上面的谷歌矩陣譜定理是下面的秩-1矯正矩陣譜擾動(dòng)定理的一個(gè)特殊化。這個(gè)一般結(jié)果是筆者之一20年前在一篇合作文章中證明的。

秩-1矯正矩陣譜擾動(dòng)定理.設(shè)A為一n階矩陣，其特征值是λ1, λ2, ..., λn。若u和v為兩個(gè)n維向量，其中u是A對(duì)應(yīng)于λ1的特征向量，則A+uvT的特征值是λ1+vTu, λ2, …, λn。

將上述定理中的A取為谷歌矩陣譜定理中的αS，u取為(1–α)e，則如前所述，A的特征值是α,αλ2,αλ3, …,αλn，且u是A對(duì)應(yīng)于α的特征向量。則秩-1矯正矩陣譜擾動(dòng)定理給出G =αS + (1–α)evT的第一個(gè)特征值為

λ1+vTu=α+ (1–α)vTe =α+ (1–α) = 1，

而αS的特征值αλ2,αλ3, …,αλn通通留給了G，得到谷歌矩陣譜定理的結(jié)論。

過去四分之一個(gè)世紀(jì)，PageRank 算法不僅成就了一家商業(yè)巨頭，更深刻改變了人類獲取信息的范式。盡管在今天，隨著人工智能的演進(jìn)和網(wǎng)絡(luò)生態(tài)的更迭，傳統(tǒng)搜索引擎的形態(tài)正經(jīng)歷劇烈的陣痛與重塑，但其背后的數(shù)學(xué)邏輯——通過矩陣刻畫關(guān)聯(lián)、用特征值尋找秩序——依然是處理海量數(shù)據(jù)的核心思想。今天正值國際數(shù)學(xué)日，回望這個(gè)“世界最大矩陣”，我們感嘆的不僅是算法帶來的便利，更是數(shù)學(xué)作為一種普適語言，在紛繁復(fù)雜的現(xiàn)實(shí)世界中剝離混沌、指引真理的純粹力量。