文献标识码：A
文章编号： 0258-7998(2015)05-0145-04
0 引言
近年来，随着互联网和Web技术的不断革新，影响最大化问题作为社会网络分析领域的重要问题得到了快速发展，并已引起越来越多的学者关注。Li等[1]研究了基于位置感知的影响力最大化问题，通过用户影响力的上界选择种子节点并消除不重要的节点，减少了初始种子节点的选择范围。Kim等[2]基于IC模型将独立影响路径作为影响评估单元，但是算法未考虑不同节点影响力的相关性。Zhao等[3]提出基于网络社区结构的节点影响力度量策略，但是算法未考虑节点度在信息传播中的重要性。Jung等[4]提出了基于IC扩展模型的IRIE算法。Guo等[5]提出基于个性化的影响力最大化算法，对给定目标用户，寻找对该目标用户影响力最大的节点。Cao等[6]提出动态规划算法(OASNET)解决影响力最大化,但此算法没有考虑社区间的连通性。Tian等[7]提出结合启发算法和贪心算法的影响力最大化算法HPG，但算法在启发阶段仅以节点的度计算潜在影响力，没有充分考虑节点的其他属性。与上述研究不同，本文将社区间的边界节点作为初始种子节点集的候选集，以减少社区内大量非边界点的计算时间，提高运行效率。同时，传统以节点度的倒数衡量节点间影响力忽略了邻居节点对节点影响的差异，基于此本文综合考虑边界节点的度、所连社区数、所连社区规模均值3个因素衡量节点对邻居的影响力传播的重要性，以更准确衡量节点影响力。
1 基于社区度的边界节点影响力最大化算法
本文提出的基于社区度的边界节点影响力最大化算法(CDEA)建立在具有社区结构的社会网络基础上，利用HPG算法框架实施。CDEA算法将社区连接边的两端节点作为边界节点，从边界节点集中选择初始传播种子节点，通过LT模型在社会网络中传播，使初始种子节点产生的影响范围最大。CDEA算法从边界节点集中选择初始种子节点是由于在具有社区结构的社会网络中，跨社区的信息最大化传播往往更有现实意义，而边界节点是社区间信息交流的大使，跨社区的信息传播必然会经过社区边界节点，因此可以先不考虑社区内大量的非边界节点，只考虑少量的边界节点，可极大降低算法运行时间。同时CDEA算法用边界节点的度和与边界节点直接相连的社区数以及社区规模均值综合衡量节点的潜在影响力，提高计算节点在贪心阶段被快速激活的可能性。
1.1 节点社区度
节点社区度是指边界节点的度、与边界节点直接连接的社区数、直接相连的社区规模均值三者叠加。社区度既考虑节点度，也结合节点在社会网络中的位置和连通性，可以较好地评估节点对影响力传播的重要性。
定义1 （社区度）社区度主要用于衡量边界节点在影响力传播中的重要性。社区度是节点在社区中邻居数、与节点直接相连的社区数以及所连社区规模均值的叠加和。节点在社区中的邻居数越多，表明节点在社区中越重要，对其他节点产生影响的可能更大。节点直接相连的社区数越多，说明节点与其他社区产生交流的机会越大，对信息的广泛传播具有重要意义。而所连社区规模的大小将直接影响信息能否通过所连社区继续向下一个社区扩散，所连社区规模越大，则此社区在整个社会网络中对信息的快速传播作用越大。因此采用三者的叠加和可以突出节点在信息传播中的重要性。社区度CDeg(u)定义如下：
社区规模均值可缩小，因为邻居社区数少而邻居社区节点数多或邻居社区多而邻居社区节点数少所造成的差异能更好地平衡社区数和每个社区规模间的关系，因此综合考虑与节点直接相连的邻居社区以及相应社区规模均值，可更准确描述社区度，提高节点获取潜在影响力节点的精度。
1.2 节点影响概率
本文综合边的权重和节点间的交流频度计算节点间的影响概率，更有效地度量节点间相互影响的概率。影响概率即为节点激活邻居的可能性，当节点的所有已激活邻居对其影响概率和大于等于特定的阈值θ，则节点被激活。本文定义节点u对邻居节点v的影响概率为
其中tuv为社会网络G中节点u和v信息交流频度，wuv为节点u到v的边权重值，Nei(v)表示节点v的邻居节点集。
1.3 CDEA算法框架
社区度描述了边界节点在整个网络中的拓扑结构和重要性，与传统单一采用节点度描述节点与邻居的关联度相比，可更好地衡量节点潜在影响力。本文对HPG算法改进，基于社区度提出新的混合算法CDEA。CDEA算法分为启发阶段和贪心阶段。
基于LT传播模型的影响累积特性在启发阶段对边界节点启发式寻找最有影响力的k′个节点作为种子节点。这些节点不是局部影响力最大的节点，但是其潜在影响力在后续信息传播激活过程中将会被充分挖掘，最终获得比KK算法更大的影响范围。令inf(u)为节点u对所有未被激活邻居节点的影响力之和，则：
这里CDeg(u)表示节点u的社区度，Nei(u)表示节点u的邻居节点集合，A(u)表示节点u的邻居中未被激活的节点集。PI综合考虑了节点的社区度和对邻居中未激活节点的影响范围。启发阶段从未激活的节点中选择潜在影响力最大的节点，并将其加入初始集合，直到出现k1个已经被激活的节点。贪心阶段基于LT信息传播模型，应用KK算法不断计算边际影响收益，在局部最优的情况下获取k-k1个最有影响力的节点。
CDEA算法具体步骤如下：
输入：社会网络G=(V，E，W)={C1，C2，C3，…，CM}，阈值θ，启发因子c，初始集合大小k。
输出：大小为k的目标节点集S，最终激活节点数k0，启发阶段激活节点数k1，贪心阶段激活节点数k2。
1.4 CDEA算法复杂度分析
启发阶段，由于静态社会网络中式(2)中节点社区度是固定的，并且只需要计算社区间的边界节点的社区度，而非整个网络中所有节点，且inf(u)是基于前一个初始种子节点并更新整个网络后确定，基本不耗时间，因此时间复杂度为O(C)。同时启发阶段不但获取了大量具有潜在影响力的节点，而且也激活了大量节点。贪心阶段，由于有大量节点已被激活，未激活节点比初始状态下需要激活节点数减少了大部分，即可看作KK算法运行在小规模数据集，因此算法复杂度比KK小。
KK、HPG以及CDEA算法不同阶段的时间复杂度如表1所示。其中Q1、Q2分别表示启发阶段CDEA算法和HPG算法每个种子节点的平均激活节点数。T1、T2、T3分别表示贪心阶段CDEA算法、HPG算法、KK算法每个种子的平均激活范围。N、M、M′分别表示社会网络G的节点数、边数、社区边界节点数。M′< 2 实验 本文实验中线性阈值模型中的每个节点阈值?兹取固定值0.5，启发因子c用于平衡不同阶段的步数，其中启发阶段为 第一个数据集是计算机类英文文献数据中的论文作者合作网络，边代表两个作者共同发表过论文，边上的权重值表示作者间的合作次数。第二个数据集是视频分享网站Youtube中的用户视频分享网，边代表用户间为彼此分享过视频，边上的权重值代表用户共享视频的次数。第三个数据集是Google公司推出的免费在线社交网站Orkut的朋友关系网，边代表用户间是朋友关系，边上权重值表示用户交流次数。 为了充分说明本文提出的基于社区度影响力最大化算法，实验在3个数据集上，从不同k值下的影响范围和算法运行时间两方面将本文提出的CDEA算法与KK算法、HPG算法进行对比，验证算法在大规模社会网络下的准确性和高效性。 2.1 影响范围对比 首先考察Youtube数据集中CDEA算法在不同启发因子c下影响范围的变化，实验结果如图1所示。由图可知，除c=0外，其他c值影响范围基本都比c=1大，且c=0.5时影响范围最大。由于c=1时，CDEA算法只有贪心阶段没有启发阶段，因此影响范围比其他c值的影响范围小。c=0表明此时CDEA算法只有启发阶段没有贪心阶段，所有初始节点都是静态选择PI最大的节点，没有传播过程参与，因此影响范围最小。实验结果表明c=0.5时CDEA算法影响范围最大，因此下面的实验中设c=0.5。 其次考察3个数据集上CDEA算法影响范围的变化，实验结果如图2所示。由图可知相同k值下，Youtube数据集上CDEA算法的影响范围最大，Orkut数据集中影响范围最小，这说明本文提出的算法更适用于社区密度比较大的社会网络。随着初始种子节点k逐渐变大，CDEA算法在3个数据集上影响范围随之扩大，且当k在[80，160]之间时影响范围的变化速率比较大，k值超过160后影响范围变化速率逐渐减小，这是因为随着k的增大，新增加的种子节点能激活的节点不断减少，其影响范围也在降低。 最后考察Youtube数据集中KK算法、HPG算法、CDEA算法在不同k值下影响范围的变化，实验结果如图3所示。由图可知，KK算法的影响范围呈线性，HPG和CDEA算法呈曲线上升，且CDEA算法在k值大于120时比HPG算法影响范围大，这是因为CDEA算法综合考虑了节点度、社区度以及社区规模均值3个因素，使影响传播的范围在大规模社会网络中更广。 2.2 运行时间对比 首先对比3个数据集上CDEA算法寻找k个种子节点需要的运行时间，实验结果如图4所示。由图可知，算法在Youtube数据集上运行时间最小，在Orkut数据集上运行时间最大，这是由于CDEA算法充分利用了节点的社区度属性，而Youtube数据集社区密度大，因此运行时间相对比较小。当k值不断变大时，CDEA算法在不同数据集中运行时间的增长率比较小，因为该算法充分考虑了社会网络中社区的边界节点，更适合大规模社会网络。 最后在Youtube数据集中比较CDEA、HPG、KK算法的运行时间。实验结果如图5所示。由图可知，随着k值的不断增长，KK算法的运行时间不断变长，而CDEA和HPG算法的运行时间相对比较稳定，呈线性增长，且当k不断变大时，CDEA算法的运行时间低于HPG算法。这是因为CDEA算法充分考虑了社区边界节点，尤其是在大规模社会网络中，极大地减少了寻找初始种子节点的时间。 3 总结 本文提出一种基于社区度的边界节点影响力最大化算法CDEA，与其他关于影响力最大化问题研究不同的是：CDEA算法利用社会网络的社区结构，将社区中的边界节点作为最有影响力节点的候选集，在两层算法模型框架下，启发阶段根据网络社区从边界节点中选择具有潜在影响力的节点集，贪心阶段在启发阶段基础上应用KK算法计算。实验表明，本文提出的算法既有效地降低了时间复杂度，又能较好地应用于大规模社会网络。接下来的工作将对算法作进一步改进，改善评估节点影响力的因素，提高算法的精度。 参考文献 [1] LI G，CHEN S，FENG J，et al.Efficient location-aware influence maximization[C].Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data.Snowbird，Utah，2014：1621. [2] KIM J，KIM S K，YU H.Scalable and parallelizable prcessing of influence maximization for large-scale social networks[C].Proceedings of the 29th IEEE International Conference on Data Engineering.Brisbane，Australia，2013：266-277. [3] 赵之滢，于海，朱志良，等.基于网络社团结构的节点传播影响力分析[J].计算机学报，2014，37(4)：753-766. [4] JUNG K，HEO W，CHEN W.IRIE：Scalable and robust influence maximization in social networks[C].Proceedings of the 12th International Conference on Data Mining.Brussels，Belgium，2012：918-923. [5] GUO J，ZHANG P，ZHOU C，et al.Personalized influence maximization on social networks[C].Proceedings of the 22nd ACM International Conference on Information & Knowledge Management.San Francisco，USA，2013：199-208. [6] CAO T，WU X，WANG S，et al.OASNET：an optimal allocation approach to influence maximization in modular social networks[C].Proceedings of the 2010 ACM Symposium on Applied Computing.ACM，2010：1088-1094. [7] 田家堂，王轶彤，冯小军.一种新型的社会网络影响力最大化算法[J].计算机学报，2011，34(10)：1956-1965. [8] YANG J，LESKOVEC J.Defining and evaluating network communities based on ground-truth[C].Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics.ACM，2012：3.
当c=1时表明此时为纯KK贪心算法。实验使用的数据集来自公开数据[8]，社区密度是每个社区平均所含节点数。数据集统计信息如表2所示。
