芶 欣,李欣悅,陳 武，劉佳謀

(1. 西南大學 計算機與信息科學學院，重慶 400715； 2. 奧克蘭大學 計算機科學學院，奧克蘭 1010)

0 引言

一個社會群體由許多在共享環(huán)境中進行交互的社會參與者組成[1]。群體的產(chǎn)生、群體成員相互合作、社會習俗形成等社會群體動態(tài)行為的研究一直是計算機科學和人工智能的一個重要課題。在這些研究中，社會群體的一個本質特征體現(xiàn)在群體成員間具有互動模式。一個人在社會群體中的決策是與他人的決策相關聯(lián)的[2]。社會影響在很大程度上是由社會互動模式引起的[3-4]。

本文遵循結構主義的傳統(tǒng)，將一個社會群體視為一個社會網(wǎng)絡，該網(wǎng)絡由代表社會群體成員的節(jié)點及節(jié)點間的相互聯(lián)系構成。通過網(wǎng)絡拓撲結構來分析社會影響，也就是節(jié)點的位置由它們的鏈路結構來決定。本文的動機來源于以下三個方面。

首先， 社會影響主要是作為個體特征來進行研究的?，F(xiàn)有大量的研究都集中于通過解決影響力最大化問題來尋找影響力最大的個體或者群體[5]。由于每個個體都想在自己所處的社會環(huán)境中發(fā)揮最大的影響力，因此，要了解所有群體成員同時做出決策時可能會產(chǎn)生什么樣的影響全局的模式就顯得非常重要。這種全局觀點自然需要引入博弈論的思想，而這個主題到目前為止并未產(chǎn)生較為深入的研究。

其次，迄今為止對社會網(wǎng)絡的研究集中在網(wǎng)絡“分解”上，也就是將網(wǎng)絡劃分成集群以構成所謂的社區(qū)結構。然而，很少有關于“一體化”問題的研究，比如社會凝聚力等問題。社會凝聚力表示一個社會群體中的成員愿意保持團結的意愿，其對于群體中的合作以及習俗形成的研究有著廣泛影響[5]。對此，一個問題將會自然而然地被提出，即什么樣的網(wǎng)絡拓撲結構會影響社會凝聚力？這個問題的答案可以作為增強社會群體凝聚力的基礎。

最后，雖然許多關于社會網(wǎng)絡的博弈論分析都集中在研究均衡或者最優(yōu)結果上，但大多沒有考慮到其對社會網(wǎng)絡結構進行調整的干預機制。對網(wǎng)絡拓撲結構的局部調整可能導致所有社會參與者的系列變化。因此，在對社會凝聚力等全局特性問題進行研究時，理解博弈論概念和網(wǎng)絡結構的動態(tài)變化之間的關系是至關重要的[3]。

本文從以上三個視角考慮，并基于聯(lián)盟結構形成的研究，探討了增強一個社會群體凝聚力的策略。首先，本文研究了一個基于合作博弈的社會群體動態(tài)行為模型。參與者可以選擇組成聯(lián)盟(子群體)，并根據(jù)其所在的聯(lián)盟獲得相應的獎勵。對個體的獎勵被定義為個體在聯(lián)盟中產(chǎn)生的局部影響力。其次，本文提出了影響力博弈模型，該模型將社會凝聚力定義為所有參與者選擇留在同一聯(lián)盟并達到均衡，并重點討論了維持網(wǎng)絡拓撲結構的條件，以保證達到這樣的均衡狀態(tài)。最后，本文探索潛在的干預機制，通過為社會網(wǎng)絡增加新的鏈接，以改變其網(wǎng)絡拓撲結構，使其社會凝聚力得到增強。本文提出了基于核心邊緣的策略，并通過實驗驗證了其有效性。

1 相關工作

