博弈論在社交網(wǎng)絡(luò)中的應(yīng)用

代翔

（中國(guó)西南電子技術(shù)研究所成都610036）

博弈論在社交網(wǎng)絡(luò)中的應(yīng)用

代翔

（中國(guó)西南電子技術(shù)研究所成都610036）

在線社交網(wǎng)絡(luò)的迅速發(fā)展引起了各研究領(lǐng)域的廣泛關(guān)注。經(jīng)濟(jì)學(xué)中，研究者們使用博弈論分析網(wǎng)絡(luò)形成的機(jī)制，稱為網(wǎng)絡(luò)形成博弈，用于解釋現(xiàn)有網(wǎng)絡(luò)形成的原因。而在計(jì)算機(jī)領(lǐng)域，研究者們?cè)谏缃痪W(wǎng)絡(luò)的社團(tuán)演化，鏈接預(yù)測(cè)，推薦系統(tǒng)等方面都提出了很多成熟的算法和模型，其主要是用于學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu)并對(duì)用戶可能感興趣的其他用戶進(jìn)行推薦。結(jié)合博弈論和鏈接預(yù)測(cè)，基于效用最大化理論指導(dǎo)鏈接預(yù)測(cè)問題的研究具有重要的意義。論文概述了博弈論在社交網(wǎng)絡(luò)中進(jìn)行鏈接預(yù)測(cè)，社團(tuán)演化等方面的應(yīng)用，并提出博弈論在網(wǎng)絡(luò)演化方向的意義。

社交網(wǎng)絡(luò)；博弈論；鏈接預(yù)測(cè)；網(wǎng)絡(luò)演化

Class NumberTP311

1 引言

社交網(wǎng)絡(luò)的發(fā)展正改變著我們的生活，它不斷地縮短現(xiàn)實(shí)世界與網(wǎng)絡(luò)世界之間的距離，滿足了用戶社交和獲取網(wǎng)絡(luò)信息的需求，用戶可以通過社交網(wǎng)絡(luò)發(fā)布信息、圖片，進(jìn)行交友等行為。根據(jù)相關(guān)統(tǒng)計(jì)，國(guó)內(nèi)2015年11月份的社會(huì)化媒體排行榜如表1所示（JiaThis 2015）。以新浪微博為例，自2009年8月開始推出以來(lái)，用戶數(shù)量一直在大規(guī)模增長(zhǎng)，據(jù)微博數(shù)據(jù)相關(guān)統(tǒng)計(jì)顯示，到2015年9月，微博月活躍用戶達(dá)到2.22億人，日活躍用戶已達(dá)到1億。可見社交網(wǎng)絡(luò)用戶基數(shù)龐大，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)復(fù)雜，因而其中蘊(yùn)含的豐富信息引起了不同領(lǐng)域研究學(xué)者的廣泛研究。

博弈論是經(jīng)濟(jì)學(xué)的一個(gè)分支，它研究人們的策略互動(dòng)行為，并認(rèn)為人人都會(huì)在約束條件下最大化自身的利益。經(jīng)濟(jì)學(xué)中有一個(gè)著名的研究方向，網(wǎng)絡(luò)形成博弈（Network Formation Games，NFG），它研究社交網(wǎng)絡(luò)的形成機(jī)制。在網(wǎng)絡(luò)形成博弈模型中，每個(gè)結(jié)點(diǎn)擁有一個(gè)收益函數(shù)來(lái)表征通過當(dāng)前網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，該結(jié)點(diǎn)所做的某項(xiàng)決定或與其他結(jié)點(diǎn)建立的某條鏈接給自身帶來(lái)的收益［1］。在社交網(wǎng)絡(luò)中，用戶結(jié)點(diǎn)之間存在復(fù)雜的鏈接關(guān)系，每個(gè)用戶結(jié)點(diǎn)在與其他用戶建立鏈接關(guān)系時(shí)都希望最大化自身的收益。對(duì)于社交群體，都會(huì)存在一個(gè)穩(wěn)定狀態(tài)，即當(dāng)前群體中的每一個(gè)結(jié)點(diǎn)的收益都處于最大化［5］。

表12015 年11月社會(huì)化媒體排行榜

針對(duì)在線社交網(wǎng)絡(luò)衍生出的研究方向十分廣泛，比如鏈接預(yù)測(cè)、推薦系統(tǒng)、社團(tuán)演化等，各種模型和算法層出不窮，近年來(lái)，有研究提出在傳統(tǒng)方法的基礎(chǔ)上結(jié)合博弈論的思想來(lái)提高鏈接預(yù)測(cè)和社團(tuán)演化分析的準(zhǔn)確性。

