發(fā)布時間：2017-07-17 01:02

  本文關(guān)鍵詞：在線社會網(wǎng)絡(luò)中影響最大化問題的研究

  更多相關(guān)文章： 社會網(wǎng)絡(luò) 貪心算法 影響最大化 帶符號網(wǎng)絡(luò) 信息傳播

【摘要】：市場營銷中,為了推廣某一產(chǎn)品,如何利用有限的資金有效的選擇若干個客戶來進(jìn)行產(chǎn)品促銷,借助“病毒式營銷”(viral marketing)和“口碑效應(yīng)”(word-of-mouth)的方式來達(dá)到產(chǎn)品營銷的目的,這是社會網(wǎng)絡(luò)影響最大化問題提出的背景。隨著在線社會網(wǎng)絡(luò)和web2.0的發(fā)展,影響最大化問題再度成為社會網(wǎng)絡(luò)領(lǐng)域研究的熱點(diǎn)。Domingos和Richardson給出影響最大化問題的定義：為了推廣一些產(chǎn)品或觀念,如何有效選擇k個節(jié)點(diǎn)作為初始傳播對象,通過社會網(wǎng)絡(luò)中信息的傳播與擴(kuò)散,最終達(dá)到傳播范圍的最大化。 擴(kuò)大影響范圍并降低時間復(fù)雜度是在線社會網(wǎng)絡(luò)影響最大化問題的重要目標(biāo)。Kempe和Kleinberg提出具有較好影響范圍的貪心算法,并證明影響最大化問題是NP-hard。但貪心算法過程非常耗時,不能適用在大型社會網(wǎng)絡(luò)中,而且不能保證影響范圍最優(yōu)。本文發(fā)現(xiàn)了線性閾值模型的“影響積累”特性：激活節(jié)點(diǎn)u嘗試激活節(jié)點(diǎn)v失敗之后,影響力buv.被“積累”下來,直到節(jié)點(diǎn)v被激活或者傳播過程結(jié)束�；诖颂匦�,提出了一個該模型下的影響最大化算法的框架,并在此框架基礎(chǔ)上給出一個新的HPG算法。同時針對帶符號網(wǎng)絡(luò)的特性,給出乘法規(guī)則,將所提算法框架和HPG算法推廣到帶符號網(wǎng)絡(luò)。HPG算法綜合考慮網(wǎng)絡(luò)的結(jié)構(gòu)特性和傳播特性,首先花費(fèi)常量時間啟發(fā)式選擇一些最具“潛在影響力”的節(jié)點(diǎn)進(jìn)行影響力的積累,然后動態(tài)尋找最具影響力的節(jié)點(diǎn)。我們在六個真實(shí)的社會網(wǎng)絡(luò)數(shù)據(jù)集(有向/無向,有權(quán)/無權(quán),稀疏/稠密,帶符號/不帶符號,在線網(wǎng)絡(luò)/傳統(tǒng)網(wǎng)絡(luò),等等)上進(jìn)行實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果顯示HPG算法在最終影響范圍和運(yùn)行時間上都獲得比貪心算法更好的效果。 另外,針對最具“潛在影響力”節(jié)點(diǎn)的選擇,我們設(shè)計實(shí)驗(yàn)去驗(yàn)證和分析所給“潛在影響力”計算公式PI的合理性。
【關(guān)鍵詞】：社會網(wǎng)絡(luò) 貪心算法 影響最大化 帶符號網(wǎng)絡(luò) 信息傳播
【學(xué)位授予單位】：復(fù)旦大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2012
【分類號】：TP301.6;F49
【目錄】：