目前有許多對凝聚力進行研究的工作[6-8]。Beal等人通過元分析方法對群體凝聚力進行了研究[7]。Purohit等人通過一組靜態(tài)的朋友/追隨者網(wǎng)絡結構特征來描述社會凝聚力[8]。然而，這些研究中很少有研究如何形成社會凝聚力。本文將使用合作博弈模型來研究如何形成一個穩(wěn)定的、具有凝聚力的社會網(wǎng)絡。在博弈論中，有許多關于如何分組使一個網(wǎng)絡達到均衡的研究。Gharehshiran等人利用合作博弈理論設計了一個分布式動態(tài)聯(lián)盟形成算法，其中節(jié)點自主決定加入哪個聯(lián)盟，使其可行睡眠時間最大化[9]。Massin等人提出使用合作博弈的方法，在ad-hoc網(wǎng)絡中形成穩(wěn)定的聯(lián)盟，以保證網(wǎng)絡中的信息可以穩(wěn)定的傳輸[10]。Apt等人提出了用一種抽象的方法，基于簡單的合并和分割規(guī)則轉換一組節(jié)點的分區(qū)，以形成穩(wěn)定的聯(lián)盟[11]。這些研究都使用博弈論的方法，致力于將網(wǎng)絡分割成不同的聯(lián)盟來達到均衡。本文基于聯(lián)盟穩(wěn)定性的研究，考慮通過局部修改網(wǎng)絡結構來達到整體的均衡。

2 基本概念

將一個社會網(wǎng)絡看作一個無權、無向圖G=(V,E)，其中，V是所有節(jié)點的集合，E為所有無向邊的集合。G中每一個節(jié)點v∈V都代表了社會網(wǎng)絡中的一個個體。對于任意一條邊{u,v}∈E，{u,v}表示節(jié)點u和v之間存在社會聯(lián)系，簡寫為uv。對于G′?G，S為G′的節(jié)點集，對任意節(jié)點u∈S，u與S中其他節(jié)點的連邊數(shù)是u在G′的度，記作degS(u)=|{v∈S|{u,v}∈E}|。

合作博弈可以用一個二元組CG=(U，f)表示，其中，U表示參與者(player)集合，f表示收益函數(shù)。在合作博弈中聯(lián)盟結構的形成是以個人收益為基礎的,通常認為個人(節(jié)點)收益會影響聯(lián)盟的收益。因此，下面將對個人(單個節(jié)點)收益進行定義。

定義1在一個聯(lián)盟C中，任意一個節(jié)點u在該聯(lián)盟中獲得的收益，表示為fC(u)。若u∈C，且C∈SC，那么節(jié)點u在聯(lián)盟結構SC中的收益可表示為FSC(u)，且fC(u)=FSC(u)。

在一個網(wǎng)絡中，一個穩(wěn)定聯(lián)盟結構的形成過程就是節(jié)點不斷選擇聯(lián)盟加入的過程。一個穩(wěn)定的聯(lián)盟結構的形成，需要網(wǎng)絡中每一個節(jié)點都不再改變它們選擇加入的聯(lián)盟。假設每一個節(jié)點都是自私的，那它們會希望獲得更高的收益，因此會選擇能獲得更多收益的聯(lián)盟加入。當一個聯(lián)盟中所有節(jié)點所獲得的收益都不低于他們加入其他聯(lián)盟所獲得的收益時，該聯(lián)盟就不容易因為節(jié)點的離開而遭到破壞，從而形成一個穩(wěn)定的聯(lián)盟結構。

若存在一個聯(lián)盟S?SC，且S中的每一個節(jié)點在該聯(lián)盟中所獲得的收益都高于它們在在聯(lián)盟結構SC中所獲得的收益，那么其就有可能離開原來的聯(lián)盟，共同形成一個比原來的聯(lián)盟更穩(wěn)定的新聯(lián)盟S，從而使得原來的聯(lián)盟結構SC被破壞。反之，若沒有這樣的S存在，那么原來的SC則可以得以保留[12]。

定義2在圖G=(V,E)中，對于一個聯(lián)盟結構SC，如果存在一個聯(lián)盟S?V，S?SC，對?u∈S，有fS(u)>FSC(u)，那么就說S可以阻塞SC。

本文用阻塞來衡量當前網(wǎng)絡中的聯(lián)盟結構是否穩(wěn)定。

定義3在圖G中，如果沒有聯(lián)盟S?SC可以阻塞SC，那么就說該聯(lián)盟結構SC是核心穩(wěn)定的。如果大聯(lián)盟是核心穩(wěn)定的，那么說G是具有凝聚力的。

在社會網(wǎng)絡的研究中，節(jié)點的度往往是衡量節(jié)點影響力大小的重要因素[13-15]。社會網(wǎng)絡中兩個節(jié)點之間的連邊表示它們之間存在的社會關系。一個節(jié)點如果有較多的鄰居節(jié)點則表示其被認可的程度較高。反過來也反映出其對所在聯(lián)盟有較強的影響力。

