人和人之間的關(guān)系，可以看成是一個網(wǎng)絡(luò)，可以用圖或有向圖來描述，或者說用它們來建模。在本欄目第2期討論一筆畫問題時我們接觸過圖，在第4期談連通問題時針對的也是圖，而在第13期討論網(wǎng)絡(luò)最大流問題時采用的模型則是有向圖。第21期談選舉，也用到了有向圖。圖和有向圖是用算法求解問題中十分常見的一類模型。

取決于所考慮的人群范圍和關(guān)系的定義，社會網(wǎng)絡(luò)，有時也稱社交網(wǎng)絡(luò)，可以多種多樣。最熟悉的，是現(xiàn)實生活中的“熟人”關(guān)系，見面相互都能叫得上名字，用圖來描述就很合適，如圖1（a）所示。而微博博主之間的“粉絲關(guān)系”，不一定是互相的，用圖來表示就不合適了，需要用有向圖，如圖1（b）所示。箭頭方向就表達了粉絲關(guān)系的單向性。如果兩個人互粉，如節(jié)點2和節(jié)點5，那么他們之間就有兩條不同方向的邊。

社會網(wǎng)絡(luò)分析有許多現(xiàn)實的意義。例如，在新冠肺炎疫情期間，發(fā)現(xiàn)一個病例，要確定他有哪些“密接者”，就涉及社會網(wǎng)絡(luò)分析。那種社會網(wǎng)絡(luò)，其中的邊具有時間特性（只是在某個時間段存在），也稱作“接觸網(wǎng)絡(luò)”?，F(xiàn)在一些城市要求市民在一些場所通過掃描特定的二維碼“打卡”，其意義之一就是為了在發(fā)現(xiàn)病例的時候，能夠迅速構(gòu)建與他相關(guān)的接觸網(wǎng)絡(luò)。

本文介紹社會網(wǎng)絡(luò)分析中的兩個基礎(chǔ)算法，讓讀者從中了解社會網(wǎng)絡(luò)分析的一種主要計算模式——矩陣運算①。這類算法，從算法邏輯的角度來說，會顯得比本專欄前面介紹過的那些算法簡單許多，它們的引人入勝之處在于其結(jié)果體現(xiàn)了某些社會現(xiàn)實意義。在討論中，我們總假定網(wǎng)絡(luò)結(jié)構(gòu)是已經(jīng)給定的有向圖，而且采用的是鄰接矩陣表示。在本欄目第4期討論圖的連通問題時，我們用過圖的鄰接矩陣表示。不過那里僅涉及無向圖，鄰接矩陣是對稱的;本文則主要關(guān)注有向圖，鄰接矩陣一般不對稱。例如，圖2（a）就是前面圖1（b）中有向圖的鄰接矩陣表示，其中行和列的編號對應(yīng)圖中的節(jié)點，即第i行第j列的值aij=1，當(dāng)且僅當(dāng)有一條從節(jié)點i指向節(jié)點j的邊。有時候，如果需要表示一個節(jié)點指向自己的情形，就會有aii=1。

對矩陣概念陌生但對編程比較熟悉的讀者，不妨就想像程序語言中的“二維數(shù)組”。在Python中可用二維列表或者numpy中的數(shù)組直接體現(xiàn)，如圖2（a）中的矩陣用二維列表給出就是：

A=[[0，0，1，0，0，0]，

[1，0，1，1，1，0]，

[0，0，0，0，0，0]，

[1，0，0，0，1，0]，

[0，1，1，0，0，1]，

[0，0，1，0，0，0]]

用A[i][j]訪問它的第i行第j列元素。有時候，為方便起見，也用矩陣（數(shù)組）的第i個行向量和第j個列向量來分別指代A[i][j]，j=1，2，…，n和A[i][j]，i=1，2，…，n。注意，它們分別都包含n個元素，視覺形象上對應(yīng)數(shù)組的行和列。

我們要討論的兩個算法，其社會現(xiàn)實意義分別與社會網(wǎng)絡(luò)中人們的“發(fā)言權(quán)”和“影響力”有關(guān)。為了體會這些說法的現(xiàn)實含義，不妨考慮下面這樣一種情境。

設(shè)想在某中學(xué)的一個班里，學(xué)生們相處久了相互已經(jīng)比較熟悉。現(xiàn)在要討論某個話題，如生物多樣性，或者校門口那一棵大槐樹的高度。教師讓每個學(xué)生分別填寫表1，寫出自己的姓名和2～5個認(rèn)為對該話題比較有發(fā)言權(quán)的同學(xué)的姓名。

