實驗室薛軟件工程

社會網(wǎng)絡(luò)中最大化模型的研究與分薛丹（蘭州大學(xué)信息科學(xué)與，蘭州致力于社交網(wǎng)絡(luò)的分析，社交網(wǎng)絡(luò)中的問題的研究具有很實際的現(xiàn)實意義，它在市場、廣告發(fā)布、以及社會安定等方面有十分重要的應(yīng)用。因此，本文對社交網(wǎng)絡(luò)最大化問題的定義、模型和算法的研究現(xiàn)狀進(jìn)行了調(diào)研分析，希望對社交網(wǎng)絡(luò)最大化問題有一個整體的認(rèn)識。:社交網(wǎng)絡(luò)；最大化；模型；貪心算法隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，越來越多的虛擬社會相繼出現(xiàn)，如大型社交網(wǎng)絡(luò)、通過它在市場、發(fā)布、以及社會安定等方面有十分重要的應(yīng)用。絡(luò)個代價中。、影業(yè)都傾向于利用現(xiàn)實社會中的社會網(wǎng)絡(luò)（例如國內(nèi)的人人、新浪，國外的、）中的社交關(guān)系來做“口碑（dfuth）”亦或式來推廣產(chǎn)品，都。于碑的，些對于最大化問題的研究，不僅有著深刻的理論意義，還可以幫助我們有效地控,最大化問在實際應(yīng)用中可以映射為策略：選取一個大小為k的子集使用新產(chǎn)品，進(jìn)而最大化問題的符號描述為：給定GV，E)和常數(shù)k≦|V|，V代表為社會網(wǎng)絡(luò)中節(jié)點(diǎn)，E代表之間的關(guān)系。如果初始節(jié)點(diǎn)集合為S，過程結(jié)束后預(yù)期激活節(jié)點(diǎn)集合為T=σ(A)，找出節(jié)點(diǎn)集合S?V且|S|=k，使得范圍σ(A)最大。經(jīng)典模最大化問題中最基本的兩個模型是獨(dú)立級聯(lián)模型和線性閾值模型。這兩個模型在實現(xiàn)最大化的問題上都是NP-Hard；同時兩個模型的結(jié)果函數(shù)σ(A)是一個子獨(dú)立級聯(lián)模型獨(dú)立級聯(lián)模型（IndependentCascade）基于這樣一個假設(shè)：的可以看做一次獨(dú)（inactive，v被激活之后，它將以概Pv,www被激活之后，同樣，其也會以概Pw,uw的鄰u。（節(jié)點(diǎn)被激活后，將一直保持激活狀態(tài)，不會從激活狀態(tài)變成未 圖3.1獨(dú)立級聯(lián)模型假 圖3.2線性閾值模型假線性閾值模型影響，每個鄰居對其影響的權(quán)重為bvw，并且有：

bv,w假設(shè)每個節(jié)點(diǎn)都有一個閾

