用戶互動(dòng)表示下的影響力最大化算法

張 萌，李維華

（云南大學(xué)信息學(xué)院，昆明 650504）

0 引言

隨著網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，越來越多的人們在獲得即時(shí)信息的同時(shí)也因互聯(lián)網(wǎng)成為了信息傳播的主體，一些學(xué)者利用Instagram、微博、Facebook 和Twitter等社交平臺用戶間信息擴(kuò)散的優(yōu)勢，挖掘社交網(wǎng)絡(luò)用戶潛在的商業(yè)價(jià)值。影響力最大化問題作為數(shù)據(jù)分析下的新興領(lǐng)域，利用“口碑效應(yīng)”在病毒營銷、廣告發(fā)布和政府監(jiān)管等方面有著良好的應(yīng)用前景。例如，品牌方有一批新產(chǎn)品待推廣，他們首先要在社交網(wǎng)絡(luò)中選擇最佳的用戶群體進(jìn)行產(chǎn)品投放，通過這些種子用戶的宣傳，讓盡可能多的人們購買和使用該產(chǎn)品，這就是影響力最大化在商業(yè)推廣中的巧妙應(yīng)用。研究影響力最大化對人們了解真實(shí)的網(wǎng)絡(luò)信息具有非常重要的意義。

影響力最大化問題最早由Domingos等［1］定義為在網(wǎng)絡(luò)中尋找t個(gè)節(jié)點(diǎn)，這些節(jié)點(diǎn)利用自身影響力使得信息最終的傳播范圍最廣。隨后，Kempe 等［2］證明了影響力最大化問題是一個(gè)NP 難（Non-deterministic Polynomial hard）問題，并提出了兩種經(jīng)典的擴(kuò)散模型——線性閾值（Linear Threshold，LT）模型和獨(dú)立級聯(lián)（Independent Cascade，IC）模型，并在此基礎(chǔ)上結(jié)合蒙特卡洛模擬提出了貪婪算法求解影響力最大化問題。后來的研究者們運(yùn)用不同的方法對影響力最大化算法進(jìn)行了改進(jìn)，也得到了不錯(cuò)的研究結(jié)果；但這些方法在計(jì)算節(jié)點(diǎn)間影響概率時(shí)都是依賴于人工處理好的簡化網(wǎng)絡(luò)和理想狀態(tài)下的公式計(jì)算，沒能真正地通過節(jié)點(diǎn)間的互動(dòng)得出影響概率。

近年來，網(wǎng)絡(luò)表示學(xué)習(xí)（Network Representation Learning，NRL）作為學(xué)術(shù)熱點(diǎn)在社交網(wǎng)絡(luò)用戶行為研究中得到了廣泛的運(yùn)用。其思想是利用一種映射函數(shù)將社交網(wǎng)絡(luò)中的每個(gè)用戶表示為低維向量，這些向量在一個(gè)向量空間中具有表示和推理的功能。Preozzi等［3］在2014年提出了基于網(wǎng)絡(luò)的表示學(xué)習(xí)模型DeepWalk，該模型是受到Mikolov 等［4］在2013 年提出的用于自然語言處理的經(jīng)典模型Word2vec 的啟發(fā)，將網(wǎng)絡(luò)中的節(jié)點(diǎn)看作單詞，將利用隨機(jī)游走生成的節(jié)點(diǎn)序列看作一個(gè)句子，通過SkipGram 模型的學(xué)習(xí)得到節(jié)點(diǎn)的向量表示。在社交網(wǎng)絡(luò)中利用這些向量表示可以進(jìn)行商品個(gè)性化推薦、節(jié)點(diǎn)分類、節(jié)點(diǎn)間鏈路預(yù)測和興趣社區(qū)發(fā)現(xiàn)等。之后，一些學(xué)者在DeepWalk 的基礎(chǔ)上提出了Node2vec［5］、LINE［6］和Struc2vec［7］等網(wǎng)絡(luò)表示學(xué)習(xí)模型。圖1 展示了網(wǎng)絡(luò)表示學(xué)習(xí)模型的流程，可以看出網(wǎng)絡(luò)表示學(xué)習(xí)為后續(xù)的社交網(wǎng)絡(luò)研究開辟了新方向。

