实验室薛软件工程

社会网络中最大化模型的研究与分薛丹（兰州大学信息科学与，兰州致力于社交网络的分析，社交网络中的问题的研究具有很实际的现实意义，它在市场、广告发布、以及社会安定等方面有十分重要的应用。因此，本文对社交网络最大化问题的定义、模型和算法的研究现状进行了调研分析，希望对社交网络最大化问题有一个整体的认识。:社交网络；最大化；模型；贪心算法随着互联网技术的发展，越来越多的虚拟社会相继出现，如大型社交网络、通过它在市场、发布、以及社会安定等方面有十分重要的应用。络个代价中。、影业都倾向于利用现实社会中的社会网络（例如国内的人人、新浪，国外的、）中的社交关系来做“口碑（dfuth）”亦或式来推广产品，都。于碑的，些对于最大化问题的研究，不仅有着深刻的理论意义，还可以帮助我们有效地控,最大化问在实际应用中可以映射为策略：选取一个大小为k的子集使用新产品，进而最大化问题的符号描述为：给定GV，E)和常数k≦|V|，V代表为社会网络中节点，E代表之间的关系。如果初始节点集合为S，过程结束后预期激活节点集合为T=σ(A)，找出节点集合S⊆V且|S|=k，使得范围σ(A)最大。经典模最大化问题中最基本的两个模型是独立级联模型和线性阈值模型。这两个模型在实现最大化的问题上都是NP-Hard；同时两个模型的结果函数σ(A)是一个子独立级联模型独立级联模型（IndependentCascade）基于这样一个假设：的可以看做一次独（inactive，v被激活之后，它将以概Pv,www被激活之后，同样，其也会以概Pw,uw的邻u。（节点被激活后，将一直保持激活状态，不会从激活状态变成未 图3.1独立级联模型假 图3.2线性阈值模型假线性阈值模型影响，每个邻居对其影响的权重为bvw，并且有：

bv,w假设每个节点都有一个阈

∈[0,1]，这个阈值代表了为使其转变为激活状态其居节点所需的影响权重。在过程中，可以描述为：在时刻t，所有在t-1处于激活状态的节点依然保持激活，对于某个未激活节点v，其处于激活状态的邻居的权重和大于等于其阈值，则v。即A(v)vv的阈值代表了当其邻居接受新想法的时候节点v也接受的一种难易程度。最大化算贪心算节点个数k最大k个节点传统贪心算法（又称贪婪算法）：在对问题求解时，总是做出在当前看来是最好的选为k的初始集合。mpe为-e-ε，其中e为自然基g节点个数k最大k个节点Algorithm1GeneralGreedy(G,k)1:initializeSandR20002:fori1to foreachvertexvV\S sv fori1toR svRanCasS end svsv/ end SSargmaxvV\Ssv11:end12:outputCELF算法：利用子模性质去除边际效益递减的节点，从而大大降低网络节点间影响NewGreedy算法：去掉对没有影响的边得到小网络，在小网络上做，启发式算High-Degree启发算基于High-Degree的启发算法：在复杂网络中以度数递减的顺序选择k个最大度数节Distance-Centrality启发算基于Distance-Centrality的启发式算法：将节点之间的路径长度作为评价尺度，该算是按照节点与其他节点之间平均距离递增的顺序，选择前kDegreeDiscount算法：当一个节点u的邻居节点中有一些节点已经被选作为初始的节点，在选取下一个度数最大的节点时，对u的度数重新计算，最后再选出打折后度数最大的节常用最大化算法时间复杂度比算时间复杂RamdomO(slog(n)+O(slog(n)+CELFGreedy表 最大化典型算法时间复杂度比启发式算贪婪算基于社团结只是局部最优表4.2最大化算法优劣比启发式和贪婪类算法存在许多不足之处。首先，这些算法大都是基于整个网针对以上问题，后续提出了一种基于社区结构的最大化算法。社区结构是社会部户)。结自从最大化问题这个概念提出至今，研究者们已经从多个方向和角度对其做了“多。由于现实网络规模庞大，最大化问题是一个-ad问题，难以在多项式时间传统的算法都是基于单一的网络结构和模型来展开研究的，而现实网络结构却是的的。实际网络中“竞争无处不在”，传统的算法都是以单一“源”为背景展开研究的，可基的。网络信息是瞬息万变的，网络结构也是不断动态演化的，因而从动态社会网络中获得响最和且降相关文［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,等.网络科学导论[J].高等教育,［10］KempeD,KleinbergJ,Tardos,&#. izingthespreadofinfluencethroughasocialnetwork[C]//ACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.ACM,2003:137--146. MEJ.Thestructureandfunctionofcomple