社交網(wǎng)絡(luò)鏈接預(yù)測(cè)——博弈論和網(wǎng)絡(luò)拓?fù)涞囊暯?pdf

1、社交網(wǎng)絡(luò)是人們分享信息和相互交流的重要途徑，通過(guò)分析和挖掘社交網(wǎng)絡(luò)數(shù)據(jù)，可獲得大量有價(jià)值的商業(yè)和社會(huì)行為信息。鏈接預(yù)測(cè)是社交網(wǎng)絡(luò)分析和挖掘中的核心問題之一，其旨在預(yù)測(cè)網(wǎng)絡(luò)鏈接的出現(xiàn)，對(duì)理解社交網(wǎng)絡(luò)的動(dòng)態(tài)演化過(guò)程具有重要作用。然而，現(xiàn)有鏈接預(yù)測(cè)方法主要利用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息進(jìn)行問題分析和建模，雖然這些方法簡(jiǎn)單高效，但沒有考慮社交網(wǎng)絡(luò)中用戶的理性選擇，存在著預(yù)測(cè)結(jié)果可解釋性不強(qiáng)的缺點(diǎn)。本文首次將博弈論思想引入鏈接預(yù)測(cè)研究領(lǐng)域，將網(wǎng)絡(luò)中的用戶看

2、作博弈參與人，用戶間的交互狀態(tài)（有鏈接和無(wú)鏈接）看作用戶的策略選擇，研究用戶的理性策略選擇，即在他人選擇既定的情況下，如何使自己利益最大化的最優(yōu)反應(yīng)。此方法能更好地解釋社交活動(dòng)中用戶理性選擇鏈按的過(guò)程，彌補(bǔ)了經(jīng)典方法得到的預(yù)測(cè)結(jié)果可解釋性差的缺點(diǎn)，是對(duì)現(xiàn)有鏈接預(yù)測(cè)研究思路的一項(xiàng)重要補(bǔ)充。本文的主要研究工作如下:
　　(1)提出一種基于博弈論的鏈接預(yù)測(cè)模型:將社交網(wǎng)絡(luò)中的用戶看作是博弈的參與人，將用戶潛在的鏈接用戶集合作為博弈的策略

3、，用戶根據(jù)策略來(lái)獲得其博弈的收益。從而構(gòu)造了一個(gè)非合作博弈模型，并利用演化法對(duì)該博弈模型進(jìn)行求解。
　　(2)提出一種基于節(jié)點(diǎn)的鏈接預(yù)測(cè)博弈方法NGLP:該方法從節(jié)點(diǎn)的角度考慮，根據(jù)多數(shù)鏈接形成受路徑距離影響現(xiàn)象，得到每個(gè)節(jié)點(diǎn)的鏈接候選節(jié)點(diǎn)集合，節(jié)點(diǎn)的策略為其鏈接候選節(jié)點(diǎn)集合的冪集，并引入局部網(wǎng)絡(luò)拓?fù)湫畔⑦M(jìn)行收益計(jì)算，節(jié)點(diǎn)根據(jù)“收益最大化”的原則獨(dú)立決策自己的最佳應(yīng)對(duì)策略，并在納什均衡求解中證明在一定條件下該博弈為勢(shì)能博弈。

4、>　　(3)提出一種基于邊的鏈接預(yù)測(cè)博弈方法EGLP:該方法從邊的角度考慮，將社交網(wǎng)絡(luò)中多人博弈近似成多矩陣博弈，即多個(gè)兩人博弈的集合;網(wǎng)絡(luò)中節(jié)點(diǎn)通過(guò)邊與其鄰居進(jìn)行博弈，并利用網(wǎng)絡(luò)拓?fù)湫畔⒌玫焦?jié)點(diǎn)部分福利，用戶收益為多次與鄰居博弈所得部分福利之和減去維護(hù)鏈接所需開銷，節(jié)點(diǎn)根據(jù)“收益最大化”原則獨(dú)立決策自己的最佳應(yīng)對(duì)策略，并在納什均衡求解中證明在一定條件下該博弈為勢(shì)能博弈。
　　(4)提出了一種基于拓?fù)浣Y(jié)構(gòu)的收益方法:該方法先利用軌

5、道向量記錄節(jié)點(diǎn)周圍拓?fù)浣Y(jié)構(gòu)信息，然后根據(jù)各軌道占比設(shè)置相應(yīng)的權(quán)重值，得到網(wǎng)絡(luò)的權(quán)力向量，最后將節(jié)點(diǎn)的軌道向量與權(quán)力向量做內(nèi)積計(jì)算，得到節(jié)點(diǎn)的收益。相比簡(jiǎn)單的收益方法，該方法能更全面和真實(shí)地描述節(jié)點(diǎn)在網(wǎng)絡(luò)中的收益。
　　(5)提出了一種新的博弈結(jié)果過(guò)濾方法Gharmony，該方法通過(guò)計(jì)算用戶之間的相似性，合理過(guò)濾掉大量博弈結(jié)果，解決了可能出現(xiàn)的“博弈解的個(gè)數(shù)遠(yuǎn)大于測(cè)試集大小”的問題。在上述工作基礎(chǔ)上，實(shí)現(xiàn)了基于博弈論的鏈接預(yù)測(cè)系統(tǒng)，