錢(qián) 榕，王嘉瑞，邢方遠(yuǎn)，許建婷，張克君

1.北京電子科技學(xué)院，北京 100070

2.西安電子科技大學(xué)，西安 710071

在復(fù)雜網(wǎng)絡(luò)[1]領(lǐng)域，節(jié)點(diǎn)重要性排序[2]在交通規(guī)劃、流行病傳播[3]、輿情監(jiān)控、商品推薦等領(lǐng)域都有著廣泛的應(yīng)用。研究者們已經(jīng)提出了許多重要節(jié)點(diǎn)排序的經(jīng)典算法，比如K-shell 算法[4]、HITs（hyperlink-induced topic search）算法[5]、PageRank算法[6]等。其中，K-shell算法計(jì)算復(fù)雜度低，適用于大型網(wǎng)絡(luò)，但該算法對(duì)節(jié)點(diǎn)重要性的區(qū)分度不高，是一種粗粒度的重要性排序方法，對(duì)于一些特殊網(wǎng)絡(luò)結(jié)構(gòu)，如星形網(wǎng)絡(luò)[7]等，無(wú)法發(fā)揮作用。HITs 算法開(kāi)創(chuàng)了用不同指標(biāo)同時(shí)評(píng)價(jià)網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的先例，但真實(shí)的網(wǎng)絡(luò)中存在很多特殊的結(jié)構(gòu)，如內(nèi)部鏈接十分緊密的社團(tuán)結(jié)構(gòu)[8]，這會(huì)導(dǎo)致社團(tuán)內(nèi)的節(jié)點(diǎn)權(quán)威值和樞紐值相互增強(qiáng)，使得結(jié)果出現(xiàn)偏差。PageRank算法在社交網(wǎng)絡(luò)[9]分析中也有著廣泛的應(yīng)用，但在實(shí)際的社交網(wǎng)絡(luò)中，人與人之間有著十分復(fù)雜的關(guān)系，PageRank中均等的分配策略顯然是不符合實(shí)際的。

針對(duì)以上算法的不足，鐘林峰提出了一種基于迭代資源分配的關(guān)鍵節(jié)點(diǎn)挖掘算法（iterative resource allocation，IRA）[10]，并從傳播學(xué)的角度對(duì)該算法進(jìn)行了改進(jìn)，提出了基于節(jié)點(diǎn)傳播屬性的迭代資源分配改進(jìn)算法（improved iterative resource allocation，IIRA），并取得了良好的效果。

但是無(wú)論是IRA 算法還是IIRA 算法，都需要以其他算法的中心性指標(biāo)作為資源分配的依據(jù)，一定程度上依賴輸入指標(biāo)的準(zhǔn)確度。在社交網(wǎng)絡(luò)中，信息往往更容易在兩個(gè)更為相似的節(jié)點(diǎn)之間傳播，以節(jié)點(diǎn)中心性指標(biāo)作為資源分配的依據(jù)本身并不準(zhǔn)確且無(wú)法衡量這種相似程度，在傳播過(guò)程中以節(jié)點(diǎn)相似度作為資源分配的依據(jù)更具有合理性。因此本文將節(jié)點(diǎn)的相似度作為資源分配的依據(jù)，提出了SBRA（similarity-based resource allocation）算法。除此之外，基于傳播概率的IIRA算法在設(shè)計(jì)之初就存在一個(gè)假設(shè)，即只有直接相連的節(jié)點(diǎn)之間才會(huì)存在資源的傳遞。但在實(shí)際的社交網(wǎng)絡(luò)中，影響力不僅在直接相連的節(jié)點(diǎn)之間傳播，而且會(huì)向節(jié)點(diǎn)的二階鄰居節(jié)點(diǎn)甚至更遠(yuǎn)的鄰居節(jié)點(diǎn)傳播。針對(duì)這一問(wèn)題，本文將LeaderRank 算法[11]的背景節(jié)點(diǎn)思想引入SBRA算法，提出了基于節(jié)點(diǎn)相似度和高階資源流動(dòng)的L-SBRA（LeaderRank similarity-based resource allocation）算法，解決了非直接相鄰節(jié)點(diǎn)間的資源傳播問(wèn)題，使得該算法更適用于社交網(wǎng)絡(luò)。

1 IRA算法體系

1.1 IRA算法

經(jīng)典的節(jié)點(diǎn)重要性算法大多是基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，即基于節(jié)點(diǎn)的屬性信息。而IRA算法認(rèn)為，節(jié)點(diǎn)的重要性不僅與自身的屬性相關(guān)，也和相鄰節(jié)點(diǎn)的屬性相關(guān)。

對(duì)于給定的無(wú)向無(wú)權(quán)網(wǎng)絡(luò)G=(V,E)，其中包含|V| =N個(gè)節(jié)點(diǎn)和|E| =M條邊。網(wǎng)絡(luò)G的鄰接矩陣A中的元素用aij表示，如果節(jié)點(diǎn)vi與節(jié)點(diǎn)vj之間有連邊，則aij=1，若節(jié)點(diǎn)vi與節(jié)點(diǎn)vj之間沒(méi)有連邊，則aij=0。IRA算法公式如下：