∈[0,1]，這個閾值代表了為使其轉(zhuǎn)變?yōu)榧せ顮顟B(tài)其居節(jié)點(diǎn)所需的影響權(quán)重。在過程中，可以描述為：在時刻t，所有在t-1處于激活狀態(tài)的節(jié)點(diǎn)依然保持激活，對于某個未激活節(jié)點(diǎn)v，其處于激活狀態(tài)的鄰居的權(quán)重和大于等于其閾值，則v。即A(v)vv的閾值代表了當(dāng)其鄰居接受新想法的時候節(jié)點(diǎn)v也接受的一種難易程度。最大化算貪心算節(jié)點(diǎn)個數(shù)k最大k個節(jié)點(diǎn)傳統(tǒng)貪心算法（又稱貪婪算法）：在對問題求解時，總是做出在當(dāng)前看來是最好的選為k的初始集合。mpe為-e-ε，其中e為自然基g節(jié)點(diǎn)個數(shù)k最大k個節(jié)點(diǎn)Algorithm1GeneralGreedy(G,k)1:initializeSandR20002:fori1to foreachvertexvV\S sv fori1toR svRanCasS end svsv/ end SSargmaxvV\Ssv11:end12:outputCELF算法：利用子模性質(zhì)去除邊際效益遞減的節(jié)點(diǎn)，從而大大降低網(wǎng)絡(luò)節(jié)點(diǎn)間影響NewGreedy算法：去掉對沒有影響的邊得到小網(wǎng)絡(luò)，在小網(wǎng)絡(luò)上做，啟發(fā)式算High-Degree啟發(fā)算基于High-Degree的啟發(fā)算法：在復(fù)雜網(wǎng)絡(luò)中以度數(shù)遞減的順序選擇k個最大度數(shù)節(jié)Distance-Centrality啟發(fā)算基于Distance-Centrality的啟發(fā)式算法：將節(jié)點(diǎn)之間的路徑長度作為評價尺度，該算是按照節(jié)點(diǎn)與其他節(jié)點(diǎn)之間平均距離遞增的順序，選擇前kDegreeDiscount算法：當(dāng)一個節(jié)點(diǎn)u的鄰居節(jié)點(diǎn)中有一些節(jié)點(diǎn)已經(jīng)被選作為初始的節(jié)點(diǎn)，在選取下一個度數(shù)最大的節(jié)點(diǎn)時，對u的度數(shù)重新計算，最后再選出打折后度數(shù)最大的節(jié)常用最大化算法時間復(fù)雜度比算時間復(fù)雜RamdomO(slog(n)+O(slog(n)+CELFGreedy表 最大化典型算法時間復(fù)雜度比啟發(fā)式算貪婪算基于社團(tuán)結(jié)只是局部最優(yōu)表4.2最大化算法優(yōu)劣比啟發(fā)式和貪婪類算法存在許多不足之處。首先，這些算法大都是基于整個網(wǎng)針對以上問題，后續(xù)提出了一種基于社區(qū)結(jié)構(gòu)的最大化算法。社區(qū)結(jié)構(gòu)是社會部戶)。結(jié)自從最大化問題這個概念提出至今，研究者們已經(jīng)從多個方向和角度對其做了“多。由于現(xiàn)實網(wǎng)絡(luò)規(guī)模龐大，最大化問題是一個-ad問題，難以在多項式時間傳統(tǒng)的算法都是基于單一的網(wǎng)絡(luò)結(jié)構(gòu)和模型來展開研究的，而現(xiàn)實網(wǎng)絡(luò)結(jié)構(gòu)卻是的的。實際網(wǎng)絡(luò)中“競爭無處不在”，傳統(tǒng)的算法都是以單一“源”為背景展開研究的，可基的。網(wǎng)絡(luò)信息是瞬息萬變的，網(wǎng)絡(luò)結(jié)構(gòu)也是不斷動態(tài)演化的，因而從動態(tài)社會網(wǎng)絡(luò)中獲得響最和且降相關(guān)文［1］KimuraM,SaitoK.TractableModelsforInformationDiffusioninSocialNetworks[M]KnowledgeDiscoveryinDatabases:PKDD2006.SpringerBerlinHeidelberg,2006:259-271.［2］ZhuT,WangB,WuB,et izingthespreadofinfluencerankinginsocial［3］WangY,CongG,SongG,etal.Community-basedgreedyalgorithmforminingtop-Kinfluentialnodesinsocialnetworks[C]//ACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.ACM,2010:1039-1048.［4］MooresG,ShakarianP,MacdonaldB,etal.FindingNear-OptimalGroupsofEpidemicSpreadersinaComplexNetwork[J].PlosOne,2014,9(4):e90303.［5］SaitoK,KimuraM,OharaK,etal.EfficientdiscoveryofinfluentialnodesforSISmodelsinsocialKnowledge&InformationSystems,2012,30(3):613- WangF,DuH,CamachoE,etal.Onpositiveinfluencedominatingsetsinsocialnetworks[J].TheoreticalComputerScience,2011,412(3):265-269. ZhangX,ZhuJ,WangQ,etal.Identifyinginfluentialnodesincomplexnetworkswithcommunitystructure[J].Knowledge-BasedSystems,2013,42(2):74-84. WangC,ChenW,WangY.Scalableinfluence izationforindependentcascademodelinlarge-scalesocialnetworks[J].DataMining&KnowledgeDiscovery,2012,25(3):545-576. WANG,Xiaofan,Xiang,等.網(wǎng)絡(luò)科學(xué)導(dǎo)論[J].高等教育,［10］KempeD,KleinbergJ,Tardos,&#. izingthespreadofinfluencethroughasocialnetwork[C]//ACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.ACM,2003:137--146. MEJ.Thestructureandfunctionofcomple