• 摘要5-6
• Abstract6-7
• 第一章 引言7-12
• 1.1 研究背景與意義7-9
• 1.2 國內(nèi)外研究現(xiàn)狀9-10
• 1.3 研究目標(biāo)和內(nèi)容10
• 1.4 論文組織架構(gòu)10-12
• 第二章 背景知識和相關(guān)工作12-22
• 2.1 背景知識12-19
• 2.1.1 社會網(wǎng)絡(luò)的數(shù)學(xué)表達(dá)形式12-15
• 2.1.2 兩個基本傳播模型15-19
• 2.1.3 次模函數(shù)(Submodiular Function)19
• 2.2 相關(guān)工作19-22
• 2.2.1 爬山貪心算法(Hill Climbing Greedy Algorithm)19-20
• 2.2.2 基于度數(shù)的節(jié)點(diǎn)選擇策略20
• 2.2.3 共它相關(guān)算法20-22
• 第三章 新型的混合式影響最大化算法22-28
• 3.1 出發(fā)點(diǎn)22
• 3.2 算法框架的提出及HPG算法22-25
• 3.3 算法框架推廣到帶符號網(wǎng)絡(luò)25-26
• 3.4 GREEDY算法和HPG算法的時間復(fù)雜度分析26-28
• 第四章 節(jié)點(diǎn)間影響力計算公式28-32
• 4.1 無權(quán)圖上b_(DV)的估計公式28-29
• 4.2 帶權(quán)圖上b_(DV)的估計公式29
• 4.3 帶符號圖上b_(DV)的估計公式29-32
• 第五章 實(shí)驗(yàn)和評估32-40
• 5.1 實(shí)驗(yàn)數(shù)據(jù)集32-33
• 5.2 實(shí)驗(yàn)設(shè)計33-34
• 5.3 實(shí)驗(yàn)結(jié)果34-39
• 5.3.1 算法框架在無向網(wǎng)絡(luò)上的效果34-35
• 5.3.2 算法框架在帶權(quán)網(wǎng)絡(luò)上的有效性35-36
• 5.3.3 算法框架在有向網(wǎng)絡(luò)上的效果36
• 5.3.4 HPG算法在帶符號網(wǎng)絡(luò)上的效果36-37
• 5.3.5 Greedy算法和算法框架之間的比較37-38
• 5.3.6 時間復(fù)雜度比較38-39
• 5.4 實(shí)驗(yàn)總結(jié)39-40
• 第六章 潛在影響力計算公式說明40-45
• 6.1 實(shí)驗(yàn)設(shè)計40
• 6.2 實(shí)驗(yàn)結(jié)果40-45
• 6.2.1 直接線性組合實(shí)驗(yàn)41-42
• 6.2.2 歸一化線性組合實(shí)驗(yàn)42-43
• 6.2.3 直接線性組合和歸一化組合對比實(shí)驗(yàn)43-45
• 第七章 總結(jié)和展望45-47
• 7.1 論文總結(jié)45
• 7.2 未來工作展望45-47
• 參考文獻(xiàn)47-50
• 附錄一 碩士期間所發(fā)表的論文50-51
• 致謝51-52

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 華軍;;讓W(xué)indows 7不再自作聰明最大化窗口[J];電腦迷;2009年24期

2 書房;;打開最大化窗口的一點(diǎn)經(jīng)驗(yàn)[J];電腦采購周刊;2001年33期

3 黑暗之客;;尋找最簡單的最大化方式[J];電腦愛好者;2008年04期

4 熊國成;;音樂電視“康美藥業(yè)”的廣告效果分析[J];新聞愛好者;2011年03期

5 師曉青;;“并發(fā)用戶數(shù)”限制下的數(shù)據(jù)庫利用效率分析[J];圖書館學(xué)研究;2009年06期

6 易水;;外刊精粹[J];微電腦世界;2006年11期

7 楊小芹;;學(xué)校虛擬圖書館構(gòu)建摭談[J];湘潭師范學(xué)院學(xué)報(社會科學(xué)版);2008年05期

8 冰冰;;關(guān)于IE瀏覽器默認(rèn)窗口大小的問題[J];網(wǎng)絡(luò)與信息;2009年01期

9 杜耀桃;;通信企業(yè)動力環(huán)境集中監(jiān)控系統(tǒng)應(yīng)用價值的實(shí)現(xiàn)[J];科技資訊;2009年30期

10 白斌;羅軍勇;劉琰;;基于搜索引擎的社會網(wǎng)絡(luò)個體關(guān)系評估實(shí)現(xiàn)[J];信息工程大學(xué)學(xué)報;2009年04期

中國重要會議論文全文數(shù)據(jù)庫 前10條

1 吳浩萍;;做好引進(jìn)國外專家工作,實(shí)現(xiàn)引智效益的最大化[A];引進(jìn)國外智力研究論文選編（2007年—2009年）——獻(xiàn)給中華人民共和國60周年華誕[C];2009年

2 何應(yīng)森;;法律與經(jīng)濟(jì)增長之間的關(guān)聯(lián)問題[A];2007年全國法經(jīng)濟(jì)學(xué)論壇論文集[C];2007年

3 張記山;;成本控制最小化 效益追求最大化[A];河南省建筑業(yè)行業(yè)優(yōu)秀論文集(2008)[C];2008年

4 陳正華;;中央與地方分權(quán)的成本收益與交易成本——法經(jīng)濟(jì)學(xué)的視角[A];2007年全國法經(jīng)濟(jì)學(xué)論壇論文集[C];2007年

5 李紅珠;;如何創(chuàng)建人性化服務(wù)品牌[A];中國輸血協(xié)會第五屆輸血大會論文專集（摘要篇）[C];2010年

6 林碧英;;強(qiáng)化內(nèi)部會計控制 實(shí)現(xiàn)企業(yè)價值最大化[A];2003年福建省會計學(xué)會理論研討論文專輯[C];2003年

7 陳典全;黃朝陽;;基于位置的社會網(wǎng)絡(luò)(LBSN)研究及其產(chǎn)業(yè)化[A];第二屆中國衛(wèi)星導(dǎo)航學(xué)術(shù)年會電子文集[C];2011年

8 李建勇;;論侵權(quán)案件審判中原創(chuàng)與再創(chuàng)的法經(jīng)濟(jì)學(xué)分析[A];2007年全國法經(jīng)濟(jì)學(xué)論壇論文集[C];2007年

