隨著互聯(lián)網(wǎng)邁入網(wǎng)絡(luò)2.0時代,得益于社交網(wǎng)絡(luò)的便利性,人們積極在社交平臺上分享自己的日�；顒�,進(jìn)而產(chǎn)生了大量數(shù)據(jù)。介于虛擬網(wǎng)絡(luò)是真實(shí)世界的映射,所以分析社交網(wǎng)絡(luò)對真實(shí)社會的影響有著長遠(yuǎn)而又實(shí)際的意義。目前,在影響力最大化算法中忽視了一種常見的社會現(xiàn)象:種子節(jié)點(diǎn)集合中具有重要影響力的節(jié)點(diǎn)可能會突然丟失,從而導(dǎo)致集合的影響力大打折扣。且現(xiàn)有的影響力最大化算法的求解過程存在大量重復(fù)的迭代操作,導(dǎo)致效率低下,運(yùn)行時間長,已無法滿足當(dāng)今數(shù)據(jù)環(huán)境需求。另外,在現(xiàn)有的替補(bǔ)種子節(jié)點(diǎn)尋找算法中,諸多算法存在節(jié)點(diǎn)選擇隨機(jī)化、數(shù)據(jù)稀疏等諸多問題。針對以上問題,本文主要研究內(nèi)容如下:（1）針對社交網(wǎng)絡(luò)中社區(qū)影響力最大化算法效率低下的問題,本文提出基于社區(qū)劃分的影響力最大化算法（Influence Maximization Algorithm Based on Community partition,IMBCP）。在IMBCP算法中,通過提出的IPS（base on Influence Probability and Similarity）算法來求解社交網(wǎng)絡(luò)的社區(qū)機(jī)構(gòu),然后在社區(qū)結(jié)構(gòu)中求解影響力最大化。IPS算... 

【文章來源】：江蘇大學(xué)江蘇省

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

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

【部分圖文】：

復(fù)雜社交網(wǎng)絡(luò)示意圖

圖 2.2 非重疊社區(qū)結(jié)構(gòu)法認(rèn)為在社交網(wǎng)絡(luò)中，社區(qū)可以被看作是圖的緊密子結(jié)構(gòu)，社區(qū)算法來解決。圖分割法將整個社交網(wǎng)絡(luò)劃分成若干個子網(wǎng)（社點(diǎn)數(shù)目相同。圖分割法中代表性的算法主要有：KL（kernighan法[40]。KL 算法的具體流程為：首先是初始化，將圖中的節(jié)點(diǎn)隨；然后持續(xù)迭代互換 A 和 B 中的節(jié)點(diǎn)，記錄增益函數(shù) P 的變的兩個節(jié)點(diǎn)。重復(fù)以上過程，直到某個社區(qū)中的所有節(jié)點(diǎn)都已分算法首先根據(jù)拉普拉斯矩陣特點(diǎn)，首先求出拉普拉斯矩陣的根據(jù)特征向量的正負(fù)性將圖分為兩個社區(qū)。須首先設(shè)定先驗(yàn)值，算法效率低下，而且同譜平分算法相同的區(qū)[41]。這些缺陷使得圖分割算法實(shí)際應(yīng)用場景稀少，應(yīng)用范圍

江 蘇 大 學(xué) 碩 士 學(xué) 位 論 文針對 GN 算法存在的問題，提出了 Newman 算法[47]，提出了模塊度的概念（Q 函數(shù)）。Newman 利用模塊度來評估社區(qū)劃分質(zhì)量。Newman 算法首先對網(wǎng)絡(luò)進(jìn)行初始化，然后計算存在共同邊的兩個社區(qū)合并后 Q 函數(shù)的增量值 Q ，選擇 Q 最大的兩個社區(qū)進(jìn)行合并。重復(fù)此過程，直到整個網(wǎng)絡(luò)合并成為一個社區(qū)。2.1.2 重疊社區(qū)發(fā)現(xiàn)算法傳統(tǒng)的社區(qū)劃分算法認(rèn)為一個節(jié)點(diǎn)只能屬于一個社區(qū)，社區(qū)之間不存在共同節(jié)點(diǎn)。而在現(xiàn)實(shí)社會中，人是復(fù)雜多變的生命體。所以，在社交網(wǎng)絡(luò)中，人們應(yīng)該屬于多個社區(qū)，這才是最符合現(xiàn)實(shí)情況的網(wǎng)絡(luò)結(jié)構(gòu)（如圖 2.3）。本節(jié)將對重疊社區(qū)發(fā)現(xiàn)領(lǐng)域出現(xiàn)的部分算法進(jìn)行簡述。

【參考文獻(xiàn)】：
期刊論文
[1]在影響力最大化問題中尋找種子節(jié)點(diǎn)的替補(bǔ)節(jié)點(diǎn)[J]. 馬茜,馬軍.  計算機(jī)學(xué)報. 2017(03)
[2]基于標(biāo)簽傳播概率的重疊社區(qū)發(fā)現(xiàn)算法[J]. 劉世超,朱福喜,甘琳.  計算機(jī)學(xué)報. 2016(04)
[3]社會網(wǎng)絡(luò)中的影響力最大化問題[J]. 顏慶,張鵬.  計算機(jī)工程與科學(xué). 2015(02)
[4]一種面向語義重疊社區(qū)發(fā)現(xiàn)的Block場取樣算法[J]. 辛宇,楊靜,謝志強(qiáng).  自動化學(xué)報. 2015(02)
[5]在線社會網(wǎng)絡(luò)中信息擴(kuò)散[J]. 李棟,徐志明,李生,劉挺,王秀文.  計算機(jī)學(xué)報. 2014(01)
[6]一種新型的社會網(wǎng)絡(luò)影響最大化算法[J]. 田家堂,王軼彤,馮小軍.  計算機(jī)學(xué)報. 2011(10)

博士論文
[1]社會網(wǎng)絡(luò)中的節(jié)點(diǎn)影響力度量和k-節(jié)點(diǎn)集的影響力最大化問題研究[D]. 馬茜.山東大學(xué) 2017
[2]社會網(wǎng)絡(luò)中信息傳播若干關(guān)鍵技術(shù)研究[D]. 周東浩.國防科學(xué)技術(shù)大學(xué) 2015

碩士論文
[1]社會網(wǎng)絡(luò)影響力最大化研究[D]. 劉振杰.安徽大學(xué) 2018
[2]基于線性閾值模型的社交網(wǎng)絡(luò)影響力最大化研究[D]. 郭振強(qiáng).哈爾濱工業(yè)大學(xué) 2017
[3]基于線性閾值模型的社交網(wǎng)絡(luò)影響最大化研究[D]. 翁旭.大連海事大學(xué) 2017
[4]社交網(wǎng)絡(luò)中用戶影響力的研究[D]. 劉金龍.北京郵電大學(xué) 2016
[5]社交網(wǎng)絡(luò)影響力最大化的研究[D]. 王歡歡.南京航空航天大學(xué) 2016
[6]社交團(tuán)體的網(wǎng)絡(luò)影響力最大化研究[D]. 徐艮.華中科技大學(xué) 2015
[7]基于android的畢業(yè)設(shè)計管理系統(tǒng)的設(shè)計與實(shí)現(xiàn)[D]. 江林.電子科技大學(xué) 2015
[8]社會網(wǎng)絡(luò)上的影響力最大化算法研究[D]. 蘭如欽.北京交通大學(xué) 2011



本文編號：3571876