眾所周知，社會網(wǎng)絡中任何個體都希望自己得到的支持和信任比較高，這樣才能在聯(lián)盟中得到更多成員的信任并影響他們，從而提高自己在聯(lián)盟中的影響力。而在一個社會網(wǎng)絡中，當一個個體的影響力有所提升的時候，影響力將會給它帶來更多的隱形的或直接的收益(如金錢、信譽、社會支持等等)，往往這樣的收益都會通過經(jīng)濟效益得以體現(xiàn)。本文使用獎勵rC(u) 來衡量節(jié)點u在當前聯(lián)盟C中的影響力所帶來的收益。同時，當一個節(jié)點加入一個聯(lián)盟時需要支付一定的費用，用tC(u) 來表示。一個節(jié)點最終所獲得的收益(也稱為局部影響力)與其影響力所帶來的獎勵以及加入聯(lián)盟時的花費都有關。節(jié)點的局部影響力定義如下：

定義4在聯(lián)盟C中的一個節(jié)點u，它的局部影響力如式(1)所示。

fC(u)=rC(u)-tC(u)

(1)

?獎勵rC(u)： 用于衡量節(jié)點u在聯(lián)盟C中的影響力給其帶來的收益。當一個聯(lián)盟的大多數(shù)成員都與節(jié)點u有連邊時，u在當前聯(lián)盟C中的影響力是相對較高的。然而，再增加一些新鄰居節(jié)點，它影響力的提升沒有最開始那么明顯。因此，本文對rC(u)進行了定義，如式(2)所示。

rC(u)=logdegC(u)

(2)

?花費tC(u)： 用于描述節(jié)點u加入聯(lián)盟C所需支付的費用，這筆費用與聯(lián)盟中節(jié)點的數(shù)量有關。如式(3)所示。

tC(u)=log |C|

(3)

定義5在圖G上的影響力博弈是一個合作博弈，表示為Γ(G)=(V,θ)。其中，V表示所有參與者(節(jié)點)集合，θ：V×2V是收益函數(shù)，表示節(jié)點u的局部影響力，有θ(u,C)=fC(u)。

如果一個社會網(wǎng)絡G在影響力博弈上是有凝聚力的，那么就說G具有社會凝聚力。

在一個社會網(wǎng)絡中，總希望所有的節(jié)點可以自愿加入到大聯(lián)盟中，從而使得整個網(wǎng)絡具有社會凝聚力。為此，本文采用合作博弈模型來研究如何實現(xiàn)具有社會凝聚力的網(wǎng)絡結構問題(achieve social cohesion structure，ASCS)。

3 方法

社會凝聚力的形成往往是基于社會群體中個體之間的合作。合作可以使個人的資源和技術被整合在一起，從而更快、更好地達到預期目標[12]。許多研究表明，相似的個體間更容易形成信任并緊密相連，以便整個社會團體可以更好地發(fā)展[16-17]。網(wǎng)絡拓撲結構是影響網(wǎng)絡社會凝聚力的重要因素。本文基于合作博弈模型，考慮利用潛在的干預機制，通過改變社會網(wǎng)絡的拓撲邏輯結構，增強網(wǎng)絡社會凝聚力。

在社會網(wǎng)絡中，部分節(jié)點緊密相連，形成一個小群體，其中的任意兩個節(jié)點之間都有邊，所有的節(jié)點在該小群體中都有相同的影響力。在網(wǎng)絡中，這樣的群體不容易被外力分開，是相對穩(wěn)定的。這樣的群體在圖論中稱作“團”。

定義6一個完全子圖c?G是圖G的一個團。團c中所包含的節(jié)點數(shù)是團的大小，G中大小最大的團稱作最大團，記作mc。

團是網(wǎng)絡中常見的子群體。它們的存在有助于探討網(wǎng)絡結構對網(wǎng)絡的社會凝聚力的影響。那么，什么樣的網(wǎng)絡結構才能促進社會網(wǎng)絡的社會凝聚力形成?這是本文將要研究的一個內容。