隨著社交網(wǎng)絡(luò)的飛速發(fā)展，大量的用戶交互數(shù)據(jù)隨之而來(lái)，而整個(gè)網(wǎng)絡(luò)也時(shí)刻都在動(dòng)態(tài)演變，如何有效地分析用戶行為之間的相互影響以及網(wǎng)絡(luò)的演化過程成為一個(gè)新的研究熱點(diǎn)。而真實(shí)世界的網(wǎng)絡(luò)普遍具有小世界特性，這種特性最早可以追溯到社會(huì)學(xué)家Milgram在1967年所做的社會(huì)學(xué)實(shí)驗(yàn)，發(fā)現(xiàn)了“六度分離（six degrees of separation）”現(xiàn)象［9］。這種現(xiàn)象表明社會(huì)關(guān)系網(wǎng)絡(luò)中人與人之間的距離是很短的。1998年Watts和Strogatz［10～11］首次提出了小世界模型，揭示了小世界特性形成的原因。由于社會(huì)網(wǎng)絡(luò)都具有很強(qiáng)的小世界屬性，因此在小世界網(wǎng)絡(luò)上研究群體博弈行為將更加具有現(xiàn)實(shí)意義，因此本文將重點(diǎn)關(guān)注博弈論在鏈接預(yù)測(cè)和社團(tuán)演化等方面的應(yīng)用。

本文主要介紹博弈論在社交網(wǎng)絡(luò)中鏈接預(yù)測(cè)方面的應(yīng)用，并提出運(yùn)用博弈論進(jìn)行網(wǎng)絡(luò)演化分析的思路。

2 相關(guān)背景

博弈論：博弈論亦名“對(duì)策論”、“賽局理論”，屬應(yīng)用數(shù)學(xué)的一個(gè)分支，主要研究公式化了的激勵(lì)結(jié)構(gòu)間的相互作用。它是研究決策主體的行為發(fā)生直接相互作用時(shí)候如何決策以及決策的均衡問題，是具有斗爭(zhēng)或競(jìng)爭(zhēng)性質(zhì)現(xiàn)象的數(shù)學(xué)理論和方法，也是運(yùn)籌學(xué)的一個(gè)重要學(xué)科。博弈論考慮游戲中的個(gè)體的預(yù)測(cè)行為和實(shí)際行為，并研究它們的優(yōu)化策略。

·納什平衡：所謂納什均衡，是指一種策略組合，在該策略組合上，任何參與人單獨(dú)改變策略都不會(huì)得到好處。即如果在一個(gè)策略組合上，當(dāng)其他人都不改變策略時(shí)，沒有人會(huì)改變自己的策略，則該策略組合就是一個(gè)納什均衡。社交網(wǎng)絡(luò)中的納什平衡，我們可以直觀地理解為：在當(dāng)前網(wǎng)絡(luò)中，沒有任何一個(gè)用戶可以通過單方面的改變自身的鏈接而獲得更高的收益［6］。也就是說，在當(dāng)前網(wǎng)絡(luò)結(jié)構(gòu)中，所有用戶結(jié)點(diǎn)的收益都達(dá)到最大時(shí)，則當(dāng)前網(wǎng)絡(luò)處于納什平衡狀態(tài)。

·異構(gòu)信息網(wǎng)絡(luò)：如果一個(gè)網(wǎng)絡(luò)包含多種類型的結(jié)點(diǎn)和鏈接，那么該網(wǎng)絡(luò)為異構(gòu)信息網(wǎng)絡(luò)。異構(gòu)社交網(wǎng)絡(luò)可用G=（V，E）來(lái)表示，其中V是一個(gè)不同類型結(jié)點(diǎn)集合的并集，E是一個(gè)異構(gòu)鏈接集合的并集。社交網(wǎng)絡(luò)就是一個(gè)典型的異構(gòu)信息網(wǎng)絡(luò)。

·小世界網(wǎng)絡(luò)：小世界網(wǎng)絡(luò)是一種圖的類型，圖中大部分結(jié)點(diǎn)不與彼此鄰接，但大部分結(jié)點(diǎn)可以從任一其他點(diǎn)經(jīng)少數(shù)幾步就可到達(dá)。若將一個(gè)小世界網(wǎng)絡(luò)中的點(diǎn)代表一個(gè)人，而點(diǎn)之間的連線代表人與人認(rèn)識(shí)，則這小世界網(wǎng)絡(luò)可以反映陌生人由彼此共同認(rèn)識(shí)的人而連結(jié)的小世界現(xiàn)象［4］。

·網(wǎng)絡(luò)形成博弈（NFG）：NFG通常用來(lái)分析用戶在社交網(wǎng)絡(luò)中建立鏈接時(shí)的判斷力，它最核心的部分是效益函數(shù)，該函數(shù)可以解釋當(dāng)前特定網(wǎng)絡(luò)的形成原因。不同的效益函數(shù)構(gòu)成了不同的網(wǎng)絡(luò)形成博弈模型，也就使得用戶通過彼此之間的鏈接可以建立不同的網(wǎng)絡(luò)結(jié)構(gòu)。而網(wǎng)絡(luò)形成博弈的目的就是通過效益函數(shù)分析網(wǎng)絡(luò)在達(dá)到納什平衡的過程中，其中用戶所獲得的效益。

