社交网络影响力最大化研究综述(2)

居重叠的情况，尽可能将这些初始的节点分散。SCG算法中定义每个节点的邻居节点为与它的最短路径?m（m可以自己设定）的节点集合，这样在选择第一个度数最大的节点之后，将这个节点的邻居节点排除，然后从剩余的节点中选择度数第二大的节点。依次下去，这样保证选取的初始度数最大的节点不会出现邻居重叠的情况，有效的提高了节点的传播。实验结果表明它的时间复杂度比贪心算法要低很多，效果比简单的选择前k个度数最大算法要好。

中心度是分析社会网络的一个最重要的和常用的概念工具之一。它是关于行动者在社会网络中的中心性位置的测量概念，反映的是行动者在社会网络结构中的位置或优势的差异。在一个社会网络中，某节点度数最高，该点就居于中心位置，这表明该点所对应的行动者为此网络中的中心人物即最具影响力的人物[20]。在社会网络和其它网络中，以度数递减的顺序选择k个最大度数节点的启发式节点选择策略，是长期以来的一个标准方法，在社会科学中被称为“度中心性”。此方法的一个缺点就是静态选择初始节点，没有考虑影响的扩散过程，不能保证最终影响范围最优。 3.3 基于社区的影响力最大化算法

基于社区的影响力最大化算法主要利用现有的社区发现算法，将网络分成若干个社区，然后在每个独立的社区上应用已有的影响力最大化算法求解，Galstyan等[21]第一次提出了利用网络的社区性质来求解影响力最大化问题。Galstyan虽然使用了社区性质来求解问题，但是方法只是局限在由两个松散社区组成的随机网络，这种选取方法有很多局限性，因为很多的社交网络都不止两个社区。OASNET算法和CGA算法是目前两种应用社区发现算法来求解影响力最大化问题的算法。 3.3.1 OASNET算法

OASNET算法[22]利用网络的社区性质把影响力最大化问题看成一种最优的资源动态分配问题而提出的一种算法，利用社区发现算法[23]将网络划分为各个独立的社区，然后利用动态规划的方法将初始的节点最优的分配到各个社区，然后将各个社区中被影响的节点累加得到最终被影响的节点数目。

利用社区发现算法找到社区之后，OASNET算法求解影响力最大化问题的公式如下：

d??Fi(ki,Gi,Mi,Γi)i?1n?k?kii?1n

其中，n为社区的个数；k为给定的初始的激活节点个数；Fi(ki,Gi,Mi,Γi)是求可达节点的函数；ki代表给第i个社区分配的节点的个数；Gi代表第i个社区，即第i个网络；Mi代表给第i个网络使用的传播模型为LT模型或IC模型；Γi为给第i个社区所使用的传播算法。该问题的目标是如何将k个初始的激活节点分配到各个社区，使各个社区的影响力之和达到最大。OASNET算法使用动态分配的方法：

OPT(k,n)?MAX{F(i,Gn,Mn,Γn)}?OPT(k?i,n?1),0?i?k

其中，OPT(k, n)代表分配给前n个社区k个节点所获得影响力最大值。对于第i个社区，可以给这个社区分配0到k个节点，求出Fi(ki,Gi,Mi,Γi)，从而可以得到OPT(k, 1)，利用上述公式可以

计算出OPT(k, 2),…., OPT(k, n)，从而得到将k个节点最佳的分配到n个社区，使获得的影响力最大。

OASNET算法分为三部分，第一部分是使用Newman等人提出的社区发现算法[23]来对网络进行社区发现，这部分的时间复杂度为O(n(log2n)2)；第二部分是对每个社区分配1到k个节点求其影响力的值，这部分时间复杂度为O(kmM)，其中k为初始分配的节点个数，M为模拟传播的次数，m为网络的边数；第三部分求最佳分配的时间复杂度为O(Nk2)，N为社区的个数。OASNET算法的时间复杂度主要由第二部分决定，因此，算法的时间复杂度为O(kmM)，相比贪心算法的时间复杂度有不少的提高。

OASNET算法首次提出把影响力最大化算法看成是资源的动态分配问题，而且证明了这种资源分配方法求解影响力最大化也是一个NP难问题，OASNET算法的特点是利用动态分配方法求解初始节点分配问题，虽然OASNET算法与均等分配算法、比例分配算法、随机分配算法和全局网络上的度数最大化算法相比有改进，但是OASNET算法有一个缺点是它假设全局网络通过社区发现后被分成各个独立的社区，然而实际社交网络中的各个社区之间还是有很多联系，将全局网络划分为独立社区之后会导致边的损失而影响最终被影响的节点数。 3.3.2 CGA算法