核心/邊緣(core-periphery，CP)結構是一種非常重要的網(wǎng)絡結構，它能很好地描述網(wǎng)絡中節(jié)點間的競爭與合作關系[18]。Borgatti和Everett指出，CP網(wǎng)絡結構具有緊密連接的核心部分以及與核心緊密連接但內部連接稀疏的邊緣部分[18-19]。前人研究指出，網(wǎng)絡的核心可以促進整個網(wǎng)絡的穩(wěn)定，幫助整個網(wǎng)絡適應環(huán)境的波動。網(wǎng)絡中核心節(jié)點之間的緊密連接可以使它們相互支持，在緊急情況下可以相互替換，以保證網(wǎng)絡的性能[18，20]。這種結構特點與本文所希望得到的具有較強穩(wěn)定性的網(wǎng)絡結構不謀而合。

定義7一個標準CP結構的網(wǎng)絡G=(V,E)可以把其分為核心C(C≠?)和邊緣P(P≠?)兩個部分。其中C={v|?u，v∈V且u≠v，vu∈E}，P={u|?u,m?C且u≠m,um?E}

在一個標準CP結構的網(wǎng)絡中，C部分的節(jié)點和網(wǎng)絡中所有節(jié)點都有直接相連的邊，P部分節(jié)點之間沒有直接相連的邊[19]，如圖1所示，C={1,2,3,4}，P={5,6,7,8,9,10}。

圖1 標準CP結構

在社會網(wǎng)絡中，一些節(jié)點通常有相對多的鄰居節(jié)點，這樣的節(jié)點對網(wǎng)絡的影響更大。這些節(jié)點的存在有利于將其他影響力較小的節(jié)點組合在一起，有利于網(wǎng)絡的社會凝聚力的形成。我們發(fā)現(xiàn)核心/邊緣結構的特征與社會網(wǎng)絡中的上述特征具有相似性。因此，本文基于CP結構進行了一系列的研究。

定理1一個網(wǎng)絡G=(V,E)，如果G是標準CP結構，那么G是具有社會凝聚力的。

證明： 若證明標準CP網(wǎng)絡具有社會凝聚力，那么需證明在影響力博弈中不存在聯(lián)盟S?GC使得?u∈S，有fS(u)>FGC(u)，如式(4)所示。

(4)

因為這是一個單調遞增的函數(shù)，所以這等價于證明不存在聯(lián)盟S?GC使得?u∈S，有：

(5)

假設在一個標準CP結構的圖G=(V,E)中，C部分節(jié)點數(shù)為m，P部分節(jié)點數(shù)為n。該圖的聯(lián)盟可以有以下三種情況： 聯(lián)盟中所有的節(jié)點都屬于C；聯(lián)盟中所有的節(jié)點都屬于P；聯(lián)盟中一些節(jié)點屬于C，另一些屬于P，聯(lián)盟仍是CP結構。在該圖的大聯(lián)盟GC中，對于 ?v∈C都有收益，如式(6)所示。

(6)

對于?u∈P都有收益，如式(7)所示。

(7)

假設聯(lián)盟S?V中所有的節(jié)點都屬于P，即，?u∈S且 ?u∈P。那么，S中的任意節(jié)點u都有fS(u)=0，則fS(u)

假設聯(lián)盟S中包含m1個C部分的節(jié)點，n1個P部分的節(jié)點，且S?GC。那么，對于?v∈S且v∈C，有：

(8)

在這種情況下，任意S均不可以阻塞大聯(lián)盟GC。同時，證明了一個聯(lián)盟S?V如果包含了C部分的節(jié)點，那么該聯(lián)盟S一定不可以阻塞大聯(lián)盟GC。

因此，可以證明任意聯(lián)盟S都不可以阻塞大聯(lián)盟GC。所以，任意一個標準CP圖G是具有社會凝聚力的。

在許多情況下，一個網(wǎng)絡很難達到標準CP結構，因為在邊緣節(jié)點之間仍然存在一些連邊。若一個網(wǎng)絡G是基于標準CP結構的，且邊緣節(jié)點之間仍有部分連邊，那么我們將這樣的網(wǎng)絡稱作近似標準CP的網(wǎng)絡，簡寫為ACP。

定義8一個網(wǎng)絡G=(V,E)是近似標準CP的網(wǎng)絡，其分為核心C(C≠?)和邊緣P(P≠?)，其中，C={v|?u,v∈V且u≠v,vu∈E}，P={u|u?C，?m?C且um∈E}，簡寫為ACP。

那么，在ACP結構的網(wǎng)絡中C部分與P部分都要滿足哪些條件才能使得網(wǎng)絡G是具有社會凝聚力的網(wǎng)絡結構？