圖1 網(wǎng)絡(luò)表示學(xué)習(xí)流程Fig.1 Flowchart of network representation learning

現(xiàn)階段影響力最大化問題的研究面臨著兩個(gè)主要的挑戰(zhàn)：1）如何跳出理想狀態(tài)下的公式計(jì)算，獲得更真實(shí)的節(jié)點(diǎn)間影響概率；2）現(xiàn)有的大部分工作集中于在簡化網(wǎng)絡(luò)中考慮最大化的影響擴(kuò)散，能否脫離固定的傳播模型，考慮節(jié)點(diǎn)間的交互，從交互聯(lián)系的角度來進(jìn)行影響評估。針對上述問題，本文提出一種用戶互動(dòng)表示下的影響力最大化（Influence Maximization based on User Interactive Representation，IMUIR）算法，主要工作包括：

1）根據(jù)社交網(wǎng)絡(luò)中用戶的互動(dòng)痕跡來構(gòu)造用戶上下文對；

2）利用SkipGram 模型學(xué)習(xí)用戶表示，得到能表示用戶的特征向量，根據(jù)用戶活躍度和交互聯(lián)系度，利用貪心策略選擇最佳種子集；

3）在兩個(gè)真實(shí)的社交網(wǎng)絡(luò)上與4 個(gè)算法進(jìn)行對比實(shí)驗(yàn)，驗(yàn)證了IMUIR算法的有效性。

1 相關(guān)研究

國內(nèi)外的研究學(xué)者利用不同類型的方法對影響力最大化問題進(jìn)行了研究。Chen 等［8］基于IC 模型和節(jié)點(diǎn)度的中心性提出了DegreeDiscount 算法；李敏佳等［9］綜合考慮了核心節(jié)點(diǎn)和結(jié)構(gòu)洞節(jié)點(diǎn)的傳播優(yōu)勢，提出了基于結(jié)構(gòu)洞和度折扣的最大化算法；Aldawish 等［10］通過對鄰居節(jié)點(diǎn)的約束提出一種新的改進(jìn)的度折扣啟發(fā)式方法MDD（Modified Degree-Discount）；Kim 等［11］提出了一種隨機(jī)游動(dòng)排序和秩合并修剪的算法，通過修剪無影響節(jié)點(diǎn)來避免無用的影響擴(kuò)散；張憲立等［12］基于度和PageRank 的思想提出了一種混合啟發(fā)式算法來解決大型網(wǎng)絡(luò)上的影響力最大化問題；吳安彪等［13］在時(shí)序圖上對影響力最大化問題進(jìn)行了研究，提出了用來計(jì)算節(jié)點(diǎn)影響力的AIMT（Advanced method for IMTG）和IMIT（Improved method for IMTG）。

此外，一些群集智能算法也被運(yùn)用到了影響力最大化的研究中。Jiang 等［14］提出一種評估預(yù)期影響的函數(shù)EDV（Expect Diffusion Value），結(jié)合模擬退火算法求解影響力最大化問題，該算法比利用函數(shù)子模性改進(jìn)的貪心算法CELF（Cost-Effective Lazy Forward）快了近3個(gè)數(shù)量級；Cui等［15］基于一種降階搜索策略，融合遺傳算法提出度數(shù)遞減搜索（Degree-Descending Search Evolution，DDSE）；Gong 等［16］利用離散離子群算法與評估節(jié)點(diǎn)二階區(qū)域內(nèi)的預(yù)期影響函數(shù)相結(jié)合提出了DPSO（Discrete Paticle Swarm Optimization）算法，能夠較為準(zhǔn)確地找出種子節(jié)點(diǎn)；Sankar 等［17］受到蜂群擺舞行為的啟發(fā)，提出了蜂群算法，在具有主題標(biāo)簽的Twitter重推網(wǎng)絡(luò)中驗(yàn)證了該算法的有效性；Tang 等［18］提出了離散混合蛙跳算法，該算法基于一種新的編碼機(jī)制和離散進(jìn)化規(guī)則尋找種子節(jié)點(diǎn)。