3 鏈接預(yù)測(cè)中的博弈論

3.1 鏈接預(yù)測(cè)與博弈論

鏈接預(yù)測(cè)是社交網(wǎng)絡(luò)研究的熱門方向之一。如圖1，它描述了6個(gè)社會(huì)網(wǎng)絡(luò)用戶之間的朋友關(guān)系（鏈接）。實(shí)線表示時(shí)刻已經(jīng)存在的朋友關(guān)系，虛線表示在區(qū)間之間形成的新朋友關(guān)系（新鏈接）。例如時(shí)刻，Dave和Bob是朋友，Dave和Cindy不是朋友。但是到了時(shí)刻，Dave和Cindy已經(jīng)成為了朋友，Eric和Alice也成為了朋友。

圖1 社交網(wǎng)絡(luò)中的鏈接預(yù)測(cè)

傳統(tǒng)的鏈接預(yù)測(cè)方法認(rèn)為任意用戶之間都可能形成新鏈接，即在所有時(shí)刻未鏈接的用戶都可能在時(shí)刻形成鏈接。它的做法是：計(jì)算所有在時(shí)刻未鏈接用戶之間的相似性，認(rèn)為相似性排名前k的用戶對(duì)在時(shí)刻會(huì)形成鏈接。

傳統(tǒng)鏈接預(yù)測(cè)的研究者們提出了很多優(yōu)秀的方法和模型，文獻(xiàn)［14］利用社交網(wǎng)絡(luò)的拓?fù)涮卣鱽?lái)預(yù)測(cè)用戶間的可信及不可信關(guān)系；文獻(xiàn)［12］提出通過捕獲信任的演化進(jìn)行鏈接預(yù)測(cè)的模型；在文獻(xiàn)［13］中作者設(shè)計(jì)因子圖方法針對(duì)跨異構(gòu)網(wǎng)絡(luò)的用戶進(jìn)行鏈接預(yù)測(cè)等等。

然而上述模型和算法幾乎都基于相似性分析或傳播分析，均沒有考慮用戶的收益變化，顯然這種做法是不合理的，社交網(wǎng)絡(luò)的用戶會(huì)自由選擇與哪些用戶形成鏈接，他們會(huì)考慮與其他用戶形成鏈接是否會(huì)為自己帶來(lái)收益的一系列問題。

在鏈接預(yù)測(cè)中引入博弈論的思想，就可以很恰當(dāng)?shù)亟鉀Q這一系列問題。基于博弈論的思想，用戶會(huì)有“條件”地進(jìn)行選擇，他們都是為了自身利益最大化，選擇與某些用戶形成鏈接，而拒絕與其他用戶形成鏈接。比如在圖1中，Dave在時(shí)刻只與Cindy形成鏈接，而沒有與Alice形成鏈接。

在基于博弈論解決鏈接預(yù)測(cè)的方法中，網(wǎng)絡(luò)形成博弈（NFG）與機(jī)器學(xué)習(xí)模型結(jié)合的方式［2］，是目前提高鏈接預(yù)測(cè)準(zhǔn)確度很有效的方法，其中很重要的一種模型是BPRLGT模型。

3.2 BPRLGT模型

文獻(xiàn)［2］提出了兩個(gè)利用網(wǎng)絡(luò)形成博弈提高鏈接預(yù)測(cè)準(zhǔn)確度的方法：其一，直接將博弈論結(jié)合到機(jī)器學(xué)習(xí)模型中；其二，將網(wǎng)絡(luò)形成博弈模型結(jié)合到貝葉斯排序框架中進(jìn)行鏈接預(yù)測(cè)。兩種方法的核心思想都是在現(xiàn)有的鏈接預(yù)測(cè)模型基礎(chǔ)上，考慮用戶自身收益的變化。

現(xiàn)有的鏈接預(yù)測(cè)模型及算法基本都基于相似性分析或者傳播分析，并以最大化預(yù)測(cè)準(zhǔn)確度為目標(biāo)。而網(wǎng)絡(luò)形成博弈是在當(dāng)前網(wǎng)絡(luò)中，沒有用戶可以通過建立新的鏈接來(lái)提高自身收益的假設(shè)下，以最大化用戶收益為目標(biāo)。因此在對(duì)兩個(gè)模型進(jìn)行結(jié)合時(shí)，存在以下三個(gè)問題：第一，大多數(shù)網(wǎng)絡(luò)形成博弈模型基于沒有用戶可以通過建立新的鏈接來(lái)提高自身收益的假設(shè)，分析現(xiàn)有網(wǎng)絡(luò)的形成，這個(gè)假設(shè)與鏈接預(yù)測(cè)沖突；第二，網(wǎng)絡(luò)形成博弈分析的目標(biāo)與鏈接預(yù)測(cè)目標(biāo)不一致；第三，目前沒有在訓(xùn)練模型時(shí)考慮用戶收益的鏈接預(yù)測(cè)模型。

