基于持續(xù)同調(diào)的在線社交網(wǎng)絡(luò)傳播研究

邱呂琳，張志堅(jiān)，蔡光程，鐘 慧

（昆明理工大學(xué) 理學(xué)院，云南 昆明 650500）

0 引言

隨著當(dāng)今社會(huì)經(jīng)濟(jì)與科技的飛速發(fā)展，互聯(lián)網(wǎng)已成為一個(gè)重要的新媒體，在人們的學(xué)習(xí)、工作、生活等各個(gè)方面扮演著不可或缺的角色。社交網(wǎng)絡(luò)以人際關(guān)系網(wǎng)為基礎(chǔ)，近年來(lái)發(fā)展迅速，正逐漸融入人們的日常生活并發(fā)揮重要影響，極大豐富了人們的各種需求。與此同時(shí)，在線社交網(wǎng)絡(luò)使得人們不再受到時(shí)間、空間限制，可快捷接收外界信息，并實(shí)時(shí)參與熱點(diǎn)話題討論，發(fā)表自己的觀點(diǎn)。在線社交網(wǎng)絡(luò)在傳播方面已顯示出強(qiáng)大的影響力，例如，“澳洲森林山火”“全球新冠病毒”等新聞事件在微博不斷實(shí)時(shí)發(fā)布消息等。在線社交網(wǎng)絡(luò)信息傳播對(duì)于生活和社會(huì)發(fā)展有著深遠(yuǎn)影響，因此受到了研究者們的廣泛關(guān)注。

近年來(lái)在線社交網(wǎng)絡(luò)信息傳播研究取得了許多進(jìn)展，使人們能夠從信息傳播角度進(jìn)一步理解社交網(wǎng)絡(luò)的屬性和規(guī)則。本文旨在分析在線社交網(wǎng)絡(luò)的信息傳播現(xiàn)象，了解信息傳播規(guī)律，并根據(jù)相關(guān)規(guī)律進(jìn)行引導(dǎo)，從而更好地進(jìn)行信息傳播，同時(shí)最大限度減少虛假消息和不良消息的傳播。要想獲取信息傳播規(guī)律，需要分析社交網(wǎng)絡(luò)圖。然而，目前在分析社交網(wǎng)絡(luò)圖時(shí)，采用最短路徑、介數(shù)中心性、聚類系數(shù)和度分布等度量指標(biāo)研究與認(rèn)識(shí)在線社交網(wǎng)絡(luò)結(jié)構(gòu)。雖然這些指標(biāo)足以提供網(wǎng)絡(luò)圖在特定方面的信息，但無(wú)法提供在線社交網(wǎng)絡(luò)的全面特征。在線社交網(wǎng)絡(luò)存在太多不確定信息，如網(wǎng)絡(luò)節(jié)點(diǎn)分布很難確定，且在線社交網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)量特別龐大，會(huì)隨著時(shí)間不斷變化，屬于動(dòng)態(tài)網(wǎng)絡(luò)，所以對(duì)在線社交網(wǎng)絡(luò)進(jìn)行全面可視化是一個(gè)很有意義的問(wèn)題。因此，本文從拓?fù)浣嵌确治鲈诰€社交網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，對(duì)在線社交網(wǎng)絡(luò)進(jìn)行全面分析。拓?fù)鋵W(xué)中的持續(xù)同調(diào)為社交網(wǎng)絡(luò)圖中存儲(chǔ)信息的全面可視化表示提供了一種新方法。

大量研究致力于理解在線社交網(wǎng)絡(luò)的相關(guān)熱點(diǎn)問(wèn)題，主要研究方法已從早期社會(huì)學(xué)研究領(lǐng)域的實(shí)證研究轉(zhuǎn)向基于小數(shù)據(jù)集的理論研究與驗(yàn)證。本文主要利用持續(xù)同調(diào)方法和代數(shù)拓?fù)涞囊恍┲R(shí)提取在線社交網(wǎng)絡(luò)的拓?fù)涮卣鳎⒒谶@些特征分析在線社交網(wǎng)絡(luò)傳播。

在線社交網(wǎng)絡(luò)分析可總結(jié)為3個(gè)方面：在線社交網(wǎng)絡(luò)結(jié)構(gòu)特征和演化機(jī)制，在線社交網(wǎng)絡(luò)群體行為形成和互動(dòng)規(guī)律，在線社交網(wǎng)絡(luò)信息傳播規(guī)律和演化機(jī)制。在早期社會(huì)學(xué)與圖論的研究基礎(chǔ)上，Kempe 等提出的線性閾值模型LTM（Linear Threshold Model）和獨(dú)立級(jí)聯(lián)模型ICM（Independent Cascade Model）以及借鑒醫(yī)學(xué)研究的傳染病模型SIR（Susceptible Infected Recovered Model）成為描述影響力傳播的主要基礎(chǔ)模型，這些模型描述了社交網(wǎng)絡(luò)中影響力傳播的隨機(jī)性與累積性。后來(lái)許多研究者根據(jù)具體傳播問(wèn)題的特點(diǎn)擴(kuò)展了基本模型，以反映傳播模型的具體傳播特性。目前，Aggarwal已從數(shù)據(jù)挖掘的角度對(duì)社區(qū)發(fā)現(xiàn)、影響力計(jì)算、溝通可視化等方面進(jìn)行了總結(jié)；Kwak 等基于Twitter 的數(shù)據(jù)，對(duì)用戶之間的關(guān)系、用戶影響以及Twitter 上話題的傳播進(jìn)行了實(shí)證分析；Fang 等介紹了在線社交網(wǎng)絡(luò)相關(guān)研究，并從網(wǎng)絡(luò)結(jié)構(gòu)特征與演化機(jī)制、群體行為形成與互動(dòng)規(guī)律、信息傳播規(guī)律與演化機(jī)制3個(gè)維度提出進(jìn)一步的研究方向。在在線社交網(wǎng)絡(luò)信息傳播方面，Guille 等從話題檢測(cè)、傳播建模以及識(shí)別有影響力的傳播者3個(gè)方面進(jìn)行了介紹，為社交網(wǎng)絡(luò)中圍繞信息擴(kuò)散的工作提供全面的分析指導(dǎo)；Zinoviev從傳播者、傳播路徑和傳播機(jī)制出發(fā)，提出博弈論模型來(lái)理解信息傳播，并對(duì)已有研究進(jìn)行總結(jié)。

