社交化P2P系統中基于個體動態屬性的共演化模型

田琳琳,李明楚,金 星,王 震

1(大連理工大學 軟件學院,遼寧 大連 116620)

2(杭州電子科技大學 網絡空間安全學院,杭州 310038)

1 引 言

在自組織資源分享與協作系統中,用戶間高效合作是保障服務質量的前提.然而在人類社會及在線社交應用中,理性個體與群體收益的矛盾常使系統陷入社會困境[1].例如,P2P系統中大量存在的“搭便車”行為,導致資源匱乏、路由與查詢效率低下且負載過重,嚴重損害系統性能和可信度,因此需要激勵機制促進合作[2,3].近年來社交化P2P應用大量涌現,利用用戶的行為習慣、內在屬性和社交關系等特性提升系統服務質量[4-6],積極互動的利他者通過聚集抵御搭便車者,而基于空間互惠的激勵機制為改善網絡環境中P2P系統性能提供理論支持[7,8].年齡作為與用戶生存期相關的內在屬性,影響其行為屬性與社交屬性.現實生活中同齡人間通常有相似的社交行為方式和興趣話題,因此在社交系統中更容易成為經常互動的朋友.基于年齡屬性的伙伴選擇機制能否促使利于合作的結構形成,這種動態屬性如何影響個體行為的演化是值得探討的問題.

演化博弈為探討網絡群體行為提供理論框架,共演化博弈模型適合分析動態網絡環境中的合作問題[9-11].自治系統中的智能體為獲得更佳收益,通過學習不斷調整策略和社交關系,從而影響策略分布與網絡結構.這種個體特性與群體行為的共演化,形成一種合作反饋機制[12].學者Zimmermann和Santos較早研究斷邊重連機制,發現改變交互環境的方式能有效促進合作[13].利用全局動力學與估計理論分析的方法,相關研究認為若個體獲得足夠機會調節不利的社交聯系,自適應網絡中可以維持較高的合作水平[14].這些工作大多假設結構演化時合作者間的親社會關聯穩定,而與自私者的反社會連接是較脆弱,并且合作者有優先調整社會關系的權利.在存在各種攻擊與噪聲的環境中,通常無法準確判斷對手的策略,因此該假設不符合實際情況.付峰等人提出社交網絡中基于信譽的伙伴選擇機制,信譽高的合作個體在吸引新伙伴方面更有優勢,而信譽低的自私個體容易被孤立[15].文獻[16]利用有向加權圖描述動態社交網絡,利他行為利于社交關系保持穩定,因此形成促進合作的網絡結構.現實中的社會關系維持的時間不僅由雙方策略決定,還與個體的地理位置、種族文化以及其他屬性相關.最新研究探討基于友誼的同伴形成機制,斷邊重連時考慮個體標簽,形成相似屬性者團簇從而促進合作[17].但共演化模型中個體標簽靜態均勻分布,并未考慮具有實際意義的動態標簽.因此構建基于用戶動態屬性的共演化模型,有助于深入理解自組織協作系統中合作如何涌現和維持.

年齡是生物種群和人類社會中個體具有的自然屬性,在線網絡環境中個體還具有系統年齡,且在一定程度上決定個體生存狀態與行為能力.在合作演化的研究中,年齡因素影響個體的收益分配、策略學習與影響力,這種與生存期相關的異構性能促進合作的生存與傳播.Szolnoki與Perc探討空間囚徒困境博弈時首先提出個體年齡決定其策略轉移能力,在此基礎上王震等人分析個體學習能力差異對合作的影響[18].在公共品博弈模型中,當年輕者分配的收益較少時,有利于合作者團簇抵御自私者入侵[19].最新研究構建年齡決定個體影響力的共演化模型,結果表明傾向學習長者更易于促進合作[20].但其中個體以固定概率與背叛者斷連,結構演化未考慮年齡因素.

