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

【摘要】：隨著互聯(lián)網(wǎng)的普及和在線(xiàn)社會(huì)網(wǎng)絡(luò)的發(fā)展,研究者可以獲取豐富的歷史數(shù)據(jù),并對(duì)社會(huì)網(wǎng)絡(luò)中的信息傳播進(jìn)行分析、預(yù)測(cè)和利用。作為一種新型的媒介,社會(huì)網(wǎng)絡(luò)中的信息可以像“病毒”一樣迅速地在人與人之間傳播,因此受到了普遍的關(guān)注：一方面,相比于電臺(tái)、報(bào)紙、電視等大眾傳媒廣播的方式,社會(huì)網(wǎng)絡(luò)中的信息傳播具有“口口相傳”的效應(yīng),更容易被人們所信任；另一方面,信息的傳播還可能具有級(jí)聯(lián)效應(yīng),造成廣泛的影響。然而,社會(huì)網(wǎng)絡(luò)中難以預(yù)測(cè)的個(gè)體行為和復(fù)雜的拓?fù)浣Y(jié)構(gòu),為信息傳播的分析和利用帶來(lái)了極大的挑戰(zhàn)。因此,如何通過(guò)歷史數(shù)據(jù)挖掘,對(duì)信息傳播進(jìn)行分析預(yù)測(cè),并進(jìn)一步利用信息傳播達(dá)到影響力最大化,為企業(yè)宣傳、廣告營(yíng)銷(xiāo)、輿情監(jiān)控等提供決策輔助,已成為當(dāng)前社會(huì)網(wǎng)絡(luò)研究的一個(gè)熱點(diǎn)問(wèn)題。針對(duì)上述問(wèn)題,本文首先對(duì)信息級(jí)聯(lián)的結(jié)構(gòu)進(jìn)行挖掘,識(shí)別出社會(huì)網(wǎng)絡(luò)信息級(jí)聯(lián)幾種典型結(jié)構(gòu)模式,并利用結(jié)構(gòu)模式對(duì)信息傳播進(jìn)行預(yù)測(cè)；然后基于信息傳播的模式,分析了多種信息同時(shí)傳播的交互模型,用信息回溯的方法找到最有影響力的節(jié)點(diǎn)；最后研究了在給定預(yù)算的情況下,如何通過(guò)預(yù)算分配來(lái)激勵(lì)這些最有影響力的節(jié)點(diǎn),從而使得影響力的擴(kuò)散可以達(dá)到最大。論文的主要貢獻(xiàn)可概括如下：(1)分析信息傳播的級(jí)聯(lián)結(jié)構(gòu),并通過(guò)級(jí)聯(lián)結(jié)構(gòu)預(yù)測(cè)信息未來(lái)的傳播模式。在社會(huì)網(wǎng)絡(luò)中,信息級(jí)聯(lián)的結(jié)構(gòu)往往和信息傳播互相影響。首先,不同機(jī)制所驅(qū)動(dòng)的信息傳播會(huì)導(dǎo)致結(jié)構(gòu)不同的級(jí)聯(lián),同質(zhì)性主導(dǎo)的級(jí)聯(lián)往往會(huì)發(fā)展為寬而淺的結(jié)構(gòu),而社會(huì)影響力主導(dǎo)的級(jí)聯(lián)則會(huì)變得深而復(fù)雜；其次,不同結(jié)構(gòu)的信息級(jí)聯(lián)會(huì)傳播到不同的范圍和社群,從而影響信息的傳播過(guò)程。本文采用數(shù)據(jù)驅(qū)動(dòng)的方法,分析了大量信息級(jí)聯(lián)的傳播結(jié)構(gòu),通過(guò)對(duì)信息級(jí)聯(lián)的結(jié)構(gòu)進(jìn)行降維嵌入(embedding)和譜聚類(lèi)(spectral clustering)，識(shí)別出社會(huì)網(wǎng)絡(luò)中的信息級(jí)聯(lián)五種典型的結(jié)構(gòu)模式,并且發(fā)現(xiàn)不同結(jié)構(gòu)模式的信息級(jí)聯(lián)之間具有明顯差異的特征。根據(jù)以上觀察,本文引入級(jí)聯(lián)結(jié)構(gòu)來(lái)預(yù)測(cè)信息未來(lái)的傳播模式,實(shí)驗(yàn)結(jié)果表明,該方法可以顯著提升預(yù)測(cè)的準(zhǔn)確率。(2)研究了多種信息同時(shí)傳播的交互模型,并識(shí)別其中有影響力的節(jié)點(diǎn)。社會(huì)網(wǎng)絡(luò)中往往有多種信息在同時(shí)傳播,而且信息之間可能存在競(jìng)爭(zhēng)、互利等交互關(guān)系。針對(duì)這種情況,本文設(shè)計(jì)了交互信息級(jí)聯(lián)模型來(lái)刻畫(huà)多種信息之間的傳播,可以同時(shí)考慮信息之間的交互關(guān)系和用戶(hù)對(duì)交互信息的選擇偏好。在這個(gè)模型下,本文首先證明了該問(wèn)題是NP難的,并提出了一種基于回溯的馬爾科夫隨機(jī)游走(markov random walk)算法：假設(shè)信息傳播可以達(dá)到所有節(jié)點(diǎn),然后通過(guò)傳播模型進(jìn)行回溯,找出信息最有可能的來(lái)源,即為影響力最大的節(jié)點(diǎn)。模擬實(shí)驗(yàn)表明,相比于其它常用的算法,本文提出的算法可以在絕大多數(shù)情況下取得最好的效果。同時(shí),該算法還可以快速地收斂,因此有很高的運(yùn)行效率。(3)提出了一個(gè)基于預(yù)算分配的策略,通過(guò)激勵(lì)社會(huì)網(wǎng)絡(luò)中的初始用戶(hù)實(shí)現(xiàn)影響力最大化。為了激勵(lì)初始用戶(hù)實(shí)現(xiàn)影響力最大化,以往的工作一般理想地假設(shè)用戶(hù)具有確定的估值,只有分配的預(yù)算高于該估值,用戶(hù)才會(huì)成為初始用戶(hù)；而在實(shí)際情況中,在不同的預(yù)算下,用戶(hù)都有可能成為初始用戶(hù)。本文使用效用函數(shù)(utility function)來(lái)刻畫(huà)用戶(hù)的滿(mǎn)意度,假定用戶(hù)的估值滿(mǎn)足一定的概率分布函數(shù)。在這個(gè)模型下,通過(guò)歸約證明了該問(wèn)題的難度。同時(shí),提出了一個(gè)離散貪心的算法來(lái)找出預(yù)算分配的方案：首先將預(yù)算均勻地離散化,然后采用迭代的方式將預(yù)算依次分配給具有邊際增益最大的用戶(hù)。該方法可以在離散的設(shè)置中取得近似最優(yōu)的結(jié)果。進(jìn)一步,本文還證明了當(dāng)合理地選擇一個(gè)離散的粒度后,該算法可以在預(yù)算連續(xù)的設(shè)置下取得1-1/e-o(1)的性能保證。最后,本文還通過(guò)更新邊際增益的計(jì)算和估算傳播概率的方法來(lái)提升算法的執(zhí)行效率。實(shí)驗(yàn)結(jié)果表明,相比于其它已有的方法,離散貪心的算法能顯著提高信息覆蓋的范圍,同時(shí)還有非常好的可擴(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é)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類(lèi)號(hào)】：G206;TP301.6

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 周麗萍;社會(huì)資本在保險(xiǎn)業(yè)發(fā)展中的作用[N];中國(guó)保險(xiǎn)報(bào);2003年

5 席來(lái)旺;社會(huì)網(wǎng)絡(luò)提高競(jìng)爭(zhēng)優(yōu)勢(shì)[N];人民日?qǐng)?bào);2007年

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

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

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

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

10 ;加強(qiáng)理論研究 推動(dòng)社會(huì)發(fā)展[N];中國(guó)社會(huì)科學(xué)院報(bào);2008年

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號(hào)：1443956