鑒于在線社交網(wǎng)絡(luò)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及特征，許多研究者提出利用“網(wǎng)絡(luò)復(fù)雜性分析”的方法論進(jìn)行相關(guān)問(wèn)題分析與研究。Watts 等提出一個(gè)小世界網(wǎng)絡(luò)模型，該模型更好地描述了從常規(guī)網(wǎng)絡(luò)到隨機(jī)網(wǎng)絡(luò)的過(guò)渡；Barabdisi 等提出BA 無(wú)標(biāo)度網(wǎng)絡(luò)模型，并根據(jù)模型的增長(zhǎng)算法和優(yōu)先連接特性演示了BA 無(wú)標(biāo)度網(wǎng)絡(luò)演化過(guò)程。根據(jù)社交網(wǎng)絡(luò)的基本功能和特點(diǎn)，田燕等描述了不同類型在線社交網(wǎng)絡(luò)的目的、特點(diǎn)及典型代表，分析了在線社交網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和信息傳輸特點(diǎn)；候夢(mèng)男等提出一種融合拓?fù)鋭?shì)的層次化社區(qū)發(fā)現(xiàn)算法；Claire 等將網(wǎng)絡(luò)圖轉(zhuǎn)換為持續(xù)同調(diào)中的條形碼格式，對(duì)照各種效用度量來(lái)觀察圖之間關(guān)鍵特征的相關(guān)性。因此，使用持續(xù)同調(diào)分析網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)以得到網(wǎng)絡(luò)的傳播變化，同樣是一個(gè)挑戰(zhàn)。

近年來(lái)，利用拓?fù)湫再|(zhì)和單純復(fù)形、持續(xù)同調(diào)性等方法對(duì)復(fù)雜網(wǎng)絡(luò)，特別是加權(quán)網(wǎng)絡(luò)的研究取得了很大進(jìn)展。Carstens 等描述了作者合作網(wǎng)絡(luò)的持續(xù)同調(diào)性，將拓?fù)鋵W(xué)中的單純復(fù)形方法應(yīng)用于網(wǎng)絡(luò)，通過(guò)對(duì)貝蒂數(shù)的定量比較解釋了合作網(wǎng)絡(luò)的持續(xù)同調(diào)性，并通過(guò)分析發(fā)現(xiàn)持續(xù)同調(diào)性在區(qū)分無(wú)標(biāo)度網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)方面也起著重要作用；Dlotko 等提出一種簡(jiǎn)化的持續(xù)同調(diào)計(jì)算復(fù)形方法，從而加深了對(duì)拓?fù)鋯渭儚?fù)形及其計(jì)算方法的理解；Cerri 等研究了多維持續(xù)同調(diào)理論中貝蒂數(shù)的連續(xù)性質(zhì)；Maletic 等采用拓?fù)鋯渭儚?fù)形法構(gòu)造網(wǎng)絡(luò)，并對(duì)復(fù)雜網(wǎng)絡(luò)的持續(xù)同調(diào)性進(jìn)行分析與研究；Kahle探討隨機(jī)網(wǎng)絡(luò)的同調(diào)性與網(wǎng)絡(luò)連通性之間的關(guān)系，為進(jìn)一步理解網(wǎng)絡(luò)拓?fù)湫再|(zhì)與網(wǎng)絡(luò)連通性之間的關(guān)系作了理論準(zhǔn)備。

本文旨在采用一種不同的方法對(duì)社交網(wǎng)絡(luò)進(jìn)行概括，通過(guò)持續(xù)同調(diào)性表示在線社交網(wǎng)絡(luò)圖的傳播特性，使用算法計(jì)算持續(xù)同調(diào)得到相應(yīng)的貝蒂數(shù)和持續(xù)性圖，并獲取社交網(wǎng)絡(luò)的拓?fù)涮卣?，分析其傳播特點(diǎn)。

1 持續(xù)同調(diào)相關(guān)理論

由于同胚對(duì)兩個(gè)空間的拓?fù)湫再|(zhì)相同，本文主要運(yùn)用代數(shù)拓?fù)渲R(shí)構(gòu)造出該空間的同胚型。在研究一個(gè)社交網(wǎng)絡(luò)時(shí)，常把社交網(wǎng)絡(luò)中的各個(gè)用戶看作節(jié)點(diǎn)，用戶之間的關(guān)系看作邊。換言之，可將社會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)視為點(diǎn)云，用持續(xù)同調(diào)方法構(gòu)造一個(gè)由一系列簡(jiǎn)單復(fù)形組成的空間，并用構(gòu)造的空間逼近社會(huì)網(wǎng)絡(luò)空間。持續(xù)同調(diào)性為人們提供了一種在不減少維數(shù)情況下刻畫數(shù)據(jù)全貌的方法。把數(shù)據(jù)放在原始高維空間中得到數(shù)據(jù)里的群集與環(huán)結(jié)構(gòu)個(gè)數(shù)，這種計(jì)算拓?fù)涮卣鞯姆椒榫W(wǎng)絡(luò)圖分析提供了一種新的效用度量。

1.1 圖

在圖論中，將圖

G

定義為一個(gè)有序二元組(

V

,

E

) 。其中，

V

稱為頂集，

E

稱為邊集，

E

與

V

不相交。頂集的元素被稱為頂點(diǎn)，表示對(duì)象；邊集的元素被稱為邊，表示對(duì)象之間的關(guān)系，有不同類型的圖表示頂點(diǎn)之間的不同關(guān)系。在無(wú)向圖中，邊對(duì)稱地連接兩個(gè)頂點(diǎn)；在有向圖中，邊不對(duì)稱地連接兩個(gè)頂點(diǎn)。如果頂點(diǎn)之間的關(guān)系有相互作用的強(qiáng)度，可用加權(quán)網(wǎng)絡(luò)表示這種類型的關(guān)系。有

n

個(gè)頂點(diǎn)的圖

G

可用

n

×

n

個(gè)鄰接矩陣表示，對(duì)于未加權(quán)圖，若有

G

=1，則表示頂點(diǎn)

i

到頂點(diǎn)

