基于結(jié)構(gòu)洞理論的影響最大化算法的研究.pdf

1、互聯(lián)網(wǎng)技術(shù)的發(fā)展推動了各種社交網(wǎng)絡(luò)（Facebook，Twitter，新浪微博等）的蓬勃發(fā)展，社會網(wǎng)絡(luò)中豐富的信息數(shù)據(jù)的挖掘以及通過社會網(wǎng)絡(luò)進行的營銷活動都給社會網(wǎng)絡(luò)的研究帶來了前所未有的挑戰(zhàn)和機遇。網(wǎng)絡(luò)營銷是基于個人通過社會關(guān)系對周圍朋友，家人或者同事進行影響力擴散而產(chǎn)生的“口碑”營銷模式，在影響力擴散過程中，挖掘社會網(wǎng)絡(luò)中最有影響力的用戶變得十分關(guān)鍵。在這個背景下，影響最大化問題的研究變得炙手可熱。影響最大化問題就是從社會網(wǎng)絡(luò)中選出

2、少量節(jié)點作為種子節(jié)點，從種子節(jié)點開始傳播，在社會網(wǎng)絡(luò)中獲得最大的影響收益。
　　目前已經(jīng)提出很多社交網(wǎng)絡(luò)中的影響最大化算法，例如各種貪心算法，啟發(fā)式算法等，目的都是降低影響最大化算法的時間開銷，提高算法的結(jié)果精度。然而，現(xiàn)有算法中鮮有考慮社會網(wǎng)絡(luò)中節(jié)點的結(jié)構(gòu)特征，例如結(jié)構(gòu)洞節(jié)點具有鮮明的結(jié)構(gòu)特征，與普通節(jié)點相比傳播能力更強。忽略節(jié)點的結(jié)構(gòu)特征的影響最大化算法的結(jié)果精度不夠理想，而且利用結(jié)構(gòu)特征可以有效的降低算法的時間開銷。

3、　　針對上述影響最大化研究中的挑戰(zhàn)和問題，本文從以下兩個方面進行研究:
　　(1)研究基于結(jié)構(gòu)洞理論的影響最大化算法。提出SG(Structure-based Greedy)算法降低影響最大化算法的時間開銷，改善影響傳播范圍。SG算法的基本思想是為原始社會網(wǎng)絡(luò)建立拉普拉斯矩陣，通過求解費德勒向量確定結(jié)構(gòu)洞節(jié)點。本文綜合考慮節(jié)點的結(jié)構(gòu)特征和影響力，采用過濾的方式篩除非結(jié)構(gòu)洞節(jié)點和影響力特別小的節(jié)點，縮小種子選取的候選集空間。在縮小的

4、候選集中貪心的選取能夠獲得最大傳播范圍的種子節(jié)點。本文通過實驗驗證，本文提出的基于結(jié)構(gòu)洞理論的影響最大化算法和現(xiàn)有算法相比，在算法時間開銷和算法結(jié)果質(zhì)量方面都具有明顯的優(yōu)勢。
　　(2)研究高效的結(jié)構(gòu)洞發(fā)現(xiàn)算法和社團劃分的關(guān)系。已有的結(jié)構(gòu)洞發(fā)現(xiàn)算法主要開銷在于計算節(jié)點的結(jié)構(gòu)洞值，在大規(guī)模社交網(wǎng)絡(luò)中，結(jié)構(gòu)洞值的計算開銷相當可觀。本文提出借助社團劃分的思想降低結(jié)構(gòu)洞值的計算開銷。首先將原始社會網(wǎng)根據(jù)節(jié)點的相似度進行粗糙劃分得到簡單社團

5、結(jié)構(gòu)，然后根據(jù)社團結(jié)構(gòu)確定結(jié)構(gòu)洞節(jié)點，最后計算結(jié)構(gòu)洞節(jié)點與已有社團的相似度值作為節(jié)點的結(jié)構(gòu)洞值。此外，在已知社會網(wǎng)結(jié)構(gòu)洞節(jié)點的前提下，本文提出基于“二步”信息流理論的新的社團劃分方法SCD（Structure-based Community Detection）。SCD算法的基本思想是首先將原始的社會網(wǎng)根據(jù)節(jié)點相似度獲得粗糙社團結(jié)構(gòu)，然后在粗糙社團中確定網(wǎng)絡(luò)中的結(jié)構(gòu)洞節(jié)點，最后從結(jié)構(gòu)洞節(jié)點出發(fā)，根據(jù)“二步”信息流理論檢測潛在社團，根據(jù)潛