盡管上述算法均取得了不錯(cuò)的效果，也在一定程度上取得了突破，但存在兩個(gè)明顯的弊端：一方面是基于理想狀態(tài)來計(jì)算的節(jié)點(diǎn)間影響傳播概率；另一方面是通過擴(kuò)散模型來計(jì)算受一組種子用戶影響的節(jié)點(diǎn)數(shù)量，而現(xiàn)有的擴(kuò)散模型依賴于假設(shè)會(huì)導(dǎo)致結(jié)果不可靠，使得影響力最大化的求解面臨著可擴(kuò)展性［19］。

由于復(fù)雜網(wǎng)絡(luò)包含數(shù)十億的用戶和連接關(guān)系，想要從中獲取用戶信息會(huì)非常棘手，而網(wǎng)絡(luò)表示學(xué)習(xí)能夠?qū)⒂绊懥ψ畲蠡瘑栴}在大規(guī)模網(wǎng)絡(luò)中進(jìn)行擴(kuò)展。Wang 等［20］通過學(xué)習(xí)低維向量來計(jì)算影響概率，并利用啟發(fā)式算法DiffusionDiscount來尋找種子集；王正海［21］將社交網(wǎng)絡(luò)的節(jié)點(diǎn)引入到向量空間后先用K-Means聚類算法找到候選種子集，再利用KD 樹確定最終的種子集。上述算法雖然利用網(wǎng)絡(luò)表示學(xué)習(xí)對節(jié)點(diǎn)進(jìn)行了表示，但僅利用網(wǎng)絡(luò)結(jié)構(gòu)來進(jìn)行研究，沒有考慮用戶間的互動(dòng)。Feng 等［22］從用戶日志級聯(lián)中提取用戶上下文對，通過構(gòu)建傳播網(wǎng)絡(luò)，利用低維表示來描述用戶的社會(huì)影響嵌入，由于信息傳播的有向性，每個(gè)用戶有兩種嵌入表示——源嵌入和目標(biāo)嵌入，源嵌入表示對其他用戶的影響，目標(biāo)嵌入表示受其他用戶的影響。該方法脫離了簡單網(wǎng)絡(luò)結(jié)構(gòu)，從用戶級聯(lián)中確定影響擴(kuò)散。Panagopoulos 等［23］利用多任務(wù)神經(jīng)網(wǎng)絡(luò)預(yù)測種子節(jié)點(diǎn)的預(yù)期影響和級聯(lián)大小，利用預(yù)測的級聯(lián)大小和CELF 算法的思想來選取種子集。該方法提出利用測試級聯(lián)評估種子集的影響范圍，更貼合真實(shí)的信息傳播，但在采樣和尋找種子集時(shí)沒有考慮到用戶行為特征。由上述研究可知，目前利用網(wǎng)絡(luò)表示學(xué)習(xí)解決影響力最大化問題的研究還較少，且還有許多問題有待研究。

受Feng 等［22］研究的啟發(fā)和針對Panagopoulos 研究中的不足，本文利用社交網(wǎng)絡(luò)中用戶自身的行為特性和用戶間的互動(dòng)，提出IMUIR算法。

2 用戶互動(dòng)表示下的影響力最大化算法

2.1 問題定義

Panagopoulos 等［23］在其研究中提出了利用用戶產(chǎn)生的測試級聯(lián)來評估種子集的影響范圍，這樣更貼近真實(shí)社交網(wǎng)絡(luò)的規(guī)律。因此在本文中，給定一個(gè)社交網(wǎng)絡(luò)圖G=(V，E，Q)，V表示社交網(wǎng)絡(luò)中的用戶，E表示用戶關(guān)系，Q表示G中用戶在一個(gè)時(shí)間段T內(nèi)產(chǎn)生的同類型社交事件，事件的類型包括但不限于發(fā)博、評論、點(diǎn)贊和投票等用戶交互行為。按照時(shí)間順序?qū)r(shí)間T中的事件劃分為訓(xùn)練級聯(lián)Qtrain和測試級聯(lián)Qtest，影響力最大化問題就是從G中找到一組大小為K(K≤|V|)的用戶集合U，使得U在Qtest中的影響范圍σ(U)最大，形式化定義如下：