在網(wǎng)絡G中，節(jié)點u和節(jié)點v之間的最短路徑記作dist(u,v)，節(jié)點u與其他節(jié)點之間的最大的最短路徑為節(jié)點u的離心率，記作ec(u)=maxv∈Vdist(u,v)。若G中所有節(jié)點的離心率ec(u)不全相等，這樣的網(wǎng)絡稱為non-diametrically uniform，記作NDU。若一個NDU網(wǎng)絡G中所有節(jié)點的離心率ec(u)最大為2，則這個網(wǎng)絡稱作NDU2。LIU和WEI在文獻[16]中研究了在圖G=(V,E)上的合作博弈F(G)=(V,ρ)(popularity games)，其收益函數(shù)如式(9)所示。

(9)

同時，他們發(fā)現(xiàn)在popularity games中，網(wǎng)絡G∈NDU2若滿足定理2，則G具有凝聚力。

定理2在NDU2網(wǎng)絡G中|V2|>c(c-1)，若|V1|≥(c-1)(|V2|-c)，那么G是具有凝聚力的。

其中，V1是與其他所有節(jié)點都有連邊的節(jié)點集合，V2是除了V1以外的節(jié)點集合。c是V2所構成的子圖中最大團的大小。

由此，在ACP圖中可得到如下定理。

定理3在ACP圖G=(V,E)中，mp為由邊緣節(jié)點集P所構成的子圖Gp的最大團。當且僅當|C|≥(|mp|-1)×(|P|-|mp|)且|P|>|mp|×(|mp|-1) 時，G具有社會凝聚力。

證明： 已知在ACP網(wǎng)絡G中，C部分的節(jié)點與所有節(jié)點都有連邊。

?u1∈C，u2∈V且u2≠u1，有dist(u1,u2)=1。因此，?u∈C，都有ec(u)=1。

易得，?v1∈P，u∈C，有v1u=1；而?v2∈P(v1≠v2)，dist(v1,v2)≤2,且?v3，v4∈P有dist(v4,v3)=2。因此，?v∈P，有ec(v)≤2。

由此可得，ACP?NDU2。

基于此，若證明網(wǎng)絡G在影響力博弈中具有社會凝聚力。則需證明不存在S?GC，使得?u∈S，fS(u)>FGC(u)，如式(10)所示。

(10)

本文通過增加節(jié)點間的鏈接使所有的節(jié)點都愿意加入到大聯(lián)盟中，從而使得一個網(wǎng)絡具有社會凝聚力。在一個社會網(wǎng)絡中，有部分節(jié)點是非常重要的，它們的存在可以促進一個網(wǎng)絡社會凝聚力的形成。因此，本文提出了核心邊緣算法，考慮將一個網(wǎng)絡分為兩層，分別是核心層與邊緣層。其中核心部分由比較重要的節(jié)點組成，其他節(jié)點則構成了邊緣層。通過增加核心部分節(jié)點與邊緣部分節(jié)點之間的鏈接使得網(wǎng)絡最終具有社會凝聚力。核心邊緣算法的具體流程如圖2所示。

圖2 核心邊緣算法流程

核心部分節(jié)點的選擇是該算法的一個重點。網(wǎng)絡中有一些節(jié)點可以成為鏈接整個網(wǎng)絡的核心節(jié)點。在復雜網(wǎng)絡的研究中，度是衡量網(wǎng)絡節(jié)點中心度的重要指標。一般認為網(wǎng)絡中節(jié)點的度越大，節(jié)點的重要性就越大[21]。然而，如果僅僅是用節(jié)點的度來對核心部分節(jié)點進行選擇，那將忽略網(wǎng)絡中個體與群體之間的關系，而個體與群體的關系是社會凝聚力形成中不可忽視的因素。往往一個具有凝聚力的群體可以帶動更多的節(jié)點加入，從而使得整個網(wǎng)絡具有凝聚力。本文從原始網(wǎng)絡本身出發(fā)，考慮到任何一個網(wǎng)絡原本必定存在一些群體，是由聯(lián)系緊密的節(jié)點組成的，而群體之間的聯(lián)系也是核心節(jié)點選擇的考慮因素。本文結合這些測量指標和網(wǎng)絡本身的特點，根據(jù)每次所選擇節(jié)點數(shù)量的不同提出了兩種尋找網(wǎng)絡中核心節(jié)點的方法。在此基礎上，提出了兩種不同的算法來形成具有社會凝聚力的結構。

