社會(huì)網(wǎng)絡(luò)問(wèn)題中的算法

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

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

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

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

對(duì)矩陣概念陌生但對(duì)編程比較熟悉的讀者，不妨就想像程序語(yǔ)言中的“二維數(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]訪問(wèn)它的第i行第j列元素。有時(shí)候，為方便起見(jiàn)，也用矩陣（數(shù)組）的第i個(gè)行向量和第j個(gè)列向量來(lái)分別指代A[i][j]，j=1，2，…，n和A[i][j]，i=1，2，…，n。注意，它們分別都包含n個(gè)元素，視覺(jué)形象上對(duì)應(yīng)數(shù)組的行和列。

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

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

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

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

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

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

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

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

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

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

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

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

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個(gè)元素非0，意味著在網(wǎng)絡(luò)中節(jié)點(diǎn)j指向i，且該元素值是節(jié)點(diǎn)j的出度的倒數(shù)，于是v[j]*M[j][i]正好就是節(jié)點(diǎn)j均分給i的PageRank值。都加起來(lái)，就正好是按照算法思想給出的節(jié)點(diǎn)i的更新值。

于是，我們可以寫(xiě)出算法了。

● PageRank基本更新算法（如下頁(yè)表2）

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

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

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

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

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

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

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

● DeGroot共識(shí)算法（如表3）

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

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

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

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

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

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

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

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

參考文獻(xiàn)：

[1]（美）大衛(wèi)·伊斯利.網(wǎng)絡(luò)、群體與市場(chǎng)[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頁(yè)是DeGroot模型的通俗介紹）

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

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