其中U*為最佳用戶集合。

2.2 構(gòu)建用戶上下文對

利用網(wǎng)絡(luò)結(jié)構(gòu)求解影響力最大化問題時(shí)存在一個(gè)弊端，大多數(shù)固定的社交網(wǎng)絡(luò)結(jié)構(gòu)均來自用戶的關(guān)注列表和粉絲列表，但在社交網(wǎng)絡(luò)中通常都會(huì)存在“僵尸用戶”，這些“僵尸用戶”的存在對用戶影響力的評估是沒有意義的，甚至?xí)?dǎo)致評估產(chǎn)生偏差。而事件記錄了一個(gè)用戶在過去一段時(shí)間T內(nèi)與網(wǎng)絡(luò)中其他用戶的互動(dòng)行為，利用這些互動(dòng)行為能較好地捕捉到用戶之間的影響傳播。Panagopoulos 等［23］在其研究中證實(shí)了那些在社交網(wǎng)絡(luò)中具有較大影響力的用戶多數(shù)都是在事件中發(fā)起互動(dòng)的用戶，也就是一個(gè)互動(dòng)級聯(lián)的產(chǎn)生者，而不是參與者。同時(shí)，根據(jù)影響力的傳播動(dòng)力學(xué)研究顯示，由于影響衰減，最近鄰域范圍內(nèi)的影響評估往往是最可靠的［24］。因此本文在構(gòu)建用戶上下文對時(shí)僅考慮用戶的直接互動(dòng)，通過事件中的用戶互動(dòng)級聯(lián)進(jìn)行采樣，并且僅對產(chǎn)生互動(dòng)級聯(lián)的用戶進(jìn)行采樣，利用該方法相當(dāng)于對網(wǎng)絡(luò)中的用戶進(jìn)行了初步篩選。

給定一個(gè)社交事件Qtrain，Xi為事件Qtrain中的一個(gè)用戶互動(dòng)級聯(lián)，在Xi中ui(ui∈V) 為該互動(dòng)的發(fā)起 者，vi={vi1，vi2，…，vik}(vi?V)表示在該級聯(lián)下與ui進(jìn)行互動(dòng)的k個(gè)用戶集合。以ui為源用戶，從集合vi中隨機(jī)選取目標(biāo)用戶構(gòu)建ui的用戶上下文對context(ui)={(ui，vi1)，(ui，vi2)，…，(ui，vik)}，由于只考慮直接互動(dòng)，因此事件中的級聯(lián)是一對多的關(guān)系，一個(gè)用戶上下文對中只有兩位用戶，分別是源用戶和目標(biāo)用戶。根據(jù)圖2 的事件描述可給出具體例子，X2是事件Qtrain中的一個(gè)用戶互動(dòng)級聯(lián)，在X2中，u2是發(fā)布微博的源用戶，v2={v21，v22，v23}是轉(zhuǎn)發(fā)了該條微博的目標(biāo)用戶，假設(shè)從v2中隨機(jī)選取兩個(gè)用戶v21和v22，那么可構(gòu)建u2的用戶上下文對context(u2)={(u2，v21)，(u2，v22)}，該集合表示u2直接影響了v21和v22。利用同樣的方法可構(gòu)建任意一個(gè)ui的用戶上下文對。

圖2 事件描述Fig.2 Event description

2.3 SkipGram模型