3.1 基于最大團的核心邊緣算法(CPMC)

在網(wǎng)絡中，往往希望核心部分節(jié)點之間是具有緊密連接的，若能找到原本連接就非常緊密的群體，那么是否就可以將這個本身連接緊密的群體作為核心層呢？然而一次性確定所有核心部分節(jié)點是非常困難的，因此本文考慮從連接緊密的最大團出發(fā)。團是完全子圖，完全圖是核心穩(wěn)定的網(wǎng)絡結構[16]。一個團是一個緊密相連的群體，最大團包含了更多能保持穩(wěn)定的節(jié)點，若將最大團加入核心部分，那么既能保證核心部分的穩(wěn)定性，也能盡快選擇出核心部分節(jié)點。為此，本文首先提出了基于最大團的核心邊緣算法(CPMC)來形成穩(wěn)定的大聯(lián)盟，從而使網(wǎng)絡具有社會凝聚力。該算法使用迭代的方式，每一輪從邊緣部分節(jié)點中選擇出一個最大團加入到核心C部分，邊緣P部分所構成的子圖中最大團的所有節(jié)點同時添加到核心部分，然后增加核心部分(C部分)節(jié)點與邊緣部分(P部分)節(jié)點之間的鏈接，并判斷是否形成具有社會凝聚力的網(wǎng)絡，若沒有則重復以上步驟繼續(xù)進行核心節(jié)點的選擇，直到網(wǎng)絡最終形成具有社會凝聚力的網(wǎng)絡。該算法的詳細介紹在算法一中給出。

算法一 基于最大團的核心邊緣算法

CPMC算法可以快速得到一個明顯的、穩(wěn)定性較好的網(wǎng)絡核心，因為它考慮了群體的特性。這種方法的缺點是可能導致在選擇核心節(jié)點時沒有考慮個體，為了更準確地選擇核心部分的節(jié)點，應該將群體和個體的特性都加以考慮。對此，本文提出了CPIN算法。

3.2 基于重要節(jié)點的核心邊緣算法(CPIN)

雖然最大團是一個非常穩(wěn)定的群體，但對于整個社會網(wǎng)絡而言并不是最大團中的所有節(jié)點都是核心的。為此，本文提出了另一種基于重要節(jié)點的核心邊緣算法以促進社會網(wǎng)絡中社會凝聚力形成。

在一個社會網(wǎng)絡中，往往會存在多個最大團，有的節(jié)點可能屬于多個最大團，這樣的節(jié)點往往可以成為鏈接各個小群體的橋梁，也更有可能將整個網(wǎng)絡緊密聯(lián)系起來，使得網(wǎng)絡具有社會凝聚力。本文將屬于最多個最大團的節(jié)點稱作重要節(jié)點。該算法同樣使用迭代的方式，每一輪選擇一個度最大的重要節(jié)點，將其加入到網(wǎng)絡的核心部分，然后增加該節(jié)點與其他邊緣部分節(jié)點的鏈接，每一輪結束時都要進行社會凝聚力的判斷，如果沒有形成社會凝聚力，那么將進行下一輪的重要節(jié)點的選擇，直到最終形成具有社會凝聚力的網(wǎng)絡。對于圖3中的網(wǎng)絡，可以很容易看出這個圖的最大團的大小是4，其中包括了3個最大團，它們分別是{1,2,3,4}，{1,9,6,5}，{1,9,8,7}，可以看出節(jié)點1屬于3個最大團，是屬于最大團數(shù)目最多的節(jié)點。因此，考慮將節(jié)點1作為一個重要節(jié)點，并將它加入到核心部分。

圖3 重要節(jié)點選擇示例

在算法二中對該算法進行了詳細的介紹。

算法二 基于重要節(jié)點的核心邊緣算法

3.3 CPMC與CPIN區(qū)別

CPMC與CPIN均是基于核心邊緣結構所提出的，但是選擇核心節(jié)點的側重點有所不同。具體來說，CMPC考慮到更快形成一個穩(wěn)定的核心部分，從群體的核心穩(wěn)定性出發(fā)，每次將核心穩(wěn)定性較好的整個最大團的節(jié)點全部加入核心部分。而CPIN則是綜合考慮群體和個體的關系，每次選擇一個屬于最多個最大團的節(jié)點加入核心部分。

