2.1　社会影响力

影响力最大化研究的初衷是病毒式营销，也就是说，公司希望通过移动社会网络（以下简称网络）中的口碑效应来推广新产品或创新。一个经济有效的方法是瞄准网络中有较高影响力的人，投入资源让其接受，例如免费或以折扣价为其提供产品样品，以期这些有影响力的人能够推动网络中的其他人选择该产品，从而在网络中产生潜在的巨大收益。因此，影响力最大化是移动社会网络分析中的重要内容。通过从网络中识别前k个最具影响力的用户，使网络利用这k个用户产生的影响传播最快、范围最广。影响力最大化在控制舆情传播、遏制病毒传染等领域有着广泛应用[17-20]。近年来，大量学者从不同角度提出了不同算法进行影响力分析，影响力节点的挖掘依然是热门研究方向。

作为社会影响力的研究基础，相关学者根据网络特点，先后提出了衡量节点重要性的指标。Freeman[21]首先提出用度中心性（Degree Centrality，DC）来衡量网络中节点的重要性，即按照节点的度中心性大小来衡量节点的影响力。介数中心性（Betweenness Centrality，BC）[22]通过拓扑图中的最短路径经过一个节点的次数来表现该节点与其他节点的互动程度，该指标的作用是评价节点在网络中的影响力程度。Sabidussi等[23]提出了一种计算接近中心性（Closeness Centrality，CC）的高效算法，能够反映节点与其他节点的接近程度。如果一个网页能被其他很多网页链接到，则该网页的PageRank（PR）[24]值相对较高，也就意味着该节点更重要。Liu等[25]重点分析了PageRank和社会影响力之间的关系，提出了线性社会模型并引入限制条件，以获得更好的排名和推荐性能。Zhang等[26]在PageRank的基础上提出了反向PageRank算法，并与度中心性相结合得到一种混合的启发式算法（Mixed PageRank and Degree，MPRD）。Kitsak[27]提出将核心度（Coreness）作为评价节点在网络中影响力的指标，利用k核分解计算网络中各个节点的影响力。Yang等[28]提出用一种局部中心性指标来辨识网络中最具影响力的节点。Morone和Makse[29]基于渗透理论提出了集体影响（Collective Influence，CI）这一网络拓扑指标，利用渗透模型找出遭到破坏就会使整个网络崩溃的节点，并把这些节点作为影响力前k节点。Tulu等[30]综述了不同技术在移动社会网络中识别关键节点的应用，并指出这些技术对未来节点选择的主要挑战。

在节点重要性衡量指标的基础上，研究人员根据具体应用场景的特点，提出了大量社会影响力算法。Song等[31]在集体影响的基础上提出了局部集体影响排序（Local Collective Influence Rank，LCIR）算法，以使影响力的传播更稳定。康玲等[32]根据紧密度情况对网络中的节点重新排序，绘制网络的区域密度曲线，并在密度图中的波谷点两侧选取一定比例的节点作为影响力节点。杨树新等[33]考虑局部方法的适宜度量层级与网络拓扑的差异性，提出了一种新的基于三级邻居的节点影响力度量法（Three-level Influence Measurement，TIM）。Kempe[34]证明了影响力最大化问题是NP−难问题，并提出原始贪心策略，用于求影响力前k节点。该策略使用基于子模块函数的分析框架，证明其所获得的解决方案在最优值的63%以内。Leskovece等[35]提出了一种具有成本效益的贪心（Cost−Effective Lazy-Forward，CELF）算法，它能根据影响力扩散的子模态特性来避免影响范围的冗余计算，从而提高了贪心算法的计算效率。Kim等[36]提出了一种基于独立级联模型的独立路径算法（Independent Path Algorithm，IPA），用于近似计算节点的影响力传播能力。Kianian等[37]在IPA的基础上，考虑到两条影响路径的相关性，结合启发式算法提出了一种高效的启发式独立路径算法（Heuristic Independent Path Algorithm，HIPA）。李国良等[38]针对多社交网络中的影响力传播问题，使用节点间具有最大传播概率的路径来近似衡量节点间的传播概率。在复杂网络中，可通过先移除某些节点，再依据剩余网络被破坏的程度来衡量被移除节点的重要性[39]。网络破坏性也可以理解为网络连通性的损失，一般从以下3个角度进行考虑：移除节点集合和剩余节点之间的非连通程度、移除节点集合内部的非连通性，以及节点移除后剩余节点之间的非连通性。Xu等[40]通过将影响力节点作为桥点，确定能够维持网络稳定性的结构洞。Chavdar[41]用Stability−sensitive方法来衡量网络的脆弱性。Wang等[42]通过引入链路的影响来对节点的重要性进行重定义。Bozorgi等[43]在社团的基础上提出了线性阈模型下影响力最大化算法。随着机器学习技术的兴起，许多学者将机器学习技术引入影响力最大化问题中，例如Tong和Wang[44]就提出了一般反馈模型下的自适应影响力最大化方案。

虽然上述指标从网络的不同角度来衡量节点的重要性，这有助于人们从宏观拓扑结构上加深理解，但是在实际的移动社会网络中，人与人之间的社交程度还与其社会属性、社会态度、通信习惯等因素有关。如何进一步将网络拓扑特征与用户的属性特征相结合，以设计高效可靠的影响力最大化方案，对于移动社会网络具有重要意义。