SkipGram 本質(zhì)上是一個(gè)神經(jīng)語言模型，在自然語言處理中被廣泛使用，可根據(jù)單詞向量表示利用當(dāng)前的單詞Wi預(yù)測其上下文Wi-2，Wi-1，Wi+1，Wi+2出現(xiàn)的概率，它規(guī)定了固定長度的“詞窗口”，Wi的上下文僅由“詞窗口”內(nèi)的單詞組成而非整個(gè)句子。將該思想運(yùn)用到網(wǎng)絡(luò)表示學(xué)習(xí)中就是預(yù)測一個(gè)當(dāng)前用戶的上下文概率假設(shè)出現(xiàn)在用戶ui上下文中的各個(gè)用戶間相互獨(dú)立，那么用戶ui上下文的概率如下所示：

SkipGram 模型的目標(biāo)是最大化用戶上下文的聯(lián)合概率，并以此來更新用戶的向量表示，因此目標(biāo)函數(shù)的定義如式（3）所示：

其 中：w∈context(ui) 表示用戶ui的上下文用戶w；(ui，context(ui)) ∈Xi表示ui的上下文對均來自Xi。

要計(jì)算目標(biāo)函數(shù)的值ψ，首先需要計(jì)算用戶上下文對中ui對w的概率p(|w ui)，這個(gè)概率的計(jì)算需要通過表示用戶間關(guān)系的特征向量來完成；θ為模型訓(xùn)練過程中需要更新的參數(shù)，也就是用戶的特征向量矩陣，d為特征向量的維度，該矩陣可表示為

在本文方法中，將ui這類產(chǎn)生影響的用戶稱作源特征，表示為；將w這些受別人影響的用戶稱作目標(biāo)特征，表示為Tw；b表示ui的影響偏置；ui對w的影響概率p(|w ui)可以利用學(xué)習(xí)到的特征向量經(jīng)softmax函數(shù)得出，定義為

2.4 尋找種子集

由于媒體時(shí)代信息的快速更新使得用戶信息產(chǎn)生了存活時(shí)長，而用戶活躍度和用戶間交互聯(lián)系度在一定程度上決定了信息存活時(shí)長。在日常的社交網(wǎng)絡(luò)平臺的使用中，如果一個(gè)源用戶在平臺上的活躍度越高，源用戶和目標(biāo)用戶間的交互聯(lián)系就越頻繁，這樣可以增加源用戶的信息存活時(shí)長，那么源用戶的影響力也會(huì)越大。本文中的用戶活躍度a是指源用戶在一個(gè)事件中產(chǎn)生級聯(lián)的次數(shù)，產(chǎn)生級聯(lián)的次數(shù)越多，用戶的活躍度也越高。

交互聯(lián)系度f是源用戶ui與網(wǎng)絡(luò)中其余用戶的互動(dòng)聯(lián)系的多少。首先利用特征向量根據(jù)式（5）計(jì)算ui對網(wǎng)絡(luò)中其余用戶的影響概率，選出網(wǎng)絡(luò)中受ui影響最大的前α個(gè)目標(biāo)用戶（α為用戶在Qtrain中產(chǎn)生的平均級聯(lián)長度），因此，ui的交互聯(lián)系度就是ui對網(wǎng)絡(luò)中其余用戶影響概率降序排列后前α個(gè)目標(biāo)用戶的影響概率總和：

本文根據(jù)用戶活躍度和交互聯(lián)系度利用貪心策略尋找最佳種子集，具體思想是：1）根據(jù)源用戶在Qtrain中出現(xiàn)的次數(shù)計(jì)算源用戶的活躍度a，選取部分活躍度高的用戶作為候選種子集；2）根據(jù)式（6）計(jì)算候選種子集中每個(gè)源用戶對網(wǎng)絡(luò)中其余用戶的影響概率，利用貪心策略選出當(dāng)前f(ui)最大的源用戶ui加入最佳種子集中，之后將選出的ui和受其影響最大的α個(gè)用戶從網(wǎng)絡(luò)中刪除；3）重復(fù)過程2）直到迭代完成。具體算法描述如下所示：

輸入 種子集大小K，事件Qtrain，源特征，目標(biāo)特征Tw；

輸出 最佳種子集U*。

2.5 時(shí)間復(fù)雜度分析