j

有一條邊。如果頂點(diǎn)

i

與頂點(diǎn)

j

之間沒(méi)有邊，則

G

=0。如果圖隨時(shí)間變化，則該圖被稱為動(dòng)態(tài)圖，圖中的頂點(diǎn)和邊會(huì)隨著時(shí)間的變化不斷刪除或添加。在在線社交網(wǎng)絡(luò)圖中，用戶被看作節(jié)點(diǎn)，用戶之間的關(guān)系被看作邊。

1.2 持續(xù)同調(diào)

1.2.1 單純復(fù)形與單純同調(diào)

通常，單純復(fù)形是一種抽象代數(shù)結(jié)構(gòu)，由點(diǎn)、邊、三角形、四面體和高維多面體組成。0 維單形是一個(gè)頂點(diǎn)，1維單形是邊，2 維單形是三角形，3 維單形是四面體（見(jiàn)圖1），直到第

k

維，其結(jié)構(gòu)取決于單純復(fù)形的維度。

Fig.1 Simplex圖1 單形

定義1

設(shè)

K

是

n

維歐氏空間

R

中單形的有限集合，稱

K

為單純復(fù)形，簡(jiǎn)稱復(fù)形（見(jiàn)圖2），則有：①若為

K

中的單形，則其任意面都屬于

K

；②若

s

和

s

為

K

中任意兩個(gè)單形，則

s

?

s

或者是空集，或者是

s

與

s

的一個(gè)公共面。

Fig.2 Complex圖2 復(fù)形

在單純復(fù)形中，把這些孔視為以不同維數(shù)的單純形為界的空洞。在0 維中，其是連接分量；在1 維中，其是以邊（1 維單純形）為邊界的環(huán)；在2 維中，其是以三角形為邊界的孔……在

i

維中，其是以

i

維單純形為邊界的孔。單純同調(diào)是指尋找單純復(fù)形中空洞的方法，下面定義兩種特殊類型的鏈，即圈和邊界。單純形包含復(fù)形中最高維單形的所有面，也即是說(shuō)，如果存在一個(gè)二維復(fù)形（具有最高維單形的單純復(fù)形是一個(gè)二維單純形，即三角形），則該復(fù)形還包含所有維數(shù)低于它的面（如邊和頂點(diǎn)）。在同調(diào)理論中，

i

鏈?zhǔn)且粋€(gè)具有整數(shù)系數(shù)的單純復(fù)形

K

所有

i

維單形的和。

K

的所有

i

鏈集合都用

C

(

K

)表示，即

C

(

K

)表示單純復(fù)形上的

i

維鏈群。對(duì)其作邊緣同態(tài)映射：

其中，

C

(

K

)為

K

的所有

i

維鏈，

C

(

K

)通過(guò)此映射后得到幺元的同態(tài)核是

i

維鏈群

C

(

K

)的子群，稱為維閉鏈群，記作

Z

(

K

)。帶有方向向量[

v

,

v

,

v

,…,

v

]的

n

維單純形

K

的邊界（?(

K

)）為：

C

(

K

)中的所有邊界，即經(jīng)過(guò)同態(tài)映射 ?:

C

(

K

)→

C

(

K

)得到的同態(tài)像是

i

維鏈群

C

(

K

)的子群，也是

i

維閉鏈群

Z

(

K

)的子群（因?yàn)檫吘壎际欠忾]的），稱為

i

維邊緣閉鏈群，簡(jiǎn)稱

i

維邊緣邊界群，記作

B

(

K

)。則定義單純復(fù)形

K

的

i

維同調(diào)群為：

第

i

個(gè)連通數(shù)

b

定義為

H

的維度，

b

=dim(

H

) 。

1.2.2 持續(xù)同調(diào)計(jì)算

對(duì)于有限的一組點(diǎn)

X

（如點(diǎn)云數(shù)據(jù)），同調(diào)性不能給出感興趣的信息。

β

給出了連通分支數(shù)目，但這只是點(diǎn)的數(shù)目，其他所有貝蒂數(shù)都是零，因?yàn)榧现袥](méi)有其他維度的洞。因此，可在數(shù)據(jù)上構(gòu)建一個(gè)最大

ε

值的單純復(fù)形，而不是構(gòu)建多個(gè)不同

ε

參數(shù)的單純復(fù)形，然后將其組合成一個(gè)序列。記錄所有點(diǎn)對(duì)之間的距離，并了解何值使得每對(duì)點(diǎn)形成邊。所有隱藏在這些值中的單純復(fù)形形成了一個(gè)連貫的濾流，即為一系列嵌套的復(fù)形。因此，本文不去處理點(diǎn)集，而定義復(fù)形濾流為：由不斷增加的比例參數(shù)

ε

生成的單純復(fù)形序列。

在這樣的結(jié)構(gòu)中，一些洞可能出現(xiàn)，然后消失，這些同源特征的持續(xù)性可被認(rèn)為是數(shù)據(jù)集特征。在一個(gè)濾流中，可以記錄洞的出生，即洞出現(xiàn)的時(shí)間，以及洞的死亡，即洞消失的時(shí)間。持續(xù)同源性的本質(zhì)是對(duì)這些同源特征的出生和死亡進(jìn)行持續(xù)性地追蹤，每個(gè)同源特征的壽命可表示為一個(gè)區(qū)間，其中區(qū)間的起點(diǎn)與終點(diǎn)分別對(duì)應(yīng)同源特征的出生和死亡。對(duì)于給定數(shù)據(jù)集，可通過(guò)持久性條形碼（PB）記錄這些間隔。同樣地，持久性條形碼可通過(guò)持久性圖（PD）表示。下面定義貝蒂數(shù)，并構(gòu)建Vietoris-Rips（VR）復(fù)形。

持續(xù)同調(diào)計(jì)算的理論基礎(chǔ)是刻畫網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，通過(guò)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化分析網(wǎng)絡(luò)社交的變化是有效、合理的。構(gòu)建社交網(wǎng)絡(luò)，計(jì)算相應(yīng)的網(wǎng)絡(luò)拓?fù)渫{(diào)群和貝蒂數(shù)相關(guān)參數(shù)，進(jìn)一步分析網(wǎng)絡(luò)拓?fù)涮匦?。這些同調(diào)空間可用空間維數(shù)來(lái)表征，因此引入貝蒂數(shù)來(lái)量化拓?fù)洳蛔兞浚瑫r(shí)其也是拓?fù)淇臻g的拓?fù)洳蛔兞?。單純?fù)形

