本文關(guān)鍵詞： 社會網(wǎng)絡(luò) 信息傳播 影響力最大化　出處：《南京大學(xué)》2016年博士論文　論文類型：學(xué)位論文

【摘要】：隨著互聯(lián)網(wǎng)的普及和在線社會網(wǎng)絡(luò)的發(fā)展,研究者可以獲取豐富的歷史數(shù)據(jù),并對社會網(wǎng)絡(luò)中的信息傳播進(jìn)行分析、預(yù)測和利用。作為一種新型的媒介,社會網(wǎng)絡(luò)中的信息可以像“病毒”一樣迅速地在人與人之間傳播,因此受到了普遍的關(guān)注：一方面,相比于電臺、報紙、電視等大眾傳媒廣播的方式,社會網(wǎng)絡(luò)中的信息傳播具有“口口相傳”的效應(yīng),更容易被人們所信任；另一方面,信息的傳播還可能具有級聯(lián)效應(yīng),造成廣泛的影響。然而,社會網(wǎng)絡(luò)中難以預(yù)測的個體行為和復(fù)雜的拓?fù)浣Y(jié)構(gòu),為信息傳播的分析和利用帶來了極大的挑戰(zhàn)。因此,如何通過歷史數(shù)據(jù)挖掘,對信息傳播進(jìn)行分析預(yù)測,并進(jìn)一步利用信息傳播達(dá)到影響力最大化,為企業(yè)宣傳、廣告營銷、輿情監(jiān)控等提供決策輔助,已成為當(dāng)前社會網(wǎng)絡(luò)研究的一個熱點(diǎn)問題。針對上述問題,本文首先對信息級聯(lián)的結(jié)構(gòu)進(jìn)行挖掘,識別出社會網(wǎng)絡(luò)信息級聯(lián)幾種典型結(jié)構(gòu)模式,并利用結(jié)構(gòu)模式對信息傳播進(jìn)行預(yù)測；然后基于信息傳播的模式,分析了多種信息同時傳播的交互模型,用信息回溯的方法找到最有影響力的節(jié)點(diǎn)；最后研究了在給定預(yù)算的情況下,如何通過預(yù)算分配來激勵這些最有影響力的節(jié)點(diǎn),從而使得影響力的擴(kuò)散可以達(dá)到最大。論文的主要貢獻(xiàn)可概括如下：(1)分析信息傳播的級聯(lián)結(jié)構(gòu),并通過級聯(lián)結(jié)構(gòu)預(yù)測信息未來的傳播模式。在社會網(wǎng)絡(luò)中,信息級聯(lián)的結(jié)構(gòu)往往和信息傳播互相影響。首先,不同機(jī)制所驅(qū)動的信息傳播會導(dǎo)致結(jié)構(gòu)不同的級聯(lián),同質(zhì)性主導(dǎo)的級聯(lián)往往會發(fā)展為寬而淺的結(jié)構(gòu),而社會影響力主導(dǎo)的級聯(lián)則會變得深而復(fù)雜；其次,不同結(jié)構(gòu)的信息級聯(lián)會傳播到不同的范圍和社群,從而影響信息的傳播過程。本文采用數(shù)據(jù)驅(qū)動的方法,分析了大量信息級聯(lián)的傳播結(jié)構(gòu),通過對信息級聯(lián)的結(jié)構(gòu)進(jìn)行降維嵌入(embedding)和譜聚類(spectral clustering)，識別出社會網(wǎng)絡(luò)中的信息級聯(lián)五種典型的結(jié)構(gòu)模式,并且發(fā)現(xiàn)不同結(jié)構(gòu)模式的信息級聯(lián)之間具有明顯差異的特征。根據(jù)以上觀察,本文引入級聯(lián)結(jié)構(gòu)來預(yù)測信息未來的傳播模式,實驗結(jié)果表明,該方法可以顯著提升預(yù)測的準(zhǔn)確率。(2)研究了多種信息同時傳播的交互模型,并識別其中有影響力的節(jié)點(diǎn)。社會網(wǎng)絡(luò)中往往有多種信息在同時傳播,而且信息之間可能存在競爭、互利等交互關(guān)系。針對這種情況,本文設(shè)計了交互信息級聯(lián)模型來刻畫多種信息之間的傳播,可以同時考慮信息之間的交互關(guān)系和用戶對交互信息的選擇偏好。在這個模型下,本文首先證明了該問題是NP難的,并提出了一種基于回溯的馬爾科夫隨機(jī)游走(markov random walk)算法：假設(shè)信息傳播可以達(dá)到所有節(jié)點(diǎn),然后通過傳播模型進(jìn)行回溯,找出信息最有可能的來源,即為影響力最大的節(jié)點(diǎn)。模擬實驗表明,相比于其它常用的算法,本文提出的算法可以在絕大多數(shù)情況下取得最好的效果。同時,該算法還可以快速地收斂,因此有很高的運(yùn)行效率。(3)提出了一個基于預(yù)算分配的策略,通過激勵社會網(wǎng)絡(luò)中的初始用戶實現(xiàn)影響力最大化。為了激勵初始用戶實現(xiàn)影響力最大化,以往的工作一般理想地假設(shè)用戶具有確定的估值,只有分配的預(yù)算高于該估值,用戶才會成為初始用戶；而在實際情況中,在不同的預(yù)算下,用戶都有可能成為初始用戶。本文使用效用函數(shù)(utility function)來刻畫用戶的滿意度,假定用戶的估值滿足一定的概率分布函數(shù)。在這個模型下,通過歸約證明了該問題的難度。同時,提出了一個離散貪心的算法來找出預(yù)算分配的方案：首先將預(yù)算均勻地離散化,然后采用迭代的方式將預(yù)算依次分配給具有邊際增益最大的用戶。該方法可以在離散的設(shè)置中取得近似最優(yōu)的結(jié)果。進(jìn)一步,本文還證明了當(dāng)合理地選擇一個離散的粒度后,該算法可以在預(yù)算連續(xù)的設(shè)置下取得1-1/e-o(1)的性能保證。最后,本文還通過更新邊際增益的計算和估算傳播概率的方法來提升算法的執(zhí)行效率。實驗結(jié)果表明,相比于其它已有的方法,離散貪心的算法能顯著提高信息覆蓋的范圍,同時還有非常好的可擴(kuò)展性。
[Abstract]:With the popularity of the Internet and online social networks, researchers can obtain rich historical data, and the dissemination of information in social network analysis, prediction and use. As a new media, social network information can be like a virus as fast speed in communication between people, so widespread attention: on the one hand, compared to newspapers, radio, television and other mass media broadcast mode, the dissemination of information in social networks with "word of mouth" effect, more likely to be discredited; on the other hand, the dissemination of information also may have a cascading effect, causing widespread influence. However, it is difficult to prediction of individual behavior in social network and complex topology, analysis and utilization of information dissemination has brought great challenges. Therefore, how to use historical data mining, the dissemination of information analysis The prediction, and further use of information dissemination to the influence maximization, for business promotion, advertising and marketing, to provide decision support public opinion monitoring, has become a hot topic of current social network research. Aiming at the above problems, firstly the structure of the cascade of information mining, identified several typical patterns of structure of social network information cascade, and to predict the structure of information dissemination and utilization mode; then based on the mode of information dissemination, the analysis of the interactive model as well as information dissemination, find the most influential nodes for information back; at the end of the budget in a given situation, how to motivate the most influential nodes through the budget allocation, which makes the influence the diffusion can reach the maximum. The main contributions of this thesis can be summarized as follows: (1) the cascade structure analysis of information dissemination, and through the connection level The communication model of forecast information in the future. In the social network, information structure and information dissemination cascade often influence each other. First of all, the dissemination of information driven by different mechanisms lead to a cascade of different structure, leading the development tend to homogeneity cascade structure wide and shallow, and cascade leading social influence will become deep and complex; secondly, information cascades with different structures will spread into different ranges and communities, thus affecting the process of information dissemination. This paper uses the method of data drive, analyzes the structure of communication information cascade, dimensionality reduction through the structure of embedded information cascade (embedding) and spectral clustering (spectral, clustering) identify the information cascade of social networks in five typical modes of the structure, and found the obvious characteristic differences between different modes of the information cascade. According to the above observations, the The introduction of cascade structure to predict the mode of transmission of information in the future, the experimental results show that this method can significantly improve the prediction accuracy. (2) the interaction model studied a variety of information dissemination and recognition at the same time, one of the nodes influential. Social network often has many kinds of information in the dissemination of information at the same time, but also may exist between competition, mutual benefit relations. In view of this situation, this paper designs the interactive information cascade model to describe the spread of a variety of information, can also choose the preference information of the interaction between the user and the interactive information. In this model, the paper proves that this problem is NP hard, and put forward a backtracking based on Markov random walk (Markov random walk) algorithm: the assumption that information transmission can reach all nodes, and then through the back propagation model, find out the information May be the source of the node is the most influential. Simulation results show that compared with other algorithms, the proposed algorithm can achieve the best effect in most cases. At the same time, the algorithm can also fast convergence, so it is very efficient. (3) proposed a budget based on distribution strategy, realize the influence maximization through initial user incentive in social networks. In order to realize the influence maximization incentive initial users, previous work generally assume that the user has a certain ideal valuation, only the allocation of budget is higher than the valuation, the user will become the initial user; but in fact, in the different budget, users are likely to become the initial user. This paper use the utility function (utility function) to describe the user's satisfaction, assume that the user valuations meet the probability distribution function of some. This model is proved by reduction, the difficulty of the problem. At the same time, we propose a discrete greedy algorithm to find the budget allocation scheme: first the budget will be uniformly discrete, then iterative method using the budget successively assigned to the user with maximum marginal gain. This method can obtain near optimal results in the discrete setting. Further, this paper also proves that when selecting a discrete particle size, the algorithm can achieve 1-1/e-o in the setting of budget under continuous (1) performance guarantee. Finally, through the method of updating the marginal gain of the calculation and estimation of propagation probability to enhance the efficiency of the algorithm. The experimental results show that compared with other existing methods, discrete greedy algorithm can significantly improve the coverage of information, also have very good scalability.