CGA[24]算法的总体思想和OASNET算法类似，也是根据社区发现算法将网络划分成各个独立的社区，然后把问题转化为将初始激活节点个数最佳的分配到各个社区，最后将各个社区影响力值求和得到最大的影响力值。

CGA算法针对从通话日志中提取的移动通话社交网络进行研究，将移动通话社交网络抽象为有向带权图G(V, E, W)，网络中的手机用户抽象为节点V，用u到v的有向边E表示用户u向用户v拨通电话，边上的权值W表示通话时长。CGA算法使用独立级联模型进行信息传播，但在独立级联模型中边上不存在权值，而在移动社交网络中，边上的权值是一个很重要的参数，权值越大表明节点间的联系越密切，节点越有可能被激活。因此，CGA算法将边上的权值和独立级联模型中的传播概率联系起来，构成独立级联模型的一个特例：带权独立级联模型。该模型中，边上权值越大则该边的传播概率越大。

CGA算法首先进行社区划分，在社区划分完成后，需要解决的问题主要是从哪些社区中选择影响力最大的节点，最简单的方法是从每个社区中平均选择，但这会带来不必要的计算量，在这里CGA算法中提出了一个动态规划算法用来确定选择影响力最大节点的社区。令Zk-1表示在第k-1步已经选择出的影响力最大节点的集合，用?Rm表示影响度的最大增量。公式1定义当第k个影响力最大节点在社区Cm中选择时基于社区Cm算出的影响度最大增量。

?Rm?max{Rm(Zk?1?vj)?Rm(Zk?1)|vj?Cm} (1)

为找到第k个影响力最大的节点，首先要找到所有社区中会产生影响度增量的社区。令

R[m,k](m?[1,M],k?[1,K])表示在前面m个社区中找到第k个最大影响力节点后得到的影响度。

R[m,k]?max{R[m?1,k],R[m,k]??Rm}R[m,0]?0,R[0,k]?0

上述公式表示若用前m-1个社区中找到的第k个节点计算所得的影响度小于在第m个社区中找到的第k个节点计算所得的影响度，则第k个节点就从社区Cm中选择，否则从前Cm-1个社区中选择。从前m个社区中选择一个社区用来找出第k个最大影响力节点，若被选出的社区用函数s[m, k]表示，则：

?s[m?1,k]s[m,k]???ms[0,k]?0R[m?1,k]?R[m.k?1]??RmR[m?1,k]?R[m.k?1]??Rm

CGA算法用函数s[m, k]选择用来找出第k个最大影响力节点的社区Cm。与OASNET相比，CGA算法是使用贪心算法作为各个社区寻找初始的影响力节点的算法，而OASNET算法是使用度数最大的算法。由于贪心算法的时间复杂度比度数最大算法的时间复杂度高很多，因此CGA算法的时间复杂度也比OASNET算法高很多。CGA算法由于将网络划分成各个小的网络，因此它相比贪心算法时间复杂度有很大数量级的降低。但是CGA算法使用贪心算法作为社区的寻找算法，时间复杂度依然比较高，而且由于网络分成各个独立社区之后会导致边的减少而影响效果。 3.4 对网络进行稀疏化

Michael提出了一种对网络结构进行稀疏化的方法来大量减少网络中边的数量[25, 26]，从而达到在较少的损失影响范围的情况下大量减少算法运行时间。Michel考察了现实社交网络中一些行为

?的传播路径，基于这些行为对网络进行稀疏化，使得稀疏化以后的网络让?中每一个可达的点

仍然可达，而且计算了所有这些行为的总的概率：

??logL?(G)??(logP(v)?logP??(v))

v?V??这里P?(v)表示v在?行为中可达的概率，相对的P?(v)表示v在?行为中不可达的概率。

最后使得稀疏化后的图中logL?(G)能达到最大，而且logL?(G)???，最终图中的边能得到大量的削减。但是，该方法是基于IC模型的，利用了概率最大化来稀疏化最终图，所以对LT模型并不适用。

3.5 混合式影响力最大化算法HPG

参考文献[19]中提到度数大的节点往往都处在社会网络的中心位置，KK算法考虑影响的传播过程能够达到最优值的63%[12]，田佳堂等[1]综合度中心性和贪心算法的优势并结合LT模型“积累特性”，提出了一种利用节点的度数outDegree(u)和节点u的潜在影响力的启发式算法HPG算法，HPG算法混合了启发式算法和KK算法。HPG算法分两个部分：首先是启发阶段，选取最具潜在影响力的节点，这部分节点虽然在当前不能带来最大的影响力，但却蕴含着巨大的潜在影响力；然后是贪心阶段，选取最具影响力的节点。