K

的

n

個(gè)貝蒂數(shù)表示為

β

：

b

(

X

)=dim(

H

(

X

))，即對(duì)于非負(fù)整數(shù)

k

，定義空間

X

的第

k

個(gè)貝蒂數(shù)

b

(

X

)為

X

第

k

個(gè)同調(diào)群

H

(

X

)的秩（線性無(wú)關(guān)生成子數(shù)）。

添加或刪除網(wǎng)絡(luò)節(jié)點(diǎn)時(shí)，相應(yīng)同調(diào)群和貝蒂數(shù)都會(huì)發(fā)生變化。在網(wǎng)絡(luò)拓?fù)鋱D中，零維貝蒂數(shù)表示網(wǎng)絡(luò)上的連通分支數(shù)，一維貝蒂數(shù)表示網(wǎng)絡(luò)上的環(huán)（一維孔）數(shù)，二維貝蒂數(shù)表示網(wǎng)絡(luò)圖中的空腔數(shù)。貝蒂數(shù)越大，拓?fù)浜x越復(fù)雜。

對(duì)于Vietoris-Rips（VR）復(fù)形，其是一種抽象的代數(shù)結(jié)構(gòu)，能夠表示歐氏空間

E

中的一組點(diǎn)。假設(shè)

G

=(

V

,

E

) 是一個(gè)無(wú)向加權(quán)圖，權(quán)重值為

W

:

V

×

V

→

R

。對(duì)于?

δ

∈

R

，1 維骨架

G

=(

V

,

E

) ?

G

被定義為

G

的子圖，其中

V

=

V

，其邊界集

E

=

E

只包含權(quán)重小于或等于

δ

的邊。然后，對(duì)于?

δ

∈

R

，本文將VR 復(fù)形定義為1 維骨架

G

、

Cl

(

G

) 的團(tuán)復(fù)形，并將Vietoris-Rips 過(guò)濾定義為：

也即是說(shuō)，在此過(guò)濾過(guò)程中，從頂點(diǎn)集開(kāi)始，之后對(duì)邊的權(quán)重從最小權(quán)重

ω

到最大權(quán)重

ω

進(jìn)行排序，并讓參數(shù)

δ

從

ω

增加到

ω

。在每一步中添加相應(yīng)的邊，得到閾值子圖

G

的復(fù)形，因此產(chǎn)生了Vietoris-Rips 過(guò)濾結(jié)構(gòu)。

1.2.3 持續(xù)性圖

隨著Rips 復(fù)形的構(gòu)建，連續(xù)的間隔一起組成持續(xù)性圖。持續(xù)性圖是濾流的點(diǎn)圖，當(dāng)一個(gè)洞出現(xiàn)時(shí)，持續(xù)性圖中的一個(gè)點(diǎn)會(huì)被標(biāo)記出，該洞即具有包圍開(kāi)放空間的邊緣結(jié)構(gòu)。持續(xù)性圖的橫坐標(biāo)代表開(kāi)始時(shí)間，標(biāo)志著一個(gè)洞的誕生；縱坐標(biāo)代表洞消失的地方。該間隔通常被稱為特征持續(xù)時(shí)間，持續(xù)性圖可定性地描述持續(xù)同調(diào)。

2 基于持續(xù)同調(diào)的社交網(wǎng)絡(luò)傳播特征

從根本上說(shuō)，持續(xù)同調(diào)是用來(lái)檢測(cè)空間的一種方法，該方法是理想的，因?yàn)殡S著復(fù)形的增加，貝蒂數(shù)趨于穩(wěn)定，即會(huì)生成穩(wěn)定的持續(xù)性圖。當(dāng)距離

δ

很小時(shí)，會(huì)有一些斷開(kāi)的組件。當(dāng)

δ

足夠長(zhǎng)時(shí)，該圖成為一個(gè)連接圖，斷開(kāi)的組件組合成一個(gè)。因此，所有持續(xù)性圖都有一個(gè)無(wú)限持續(xù)下去的持續(xù)性點(diǎn)。對(duì)應(yīng)在網(wǎng)絡(luò)圖中，當(dāng)距離較小時(shí)用戶緊密相連，從信息迅速傳播到最后信息傳播完成，形成一個(gè)穩(wěn)定的圈。

運(yùn)用代數(shù)拓?fù)渲谐掷m(xù)同調(diào)的知識(shí)對(duì)在線社交網(wǎng)絡(luò)構(gòu)造VR 復(fù)形，將在線社交網(wǎng)絡(luò)邊數(shù)據(jù)集生成距離矩陣，再使用perseus 軟件計(jì)算得出貝蒂數(shù)和持續(xù)性圖，從而分析在線社交網(wǎng)絡(luò)的傳播特征。具體方法如下：

2.1 貝蒂數(shù)持續(xù)性圖計(jì)算算法

利用圖描述社交網(wǎng)絡(luò)時(shí)，節(jié)點(diǎn)表示社交網(wǎng)絡(luò)中的用戶，邊表示用戶之間的關(guān)系，有關(guān)系則為“1”，沒(méi)有關(guān)系則為“0”。社交網(wǎng)絡(luò)中關(guān)注的是節(jié)點(diǎn)間的連接關(guān)系，并不強(qiáng)調(diào)坐標(biāo)位置。因此，本文首先利用Floyd算法計(jì)算得到距離矩陣，再將距離矩陣導(dǎo)入Perseus 軟件，最后通過(guò)Perseus 軟件計(jì)算得到社交網(wǎng)絡(luò)圖的貝蒂數(shù)和持續(xù)性圖。

2.1.1 數(shù)據(jù)處理

