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

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

0 引言

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

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

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

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

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

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

1 相關(guān)工作

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

2 基本概念

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

rC(u)=logdegC(u)

(2)

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

tC(u)=log |C|

(3)

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

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

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

3 方法

社會(huì)凝聚力的形成往往是基于社會(huì)群體中個(gè)體之間的合作。合作可以使個(gè)人的資源和技術(shù)被整合在一起，從而更快、更好地達(dá)到預(yù)期目標(biāo)[12]。許多研究表明，相似的個(gè)體間更容易形成信任并緊密相連，以便整個(gè)社會(huì)團(tuán)體可以更好地發(fā)展[16-17]。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是影響網(wǎng)絡(luò)社會(huì)凝聚力的重要因素。本文基于合作博弈模型，考慮利用潛在的干預(yù)機(jī)制，通過改變社會(huì)網(wǎng)絡(luò)的拓?fù)溥壿嫿Y(jié)構(gòu)，增強(qiáng)網(wǎng)絡(luò)社會(huì)凝聚力。

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

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

團(tuán)是網(wǎng)絡(luò)中常見的子群體。它們的存在有助于探討網(wǎng)絡(luò)結(jié)構(gòu)對(duì)網(wǎng)絡(luò)的社會(huì)凝聚力的影響。那么，什么樣的網(wǎng)絡(luò)結(jié)構(gòu)才能促進(jìn)社會(huì)網(wǎng)絡(luò)的社會(huì)凝聚力形成?這是本文將要研究的一個(gè)內(nèi)容。

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

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

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

圖1 標(biāo)準(zhǔn)CP結(jié)構(gòu)

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

定理1一個(gè)網(wǎng)絡(luò)G=(V,E)，如果G是標(biāo)準(zhǔn)CP結(jié)構(gòu)，那么G是具有社會(huì)凝聚力的。

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

(4)

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

(5)

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

(6)

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

(7)

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

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

(8)

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

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

在許多情況下，一個(gè)網(wǎng)絡(luò)很難達(dá)到標(biāo)準(zhǔn)CP結(jié)構(gòu)，因?yàn)樵谶吘壒?jié)點(diǎn)之間仍然存在一些連邊。若一個(gè)網(wǎng)絡(luò)G是基于標(biāo)準(zhǔn)CP結(jié)構(gòu)的，且邊緣節(jié)點(diǎn)之間仍有部分連邊，那么我們將這樣的網(wǎng)絡(luò)稱作近似標(biāo)準(zhǔn)CP的網(wǎng)絡(luò)，簡寫為ACP。

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

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

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

(9)

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

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

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

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

定理3在ACP圖G=(V,E)中，mp為由邊緣節(jié)點(diǎn)集P所構(gòu)成的子圖Gp的最大團(tuán)。當(dāng)且僅當(dāng)|C|≥(|mp|-1)×(|P|-|mp|)且|P|>|mp|×(|mp|-1) 時(shí)，G具有社會(huì)凝聚力。

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

?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)絡(luò)G在影響力博弈中具有社會(huì)凝聚力。則需證明不存在S?GC，使得?u∈S，fS(u)>FGC(u)，如式(10)所示。

(10)

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

圖2 核心邊緣算法流程

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

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

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

算法一 基于最大團(tuán)的核心邊緣算法

CPMC算法可以快速得到一個(gè)明顯的、穩(wěn)定性較好的網(wǎng)絡(luò)核心，因?yàn)樗紤]了群體的特性。這種方法的缺點(diǎn)是可能導(dǎo)致在選擇核心節(jié)點(diǎn)時(shí)沒有考慮個(gè)體，為了更準(zhǔn)確地選擇核心部分的節(jié)點(diǎn)，應(yīng)該將群體和個(gè)體的特性都加以考慮。對(duì)此，本文提出了CPIN算法。

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

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

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

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

在算法二中對(duì)該算法進(jìn)行了詳細(xì)的介紹。

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

3.3 CPMC與CPIN區(qū)別

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

4 實(shí)驗(yàn)和結(jié)果

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

4.1 實(shí)驗(yàn)設(shè)置

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

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

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

4.2 實(shí)驗(yàn)結(jié)果

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

圖4 RC網(wǎng)絡(luò)中不同算法實(shí)現(xiàn)社會(huì)凝聚力所需花費(fèi)

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

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

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

續(xù)表

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

5 總結(jié)和展望

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