【摘要】：近年來,隨著微信、微博等在生活的中普及,社交網(wǎng)絡(luò)在人們的生活中逐漸變得不可或缺。利用在線社交網(wǎng)絡(luò),人們可以建立社會關(guān)系,對同一件熱點事件進(jìn)行交流并分享想法,社交網(wǎng)絡(luò)逐漸成為一種有價值的營銷媒體。同時,人們逐漸發(fā)現(xiàn)在社交網(wǎng)絡(luò)上進(jìn)行廣告投放可以取得很好的反饋,影響力最大化問題也就隨之產(chǎn)生。傳統(tǒng)的影響力最大化問題主要從個體層面去進(jìn)行影響力分析,很少考慮在線社交網(wǎng)絡(luò)中的用戶一般都會形成社區(qū)這樣一個客觀事實。從個體層面去挖掘網(wǎng)絡(luò)中最具影響力的節(jié)點是一個NP-hard問題,現(xiàn)有研究中的貪婪算法可以保證其解的近似最優(yōu),但是其不足之處在于,在大規(guī)模網(wǎng)絡(luò)上該算法運行時間成本較高�；诖�,為了提高在大規(guī)模網(wǎng)絡(luò)上解決此問題的算法的運行效率,本文提出基于社區(qū)的影響力最大化算法NVPA-IM(Neighborhood Vector Propagation Algorithm-Influence Maximization)算法,該算法主要利用網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)選擇影響力最大的k個節(jié)點。本文主要包括以下幾點:第一、在社交網(wǎng)絡(luò)中,具有同樣屬性的用戶聯(lián)系更趨向于緊密,那么在社交網(wǎng)絡(luò)中就會形成各種虛擬社區(qū)結(jié)構(gòu)。而挖掘網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)對于人們理解信息在網(wǎng)絡(luò)中的傳播具有重要的作用。本文提出的解決影響力最大化問題的算法的第一步就是獲取網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。選擇何種社區(qū)劃分算法是一個需要考量的問題,本文基于社區(qū)劃分算法的性質(zhì),選擇NVPA社區(qū)劃分算法,并且選擇具有代表性的貪心算法快速紐曼算法FN(Fast Newman),基于相似度的聚合算法HClustering(Hierarchical Clustering)及經(jīng)典的標(biāo)簽傳播算法LPA(Label Propagation Algorithm)作為對比算法對網(wǎng)絡(luò)進(jìn)行社區(qū)劃分,并從影響力的角度對劃分結(jié)果進(jìn)行對比分析。第二、本文分析了從社區(qū)角度出發(fā)的種子節(jié)點選取算法。傳統(tǒng)的從網(wǎng)絡(luò)中選擇節(jié)點的策略主要有兩種:啟發(fā)式策略和貪心策略。算法效率較高的是啟發(fā)式策略,度中心算法和隨機(jī)算法是兩種典型的啟發(fā)式策略,一般情況下作為對比算法使用。貪心策略主要是貪婪爬山算法。該算法精度很高,但是效率低。而本文基于NVPA社區(qū)劃分算法的性質(zhì),提出了一種度中心算法的擴(kuò)展算法NVPA-IM種子節(jié)點選取算法,并且從影響覆蓋的角度對NVPA-IM算法進(jìn)行了性能驗證。
【學(xué)位授予單位】：上海交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：TP301.6;TP393.09
【圖文】：

圖 2-1 一個具有簡單社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)Fig 2-1 The network with a simple community structure度優(yōu)化思想的 FN 社區(qū)發(fā)現(xiàn)算法衡量社區(qū)劃分算法劃分網(wǎng)絡(luò)的所獲得的社區(qū)的結(jié)構(gòu)強(qiáng)

圖 2-2 NVPA 算法示例:（a）節(jié)點初始向量；（b）經(jīng)過鄰域向量傳播后節(jié)點的領(lǐng)域向量值和節(jié)點之間的相似度Fig. 2-2 NVPA algorithm example: (a) initialize vectors; (b) vectors propagate through neighbors,and calculate similarities在鄰域向量定義階段，正如第二章所介紹的，為了避免相似度只考慮一跳鄰居節(jié)點的情況，NVPA 算法在計算相似度時考慮了與節(jié)點并非直接相鄰的多跳鄰居

圖 2-3 鄰域向量降維規(guī)則偽代碼. 2-3 Pseudo code of neighborhood vector reducing dimension，i jn 、 n分別表示社區(qū)i jv 、 v的中的節(jié)點數(shù)，同時5 中的迭代終止條件一般是 Newman 等人提出的模因為基于社區(qū)層面挖掘網(wǎng)絡(luò)中最具影響力的k 個節(jié)

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 劉嘉唯;高慧穎;崔立新;朱珈印;吳奕萱;;微信社交網(wǎng)絡(luò)顧客感知服務(wù)質(zhì)量評價指標(biāo)體系研究[J];信息與管理研究;2019年Z2期

2 陳健;周麗華;;大學(xué)生社交網(wǎng)絡(luò)自我表露的實證研究[J];高校輔導(dǎo)員學(xué)刊;2018年06期

3 譚洪旭;袁帥;代連奇;任利峰;;淺談社交網(wǎng)絡(luò)對當(dāng)代大學(xué)生的影響[J];產(chǎn)業(yè)與科技論壇;2018年24期

4 孫夏卿;;社交網(wǎng)絡(luò)媒體對大學(xué)生賦權(quán)的價值體現(xiàn)[J];傳播力研究;2018年31期

5 張曉飛;;以社交網(wǎng)絡(luò)為基礎(chǔ)的企業(yè)營銷策略[J];商場現(xiàn)代化;2018年22期

6 孫國強(qiáng);竇倩倩;張寶建;;西方社交網(wǎng)絡(luò)研究進(jìn)展與未來展望[J];情報科學(xué);2019年02期

7 陳文泰;李衛(wèi)東;;國際社交網(wǎng)絡(luò)中“國家實在”傳播與國家形象演化機(jī)制研究[J];新聞大學(xué);2018年06期

8 孫晉;沈紅;;社交網(wǎng)絡(luò)群體性迷失現(xiàn)象分析[J];電腦知識與技術(shù);2019年12期

9 鄧華闖;項yN麟;周楠;周子清;;社交網(wǎng)絡(luò)招聘有效性影響因素研究[J];中小企業(yè)管理與科技(上旬刊);2019年04期

10 王超瓊;陳s

本文編號：2803044