融合級聯(lián)活躍轉(zhuǎn)發(fā)者的社交網(wǎng)絡(luò)影響最大化方法
2022-12-31 00:00:00楊書新林仁耀許景峰梁文
計算機應(yīng)用研究 2022年11期
摘 要：已有的社交網(wǎng)絡(luò)影響最大化研究大多基于網(wǎng)絡(luò)圖結(jié)構(gòu)，沒有利用級聯(lián)數(shù)據(jù)蘊涵的信息，不能有效捕捉用戶間的真實影響。針對此問題，基于級聯(lián)數(shù)據(jù)提出融合級聯(lián)活躍轉(zhuǎn)發(fā)者的影響最大化方法。該方法首先設(shè)計融合活躍轉(zhuǎn)發(fā)者的嵌入式神經(jīng)網(wǎng)絡(luò)模型，通過級聯(lián)轉(zhuǎn)發(fā)記錄有監(jiān)督地訓(xùn)練獲取用戶特征向量，然后根據(jù)信息可達(dá)對象數(shù)量和擴散概率計算融合活躍轉(zhuǎn)發(fā)者的用戶影響力，最后基于貪婪策略選擇種子集。在三種大規(guī)模數(shù)據(jù)集上同四種具有代表性的方法進(jìn)行對比，實驗結(jié)果表明，在信息真實擴散范圍方面，提出方法更具有效性。
關(guān)鍵詞：活躍轉(zhuǎn)發(fā)者；神經(jīng)網(wǎng)絡(luò)；社交網(wǎng)絡(luò)；影響最大化
中圖分類號：TP39 文獻(xiàn)標(biāo)志碼：A 文章編號：1001-3695（2022）11-007-3252-06
doi： 10.19734/j.issn.1001-3695.2022.04.0186
Integrating active information forwarder of cascade for influence maximization
Yang Shuxin1， Lin Renyao1， Xu Jingfeng1， Liang Wen2
（1. School of Information Engineering， Jiangxi University of Science amp; Technology， Ganzhou Jiangxi 341000， China; 2. School of Computer Science amp; Technology， Changchun University of Science amp; Technology， Changchun 130000， China）
Abstract：The existing works for solving the problem of influence maximization mainly focused on graph and didn’t fully exploited the information cascade， which couldn’t effectively capture the actual influence between users. To this end， this paper proposed a new approach integrating active information forwarder for influence maximization based on the information cascade. Firstly， this approach designed an embedded neural network model considering active information forwarder and obtained the feature vectors of users by training model supervised by the actual diffusion record of the cascade data. Then， it presented a measurement method of user influence combining the feature vector of active information forwarder and information initiator according to the number of information reachable objects and diffusion probability. Finally， it selected the seeds by using greedy policy. The experimental results with four approaches on three large-scale data sets show the validity of this proposed approach in the actual spread of information.
Key words：active forwarder; embedded neural network; social network; influence maximization
基金項目：國家自然科學(xué)基金資助項目（61662028）；江西省教育廳科學(xué)技術(shù)研究資助項目（GJJ170518）；江西理工大學(xué)研究生創(chuàng)新計劃資助項目（XY2021-S091）
作者簡介：楊書新（1978-），男（通信作者），江西九江人，教授，碩導(dǎo)，博士，主要研究方向為社交網(wǎng)絡(luò)分析和生物信息（yimuyunlang@sina.com）；林仁耀（1998-），男，江西上饒人，碩士研究生，主要研究方向為社交網(wǎng)絡(luò)分析和數(shù)據(jù)挖掘；許景峰（1997-），男，江西贛州人，碩士研究生，主要研究方向為社交網(wǎng)絡(luò)分析和數(shù)據(jù)挖掘；梁文（1995-），男，吉林梅河口人，博士研究生，主要研究方向為復(fù)雜網(wǎng)絡(luò)分析和量子信息學(xué).
隨著互聯(lián)網(wǎng)的快速發(fā)展，越來越多的互聯(lián)網(wǎng)用戶由信息的接收者成為信息的發(fā)布者，在線社交網(wǎng)絡(luò)成為信息發(fā)布者用來分享生活、學(xué)習(xí)和觀點的平臺。新浪微博正是這樣的在線社交網(wǎng)絡(luò)平臺，自新浪微博上線以來，微博用戶的數(shù)量不斷增多，現(xiàn)如今已成為我國最有影響力的社交平臺之一。在龐大的社交網(wǎng)絡(luò)平臺上，信息發(fā)布者們可以分享他們的所見所聞、學(xué)習(xí)感悟和生活趣事等信息，這些信息會影響平臺中的其他用戶。信息的傳播具有速度快、范圍廣的特點，如何使信息發(fā)布者的信息快速傳播并且影響范圍廣，成為了社交網(wǎng)絡(luò)分析領(lǐng)域的熱點問題。該問題具有巨大的社會和商業(yè)價值，如興趣推薦［1］、市場營銷［2］、輿情監(jiān)管［3］等。
社交網(wǎng)絡(luò)影響最大化的研究目標(biāo)為如何從網(wǎng)絡(luò)圖中選擇出k個用戶開始擴散信息，使得信息的影響范圍最廣。為了解決該問題，學(xué)者們不斷深入研究與總結(jié)。起初，影響最大化的研究思路主要圍繞網(wǎng)絡(luò)圖的拓?fù)浣Y(jié)構(gòu)，從模擬傳播路徑、鄰域節(jié)點和連接情況等角度設(shè)計了節(jié)點影響力的度量方法，再基于貪心式或啟發(fā)式的策略來求解種子集。然而這種研究思路忽略了實際社交中產(chǎn)生的信息級聯(lián)，這些信息級聯(lián)蘊涵豐富的數(shù)據(jù)價值。早在2011年，Goyal等人［4］就已經(jīng)嘗試使用一些網(wǎng)絡(luò)和級聯(lián)來研究影響最大化問題。在此基礎(chǔ)上，2018年，Pei等人［5］和Aral等人［6］進(jìn)行了進(jìn)一步研究，他們的研究表明單靠社交網(wǎng)絡(luò)結(jié)構(gòu)不能獲得信息傳播和影響的真實能力。現(xiàn)有研究忽略了級聯(lián)數(shù)據(jù)中的活躍轉(zhuǎn)發(fā)者對信息擴散的影響，綜合考慮信息級聯(lián)和活躍轉(zhuǎn)發(fā)者，本文提出融合級聯(lián)活躍轉(zhuǎn)發(fā)者的影響最大化方法（integrating active information forwarder for influence maximization，IMIAF）。本文定義了級聯(lián)數(shù)據(jù)的活躍轉(zhuǎn)發(fā)者，設(shè)計了融合信息發(fā)布者和活躍轉(zhuǎn)發(fā)者特征的嵌入式神經(jīng)網(wǎng)絡(luò)模型；提出基于信息發(fā)布者和活躍轉(zhuǎn)發(fā)者特征的用戶影響力計算方法，給出了融合活躍轉(zhuǎn)發(fā)者的種子節(jié)點選擇策略；同三個算法相比，IMIAF在三個數(shù)據(jù)集上的影響擴散范圍最廣，即所選拔的種子節(jié)點具有更高的影響力。
1 相關(guān)文獻(xiàn)
2001年，Domingos等人［7］首次將影響最大化問題引入社交網(wǎng)絡(luò)領(lǐng)域進(jìn)行研究，為單條信息的影響最大化研究奠定了一定基礎(chǔ)。隨后，2003年，Kempe等人進(jìn)一步提出top-k的影響最大化問題，將問題轉(zhuǎn)換為在傳播模型上選擇影響力最大的k個節(jié)點的求解過程。
隨著學(xué)者們對社交網(wǎng)絡(luò)影響最大化問題的不斷研究，現(xiàn)有工作的研究內(nèi)容主要為傳播模型和種子節(jié)點選擇算法。傳播模型是用來描述信息的傳播機制的，可以幫助人們理解信息的傳播過程。針對傳播機制，學(xué)者們給出了不同的傳播模型，比較有代表性的傳播模型有獨立級聯(lián)模型（independent cascade model，IC）［8］、線性閾值模型 （linear threshold model，LT）［9，10］和觸發(fā)模型 （triggering model，TR）［11］等。在種子節(jié)點選擇方面，Kempe等人［11］基于子模特性給出了貪心求解算法 （又名KK算法），該算法每次迭代選擇一個節(jié)點，使得其在已激活集合的基礎(chǔ)上能夠觸發(fā)的新增激活節(jié)點最多。然而，由于依賴大量的隨機擴散模擬，算法的時間成本高。所以，Leskovec等人［12］提出一種改進(jìn)的KK算法，基于子模性質(zhì)利用偷懶估計法來減少對延展度估計的次數(shù)，加速了影響最大化的求解過程。除了貪心算法，另一種是啟發(fā)式算法，Chen等人［13］提出簡單高效的啟發(fā)式方法來求解影響力最大化問題，該方法基于節(jié)點中心度的指標(biāo)，先對激活鄰居對應(yīng)的中心度定量打折，然后再選擇度數(shù)最大的k個節(jié)點。相比于貪心算法，啟發(fā)式算法更簡單且具有效率優(yōu)勢。因此，一些研究考慮了基于擴展的傳播模型，簡化社交網(wǎng)絡(luò)圖結(jié)構(gòu)或剪枝信息擴散路徑以加速影響力最大化的計算［14～16］。由于現(xiàn)有擴散機制忽略了時空因素（如時序關(guān)系、個體與群體關(guān)系等），為了使信息更好地模擬傳播，一些學(xué)者開始研究基于擴展傳播模型的社交網(wǎng)絡(luò)影響最大化方法［17～19］，他們發(fā)掘用戶之間的關(guān)系，在傳統(tǒng)擴散機制的基礎(chǔ)上設(shè)計了更復(fù)雜的擴散模型，這些模型分別為加權(quán)級聯(lián)擴散模型［17］（improved weighted cascade model，IWCM）、熱擴散模型［18］ （heat diffusion-based polarity influence diffusion model，HDPID）和實體競爭擴散模型［19］ （competitive information propagation model considers inactive nodes，CIPMCIN） 等。總的來說，這些影響最大化研究都有兩個特點：a）如何選拔種子節(jié)點依賴于節(jié)點特征（度、密度等）和圖拓?fù)浣Y(jié)構(gòu)（連通分量、橋等）；b）信息需要借助傳播模型在社交圖結(jié)構(gòu)上模擬擴散。當(dāng)評估種子節(jié)點的影響范圍時，這些研究依賴Monte-Carlo模擬。然而，Monte-Carlo模擬時間成本高，使得研究局限于小規(guī)模社交網(wǎng)絡(luò)數(shù)據(jù)。
以上研究依賴于社交網(wǎng)結(jié)構(gòu)和擴散模型，忽略了信息在社交網(wǎng)絡(luò)上的實際產(chǎn)生方式（發(fā)布、轉(zhuǎn)載等）和實際傳播方式（轉(zhuǎn)發(fā)、關(guān)注等）。為此，一些學(xué)者開始利用現(xiàn)實社交網(wǎng)絡(luò)平臺記錄用戶行為，這些用戶行為被保存為擴散級聯(lián)日志。為挖掘這些日志數(shù)據(jù)所蘊涵的信息，一些社交網(wǎng)絡(luò)影響最大化研究開始圍繞級聯(lián)日志數(shù)據(jù)，即級聯(lián)數(shù)據(jù)。Goyal等人使用一些網(wǎng)絡(luò)和級聯(lián)來研究影響最大化問題，以用戶間的行為日志度量用戶影響力，不再簡單基于網(wǎng)絡(luò)拓?fù)湓u估用戶影響力，為圍繞級聯(lián)數(shù)據(jù)的社交網(wǎng)絡(luò)影響最大化研究奠定了一定基礎(chǔ)。在擴散模型中模擬信息擴散往往并不貼近現(xiàn)實，而級聯(lián)信息中的擴散日志由用戶實際行為產(chǎn)生，可以真實反映信息的傳播范圍。為此，Panagopoulos等人［20］提出CELFIE （cost effective lazy forward with influence embeddings）算法，發(fā)掘級聯(lián)數(shù)據(jù)中的真實影響范圍，基于inf2vec［21］和機器學(xué)習(xí)，通過將信息擴散過程簡化為二分網(wǎng)絡(luò)模型 （用戶與用戶之間信息擴散的可能性直接通過模型預(yù)測），求解大規(guī)模社交網(wǎng)絡(luò)的影響最大化問題。為了進(jìn)一步利用轉(zhuǎn)發(fā)級聯(lián)，他們又提出IMINFECTOR（influence maximization with influencer vectors）［22］算法，該算法通過增加擴散級聯(lián)預(yù)測任務(wù)，使信息影響最大化結(jié)果更優(yōu)。相比于傳統(tǒng)影響最大化研究，這些研究不再依賴于社交圖結(jié)構(gòu)信息和模擬信息擴散，而是開始有效利用級聯(lián)數(shù)據(jù)，挖掘級聯(lián)中用戶實際行為，提取級聯(lián)信息的現(xiàn)實擴散范圍。然而，級聯(lián)數(shù)據(jù)中信息豐富，這些研究并沒有挖掘出轉(zhuǎn)發(fā)級聯(lián)中用戶之間的影響。
相比在社交圖結(jié)構(gòu)上以傳播模型模擬信息擴散，級聯(lián)信息中的用戶行為記錄更能反映信息的真實傳播范圍。現(xiàn)有級聯(lián)日志數(shù)據(jù)的社交網(wǎng)絡(luò)影響最大化研究忽略了轉(zhuǎn)發(fā)級聯(lián)日志中的活躍用戶，而活躍用戶往往能促進(jìn)級聯(lián)信息擴散。為此，本文基于級聯(lián)數(shù)據(jù)提出一種融合級聯(lián)活躍轉(zhuǎn)發(fā)者的影響最大化方法IMIAF，挖掘級聯(lián)數(shù)據(jù)中的活躍用戶，提出級聯(lián)活躍轉(zhuǎn)發(fā)者概念。該方法通過融合活躍轉(zhuǎn)發(fā)者特征，并利用級聯(lián)數(shù)據(jù)的真實擴散記錄有監(jiān)督地訓(xùn)練神經(jīng)網(wǎng)絡(luò)，使信息傳播更貼合實際過程。
2 融合級聯(lián)數(shù)據(jù)中的活躍轉(zhuǎn)發(fā)者
2.1 概念定義
社交平臺上的用戶每天發(fā)布大量信息或轉(zhuǎn)發(fā)信息，因此產(chǎn)生了大量信息級聯(lián)。這些信息級聯(lián)包含了級聯(lián)長度和參與傳播的用戶，級聯(lián)能夠反映信息真實的影響范圍。用戶對信息m的發(fā)布和轉(zhuǎn)發(fā)行為可視為用戶參與級聯(lián)。用戶參與信息傳播的行為定義如下：
a）發(fā)布（publish）。用戶u可以產(chǎn)生信息m，通過發(fā)布功能將信息m發(fā)送到社交平臺，形成信息傳播的初始化，記用戶的發(fā)布為Ap。
b）轉(zhuǎn)發(fā)（forward）。用戶u可以轉(zhuǎn)發(fā)他人發(fā)布的信息m，通過轉(zhuǎn)發(fā)功能將信息m轉(zhuǎn)發(fā)至社交平臺，實現(xiàn)信息的擴散，記用戶轉(zhuǎn)發(fā)為Af。
定義1 級聯(lián)。信息的級聯(lián)被定義為式（2）所表示的集合。
其中：Actj表示對信息m的第j個級聯(lián)行為；用戶u為信息m的行為關(guān)聯(lián)人；u的級聯(lián)行為可以是發(fā)起行為Ap或轉(zhuǎn)發(fā)行為Af；t為用戶u發(fā)起行為的時間。
設(shè)O為所有信息發(fā)布者的集合，C（m）為參與信息m的級聯(lián)用戶集合。其中，集合C（m）由一個信息發(fā)布者和多個轉(zhuǎn)發(fā)者組成。在所有轉(zhuǎn)發(fā)者中，有些轉(zhuǎn)發(fā)者是其他信息的發(fā)布者，在這里，稱其為活躍轉(zhuǎn)發(fā)者。
定義2 活躍轉(zhuǎn)發(fā)者。信息m的級聯(lián)中包含級聯(lián)信息發(fā)布者和轉(zhuǎn)發(fā)者，轉(zhuǎn)發(fā)者中有普通轉(zhuǎn)發(fā)者和活躍轉(zhuǎn)發(fā)者，forwarders（m）=forwardersc（m）∪forwardersp（m）。當(dāng)轉(zhuǎn)發(fā)者集合中的用戶u屬于集合O和C（m）時，則將u定義為活躍轉(zhuǎn)發(fā)者，即forwardersc（m）={u1，…，uλ}，u∈O且u∈C（m）。最先發(fā)起轉(zhuǎn)發(fā)的活躍轉(zhuǎn)發(fā)者為最早活躍轉(zhuǎn)發(fā)者u1，u1是集合forwardersc（m）中以轉(zhuǎn)發(fā)時刻升序的第一個用戶。
2.2 級聯(lián)活躍轉(zhuǎn)發(fā)者的影響
活躍轉(zhuǎn)發(fā)者能更好地傳播與擴散信息，但不同的轉(zhuǎn)發(fā)者對信息擴散的影響程度不同。以微信公眾號平臺為例，相比常處于沉默狀態(tài)的用戶（偶爾轉(zhuǎn)發(fā)文章），經(jīng)常發(fā)布文章并轉(zhuǎn)發(fā)其他文章的用戶在平臺中更活躍。由此，以信息的活躍性來區(qū)別轉(zhuǎn)發(fā)者。根據(jù)定義2，活躍轉(zhuǎn)發(fā)者不僅會參與當(dāng)前信息的轉(zhuǎn)發(fā)，而且會發(fā)布新的信息，這說明活躍轉(zhuǎn)發(fā)者對信息的活躍程度比普通轉(zhuǎn)發(fā)者更強。活躍轉(zhuǎn)發(fā)者越早轉(zhuǎn)發(fā)信息，越能讓更多的用戶參與級聯(lián)，也就使得信息的級聯(lián)長度更長。因此，最早活躍轉(zhuǎn)發(fā)者往往更能積極影響信息的擴散。
為了說明活躍轉(zhuǎn)發(fā)者對信息擴散的影響程度，本節(jié)在開源的級聯(lián)數(shù)據(jù)集Digg［23］、Sina Weibo［24］和AMiner［25］中統(tǒng)計了不同長度信息級聯(lián)中的活躍轉(zhuǎn)發(fā)者數(shù)量。若活躍轉(zhuǎn)發(fā)者數(shù)量越多的信息級聯(lián)越長，則說明活躍轉(zhuǎn)發(fā)者對信息擴散的影響程度越深。較長和較短級聯(lián)的平均活躍轉(zhuǎn)發(fā)者數(shù)量統(tǒng)計過程如下：a）按級聯(lián)的長度降序排列；b）由于數(shù)據(jù)集中的級聯(lián)數(shù)據(jù)規(guī)模較大，選取前10%的級聯(lián)為長級聯(lián)和后10%的級聯(lián)為短級聯(lián)；c）分別統(tǒng)計活躍轉(zhuǎn)發(fā)者在對應(yīng)長短類別級聯(lián)的總數(shù)，并計算對應(yīng)類別中級聯(lián)的活躍轉(zhuǎn)發(fā)者數(shù)量的平均數(shù)量。長短級聯(lián)的平均活躍轉(zhuǎn)發(fā)者數(shù)量如圖1所示。
圖1的橫坐標(biāo)為開源數(shù)據(jù)集，縱坐標(biāo)為平均活躍轉(zhuǎn)發(fā)者數(shù)量。從圖1中能看出，在不同數(shù)據(jù)集上，長級聯(lián)數(shù)據(jù)比短級聯(lián)數(shù)據(jù)的平均活躍轉(zhuǎn)發(fā)者數(shù)量都多，整體上說明活躍轉(zhuǎn)發(fā)者對于信息級聯(lián)的長度存在影響且影響積極。級聯(lián)長度越長的信息說明被轉(zhuǎn)發(fā)的越多，信息可達(dá)用戶也就更多，擴散范圍也就越廣。因此，活躍轉(zhuǎn)發(fā)者能積極影響信息的擴散。
2.3 融合活躍轉(zhuǎn)發(fā)者模型
鑒于基于神經(jīng)網(wǎng)絡(luò)模型計算傳播概率［22］能捕捉到信息傳播過程的高階相關(guān)性，同時為了更好地融合活躍轉(zhuǎn)發(fā)者對信息傳播的影響，設(shè)計了融合活躍轉(zhuǎn)發(fā)者特征的嵌入式神經(jīng)網(wǎng)絡(luò)模型。嵌入式部分主要為初始化所有用戶的表示向量和特征融合。神經(jīng)網(wǎng)絡(luò)部分?jǐn)M以級聯(lián)的信息發(fā)布者和活躍轉(zhuǎn)發(fā)者的特征融合向量為輸入，通過級聯(lián)的真實影響范圍進(jìn)行有監(jiān)督訓(xùn)練。
基于上述思路，設(shè)計如圖2所示的模型。模型由四個部分組成，分別為輸入層、嵌入式層、神經(jīng)網(wǎng)絡(luò)層和輸出層。輸入層是信息級聯(lián)的用戶。在嵌入式層中，SI×E表示所有級聯(lián)信息發(fā)布者對應(yīng)的初始嵌入式特征向量矩陣，其中I表示所有級聯(lián)信息發(fā)布者的數(shù)量，E表示嵌入式特征向量指定的維度。根據(jù)定義2，從上層輸入的用戶提取出級聯(lián)信息發(fā)布者u和最早活躍轉(zhuǎn)發(fā)者i，并根據(jù)u和i的索引得到矩陣SI×E中對應(yīng)的嵌入式特征向量Su和Si。方法重點關(guān)注最早活躍轉(zhuǎn)發(fā)者，將最早活躍轉(zhuǎn)發(fā)者i作為級聯(lián)信息發(fā)布者u的信息擴散影響因素。隨后，以i作為u的融合對象，將Su和Si特征融合后的向量作為神經(jīng)網(wǎng)絡(luò)層輸入，其中特征融合為特征的值相加并保持向量維度不變，Su、Si的特征維度和神經(jīng)網(wǎng)絡(luò)層輸入向量的特征維度相等。神經(jīng)網(wǎng)絡(luò)層是由N個神經(jīng)元組合而成，每個神經(jīng)元都有其權(quán)重和偏置參數(shù)，WE×N表示權(quán)重矩陣，其中N表示設(shè)計網(wǎng)絡(luò)中所有用戶集合的數(shù)量，bn表示偏置向量，n為偏置向量長度且值與N相等。輸出層的函數(shù)f為sigmoid函數(shù)，該函數(shù)能將前一層網(wǎng)絡(luò)的輸出數(shù)值映射為數(shù)值為0～1的概率值。
設(shè)級聯(lián)信息的發(fā)布者為訓(xùn)練對象，對象的標(biāo)簽則為該級聯(lián)信息能傳播到的用戶。根據(jù)級聯(lián)信息發(fā)布者的標(biāo)簽，將模型進(jìn)行有監(jiān)督訓(xùn)練。類比圖像識別，神經(jīng)網(wǎng)絡(luò)輸出值經(jīng)過sigmoid 函數(shù)生成識別類別的概率向量，將經(jīng)過sigmoid 函數(shù)的概率向量視為信息對目標(biāo)用戶的傳播概率向量。常見的損失函數(shù)有均方誤差損失函數(shù)和交叉熵?fù)p失函數(shù)等，其中交叉熵?fù)p失函數(shù)使用了sigmoid 函數(shù)，能避免神經(jīng)網(wǎng)絡(luò)在梯度下降時學(xué)習(xí)速率降低的問題。為了驗證模型的效果，設(shè)計了融合活躍轉(zhuǎn)發(fā)者特征的損失函數(shù)。損失函數(shù)如式（3）所示。
其中：y為對應(yīng)級聯(lián)用戶在所有用戶序列中的索引序號的布爾值向量，在級聯(lián)中出現(xiàn)的用戶布爾值為1，未在級聯(lián)中出現(xiàn)的用戶布爾值為0；α為特征向量Su的融合權(quán)重；1-α為特征向量Si的融合權(quán)重；α∶（1－α）為特征融合的權(quán)重比例；W為神經(jīng)網(wǎng)絡(luò)層中的權(quán)重矩陣；b為神經(jīng)網(wǎng)絡(luò)層中的偏置向量。
嵌入式神經(jīng)網(wǎng)絡(luò)通過隨機梯度下降函數(shù)來優(yōu)化訓(xùn)練過程中的損失值，模型在學(xué)習(xí)率為r的梯度下降過程中，損失值L會隨迭代次數(shù)q的不斷增大而逐漸趨于最小值，每次訓(xùn)練結(jié)束后，模型會將誤差反向傳遞來更新神經(jīng)網(wǎng)絡(luò)層中的權(quán)重矩陣W和偏置向量b，級聯(lián)信息發(fā)布者u和活躍轉(zhuǎn)發(fā)者i的特征向量也隨著誤差的反向傳遞而更新數(shù)值。Su和Si的更新如式（4）所示。
3 種子節(jié)點選擇
訓(xùn)練完2.3節(jié)定義的嵌入式神經(jīng)網(wǎng)絡(luò)模型，可以計算級聯(lián)信息發(fā)布者u對所有用戶的信息傳播概率向量。傳播概率向量的計算如式（5）所示。
綜合考慮最早活躍轉(zhuǎn)發(fā)者對信息擴散的影響，將Su和Si按α∶（1－α）進(jìn)行融合并進(jìn)行歸一處理，通過式（6）計算級聯(lián)信息發(fā)布者u的信息可達(dá)對象數(shù)量κu。
其中：κu為用戶u的信息可達(dá)對象數(shù)量；floor 為下限函數(shù)；γ為所有級聯(lián)中不同的用戶數(shù)量；I（C）為所有級聯(lián)的信息發(fā)起者集合。
在可達(dá)用戶數(shù)量κu的基礎(chǔ)上，級聯(lián)信息發(fā)布者u的影響力計算公式如式（7）所示。
其中：P^u，η為Pu按值降序排列后的第η個概率值。
在獲得節(jié)點信息傳播概率向量和用戶節(jié)點影響力的技術(shù)上，采用了以下種子節(jié)點選取規(guī)則：a）影響力越大，越易擴散信息，先找出最大影響力u的節(jié)點；b）為了規(guī)避已選擇節(jié)點，記錄前κu個Pu向量中概率大的節(jié)點為可達(dá)對象集；c）重新計算除可達(dá)對象外的用戶節(jié)點傳播概率向量和用戶節(jié)點影響力值；d）基于貪心啟發(fā)策略，循環(huán)執(zhí)行步驟a）～c），每輪選擇當(dāng)前影響力值最大的節(jié)點為種子節(jié)點，直至選擇出k個種子為止。這些種子節(jié)點最終在理論上可達(dá)到理想的傳播范圍。
根據(jù)以上規(guī)則和2.3節(jié)介紹的嵌入式神經(jīng)網(wǎng)絡(luò)模型，給出融合最早活躍轉(zhuǎn)發(fā)者特征的種子節(jié)點選擇算法，如算法1所示。
算法1 融合最早活躍轉(zhuǎn)發(fā)者特征的種子節(jié)點選擇
輸入： 預(yù)選種子節(jié)點數(shù)量k，候選種子節(jié)點集合H。
輸出： 信息擴散的初始種子節(jié)點集合Z。
1 initialize S，W，α，epoch， empty list P={}，Ω={}，U={};
2 while epochgt;0 do //訓(xùn)練模型
3 for u in H do
4 i=FindFirst（u）;//查找最早活躍轉(zhuǎn)發(fā)者
5 compute loss by using 式（3）;
6 update Su，Si by using 式（4）;
7 end for
8 epoch--;
9 end while
10 for u in H do
11 compute Pu by using 式（5）;
12 compute κu by using 式（6）;
13 compute u by using 式（7）;
14 P.add（Pu）;
15 Ω.add（κu）;
16 U.add（u）;
17 end for
18 for （j=0;jlt;k;j++）
19 curr_seed=sort（U）［0］.user;
20 Z.add（curr_seed）;
21 H.delete（curr_seed）;
22 top_users=sort（P.get（curr_seed））
［0：Ω.get（curr_seed）］.users;
23 U={};
24 for s in H do
25 P.get（s）.removeValues（［top_users］）;
26 compute s by using 式（7）;
27 U.add（s）;
28 end for
29 end for
30 return Z。
在算法1中，第1行是模型初始階段，初始化嵌入式層中的嵌入式矩陣S、神經(jīng)網(wǎng)絡(luò)層的權(quán)重矩陣W、特征向量Su的融合權(quán)重α、模型迭代訓(xùn)練次數(shù)epoch、列表U、P和Ω。第2～9行是模型的訓(xùn)練階段，u表示級聯(lián)信息發(fā)布者集合的用戶，i表示u對應(yīng)的最早活躍轉(zhuǎn)發(fā)者。在嵌入式層，將u的特征向量融合i的特征向量，把融合向量作為神經(jīng)網(wǎng)絡(luò)層的輸入。隨后，在神經(jīng)網(wǎng)絡(luò)層中，模型先根據(jù)式（5）前向計算，然后以式（3）計算損失值（第5行），再根據(jù)損失值反向傳遞更新權(quán)重矩陣W和偏置向量b并使用梯度下降法更新Su和Si（第6行），最后迭代直至訓(xùn)練次數(shù)epoch為0。第10～17行是候選種子參數(shù)的記錄階段，列表U記錄所有信息發(fā)布者節(jié)點的影響力值，列表P記錄所有信息發(fā)布者節(jié)點的傳播概率向量，列表Ω記錄所有信息發(fā)布者的信息可達(dá)對象數(shù)量。第18～29行為種子節(jié)點選擇的迭代階段，curr_seed表示為當(dāng)前影響力最大用戶節(jié)點（第19行）。第22～28行為更新影響力過程，top_users為種子節(jié)點curr_seed的所有可達(dá)對象用戶，重置列表U后，更新剩余候選節(jié)點的傳播概率向量和影響力。其中，更新剩余候選節(jié)點的影響力所用的概率向量需規(guī)避可達(dá)對象，故將剩余候選節(jié)點的傳播概率向量剔除可達(dá)對象對應(yīng)的概率值（第25行）。在算法1中，模型訓(xùn)練時間復(fù)雜度為O（epoch·Hsize），Hsize為初始候選種子集合H的數(shù)量，種子節(jié)點選擇算法的時間復(fù)雜度為O（（epoch+k）·Hsize），k為種子節(jié)點個數(shù)。
4 實驗
4.1 實驗數(shù)據(jù)
相比于傳統(tǒng)的社交網(wǎng)絡(luò)圖數(shù)據(jù)，帶有級聯(lián)數(shù)據(jù)的數(shù)據(jù)能更好地描述信息傳播的實際情況，其數(shù)據(jù)也更有利于社交分析。因此，選擇數(shù)據(jù)集Digg、Sina Weibo和AMiner作為實驗數(shù)據(jù)集，這些數(shù)據(jù)集的用戶之間存在著較多的信息級聯(lián)。實驗數(shù)據(jù)集的用戶數(shù)和級聯(lián)數(shù)如表1所示。
數(shù)據(jù)集Digg、Sina Weibo和AMiner分別下載于開源地址https：//www.isi.edu/～lerman/downloads/digg2009.html、https：//www.
aminer.cn/influencelocality和https：//www.aminer.cn/aminernetwOrk。Digg是一個由社交媒體網(wǎng)站衍生的朋友關(guān)系網(wǎng)絡(luò)和級聯(lián)數(shù)據(jù)集，其轉(zhuǎn)發(fā)記錄構(gòu)成級聯(lián)數(shù)據(jù)；Sina Weibo是一個由新浪微博平臺提供的真實社交網(wǎng)絡(luò)和級聯(lián)數(shù)據(jù)集，其轉(zhuǎn)載日志構(gòu)成級聯(lián)數(shù)據(jù)；AMiner是一個論文作者（發(fā)布者）網(wǎng)絡(luò)和級聯(lián)數(shù)據(jù)集，其論文引用（轉(zhuǎn)發(fā)記錄）構(gòu)成級聯(lián)數(shù)據(jù)。
4.2 實驗設(shè)計與環(huán)境
傳統(tǒng)影響最大化方法通過蒙特卡羅模擬仿真實驗，需要將社交網(wǎng)絡(luò)中的種子節(jié)點以指定擴散模型模擬信息擴散數(shù)千或（甚至）萬次，仿真擴散結(jié)果為激活節(jié)點數(shù)量的均值。但當(dāng)社交網(wǎng)絡(luò)規(guī)模較大時，仿真實驗的代價過大、模擬信息擴散過程漫長，所以大多傳統(tǒng)影響最大化方法不能直接應(yīng)用于大規(guī)模數(shù)據(jù)集，如基于割點的CVIM（cut-vertex-based influence maximization）［16］、基于擴展擴散模型的TIM（two-stage impact maximization）［17］等。相比之下，在級聯(lián)數(shù)據(jù)中通過統(tǒng)計信息轉(zhuǎn)發(fā)級聯(lián)規(guī)模得到信息擴散范圍的方式簡單高效，適用大規(guī)模數(shù)據(jù)，同時又能真實反映信息的實際擴散。因此，實驗以級聯(lián)中真實影響范圍作為衡量指標(biāo)。為了驗證融合最早活躍轉(zhuǎn)發(fā)者的特征能使信息更好地擴散，本實驗將IMIAF和其他具有代表性的算法進(jìn)行對比。在相關(guān)工作中，大多算法是基于社交圖結(jié)構(gòu)數(shù)據(jù)驗證且不適合規(guī)模大的數(shù)據(jù)集，因此選擇與AVG-CS［26］、K-cores［27］、CELFIE［20］和IMINFECTOR［22］進(jìn)行比較。各算法簡介如表2所示。
在種子節(jié)點選擇上，AVG-CS通過計算平均級聯(lián)數(shù)，并以級聯(lián)數(shù)屬性選擇種子集合；K-cores通過無向k核分解得到節(jié)點的核心數(shù)，并綜合節(jié)點的核心數(shù)和度數(shù)兩個屬性選擇種子集合；CELFIE基于inf2vec［21］，先將用戶特征向量化表示，然后結(jié)合機器學(xué)習(xí)方法篩選種子節(jié)點；IMINFECTOR通過其模型計算表示學(xué)習(xí)向量，以表示學(xué)習(xí)向量為基礎(chǔ)設(shè)計篩選種子節(jié)點方法。
在本實驗中，將用戶和最早活躍轉(zhuǎn)發(fā)者的特征向量的維度設(shè)置為50，神經(jīng)網(wǎng)絡(luò)模型的學(xué)習(xí)率和迭代訓(xùn)練次數(shù)分別設(shè)置為0.1和10。為了更好地體現(xiàn)信息發(fā)布者特征在特征融合中的主體作用，設(shè)置參數(shù)α≥0.5。實驗從信息的擴散角度出發(fā)，對比分析種子節(jié)點的信息擴散效果，從而評價算法的有效性。考慮到種子節(jié)點數(shù)量對各算法的實驗結(jié)果有一定影響，實驗以遞增種子節(jié)點的數(shù)量來觀察算法的影響最大化結(jié)果，Digg、Sina Weibo和AMiner的種子數(shù)量根據(jù)數(shù)據(jù)集規(guī)模設(shè)置為50、1 000和10 000。
實驗運行于服務(wù)器環(huán)境，操作系統(tǒng)使用Linux，CPU為Intel? Xeon? CPU E7-4830 v4 @ 2.00 Hz（14核），內(nèi)存大小為1 TB，固態(tài)硬盤大小為256 TB，機械硬盤大小為128 TB，編程語言使用Python 3.6，深度學(xué)習(xí)框架使用TensorFlow 2.0。
4.3 實驗結(jié)果
由于IMIAF方法的式（3）（6）需要參數(shù)α來設(shè)置信息發(fā)布者u和最早活躍轉(zhuǎn)發(fā)者i的特征向量融合比例，所以需要確定信息發(fā)布者u的特征向量融合權(quán)重α。信息發(fā)布者u和最早活躍轉(zhuǎn)發(fā)者i的特征向量以不同比例融合后，由式（6）得到的信息發(fā)布者的傳播概率向量會有所不同，最早活躍轉(zhuǎn)發(fā)者對實際信息擴散的影響效果也不同，最終導(dǎo)致IMIAF的影響最大化的結(jié)果差異化。為了更深入分析特征融合比例對信息擴散結(jié)果的影響，本節(jié)實驗將調(diào)整級聯(lián)信息發(fā)布者與最早活躍轉(zhuǎn)發(fā)者特征向量的融合比例，即調(diào)整參數(shù)α，分析并總結(jié)不同比例的融合向量對影響最大化的影響效果。哪種特征融合比例的信息擴散的范圍更廣，則說明哪種特征融合比例對算法的有效性提升更有利。圖3為實驗數(shù)據(jù)上IMIAF調(diào)整參數(shù)α的影響最大化結(jié)果。
在圖3中，橫坐標(biāo)為種子節(jié)點的數(shù)量，縱坐標(biāo)為信息的真實擴散范圍值，即真實擴散范圍內(nèi)影響到的去重用戶數(shù)量（distinct nodes influence，DNI）。如圖3所示，Su和Si在不同比例特征融合下對影響最大化結(jié)果有一定的影響，不同數(shù)據(jù)集的實驗結(jié)果也有差異。三個數(shù)據(jù)集中，信息的真實擴散范圍隨著種子個數(shù)呈上升趨勢，但并不是最早活躍轉(zhuǎn)發(fā)者特征向量的融合權(quán)重越高，IMIAF的影響最大化效果越好，這是因為數(shù)據(jù)集的差異性，數(shù)據(jù)集的差異在于長短級聯(lián)中活躍轉(zhuǎn)發(fā)者是否相對離散分布，使得最早活躍轉(zhuǎn)發(fā)者特征向量的融合權(quán)重需要調(diào)整。由圖1可以看出，Sina Weibo和AMiner中長短級聯(lián)的平均活躍轉(zhuǎn)發(fā)者數(shù)量差距相比于Digg較為明顯，活躍轉(zhuǎn)發(fā)者在信息級聯(lián)中更集中于長級聯(lián)，一定程度上說明Sina Weibo和AMiner的活躍轉(zhuǎn)發(fā)者對真實擴散范圍的影響更為明顯。在Digg數(shù)據(jù)集中，α的取值越大，信息的真實擴散范圍值隨之提升，數(shù)據(jù)集中活躍轉(zhuǎn)發(fā)者離散分布，信息發(fā)布者在真實信息擴散過程中更多靠自身影響力，最早活躍轉(zhuǎn)發(fā)者對信息擴散的影響也受到一定局限，因此，在融合活躍轉(zhuǎn)發(fā)者的前提下，信息發(fā)布者特征向量的融合權(quán)重更大，有利于IMIAF的影響最大化結(jié)果，α=0.9時IMIAF的影響最大化結(jié)果較為顯著；在Sina Weibo數(shù)據(jù)集上，調(diào)節(jié)參數(shù)α對IMIAF的影響并沒有Digg數(shù)據(jù)集上明顯，但從整體上看，α=0.6時IMIAF的影響最大化效果更好，最早活躍轉(zhuǎn)發(fā)者特征向量的融合權(quán)重越大，一定程度上能體現(xiàn)出最早活躍轉(zhuǎn)發(fā)對信息擴散的影響越積極；在AMiner數(shù)據(jù)集上，可以看出α=0.6時IMIAF的影響最大化效果更好，隨著提升最早活躍轉(zhuǎn)發(fā)者的權(quán)重，IMIAF的效果也呈現(xiàn)上升趨勢。綜合三個數(shù)據(jù)集的實驗結(jié)果，將實驗參數(shù)α設(shè)置為0.6。
為了驗證IMIAF的有效性，在實驗數(shù)據(jù)集上還將部分經(jīng)典算法和IMIAF的信息擴散范圍值分別進(jìn)行對比。圖4～6分別為各算法在實驗數(shù)據(jù)集上的實驗結(jié)果。
從圖4～6中可以看出，在數(shù)據(jù)集Digg、Sina Weibo和AMiner上，隨著選擇種子節(jié)點數(shù)量的增加，各算法的信息擴散范圍也隨之增大。由于CELFIE對相鄰節(jié)點重復(fù)采樣，導(dǎo)致候選種子的數(shù)量固定，可選拔的種子節(jié)點數(shù)量有限［22］。當(dāng)種子節(jié)點選拔規(guī)模大于CELFIE最多檢索種子數(shù)量時，擴散范圍維持現(xiàn)狀，相比之下，IMIAF不會存在此種限制，隨著種子節(jié)點規(guī)模的擴大，真實擴散范圍隨之增大。此外，考慮了最早活躍轉(zhuǎn)發(fā)者的IMIAF表現(xiàn)有著相對優(yōu)勢，優(yōu)于AVG-CS、K-cores、和IMINFECTOR。在實際的社交網(wǎng)絡(luò)中，最早活躍轉(zhuǎn)發(fā)者通常是有大影響力的轉(zhuǎn)發(fā)人，對信息有時能起到強擴散作用。由此，IMIAF在不同數(shù)據(jù)集上能有效求解影響最大化問題，體現(xiàn)了它的有效性。從圖5還能看出，在種子節(jié)點k=200和300時，IMINFECTOR的信息擴散范圍起伏較大；在種子節(jié)點k=300時，K-cores的信息擴散范圍存在波動。從圖6還能看出，當(dāng)種子節(jié)點在k=4 000和6 000時，K-cores的信息擴散范圍存在波動。
5 結(jié)束語
由于個人信息的傳播范圍有限，融合活躍轉(zhuǎn)發(fā)者特征的發(fā)布者更有利于其信息的影響最大化。IMIAF以融合活躍轉(zhuǎn)發(fā)者特征的傳播概率和影響力來篩選種子節(jié)點，從而求解影響最大化問題。實驗結(jié)果表明，IMIAF相比其他具有代表性的算法在信息擴散范圍上有一定的提升，選擇的種子節(jié)點對信息擴散更有優(yōu)勢。級聯(lián)數(shù)據(jù)所包含的信息豐富，本文方法僅針對級聯(lián)數(shù)據(jù)的活躍用戶，忽略了其他隱含的有價值信息，如信息主題［17］、團體關(guān)系［19］等。因此在未來工作當(dāng)中，應(yīng)當(dāng)考慮如何利用更多有價值的信息，挖掘更具影響力的種子節(jié)點，使算法的性能進(jìn)一步提升。
參考文獻(xiàn)：
［1］Pisarski M，Gralczyk A. From disruption to dialog： days of Judaism on polish Twitter［J］. Religions，2021，12（10）： 828.
［2］Pourkhani A，Abdipour K，Baher B，et al. The impact of social media in business growth and performance： a scientometrics analysis［J］. International Journal of Data amp; Network Science，2019，3（3）： 223-244.
［3］He Ziwei，Tajeuna E G，Wang Shengrui，et al. A comparative study of different approaches for tracking communities in evolving social networks［C］// Proc of IEEE International Conference on Data Science and Advanced Analytics. Piscataway，NJ： IEEE Press，2017： 89-98.
［4］Goyal A，Lu Wei，Lakshmanan L V. SIMPATH： an efficient algorithm for influence maximization under the linear threshold model［C］// Proc of the 11th IEEE International Conference on Data Mining. Piscataway，NJ： IEEE Press，2011： 211-220.
［5］Pei S，Morone F，Liljeros F，et al. Inference and control of the nosocomial transmission of methicillin-resistant staphylococcus aureus［J］. Elife，2018，7： e40977.
［6］Aral S，Dhillon P S. Social influence maximization under empirical influence models［J］. Nature Human Behaviour，2018，2（6）： 375-382.
［7］Domingos P，Richardson M. Mining the network value of customers［C］// Proc of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM Press，2001： 57-66.
［8］Goldenberg J，Libai B，Muller E. Talk of the network： a complex systems look at the underlying process of word-of-mouth［J］. Marketing Letters，2001，12（3）： 211-223.
［9］Granovetter M. Threshold models of collective behavior［J］. American Journal of Sociology，1978，83（6）： 1420-1443.
［10］Connolly T，Schelling T C. Micromotives and macrobehavior［J］. Administrative Science Quarterly，1979，24 （3）： 500-504.
［11］Kempe D，Kleinberg J，Tardos é. Maximizing the spread of influence through a social network［C］// Proc of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM Press，2003： 137-146.
［12］Leskovec J，Krause A，Guestrin C，et al. Cost-effective outbreak detection in networks［C］// Proc of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM Press，2007： 420-429.
［13］Chen Wei，Wang Yajun，Yang Siyu. Efficient influence maximization in social networks［C］// Proc of the 15th ACM SIGKDD Internatio-nal Conference on Knowledge Discovery and Data Mining. New York： ACM Press，2009： 199-208.
［14］Huang Keke，Tang Jing，Xiao Xiaokui，et al. Efficient approximation algorithms for adaptive target profit maximization［C］// Proc of the 36th IEEE International Conference on Data Engineering. Piscataway，NJ： IEEE Press，2020： 649-660.
［15］Deng Xiaoheng，Long Fang，Li Bo，et al. An influence model based on heterogeneous online social network for influence maximization［J］. IEEE Trans on Network Science and Engineering，2020，7（2）： 737-749.
［16］楊書新，宋建繽，梁文. 基于割點的社交網(wǎng)絡(luò)影響最大化問題［J］. 計算機科學(xué)與探索，2022，16（6）：1316-1326. （Yang Shu-xin，Song Jianbin，Liang Wen. Cut-vertex-based influence maximization problem in social network［J］. Journal of Frontiers of Computer Science and Technology，2022，16（6）：1316-1326.）
［17］陳晶，祁子怡. 基于時序關(guān)系的社交網(wǎng)絡(luò)影響最大化算法研究［J］. 通信學(xué)報，2020，41（10）： 211-221. （Chen Jing，Qi Ziyi. Research on social network influence maximization algorithm based on time sequential relationship［J］. Journal on Communications，2020，41（10）： 211-221.）
［18］Wang Yuejiao，Zhang Yatao，Yang Fei，et al. Time-sensitive positive influence maximization in signed social networks［J］. Physica A： Statistical Mechanics and Its Applications，2021，584： 126353.
［19］Xie Xiaoqin，Li Jiahua，Sheng Yi，et al. Competitive influence maximization considering inactive nodes and community homophily［J］. Knowledge-Based Systems，2021，233： 107497.
［20］Panagopoulos G，Malliaros F，Vazirgiannis M. Influence maximization using influence and susceptibility embeddings［C］// Proc of the 14th International AAAI Conference on Web and Social Media. Palo Alto，CA： AAAI Press，2020： 511-521.
［21］Feng Shanshan，Cong Gao，Khan A，et al. inf2vec： latent representation model for social influence embedding［C］// Proc of the 34th IEEE International Conference on Data Engineering. Piscataway，NJ： IEEE Press，2018： 941-952.
［22］Panagopoulos G，Malliaros F，Vazirgiannis M. Multi-task learning for influence estimation and maximization［J］. IEEE Trans on Know-ledge and Data Engineering，2022，34（9）： 4398-4409.
［23］Hogg T，Lerman K. Social dynamics of Digg［J］. EPJ Data Science，2012，1（1）： 1-26.
［24］Zhang Jing，Liu Biao，Tang Jie，et al. Social influence locality for modeling retweeting behaviors［C］// Proc of the 23rd International Joint Conference on Artificial Intelligence. Palo Alto，CA： AAAI Press，2013： 2761-2767.
［25］Tang Jie，Zhang Jing，Yao Limin，et al. ArnetMiner： extraction and mining of academic social networks［C］// Proc of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM Press，2008： 990-998.
［26］Bakshy E，Hofman J M，Mason W A，et al. Everyone’s an influencer： quantifying influence on Twitter［C］// Proc of the 4th ACM International Conference on Web Search and Data Mining. New York： ACM Press，2011： 65-74.
［27］Malliaros F D，Rossi M E，Vazirgiannis M. Locating influential nodes in complex networks［J］. Scientific Reports，2016，6（1）： 1-10.