【學(xué)位授予單位】：南京大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2016
【分類號】：G206;TP301.6

【相似文獻(xiàn)】

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

1 彭蘭;;從社區(qū)到社會網(wǎng)絡(luò)——一種互聯(lián)網(wǎng)研究視野與方法的拓展[J];國際新聞界;2009年05期

2 王琪;;嵌入互聯(lián)網(wǎng)中的社會網(wǎng)絡(luò)—企業(yè)電子社會網(wǎng)絡(luò)[J];企業(yè)經(jīng)濟(jì);2011年04期

3 李春霞;;網(wǎng)絡(luò)媒體對社會網(wǎng)絡(luò)的影響[J];河北大學(xué)學(xué)報(哲學(xué)社會科學(xué)版);2013年01期

4 阮冰;朱建沖;姜禮平;汲萬鋒;;基于社會網(wǎng)絡(luò)的民意形成演化建模與仿真研究[J];計算機(jī)仿真;2011年02期

5 劉晶;張秀蘭;;談社會網(wǎng)絡(luò)在圖書館的應(yīng)用[J];新世紀(jì)圖書館;2011年09期

6 秦紅霞;陳華東;;社會網(wǎng)絡(luò)視角的企業(yè)知識共享演化博弈分析[J];情報雜志;2009年05期