為深入理解與分析社交化P2P系統中網絡群體合作行為,本文在演化博弈的理論框架下探討基于個體動態標簽的伙伴選擇機制,構建個體行為策略、內在屬性與社交關系的共演化模型.與以往工作不同之處:首先,考慮以年齡屬性為代表的動態標簽,分析靜態與動態年齡協議下群體行為的演化動態性;其次,結構演化更符合現實情況,在自適應網絡中關系的穩定性由個體間關系強度決定,有限理性個體更新朋友圈時考慮交互歷史、雙方收益以及屬性相似度.

2 模型構建

系統中具有特定屬性的智能體參與交互,每個對等個體i具有動態屬性集合Attri={Si,Ri,Ai},其中包括策略屬性Si、社交屬性Ri及以年齡為代表的自然屬性Ai.下面具體介紹用戶動態屬性驅動的共演化模型.

2.1 空間囚徒困境博弈模型

策略屬性Si∈[A,F]包括利他策略A與搭便車策略F,個體的策略決定其行為和收益.在社交應用中,利他個體進行積極交互活動,包括資源分享、信息轉發與回復評論等合作行為,而搭車者只獲取資源或瀏覽信息,并不分享資源或參與互動.大量自私個體傾向不勞而獲從而損害群體利益,囚徒困境博弈模型常被用來研究這種社會困境問題.個體的收益由交互雙方的策略決定,博弈中個體i與j交互后收益為uij.由于利他行為需支付帶寬、資源與能量等開銷,相當于自私者獲得額外收益0<μ<1.當博弈雙方均為利他者時都獲得單位收益(即uAA=1),若同為搭車者收益均為uFF=μ.而當利他個體遭遇自私個體時沒有回報uAF=0,而后者收獲uFA=1+μ.

2.2 共演化模型

共演化主要包括策略學習、年齡更新及關系調整三個階段:個體經過τs輪交互后調整策略,即每輪以ωs=1/τs的概率學習他人策略;在不同的年齡規則下,個體的年齡以ωA的頻率進行更新;根據收益和年齡調整與朋友之間的親密度,社交關系以ωR的頻率進行演化.共演化的各過程均采用同步更新方式,參數ω=ωs/ωR刻畫策略更新與結構調整的時間尺度[15].

2.2.1 策略演化

按照成對比較的策略更新方式,個體i隨機選擇鄰居j∈Ni,根據雙方收益Ui與Uj學習更有利的策略.現實生活中模仿朋友的行為方式具有不確定性,采用Fermi函數描述下一輪i采取j的策略的概率W(Si←Sj),見公式(1).

(1)

其中K刻畫策略學習的強度,K→時近于確定性學習,即Ui

2.2.2 年齡演化

年齡從一定程度上反映個體的特點及其生存狀態,根據不同應用場景和年齡協議[19],標簽Ai∈[1,Amax]可以描述個體i的生物年齡或進入系統的在線時間,也可表示保持某種行為時長的策略年齡.最大年齡參數Amax表示個體的生存期,并決定了年齡標簽的數目.當Amax=1時個體年齡相同,作為基本情況Basic.而Amax→不符合現實,且歸一化后個體間年齡差距過小.根據仿真實驗結果該參數取適中值Amax=20.

當年齡更新頻率較低時(ωA?ωs),認為個體年齡不隨博弈過程發生改變,文獻[17]的方案可視為靜態年齡規則QueA.為分析P2P系統中個體的動態屬性,本文考慮如下自然年齡規則NatA和策略年齡規則StrA.

自然年齡規則下,每輪交互后個體年齡自增,超過生存期后視為新用戶并重置年齡,公式(2)給出年齡更新方式.

(2)

若本輪個體未與其他個體進行交互則認為處于休眠狀態,即被孤立的個體系統年齡保持不變.

策略年齡規則在上述規則的基礎上,個體策略改變后便演化為新生個體,年齡更新方式見公式(3).

(3)

2.2.3 結構演化

個體交互后,根據當前雙方的收益和年齡相似度調整社交關系.關系強度Rij描述個體i與朋友j(i≠j)的親密關系,這種關系具有非對稱性(Rij≠Rji)及不穩定性,其值越大則i保持與j的關聯的概率越高,即單向的友誼關系越穩固.現實生活中年齡相似的老朋友之間通常更親近,并且交往中雙方皆有利可圖更易于關系的維護,公式(4)給出關系強度的更新規則.