由于在線社交網(wǎng)絡(luò)往往較為龐大，為方便進(jìn)行持續(xù)同調(diào)相關(guān)計(jì)算，本文使用隨機(jī)游走算法對(duì)數(shù)據(jù)進(jìn)行處理，在有效保護(hù)網(wǎng)絡(luò)的同時(shí)，創(chuàng)建一個(gè)可行的數(shù)據(jù)集。隨機(jī)游走算法通常被視為一些隨機(jī)過(guò)程的基本模型，并被視為馬爾可夫過(guò)程。隨機(jī)游走算法的基本思想是從一個(gè)頂點(diǎn)或一系列頂點(diǎn)游走一個(gè)圖，在任何頂點(diǎn)中，遍歷者將以概率1-

a

移動(dòng)到此頂點(diǎn)的相鄰頂點(diǎn)，并以概率

a

隨機(jī)跳到圖中任何頂點(diǎn)，

a

稱為跳躍發(fā)生概率。每次行走后都會(huì)得到一個(gè)概率分布，此概率分布描述了圖中每個(gè)頂點(diǎn)被訪問(wèn)的概率。使用此概率分布作為下一次行走的輸入，并迭代該過(guò)程。當(dāng)滿足一定條件時(shí)，概率分布趨于收斂，得到平穩(wěn)的概率分布。一維的隨機(jī)游走可定義如下：每過(guò)一個(gè)單位時(shí)間，游走者從數(shù)軸位置

x

出發(fā)，以固定概率隨機(jī)向左或向右移動(dòng)一個(gè)單位。不妨將

n

時(shí)刻游走者的位置記為

L

，則有：

其中，

X

,

X

,

…X

為相互獨(dú)立的隨機(jī)變量，滿足：

在本文中，偽隨機(jī)數(shù)生成器從原始在線社交網(wǎng)絡(luò)圖中選擇一個(gè)節(jié)點(diǎn)作為起點(diǎn)，接下來(lái)將相同節(jié)點(diǎn)作為第一個(gè)節(jié)點(diǎn)添加到新的圖

G

′中。此后，程序查看連接到原始圖中當(dāng)前節(jié)點(diǎn)的邊，并隨機(jī)選擇一個(gè)進(jìn)行遍歷，同時(shí)將相同的邊添加到新的圖

G

′中。整個(gè)過(guò)程經(jīng)歷了多次迭代，直到新構(gòu)建的圖

G

′完全包含一部分節(jié)點(diǎn)，本文取得的節(jié)點(diǎn)數(shù)為100。

2.1.2 距離矩陣形成

此時(shí)初始化一個(gè)鄰接矩陣作為輔助，即在給定一組節(jié)點(diǎn)時(shí)，一個(gè)鄰接矩陣表示其邊關(guān)系。該矩陣表示在具有“1”和“0”的一對(duì)節(jié)點(diǎn)之間是否存在一條邊，“1”表示兩節(jié)點(diǎn)間存在一條邊，“0”表示兩節(jié)點(diǎn)間不存在邊。然后使用Floyd算法，通過(guò)Python 計(jì)算得出距離矩陣。下面簡(jiǎn)單介紹Floyd算法以及距離矩陣。

Floyd算法又稱為插點(diǎn)法，是一種利用動(dòng)態(tài)規(guī)劃的思想尋找給定加權(quán)圖中多源點(diǎn)之間最短路徑的算法。首先，從任意一條單邊路徑開(kāi)始，所有兩點(diǎn)之間的距離是邊的權(quán)，這里設(shè)所有邊的權(quán)值為1。如果兩點(diǎn)之間沒(méi)有邊相連，則權(quán)為無(wú)窮大。對(duì)于每一對(duì)頂點(diǎn)

u

和

v

，看看是否存在一個(gè)頂點(diǎn)

w

，使得從

u

到

w

再到

v

比已知路徑更短，如果是則對(duì)其進(jìn)行更新。用鄰接矩陣

G

表示圖，如果從

v

到

v

有路可達(dá)，則

G

=

d

，

d

表示該路的長(zhǎng)度，否則

G

=

∞

。定義一個(gè)矩陣

D

用來(lái)記錄所插入點(diǎn)的信息，

D

表示從

v

到

v

需要經(jīng)過(guò)的點(diǎn)，初始化

D

=

j

。把各個(gè)頂點(diǎn)插入圖中，比較插點(diǎn)后的距離與原來(lái)的距離，

G

=min(

G

,

G

+

G

) 。如果

G

的值變小，則

D

=

k

。由此便可得到任意兩點(diǎn)間的距離信息，一個(gè)距離矩陣是一個(gè)包含一組點(diǎn)兩兩之間距離的矩陣（即二維數(shù)組），所以可將距離信息轉(zhuǎn)換成距離矩陣。

2.1.3 持續(xù)性圖生成

對(duì)數(shù)據(jù)進(jìn)行處理后，首先運(yùn)用Floyd算法對(duì)處理得到的100個(gè)點(diǎn)計(jì)算得出距離矩陣，然后利用持續(xù)同調(diào)計(jì)算軟件計(jì)算得出各維數(shù)的持續(xù)性間隔以及各維貝蒂數(shù)，最后得到持續(xù)性圖（見(jiàn)圖3）。

Fig.3 Steps to generate a persistence diagram圖3 持續(xù)性圖生成步驟

2.2 小型社交網(wǎng)絡(luò)持續(xù)性信息獲取示例

已知兩個(gè)小型社交網(wǎng)絡(luò)，節(jié)點(diǎn)與節(jié)點(diǎn)之間的關(guān)系如圖4、圖5 所示。利用Floyd算法計(jì)算得到兩個(gè)小型網(wǎng)絡(luò)圖的8 × 8 距離矩陣，分別如下：

Fig.4 Small network diagram a圖4 小型網(wǎng)絡(luò)圖a

Fig.5 Small network diagram b圖5 小型網(wǎng)絡(luò)圖b

此時(shí)通過(guò)貝蒂數(shù)持續(xù)性圖計(jì)算方法得出兩個(gè)社交網(wǎng)絡(luò)的貝蒂數(shù)分別如表1、表2 所示。

Table 1 Betti number of small network diagram a表1 小型網(wǎng)絡(luò)圖a 的貝蒂數(shù)

Table 2 Betti number of small network diagram b表2 小型網(wǎng)絡(luò)圖b 的貝蒂數(shù)