根據(jù)用戶采樣、訓(xùn)練模型和尋找種子集對IMUIR 算法進(jìn)行時(shí)間復(fù)雜度分析。設(shè)采樣數(shù)為I，特征向量的維數(shù)為m，Qtrain中的影響傳播用戶數(shù)為n，負(fù)采樣數(shù)為M，種子集大小為K，候選種子集大小為|C|，訓(xùn)練過程中的收斂次數(shù)為D，則IMUIR的時(shí)間復(fù)雜度為：

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)與對比算法

本文使用Digg和Weibo兩個(gè)真實(shí)的社交網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)集除了有真實(shí)網(wǎng)絡(luò)，還包括用戶的日?；?dòng)級聯(lián)，根據(jù)時(shí)間將前80%的級聯(lián)作為訓(xùn)練集，將剩余級聯(lián)作為測試集，詳細(xì)信息如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集Tab.1 Datasets used in experiments

經(jīng)實(shí)驗(yàn)測試，本文提出的IMUIR的參數(shù)設(shè)置為：采樣率為400%，學(xué)習(xí)率為0.02，向量維度的設(shè)置參考了部分表示學(xué)習(xí)對于節(jié)點(diǎn)向量的人為設(shè)定，設(shè)定為50。同時(shí)為了驗(yàn)證所提算法IMUIR 的性能，選取下述4 個(gè)具有代表性的算法進(jìn)行對比實(shí)驗(yàn)。

1）Random：該算法從網(wǎng)絡(luò)中隨機(jī)選擇K個(gè)用戶作為種子節(jié)點(diǎn)。

2）Average Cascade（AC）：該算法的思想是利用用戶產(chǎn)生的平均級聯(lián)大小來決定種子集中的節(jié)點(diǎn)，產(chǎn)生的平均級聯(lián)越長，就越有可能被選為種子節(jié)點(diǎn)。

3）Kcore：根據(jù)網(wǎng)絡(luò)中用戶的核數(shù)來決定種子節(jié)點(diǎn)。

4）Imfector：利用多任務(wù)神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)得到用戶的向量表示和用戶可能產(chǎn)生的級聯(lián)大小，利用特征向量計(jì)算用戶的期望影響用戶的比例Λ，根據(jù)Λ與影響擴(kuò)散概率選取種子節(jié)點(diǎn)。在對比時(shí)，該算法的向量維度為50，采樣率為120%，學(xué)習(xí)率為0.1，與其論文中的設(shè)置一致［23］。

本文所有算法均使用Python3 編寫，在Windows 10 系統(tǒng)的PC端上運(yùn)行，硬件配置為2.3 GHz Intel i5-6300HQ處理器，8 GB內(nèi)存。

3.2 結(jié)果分析

評價(jià)影響力最大化算法通常使用影響擴(kuò)散范圍和運(yùn)行時(shí)間這兩個(gè)指標(biāo)。本文的影響擴(kuò)散范圍是指在測試級聯(lián)Qtest中與種子用戶互動(dòng)的用戶數(shù)量，數(shù)量越多，種子集影響力越大［23］。運(yùn)行時(shí)間是指算法找到最佳種子集所需要的時(shí)間，IMUIR 和Imfector 的時(shí)間包含采樣、訓(xùn)練和尋找種子集三部分。

3.2.1 種子集質(zhì)量評估

在利用算法找到最佳種子集后，首先需要找到種子用戶出現(xiàn)在測試集中的數(shù)量，這主要是根據(jù)種子用戶能否在未來的一段時(shí)間內(nèi)產(chǎn)生影響來評估選出的用戶集合的質(zhì)量。在Digg和Weibo數(shù)據(jù)集中找到的種子用戶數(shù)如表2、3所示，在指定的種子大小下基于用戶級聯(lián)的表示學(xué)習(xí)方法找到的種子用戶比基于網(wǎng)絡(luò)結(jié)構(gòu)的方法多，而在表示學(xué)習(xí)的方法中，IMUIR能找到的種子集數(shù)量比Imfector 多。這說明利用表示學(xué)習(xí)尋找到種子集的方法是可行的，并且IMUIR 能找到的有效節(jié)點(diǎn)更多，種子集質(zhì)量優(yōu)于其他方法。

