競爭網(wǎng)絡(luò)中合作策略的研究

楊旭華，周榮升，童長飛

(1.浙江工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院，杭州 310023；2.溫州大學(xué)計算機科學(xué)與工程系，浙江 溫州 325035)

競爭網(wǎng)絡(luò)中合作策略的研究

楊旭華1，周榮升1，童長飛2

(1.浙江工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院，杭州 310023；2.溫州大學(xué)計算機科學(xué)與工程系，浙江 溫州 325035)

合作與競爭驅(qū)動自然社會與生態(tài)系統(tǒng)的動態(tài)演化，這些機制的相互作用可以對多個網(wǎng)絡(luò)產(chǎn)生不同的影響?；谔卣飨蛄恐行男?，在網(wǎng)絡(luò)的網(wǎng)絡(luò)基礎(chǔ)之上提出合作競爭模型，定義網(wǎng)絡(luò)之間對外是一種競爭關(guān)系，對內(nèi)為合作關(guān)系。揭示合作競爭特性，依據(jù)節(jié)點的重要性不同將合作策略與競爭策略進行了分類，研究模塊網(wǎng)絡(luò)間不同合作策略對集群網(wǎng)絡(luò)乃至整個網(wǎng)絡(luò)的資源配置的影響，發(fā)現(xiàn)重要性越大的節(jié)點間的結(jié)合能夠給網(wǎng)絡(luò)帶來更多的利益。

合作競爭；特征向量中心性；復(fù)雜網(wǎng)絡(luò)；網(wǎng)絡(luò)的網(wǎng)絡(luò)

0 引言

研究網(wǎng)絡(luò)結(jié)構(gòu)最終目的是為了更好地理解網(wǎng)絡(luò)背后系統(tǒng)所代表的行為[1]，迄今為止，復(fù)雜網(wǎng)絡(luò)在實際系統(tǒng)中的應(yīng)用已經(jīng)取得了豐碩的成果，復(fù)雜網(wǎng)絡(luò)由最初的描述系統(tǒng)的拓撲結(jié)構(gòu)，轉(zhuǎn)而投向動態(tài)的過程研究，隨著復(fù)雜網(wǎng)絡(luò)領(lǐng)域的推進與深入，研究發(fā)現(xiàn)單一的網(wǎng)絡(luò)并不能準確地囊括真實世界系統(tǒng)的行為[2]，最近，一些研究顯示，孤立網(wǎng)絡(luò)中存在的魯棒性[3]、同步[4]、合作、運輸與疾病傳播等特性隨著網(wǎng)絡(luò)之間的連接發(fā)生著顯著的變化，不同網(wǎng)絡(luò)之間的交互可能使得網(wǎng)絡(luò)無法保留原有的屬性。為了更好地理解復(fù)雜系統(tǒng)的有關(guān)特征與動力學(xué)的行為特性，人們正逐步開始對網(wǎng)絡(luò)的網(wǎng)絡(luò)的深入研究[5-6]。

網(wǎng)絡(luò)的網(wǎng)絡(luò)可以理解為網(wǎng)絡(luò)由不同模塊化的網(wǎng)絡(luò)所組成，不同模塊網(wǎng)絡(luò)的結(jié)合無可避免存在著合作與競爭現(xiàn)象，合作競爭理論的提出主要源于對競爭本身固有缺點的認識和當今復(fù)雜經(jīng)營環(huán)境的認知[7]，當前競爭合作理論還無法為不同的競爭與合作提供精確的測度，無法有效直觀通過數(shù)據(jù)發(fā)現(xiàn)個體之間合作為群體帶來的效益[8]。合作與競爭策略的選擇主要為了解決兩個關(guān)鍵的問題:從網(wǎng)絡(luò)自身進行考慮，對外如何通過與其他網(wǎng)絡(luò)進行競爭獲取最大利益。如果從集團效益考慮，對內(nèi)模塊子網(wǎng)之間應(yīng)該如何進行合作才能為集群網(wǎng)絡(luò)獲取最大利益[9]。

