發(fā)布時(shí)間：2020-12-13 19:48

　　近年來,隨著網(wǎng)絡(luò)技術(shù)的不斷完善,社交網(wǎng)絡(luò)得到了迅猛的發(fā)展,如CSDN、BLOG、Weibo等。隨著信息的高速傳播,影響最大化問題成為社交網(wǎng)絡(luò)中的熱門研究話題。影響最大化的研究對市場營銷、廣告宣傳以及輿情控制等方面具有重要意義。Kempe首次證明了影響最大化是NP-hard問題,并提出了貪心算法。貪心算法能夠達(dá)到（1-1/e）的近似最優(yōu),但其計(jì)算開銷巨大,不能適用于大型網(wǎng)絡(luò)。啟發(fā)式方法,能夠快速地找出種子集合,但是不能保證影響的傳播范圍�；旌鲜剿惴ú捎脝�發(fā)式和貪心相結(jié)合的方式,有效的解決了貪心算法的時(shí)間開銷問題。在啟發(fā)階段,混合式算法利用節(jié)點(diǎn)鄰域信息選取最具"潛力"節(jié)點(diǎn),這些節(jié)點(diǎn)能積累大量的影響力使得周圍未激活的節(jié)點(diǎn)更容易被激活;在貪心階段,大量的節(jié)點(diǎn)已被激活或者更容易被激活,從而貪心的時(shí)間開銷得到了大幅度的降低。但是,如何選取最有潛力節(jié)點(diǎn)以及怎樣加快貪心尋找,仍然是一個(gè)待解決的問題。針對以上問題,本文提出了基于H階鄰居的混合式算法,旨在擴(kuò)大最終的傳播范圍的同時(shí),減少算法的時(shí)間復(fù)雜度�；�于H階鄰居的混合式算法同樣采用兩個(gè)階段實(shí)現(xiàn)種子節(jié)點(diǎn)的選取:啟發(fā)階段和貪心階段。在啟發(fā)階段,由于大型社交... 

【文章來源】：大連海事大學(xué)遼寧省 211工程院校

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

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

【部分圖文】：

圖１．１用圖來表示的社交網(wǎng)絡(luò)??Ｆｉｇ．?１．１?Ａ?ｓｏｃｉａｌ?ｎｅｔｗｏｒｋ?ｄｅｐｉｃｔｅｄ?ｂｙ?ａ?ｇｒａｐｈ??網(wǎng)絡(luò)影響力最大化研有著十分重要的現(xiàn)實(shí)意義，并且己在多個(gè)領(lǐng)

圖３．１節(jié)點(diǎn)Ｖ的鄰接圖??Ｆｉｇ．?３．１?Ａｄｊａｃｅｎｔ?ｇｒａｐｈ?ｏｆ?ｎｏｄｅ?ｖ??

（ａ）?（ｂ）??圖３．２節(jié)點(diǎn)的兩階出邊圖??Ｆｉｇ．?３．２?Ｔｗｏ－ｆｌｏｏｒ?ｏｕｔｃｏｍｉｎｇ?ｇｒａｐｈ?ｏｆ?ｎｏｄｅｓ??０＾５）??０．?６＼?〇？??？?Ｂ??（ａ）?（ｂ）??圖３．３相同影響力情況下不同的出邊鄰居激活閾值??Ｆｉｇ．?３．３?Ｄｉｆｆｅｒｅｎｔ?ｔｈｒｅｓｈｏｌｄ?ｏｆ?ｏｕｔｃｏｍｉｎｇ?ｎｏｄｅｓ?ｗｉｔｈ?ｔｈｅ?ｓａｍｅ?ｉｎｆｌｕｅｎｃｅ??除了節(jié)點(diǎn)對其Ｈ階內(nèi)節(jié)點(diǎn)產(chǎn)生的影響之外，Ｈ階內(nèi)節(jié)點(diǎn)自身的激活閾值也需??要被考慮到選擇最具有潛在影響力節(jié)點(diǎn)的過程中。從圖３．３我們可以看出，雖然ｘ??節(jié)點(diǎn)和ｙ節(jié)點(diǎn)對其出邊節(jié)點(diǎn)的影響力相同，但是由于其出邊節(jié)點(diǎn)的激活閾值不同，??因此帶來不同的結(jié)果。圖３．３（ａ）中ｘ節(jié)點(diǎn)可以激活閾值為０．４的節(jié)點(diǎn)，而在圖３．３（ｂ）??中閾值為０．５和０．３的節(jié)點(diǎn)都可以被ｙ節(jié)點(diǎn)激活。因此，對于節(jié)點(diǎn)ｘ和ｙ，對出邊??節(jié)點(diǎn)有同樣的影響力，激活結(jié)果卻不同。??－２２－??

【參考文獻(xiàn)】：
期刊論文
[1]邊緣覆蓋去重的社交網(wǎng)絡(luò)影響力最大化算法[J]. 胡敏,孫欣然,黃宏程.  計(jì)算機(jī)科學(xué)與探索. 2017(05)
[2]社交網(wǎng)絡(luò)影響力傳播研究[J]. 陳衛(wèi).  大數(shù)據(jù). 2015(03)
[3]基于用戶行為的微博用戶社會影響力分析[J]. 毛佳昕,劉奕群,張敏,馬少平.  計(jì)算機(jī)學(xué)報(bào). 2014(04)
[4]在線社交網(wǎng)絡(luò)影響力分析[J]. 吳信東,李毅,李磊.  計(jì)算機(jī)學(xué)報(bào). 2014(04)
[5]在線社會網(wǎng)絡(luò)的測量與分析[J]. 徐恪,張賽,陳昊,李海濤.  計(jì)算機(jī)學(xué)報(bào). 2014(01)
[6]在線社會網(wǎng)絡(luò)中信息擴(kuò)散[J]. 李棟,徐志明,李生,劉挺,王秀文.  計(jì)算機(jī)學(xué)報(bào). 2014(01)
[7]一種新型的社會網(wǎng)絡(luò)影響最大化算法[J]. 田家堂,王軼彤,馮小軍.  計(jì)算機(jī)學(xué)報(bào). 2011(10)

碩士論文
[1]社交網(wǎng)絡(luò)中節(jié)點(diǎn)影響力的評價(jià)與優(yōu)化機(jī)制研究[D]. 陳一帆.中南大學(xué) 2014



本文編號：2915084