在網(wǎng)絡(luò)拓?fù)鋱D中，零維貝蒂數(shù)表示網(wǎng)絡(luò)上的連通分支數(shù)，一維貝蒂數(shù)表示網(wǎng)絡(luò)上的環(huán)（一維孔）數(shù)，二維貝蒂數(shù)表示網(wǎng)絡(luò)圖中的空腔數(shù)，貝蒂數(shù)越大，拓?fù)浜x越復(fù)雜。

對(duì)于圖4，一開(kāi)始它有8個(gè)連通分支（即一開(kāi)始的8個(gè)節(jié)點(diǎn)），更高維的貝蒂數(shù)為零；形成第一個(gè)子復(fù)形時(shí)，零維貝蒂數(shù)為1，即連通分支數(shù)為1，一維貝蒂數(shù)為2，即有2個(gè)圈，沒(méi)有更高維的貝蒂數(shù)；形成第二個(gè)復(fù)形時(shí)，零維貝蒂數(shù)為1，沒(méi)有一、二維的貝蒂數(shù)，三維貝蒂數(shù)為5，即更高一維的三維空間有5個(gè)空洞；形成第三個(gè)復(fù)形時(shí)，零維貝蒂數(shù)為1，沒(méi)有一、二維的貝蒂數(shù)，三維貝蒂數(shù)為35，即更高一維的三維空間有35個(gè)空洞；沒(méi)有再形成更多復(fù)形。

對(duì)于圖5，同樣一開(kāi)始它有8個(gè)連通分支，更高維的貝蒂數(shù)為零；形成第一個(gè)子復(fù)形時(shí)，零維貝蒂數(shù)為1，即連通分支數(shù)為1，沒(méi)有更高維的貝蒂數(shù)；形成第二個(gè)復(fù)形時(shí)，零維貝蒂數(shù)為1，沒(méi)有一、二維的貝蒂數(shù)，三維貝蒂數(shù)為25，即更高一維的三維空間有25個(gè)空洞；形成第三個(gè)復(fù)形時(shí)，零維貝蒂數(shù)為1，沒(méi)有一、二維的貝蒂數(shù)，三維貝蒂數(shù)為35，即更高一維的三維空間有35個(gè)空洞；沒(méi)有再形成更多復(fù)形。

圖4 和圖5 是兩個(gè)小型網(wǎng)絡(luò)圖，都擁有8個(gè)節(jié)點(diǎn)，從圖中可以看出，圖4 相對(duì)于圖5 節(jié)點(diǎn)與節(jié)點(diǎn)之間的聯(lián)系更緊密。所以圖4 各個(gè)節(jié)點(diǎn)之間的距離比圖5 更近，如果是節(jié)點(diǎn)之間相互傳播，圖4 相對(duì)于圖5 也更為容易，而這一點(diǎn)在持續(xù)同調(diào)計(jì)算得出的貝蒂數(shù)中得到了驗(yàn)證。表1 的貝蒂數(shù)總的來(lái)說(shuō)少于表2 的貝蒂數(shù)。

小型網(wǎng)絡(luò)圖的持續(xù)性圖如圖6 所示。

Fig.6 Persistence diagram of small network diagram圖6 小型網(wǎng)絡(luò)圖的持續(xù)性圖

其中，橫坐標(biāo)表示持續(xù)性點(diǎn)的出生時(shí)間，縱坐標(biāo)表示持續(xù)性點(diǎn)的死亡時(shí)間。

對(duì)于持續(xù)性圖，具有無(wú)限持續(xù)性點(diǎn)的出生時(shí)間被繪制為紅色菱形，即在網(wǎng)絡(luò)圖a 的持續(xù)性圖中有出生時(shí)間為2 和3 的兩個(gè)持續(xù)性點(diǎn)，網(wǎng)絡(luò)圖b 的持續(xù)性圖中只有1個(gè)出生時(shí)間為3 的持續(xù)性點(diǎn)。

通過(guò)示例可以看出：該方法充分捕捉了網(wǎng)絡(luò)拓?fù)涮卣?，可?jì)算出網(wǎng)絡(luò)拓?fù)湫畔?，得到的拓?fù)湫畔⑴c網(wǎng)絡(luò)圖的圖像一致，并且可根據(jù)拓?fù)湫畔嫵龀掷m(xù)性圖；節(jié)點(diǎn)間聯(lián)系更緊密的網(wǎng)絡(luò)圖更容易傳播，且其貝蒂數(shù)更大，傳播更容易擴(kuò)散；節(jié)點(diǎn)間聯(lián)系更緊密的網(wǎng)絡(luò)圖的持續(xù)性點(diǎn)數(shù)量多于稀疏的網(wǎng)絡(luò)圖；貝蒂數(shù)在零維、一維和二維中表現(xiàn)出持續(xù)同調(diào)性。

3 數(shù)值實(shí)驗(yàn)

選取SNAP數(shù)據(jù)庫(kù)中Facebook、Deezer 和Wiki-Vote的3個(gè)社交網(wǎng)絡(luò)圖，每個(gè)圖都提供了邊列表（每個(gè)邊列表數(shù)據(jù)由兩個(gè)節(jié)點(diǎn)ID 組成）。所有包含的數(shù)據(jù)集都滿足社交網(wǎng)絡(luò)標(biāo)準(zhǔn)，即一個(gè)簡(jiǎn)單、未加權(quán)的網(wǎng)絡(luò)圖。具體來(lái)說(shuō)，F(xiàn)acebook 網(wǎng)絡(luò)圖代表匿名社交圈人與人之間的關(guān)系，Deezer 網(wǎng)絡(luò)圖表示在線音樂(lè)網(wǎng)站中在線社交網(wǎng)絡(luò)的信息，而Wiki-Vote 網(wǎng)絡(luò)圖是由世界各地的志愿者合作編寫的免費(fèi)百科全書(shū)。上述社交網(wǎng)絡(luò)來(lái)自于大眾廣泛使用的社交媒體平臺(tái)，可使本文能更好地模擬持續(xù)同調(diào)的實(shí)際應(yīng)用。

對(duì)每個(gè)在線社交網(wǎng)絡(luò)的研究，主要是分析網(wǎng)絡(luò)所對(duì)應(yīng)的持續(xù)性圖。通過(guò)對(duì)每個(gè)使得持續(xù)性圖穩(wěn)定區(qū)間的分析與研究，可得到社交網(wǎng)絡(luò)空間的同調(diào)信息。這些同調(diào)信息可幫助獲取在線社交網(wǎng)絡(luò)的空間特點(diǎn)，從而分析其傳播變化。