教師收上來這些紙條，你馬上能意識到，她有了一個社會網(wǎng)絡(luò)的數(shù)據(jù)，而且其中表達的關(guān)系是有方向性的：每個學(xué)生是其中一個節(jié)點，如果學(xué)生i在他的表中提到了學(xué)生j的名字，那么網(wǎng)絡(luò)中就有一條從i指向j的邊。例如，圖3就是一次實際填報數(shù)據(jù)給出的結(jié)果。我們看到每個節(jié)點發(fā)出有若干指向其他節(jié)點的邊（稱為出向邊），同時作為結(jié)果，每個節(jié)點也“收到了”若干來自其他節(jié)點的邊。此處重點是，這種“入向邊的條數(shù)（稱為“入度”），不同節(jié)點很可能是不同的，反映了一個學(xué)生被其他學(xué)生“認(rèn)可”的情況。

一般來說，針對一個話題，每個學(xué)生都會有自己的觀點，有的堅實，有的飄忽，姑且稱其為不同程度的“發(fā)言權(quán)”。而這種程度是被其他同學(xué)看在眼里，表達在上述表格中的。顯然，這種發(fā)言權(quán)意味著某種價值，有高低。我們來介紹一種評估這種價值的計算方法。

按照填表時給學(xué)生的背景意義，我們可以理解，如果節(jié)點i的入度大于節(jié)點j的入度，大致可以說明更多的人認(rèn)為i比j對當(dāng)下話題更有發(fā)言權(quán)。也就是說，節(jié)點的入度可以是發(fā)言權(quán)高低的一種指示器。不過我們還想更進一步，認(rèn)為一個人的發(fā)言權(quán)不光取決于有多少人認(rèn)為他有發(fā)言權(quán)，還取決于認(rèn)為他有發(fā)言權(quán)的人有多大的發(fā)言權(quán)。同時，若某人認(rèn)可的人較多，他的分量體現(xiàn)在一個人身上應(yīng)該較少。直覺上，這是有道理的。利用一些合理的直覺（盡管不一定能證明總是對的），形成啟發(fā)式來指導(dǎo)計算，是利用計算機求解問題的一種基本策略。在本欄目前面的文章中我們已經(jīng)看到過不少例子。在這種思想下，接著就要考慮兩點，一是將啟發(fā)式變成算法，二是在應(yīng)用實踐中檢驗。

下面就是解決這個問題的著名的PageRank算法，它通過迭代同時更新每個節(jié)點的值，直到收斂誤差滿足要求或達到某個預(yù)設(shè)的迭代次數(shù)。算法要點是：在迭代的每一輪，讓每個節(jié)點將自己的當(dāng)前值均分給出向鄰居節(jié)點，同時將從入向鄰居節(jié)點收到的當(dāng)前值加和作為自己下一輪的當(dāng)前值。圖4給出一個示意。關(guān)注左邊圖中的節(jié)點v，它有3個入向鄰居，每個有不同的出度。右邊則是按照上述算法思想對v進行更新的公式。

不難想到，基于有向圖中的連接關(guān)系，對每一個節(jié)點都可以寫出一個類似但不同的公式來。假設(shè)有n個節(jié)點，通常令每個節(jié)點的初值為1/n，按照公式進行迭代，就是PageRank計算的過程。在我們前面設(shè)置的背景問題下，這也就是學(xué)生們對某一個問題的“發(fā)言權(quán)”的計算過程了。

不過，上面只是闡述了“算法思想”。落實到明晰的算法描述還需要做些整理。關(guān)鍵在于“按不同的公式同時更新每個節(jié)點的值”具體怎么實施。這里首先要解決的是不同公式的統(tǒng)一表達問題。

令v=（v1，v2，…，vn）為擬求的網(wǎng)絡(luò)節(jié)點PageRank值的向量，其中每個vi對應(yīng)一個節(jié)點。

為了體現(xiàn)算法思想中的“將當(dāng)前值均分給出向鄰居”，我們在網(wǎng)絡(luò)圖的鄰接矩陣（A）基礎(chǔ)上，用節(jié)點的出度除每一行，得到矩陣A'。圖2（b）就是對應(yīng)圖2（a）的例子。其中第3行有些特別，多出了一個“1”，待下面解釋?，F(xiàn)在重要的是可以看到，向量v左乘A'，即v←vA'，恰好就是按公式對所有節(jié)點的同時更新。為什么呢？請讀者思考體會。