其中，IRA 值用來(lái)衡量每個(gè)節(jié)點(diǎn)的重要程度，IRAi(t)表示第t個(gè)時(shí)間步節(jié)點(diǎn)vi的IRA 值，Γ(i)表示節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)集，θi表示節(jié)點(diǎn)vi的一個(gè)具體的資源值，可以將K-shell、度中心性（degree centrality，DC）[12]、特征向量中心性（eigenvector centrality，EC）[13]、接近中心性（closeness centrality，CC）[14]等指標(biāo)作為輸入，α為可調(diào)節(jié)中心性值的權(quán)重。

IRA算法大致流程為：首先將所有節(jié)點(diǎn)的IRA 值都初始化為1，然后按照式（1）迭代更新IRA 值直至其穩(wěn)定，最后得到的資源值就代表了各節(jié)點(diǎn)的重要程度。

IRA算法融合了節(jié)點(diǎn)自身屬性和鄰居節(jié)點(diǎn)屬性，文獻(xiàn)[10]證明，相比其他算法，IRA算法在大部分網(wǎng)絡(luò)中準(zhǔn)確度都有不同程度的提升，并且得到了更加精確的排序結(jié)果。此外，在真實(shí)網(wǎng)絡(luò)中，隨著參數(shù)α的增大，IRA算法得出的準(zhǔn)確率先緩慢上升然后急劇下降，這意味著隨著參數(shù)α的增大，IRA算法得出的節(jié)點(diǎn)重要性程度排名的準(zhǔn)確性是逐漸下降的，因此后續(xù)文章默認(rèn)該值為1。

1.2 IIRA算法

IRA 算法同時(shí)考慮節(jié)點(diǎn)自身屬性和鄰居節(jié)點(diǎn)屬性的影響，提高了重要節(jié)點(diǎn)排序的準(zhǔn)確性，但I(xiàn)RA 算法在對(duì)葉子節(jié)點(diǎn)的重要性排序中往往表現(xiàn)較差。這是由于在資源分配的過(guò)程中，網(wǎng)絡(luò)的局域現(xiàn)象干擾了算法的準(zhǔn)確性，未考慮節(jié)點(diǎn)的傳播屬性可能會(huì)對(duì)資源分配的結(jié)果產(chǎn)生影響。因此，文獻(xiàn)[10]引入節(jié)點(diǎn)的傳播概率，提出了改進(jìn)的資源分配算法IIRA。在IIRA算法的資源分配過(guò)程中，節(jié)點(diǎn)獲得的資源值不僅與節(jié)點(diǎn)自身和鄰居節(jié)點(diǎn)的屬性信息有關(guān)，還受到傳播概率和鄰居節(jié)點(diǎn)數(shù)目的影響。

對(duì)于給定的無(wú)向無(wú)權(quán)網(wǎng)絡(luò)G=(V,E)，IIRA 算法公式如下：其中，IIRA 值用來(lái)衡量每個(gè)節(jié)點(diǎn)的重要程度，IIRAi(t)表示第t個(gè)時(shí)間步節(jié)點(diǎn)vi的IIRA 值。式（2）中除ψi外各符號(hào)與IRA算法中相同。ψi表示節(jié)點(diǎn)所受到的傳播屬性的影響，具體含義為：

其中，β為傳播概率；di為節(jié)點(diǎn)vi的度，定義為：

IIRA算法大致流程為：首先將所有節(jié)點(diǎn)的IIRA 值都初始化為1，然后按照式（2）迭代更新IIRA 值直至其穩(wěn)定，最后得到的資源值就代表了各節(jié)點(diǎn)的重要程度。改進(jìn)后的IIRA算法準(zhǔn)確性比IRA算法有了進(jìn)一步的提高。

2 基于節(jié)點(diǎn)相似度的SBRA算法

IRA算法體系可以應(yīng)用于許多中心性算法，并提高這些中心性算法的性能。但這樣會(huì)使得排序的結(jié)果很大程度上依賴于輸入的中心性指標(biāo)，只能有限地提升算法的準(zhǔn)確度，難以突破這些中心性指標(biāo)的局限。

在實(shí)際的社交網(wǎng)絡(luò)中，人們往往有著復(fù)雜的關(guān)系。從傳播學(xué)的角度來(lái)說(shuō)，消息在不同節(jié)點(diǎn)之間的傳播能力是不同的。例如在消息網(wǎng)絡(luò)中，消息往往更容易在有著相同興趣愛(ài)好的小圈子里快速傳播，換句話說(shuō)，它們更為相似。在社交網(wǎng)絡(luò)中，節(jié)點(diǎn)之間的相似程度也可以用來(lái)刻畫(huà)節(jié)點(diǎn)之間的消息傳播效率。傳統(tǒng)的中心性指標(biāo)是無(wú)法衡量這種相似程度的，也是不夠準(zhǔn)確的，因此提出一種新的指標(biāo)來(lái)替代原有的中心性指標(biāo)作為資源分配算法的輸入很有必要。正是基于上述原因提出SBRA算法，用節(jié)點(diǎn)之間的相似性指標(biāo)代替中心性作為IIRA算法的輸入，通過(guò)節(jié)點(diǎn)之間相似性的比例來(lái)分配資源，使得算法更適用于社交網(wǎng)絡(luò)。

