近年來,社交網(wǎng)絡(luò)分析成為人們研究的熱點,通過社交網(wǎng)絡(luò)分析,可以挖掘隱藏在網(wǎng)絡(luò)中的重要信息,其中在社交網(wǎng)絡(luò)分析中的一個研究熱點就是社交影響力最大化問題。然而在這個研究領(lǐng)域中,大部分學者僅僅關(guān)注于影響力最大化,而忽視了被影響群體的多樣性,而在實際營銷中,商家更傾向于選擇多樣化的目標受眾以推廣新產(chǎn)品。除此之外,大部分學者在研究社交影響力最大化問題時忽視了節(jié)點成本的重要性,對于市場營銷而言,在期望獲得影響力最大化的同時營銷的成本可以最小化。為了解決上述兩個重要問題,本文將研究基于重疊社團檢測的社交影響力最大化的多目標方法。之所以采用重疊社團檢測技術(shù),是因為重疊社團中的重疊點起著“橋梁”的作用,可以使得信息在不同的社團之間傳播,因此被影響的節(jié)點的分布會更加多樣化;同時,利用重疊社團結(jié)構(gòu)信息可以挖掘網(wǎng)絡(luò)中性價比（影響力/成本）高的節(jié)點,為用戶提供影響力大成本小的種子節(jié)點。因此,本文在社交影響力最大化問題上分別考慮節(jié)點多樣性和成本,提出了基于重疊社團檢測的多樣性影響力最大化進化算法和基于重疊社團檢測的成本最小化影響力最大化進化算法。本文的主要研究工作如下:（1）本文提出了基于重疊社團檢測的多樣性影響... 

【文章來源】：安徽大學安徽省 211工程院校

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

【學位級別】：碩士

【部分圖文】：

在線社交網(wǎng)絡(luò)示例圖

第二章相關(guān)工作與理論基礎(chǔ)102.2.2線性閾值模型線性閾值模型（LinearThresholdModel）簡稱LT模型，它是基于隨機擴散的一種模型，設(shè)定網(wǎng)絡(luò)中每個節(jié)點都有一個激活的閾值∈[0,1]，表示節(jié)點被激活的臨界值。節(jié)點的鄰居節(jié)點()對該節(jié)點的影響力滿足以下公式：∑≤1∈(),(2.2)與IC模型不同的是，線性閾值模型假定多個節(jié)點對同一個節(jié)點的影響力是可以累加的，當節(jié)點的影響力累加值大于它的閾值，即∑≥∈()此節(jié)點就會被激活，一直重復(fù)這個過程直到網(wǎng)絡(luò)中沒有新的激活節(jié)點產(chǎn)生。2.3重疊社團檢測的相關(guān)理論社團結(jié)構(gòu)，即將網(wǎng)絡(luò)中的節(jié)點被劃分為若干個不同的集合，同時每個集合內(nèi)部節(jié)點之間的連邊相對緊密，而不同集合節(jié)點之間的連邊相對稀疏[40]。例如，在社交網(wǎng)絡(luò)中，具有相似愛好的人形成一個社團；在蛋白質(zhì)網(wǎng)絡(luò)中，不同類別的蛋白質(zhì)形成各個功能模塊；在科學家合作網(wǎng)絡(luò)中，不同的研究領(lǐng)域形成不同的社團。類似地，重疊社團中的節(jié)點可能屬于一個社團，也可能屬于多個社團，屬于多個社團的節(jié)點被稱為重疊點。下面給出重疊社團[41]的詳細定義：定義2.2（重疊社團）：定義一個無向無權(quán)的網(wǎng)絡(luò)(,)，把網(wǎng)絡(luò)分成={1,2,...,}，共個社團，對于任意(1≤≤)滿足≠且存在≠，(1≤≤,1≤≤,≠)，=1=。即網(wǎng)絡(luò)中的節(jié)點可以屬于多個社團。圖2.1重疊社團結(jié)構(gòu)示例Fig.2.1Exampleofoverlappingcommunitystructure圖2.1中，可以看出有兩個社團1={1,2,3,4}，2={4,5,6,7}，其中節(jié)點4屬于在兩個社團中。因此節(jié)點4是重疊點，則1和2是重疊社團。本文采用經(jīng)典的重疊社團檢測算法SLPA（Speaker-listenerLabelPropagation

第二章相關(guān)工作與理論基礎(chǔ)12定義2.6（Pareto前沿面）：Pareto前沿面即PaS中所有Pareto最優(yōu)解在目標空間上的映射，記為={F()|∈}。本文采用經(jīng)典的多目標進化算法NSGA-II[49]為框架，下面將對該算法做出相關(guān)介紹。通常利用進化算法求解多目標優(yōu)化問題，多目標進化算法是通過模擬生物在自然界的進化過程而形成的搜索方法，其中NSGA-II是多目標進化算法中經(jīng)典的算法之一。NSGA-II算法是在NSGA算法[50]基礎(chǔ)上的改進版本。NSGA采用非支配排序方法，可以使好的個體有更大的機會保留到下一代，同時提出適應(yīng)度共享策略，使Pareto前沿面上的個體分布均勻，確保群體的多樣性，防止過早收斂。但是NSGA算法中非支配排序時間復(fù)雜度較高，為（3）（m是目標數(shù)量，N是種群大小）。2002年Deb等人提出了NSGA-II，為了降低時間復(fù)雜度，首先提出了快速非支配排序方法，將時間復(fù)雜度降低到（2），大大地縮短了搜索時間。除此之外，NSGA-II引入精英保留策略，將父代和子代種群中非支配的個體保留下來，從而保證了種群的質(zhì)量。最后，利用擁擠距離選擇算子來保證種群的多樣性。由于NSGA-II中巧妙的策略，該算法比NSGA有更高的計算效率，并且NSGA-II也已成為對比算法中的基準算法。多目標進化算法一般分為以下部分，如圖2.2所示。首先，初始化種群，即產(chǎn)生一個初始的種群；然后，利用交叉變異操作產(chǎn)生子代。最后，利用環(huán)境選擇機制，在父代和子代種群中選擇生成下一代種群。圖2.2多目標進化算法流程示例Fig.2.2Theflowchartofmulti-objectiveevolutionaryalgorithm

【參考文獻】：
期刊論文
[1]交易型社區(qū)的病毒式營銷策略:基于社會影響、同質(zhì)性和網(wǎng)絡(luò)拓撲結(jié)構(gòu)的ABMS仿真研究[J]. 肖邦明,黃敏學.  營銷科學學報. 2015(01)
[2]社交網(wǎng)絡(luò)影響力研究綜述[J]. 丁兆云,賈焰,周斌,唐府.  計算機科學. 2014(01)
[3]多目標進化算法綜述[J]. 張福威,李軍,孟品超,姜志俠,李延忠.  長春理工大學學報(自然科學版). 2012(03)

碩士論文
[1]群集智能優(yōu)化算法的研究[D]. 王冬梅.武漢科技大學 2004



本文編號：3482837