3.1 網(wǎng)絡(luò)圖比較

Facebook、Deezer 和Wiki-Vote 網(wǎng)絡(luò)數(shù)據(jù)集都包含了節(jié)點(diǎn)數(shù)據(jù)和邊數(shù)據(jù)，通過(guò)邊數(shù)據(jù)獲取節(jié)點(diǎn)間的關(guān)聯(lián)信息，若形成邊則為“1”，若沒(méi)有形成邊則為“0”，由此生成網(wǎng)絡(luò)圖如圖7-圖9 所示。

Fig.7 Facebook network diagram圖7 Facebook 網(wǎng)絡(luò)圖

Fig.8 Wiki-Vote network diagram圖8 Wiki-Vote 網(wǎng)絡(luò)圖

Fig.9 Deezer network diagram圖9 Deezer 網(wǎng)絡(luò)圖

圖7-圖9 分別是Facebook、Wiki-Vote 以及Deezer 3個(gè)網(wǎng)絡(luò)在經(jīng)過(guò)數(shù)據(jù)處理后100個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)圖，從圖中可以看出，F(xiàn)acebook 網(wǎng)絡(luò)圖分成了3個(gè)團(tuán)，且各個(gè)團(tuán)中各節(jié)點(diǎn)相互之間聯(lián)系緊密，具有很強(qiáng)的互聯(lián)性，這也對(duì)應(yīng)表現(xiàn)出Facebook 各個(gè)用戶之間的聯(lián)系。Wiki-Vote 與Deezer 兩個(gè)社交網(wǎng)絡(luò)的網(wǎng)絡(luò)圖則呈現(xiàn)出一個(gè)節(jié)點(diǎn)被其他多個(gè)節(jié)點(diǎn)連接，出現(xiàn)了類似于環(huán)狀結(jié)構(gòu)，這與3個(gè)網(wǎng)絡(luò)的類型有一定聯(lián)系。在現(xiàn)實(shí)世界中，F(xiàn)acebook 網(wǎng)絡(luò)圖代表匿名社交圈的人際關(guān)系，每個(gè)用戶之間都存在相互聯(lián)系的可能，所以圖中所有節(jié)點(diǎn)之間始終具有很強(qiáng)的互連性；Wiki-Vote 網(wǎng)絡(luò)圖是用多種語(yǔ)言編寫而成的網(wǎng)絡(luò)百科全書(shū)，其基于維基技術(shù)的多語(yǔ)言百科全書(shū)式協(xié)作計(jì)劃，所以其一個(gè)節(jié)點(diǎn)連接到多個(gè)端節(jié)點(diǎn)，形成環(huán)狀；Deezer 網(wǎng)絡(luò)圖代表法國(guó)在線音樂(lè)網(wǎng)站，可提供樂(lè)隊(duì)與歌曲搜索及音樂(lè)播放等功能，通常在圖的中心創(chuàng)建一個(gè)環(huán)，而邊界節(jié)點(diǎn)保持連接。

3.2 貝蒂數(shù)比較

根據(jù)節(jié)點(diǎn)以及邊關(guān)系，對(duì)Facebook、Deezer 和Wiki-Vote 3個(gè)社交網(wǎng)絡(luò)分別創(chuàng)建距離矩陣，通過(guò)持續(xù)同調(diào)計(jì)算，分別生成3個(gè)網(wǎng)絡(luò)圖的零維貝蒂數(shù)、一維貝蒂數(shù)及二維貝蒂數(shù)（見(jiàn)表3-表5），分析并比較其傳播規(guī)律。

Table 3 Facebook Betti number表3 Facebook 貝蒂數(shù)

Table 4 Wiki-Vote Betti number表4 Wiki-Vote 貝蒂數(shù)

Table 5 Deezer Betti number表5 Deezer 貝蒂數(shù)

從表3 數(shù)據(jù)中可以看出，當(dāng)沒(méi)有形成子復(fù)形時(shí)，F(xiàn)acebook 網(wǎng)絡(luò)對(duì)應(yīng)的零維貝蒂數(shù)為100，即連通分支數(shù)量為100（本文選取100個(gè)節(jié)點(diǎn)），更高維的貝蒂數(shù)都為0；形成第一個(gè)子復(fù)形時(shí)，零維貝蒂數(shù)為1，即連通分支數(shù)為1，一維貝蒂數(shù)為10，即有10個(gè)圈，二維貝蒂數(shù)為1，即有1個(gè)洞，沒(méi)有更高維的貝蒂數(shù)；形成第二個(gè)復(fù)形時(shí)，零維貝蒂數(shù)為1，沒(méi)有一、二維的貝蒂數(shù)；之后隨著子復(fù)形的增加，零維、一維、二維貝蒂數(shù)均沒(méi)有發(fā)生變化；直到第9個(gè)子復(fù)形形成，之后沒(méi)有再形成更多復(fù)形。

同理，從表4 的數(shù)據(jù)中，一開(kāi)始零維貝蒂數(shù)都為100，即連通分支數(shù)量為100，一維貝蒂數(shù)為12，二維貝蒂數(shù)為6；當(dāng)?shù)诙€(gè)子復(fù)形形成時(shí)，零維貝蒂數(shù)變?yōu)?，而一、二維貝蒂數(shù)分別為19 和0；當(dāng)?shù)谌齻€(gè)子復(fù)形形成時(shí)，零維貝蒂數(shù)依然為1，而一、二維貝蒂數(shù)變?yōu)?；該情況一直持續(xù)到第四個(gè)子復(fù)形形成，之后沒(méi)有再形成更多復(fù)形。

表5 的數(shù)據(jù)情況與表3 類似，一開(kāi)始零維貝蒂數(shù)都為100，第二個(gè)子復(fù)形形成時(shí)，零維貝蒂數(shù)變?yōu)?，而一、二維貝蒂數(shù)分別為10 和3；當(dāng)?shù)谌齻€(gè)子復(fù)形形成時(shí)，零維貝蒂數(shù)依然為1，沒(méi)有一、二維貝蒂數(shù)；直到第四個(gè)子復(fù)形形成，之后沒(méi)有再形成更多復(fù)形。