2.1 算法思想

SBRA 算法的核心思想是計(jì)算節(jié)點(diǎn)之間的余弦相似度，并根據(jù)節(jié)點(diǎn)間的相似性指標(biāo)占比作為資源分配的依據(jù)，進(jìn)行迭代資源分配，最后穩(wěn)定后的資源值就是節(jié)點(diǎn)的重要程度。

2.2 算法描述

對(duì)于給定的無(wú)向無(wú)權(quán)網(wǎng)絡(luò)G=(V,E)，在迭代開(kāi)始前，將節(jié)點(diǎn)的資源值全部初始化為1，使用Node2vec[15]模型將網(wǎng)絡(luò)節(jié)點(diǎn)表示成向量形式，并根據(jù)向量的余弦相似度得出相似性矩陣M。相似性矩陣M中的元素mij的計(jì)算方法如下：

其中，mij為節(jié)點(diǎn)vi與節(jié)點(diǎn)vj的余弦相似度，vector(vi)表示節(jié)點(diǎn)vi的向量，‖ ‖vector(vi) 表示節(jié)點(diǎn)vi的向量模長(zhǎng)，余弦相似度的范圍為[-1,1]。在資源分配的過(guò)程中，要以相似度的占比來(lái)分配資源，其中的零值和負(fù)值的相似度是無(wú)法參與計(jì)算的，在實(shí)際的社交網(wǎng)絡(luò)中也是不合乎邏輯的。因此對(duì)相似度的值進(jìn)行修正，將余弦相似度的值整體加1 并乘上0.5，使節(jié)點(diǎn)的相似度修正到[0,1]的區(qū)間，得到修正后的相似性矩陣S，既便于計(jì)算，又符合通常的認(rèn)知。矩陣S中的元素sij為：

其中，sij為節(jié)點(diǎn)vi與節(jié)點(diǎn)vj修正后的余弦相似度。

初始化完成后，開(kāi)始資源迭代分配。在每輪的迭代過(guò)程中，每個(gè)節(jié)點(diǎn)的資源值更新為其所有相鄰節(jié)點(diǎn)為其分配的資源值總和，而資源分配的依據(jù)就是節(jié)點(diǎn)間的相似性指標(biāo)占比。用Ii(t)表示第t輪資源迭代節(jié)點(diǎn)vi的資源值，則每輪迭代節(jié)點(diǎn)vi獲得的資源可以表示為：

除sij外各符號(hào)與IRA算法體系一致。

可以進(jìn)一步寫(xiě)成矩陣形式：矩陣W中的元素wij為：

可以將資源矩陣W看作一個(gè)對(duì)角陣D左乘矩陣T得到的矩陣，式（8）則可以改寫(xiě)為：

其中對(duì)角陣D可表示為：

可知tij≥0 且∑itij=1，根據(jù)圓盤(pán)定理[16]，當(dāng)t趨于無(wú)窮時(shí)，Tt將收斂于一個(gè)常數(shù)矩陣，而矩陣左乘一個(gè)對(duì)角陣只會(huì)使其行乘上一個(gè)倍數(shù)，又由于矩陣D中的元素取值均在(0,1]區(qū)間，因此資源值的變化量會(huì)無(wú)限趨近于零值，也就是說(shuō)存在一個(gè)足夠小的ε，且ε ＞0，當(dāng)I(t)在t趨于無(wú)窮時(shí)收斂，滿足 |I(t)-I(t-1)|＜ε，經(jīng)過(guò)若干輪迭代后，資源值一定會(huì)達(dá)到穩(wěn)定狀態(tài)。

具體來(lái)看，SBRA算法的過(guò)程如下：

（1）計(jì)算出資源矩陣W并初始化資源值I(0)=(1,1,…,1)T。

（2）按I(t+1)=W·I(t)或I(t)=Wt·I(0)的方式更新第t輪迭代節(jié)點(diǎn)的資源值。

（3）重復(fù)步驟（2），直到所有節(jié)點(diǎn)的資源值穩(wěn)定，即滿足 |I(t)-I(t-1)|＜ε，令ε=10-6。

以圖1中的網(wǎng)絡(luò)a來(lái)詳細(xì)說(shuō)明SBRA算法。其中有5個(gè)節(jié)點(diǎn)和5條邊，在初始階段，將其資源值全部設(shè)為1，即I(0)=(1,1,…,1)T，經(jīng)過(guò)建?？梢缘玫焦?jié)點(diǎn)的向量表示，將修正的節(jié)點(diǎn)之間的余弦相似度作為資源分配的依據(jù)，假設(shè)傳播概率β為0.8，則資源分配矩陣W為：

圖1 具有5個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)示例Fig.1 Network examples with 5 nodes

因?yàn)镾BRA算法中對(duì)角陣的存在，節(jié)點(diǎn)資源值會(huì)隨著迭代不斷變少，所以將每輪迭代后的資源值總量重新等比放大到初始化時(shí)的資源總量。如圖2所示，可以看到經(jīng)過(guò)迭代，網(wǎng)絡(luò)a中的每個(gè)節(jié)點(diǎn)的資源變化值最終趨于0，表示資源值達(dá)到穩(wěn)定狀態(tài)。