目前現(xiàn)有的研究合作競爭網(wǎng)絡(luò)的主要方式是通過建立博弈模型，針對企業(yè)管理體系建立競爭策略分析需要大量的具體實例[10-11]，強調(diào)戰(zhàn)略的互動性與系統(tǒng)性，但缺乏一定的普適性，無法在底層機理上給競爭合作體系做一個明確的界定。通過網(wǎng)絡(luò)的網(wǎng)絡(luò)研究合作競爭現(xiàn)象，可以檢測分析深入研究網(wǎng)絡(luò)中各個模塊，研究不同的網(wǎng)內(nèi)結(jié)構(gòu)對整個網(wǎng)絡(luò)動力學(xué)過程的影響。這對了解整個系統(tǒng)的內(nèi)部機理具有非常重要的作用。例如在文獻[12]中滲流在網(wǎng)絡(luò)之間的相互連接過程起著至關(guān)重要的作用，最終導(dǎo)致一階滲流相變的現(xiàn)象。文獻[13]表明，建立兩個社區(qū)的核心節(jié)點之間的聯(lián)系可以提高疾病的傳播效率，文獻[14]說明單一的網(wǎng)絡(luò)組合成一個相互關(guān)聯(lián)的網(wǎng)絡(luò)需要經(jīng)過一個不連續(xù)的過渡關(guān)系。本文將合作競爭理論應(yīng)用于網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)中，提出合作競爭模型，展示不同的合作策略在競爭網(wǎng)絡(luò)中的應(yīng)用，并通過數(shù)值仿真分析不同的網(wǎng)絡(luò)結(jié)構(gòu)揭示該模型的有效性，對未來分析不同網(wǎng)絡(luò)之間的合作策略對資源分配的影響具有一定的理論價值與現(xiàn)實意義。

1 合作競爭網(wǎng)絡(luò)模型

圖1 合作競爭模型Fig.1 Cooperation-competition model

基于對合作競爭特性的認知與考察，建立合作競爭模型如圖1所示，節(jié)點代表不同網(wǎng)絡(luò)之中的個體，節(jié)點的大小代表各個節(jié)點的重要性程度，不同顏色部分表示不同的模塊網(wǎng)絡(luò)，由圖1中A1,A2,B1,B2所標識，多個模塊網(wǎng)絡(luò)將組成集群網(wǎng)絡(luò)，由T1,T2所標識，將模塊網(wǎng)絡(luò)之間的個體的連接視為合作(深灰邊所示)，不同集群網(wǎng)絡(luò)之間個體的連接視為競爭(黑色邊所示)，根據(jù)相互連接節(jié)點重要性的不同，將其分為不同的合作與競爭策略，主要有CC合作策略，CP合作策略，PC合作策略，PP合作策略，CC競爭策略，CP競爭策略，PC競爭策略，PP競爭策略，C代表關(guān)鍵節(jié)點(Central Point)，P代表邊緣節(jié)點(Peripheral Point)。

本文主要通過研究特征向量中心性量化節(jié)點的重要性，特征向量中心性不僅僅是復(fù)雜網(wǎng)絡(luò)學(xué)科中量化節(jié)點重要性的一種重要方法[15-16]，更關(guān)鍵是它能夠描述網(wǎng)絡(luò)中能量遷移的動力學(xué)過程。特征向量中心性刻畫一個節(jié)點的重要性體現(xiàn)在其鄰居節(jié)點的重要性和數(shù)量上，節(jié)點的重要性可以被刻畫化成一個資源掠奪的動態(tài)過程，標記整個網(wǎng)絡(luò)的資源是一定的，每個節(jié)點根據(jù)節(jié)點重要性的不同所獲得一定資源比例，在這個前提之下，研究如何通過個體之間的不同合作或者競爭策略使得個體所在的模塊網(wǎng)絡(luò)和集群網(wǎng)絡(luò)獲得最大的資源利益[17]。

2 競爭網(wǎng)絡(luò)中合作策略研究

合作競爭模型中主要用到的拓撲方法主要是特征向量中心性，該方法主要描述個體重要性，基于這個理念，可以定義節(jié)點的特征向量中心性為其他鄰居節(jié)點的中心和：