一般地，所謂一個n元行向量v=（v1，v2，…，vn）左乘一個nxn矩陣M，其中元素用mij表示，就是用v和M的每個列向量分別相乘（內(nèi)積），得到一個結(jié)果向量w= （w1， w2，…，wn）。其數(shù)學(xué)關(guān)系就是：

對應(yīng)到程序中的數(shù)組操作表達如下：

w=[0]*n

for i in range（n）：

for j in range（n）：

w[i]=w[i]+v[j]*M[j][i]

注意到我們現(xiàn)在用的矩陣M是A'，如果它的第i列中的第j個元素非0，意味著在網(wǎng)絡(luò)中節(jié)點j指向i，且該元素值是節(jié)點j的出度的倒數(shù)，于是v[j]*M[j][i]正好就是節(jié)點j均分給i的PageRank值。都加起來，就正好是按照算法思想給出的節(jié)點i的更新值。

于是，我們可以寫出算法了。

● PageRank基本更新算法（如下頁表2）

表2中，第4步的具體實現(xiàn)可參考前面的代碼段。這里有一個重要問題提請讀者注意，如果網(wǎng)絡(luò)中有節(jié)點的出度為0，會出現(xiàn)什么情況？在我們談到的“發(fā)言權(quán)問題”背景下不會有這樣的問題（因為假設(shè)每個學(xué)生都按要求提交了一張表），但一般情況下難免，如圖1（b）中的節(jié)點3，就只有入邊沒有出邊。一旦有這種情況，算法第1步就會遇到除數(shù)為0的困難，在這種情況下，通常的處理方法是令該節(jié)點指向自己（圖2（b）矩陣中的A'[3][3]=1就是這么來的）。

不過這還沒有完，還有一個更嚴(yán)重的潛在問題。想想上述PageRank更新規(guī)則的含義，如果某節(jié)點沒有指向其他節(jié)點的邊，它就會表現(xiàn)得很“自私”——不斷從其他節(jié)點吸納價值，全部累積在自己身上，從而讓算法失去意義。為此，PageRank設(shè)計者在算法中增加了一個“同比縮減+等量補償”規(guī)則，也就讓它真正實用了。有進一步興趣的讀者可參閱其他資料，在此不贅述。

另外，值得一提的是迭代過程的收斂問題。理論上，包含“同比縮減+等量補償”規(guī)則的算法總是可以收斂的，但需要無窮時間，因而在實際應(yīng)用中需要有結(jié)束控制。上面的算法描述是依靠預(yù)先設(shè)定的一個迭代次數(shù)，實際中也可以通過判斷相繼兩次迭代結(jié)果之間的誤差來控制。

下面來看社會網(wǎng)絡(luò)分析中的另一個算法。我們還是以前面的班級網(wǎng)絡(luò)為情境，學(xué)生們給出了他們認(rèn)為誰更有發(fā)言權(quán)的數(shù)據(jù)。反過來說，每一個學(xué)生對當(dāng)下話題的觀點就會有一定的“影響力”。如果網(wǎng)絡(luò)中有一條i指向j的邊，那么可以想象j的觀點就會對i有影響。我們來考慮觀點在社會網(wǎng)絡(luò)中的傳播問題。

在有向圖上的觀點傳播，一個簡單模型（DeGroot）是這樣的：假設(shè)每個節(jié)點i有一個代表其觀點的初值vi，構(gòu)成向量v=（v1，v2，…，vn），傳播過程以迭代方式進行，每一輪每個節(jié)點同時用對它有影響的節(jié)點的均值更新自己。就好像在對一些事情的態(tài)度上你會綜合考慮朋友們的態(tài)度，不愿意走極端。

最后會怎么樣？最后所有節(jié)點會收斂到同一個值（記為c）！這似乎是在說在一個封閉世界中，一群人互動，長此以往，大家的觀念會趨同。下面是算得這個共識值的算法。假設(shè)我們還是用前面算PageRank時的初始矩陣A和A'，其中“有影響”的含義如上所述，即節(jié)點受其出向鄰居的影響。

此時我們特別注意到，由于A'是在A的基礎(chǔ)上通過每行除以節(jié)點出度而得，為了符合上面影響力傳播模型的描述，矩陣向量運算時迭代向量應(yīng)該出現(xiàn)在矩陣的右邊（用矩陣的行向量和它相乘），從而體現(xiàn)了“對其有影響的節(jié)點的均值”的要求。這是和PageRank算法的一個本質(zhì)不同。讀者可以嘗試寫出和前面類似的數(shù)學(xué)關(guān)系和數(shù)組操作代碼段。下面是算法描述。

● DeGroot共識算法（如表3）