圖2 SBRA算法下網(wǎng)絡(luò)a節(jié)點(diǎn)資源變化值Fig.2 Node resource change value in Network a with SBRA algorithm

在網(wǎng)絡(luò)a的基礎(chǔ)上得到網(wǎng)絡(luò)b、網(wǎng)絡(luò)c、網(wǎng)絡(luò)d。同樣設(shè)置修正的余弦相似度作為資源分配依據(jù)，并將資源迭代后的結(jié)果放縮到合適的區(qū)間，可以得出網(wǎng)絡(luò)節(jié)點(diǎn)最終的資源值。如表1所示，隨著節(jié)點(diǎn)2、3、4節(jié)點(diǎn)度的增大，節(jié)點(diǎn)1在網(wǎng)絡(luò)中的重要性比重逐漸減弱，這樣的結(jié)果也是符合通常認(rèn)知的。

表1 SBRA算法在圖1中網(wǎng)絡(luò)各節(jié)點(diǎn)迭代穩(wěn)定的資源值Table 1 Iterative stable resource value of each node of networks in Fig.1 with SBRA algorithm

3 基于節(jié)點(diǎn)相似度和高階流動(dòng)的L-SBRA算法

IIRA 算法在設(shè)計(jì)之初就存在一個(gè)假設(shè)，即只有直接相連的節(jié)點(diǎn)之間才會(huì)存在資源的傳遞。但無(wú)論網(wǎng)絡(luò)中的節(jié)點(diǎn)是否直接相連，其影響力的傳播都是存在的，只是影響力的傳播距離越遠(yuǎn)，對(duì)節(jié)點(diǎn)影響就越小。資源分配的過(guò)程也應(yīng)該考慮到非直接相連的節(jié)點(diǎn)的資源流動(dòng)情況。因此將LeaderRank 算法的背景節(jié)點(diǎn)思想引入SBRA算法，提出了L-SBRA算法。

3.1 算法思想

L-SBRA算法就是在SBRA算法的基礎(chǔ)上在網(wǎng)絡(luò)中加入一個(gè)背景節(jié)點(diǎn)。首先將背景節(jié)點(diǎn)和原網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)建立連邊，然后通過(guò)連邊關(guān)系將相鄰節(jié)點(diǎn)分配的資源值迭代更新到每個(gè)節(jié)點(diǎn)上，直到每個(gè)節(jié)點(diǎn)的資源值都達(dá)到穩(wěn)定狀態(tài)，再將背景節(jié)點(diǎn)的資源值按照輸入指標(biāo)的占比分配給原網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)，此時(shí)節(jié)點(diǎn)的資源值大小即可作為節(jié)點(diǎn)重要性排序的指標(biāo)。

3.2 算法描述

對(duì)于給定的無(wú)權(quán)無(wú)向網(wǎng)絡(luò)G=(V,E)，加入背景節(jié)點(diǎn)vb形成新的網(wǎng)絡(luò)Ge，網(wǎng)絡(luò)Ge的鄰接矩陣U中的元素用uij表示，若網(wǎng)絡(luò)Ge中的節(jié)點(diǎn)vi和vj有連邊則uij=1，反之若沒(méi)有連邊則uij=0。并將新的網(wǎng)絡(luò)除背景節(jié)點(diǎn)外的資源值全部初始化為1，背景節(jié)點(diǎn)的資源值初始化為0。若用Ie表示網(wǎng)絡(luò)Ge節(jié)點(diǎn)的資源值，則Ie=[1,1,…,1,0]T。

對(duì)于節(jié)點(diǎn)相似性來(lái)說(shuō)，在加入背景節(jié)點(diǎn)后，由于背景節(jié)點(diǎn)與原網(wǎng)絡(luò)中的所有節(jié)點(diǎn)都相連，在建模時(shí)從每個(gè)節(jié)點(diǎn)隨機(jī)游走到該節(jié)點(diǎn)的概率都很大，即背景節(jié)點(diǎn)和所有節(jié)點(diǎn)的相似度都很高，這就會(huì)導(dǎo)致在資源迭代時(shí)大量的資源流動(dòng)到背景節(jié)點(diǎn)。這樣的結(jié)果違背了設(shè)計(jì)算法的初衷，即希望只有少量的資源通過(guò)背景節(jié)點(diǎn)，用以表示資源在高階鄰居節(jié)點(diǎn)間的流動(dòng)。因此用原網(wǎng)絡(luò)G中所有節(jié)點(diǎn)對(duì)之間相似度的平均值sˉ作為背景節(jié)點(diǎn)與其余各節(jié)點(diǎn)的相似度?？傻孟嗨菩跃仃嘢′，其中矩陣中元素s′ij為：

初始化完成后，開(kāi)始進(jìn)行資源迭代。用Iei(t)表示第t輪迭代網(wǎng)絡(luò)Ge中的節(jié)點(diǎn)vi的資源值，那么每輪迭代網(wǎng)絡(luò)Ge的節(jié)點(diǎn)資源值可以表示為：