(1)

c為一個常量，M為網(wǎng)絡(luò)的鄰接矩陣，并且Mij>0。該方法的動態(tài)過程可以描述為任選一個初始向量X(0)循環(huán)與鄰接矩陣M相乘，直至向量不再改變趨于穩(wěn)態(tài)?？梢缘玫?/p>

(2)

假如每次迭代之后，有|x(t)|=1，當t趨于無窮的時候，x(t)會收斂到M的主特征向量。由上述可得主特征向量為

(3)

特征值λ1決定了主特征向量的收斂速率,時間不斷趨于無窮的過程中，x(t)將會趨于原始矩陣M第一特征向量u1。

在合作競爭模型的基礎(chǔ)之上，假設(shè)首先忽略模塊網(wǎng)絡(luò)之間合作對外部競爭的影響,將集群網(wǎng)絡(luò)視為同一個整體，定義為T1網(wǎng)絡(luò)與T2網(wǎng)絡(luò)，假定T1鄰接矩陣的第一特征值大于T2鄰接矩陣的特征值，λT1>λT2:

Ms*us,1=λs,1*us,1

(4)

λS,1為整個系統(tǒng)的鄰接矩陣MS的最大特征值。因為S網(wǎng)絡(luò)通過T1與T2進行競爭，可知MS=MT1T2+∈P,∈P代表用何種策略進行連接兩個網(wǎng)絡(luò)，由于構(gòu)造的網(wǎng)絡(luò)是無向的所以可知Pij=Pij=1，將組成的新的網(wǎng)絡(luò)S的第一特征向量us看作T2網(wǎng)絡(luò)對T1網(wǎng)絡(luò)的干擾，通過干擾理論[18]，可得

us=uT1,1+εv1+ε2v2+o(ε3)

(5)

λs,1=λT1,1+εt1+ε2t2+o(ε3)

(6)

新形成的網(wǎng)絡(luò)的第一特征向量認為是小的網(wǎng)絡(luò)對大的網(wǎng)絡(luò)的干擾的累加所得。

(7)

(8)

(9)

因為這里忽略了T1，T2集群網(wǎng)絡(luò)內(nèi)部合作之間的擾動，忽略外部競爭對內(nèi)部的影響，將內(nèi)部的合作也視為模塊網(wǎng)絡(luò)之間的競爭。假設(shè)λA1>λA2,λB1>λB2可得

(10)

(11)

(12)

(13)

綜合上述公式(8),(10),(12)得:

(14)

p1代表模塊網(wǎng)絡(luò)之間的合作策略對整個矩陣的微擾，p代表集群網(wǎng)絡(luò)之間的競爭策略對網(wǎng)絡(luò)矩陣之間的擾動。us代表新形成的網(wǎng)絡(luò)S的特征向量隨著集群網(wǎng)絡(luò)T1內(nèi)部模塊之間合作策略與集群網(wǎng)絡(luò)T2的競爭策略的擾動，從而影響對整個網(wǎng)絡(luò)中資源的走向。

3 合作競爭網(wǎng)絡(luò)模型數(shù)值仿真研究

圖2a中A1，B1為分布在不同集群下有100個固定節(jié)點的星形網(wǎng)絡(luò)，A2，B2為不斷增長的星形網(wǎng)絡(luò)，并且網(wǎng)絡(luò)的增長速率相同，A1，A2選擇CC合作策略構(gòu)成T1集群，B1，B2選擇PP合作策略構(gòu)成T2集群網(wǎng)絡(luò)，T1與T2集群網(wǎng)絡(luò)進行CC競爭策略，上述模型都采用一個連接器進行連接。橫坐標代表A2，B2的星形網(wǎng)絡(luò)中節(jié)點的個數(shù)，縱坐標代表各個模塊在在整個網(wǎng)絡(luò)S中資源占有的程度。模塊網(wǎng)絡(luò)之間也存在著競爭，隨著A2，B2模塊的增長并且超過各自合作模塊時，在整個合作競爭過程中將為自身模塊帶來一個非連續(xù)的突變關(guān)系[15][16]。想要在整個合作過程為自身模塊帶來效益的最快方法就是將自身的影響力提升并超過與你合作的模塊網(wǎng)絡(luò)。