為了解決上述三個(gè)問題，文獻(xiàn)［2］提出了以下解決方案，如圖2所示。

首先計(jì)算原始網(wǎng)絡(luò)中各用戶結(jié)點(diǎn)的收益；然后使用機(jī)器學(xué)習(xí)算法生成為原始網(wǎng)絡(luò)推薦的鏈接；最后計(jì)算加入推薦鏈接后的網(wǎng)絡(luò)中各用戶結(jié)點(diǎn)的收益。比較初始網(wǎng)絡(luò)G與加入新鏈接后的網(wǎng)絡(luò)G+｛eij｝中各結(jié)點(diǎn)的收益變化，對(duì)機(jī)器學(xué)習(xí)算法生成的推薦鏈接進(jìn)行重新排序，則得到最終的推薦鏈接列表。例如，對(duì)于用戶i，通過計(jì)算得到加入新鏈接后該用戶的收益變化為

圖2 算法流程圖

若Δi≥0，則eij是對(duì)用戶i有益的鏈接；若Δi≥0且Δj≥0，則eij為用戶i和用戶j之間的互惠鏈接。計(jì)算收益變化后，保留有益鏈接，懲罰推薦鏈接集合中雖排名在前但無(wú)法提高用戶收益的鏈接。通過這樣的方式達(dá)到向用戶推薦既是由鏈接預(yù)測(cè)模型推薦又可提高用戶收益鏈接的目的，從而提高了鏈接預(yù)測(cè)的準(zhǔn)確度。

上述方法將網(wǎng)絡(luò)形成博弈結(jié)合到機(jī)器學(xué)習(xí)模型中，但兩者是互相獨(dú)立的，即在訓(xùn)練機(jī)器學(xué)習(xí)模型時(shí)并未考慮網(wǎng)絡(luò)形成博弈，在機(jī)器學(xué)習(xí)模型進(jìn)行鏈接預(yù)測(cè)時(shí)也并未考慮用戶收益問題。為了使兩者更好的結(jié)合，作者［2］將網(wǎng)絡(luò)形成博弈模型與貝葉斯排序模型結(jié)合，提出了使用博弈論進(jìn)行鏈接預(yù)測(cè)的貝葉斯個(gè)性化排序模型（Bayesian Personalized Ranking for Link recommendation with Game Theory，BPRLGT）。BPRLGT模型以貝葉斯個(gè)性化排序框架為基礎(chǔ)，使用博弈理論進(jìn)行抽樣，將生成的訓(xùn)練數(shù)據(jù)用于模型訓(xùn)練，并考慮網(wǎng)絡(luò)拓?fù)涞挠绊憽Ｔ撃Ｐ突谟脩舾鼉A向于與朋友的朋友建立連接的假設(shè)，使用隨機(jī)梯度下降算法進(jìn)行學(xué)習(xí)。該模型選取樣本的流程如圖3所示。

圖3 BPRLGT樣本選取流程圖

如圖3所示BPRLGT采用博弈論的思想進(jìn)行樣本數(shù)據(jù)選取的核心為如果用戶j通過相似性計(jì)算推薦給u的概率很高，但是增加鏈接euj未提高u的收益，則通過最大化puk（u與k建立鏈接的概率）和puj（u與j建立鏈接的概率）的方式對(duì)j進(jìn)行懲罰。

在模型的學(xué)習(xí)過程中，BPRLGT不僅實(shí)現(xiàn)了觀測(cè)鏈接優(yōu)先順序的最大似然，而且考慮了每個(gè)用戶的收益。

為了驗(yàn)證BPRLGT模型的有效性，文獻(xiàn)［2］中作者使用Ciao，Epinions，COL和Facebook四個(gè)數(shù)據(jù)集，對(duì)現(xiàn)有的鏈接預(yù)測(cè)方法與結(jié)合BPRLGT的鏈接預(yù)測(cè)方法進(jìn)行了比較。結(jié)果表明，在多個(gè)度量標(biāo)準(zhǔn)中，結(jié)合BPRLGT模型的鏈接預(yù)測(cè)方法比現(xiàn)有的鏈接預(yù)測(cè)方法的準(zhǔn)確度高。同時(shí)，與BPRLGT相比，結(jié)合BPR模型的鏈接預(yù)測(cè)方法在部分?jǐn)?shù)據(jù)集上效果較差，原因是BPR在訓(xùn)練數(shù)據(jù)的選取時(shí)采用的是均值采樣，并未考慮網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。

3.3 小結(jié)