可以進(jìn)一步寫(xiě)成矩陣形式：

矩陣H中的元素hij為：

同樣可以證明，當(dāng)?shù)螖?shù)t足夠大時(shí)，節(jié)點(diǎn)的資源值會(huì)趨于穩(wěn)定。最后，將背景節(jié)點(diǎn)的資源值按照各節(jié)點(diǎn)與背景節(jié)點(diǎn)修正的余弦相似度比重分給原網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)，便可以計(jì)算出節(jié)點(diǎn)vi的最終資源值：

其中，sib指網(wǎng)絡(luò)Ge中節(jié)點(diǎn)vi與背景節(jié)點(diǎn)vb修正后的余弦相似度。

具體來(lái)看，L-SBRA算法的過(guò)程如下：

（1）網(wǎng)絡(luò)G中加入背景節(jié)點(diǎn)vb形成網(wǎng)絡(luò)Ge，計(jì)算出資源矩陣H并初始化資源值Ie=[1,1,…,1,0]T，其中背景節(jié)點(diǎn)的資源值為0。

（2）按Ie(t+1)=H·Ie(t)或Ie(t)=Ht·Ie(0)的方式更新第t輪迭代節(jié)點(diǎn)的資源值。

（3）重復(fù)步驟（2），直到所有節(jié)點(diǎn)的資源值穩(wěn)定，即滿足 |Ie(t)-Ie(t-1)|＜ε，令ε=10-6。

（4）將背景節(jié)點(diǎn)的資源值按照各節(jié)點(diǎn)與背景節(jié)點(diǎn)修正的余弦相似度比重分給其他節(jié)點(diǎn)，得到各節(jié)點(diǎn)的最終資源值Ii(t)。

同樣以圖1 中的網(wǎng)絡(luò)a 來(lái)詳細(xì)說(shuō)明L-SBRA 算法。在初始階段，加入背景節(jié)點(diǎn)并將資源值初始化Ie(0)=(1,1,…,1,0)T,假設(shè)傳播概率β為0.8，則資源分配矩陣H為：

因?yàn)楣?jié)點(diǎn)的資源值最終會(huì)收斂到一個(gè)穩(wěn)定的狀態(tài)，所以將每輪迭代后的資源值總量重新等比放大到初始化時(shí)的資源總量。如圖3 所示，可以看到經(jīng)過(guò)迭代，網(wǎng)絡(luò)a 中的每個(gè)節(jié)點(diǎn)的資源變化值最終趨于0，資源值達(dá)到穩(wěn)定狀態(tài)。

圖3 L-SBRA算法下網(wǎng)絡(luò)a節(jié)點(diǎn)資源變化值Fig.3 Node resource change value in Network a with L-SBRA algorithm

同樣對(duì)圖1的4個(gè)網(wǎng)絡(luò)設(shè)置修正的余弦相似度值作為算法的輸入，假設(shè)傳播概率β為0.8，并將資源迭代后的結(jié)果放縮到合適的區(qū)間，可以得出網(wǎng)絡(luò)節(jié)點(diǎn)最終的資源值。如表2所示，隨著網(wǎng)絡(luò)節(jié)點(diǎn)2、3、4連邊的增多，節(jié)點(diǎn)1 重要性不斷降低，而連邊變化后節(jié)點(diǎn)3、4、5 的重要性始終未超過(guò)節(jié)點(diǎn)1，在網(wǎng)絡(luò)b 中節(jié)點(diǎn)3 的連邊多于節(jié)點(diǎn)2和4，因此重要性高于節(jié)點(diǎn)2和4，與預(yù)期一致。

表2 L-SBRA算法在圖1中網(wǎng)絡(luò)各節(jié)點(diǎn)迭代穩(wěn)定的資源值Table 2 Iterative stable resource value of each node of networks in Fig.1 with L-SBRA algorithm

4 實(shí)驗(yàn)與分析

本文設(shè)計(jì)了對(duì)比實(shí)驗(yàn)來(lái)展示和分析IIRA、SBRA及L-SBRA算法的有效性和優(yōu)越性。

4.1 實(shí)驗(yàn)?zāi)Ｐ团c數(shù)據(jù)集

實(shí)驗(yàn)采用基于傳播動(dòng)力學(xué)的SIR模型[17]作為評(píng)價(jià)標(biāo)準(zhǔn)，以某一節(jié)點(diǎn)在一定時(shí)間感染的節(jié)點(diǎn)數(shù)來(lái)衡量該節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度。為了刻畫(huà)節(jié)點(diǎn)重要性排序算法的準(zhǔn)確度，采用不精確函數(shù)（Inaccu function）和Kendall系數(shù)[18]來(lái)表示排序結(jié)果和節(jié)點(diǎn)真實(shí)影響力之間的關(guān)系。

不精確函數(shù)是通過(guò)計(jì)算關(guān)鍵節(jié)點(diǎn)挖掘算法得出來(lái)的關(guān)鍵性排名里比較靠前的關(guān)鍵節(jié)點(diǎn)的平均傳播能力，進(jìn)而判定挖掘算法準(zhǔn)確性的函數(shù)，其計(jì)算方法為：

