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

張 萌，李維華

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

0 引言

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

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

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

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

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

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

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

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

1 相關(guān)研究

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

此外，一些群集智能算法也被運(yùn)用到了影響力最大化的研究中。Jiang 等［14］提出一種評(píng)估預(yù)期影響的函數(shù)EDV（Expect Diffusion Value），結(jié)合模擬退火算法求解影響力最大化問(wèn)題，該算法比利用函數(shù)子模性改進(jìn)的貪心算法CELF（Cost-Effective Lazy Forward）快了近3個(gè)數(shù)量級(jí)；Cui等［15］基于一種降階搜索策略，融合遺傳算法提出度數(shù)遞減搜索（Degree-Descending Search Evolution，DDSE）；Gong 等［16］利用離散離子群算法與評(píng)估節(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)來(lái)計(jì)算的節(jié)點(diǎn)間影響傳播概率；另一方面是通過(guò)擴(kuò)散模型來(lái)計(jì)算受一組種子用戶(hù)影響的節(jié)點(diǎn)數(shù)量，而現(xiàn)有的擴(kuò)散模型依賴(lài)于假設(shè)會(huì)導(dǎo)致結(jié)果不可靠，使得影響力最大化的求解面臨著可擴(kuò)展性［19］。

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

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

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

2.1 問(wèn)題定義

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

其中U*為最佳用戶(hù)集合。

2.2 構(gòu)建用戶(hù)上下文對(duì)

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

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

圖2 事件描述Fig.2 Event description

2.3 SkipGram模型

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

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

其 中：w∈context(ui) 表示用戶(hù)ui的上下文用戶(hù)w；(ui，context(ui)) ∈Xi表示ui的上下文對(duì)均來(lái)自Xi。

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

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

2.4 尋找種子集

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

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

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

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

輸出 最佳種子集U*。

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

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

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

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

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

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

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

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

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

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

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

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

3.2 結(jié)果分析

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

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

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

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

3.2.2 影響范圍對(duì)比

在影響范圍圖中，X軸表示不同大小的種子集，Y軸對(duì)應(yīng)不同種子集下影響的用戶(hù)數(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ì)量用戶(hù)產(chǎn)生的影響范圍是31 144，而Imfector 找到的50 個(gè)高質(zhì)量用戶(hù)產(chǎn)生的影響范圍是33 417，Imfector 在高質(zhì)量種子比IMUIR 少了6 個(gè)的情況下影響范圍比IMUIR高了7.29%，產(chǎn)生的原因可能有兩個(gè)：一方面是因?yàn)镮MUIR 找到的這56 個(gè)種子在影響傳播時(shí)產(chǎn)生了富集性，通常來(lái)說(shuō)就是有一部分用戶(hù)可能受到多個(gè)種子用戶(hù)的影響，出現(xiàn)在了多個(gè)種子用戶(hù)產(chǎn)生的級(jí)聯(lián)下，由此產(chǎn)生了影響重疊；另一方面是種子用戶(hù)在未來(lái)的這段時(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)生影響的種子用戶(hù)，但I(xiàn)MUIR的影響范圍比Imfector高了4.4%。

圖3 影響范圍對(duì)比Fig.3 Comparison of influence scope

在Weibo 數(shù)據(jù)集中，從整體來(lái)看，基于表示學(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ù)集中討論過(guò)的現(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中找到的種子用戶(hù)數(shù)量Tab.3 Number of seed users found in Weibo

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

表4 各算法在Digg上與C(k)影響范圍的對(duì)比 單位：%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 的影響范圍均超過(guò)了C(k)產(chǎn)生的影響范圍，可能的原因是C(k)產(chǎn)生影響時(shí)有較多的影響重疊，局限了傳播范圍，而IMUIR尋找到的種子集產(chǎn)生的影響重疊不多，影響范圍更廣，說(shuō)明利用IMUIR尋找到的種子集質(zhì)量更高。

表5 各算法在Weibo上與C(k)影響范圍的對(duì)比 單位：%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之間的比較也說(shuō)明了在尋找最佳種子時(shí)考慮用戶(hù)的活躍度和交互聯(lián)系度是必要的，而像AC這樣根據(jù)平均級(jí)聯(lián)來(lái)選擇種子集的算法對(duì)用戶(hù)級(jí)聯(lián)很挑剔，Kcore表現(xiàn)也較為穩(wěn)定，但總體效果不佳。

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

圖4 顯示了Kcore、AC、Imfector、IMUIR 這四個(gè)算法在兩個(gè)不同數(shù)據(jù)集上的運(yùn)行時(shí)間對(duì)比，這里需要說(shuō)明的是由于Random 算法的運(yùn)行時(shí)間極短，在Digg 和Weibo 這兩個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間分別為0.81 s 和1.97 s，因此沒(méi)有在圖上進(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)定，對(duì)數(shù)據(jù)結(jié)構(gòu)很挑剔；IMUIR 在兩個(gè)數(shù)據(jù)集上的用時(shí)比Imfector分別多了14.28%和6.53%，但I(xiàn)MUIR 在影響范圍上的優(yōu)勢(shì)可以彌補(bǔ)效率上的不足，說(shuō)明IMUIR 也是能夠解決影響力最大化問(wèn)題的一種方法。

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

4 結(jié)語(yǔ)

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