文獻(xiàn)［2］結(jié)合博弈論的思想進(jìn)行鏈接預(yù)測(cè)，為我們提供了一個(gè)新的研究方向。無(wú)論是鏈接預(yù)測(cè)還是好友推薦，或是異構(gòu)信息網(wǎng)絡(luò)中的推薦應(yīng)用，都可以加入博弈論的思想進(jìn)行分析。

網(wǎng)絡(luò)形成博弈通常用來(lái)分析用戶在社交網(wǎng)絡(luò)中建立鏈接時(shí)的判斷力，其最核心的部分是效益函數(shù)，該函數(shù)可以解釋當(dāng)前網(wǎng)絡(luò)的形成原因。不同的效益函數(shù)構(gòu)成了不同的網(wǎng)絡(luò)形成博弈模型，也就使得用戶通過彼此之間的鏈接可以建立不同的網(wǎng)絡(luò)結(jié)構(gòu)。而網(wǎng)絡(luò)形成博弈的目的就是通過效益函數(shù)分析網(wǎng)絡(luò)在達(dá)到納什平衡的過程中，其中用戶所獲得的效益。首先，結(jié)合網(wǎng)絡(luò)形成博弈，可以提出不同的收益函數(shù)分析結(jié)點(diǎn)收益的變化情況。通過各結(jié)點(diǎn)的收益變化情況，我們可以進(jìn)一步對(duì)社交網(wǎng)絡(luò)結(jié)構(gòu)的變化進(jìn)行分析。除此之外，結(jié)合上下文語(yǔ)義與網(wǎng)絡(luò)形成模型來(lái)進(jìn)行鏈接預(yù)測(cè)也是一個(gè)很有意義的研究方向。再進(jìn)一步，將博弈論與其它機(jī)器學(xué)習(xí)模型，如馬爾科夫決策過程，融合也是未來(lái)一個(gè)有意義的研究點(diǎn)。

4 社團(tuán)演化中的博弈論

4.1 社團(tuán)演化

社交網(wǎng)絡(luò)是一種典型的復(fù)雜網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)是這樣定義的：具有自組織、自相似、吸引子、小世界、無(wú)標(biāo)度中部分或全部性質(zhì)的網(wǎng)絡(luò)稱之為復(fù)雜網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)是一種呈現(xiàn)高度復(fù)雜性的網(wǎng)絡(luò)，其特點(diǎn)主要有：

小世界特性：小世界特性被稱之為六度空間理論或者是六度分割理論，小世界特性指出：社交網(wǎng)絡(luò)中任何一個(gè)成員和任何一個(gè)陌生人之間所間隔的人不會(huì)超過六個(gè)。

無(wú)標(biāo)度特性：現(xiàn)實(shí)世界的大部分網(wǎng)絡(luò)都不是隨機(jī)網(wǎng)絡(luò)，極少數(shù)的節(jié)點(diǎn)往往擁有大量的連接，大部分的節(jié)點(diǎn)連接數(shù)都比較稀少，節(jié)點(diǎn)度數(shù)符合冪律分布。節(jié)點(diǎn)度分布符合冪律分布的復(fù)雜網(wǎng)絡(luò)稱之為無(wú)標(biāo)度網(wǎng)絡(luò)。

社團(tuán)結(jié)構(gòu)特性：社團(tuán)結(jié)構(gòu)是指整個(gè)網(wǎng)絡(luò)是由若干個(gè)“群（Group）”或“團(tuán)（Cluster）”構(gòu)成的。例如社會(huì)網(wǎng)絡(luò)中的朋友圈，其中每個(gè)成員都認(rèn)識(shí)其他成員。每個(gè)群的內(nèi)部節(jié)點(diǎn)之間的連接相對(duì)比較緊密，但是各個(gè)群之間的連接卻比較稀疏［8］。

其中網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的演化性是社交網(wǎng)絡(luò)的一個(gè)重要特性。用戶（網(wǎng)絡(luò)節(jié)點(diǎn)）的興趣、角色、社會(huì)地位等因素隨時(shí)間不斷地變化引起網(wǎng)絡(luò)結(jié)構(gòu)隱式地變化。與此同時(shí)，社團(tuán)結(jié)構(gòu)的改變也反過來(lái)影響著用戶的興趣、角色、社會(huì)地位。