其中，εalg(p)表示通過(guò)重要性排序算法alg 得出的網(wǎng)絡(luò)中重要程度排前pN個(gè)節(jié)點(diǎn)的影響力與網(wǎng)絡(luò)中真實(shí)傳播能力排前pN個(gè)節(jié)點(diǎn)的影響力區(qū)別。Malg(p)表示算法得出的前pN個(gè)節(jié)點(diǎn)在一定的時(shí)間步感染的節(jié)點(diǎn)數(shù)，Meff(p)表示網(wǎng)絡(luò)中真實(shí)傳播能力排前pN個(gè)節(jié)點(diǎn)的在相同時(shí)間步感染的節(jié)點(diǎn)數(shù)。這里的p為選取網(wǎng)絡(luò)中節(jié)點(diǎn)的比例，0＜p ＜1,N為網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)。若Malg(p)與Meff(p)越接近，則不精確函數(shù)εalg(p)值越小，表示算法的結(jié)果精確度越高。

Kendall 系數(shù)τ可以用來(lái)表示兩個(gè)序列之間的相關(guān)程度，用這個(gè)指標(biāo)來(lái)評(píng)價(jià)重要性排序算法得到的結(jié)果與節(jié)點(diǎn)的真實(shí)影響力之間的相關(guān)性，其具體計(jì)算方法為：

其中，N為網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)，xi表示節(jié)點(diǎn)vi的真實(shí)影響力，即SIR模型模擬的影響力，yi表示排序算法計(jì)算出的節(jié)點(diǎn)vi影響力。sgn(x)為符號(hào)函數(shù)，當(dāng)x ＞0,時(shí)sgn(x)=1,當(dāng)x ＜0 時(shí)，sgn(x)=-1,當(dāng)x=0 時(shí)，sgn(x)=0。算法準(zhǔn)確性越高則τ值越大。

為了驗(yàn)證算法的有效性和優(yōu)越性，本文數(shù)據(jù)集采用了US Airline網(wǎng)絡(luò)、Email網(wǎng)絡(luò)和Hamster用戶網(wǎng)絡(luò)。三個(gè)網(wǎng)絡(luò)均為無(wú)權(quán)無(wú)向網(wǎng)絡(luò)，網(wǎng)絡(luò)的基本參數(shù)如表3 所示。其中N為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)，M為網(wǎng)絡(luò)邊數(shù)，＜k ＞為網(wǎng)絡(luò)平均度，r為網(wǎng)絡(luò)的同配系數(shù)，C為網(wǎng)絡(luò)的平均聚集系數(shù)。

表3 網(wǎng)絡(luò)數(shù)據(jù)集參數(shù)Table 3 Network dataset parameters

4.2 SBRA與IIRA對(duì)比實(shí)驗(yàn)

設(shè)置SIR模型的傳播率為0.2，恢復(fù)率為0.1，分別以DC、EC、CC、K-shell值作為IIRA算法的輸入，兩種算法中節(jié)點(diǎn)間的傳播概率β取0.8，使用Node2vec算法來(lái)對(duì)網(wǎng)絡(luò)結(jié)構(gòu)建模。經(jīng)過(guò)迭代可以得到兩個(gè)算法在各網(wǎng)絡(luò)中的不精確函數(shù)和Kendall 系數(shù)。

如圖4、圖5所示，在US Airline網(wǎng)絡(luò)中，SBRA算法表現(xiàn)和以DC、EC、CC中心性指標(biāo)為輸入的IIRA算法精確度相當(dāng)，明顯優(yōu)于以K-shell指標(biāo)為輸入的IIRA算法。

圖4 US Airline數(shù)據(jù)集不同輸入指標(biāo)的Kendall系數(shù)Fig.4 Kendall coefficients of different input indicators in US Airline dataset

圖5 US Airline數(shù)據(jù)集不同輸入指標(biāo)的不精確函數(shù)Fig.5 Inaccu function of different input indicators in US Airline dataset

如圖6、圖7所示，在Email網(wǎng)絡(luò)中，兩種算法的表現(xiàn)和在US Airline中相似，SBRA算法和以DC、EC、CC中心性指標(biāo)為輸入的IIRA 算法精確度相當(dāng)，顯著優(yōu)于以K-shell指標(biāo)為輸入的IIRA算法。

圖6 Email數(shù)據(jù)集不同輸入指標(biāo)的Kendall系數(shù)Fig.6 Kendall coefficients of different input indicators in Email dataset

圖7 Email數(shù)據(jù)集不同輸入指標(biāo)的不精確函數(shù)Fig.7 Inaccu function of different input indicators in Email dataset