(4)

第n輪關系強度取決于交互經驗及本輪交互情況,其中遺忘因子α∈[0,1]描述歷史信息所占的比重.利他因子β∈[0,1]刻畫雙方收益對當前關系的影響,β較小時更注重對方的收益,而β→1時親密度更大程度上由自身利益所決定.

所謂“物以類聚,人以群分”,親密度通常受雙方屬性的影響,定義相似度函數刻畫朋友間年齡的差異性,見公式(5).

sim(i,j)=1-(|Ai-Aj|/Amax)θ

(5)

其中參數θ≥0表示差異強度系數,當θ=0時關系強度不考慮年齡因素回歸基本模型,本文采用簡單的線性相似度函數θ=1.

在動態網絡中每條邊的穩定程度由節點間的關系強度決定.個體i隨機選擇n=max{1,?m|Ni|」}個朋友,并分別以1-Rij的概率與其斷連,其中關系調整比例因子m∈[0,1].剔除不良社交關系后,個體嘗試尋找n個屬性相似的新朋友.在原有的朋友圈以外隨機選擇新朋友k建立連接,需排除自連接和剛斷連的鄰居,其重連概率見公式(6).

(6)

其中選擇強度λ≥0刻畫標簽差異敏感性,λ較大導致屬性不同的個體很難建立新的連接,當λ=0時回歸基本模型即隨機選擇新鄰居[13].不同于斷開親密度最低的鄰居的結構更新方式[17],本文的斷邊重連規則考慮到個體社交能力的異構性,而且不存在永遠穩定的連接.此外,度為零的節點為被孤立的個體,它們也有機會重新結識新朋友.因此這種基于個體屬性的結構演化規則更符合現實的社交方式.

3 仿真實驗及分析

為研究基于年齡屬性的伙伴選擇機制對群體行為的影響,構建共演化模型并進行蒙特卡洛仿真實驗.初始化階段個體策略和年齡隨機均勻分布,利用如下ER隨機網絡描述人口結構:節點數目N=1000、隨機連接L=5000條邊,平均度為10,雙向邊權初值為0.5.經過105-106輪蒙特卡洛步(MCS)演化基本穩定,演化結果取后100輪MCS的平均值,最終數據為20次獨立實驗的均值.為便于比較結果,實驗中的基本參數設置主要參照文獻[17],包括關系選擇強度λ=10、關系調整比例因子m=0.1、自私誘惑參數μ∈(0.2,0.4)以及時間尺度參數ω∈[0.2,0.3].假設有限理性個體具備適中的記憶能力和利他性,關系強度中遺忘因子和利他因子分別取默認值α=β=0.5.

3.1 利他策略演化結果

群體行為的演化結果很大程度上由自私誘惑參數μ決定,因此首先分析不同μ值對演化穩定后系統中利他個體比例ρc的影響.圖1給出基本情況Basic和三種年齡規則下的結果:μ值較小時演化穩定后ρc較高,策略A占優;隨著μ值增加自私行為逐漸增加,最終策略F占優.μA與μF分別描述合作占優與消失時參數臨界點,即μ≤μA時ρc=1,而μ≥μF時系統中基本全部演化為自私個體.相比于基本情況,三種年齡規則下μA與μF值較大,即利他者的生存空間更大,因此基于個體年齡的結構調整機制更利于合作的涌現與維持.其中策略年齡StrA規則顯著提升網絡群體的合作水平,不僅μA與μF值都最大,而且μA<μ<μF時系統中利他者比例最高.而固定年齡QueA與自然年齡NatA規則對于合作的促進程度基本相似,兩種規則下μ臨界值基本相同,而且μA<μ<μF時ρc值不相上下.

圖1 不同參數μ下演化穩定的合作比例Fig.1 Stationary fractions of cooperation in dependence on the benefit μ