表2 Digg中找到的種子用戶數(shù)量Tab.2 Number of seed users found in Digg

3.2.2 影響范圍對比

在影響范圍圖中，X軸表示不同大小的種子集，Y軸對應(yīng)不同種子集下影響的用戶數(shù)量。

圖3 展示了5 個(gè)算法在兩個(gè)數(shù)據(jù)集和不同種子集大小下的實(shí)驗(yàn)結(jié)果，從Digg 數(shù)據(jù)集可以發(fā)現(xiàn)，IMUIR 算法表現(xiàn)最好，當(dāng)種子集大小為200 時(shí)，其影響范圍比Random、AC、Kcore 和Imfector 分別高了13.59%、39.47%、16.10%和5.90%，產(chǎn)生的影響范圍最廣，Imfector其次，而AC表現(xiàn)最差。值得注意的是，結(jié)合表2 和圖3（a）可以看到，當(dāng)種子集大小為80 時(shí)，IMUIR 找到的56 個(gè)高質(zhì)量用戶產(chǎn)生的影響范圍是31 144，而Imfector 找到的50 個(gè)高質(zhì)量用戶產(chǎn)生的影響范圍是33 417，Imfector 在高質(zhì)量種子比IMUIR 少了6 個(gè)的情況下影響范圍比IMUIR高了7.29%，產(chǎn)生的原因可能有兩個(gè)：一方面是因?yàn)镮MUIR 找到的這56 個(gè)種子在影響傳播時(shí)產(chǎn)生了富集性，通常來說就是有一部分用戶可能受到多個(gè)種子用戶的影響，出現(xiàn)在了多個(gè)種子用戶產(chǎn)生的級聯(lián)下，由此產(chǎn)生了影響重疊；另一方面是種子用戶在未來的這段時(shí)間內(nèi)自身產(chǎn)生的影響范圍較小。此外，當(dāng)種子集大小為200 時(shí)，Kcore 與Random 相比影響范圍低了2.2%也是上述原因之一導(dǎo)致的。當(dāng)種子集大小為20 時(shí)，在IMUIR 和Imfector 中均找到15 個(gè)能夠產(chǎn)生影響的種子用戶，但I(xiàn)MUIR的影響范圍比Imfector高了4.4%。

圖3 影響范圍對比Fig.3 Comparison of influence scope

在Weibo 數(shù)據(jù)集中，從整體來看，基于表示學(xué)習(xí)的IMUIR和Imfector的表現(xiàn)遠(yuǎn)優(yōu)于其余三個(gè)算法，但I(xiàn)MUIR依舊表現(xiàn)最好，而Random 表現(xiàn)最差。當(dāng)種子集大小為2 000時(shí)，IMUIR 的影響范圍比Random、AC、Kcore 和Imfector 分別高304.19%、16.53%、18.48%和0.58%。同樣結(jié)合表3 和圖3（b）可以看到，AC 與Random、AC 與Kcore 也出現(xiàn)了上述在Digg 數(shù)據(jù)集中討論過的現(xiàn)象，當(dāng)種子集大小為200和400時(shí)，Random 中能產(chǎn)生影響的種子數(shù)量比AC 多，但在傳播范圍上AC 比Random多了174.82%和217.34%。當(dāng)種子集大小為2 000 時(shí)，Kcore中能產(chǎn)生影響的種子數(shù)比AC 多了129 個(gè)，但影響范圍比AC低了1.64%。

表3 Weibo中找到的種子用戶數(shù)量Tab.3 Number of seed users found in Weibo

此外，為了進(jìn)一步證明IMUIR 的有效性，將Qtest中產(chǎn)生的級聯(lián)大小排在前K的源用戶所組成的種子集產(chǎn)生的影響范圍C(k)（k為種子集大?。┳鳛閰⒖蓟€，并將5個(gè)算法與C(k)進(jìn)行影響范圍對比，獲得在以C(k)為基線的參考下，5個(gè)算法影響范圍降低或提高的百分比，如表4 和表5 所示，其中：“+”表示算法的影響范圍與C(k)相比提高的百分比，“-”則表示降低的百分比。