社團(tuán)演化問題的研究由來(lái)已久，目前主流的研究方法分為兩類：獨(dú)立聚類和演化聚類。獨(dú)立聚類是對(duì)動(dòng)態(tài)網(wǎng)絡(luò)按時(shí)間取一系列網(wǎng)絡(luò)狀態(tài)，每個(gè)網(wǎng)絡(luò)狀態(tài)就是該時(shí)刻網(wǎng)絡(luò)的一個(gè)快照，然后將社團(tuán)發(fā)現(xiàn)算法分別應(yīng)用于每個(gè)網(wǎng)絡(luò)快照。比較不同時(shí)刻的社團(tuán)，便可以定義并發(fā)現(xiàn)社團(tuán)增長(zhǎng)、收縮、合并、分裂、產(chǎn)生和消失等社團(tuán)演化事件［7］。演化聚類方法通過考慮網(wǎng)絡(luò)演化的時(shí)間信息，確保社團(tuán)結(jié)構(gòu)在連續(xù)時(shí)間戳上的平滑性，該方法可以克服社團(tuán)發(fā)現(xiàn)算法或網(wǎng)絡(luò)噪聲帶來(lái)的隨機(jī)性問題［15～23］。

4.2 經(jīng)典博弈論與演化博弈論

經(jīng)典博弈論基于兩個(gè)假設(shè)：一是參與者完全理性，即參與者對(duì)自己和對(duì)手的策略以及不同策略組合下的收益函數(shù)都有明確的認(rèn)知；二是參與者有共同的共識(shí)，所有的參與者都知道其他參與者是完全理性的。在這兩個(gè)假設(shè)下參與者會(huì)追求自身利益的最大化。典型的例子就是囚徒困境博弈。

演化博弈論是基于現(xiàn)實(shí)社會(huì)中，個(gè)體不可能是完全理性的（有限理性）這個(gè)前提，它認(rèn)為個(gè)體通過不斷吸取經(jīng)驗(yàn)來(lái)調(diào)整自己的策略以適應(yīng)環(huán)境。演化博弈論是經(jīng)典博弈論由完全理性轉(zhuǎn)向有限理性的進(jìn)化過程中產(chǎn)生的一種研究手段，放寬了經(jīng)典博弈論中完全理性假設(shè)的限制，參與博弈的對(duì)象不再是確定的。而且博弈的過程不再是經(jīng)典博弈論中的一次博弈，而是會(huì)發(fā)生多次，即動(dòng)態(tài)演化，這也為經(jīng)典博弈論中出現(xiàn)多個(gè)納什均衡點(diǎn)而無(wú)法收斂的情況提供了一種更有效的方法［24］。

4.3 社團(tuán)演化與博弈論

社團(tuán)演化是社交網(wǎng)絡(luò)研究的傳統(tǒng)方向，針對(duì)這個(gè)問題的研究已趨于成熟，但從博弈論的角度，分析用戶在社團(tuán)演化過程中所獲利益變化情況的研究還較少。在社團(tuán)演化領(lǐng)域中融入演化博弈論，思路是將網(wǎng)絡(luò)中的節(jié)點(diǎn)認(rèn)為是博弈的參與者，節(jié)點(diǎn)之間的邊看作是參與者之間的關(guān)系，博弈發(fā)生在有邊的參與者（節(jié)點(diǎn)）之間。網(wǎng)絡(luò)演化的過程是：首先，節(jié)點(diǎn)隨機(jī)選擇鄰居節(jié)點(diǎn)進(jìn)行博弈并獲得收益；其次，節(jié)點(diǎn)會(huì)根據(jù)收益值進(jìn)行博弈學(xué)習(xí)，同時(shí)調(diào)整網(wǎng)絡(luò)結(jié)構(gòu)。不斷執(zhí)行這兩個(gè)過程，直至達(dá)到平衡狀態(tài)。演化博弈主要涉及三個(gè)要素：網(wǎng)絡(luò)模型，博弈模型和策略更新規(guī)則。

一般的網(wǎng)絡(luò)博弈研究中，網(wǎng)絡(luò)結(jié)構(gòu)是靜態(tài)不變的。近年來(lái)，人們逐步關(guān)注在演化博弈論的影響下，網(wǎng)絡(luò)結(jié)構(gòu)是如何發(fā)生變化的。Zimmermann等提出了一個(gè)動(dòng)態(tài)網(wǎng)絡(luò)囚徒困境博弈模型［25］；Li等提出了一種由演化博弈驅(qū)動(dòng)生成的無(wú)標(biāo)度網(wǎng)絡(luò)型［26］；Helbing等提出成功驅(qū)動(dòng)的博弈模型［27］。

文獻(xiàn)［3］提出了在異構(gòu)信息網(wǎng)絡(luò)中利用博弈論進(jìn)行社團(tuán)演化聚類的框架：GHIN，該框架將異構(gòu)信息網(wǎng)絡(luò)中結(jié)點(diǎn)的不同類型作為博弈論中的一個(gè)玩家，將每一個(gè)聚類結(jié)果作為一個(gè)納什平衡點(diǎn)。經(jīng)過實(shí)驗(yàn)證明，該框架的聚類效果比一些著名的聚類算法都要好，該框架的特點(diǎn)是聚類結(jié)果依賴于當(dāng)前網(wǎng)絡(luò)結(jié)構(gòu)的回報(bào)函數(shù)。其算法流程如圖4所示。

圖4 GHIN算法流程圖