9 李莉;武邦濤;陳忠;;社會網(wǎng)絡(luò)作為雙刃劍:交易網(wǎng)絡(luò)的摩擦、中介可能性與結(jié)構(gòu)洞[A];第五屆全國復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會議論文（摘要）匯集[C];2009年

10 艾佳慧;;中國的法官最大化些什么?——實(shí)證和比較視野下的經(jīng)濟(jì)學(xué)分析[A];2007年全國法經(jīng)濟(jì)學(xué)論壇論文集[C];2007年

中國重要報紙全文數(shù)據(jù)庫 前10條

1 野風(fēng)集團(tuán)有限公司副總裁兼首席財務(wù)官 蔣建林;企業(yè)要在財務(wù)文化上有所建樹[N];經(jīng)理日報;2010年

2 李俠 上海交通大學(xué)教授;我們?yōu)楹巫鹬貦?quán)威[N];上�？萍紙�;2011年

3 張瑩瑩;常寶股份變更募資投向斥資7.8億新建三項(xiàng)目[N];證券時報;2011年

4 ;“快速擴(kuò)張考驗(yàn)運(yùn)營水平”[N];經(jīng)濟(jì)視點(diǎn)報;2011年

5 谷歡歡　本報記者 董菁;企業(yè)家的七秒鐘[N];中國企業(yè)報;2010年

6 劉厚珉 王富剛;單縣交警實(shí)現(xiàn)“四個最大化”保群眾交通安全[N];菏澤日報;2007年

7 王雅楠;明智管理讓城市化好處最大[N];中國建設(shè)報;2010年

8 高三學(xué)生 王彥龍;“地球一小時”與母親的365天[N];新華每日電訊;2011年

9 東興證券 孫繼青;鋼鐵主業(yè)將進(jìn)入盈利周期 業(yè)績彈性或?qū)⒆畲蠡痆N];通信信息報;2009年

10 記者 陳化宇;安瑞電力——規(guī)范化運(yùn)作創(chuàng)效益最大化[N];雅安日報;2008年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 王洋;社會網(wǎng)絡(luò)視角下的危機(jī)傳播機(jī)理與治理[D];哈爾濱工業(yè)大學(xué);2011年

2 倪順江;基于復(fù)雜網(wǎng)絡(luò)理論的傳染病動力學(xué)建模與研究[D];清華大學(xué);2009年

3 袁曉婷;企業(yè)R&D團(tuán)隊(duì)內(nèi)部社會網(wǎng)絡(luò)與團(tuán)隊(duì)知識創(chuàng)造關(guān)系研究[D];華南理工大學(xué);2010年

4 張淑娟;吳景濂與民國政治：1916～1923[D];復(fù)旦大學(xué);2007年

5 徐峰;互聯(lián)網(wǎng)宏觀拓?fù)浣Y(jié)構(gòu)中社團(tuán)特征演化分析及應(yīng)用[D];東北大學(xué);2009年

6 蘇春艷;社會網(wǎng)絡(luò)與職業(yè)獲得[D];上海大學(xué);2005年

7 王小明;社會資本的經(jīng)濟(jì)分析[D];復(fù)旦大學(xué);2008年

8 鄧學(xué)軍;企業(yè)家社會網(wǎng)絡(luò)對企業(yè)績效的影響研究[D];暨南大學(xué);2009年

9 丁楠;高管團(tuán)隊(duì)社會網(wǎng)絡(luò)、運(yùn)作過程與績效間關(guān)系研究[D];江蘇大學(xué);2010年

10 譚婷婷;網(wǎng)絡(luò)微內(nèi)容推薦方法及支持系統(tǒng)研究[D];華中科技大學(xué);2011年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 田家堂;在線社會網(wǎng)絡(luò)中影響最大化問題的研究[D];復(fù)旦大學(xué);2012年

2 冀進(jìn)朝;社區(qū)影響最大化算法及其傳播模型研究[D];吉林大學(xué);2010年

3 章云龍;社交網(wǎng)絡(luò)中基于話題的影響最大化問題研究[D];上海交通大學(xué);2012年

4 艾福嬌;成人后悔傾向問卷編制及其相關(guān)研究[D];江西師范大學(xué);2010年

5 趙秀濤;Web病毒式營銷中的挖掘技術(shù)研究[D];沈陽航空工業(yè)學(xué)院;2010年

6 黎雷;社會網(wǎng)絡(luò)影響力模型及其算法研究[D];北京交通大學(xué);2010年

7 黃平;消費(fèi)類電子產(chǎn)品附加設(shè)計研究[D];燕山大學(xué);2010年

8 李高吉;社會網(wǎng)絡(luò)對集群企業(yè)績效的影響研究[D];南華大學(xué);2010年

9 李磊;社會網(wǎng)絡(luò)與金融危機(jī)[D];南京大學(xué);2011年

10 張普瑋;我國慈善組織的社會服務(wù)能力最大化理財目標(biāo)[D];首都經(jīng)濟(jì)貿(mào)易大學(xué);2012年

，

本文編號：551258