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]就提出了一般反饋模型下的自適應影響力最大化方案。

雖然上述指標從網絡的不同角度來衡量節點的重要性，這有助于人們從宏觀拓撲結構上加深理解，但是在實際的移動社會網絡中，人與人之間的社交程度還與其社會屬性、社會態度、通信習慣等因素有關。如何進一步將網絡拓撲特征與用戶的屬性特征相結合，以設計高效可靠的影響力最大化方案，對于移動社會網絡具有重要意義。