一、影響力最大化定義

定義：影響力最大化問題的目標(biāo)是尋找社會(huì)網(wǎng)絡(luò)中最終影響范圍最大的K個(gè)節(jié)點(diǎn)，從而使得以這K個(gè)節(jié)點(diǎn)作為初始活躍節(jié)點(diǎn)集合，經(jīng)過影響在社會(huì)網(wǎng)絡(luò)中的傳播，最終被影響的節(jié)點(diǎn)個(gè)數(shù)最大。
形式化描述
給定：社會(huì)網(wǎng)絡(luò)圖G=(V,E,W)，設(shè)定的影響力傳播模型，以及一個(gè)正整數(shù)K；
目標(biāo)：從網(wǎng)絡(luò)圖G中選取初始活躍節(jié)點(diǎn)集合S，使得σ(S)；
約束：S?V且|S|=K。

二、常用傳播模型

2.1獨(dú)立及聯(lián)模型（IC）
獨(dú)立級(jí)聯(lián)模型（IC）基于概率，每個(gè)節(jié)點(diǎn)在自身轉(zhuǎn)變?yōu)榛钴S狀態(tài)之后都以一定的概率去試圖激活其后繼節(jié)點(diǎn)，并且多個(gè)活躍節(jié)點(diǎn)試圖影響同一鄰居節(jié)點(diǎn)的行為是相互獨(dú)立的，所以叫獨(dú)立級(jí)聯(lián)模型。

2.2 線性闕值模型（LT）
線性閾值模型（LT）基于闕值，并且多個(gè)活躍節(jié)點(diǎn)試圖影響同一后繼節(jié)點(diǎn)的行為是非獨(dú)立的，影響是否成功取決于所有活躍節(jié)點(diǎn)對(duì)后繼節(jié)點(diǎn)影響權(quán)重的和是否超過后繼節(jié)點(diǎn)的闕值。

2.3加權(quán)級(jí)聯(lián)模型（WC）
加權(quán)級(jí)聯(lián)模型（WC）是特殊的獨(dú)立級(jí)聯(lián)模型。在加權(quán)級(jí)連模型中，節(jié)點(diǎn)v成功激活后繼節(jié)點(diǎn)w的概率為節(jié)點(diǎn)w入度的倒數(shù)，即p(v,w)=1/d_w，其中d_w是節(jié)點(diǎn)w的入度1。

三、影響力最大化度量標(biāo)準(zhǔn)

運(yùn)行時(shí)間、算法精度、可擴(kuò)展性
1、運(yùn)行時(shí)間：
設(shè)計(jì)影響力最大化求解方案必須以盡量少的運(yùn)行時(shí)間作為基本出發(fā)點(diǎn)。
傳統(tǒng)的影響力最大化貪心算法通過大量重復(fù)的蒙特卡羅模擬來計(jì)算給定節(jié)點(diǎn)集合的影響范圍，從而導(dǎo)致相當(dāng)長(zhǎng)的運(yùn)行時(shí)間。
2、算法精度：
算法精度指在給定的影響傳播模型下，一個(gè)影響力最大化算法選定的節(jié)點(diǎn)，經(jīng)過影響傳播，最終可以成功影響的節(jié)點(diǎn)數(shù)量。
近年來對(duì)影響力最大化問題的研究表明，尋找最有影響力的K個(gè)節(jié)點(diǎn)是NP-Hard問題。傳統(tǒng)的排序算法以及PageRank等方法由于沒有考慮影響傳播特性，故算法精度太差，無法用于影響力最大化算法求解。
3、可擴(kuò)展性：
當(dāng)前的求解算法由于算法復(fù)雜度高、運(yùn)行時(shí)間長(zhǎng)，僅僅適用于節(jié)點(diǎn)數(shù)目在百萬以下的中小規(guī)模社會(huì)網(wǎng)絡(luò)。（怎樣設(shè)計(jì)具有良好擴(kuò)展能力的影響力最大算法來面對(duì)大規(guī)模社會(huì)網(wǎng)絡(luò)）

三、影響力最大化算法分類

影響力最大化問題被證明是NP-Hard問題。
兩個(gè)方向求近似解：
（1）貪心算法—基于爬山貪心算法，每一次選擇能提供最大影響值得節(jié)點(diǎn)，通過局部最優(yōu)解來近似全局最優(yōu)解。
優(yōu)點(diǎn)：精度相對(duì)較高
缺點(diǎn)：算法復(fù)雜度高，執(zhí)行時(shí)間
（2）啟發(fā)式算法—基于設(shè)定的啟發(fā)策略來選擇最有影響力節(jié)點(diǎn)，不需要精確計(jì)算節(jié)點(diǎn)的影響值
優(yōu)點(diǎn)：運(yùn)行時(shí)間短，效率高
缺點(diǎn)：算法精度差

備注：本文是我在博客中看到的關(guān)于影響力最大化的總結(jié)，但是找不到原鏈接了，所以標(biāo)注為原創(chuàng)，如有侵犯，請(qǐng)告知！

總結(jié)

以上是生活随笔為你收集整理的社交网络影响力最大化基础知识总结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。