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

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

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

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

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