通過影響網(wǎng)絡(luò)中的正影響支配集(Positive Influence Dominating Set,簡稱為PIDS)可以有效的引導(dǎo)社交網(wǎng)絡(luò)中的輿論,培養(yǎng)社會風(fēng)氣。對于許多社會問題例如抽煙、酗酒等,都有很大的實際意義。對于網(wǎng)絡(luò)中的一個節(jié)點子集來說,如果網(wǎng)絡(luò)中的所有節(jié)點都有半數(shù)以上的鄰居節(jié)點處于該子集中,那么這樣的節(jié)點子集就是該網(wǎng)絡(luò)的一個PIDS。連通正影響支配集(Connected Positive Influence Dominating Set,簡稱為CPIDS)即在正影響支配集的基礎(chǔ)上,進(jìn)一步要求支配集內(nèi)部連通。目前已有許多關(guān)于PIDS的研究,但其中的大部分方法計算量大,時間復(fù)雜度高,因此難以適用于大型的社交網(wǎng)絡(luò)。在本文中,針對一些已有方法的不足,我們提出了一種高效的啟發(fā)式算法TBCM來構(gòu)建大規(guī)模社交網(wǎng)絡(luò)中的CPIDS。文中實驗結(jié)果表明,本文提出的TBCM算法在運(yùn)行時間上優(yōu)于現(xiàn)有的大規(guī)模網(wǎng)絡(luò)算法。并且,考慮到正影響支配集在網(wǎng)絡(luò)中占比較大,難以應(yīng)用到實際的社交網(wǎng)絡(luò)中,本文提出了將影響力最大化問題應(yīng)用在網(wǎng)絡(luò)中的CPIDS的想法,設(shè)計了基于網(wǎng)絡(luò)中CPIDS的兩步影響力傳播算法LIBH,在得... 

【文章來源】：哈爾濱工業(yè)大學(xué)黑龍江省 211工程院校 985工程院校

【文章頁數(shù)】：62 頁

【學(xué)位級別】：碩士

【部分圖文】：

算法[25]在BA-250以及BA-300網(wǎng)絡(luò)中的運(yùn)行效果1)BA-2502)BA-300

ER-1024 786.0 76.75% 55.55 0.67 15000WS-256 231.1 90.23% 20.296 0.36 15000WS-512 430 83.98% 39.46 0.53 15000WS-1024 790.8 77.22% 77.70 0.66 15000Karate 31 91.17% 0.70<0.1 4292Dolphins 56.7 91.45% 2.27<0.1 10504Football 110 95.65% 7.15 0.16 15000Science 1152.3 78.87% 63.53 0.73 15000a)ER網(wǎng)絡(luò)中PIDS占比結(jié)果 b)BA網(wǎng)絡(luò)中PIDS占比結(jié)果

c)各算法在WS網(wǎng)絡(luò)中的運(yùn)行時間 d)各算法在實際網(wǎng)絡(luò)中的運(yùn)行時間圖3-10 TBCM算法不同數(shù)據(jù)集上剪枝效果TBCM算法在時間運(yùn)行方面具有更大的優(yōu)勢。圖3-10中，顯示了三種算法在不同數(shù)據(jù)集上的運(yùn)行時間�？梢钥闯觯鱾�算法的運(yùn)行時間都隨著網(wǎng)絡(luò)規(guī)模變大而增加，雖然Wang-Greedy算法在解集上優(yōu)于SSA算法，但其在實際網(wǎng)絡(luò)中運(yùn)行時間過長，難以應(yīng)用于實際的大規(guī)模網(wǎng)絡(luò)中。例如對于真實網(wǎng)絡(luò)數(shù)據(jù)集中的Astrophysics網(wǎng)絡(luò)以及Email-Enron網(wǎng)絡(luò)，在這兩個數(shù)據(jù)集中Wang-Greedy的運(yùn)行時間均超過10,000秒，因此在圖3-10d)中并未顯示該算法在這兩個數(shù)據(jù)集上的運(yùn)行時間。由于三種算法在運(yùn)行時間方面差異過大，因此在實驗結(jié)果圖中，我們選擇以指數(shù)坐標(biāo)來顯示算法的運(yùn)行時間，但是仍然可以看出TBCM算法明顯優(yōu)于另外兩種算法。這表明TBCM算法相對于另外兩種算法來說更具有實際的應(yīng)用價值。例如，在ego-Facebook數(shù)據(jù)集中，TBCM的運(yùn)行時間僅為10.79秒，而在相同數(shù)據(jù)集上，SSA的運(yùn)行時間為108.90秒，Wang-Greedy的運(yùn)行時間為3205.45秒�？梢钥闯�，文章中提出的TBCM算法在運(yùn)行時間上與其他對比算法相比有較大的優(yōu)勢。

【參考文獻(xiàn)】：
期刊論文
[1]基于啟發(fā)式和貪心策略的社交網(wǎng)絡(luò)影響最大化算法[J]. 曹玖新,閔繪宇,徐順,劉波.  東南大學(xué)學(xué)報(自然科學(xué)版). 2016(05)
[2]社交網(wǎng)絡(luò)中求最小正影響支配集的改進(jìn)算法[J]. 麥飛,陳衛(wèi)東.  華南師范大學(xué)學(xué)報(自然科學(xué)版). 2016(03)
[3]國內(nèi)在線社交網(wǎng)絡(luò)群體行為研究現(xiàn)狀與展望[J]. 孫國強(qiáng),石文萍,王莉.  現(xiàn)代情報. 2016(02)
[4]網(wǎng)絡(luò)拓?fù)涮卣鲗Σ《臼綘I銷傳播動態(tài)影響的研究——基于新浪微博大數(shù)據(jù)的實證分析[J]. 陸煊,江若塵.  新聞與傳播研究. 2014(10)
[5]復(fù)雜網(wǎng)絡(luò)中節(jié)點重要性排序的研究進(jìn)展[J]. 劉建國,任卓明,郭強(qiáng),汪秉宏.  物理學(xué)報. 2013(17)
[6]基于閾值的社交網(wǎng)絡(luò)影響力最大化算法[J]. 陳浩,王軼彤.  計算機(jī)研究與發(fā)展. 2012(10)
[7]一種新型的社會網(wǎng)絡(luò)影響最大化算法[J]. 田家堂,王軼彤,馮小軍.  計算機(jī)學(xué)報. 2011(10)



本文編號：2937809