为了找到潜在影响力最大的节点，通过网络结构分析和实验发现有两个因素影响最具潜在影响力节点的选择[1]：节点的度数(outDegree)和一个激活节点对其所有未激活节点邻居影响力之和(inf)。HPG算法选择以节点的度数作为最具潜在影响力节点的选择，并综合考虑inf因素。潜在影响力

PI(Potential Influence)定义如下：

inf(u)?v?N(u),v?A(u)?0?buv

PI(u)?outDegree(u)?(1?e?inf(u))其中，N(u)表示u的出边邻居节点集合，A(u)表示N(u)中已激活的节点，buv表示节点u对v的影响力。因此，inf(u)表示节点u施加于所有未激活邻居节点的影响力之和，我们称之为节点u的影响力，它由节点u未激活邻居的个数以及buv大小这两个因素决定。outDegree(u)表示节点u的出度，当节点的出度相同时，选择影响力较大的节点，而不是盲目随机的选择一个度数最大的节点作为当前潜在影响力最大的节点。因此，最具潜在影响力的节点就是PI值最大的节点。

HPG算法将k个初始节点的选择分为两个阶段：启发阶段和贪心阶段。首先利用启发式算法来选择k???ck??个种子节点来激活网络，启发阶段每一步选取PI值最大的节点u作为种子节点激活网络；贪心阶段利用KK算法选取剩余??ck??个种子节点，但是HPG算法的启发阶段并没有考虑每个节点阈值不同的情况，仅仅将buv进行相加，而且若buv??v，则buv表明v节点提供了超过一个节点的价值，这显然不太合理。但是HPG算法没有考虑在不同节点不同激活阈值的问题，而且无法在启动因此c较小的情况下得到较好的激活范围，即无法在较小的复杂度下得到好的激活范围。 3.6 基于节点激活阈值的启发式算法

陈浩等利用线性阈值模型提出了一种基于节点激活阈值的启发式算法[11]，该算法分为两个阶段：第1个阶段为启发阶段，并不像KK算法那样寻求局部最优，而是通过LT模型的影响累积特性来启发式寻找那些能够提供最大潜在影响的节点作为种子节点；第2个阶段则是在第1个阶段激活的基础上，利用KK算法局部最优的特性来尽可能扩展影响范围。它综合考虑了节点之间的影响力和节点的激活阈值，根据每个节点在激活过程中动态变化的阈值来计算PIN值，启发过程中，每一次都选取PIN最大的节点作为种子节点进行激活，贪心阶段中再贪心地挑选那些具有最大影响范围增量的节点作为种子节点，该算法的复杂度相对较小。 3.7 其他相关算法

集合覆盖贪心算法[19]每次选择最高“uncovered”度数的节点，一旦一个节点被选中，它的所有邻居节点被标记为“covered”，这个过程一直持续k步．它选择覆盖范围最大的节点，但是在影响最大化的约束下，覆盖并不等于激活，所以其实验结果并不好。文献[27, 28]中讨论了如何在作者合作网络中找到k个研究员，使得与他们合作的其他研究员人数最多，这是影响力最大化问题的一个特例。

Kimura等[29]提出了一种通过分解极大联通子图去寻找影响力最大的节点的算法，实验结果表明算法的时间复杂度相比贪心算法降低了很多，而且效果和贪心算法差不多，是处理影响力最大化比较好的一个方法，但是这个算法在处理大型网络的时间复杂度仍然非常高。

Eyal等[14]把投票模型(Voter Model)引进到影响力最大化中来，通过分析Voter模型把影响力最大化问题转化为一种求解概率的问题，因为选民的投票也是一种概率策略，很多选民投票时会受周

围人的影响。Eyal等借助Voter模型然后利用启发式的算法(包括随机算法、最小路径算法、度数最大化等算法)来选择初始节点去求影响力最大化问题。

4结论

社交网络中对于影响力最大化问题的研究是近年来的研究热点之一，本文详细介绍了基本的影响力传播模型和几个主要的影响力最大化算法。从调研中发现，针对具体的社交网络，影响力最大化算法需要更合适的传播模型。在通用的LT模型和IC模型中，激活率是通过系统去随机给定，一旦给定这个传播概率则在此次试验的传播过程中将不会改变。这里面有两个问题，一是在实际的社交网络中，这个传播概率很难去界定，更需要根据实际情况来处理网络的传播概率；二是由于社交网络是动态变化的，节点之间的影响也是动态的，节点之间的这种激活概率也是动态变化的，因此，在针对具体社交网络求解影响力最大化问题时需要考虑合适的传播模型。