7 王煜全;;警惕互聯(lián)網(wǎng)上的“國家模式”——再談社會網(wǎng)絡(luò)的進(jìn)化機(jī)制[J];互聯(lián)網(wǎng)周刊;2011年02期

8 陳萍;;社會網(wǎng)絡(luò)中企業(yè)知識資源的互補(bǔ)性[J];圖書與情報;2007年05期

9 黎剛;;文獻(xiàn)信息社會網(wǎng)絡(luò)建設(shè)新論[J];職業(yè)技術(shù);2007年24期

10 張星;蔡淑琴;夏火松;侯德林;;基于社會網(wǎng)絡(luò)的企業(yè)知識管理系統(tǒng)框架研究[J];現(xiàn)代圖書情報技術(shù);2011年05期

相關(guān)會議論文 前10條

1 郭永昌;;中國大城市流動人口社會網(wǎng)絡(luò)構(gòu)筑的空間過程研究[A];2006年中國可持續(xù)發(fā)展論壇——中國可持續(xù)發(fā)展研究會2006學(xué)術(shù)年會經(jīng)濟(jì)發(fā)展與人文關(guān)懷專輯[C];2006年

2 程平;;基于社會網(wǎng)絡(luò)的“云會計”知識流動研究[A];第十屆全國會計信息化年會論文集[C];2011年

3 馬宗正;楊永芳;;貧困地區(qū)農(nóng)村社會網(wǎng)絡(luò)與農(nóng)民發(fā)展——對寧夏固原市五個村落的調(diào)查與思考[A];西部發(fā)展評論(2005年第2期 總第16期)[C];2005年

4 陸雙梅;;藏民社會網(wǎng)絡(luò)在手機(jī)中的呈現(xiàn)與重構(gòu)[A];第四屆中國少數(shù)民族地區(qū)信息傳播與社會發(fā)展論叢[C];2012年

5 周靜;;社會網(wǎng)絡(luò)在營銷實踐中的研究初探[A];中國高等院校市場學(xué)研究會2011年年會論文集[C];2011年

6 周尚意;吳莉萍;王策;;都市更新中社區(qū)社會網(wǎng)絡(luò)變遷的結(jié)構(gòu)主義分析——以北京西單南太常社區(qū)整體搬遷為例[A];中國地理學(xué)會百年慶典學(xué)術(shù)論文摘要集[C];2009年

7 陳忠衛(wèi);王志成;;社會資本對企業(yè)成長的推動作用分析[A];2004年中國管理科學(xué)學(xué)術(shù)會議論文集[C];2004年

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

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