圖2b表示T1，T2集群網(wǎng)絡(luò)通過選擇不同的合作策略在競爭過程中所獲得的資源比，T1網(wǎng)絡(luò)內(nèi)部通過CC合作策略建立合作關(guān)系，T2通過PP合作策略建立合作關(guān)系。個體之間的合作對兩個集群網(wǎng)絡(luò)之間的競爭影響是巨大的，僅僅改變了一個個體之間的連接對整個網(wǎng)絡(luò)中的資源遷移產(chǎn)生了巨大的變化。兩個模塊網(wǎng)絡(luò)之間的差異越小，通過改變合作策略對集群網(wǎng)絡(luò)所帶來的影響也越明顯。

圖2 星形網(wǎng)絡(luò)合作與競爭Fig.2 Cooperation-competitionof star networks

為了讓合作競爭模型具有普適性，使用小世界網(wǎng)絡(luò)[19]替代星形網(wǎng)絡(luò)，圖3a中A1，B1為兩個相同的小世界網(wǎng)絡(luò)，每個網(wǎng)絡(luò)有200個節(jié)點，每個節(jié)點有6個鄰居節(jié)點，以隨機概率0.2至1隨機化重連邊使得網(wǎng)絡(luò)的最大特征值為7.43，A2，B2同為兩個相同的小世界網(wǎng)絡(luò)，每個網(wǎng)絡(luò)有200個節(jié)點，每個節(jié)點有6個鄰居節(jié)點，兩個網(wǎng)絡(luò)是相等的，以隨機概率0.2至1隨機化重連邊同時改變A2，B2的結(jié)構(gòu)來改變兩個網(wǎng)絡(luò)的最大特征值。橫坐標表示模塊網(wǎng)絡(luò)鄰接矩陣所計算的最大特征值，縱坐標各個模塊網(wǎng)絡(luò)在整個網(wǎng)絡(luò)S中資源占有的程度。圖3b圖中表示兩個通過不同小世界網(wǎng)絡(luò)所構(gòu)成的集群網(wǎng)絡(luò)在不同的合作模式所獲得的資源比。這里的每種策略都只通過一個合作連接器與競爭連接器。

圖3 小世界網(wǎng)絡(luò)合作與競爭Fig.3 Cooperation-competition of small-world networks

圖4a中A1，B1為200個節(jié)點，每個節(jié)點的度數(shù)為2所組成的相同的無標度網(wǎng)絡(luò)[20]，改變網(wǎng)絡(luò)的拓撲結(jié)構(gòu)使得兩個網(wǎng)絡(luò)的最大特征值都為7.43，A2，B2為200個節(jié)點，每個節(jié)點度數(shù)為2的相同的無標度網(wǎng)絡(luò)，改變A2，B2的拓撲結(jié)構(gòu)來改變兩個網(wǎng)絡(luò)的最大特征值。使之分別與A1，B1網(wǎng)絡(luò)進行合作。圖4b代表由無標度網(wǎng)絡(luò)組成的集群網(wǎng)絡(luò)T1，T2之間的競爭。通過小世界網(wǎng)絡(luò)與無標度網(wǎng)絡(luò)在合作競爭模型中的數(shù)值仿真，在競爭過程中可以發(fā)現(xiàn)，合作的雙方隨著兩個集群網(wǎng)絡(luò)所帶來的效益主要由模塊網(wǎng)絡(luò)所構(gòu)成的網(wǎng)絡(luò)矩陣的第一特征值所決定，當兩個合作網(wǎng)絡(luò)之間的特征值越接近，對整個集群所帶來的效益也將越高。當且僅能選擇一種合作策略的前提下，當兩個網(wǎng)絡(luò)之間的最大特征值越接近，為集群網(wǎng)絡(luò)帶來的利益也越大。

圖4 無標度網(wǎng)絡(luò)的合作與競爭Fig.4 Cooperation-competition of scale-free networks networks