基于空間互惠的理論,網絡結構利于合作,尤其當個體具有自主調節結構的能力時,利他者以聚簇的方式抵御自私者的入侵.圖2給出了不同參數ω和μ下演化穩定后結果.當ω→0時結構更新要快于策略調整,只有μ較低時利他策略才可能占優;隨著ω增大策略更新頻率增加,個體為獲得更好收益傾向于選擇策略F.而ω=1時策略和結構同時調整,利他個體生存空間更小μA<0.1.隨著μ值的增大,在ω值較小時ρc才能保持較高值,即只有當結構更新足夠快時合作才得以維持.在基于親密度的斷邊重連規則下,自私行為導致社交關系的不穩定,搭便車者容易被斷連從而不能獲得更豐厚的收益.這種孤立自私個體的方式,可以從一定程度上激勵利他行為.此外,利他個體也可以通過重連跳離自私個體的包圍,與具有相同年齡標簽的個體建立新的關系.StrA規則中利他者的年齡相當于信譽值,他們更容易建立穩定的關系并形成團簇,更好地抵御自私行為.因此相比于NatA的結果圖2(a),策略年齡規則下利他策略占優的空間更大,如圖2(b)所示.

圖2 不同參數ω和μ下合作演化結果(a)QueA(b)StrAFig.2 Stationary fractions of cooperation in dependence on the benefit μ and the time scale ω(a)QueA and(b)StrA

3.2 共演化過程

下面從時間維度探討各種年齡規則促進合作的機理,圖3給出在ω=0.3,μ=0.25時系統中群體合作的演化過程.演化初期,在策略均勻分布的群體中,自私行為獲得豐厚的收益,因此搭便車者占優勢.演化過程中合作比例呈下降趨勢,Basic的ρc曲線降至最低,而其他情況下搭車者對利他個體的侵蝕程度有限.在演化中期系統合作水平逐漸攀升,利他個體不斷調整交互環境從而形成團簇.根據年齡選擇新朋友的機制,使得年齡相仿的個體更容易聚集,空間互惠的作用更為明顯.隨后除基本情況外,最終系統幾乎全部演化為利他者.演化過程中,StrA規則下ρc降低幅度最小且攀升最快,較早演化為合作穩定狀態.下面從結構演化與年齡分布角度分析其原因.

圖3 不同年齡規則下利他策略的演化過程Fig.3 Time courses of the strategy evolution under age rules

圖4 StrA年齡規則下結構與平均年齡的演化過程(a)-(c)分別描述各種連接比、簇系數和利他者平均年齡的演化過程Fig.4 Evolution processes of the structures and ages under StrA rule Figures(a)-(c)describe time processes of fractions of different links,clustering coefficient of networks and average ages of altruism cooperators respectively

圖4中分別描述不同策略個體的連接比例、簇系數[9]以及歸一化的利他者平均年齡的演化過程.演化初期,合作者聚簇以抵御自私個體的剝削,能夠存活的少數利他者周圍的交互環境良好,不易改變策略因此平均年齡較高.在演化中期利他與搭車個體的連接比例A-F顯著下降,而利他個體之間的比例A-A不斷提升,他們不斷剔除與自私者的連接,從而逐步形成穩定的合作團簇,因此網絡中簇系數不斷攀升.年齡取決于策略保持的時間,因此團簇內部年長者居多,平均年齡繼續提升.當自私個體企圖侵蝕合作團簇時,位于邊界的個體改變策略后年齡歸零,和團簇內部年長利他個體的關系強度變得很低,更容易與合作團簇斷連.同時新生的利他個體,由于年齡關系更傾向與原來的自私朋友斷連.因此自私個體或團簇逐步被孤立,只有改變策略后與利他個體連接,才能獲得繼續生存的機會.演化中后期涌現出大量的新生利他者,平均年齡迅速下降,而當ρc值升高后則逐步回升,年齡結構趨于穩定.可見這種年齡的異構性能在一定程度上激勵合作.而其他兩種規則中,雖然年齡的異構性在一定程度上促進合作,但是NatA規則下由于年齡自增到最大后歸零,會突然改變團簇的年齡分布,因此演化過程中QueA的ρc始終保持在NatA之上.