10 郭彥麗;;社會網(wǎng)絡(luò)視角下組織內(nèi)部信息資源共享研究[A];信息資源配置理論與模型研究——2009信息化與信息資源管理學(xué)術(shù)研討會專集[C];2009年

相關(guān)重要報紙文章 前10條

1 本報記者 范昕;面對巨大的社會網(wǎng)絡(luò)，你無法獨(dú)立存在[N];文匯報;2013年

2 本報記者 蔡雙喜;家政服務(wù)員如何建構(gòu)社會網(wǎng)絡(luò)[N];中國婦女報;2013年

3 ;Google對搜索人感興趣[N];計算機(jī)世界;2004年

4 周麗萍;社會資本在保險業(yè)發(fā)展中的作用[N];中國保險報;2003年

5 席來旺;社會網(wǎng)絡(luò)提高競爭優(yōu)勢[N];人民日報;2007年

6 沈慧婷　本報記者 丁秀偉;從“擇偶途徑”看改革30年婚戀變遷[N];中國婦女報;2008年

7 北京大學(xué)博士后 山東大學(xué)教授 博導(dǎo) 李春霞;家政服務(wù)員的社會網(wǎng)絡(luò)及其城鄉(xiāng)差異[N];中國婦女報;2013年

8 賈利強(qiáng);人物研究須重視社會網(wǎng)絡(luò)與日常生活[N];中國社會科學(xué)報;2011年

9 梁捷;節(jié)點(diǎn)人際關(guān)系[N];經(jīng)濟(jì)觀察報;2012年

10 ;加強(qiáng)理論研究 推動社會發(fā)展[N];中國社會科學(xué)院報;2008年

相關(guān)博士學(xué)位論文 前10條

1 杜曉林;大規(guī)模社會網(wǎng)絡(luò)可視化若干問題及算法研究[D];哈爾濱工業(yè)大學(xué);2015年

2 李棟;在線社會網(wǎng)絡(luò)中信息擴(kuò)散研究[D];哈爾濱工業(yè)大學(xué);2014年

3 易成岐;社會網(wǎng)絡(luò)的信息傳播機(jī)制及控制方法研究[D];哈爾濱理工大學(xué);2016年

4 張伯雷;社會網(wǎng)絡(luò)信息傳播與影響力最大化研究[D];南京大學(xué);2016年

5 李文金;創(chuàng)業(yè)者社會網(wǎng)絡(luò)的演化過程研究[D];吉林大學(xué);2012年

6 裴志軍;社會網(wǎng)絡(luò)與經(jīng)濟(jì)發(fā)展[D];浙江大學(xué);2010年

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

8 高紅艷;社會網(wǎng)絡(luò)與“新生存空間”的生成[D];上海大學(xué);2007年

9 伍滿桂;創(chuàng)業(yè)企業(yè)網(wǎng)絡(luò)動態(tài)能力與創(chuàng)新社會網(wǎng)絡(luò)沃度研究[D];浙江大學(xué);2008年

10 黃亮;社會網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)與鏈接預(yù)測算法研究[D];華中科技大學(xué);2012年

相關(guān)碩士學(xué)位論文 前10條

1 吳迪;《在線社會網(wǎng)絡(luò)中產(chǎn)生信任評價的可信圖》翻譯實踐報告[D];內(nèi)蒙古大學(xué);2015年

2 于洋;國有企業(yè)高管社會網(wǎng)絡(luò)與企業(yè)創(chuàng)新行為關(guān)系研究[D];遼寧大學(xué);2015年

3 周新;建筑行業(yè)農(nóng)民工社會網(wǎng)絡(luò)對收入狀況的影響研究[D];西南交通大學(xué);2015年

4 閆晶星;基于敏感關(guān)系的社會網(wǎng)絡(luò)隱私保護(hù)方法研究[D];河北工程大學(xué);2015年

5 王美;社會網(wǎng)絡(luò)視角下的裝備制造業(yè)產(chǎn)業(yè)集群創(chuàng)新研究[D];集美大學(xué);2015年

6 杜宇;社會網(wǎng)絡(luò)對中小企業(yè)融資可獲性的作用[D];蘇州大學(xué);2015年

7 張玉志;社會網(wǎng)絡(luò)中知識流動的邏輯研究[D];西南大學(xué);2015年

8 王利娟;都市菜販的社會網(wǎng)絡(luò)建構(gòu)[D];西南大學(xué);2015年

9 李超;多維社會網(wǎng)絡(luò)上的信息挖掘問題研究[D];電子科技大學(xué);2014年

10 王詩懿;GraphLab云計算平臺下社會網(wǎng)絡(luò)的社區(qū)識別[D];寧波大學(xué);2015年

，

本文編號：1443956