李曉明

人和人之間的關(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）所示。箭頭方向就表達(dá)了粉絲關(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ù)，而且其中表達(dá)的關(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é)看在眼里，表達(dá)在上述表格中的。顯然，這種發(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é)點的值，直到收斂誤差滿足要求或達(dá)到某個預(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)一表達(dá)問題。