隨著在線社交網(wǎng)絡的蓬勃發(fā)展,通過大數(shù)據(jù)分析用戶的行為屬性,面向目標用戶建立相應標簽的精準營銷和個性化推薦越來越具有應用價值。本文主要圍繞面向目標用戶的最小節(jié)點問題進行研究。本文采用用戶畫像區(qū)分目標用戶與非目標用戶,首先針對單一傳播環(huán)境下面向目標用戶的最小節(jié)點問題（NLC-TU）展開研究。NLC-TU問題旨在尋求最小的初始種子節(jié)點集,使得初始種子節(jié)點集的信息傳播范圍可以覆蓋目標用戶群體中預期數(shù)量的用戶�？紤]社交網(wǎng)絡中節(jié)點傳播能力的不同,本文提出了受限傳播模型（LD-IC）,證明了在該模型下NLC-TU問題是NP-hard問題,并且NLC-TU問題的信息傳播函數(shù)在LD-IC模型下具有單調(diào)性和子模性。本文提出貪心算法來解決這個問題并且分析了貪心算法的精度保證。然而貪心算法耗時長,難以應用于大型社交網(wǎng)絡�？紤]到在LD-IC模型下節(jié)點的局部影響力可以近似表示全局影響力,面向目標節(jié)點的局部影響力啟發(fā)式算法（TU-LIH）被提出。在四個真實社交網(wǎng)絡上的實驗證明了我們提出的算法高效且具有可拓展性。隨后,考慮現(xiàn)實網(wǎng)絡中信息傳播的復雜性,本文在NLC-TU問題的基礎(chǔ)上針對競爭環(huán)境下面向目標用戶的最小節(jié)點問... 

【文章來源】：上海交通大學上海市 211工程院校 985工程院校 教育部直屬院校

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

【學位級別】：碩士

【部分圖文】：

在線社交網(wǎng)絡抽象成拓撲圖

上海交通大學碩士學位論文-10-圖2-2用戶畫像來源Fig.2-2userprofile2.3單一傳播環(huán)境下最小節(jié)點問題的研究病毒式營銷中的影響力最大化問題最先受到研究者的關(guān)注。Kempe等人[7]總結(jié)了影響力傳播的經(jīng)典模型獨立級聯(lián)模型，在這種模型下影響力最大化問題是NP-hard問題可用貪心算法求解，并且貪心算法可提供(11e)的精度保證。此后在影響力最大化問題的基礎(chǔ)上，又衍生了最小節(jié)點問題。Long,Cheng[4]首次提出了J-MIN-Seed問題，并證明它在IC傳播模型下是NP-hard問題，可用貪心算法求解。最小節(jié)點問題本質(zhì)上是影響力最大化的對偶問題，因此很多影響力最小化問題的性質(zhì)得以在最小節(jié)點的問題中沿用。此后，一部分研究者致力于研究更普遍場景下的最小節(jié)點問題，Goyal[5]提出了影響力傳播的最小時間和最小預算問題，針對不同的傳播時間限制和預算限制控制變量分別進行了研究。Zhang,Peng[6]引入了概率P，研究了以概率P覆蓋一定范圍的最小節(jié)點問題，更加貼近現(xiàn)實情況。Kai等人[32]研究了在線社交網(wǎng)絡中的最小成本種子選擇問題，其目標是選擇一組總成本最小的種子節(jié)點，使網(wǎng)絡中受影響節(jié)點的預期數(shù)量超過預定義的閾值，根據(jù)傳染模型提出了雙準則近似算法。上述研究從初始用戶選擇出發(fā)研究了最小的代價問題，將所有用戶無差別的看待。近年來隨著大數(shù)據(jù)的興起，研究者開始

上海交通大學碩士學位論文-15-速傳播，而粉絲數(shù)不多的普通賬號發(fā)布的信息往往沒有獲得關(guān)注[41]。因此我們考慮信息在社交網(wǎng)絡中用戶傳播能力的不同，提出受限傳播模型（limited-diffusion-IC，LD-IC）。在LD-IC模型中，信息不會無限的傳播下去，種子節(jié)點的影響只能傳播有限的深度。給定社交網(wǎng)絡G，其中每一條邊(,)∈E都有個激活概率(,)，此時是的入度鄰居，是的出度鄰居。信息從節(jié)點1出發(fā)傳遞到節(jié)點可能存在多種傳播路徑。對于一個信息傳播路徑P=(1→2→→1→)，我們定義這條信息傳播路徑的傳播概率是Pa()：Pa(P)=∏p(ui,ui+1)m1i=1(3-1)式中(ui,ui+1)——節(jié)點ui被激活后，節(jié)點ui通過邊(ui,ui+1)激活ui+1的概率。路徑越長，節(jié)點越多，則信息從u1傳遞到um的概率Pa(P)越小，因此我們引入閾值θ，θ代表了路徑最小傳播概率，一旦Pa(P)<θ時信息傳播終止，即Pa(P)=∏p(ui,ui+1)m1i=1≥θ時信息才會從節(jié)點u1沿路徑P傳播到節(jié)點um。圖3-1IC模型和LD-IC模型的不同F(xiàn)ig.3-1DifferenceofinformationpropagationbetweentheICandtheLD-IC如圖3-1所示。圖中黑色的點代表被激活后處于活躍狀態(tài)，白色的點代表還沒有被激活處于非活躍態(tài)，每條邊都有一個激活概率。在IC模型中信息傳播不受

【參考文獻】：
期刊論文
[1]社交網(wǎng)絡影響力傳播研究[J]. 陳衛(wèi).  大數(shù)據(jù). 2015(03)



本文編號：3425144