算法盡管輸出的還是一個向量，但其中的元素趨同，無論初值如何。

那影響力是怎么回事？不是說不同的人有不同的影響力嗎？而且通過前面的討論，“發(fā)言權(quán)”（PageRank值）較高似乎應(yīng)該對應(yīng)影響力較大才是。

細(xì)心的讀者此時也許看出點門道來了。此處以PageRank概念為表征的“發(fā)言權(quán)”的確對共識的形成有著一種精妙的影響，那就是：設(shè)v=（v1，v2，…，vn）為初始觀點向量，c是在DeGroot算法下得到的共識值，記p =（p1，p2，…，pn）為在PageRank算法下得到的結(jié)果，則：

這個結(jié)果的嚴(yán)格證明需要些線性代數(shù)知識，此處略過。它表明，一個人的PageRank值越高，他的觀點在形成群體共識中的作用就越大。PageRank扮演了對其觀點“加權(quán)”的角色。這也意味著，在社會網(wǎng)絡(luò)中，一個人的“發(fā)言權(quán)”，正好也就是它的“影響力”。當(dāng)然，這種“精確的結(jié)論”只是在上述PageRank和DeGroot模型意義下才成立，現(xiàn)實情況自然要復(fù)雜多了。

至此，我們完成了本文所有技術(shù)性討論。此時值得回頭再看看PageRank和DeGroot算法。除了要用到一點非?；A(chǔ)的矩陣向量運算外，算法邏輯本身十分淺顯易懂，也就是說，按照它們寫出程序來會很簡單。不過，這種算法描述的簡單不意味著計算復(fù)雜性低，事實上，從前面給出的數(shù)組操作代碼段可以看到是一個二重循環(huán)，再加上迭代次數(shù)控制，就是一個三重循環(huán)，對于較大n，就會比較耗時。

通過這兩個例子，讀者也許能體會用矩陣表示圖結(jié)構(gòu)對于許多算法描述的便利，要點是認(rèn)識到矩陣向量運算和圖中節(jié)點值的更新規(guī)則之間的對應(yīng)關(guān)系。類似的問題還有很多，如本欄目第21期討論的選舉問題，也是涉及在初始向量元素是全1的輸入下，按照“競賽圖”（完全有向圖）來迭代更新每個選手的得分，最后排出一個高低來。顯然，競賽圖可以用矩陣表示。這里的問題是，如何用矩陣向量計算來描述該算法呢？特別地，參照本文前面的算法，這里需要對矩陣做什么預(yù)處理嗎？如果要做矩陣和向量相乘，向量該放在左邊還是右邊？請有興趣的讀者自行思考回答。

從2019年6月開始，本欄目規(guī)劃的24篇與算法相關(guān)的小文章到這一期就都完成了。這些文章的內(nèi)容，不一定都適合直接在中小學(xué)計算機課上教學(xué)生，但我們相信它們所體現(xiàn)的內(nèi)容范疇和認(rèn)知要求應(yīng)當(dāng)在教師的素養(yǎng)之中，同時也認(rèn)為如果沒有整塊的時間系統(tǒng)學(xué)習(xí)算法知識，這24篇相對獨立的短文當(dāng)適合作為“碎片化學(xué)習(xí)”的素材。目前，我們中小學(xué)計算機課程正在經(jīng)歷一次重大變革，算法無疑是計算機課程的核心。數(shù)理化在我國中小學(xué)能教得很好，算法也應(yīng)該能教好。

釋：①盡管中學(xué)數(shù)學(xué)課沒有包含矩陣方面的內(nèi)容，但我們認(rèn)為在學(xué)習(xí)信息技術(shù)課程（尤其是數(shù)據(jù)結(jié)構(gòu)與算法）的時候，結(jié)合程序中數(shù)組的概念，簡單介紹一點矩陣知識和基本運算，既有很大的益處，也為中學(xué)生的認(rèn)知能力所及。

參考文獻：

[1]（美）大衛(wèi)·伊斯利.網(wǎng)絡(luò)、群體與市場[M].李曉明，王衛(wèi)紅，楊韞麗，譯.北京：清華大學(xué)出版社，2011，10.（關(guān)于PageRank的介紹出現(xiàn)在第14章）

[2]Matthew O. Jackson.The Human Networks[M].New York：Pantheon Books，2019.（162-170頁是DeGroot模型的通俗介紹）

[3]李曉明.連通還是不連通[J].中小學(xué)教材教學(xué)，2019（09）：75-80.

注：作者系北京大學(xué)計算機系原系主任。