表4 各算法在Digg上與C(k)影響范圍的對比 單位：%Tab.4 Comparison of influence scope of different algorithms on Digg with C(k unit：%

在Digg 數(shù)據(jù)集中可以看到，當(dāng)種子集大小為200 時(shí)，IMUIR 的影響范圍只比C(200)小22.43%，Imfector次之，相差26.76%，而AC 與之相差44.38%，差距最大。在表5 顯示的Weibo 數(shù)據(jù)集中，在不同種子集大小下，IMUIR 的影響范圍均超過了C(k)產(chǎn)生的影響范圍，可能的原因是C(k)產(chǎn)生影響時(shí)有較多的影響重疊，局限了傳播范圍，而IMUIR尋找到的種子集產(chǎn)生的影響重疊不多，影響范圍更廣，說明利用IMUIR尋找到的種子集質(zhì)量更高。

表5 各算法在Weibo上與C(k)影響范圍的對比 單位：%Tab.5 Comparison of influence scope of different algorithms on Weibo with C(k unit：%

上述實(shí)驗(yàn)結(jié)果表明，本文提出的IMUIR 在兩個(gè)數(shù)據(jù)集上表現(xiàn)都較好也較為穩(wěn)定，IMUIR 和Imfector之間的比較也說明了在尋找最佳種子時(shí)考慮用戶的活躍度和交互聯(lián)系度是必要的，而像AC這樣根據(jù)平均級聯(lián)來選擇種子集的算法對用戶級聯(lián)很挑剔，Kcore表現(xiàn)也較為穩(wěn)定，但總體效果不佳。

3.2.3 運(yùn)行時(shí)間對比

圖4 顯示了Kcore、AC、Imfector、IMUIR 這四個(gè)算法在兩個(gè)不同數(shù)據(jù)集上的運(yùn)行時(shí)間對比，這里需要說明的是由于Random 算法的運(yùn)行時(shí)間極短，在Digg 和Weibo 這兩個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間分別為0.81 s 和1.97 s，因此沒有在圖上進(jìn)行顯示。雖然Random 運(yùn)行時(shí)間最短，但其算法性能不穩(wěn)定，效果也不佳。從圖中可以發(fā)現(xiàn)，表示學(xué)習(xí)算法由于要進(jìn)行采樣和學(xué)習(xí)，因此運(yùn)行時(shí)間均比其他幾個(gè)算法多。Kcore也只需要125.847 7 s 就能從Digg 數(shù)據(jù)集中找出最佳種子集，但找到的種子集質(zhì)量不高，傳播的影響范圍也不夠大；AC 相比起Random 和Kcore用時(shí)多一些，但算法性能也不穩(wěn)定，對數(shù)據(jù)結(jié)構(gòu)很挑剔；IMUIR 在兩個(gè)數(shù)據(jù)集上的用時(shí)比Imfector分別多了14.28%和6.53%，但I(xiàn)MUIR 在影響范圍上的優(yōu)勢可以彌補(bǔ)效率上的不足，說明IMUIR 也是能夠解決影響力最大化問題的一種方法。

圖4 不同數(shù)據(jù)集上各算法的運(yùn)行時(shí)間對比Fig.4 Running time comparison of different algotirhms on different datasets

4 結(jié)語

本文基于用戶互動(dòng)表示提出IMUIR 算法，主要利用用戶自身活躍度和特征向量捕捉的交互聯(lián)系度尋找最優(yōu)種子集，并驗(yàn)證了算法的有效性。但利用表示學(xué)習(xí)求解影響力最大化問題還有充足的改進(jìn)空間：一方面針對上述算法可以尋求更便捷的方法以縮短時(shí)間，在兼顧效果的同時(shí)提高效率；另一方面，用戶間不僅僅有行為上的交互，還會(huì)涉及情感交互，在有合適數(shù)據(jù)集的情況下可以將情感交互融合到這種類型的影響力最大化問題的求解中，以探索更真實(shí)可靠的用戶影響力。