在圖4 到圖7 中，無(wú)論是以哪種中心性指標(biāo)作為輸入，IIRA 算法和SBRA 算法在迭代100 次前的Kendall系數(shù)都可以趨于穩(wěn)定。在US Airline網(wǎng)絡(luò)和Email網(wǎng)絡(luò)中以DC、EC 和CC 中心性指標(biāo)作為輸入的IIRA 算法Kendall 系數(shù)和SBRA 算法穩(wěn)定后的Kendall 系數(shù)都十分接近，不精確函數(shù)也基本重合。兩種算法的Kendall系數(shù)接近說(shuō)明在這兩個(gè)網(wǎng)絡(luò)中，兩種算法的精確度基本一致，基本重合的不精確函數(shù)說(shuō)明導(dǎo)致出現(xiàn)結(jié)果差異的節(jié)點(diǎn)影響力十分接近，它們之間的影響力差別基本可以忽略不計(jì)。以K-shell值作為輸入的IIRA算法中，SBRA算法明顯結(jié)果更優(yōu)。出現(xiàn)這一現(xiàn)象的原因在于IIRA算法精度依賴于輸入的中心性指標(biāo)，而K-shell 值本身并不精確。

如圖8、圖9所示，在Hamster網(wǎng)絡(luò)中，SBRA算法在第25次迭代之后就已穩(wěn)定，其精確度均高于IIRA算法，明顯優(yōu)于以EC 中心性指標(biāo)和以K-shell 指標(biāo)為輸入的IIRA 算法。SBRA 算法和以DC 中心性指標(biāo)為輸入的IIRA 算法在影響力排前7%的節(jié)點(diǎn)精確度相當(dāng)，在超過(guò)7%節(jié)點(diǎn)后顯著優(yōu)于IIRA 算法，和以CC 中心性指標(biāo)為輸入的IIRA 算法在影響力排前14%的節(jié)點(diǎn)精確度相當(dāng)，在超過(guò)14%的節(jié)點(diǎn)以后明顯優(yōu)于IIRA 算法。可以看到，SBRA算法不僅收斂速度更快，而且精度更高、更穩(wěn)定。

圖8 Hamster數(shù)據(jù)集不同輸入指標(biāo)的Kendall系數(shù)Fig.8 Kendall coefficients of different input indicators in Hamster dataset

圖9 Hamster數(shù)據(jù)集不同輸入指標(biāo)的不精確函數(shù)Fig.9 Inaccu function of different input indicators in Hamster dataset

通過(guò)IIRA 算法和SBRA 算法的對(duì)比實(shí)驗(yàn)可以看出，在三個(gè)不同網(wǎng)絡(luò)中兩種算法的表現(xiàn)并不相同。IIRA算法的精度很大程度上受輸入的中心性指標(biāo)影響。如圖10、圖11所示，將SBRA算法迭代穩(wěn)定后的資源值作為IIRA算法的輸入重新迭代，算法的精度下降，可以說(shuō)明SBRA 算法已經(jīng)接近了IRA 算法體系的精度上限。兩種算法在Hamster網(wǎng)絡(luò)中SBRA的表現(xiàn)更好，已經(jīng)可以說(shuō)明以節(jié)點(diǎn)相似度作為輸入要比以中心性指標(biāo)作為輸入進(jìn)行資源迭代更加合理。在US Airline網(wǎng)絡(luò)和Email網(wǎng)絡(luò)中兩種算法精度相當(dāng)，是由于這兩個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)較少，中心性指標(biāo)的誤差不至于影響到節(jié)點(diǎn)的重要性排序情況，因此兩種算法都能準(zhǔn)確地識(shí)別到關(guān)鍵節(jié)點(diǎn)。

圖10 IIRA重新迭代SBRA穩(wěn)定后資源的三個(gè)網(wǎng)絡(luò)的Kendall系數(shù)Fig.10 Kendall coefficients of three networks when IIRA re-iterates resources after SBRA stabilization

圖11 IIRA重新迭代SBRA穩(wěn)定后資源的三個(gè)網(wǎng)絡(luò)的不精確函數(shù)Fig.11 Inaccu function of three networks when IIRA re-iterates resources after SBRA stabilization

通過(guò)對(duì)比實(shí)驗(yàn)可以得出，在節(jié)點(diǎn)數(shù)量較多的情況下SBRA 算法的精度要高于IIRA 算法。在時(shí)間方面，以CC 中心性指標(biāo)為輸入的IIRA 算法雖然有一定的精確度，但由于要計(jì)算CC中心性指標(biāo)，算法的復(fù)雜度隨著網(wǎng)絡(luò)規(guī)模的增大呈指數(shù)級(jí)上升，對(duì)于大型網(wǎng)絡(luò)來(lái)說(shuō)這樣的計(jì)算成本是不可接受的，相對(duì)而言SBRA算法計(jì)算復(fù)雜度要小得多。在算力成本不斷下降的今天，SBRA算法的復(fù)雜度仍然是可以承擔(dān)得起的。但這并不說(shuō)明在較少節(jié)點(diǎn)情況下SBRA 算法是沒(méi)有意義的。由于IIRA 算法有多種輸入，并不能確定用哪種輸入可以得到最準(zhǔn)確的排序結(jié)果。而SBRA 算法在小型網(wǎng)絡(luò)中雖然排序精度并不會(huì)提升，但其排序結(jié)果與IIRA 算法最精確的排序結(jié)果相當(dāng)，免去了選擇輸入指標(biāo)的麻煩。因此可以得出SBRA算法優(yōu)于IIRA算法的結(jié)論。

4.3 L-SBRA與SBRA對(duì)比實(shí)驗(yàn)

