實(shí)驗(yàn)室薛軟件工程

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

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

∈[0,1]，這個(gè)閾值代表了為使其轉(zhuǎn)變?yōu)榧せ顮顟B(tài)其居節(jié)點(diǎn)所需的影響權(quán)重。在過(guò)程中，可以描述為：在時(shí)刻t，所有在t-1處于激活狀態(tài)的節(jié)點(diǎn)依然保持激活，對(duì)于某個(gè)未激活節(jié)點(diǎn)v，其處于激活狀態(tài)的鄰居的權(quán)重和大于等于其閾值，則v。即A(v)vv的閾值代表了當(dāng)其鄰居接受新想法的時(shí)候節(jié)點(diǎn)v也接受的一種難易程度。最大化算貪心算節(jié)點(diǎn)個(gè)數(shù)k最大k個(gè)節(jié)點(diǎn)傳統(tǒng)貪心算法（又稱貪婪算法）：在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選為k的初始集合。mpe為-e-ε，其中e為自然基g節(jié)點(diǎn)個(gè)數(shù)k最大k個(gè)節(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算法：去掉對(duì)沒(méi)有影響的邊得到小網(wǎng)絡(luò)，在小網(wǎng)絡(luò)上做，啟發(fā)式算High-Degree啟發(fā)算基于High-Degree的啟發(fā)算法：在復(fù)雜網(wǎng)絡(luò)中以度數(shù)遞減的順序選擇k個(gè)最大度數(shù)節(jié)Distance-Centrality啟發(fā)算基于Distance-Centrality的啟發(fā)式算法：將節(jié)點(diǎn)之間的路徑長(zhǎng)度作為評(píng)價(jià)尺度，該算是按照節(jié)點(diǎn)與其他節(jié)點(diǎn)之間平均距離遞增的順序，選擇前kDegreeDiscount算法：當(dāng)一個(gè)節(jié)點(diǎn)u的鄰居節(jié)點(diǎn)中有一些節(jié)點(diǎn)已經(jīng)被選作為初始的節(jié)點(diǎn)，在選取下一個(gè)度數(shù)最大的節(jié)點(diǎn)時(shí)，對(duì)u的度數(shù)重新計(jì)算，最后再選出打折后度數(shù)最大的節(jié)常用最大化算法時(shí)間復(fù)雜度比算時(shí)間復(fù)雜RamdomO(slog(n)+O(slog(n)+CELFGreedy表 最大化典型算法時(shí)間復(fù)雜度比啟發(fā)式算貪婪算基于社團(tuán)結(jié)只是局部最優(yōu)表4.2最大化算法優(yōu)劣比啟發(fā)式和貪婪類算法存在許多不足之處。首先，這些算法大都是基于整個(gè)網(wǎng)針對(duì)以上問(wèn)題，后續(xù)提出了一種基于社區(qū)結(jié)構(gòu)的最大化算法。社區(qū)結(jié)構(gòu)是社會(huì)部戶)。結(jié)自從最大化問(wèn)題這個(gè)概念提出至今，研究者們已經(jīng)從多個(gè)方向和角度對(duì)其做了“多。由于現(xiàn)實(shí)網(wǎng)絡(luò)規(guī)模龐大，最大化問(wèn)題是一個(gè)-ad問(wèn)題，難以在多項(xiàng)式時(shí)間傳統(tǒng)的算法都是基于單一的網(wǎng)絡(luò)結(jié)構(gòu)和模型來(lái)展開(kāi)研究的，而現(xiàn)實(shí)網(wǎng)絡(luò)結(jié)構(gòu)卻是的的。實(shí)際網(wǎng)絡(luò)中“競(jìng)爭(zhēng)無(wú)處不在”，傳統(tǒng)的算法都是以單一“源”為背景展開(kāi)研究的，可基的。網(wǎng)絡(luò)信息是瞬息萬(wàn)變的，網(wǎng)絡(luò)結(jié)構(gòu)也是不斷動(dòng)態(tài)演化的，因而從動(dòng)態(tài)社會(huì)網(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