4.4 小結(jié)

結(jié)合博弈論進(jìn)行社團(tuán)演化分析，使得演化的發(fā)生可以有效地解釋。我們認(rèn)為網(wǎng)絡(luò)的演化本質(zhì)上是結(jié)點(diǎn)間邊的變化，而邊的變化必定影響結(jié)點(diǎn)的收益，同時(shí)假設(shè)社交網(wǎng)絡(luò)中的點(diǎn)都是有限理性的，每個(gè)點(diǎn)都以自身利益最大化為目標(biāo)，基于上述兩點(diǎn)，首先要定義衡量結(jié)點(diǎn)收益及社團(tuán)收益的權(quán)值函數(shù)，以此作為收益，并以網(wǎng)絡(luò)趨向于利益最大化的方向發(fā)展為基本假設(shè)，分析網(wǎng)絡(luò)中鏈接的變化過程，直至網(wǎng)絡(luò)到達(dá)納什平衡狀態(tài)。主要思路如圖5所示。

圖5 分析流程圖

5 結(jié)語(yǔ)

博弈論所研究的是理性的決策者之間沖突及合作的理論，可以為實(shí)際決策提供理論基礎(chǔ)和方向指導(dǎo)。其最終追求結(jié)果是使博弈方達(dá)到利益最大化的均衡。在生活中，博弈仍然無(wú)處不在。博弈論代表著一種全新的分析方法和全新的思想，而我們所在的現(xiàn)實(shí)及網(wǎng)絡(luò)世界，利益分析無(wú)處不在，結(jié)合博弈論進(jìn)行社交網(wǎng)絡(luò)分析是一個(gè)合理并新穎的思路。

本文概述了博弈論在鏈接預(yù)測(cè)，聚類等方向的應(yīng)用。在社交網(wǎng)絡(luò)中博弈論運(yùn)用的核心為，將用戶在社交網(wǎng)絡(luò)中的行為看做博弈的過程，同時(shí)考慮每個(gè)用戶均以個(gè)人利益最大化為目標(biāo)。因此，無(wú)論是鏈接預(yù)測(cè)，推薦系統(tǒng)或是社團(tuán)形成，其本質(zhì)都是在個(gè)體利益最大化過程中達(dá)到的尋找博弈過程中達(dá)到的整體利益均衡狀態(tài)，這為我們提供了一個(gè)新穎而有潛力的研究新思路。

除了本文介紹的博弈論在鏈接預(yù)測(cè)、聚類和網(wǎng)絡(luò)形成分析的應(yīng)用，博弈論在異構(gòu)信息網(wǎng)絡(luò)中還有其他巨大的價(jià)值等待研究者去挖掘與探索。如，在較為成熟的機(jī)器學(xué)習(xí)模型中加入博弈論的思想來(lái)提高模型效率或準(zhǔn)確率。又如，結(jié)合博弈論的思想和傳統(tǒng)的網(wǎng)絡(luò)演化動(dòng)力學(xué)模型來(lái)分析異構(gòu)信息網(wǎng)絡(luò)的演化過程，進(jìn)行預(yù)測(cè)社群演化。綜上所述，博弈論在數(shù)據(jù)挖掘研究領(lǐng)域具有巨大的研究?jī)r(jià)值，這也為研究者們提供了一個(gè)新穎的、有潛力的研究方向。

［1］Jackson M O，Zenou Y.Games on networks［J］.Handbook of game theory，2014（4）：1-89.

［2］Zhao T，Zhao H V，King I.Exploiting Game Theoretic Analysis for Link Recommendation in Social Networks［C］//ACM International Conference on Information Management，2015：851-860.

［3］Alqadah F，Bhatnagar R.A game theoretic framework for heterogenous information network clustering［C］//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2011：795-804.

［4］Yang Z，Chen W.A Game Theoretic Model for the Formation of Navigable Small-World Networks［C］//International Conference on World Wide Web，2015：1329-1339.

［5］Jackson M O.A survey of network formation models：stability and efficiency［J］.Group Formation in Economics：Networks，Clubs，and Coalitions，2005，11-49.

［6］吳枝喜，榮智海，王文旭.復(fù)雜網(wǎng)絡(luò)上的博弈［J］.力學(xué)進(jìn)展，2008，38（6）：794-804.

WU Zhixi，RONG Zhihai，WANG Wenxu.Games on Complex Networks［J］.Advances in Mechanics，2008，38（6）：794-804.

［7］劉群，易佳.基于演化博弈的社交網(wǎng)絡(luò)模型演化研究［J］.物理學(xué)報(bào)，2013，（23）：463-471.

LIU Qun，YI Jia.The research of the social network evolution based on the evolutionary game theory［J］.Acta Physica Sinica，2013，（23）：463-471.

