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

李曉明

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

取決于所考慮的人群范圍和關(guān)系的定義，社會(huì)網(wǎng)絡(luò)，有時(shí)也稱社交網(wǎng)絡(luò)，可以多種多樣。最熟悉的，是現(xiàn)實(shí)生活中的“熟人”關(guān)系，見面相互都能叫得上名字，用圖來描述就很合適，如圖1（a）所示。而微博博主之間的“粉絲關(guān)系”，不一定是互相的，用圖來表示就不合適了，需要用有向圖，如圖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ò)”。現(xiàn)在一些城市要求市民在一些場(chǎng)所通過掃描特定的二維碼“打卡”，其意義之一就是為了在發(fā)現(xiàn)病例的時(shí)候，能夠迅速構(gòu)建與他相關(guān)的接觸網(wǎng)絡(luò)。

本文介紹社會(huì)網(wǎng)絡(luò)分析中的兩個(gè)基礎(chǔ)算法，讓讀者從中了解社會(huì)網(wǎng)絡(luò)分析的一種主要計(jì)算模式——矩陣運(yùn)算①。這類算法，從算法邏輯的角度來說，會(huì)顯得比本專欄前面介紹過的那些算法簡單許多，它們的引人入勝之處在于其結(jié)果體現(xiàn)了某些社會(huì)現(xiàn)實(shí)意義。在討論中，我們總假定網(wǎng)絡(luò)結(jié)構(gòu)是已經(jīng)給定的有向圖，而且采用的是鄰接矩陣表示。在本欄目第4期討論圖的連通問題時(shí)，我們用過圖的鄰接矩陣表示。不過那里僅涉及無向圖，鄰接矩陣是對(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ì)編程比較熟悉的讀者，不妨就想像程序語言中的“二維數(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í)候，為方便起見，也用矩陣（數(shù)組）的第i個(gè)行向量和第j個(gè)列向量來分別指代A[i][j]，j=1，2，…，n和A[i][j]，i=1，2，…，n。注意，它們分別都包含n個(gè)元素，視覺形象上對(duì)應(yīng)數(shù)組的行和列。

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

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

教師收上來這些紙條，你馬上能意識(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)也“收到了”若干來自其他節(jié)點(diǎn)的邊。此處重點(diǎn)是，這種“入向邊的條數(shù)（稱為“入度”），不同節(jié)點(diǎn)很可能是不同的，反映了一個(gè)學(xué)生被其他學(xué)生“認(rèn)可”的情況。

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

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

下面就是解決這個(gè)問題的著名的PageRank算法，它通過迭代同時(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)都可以寫出一個(gè)類似但不同的公式來。假設(shè)有n個(gè)節(jié)點(diǎn)，通常令每個(gè)節(jié)點(diǎn)的初值為1/n，按照公式進(jìn)行迭代，就是PageRank計(jì)算的過程。在我們前面設(shè)置的背景問題下，這也就是學(xué)生們對(duì)某一個(gè)問題的“發(fā)言權(quán)”的計(jì)算過程了。

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