3.3 不同參數值對演化結果的影響

年齡是個體的重要自然屬性,圖5描述不同生存期Amax對演化穩定后ρc的影響,可見適中的Amax能有效激勵個體的合作行為.該參數較小時,年齡標簽數目有限,不能正確反映個體的屬性和個體間的親密度.個體年齡達到最大值后要重置，良性社交關系可能由于年齡的突變而變得不穩定,干擾有效的社交關系調整,此時動態的年齡規則下系統合作水平要低于靜態規則QueA.隨著Amax的增大,這種不良干擾減弱.年齡基本能夠反映個體在社交網絡中交互時間、策略保持時間以及生存狀態,基于年齡的結構調整規則能夠在一定程度上激勵用戶間進行合作.此外,在社交關系更新時,采用歸一化的年齡度量親密度和重連概率,Amax較大時年齡標簽的差距較小,對合作的促進作用降低.在適當的范圍內Amax∈[5,50],演化后系統的合作率穩定在較高水平.

圖5 不同最大年齡對演化結果的影響Fig.5 Stationary fractions of cooperation on Amax

個體間關系強度影響網絡結構演化,下面討論參數α與β對演化結果的影響.遺忘因子α決定歷史信息在關系強度中的比重,為分析結構演化中的記憶效應,分析特定參數ω=0.2,μ=0.36下ρc與α的關系,如圖6(a)所示.可見α值在較小時,親密度主要由當前屬性與交互情況決定,系統中利他行為保持優勢.究其原因,建立與利他朋友的新的連接后,這種良性社交關系較為穩定,因缺乏交互經驗而斷連的概率較小.同時,當老朋友采取自私策略后,個體能較快遺忘先前經歷,使親密度迅速降低,以便盡快排除不良連接.而隨著α的增大,記憶效應更加明顯,不良社交關系不能及時斷開,與新利他朋友的親密度也不能及時提升,此時不能有效激勵合作行為的涌現.

圖6 關系強度參數α與β對演化結果的影響Fig.6 Stationary fractions of cooperation on different parameters(a)α and(b)β

現實社交網中個體并非完全理性,在度量親密度時不僅考慮自身的收益,由于責任和情感需求還可能考慮其他因素.利他因子β決定了雙方收益對關系強度的影響,該值越大則度量親密度越關注朋友的收益.圖6(b)描述了ω=0.2,μ=0.38時ρc與β的關系,可見較大β值利于激勵合作行為.由于合作性朋友會帶來理想的收益,個體更樂于與其保持連接,這從一定程度上加強了互惠連接.自私者雖能獲得豐厚的收益,但損人利己的行為降低親密度,利他朋友會主動調整與其的連接,不良社交關系斷連的概率較高.因此,這種結構演化方式使利他者在社交網絡中具有連接優勢,而自私者更容易被孤立,從而失去原有的收益優勢.

4 總 結

為深入理解合作如何在網絡群體中涌現,本文構建個體動態屬性、策略與網絡結構的共演化模型,分析社交化P2P系統中用戶屬性、行為及社交關系的演化動態性.探討以年齡為代表的動態屬性,比較不同的年齡協議對合作演化的影響.研究基于年齡的伙伴選擇機制,根據個體間關系強度更新社會關系.度量關系強度時引入年齡相似度因子,并根據年齡差異選擇新伙伴.仿真實驗表明,動態屬性驅動的共演化能夠促進網絡群體中合作涌現并維持,其中策略年齡規則更有利于形成穩定的合作團簇,拓展利他者的生存空間.未來工作可將這種動態的標簽擴展為其他屬性,并研究基于多屬性的關系形成機制對演化動態性的影響.

：

[1] Nowak M A.Five rules for the evolution of cooperation[J].Science,2006,5805(314):1560-1563.

[2] Haddi F L,Bencha?ba M.A survey of incentive mechanism in static and mobile P2P systems[J].Journal of Network & Computer Applications,2015,58(C):108-118.