［8］王龍，伏鋒，陳小杰，等.復(fù)雜網(wǎng)絡(luò)上的演化博弈［J］.智能系統(tǒng)學(xué)報(bào)，2007，（2）：1-10.

WANG Long，F(xiàn)U Feng，CHEN Xiaojie，et al.Evolutionary games on complex networks［J］.CAAI Transactions on Intelligent Systems，2007，（2）：1-10.

［9］Watts D J.Six Degree：The Science of a Connected Age［M］.New York：Norton，2003.

［10］WattsDJ，StrogatzSH.Colectivedynamicsof small-world networks［J］.Nature，1998，393：440-442.

［11］Watts D J.Small Worlds：The Dynamics of Newtorks Between Order and Randomness［M］.New Jersey：Princeton University Press，1999.

［12］J.Tang，H.Gao，H.Liu，A.D.Sarma.eTrust：Understanding trust evolution in an online world［C］.New York，NY：ACM.2012.253-261.

［13］Y.Dong，J.Tang，S.Wu，J.Tian，et al.Link prediction and recommendation across heterogenous social networks［C］.Piscataway，NJ：IEEE.2012.181-190.

［14］J.Leskovec，D.Huttenlocher，J.Kleinberg.Predicting positive and negative links in online social networks［C］.Berlin，German：Springer.2010.

［15］Chakrabarti D，Kumar R，Tomkins A.Evolutionary clustering［C］.New York，NY：ACM.2006.554-560.

［16］Chi Y，Song X，Zhou D，et al.Evolutionary spectral clustering by incorporating temporal smoothness［C］. New York，NY：ACM.2007.153-162.

［17］Sarkar P，Moore A W.Dynamic social network analysis using latent space models［J］.ACM SIGKDD Explorations Newsletter，2005，7（2）：31-40.

［18］Lin Y R，Chi Y，Zhu S，et al.Facetnet：a framework for analyzing communities and their evolutions in dynamic networks［C］.New York，NY：ACM.2008.685-694.

［19］Yang T，Chi Y，Zhu S，et al.Detecting communities and their evolutions in dynamic social networks—a Bayesian approach［J］.Machine learning，2011，82（2）：157-189.

［20］Yang T，Chi Y，Zhu S，et al.A Bayesian Approach Toward Finding Communities and Their Evolutions in Dynamic Social Networks［C］.Philadelphia：SIAM.2009. 990-1001.

［21］Lin Y R，Sun J，Cao N，et al.Contextour：Contextual contour visual analysis on dynamic multi-relational clustering［C］.Philadelphia：SIAM.2010.418-429.

［22］Tantipathananandh C，Berger-Wolf T，Kempe D.A framework for community identification in dynamic social networks［C］.New York，NY：ACM.2007.717-726.

［23］Kim M S，Han J.A particle-and-density based evolutionary clustering method for dynamic networks［J］.Proceedings of the VLDB Endowment，2009，2（1）：622-633.

［24］侯彩芳.基于偏好的博弈學(xué)習(xí)與復(fù)雜網(wǎng)絡(luò)的共演化機(jī)制的研究［D］.長(zhǎng)春：吉林大學(xué)，2016.

HOU Caifang.The Research of Co-Evolution Mechanism Between Complex Networks and Game Learning Based on Individual Preference［D］.Changchun：JILIN University，2016.

［25］Zimmermann M G，Eguíluz V M，San Miguel M.Coevolution of dynamical states and interactions in dynamic networks［J］.Physical Review E，2004，69（6）：065102.

［26］Li W，Zhang X，Hu G.How scale-free networks and large-scale collective cooperation emerge in complex homogeneous social systems［J］.Physical Review E，2007，76（4）：045102.

［27］Helbing D，Yu W.The outbreak of cooperation among success-driven individuals under noisy conditions［J］. Proceedings of the National Academy of Sciences，2009，106（10）：3680-3685.

Application of Game Theory in Social Networks

DAI Xiang
（Southwest China Institute of Electronic Technology，Chengdu610036）

The rapid development of online social networks has attracted great research interests in different fields.In Economics，researchers use game theory to analyze the mechanism of network formation which explains the reason of network formation，called network formation game.While in computer science，many mature algorithms and models have been proposed by researchers for community formation，link prediction，recommendation system etc.We mainly use these models and algorithms to recommend friends to users.Combing game theory with link prediction is of great significance to research on link prediction based on utility maximization theory.This article summarizes some achievements about the application of game theory in the study of link prediction and community formation in social networks，and demonstrates the meaning of game theory in network evolution.

social networks，game theory，link prediction，network evolution

TP311

10.3969/j.issn.1672-9722.2017.06.024

2016年12月3日，

2017年1月19日

國(guó)家自然科學(xué)基金項(xiàng)目（編號(hào)：61173099，61103043）資助。

代翔，男，博士，工程師，研究方向：自然語(yǔ)言處理、數(shù)據(jù)挖掘等。