圖5主要展示在通過不同合作策略的集群網(wǎng)絡(luò)T1與PP合作策略的集群網(wǎng)絡(luò)進行競爭過程中，所帶來的效益比，T1，T2僅有合作策略不同，都是兩個小世界模塊網(wǎng)絡(luò)構(gòu)成的集群。MA1,MA2分別表示兩個模塊網(wǎng)絡(luò)A1，A2之間進行合作的個體在各自模塊網(wǎng)絡(luò)中的重要程度，代表通過不同的合作策略在整個資源掠奪中所取得的利益比。圖5a圖展示了A1，A2模塊網(wǎng)絡(luò)中重要性前十五的個體分別進行合作與PP合作策略進行對比，圖5b圖中展示了A1，A2模塊網(wǎng)絡(luò)所有的合作策略與PP合作策略進行對比。模型都有且僅有一個合作連接器與競爭連接器，由實驗結(jié)果可以看出,模塊之間的合作為集群網(wǎng)絡(luò)所帶來的利益隨著節(jié)點重要性的增強而增強，這個效果隨著節(jié)點重要性的增強而尤為明顯。

圖5 不同的合作策略所帶來的效益比Fig.5 Benefit ratio with different cooperation strategies

4 結(jié)論

通過研究合作競爭模型，發(fā)現(xiàn)集群網(wǎng)絡(luò)間資源的掠奪情況很大程度取決于其內(nèi)部模塊間合作策略的選擇，正確的合作策略能夠很大程度影響到網(wǎng)絡(luò)資源的重新分配。模塊網(wǎng)絡(luò)在資源重新分配的過程中存在不連續(xù)過渡現(xiàn)象，主要和其鄰接矩陣的最大特征值有關(guān)。通過數(shù)值建模分析，發(fā)現(xiàn)兩個模塊網(wǎng)絡(luò)中合作個體的重要性越大，其鄰接矩陣的最大特征值越接近，為其所在的集群網(wǎng)絡(luò)帶來的效益也越多，這對現(xiàn)實生活中的各個系統(tǒng)具有參考意義。

本文主要構(gòu)建了基于特征向量中心性的合作競爭模型，將傳統(tǒng)的單一網(wǎng)絡(luò)框架應(yīng)用到“網(wǎng)絡(luò)的網(wǎng)絡(luò)”框架體系中[21]，模擬網(wǎng)絡(luò)之間的合作以及競爭，展示個體之間如何通過選擇不同的合作策略對模塊乃至集群網(wǎng)絡(luò)在復(fù)雜的競爭環(huán)境中的影響,該模型的建立對未來將應(yīng)用場景拓展到一些動力學(xué)以及諸如魯棒性，同步，散播或擁塞等功能特性的研究也具有十分重大的意義。合作競爭模型可以應(yīng)用生活中的網(wǎng)站連接策略選擇等實際場景，其結(jié)論具有普適性，適用于寬范圍系統(tǒng)，對其他在面臨競爭過程中選擇合作對象的企業(yè)或者組織具有一定的參考價值。

[1]Newman M E J. Networks:an Introduction[M]. 北京電子工業(yè)出版社, 2014.