設(shè)置SIR模型的傳播率為0.2，恢復(fù)率為0.1，L-SBRA算法和SBRA 算法中節(jié)點(diǎn)間的傳播概率β取0.8，使用Node2vec 算法來(lái)對(duì)網(wǎng)絡(luò)結(jié)構(gòu)建模。經(jīng)過(guò)迭代可以得到兩種算法在各網(wǎng)絡(luò)之中的不精確函數(shù)和Kendall 系數(shù)，如圖12、圖13所示。

圖12 L-SBRA算法與SBRA算法在三個(gè)網(wǎng)絡(luò)中的Kendall系數(shù)Fig.12 Kendall coefficients of L-SBRA algorithm and SBRA algorithm in three networks

圖13 L-SBRA算法與SBRA算法在三個(gè)網(wǎng)絡(luò)中的不精確函數(shù)Fig.13 Inaccu functions of L-SBRA algorithm and SBRA algorithm in three networks

在三個(gè)網(wǎng)絡(luò)中，L-SBRA算法均在第25次迭代之前趨于穩(wěn)定，收斂速度均比SBRA 算法快，算法收斂速度加快是由于背景節(jié)點(diǎn)的出現(xiàn)使得網(wǎng)絡(luò)中的連邊數(shù)顯著增多，從而加快了資源流動(dòng)的速度。在US Airline網(wǎng)絡(luò)和Email 網(wǎng)絡(luò)中，SBRA 算法和L-SBRA 算法的精確度基本相當(dāng)。在Hamster 網(wǎng)絡(luò)中，在選取節(jié)點(diǎn)數(shù)量超過(guò)網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)的14%時(shí)，L-SBRA 算法精度也有一定的提高。結(jié)合算法在三個(gè)網(wǎng)絡(luò)中的表現(xiàn)同樣可以得出，算法可以同時(shí)提高收斂速度和準(zhǔn)確度。在US Airline 網(wǎng)絡(luò)和Email網(wǎng)絡(luò)上算法精度未提高，是因?yàn)檫@兩個(gè)網(wǎng)絡(luò)規(guī)模較小，算法的精度差，不足以影響節(jié)點(diǎn)的排序結(jié)果。

通過(guò)上述對(duì)比實(shí)驗(yàn)，可以發(fā)現(xiàn)在小型數(shù)據(jù)集上SBRA算法和L-SBRA 算法都能接近IRA 算法框架的精度上限，而L-SBRA 算法收斂速度更快；在大型數(shù)據(jù)集上，L-SBRA 算法收斂速度不僅更快，而且準(zhǔn)確率也更高。由此可以得出結(jié)論，L-SBRA算法要優(yōu)于SBRA算法。

5 結(jié)束語(yǔ)

本文分析了IIRA 算法的不足之處，對(duì)IIRA 算法進(jìn)行改進(jìn)，使用節(jié)點(diǎn)相似性指標(biāo)替換掉原算法中的中心性指標(biāo)作為算法的輸入，提出了SBRA算法。并且在SBRA算法的基礎(chǔ)上，引入了LeaderRank算法中背景節(jié)點(diǎn)的思想，提出了L-SBRA算法。這兩種改進(jìn)算法考慮了非直接相連節(jié)點(diǎn)間的傳播情況，更加符合社交網(wǎng)絡(luò)的實(shí)際情況，也更加合理。通過(guò)設(shè)置以四種中心性指標(biāo)為輸入的IIRA算法與SBRA算法的對(duì)比實(shí)驗(yàn)，展示了在三個(gè)真實(shí)網(wǎng)絡(luò)中兩種算法的表現(xiàn)，并分析出現(xiàn)結(jié)果差異的原因，證明了相似性作為算法輸入的合理性。設(shè)置L-SBRA算法和SBRA算法的對(duì)比實(shí)驗(yàn)，展示了在三個(gè)不同真實(shí)網(wǎng)絡(luò)中兩種算法的表現(xiàn)，并分析了兩種算法精度和收斂速度出現(xiàn)不同的原因，證明了L-SBRA算法的優(yōu)越性。

本文網(wǎng)絡(luò)建模部分使用了Node2vec 模型，而該模型產(chǎn)生隨機(jī)游走序列時(shí)只考慮了連接關(guān)系，而在實(shí)際的社交網(wǎng)絡(luò)中，節(jié)點(diǎn)的屬性信息也應(yīng)該對(duì)該隨機(jī)游走序列產(chǎn)生一定影響。另外，本文研究的對(duì)象為靜態(tài)無(wú)權(quán)無(wú)向網(wǎng)絡(luò)，而在真實(shí)的社交網(wǎng)絡(luò)中，還存在更為復(fù)雜的結(jié)構(gòu)，并且網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)也是變化的。因此在未來(lái)的研究中，可以考慮修改隨機(jī)游走序列的產(chǎn)生規(guī)則，讓生成的隨機(jī)游走序列包含節(jié)點(diǎn)的屬性信息，以及考慮到網(wǎng)絡(luò)結(jié)構(gòu)的動(dòng)態(tài)變化，使得算法更加適用于真實(shí)的社交網(wǎng)絡(luò)。