從表中3 組數(shù)據(jù)可以看出，當(dāng)沒(méi)有子復(fù)形形成時(shí)，3個(gè)網(wǎng)絡(luò)圖對(duì)應(yīng)的零維貝蒂數(shù)都為100，即連通分支數(shù)量為100（本文選取100個(gè)節(jié)點(diǎn)）。Facebook 網(wǎng)絡(luò)和Deezer 網(wǎng)絡(luò)的一、二維貝蒂數(shù)都為0，而在Wiki-Vote 網(wǎng)絡(luò)中，一維貝蒂數(shù)為12，二維貝蒂數(shù)為6，這是由于Wiki-Vote 網(wǎng)絡(luò)是一個(gè)百科全書(shū)網(wǎng)絡(luò)。從網(wǎng)絡(luò)圖中可以發(fā)現(xiàn)，它有一些圈和洞產(chǎn)生，即一、二維貝蒂數(shù)。隨著子復(fù)形個(gè)數(shù)的增加，連通分支的個(gè)數(shù)逐漸穩(wěn)定為1，而更高維的圈、洞個(gè)數(shù)逐漸變?yōu)?，此時(shí)意味著傳播結(jié)束。從整個(gè)貝蒂數(shù)表格數(shù)據(jù)中可以看出，F(xiàn)acebook 網(wǎng)絡(luò)和Deezer 網(wǎng)絡(luò)在第二個(gè)復(fù)形形成時(shí)的一維貝蒂數(shù)都小于Wiki-Vote 網(wǎng)絡(luò)，說(shuō)明Facebook 網(wǎng)絡(luò)和Deezer網(wǎng)絡(luò)的傳播更容易擴(kuò)散，更有利于傳播，而Wiki-Vote 網(wǎng)絡(luò)不容易激活很多節(jié)點(diǎn)，傳播力相對(duì)弱一些，傳播更為困難。因此，可利用貝蒂數(shù)來(lái)刻畫在線社交網(wǎng)絡(luò)的傳播。

3.3 持續(xù)性圖比較

根據(jù)節(jié)點(diǎn)以及邊關(guān)系，對(duì)3個(gè)社交網(wǎng)絡(luò)分別創(chuàng)建距離矩陣，由此生成3個(gè)網(wǎng)絡(luò)圖的持續(xù)性圖（見(jiàn)圖10），分析比較其傳播變化規(guī)律。

對(duì)于持續(xù)性圖，具有無(wú)限持續(xù)性點(diǎn)的出生時(shí)間被繪制為紅色菱形。從3個(gè)持續(xù)性圖可以看出，F(xiàn)acebook 網(wǎng)絡(luò)的持續(xù)性圖有9個(gè)紅色菱形，即有9個(gè)無(wú)限持續(xù)性點(diǎn)，與上述貝蒂數(shù)中的子復(fù)形個(gè)數(shù)相對(duì)應(yīng)；Wiki-Vote 網(wǎng)絡(luò)的持續(xù)性圖有4個(gè)紅色菱形，即有4個(gè)無(wú)限持續(xù)性點(diǎn)；Deezer 網(wǎng)絡(luò)的持續(xù)性圖同樣有4個(gè)紅色菱形，即有4個(gè)無(wú)限持續(xù)性點(diǎn)。對(duì)于持續(xù)性點(diǎn)，圖結(jié)構(gòu)越復(fù)雜，其持續(xù)性點(diǎn)也會(huì)更多。從以上3個(gè)持續(xù)性圖可以看出，F(xiàn)acebook 網(wǎng)絡(luò)的無(wú)限持續(xù)性點(diǎn)多于Wiki-Vote 網(wǎng)絡(luò)和Deezer 網(wǎng)絡(luò)，說(shuō)明Facebook 網(wǎng)絡(luò)比Deezer 網(wǎng)絡(luò)和Wiki-Vote 網(wǎng)絡(luò)更利于傳播，而Deezer 網(wǎng)絡(luò)和Wiki-Vote 網(wǎng)絡(luò)的傳播力相對(duì)弱一些，傳播更為困難。說(shuō)明Wiki-Vote 網(wǎng)絡(luò)和Deezer 網(wǎng)絡(luò)相對(duì)于Facebook 網(wǎng)絡(luò)更穩(wěn)定，這也很好地驗(yàn)證了上述小型網(wǎng)絡(luò)圖示例得出的結(jié)論。因此，持續(xù)性圖也可用來(lái)刻畫在線社交網(wǎng)絡(luò)的傳播。

Fig.10 Persistence diagram of online social networks圖10 在線社交網(wǎng)絡(luò)的持續(xù)性圖

4 結(jié)語(yǔ)

社交網(wǎng)絡(luò)傳播是在線社交網(wǎng)絡(luò)的重要研究?jī)?nèi)容，本文主要運(yùn)用持續(xù)同調(diào)方法構(gòu)造一系列單純復(fù)形來(lái)逼近社交網(wǎng)絡(luò)空間，得到社交網(wǎng)絡(luò)的同調(diào)信息，再將這些信息寫入持續(xù)性圖中，通過(guò)貝蒂數(shù)和持續(xù)性圖的穩(wěn)定信息分析在線社交網(wǎng)絡(luò)傳播。在一定程度下，盡管在線社交網(wǎng)絡(luò)會(huì)發(fā)生變化（在線社交網(wǎng)絡(luò)本就屬于動(dòng)態(tài)網(wǎng)絡(luò)），對(duì)本文要得到的同調(diào)信息也幾乎沒(méi)有影響。從本文得出的結(jié)論中，發(fā)現(xiàn)持續(xù)同調(diào)性可作為描述社交網(wǎng)絡(luò)圖傳播的一種手段。根據(jù)已有數(shù)據(jù)顯示，該方法充分捕捉了網(wǎng)絡(luò)拓?fù)涮卣?，為在線社交網(wǎng)絡(luò)圖描述傳播提供了有效的新方法。在后續(xù)工作中將采用更大的數(shù)據(jù)集，并根據(jù)在線社交網(wǎng)絡(luò)得到的持續(xù)同調(diào)對(duì)在線社交網(wǎng)絡(luò)傳播進(jìn)行更深入研究。