[2]李明, 汪秉宏. 多重網(wǎng)絡(luò)的結(jié)構(gòu)與魯棒性[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 2015, 12(2): 32-37. Li Ming, Wang Binghong, The structure and robustness of multilayer networks[J]. Complex Systems and Complexity Science,, 2015, 12(2): 32-37.

[3]Fortunato S. Community detection in graphs[J]. Physics Reports, 2010, 486(3-5):75-174.

[4]Gao J, Buldyrev S V, Havlin S, et al. Robustness of a network of networks[J]. Physical Review Letters, 2011, 107(19):346-356.

[5]Arenas A, Díaz-Guilera A, Kurths J, et al. Synchronization in complex networks[J].Phys Rep， 2008,469, 93-153.

[6]Nicosia V, Bianconi G, Latora V, et al. Growing multiplex networks[J]. Physical Review Letters, 2013, 111(5):1-6.

[7]吳昊, 楊梅英, 陳良猷. 合作競爭博弈中的復(fù)雜性與演化均衡的穩(wěn)定性分析[J]. 系統(tǒng)工程理論與實踐, 2004, 24(2):90-94. Wu Hao, Yang Meiying, Chen Liangyou. An analyzes on complexity and evolutionary stability in coopetition games[J]. System Engineering Theory and Practice, 2004, 24(2):90-94.

[8]Granell C, Gómez S, Arenas A. Competing spreading processes on multiplex networks: awareness and epidemics[J]. Physical Review E, 2014, 90(1): 012808.

[9]Gómez-Gardenes J, Reinares I, Arenas A, et al. Evolution of cooperation in multiplex networks[J]. Scientific reports, 2012, 2.

[10] Wang Z, Szolnoki A, Perc M. Interdependent network reciprocity in evolutionary games[DB/OL].[2016-07-07]. http://dx.doi.org/1038/srepo1183.[11] Cygler J, Co-opetition in network relations between businesses[J]. Organization and Management,2010,139(1) : 59-71.

[12] Bianconi G. Statistical mechanics of multiplex networks: entropy and overlap.[J]. Physical Review E, 2013, 87(6):062806.

[13] Canright G S, Engo-Monson K. Spreading on networks: a topographic view[J]. Complexus, 2006,3,131-146.

[14] Radicchi F, Arenas A. Abrupt transition in the structural formation of interconnected networks[J]. Nature Physics, 2013, 9(11): 717-720.

[15] Qi X, Fuller E, Wu Q, et al. Laplacian centrality: a new centrality measure for weighted networks[J]. Information Sciences, 2012, 194: 240-253.

[16] Solá L, Romance M, Criado R, et al. Eigenvector centrality of nodes in multiplex networks[J]. Chaos: an Interdisciplinary Journal of Nonlinear Science, 2013, 23(3): 033131.

[17] Aguirre J, Papo D, Buldú J M. Successful strategies for competing networks[J]. Nature Physics, 2013, 9(4): 230-234.

[18] Marcus R A. Brief comments on perturbation theory of a nonsymmetric matrix: the GF matrix[J]. The Journal of Physical Chemistry A, 2001, 105(12): 2612-2616.

[19] Watts D J, Strogatz S H. Collective dynamics of ”small-world” nettworks[J]. Nature, 1998, 393(6684):440-2.

[20] Pastor-Satorras R, Vespignani A. Epidemic spreading in scale-free networks.[J]. Physical Review Letters, 2001, 86(14):3200-3.

[21] Fang J Q, Liu Q H, Tang M, et al. Network science faces the challenge and opportunity:exploring “network of networks” and its unified theoretical framework[R]. The 11th China Forum on Network Science,Shanghai,2015.

(責(zé)任編輯 李進)

Cooperation Strategy in Competition Networks

YANG Xuhua1， ZHOU Rongsheng1， TONG Changfei2

(1.School of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China;2.Department of Computer Science and Engineering, WenZhou University, Wenzhou 325035, China)

Cooperation and competition drive the dynamic evolution of the natural social and ecological system, and the interaction of these mechanisms can have different effects on multiple networks. Based on the basis of eigenvector centrality, we propose a cooperation-competition model based on the network of networks, to give a definition that the network is a kind of competition between the external relations, but the cooperation within the relationship. To reveal the competition characteristics, we classify the cooperation strategies and competitive strategies to do some research on the influence if different cooperation strategies among module network will bring the question of resource distribution to cluster network, even the entire network, and then find out the combination of the nodes with greater importance bringing.

cooperation and competition； eigenvector centrality； complex network； network of networks

1672-3813(2017)02-0046-06；

10.13306/j.1672-3813.2017.02.007

2016-10-10；

2017-01-10

國家自然科學(xué)基金(61374152)；浙江省自然科學(xué)基金(LY17F030016,LQ13G010007)

楊旭華(1971-)，男，浙江余姚人，博士，教授，主要研究方向為復(fù)雜網(wǎng)絡(luò)、人工智能。

N94

A