4 實驗和結果

為了驗證算法的有效性，本文進行了一系列對比實驗。降低由于新增鏈接所帶來的成本是本文的一個目標。本文將使用隨機算法(random)和介數(shù)中心性(betweenness centrality，BC)算法，與本文所提出的算法進行比較。在本文的仿真實驗中，主要在無標度網(wǎng)絡(BA)、富人俱樂部網(wǎng)絡(rich-club,RC)兩種合成圖和6種現(xiàn)實網(wǎng)絡中進行。使用四種算法在相同的網(wǎng)絡中進行仿真實驗，然后對比他們在相同網(wǎng)絡中達到社會凝聚力所需要的花費(即，增加連接的數(shù)量)。

4.1 實驗設置

本節(jié)將介紹本文在實驗中所使用的現(xiàn)實數(shù)據(jù)集及合成圖數(shù)據(jù)集。

為了驗證所提出的算法的性能，本文在部分現(xiàn)實網(wǎng)絡中進行了相關的比較實驗，分別是： Football(FB)[23]、Jazz(JA)[24]、Prisons(PR)[25]、Dolphins(DO)[26]、Karate(KA)[26]和Italian Gangs(IG)。這些現(xiàn)實網(wǎng)絡更有利于驗證本文所提出方法的有效性。表1對現(xiàn)實網(wǎng)絡數(shù)據(jù)集進行了詳細介紹。

表1 現(xiàn)實網(wǎng)絡數(shù)據(jù)集

4.2 實驗結果

圖4、圖5分別展示了在富人俱樂部網(wǎng)絡RC、BA網(wǎng)絡中CPMC、CPIN、BC以及Random四種算法實現(xiàn)形成具有社會凝聚力的網(wǎng)絡所需要的花費。其中，橫坐標是合成網(wǎng)絡中所使用網(wǎng)絡的節(jié)點數(shù)目，縱坐標則表示形成具有社會凝聚力的網(wǎng)絡所需的代價。圖4是在Rich-Club合成圖中進行實驗的結果，可以看出本文所提出的CPIN算法具有較明顯的優(yōu)勢，而CPMC與BC算法相比雖然有一定優(yōu)勢，但并不明顯，同時也可以看出Random算法是所需花費最多的。圖5是在BA合成網(wǎng)絡中的實驗結果，從結果可以看出它不僅有在RC中的實驗結果的特點，同時也可以發(fā)現(xiàn)隨著原始網(wǎng)絡越來越密集，本文所提出的兩種算法和BC算法所需的花費比較接近。

圖4 RC網(wǎng)絡中不同算法實現(xiàn)社會凝聚力所需花費

圖5 BA網(wǎng)絡中不同算法實現(xiàn)社會凝聚力所需的花費(增加鏈接數(shù))

表2是在6個現(xiàn)實網(wǎng)絡中進行實驗的結果，從中可以看出CPMC與BC算法使得網(wǎng)絡具有社會凝聚力所需的代價比較接近，而本文所提出的CPIN算法可以使用最小的代價使得網(wǎng)絡具有社會凝聚力。

表2 在現(xiàn)實網(wǎng)絡中不同算法實現(xiàn)社會凝聚力所需的花費(增加鏈接數(shù))

續(xù)表

從以上分析可以看出，本文所提出的CPIN算法可以使網(wǎng)絡在盡可能低的成本下實現(xiàn)社會凝聚力。同時，也可以看出CPIN算法能更準確地選擇核心部分節(jié)點，有助于在社會凝聚力形成過程中降低花費。

5 總結和展望

本文提出使用一個合作博弈的模型從網(wǎng)絡結構的角度來研究如何形成社會凝聚力。從理論上證明了標準的CP結構和滿足一定條件的ACP結構是具有社會凝聚力的網(wǎng)絡結構。這為研究如何實現(xiàn)社會凝聚力網(wǎng)絡提供了重要依據(jù)。本文通過潛在的干預方法，提出了核心邊緣的算法。通過增加網(wǎng)絡中節(jié)點之間的聯(lián)系，使網(wǎng)絡具有社會凝聚力。實驗驗證了算法的有效性。下一步將探索具有社會凝聚力的更常見的網(wǎng)絡結構，以及使用其他成本更低的方法來促進社會凝聚力的形成。