5参考文献

1. Tian, J., Y. Wang and X. Feng, A new hybrid algorithm for influence maximization in social networks.

Jisuanji Xuebao(Chinese Journal of Computers), 2011. 34(10): p. 1956--1965.

2. Boccaletti, S., et al., Complex networks: Structure and dynamics. Physics reports, 2006. 424(4): p.

175--308.

3. Domingos, P. and M. Richardson. Mining the network value of customers. 2001.

4. Richardson, M. and P. Domingos. Mining knowledge-sharing sites for viral marketing. 2002.

5. Goldenberg, J., B. Libai and E. Muller, Using complex systems analysis to advance marketing theory

development: Modeling heterogeneity effects on new product growth through stochastic cellular automata. Academy of Marketing Science Review, 2001. 9(3): p. 1--18.

6. Mahajan, V., E. Muller and F.M. Bass, New product diffusion models in marketing: A review and

directions for research. The Journal of Marketing, 1990: p. 1--26.

7. Bass, F.M., Comments on “A New Product Growth for Model Consumer Durables The Bass Model”.

Management science, 2004. 50(12 supplement): p. 1833--1840.

8. Brown, J.J. and P.H. Reingen, Social ties and word-of-mouth referral behavior. Journal of Consumer

Research, 1987: p. 350--362.

9. Goldenberg, J., B. Libai and E. Muller, Talk of the network: A complex systems look at the underlying

process of word-of-mouth. Marketing letters, 2001. 12(3): p. 211--223.

10. Ma, H., et al. Mining social networks using heat diffusion processes for marketing candidates selection.

2008.

11. Hao, C. and W. Yitong, Threshold-Based Heuristic Algorithm for Influence Maximization. Journal of

Computer Research and Development, 2012. 10: p. 019.

12. Kempe, D., J. Kleinberg and E.V. Tardos. Maximizing the spread of influence through a social network.

2003.

13. 冀进朝, 韩笑, 王喆, 基于完全级联传播模型的社区影响最大化. 吉林大学学报: 理学版, 2009.

47(005): p. 1032--1034.

14. Even-Dar, E. and A. Shapira, A note on maximizing the spread of influence in social networks. Internet

and Network Economics, 2007: p. 281--286.

15. 汪小帆, 李翔, 陈关荣, 复杂网络理论及其应用. 2006: 清华大学出版社有限公司. 16. Leskovec, J., et al. Cost-effective outbreak detection in networks. 2007.

17. Chen, W., Y. Wang and S. Yang. Efficient influence maximization in social networks. 2009. 18. 兰如钦, 社会网络上的影响力最大化算法研究. 2011, 北京交通大学.

19. Estevez, P.A., P. Vera and K. Saito. Selecting the most influential nodes in social networks. 2007. 20. 景天魁, 林聚任, 社会网络分析: 理论, 方法与应用. 2009, 北京: 北京师范大学出版社.

21. Galstyan, A., V. Musoyan and P. Cohen, Maximizing influence propagation in networks with community

structure. Physical Review E, 2009. 79(5): p. 056102.

22. Cao, T., et al. OASNET: an optimal allocation approach to influence maximization in modular social

networks. 2010.

23. Clauset, A., M.E. Newman and C. Moore, Finding community structure in very large networks. Physical

review E, 2004. 70(6): p. 066111.

24. Wang, Y., et al. Community-based greedy algorithm for mining top-k influential nodes in mobile social

networks. 2010.

25. Mathioudakis, M., et al. Sparsification of influence networks. 2011.

26. Gomez-Rodriguez, M., J. Leskovec and A. Krause, Inferring networks of diffusion and influence. ACM

Transactions on Knowledge Discovery from Data (TKDD), 2012. 5(4): p. 21.

27. Suri, N.R. and Y. Narahari. Determining the top-k nodes in social networks using the shapley value. 2008. 28. Narayanam, R. and Y. Narahari, A shapley value-based approach to discover influential nodes in social

networks. IEEE Transactions on Automation Science and Engineering, 2010(99): p. 1--18.

29. Kimura, M., K. Saito and R. Nakano. Extracting influential nodes for information diffusion on a social

network. 2007.

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库社交网络影响力最大化研究综述(2)在线全文阅读。