[3] Wang Yue-feng,Vasilakos A V,Ma Jian-hua.VPEF:a simple and effective incentive mechanism in community-based autonomous networks[J].IEEE Transactions on Network and Service Management,2015,12(1):75-86.

[4] Liu Guo-xin,Shen Hai-ying,Ward L.An efficient and trustworthy P2P and social network integrated file sharing system[J].IEEE Transactions on Computers,2013,64(1):54-70.

[5] Wang Hai-yang,Wang Feng,Liu Jia-chuan,et al.Accelerating peer-to-peer file sharing with social relations:potentials and challenges[J].IEEE Journal on Selected Areas in Communications,2013,31(9):66-74.

[6] Shen Hai-ying,Ze Li,Kang Chen.Social-P2P:an online social network based P2P file sharing system[J].IEEE Transactions on Parallel & Distributed Systems,2015,26(10):2874-2889.

[7] Wu Tie,Lee Wei-tong,Nadra Guizani,et al.Incentive mechanism for P2P file sharing based on social network and game theory[J].Journal of Network & Computer Applications,2014,41(1):47-55.

[8] Tang Chang-bing,Wang Yu,Cao Lang,et al.Towards the role of social connectivity and aspiration level on evolutionary game[J].European Physical Journal B,2013,86(1):26-32.

[9] Wang Yuan-zhuo,Yu Jian-ye,Qiu Wen,et al.Evolutionary game model and analysis methods for network group behavior[J].Chinese Journal of Computers,2015,38(2):282-300.

[10] Perc M,Szolnoki A.Coevolutionary games-a mini review[J].Biosystems,2010,99(2):109-125.

[11] Cui Guang-hai,Li Ming-chu,Jin Xing,et al.Study of mechanism with punish-reward under evolutionary game framework[J].Journal of Chinese Computer Systems,2016,37(2):202-206.

[12] Wang Long,Cong Rui,Li Kun.Feedback mechanism in cooperation evolving[J].Chinese Science:Information Science,2014,44(12):1495-1514.

[13] Santos F C,Pacheco J M,Lenaerts T.Cooperation prevails when individuals adjust their social ties[J].Plos Computational Biology,2006,2(10):1284-1291.

[14] Rong Zhi-hai,Wu Zhi-xi,Chen Guang-rong.Coevolution of strategy selection time scale and cooperation in spatial prisoner's dilemma game[J].Europhysics Letters,2013,102(6):68005,1-9.

[15] Fu Feng,Hauert C,Nowak M A,et al.Reputation-based partner choice promotes cooperation in social networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2008,78(2):026117,1-8.

[16] Yang Zi,Wu Tie,Wang Long，et al.Effects of adaptive dynamical linking in networked games[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2013,88(1):042128,1-8.

[17] Chen Wei,Wu Tie,Li Zhi-wu,et al.Friendship-based partner switching promotes cooperation in heterogeneous populations[J].Physica a Statistical Mechanics & Its Applications,2016,443(1):192-199.

[18] Wang Zhen,Yang Yuan-han,Yu Ming-xing,et al.Age-related preferential selection can promote cooperation in the prisoner's dilemma game[J].International Journal of Modern Physics C,2012,23(2):1250013,1-11.

[19] Tian Lin-lin,Li Ming-chu,Lu Kun,et al.The influence of age-driven investment on cooperation in spatial public goods games[J].Chaos Solitons & Fractals,2013,54(9):65-70.

[20] Yang Guo-li,Huang Jin-cai,Zhang Wei-min.Older partner selection promotes the prevalence of cooperation in evolutionary games[J].Journal of Theoretical Biology,2014,359(24):171-183.

附中文參考文獻：

[9] 王元卓,于建業,邱 雯,等.網絡群體行為的演化博弈模型與分析方法[J].計算機學報,2015,38(2):282-300.

[11] 崔光海,李明楚,金 星,等.基于自組織激勵的P2P多媒體共享網絡節點合作的演化[J].小型微型計算機系統,2016,37(2):202-206.

[12] 王 龍,叢 睿,李 昆.合作演化中的反饋機制[J].中國科學:信息科學,2014,44(12):1495-1514.