異質(zhì)信息網(wǎng)絡(luò)中基于元結(jié)構(gòu)的影響力最大化

徐智敏，周麗華

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

1 引言

社交網(wǎng)絡(luò)的發(fā)展為信息的全球傳播和新聞的有效傳播帶來了新的潛力，人們可以直接參與這些社交網(wǎng)絡(luò)，建立自己的友誼網(wǎng)絡(luò)，并相互分享他們的觀點、見解和經(jīng)驗。而確定網(wǎng)絡(luò)中有影響力的成員被視為這種潛力付諸行動的關(guān)鍵因素，影響力最大化問題由此被提出。

Domingos等人[1]首先將影響力最大化問題建模為一個算法問題。Kempe等人[2]首次將影響力最大化問題定義為一個離散最優(yōu)問題，并證明該問題是一個NP-hard問題，同時提出了貪心算法得到了該問題的一個近似解。但貪心算法的時間復(fù)雜度過高，無法高效解決大規(guī)模網(wǎng)絡(luò)問題。對此研究者們相繼提出了許多啟發(fā)式算法[3，4]或改進貪心算法[5，6]以提高運行效率。然而這些方法僅針對同質(zhì)信息網(wǎng)絡(luò)進行考慮，即只考慮了一種對象類型和一種關(guān)系類型，忽略了對象之間的異質(zhì)關(guān)系和潛在的語義信息。

異質(zhì)信息網(wǎng)絡(luò)[7]是一種包含了多種對象類型和多種關(guān)系類型的信息網(wǎng)絡(luò)，能夠更加合理的描述真實的社會網(wǎng)絡(luò)。因此，在異質(zhì)信息網(wǎng)絡(luò)上進行影響力最大化研究更具有現(xiàn)實意義。近些年來，影響力最大化研究的焦點逐漸轉(zhuǎn)向異質(zhì)信息網(wǎng)絡(luò)。楊等人[8]通過多種元路徑提取不同對象之間關(guān)系，來度量節(jié)點的影響力。Kuhnle等人[9]提出了多重網(wǎng)絡(luò)上的影響力最大化算法等。但由于異質(zhì)信息網(wǎng)絡(luò)具有復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)，如何高效的利用異質(zhì)信息一直是異質(zhì)信息網(wǎng)絡(luò)分析的難點問題。

本文的目的是在異質(zhì)信息網(wǎng)絡(luò)中研究相同類型對象的影響力最大化問題，并提出了基于元結(jié)構(gòu)的影響力最大化算法(MSIM)。異質(zhì)信息網(wǎng)絡(luò)中包含了豐富的語義信息，元路徑可以有效地捕獲源對象和目標對象間的單一關(guān)系，但無法捕獲到它們之間的復(fù)雜關(guān)系。而元結(jié)構(gòu)本質(zhì)上可以看作多條元路徑的集合，能夠方便的表達對象間復(fù)雜的關(guān)系。因此，在MSIM算法中采用元結(jié)構(gòu)存儲目標對象與網(wǎng)絡(luò)中所有類型對象間的語義關(guān)系，并且引入信息熵來度量節(jié)點的影響力，提出了路徑熵度量不同元路徑對源節(jié)點的影響貢獻，然后整合了元結(jié)構(gòu)中不同元路徑的路徑熵提出了結(jié)構(gòu)熵度量源節(jié)點的最終影響。最后在真實數(shù)據(jù)集上進行實驗，驗證了該算法的有效性。本文的貢獻主要包含以下三個方面：

1) 提出了一種基于元結(jié)構(gòu)的信息熵影響力最大化算法(MSIM)，該算法為每個目標類型節(jié)點構(gòu)造一個元結(jié)構(gòu)，存儲不同對象之間的異質(zhì)關(guān)系；

2) 提出了路徑熵(PE)和結(jié)構(gòu)熵(SE)來評估一個節(jié)點在異質(zhì)信息網(wǎng)絡(luò)中的重要性，PE值反映了單條路徑對源節(jié)點的影響，SE值反映了局部結(jié)構(gòu)對節(jié)點的影響；

3) 在兩個真實數(shù)據(jù)集上驗證了MSIM算法的有效性和效率，并證明MSIM算法在效率和性能上有較好的折中。

2 相關(guān)工作

影響力最大化問題在2003年首次被定義為一個算法問題，Kempe等人[2]證明了該問題是一個NP-hard問題，并提出了貪心算法，該算法具有高精度的近似結(jié)果，但也有著高昂的時間代價，難以拓展到大規(guī)模網(wǎng)絡(luò)問題的應(yīng)用。為了克服傳統(tǒng)的貪心算法的低效性，研究者們對傳統(tǒng)的貪心算法進行了一系列的改進，或者提出了新的啟發(fā)式算法。劉等人[10]基于局部節(jié)點優(yōu)化和折扣度構(gòu)造了節(jié)點近似影響值函數(shù)來計算局部節(jié)點的影響值。曹等人[11]提出了基于核數(shù)層次特征和影響半徑的啟發(fā)式算法。聶等人[12]將信息熵引入復(fù)雜網(wǎng)絡(luò)以計算節(jié)點的影響力，使用信息熵度量不同鄰居對節(jié)點的影響。然而這些方法均為同質(zhì)信息網(wǎng)絡(luò)的研究方法，未考慮到不同類型對象之間的連接關(guān)系。

隨著社交媒體的快速發(fā)展，異質(zhì)信息網(wǎng)絡(luò)已被提議作為真實世界圖或網(wǎng)絡(luò)的一般表示。目前關(guān)于異質(zhì)信息網(wǎng)絡(luò)的研究主要集中在聚類、分類、相似性搜索鏈路預(yù)測等，而關(guān)于異質(zhì)信息網(wǎng)絡(luò)的影響力最大化研究相對較少。李等人[13]通過限制相同類型節(jié)點間的最短路徑從異質(zhì)信息網(wǎng)絡(luò)中抽取一個同質(zhì)子圖，并根據(jù)節(jié)點對在異質(zhì)信息網(wǎng)絡(luò)中的路徑來確定子圖中節(jié)點間的影響。楊等人[8]利用元路徑在異質(zhì)信息網(wǎng)絡(luò)中提取出多個同質(zhì)子圖進行影響力最大化研究，但使用獨立的元路徑進行對象之間關(guān)系的提取，會忽略一些對象被多條邊共享的問題，會導(dǎo)致這些信息的損失。

3 相關(guān)概念

本節(jié)主要介紹異質(zhì)信息網(wǎng)絡(luò)和信息熵中的基本概念，這些概念是本文工作的基礎(chǔ)。

定義1 異質(zhì)信息網(wǎng)絡(luò)[7]：異質(zhì)信息網(wǎng)絡(luò)是具有一個對象類型函數(shù)α和一個關(guān)系類型函數(shù)β的有向圖G=(V，E，T，R)。其中V是節(jié)點集，E是邊集，T是節(jié)點類型集合，|T|>1，R是關(guān)系類型集合，|R|>1，α：V→T是節(jié)點和節(jié)點類型的映射，β：E→R是邊和關(guān)系類型的映射。如圖1描述了異質(zhì)信息網(wǎng)網(wǎng)絡(luò)DBLP的一個網(wǎng)絡(luò)實例，它描述了不同類型實體之間的關(guān)系，如Bob和Ada曾合作發(fā)表了論文P2。

定義2 異質(zhì)信息網(wǎng)絡(luò)模式[14]：異質(zhì)信息網(wǎng)絡(luò)模式記為TG=(T，R)，是帶有對象映射函數(shù)α：V→T和關(guān)系映射函數(shù)β：E→R的異質(zhì)信息網(wǎng)絡(luò)G=(V，E，T，R)的元模板。

定義4 元結(jié)構(gòu)[16]：元結(jié)構(gòu)可以看作由多條具有公共節(jié)點組成的有向無環(huán)圖，形式化地，元結(jié)構(gòu)可以記為M=(VM，EM)，其中VM是節(jié)點集合，EM是邊集合。

定義5 信息熵[4]：信息熵是一個系統(tǒng)的信息含量的量化指標，常用來作為系統(tǒng)方程優(yōu)化的目標或參數(shù)選擇的判據(jù)。喬等人[4]將信息熵引入復(fù)雜網(wǎng)絡(luò)以計算節(jié)點的影響力。對于網(wǎng)絡(luò)中的任意節(jié)點v的信息熵可以由式(1)計算

(1)

4 基于元結(jié)構(gòu)的影響力最大化建模

在這一部分，本文提出了一個基于元結(jié)構(gòu)的影響力最大化算法模型(MSIM)，采用的數(shù)學(xué)符號及含義見表1。

表1 符號說明

4.1 問題定義

本文選擇以異質(zhì)信息網(wǎng)絡(luò)中的信息傳播為例，研究異質(zhì)信息網(wǎng)絡(luò)的影響力最大化問題。給定一個異質(zhì)信息網(wǎng)絡(luò)G=(V，E，T，R)，本文的目的是在考慮在度量節(jié)點的影響力時利用異質(zhì)信息網(wǎng)絡(luò)中豐富的語義信息，考慮不同類型節(jié)點之間的影響，在特定的擴散模型下，選擇出具有最大影響范圍的相同節(jié)點類型的子集。

4.2 構(gòu)造元結(jié)構(gòu)

為了度量節(jié)點的影響力，本文為每一個目標類型節(jié)點u∈V構(gòu)造一個元結(jié)構(gòu)MSu，并且將u作為元結(jié)構(gòu)中的源節(jié)點，根據(jù)網(wǎng)絡(luò)模式不同類型節(jié)點之間的關(guān)系，查找出節(jié)點u的出鄰居加入MSu，然后根據(jù)網(wǎng)絡(luò)模式中u的出鄰居所屬的節(jié)點類型與其它節(jié)點類型節(jié)點的關(guān)系，將出鄰居的出鄰居添加至MSu，直至遍歷網(wǎng)絡(luò)模式中u與所有類型節(jié)點之間的關(guān)系。在構(gòu)造元結(jié)構(gòu)的過程中保留節(jié)點本身的度的信息。如圖2描述了圖1中作者Ying的元結(jié)構(gòu)的構(gòu)造過程。本文通過網(wǎng)絡(luò)模式提取出目標節(jié)點的元結(jié)構(gòu)能夠有效的保留局部結(jié)構(gòu)信息和節(jié)點間的異質(zhì)信息，而本文對節(jié)點影響力的度量也將以節(jié)點的元結(jié)構(gòu)為基礎(chǔ)。

圖2 元結(jié)構(gòu)構(gòu)造示例

4.3 路徑熵與結(jié)構(gòu)熵

元路徑可以提取源節(jié)點與目標節(jié)點的關(guān)系，對于以v1為源節(jié)點的元路徑W，路徑w(v1v2…vn)是W的一條路徑實例，本文由式(2)計算元路徑W對源節(jié)點v1的路徑熵。

(2)

社交網(wǎng)絡(luò)中的三度影響力理論指出信息在網(wǎng)絡(luò)傳播過程中存在衰減，并發(fā)現(xiàn)三度之內(nèi)的節(jié)點屬強連接關(guān)系，而距離三度之外的節(jié)點間為弱連接關(guān)系，信息在弱連接中基本不產(chǎn)生影響。因此，本文對多介質(zhì)元路徑進行“折半”處理，只計算其前驅(qū)的路徑熵，如對于元路徑APTPA，只計算元路徑APT對源節(jié)點所提供的路徑熵。在本文構(gòu)造的所求影響力最大化的目標類型節(jié)點的元結(jié)構(gòu)中能夠有效的存儲多介質(zhì)元路徑的前驅(qū)信息，以及目標節(jié)點與其它類型節(jié)點間的聯(lián)系。對于節(jié)點v1的元結(jié)構(gòu)MSv1，綜合由不同元路徑W的路徑熵得出v1的結(jié)構(gòu)熵，由式(3)計算節(jié)點的結(jié)構(gòu)熵。

(3)

其中λi為元路徑Wi的影響因子。

4.4 MSIM算法描述

本文提出了在異質(zhì)信息網(wǎng)絡(luò)中基于元結(jié)構(gòu)的影響力最大化算法(MSIM)。MSIM算法構(gòu)造節(jié)點的元結(jié)構(gòu)，并定義節(jié)點的結(jié)構(gòu)熵度量源節(jié)點的影響力，也考慮了不同類型的元路徑對節(jié)點影響力的影響。元結(jié)構(gòu)的構(gòu)建有利于根據(jù)不同的擴散任務(wù)，有針對性的選擇種子節(jié)點。如在DBLP網(wǎng)絡(luò)中選擇作者節(jié)點作為影響力最大化的研究目標，那么MSIM通過構(gòu)造作者節(jié)點的元結(jié)構(gòu)來度量作者的影響力。通過元結(jié)構(gòu)中不同的元路徑的結(jié)合來度量節(jié)點的影響，既考慮到了節(jié)點的局部影響也考慮到了節(jié)點的全局影響。MSIM算法偽代碼如下所示。

MSIM算法偽代碼

1)輸入：G(V，E，T，R)，種子集節(jié)點數(shù)量k

2) 輸出：種子集合S

3)初始化S=φ

4)Foreachu∈V，

5)構(gòu)造元結(jié)構(gòu)MSu

6)由式(2)(3)計算節(jié)點的結(jié)構(gòu)熵MEu

7)Endfor

8)Fori=1tokdo：

9)s=max(MEu)

10)S=S∪{s}

11)Endfor

12)ReturnS

5 仿真驗證

5.1 數(shù)據(jù)集準備

本文在真實的異質(zhì)信息網(wǎng)絡(luò)數(shù)據(jù)集DBLP數(shù)據(jù)集和YELP數(shù)據(jù)集驗證MSIM算法的性能。數(shù)據(jù)集的詳細描述如表2所示。為了驗證所提出的MSIM算法的有效性，本文采用同質(zhì)信息網(wǎng)絡(luò)中基于信息熵的影響力最大化算法ME算法[12]，以及異質(zhì)信息網(wǎng)絡(luò)中基于同質(zhì)子圖的Entropy算法[13]和MPIE算法[8]作為對比算法。

表2 數(shù)據(jù)集詳細信息

5.2 有效性驗證

為了驗證MSIM算法的性能，本文在DBLP和YELP數(shù)據(jù)集上進行實驗。對于同質(zhì)信息網(wǎng)絡(luò)中的ME算法，實驗中不區(qū)分節(jié)點類型與邊類型。分別選取k個DBLP網(wǎng)絡(luò)中的作者節(jié)點和YELP網(wǎng)絡(luò)中的用戶節(jié)點作為種子節(jié)點，k分別選取10，20，30，40，50個節(jié)點。通過LT模型進行擴散模擬，采用影響范圍(InfluenceSpread)作為評價指標，影響范圍定義為成功激活節(jié)點的數(shù)量。圖3展示了不同算法對不同k個影響節(jié)點的影響擴散范圍，其中橫坐標表示種子集合大小，縱坐標表示最終激活節(jié)點數(shù)量。

從圖3中可以看出，不同算法在不同的數(shù)據(jù)集上表現(xiàn)出不同的性能，并隨著k值的增加，最終激活節(jié)點的數(shù)量也會增加。在這些算法中，所提出的MSIM算法優(yōu)于同質(zhì)信息網(wǎng)絡(luò)的ME算法，表明考慮節(jié)點的異質(zhì)信息可以提高擴散影響范圍。MPIE算法、Entropy算法在不同的數(shù)據(jù)集表現(xiàn)出不同性能，其中MPIE算法在DBLP數(shù)據(jù)集中的表現(xiàn)較差，而在YELP數(shù)據(jù)集中性能有所提升，這說明在異質(zhì)信息網(wǎng)絡(luò)中提取同質(zhì)子圖進行影響力最大化研究依賴數(shù)據(jù)集的結(jié)構(gòu)特征。而本文依據(jù)異質(zhì)信息網(wǎng)絡(luò)的網(wǎng)絡(luò)模式為節(jié)點構(gòu)造的元結(jié)構(gòu)，并且基于元結(jié)構(gòu)提出的MSIM算法在兩個數(shù)據(jù)集上都有較好的表現(xiàn)。因此，本文所提出的元結(jié)構(gòu)是有意義的，它能夠較好的保留節(jié)點的結(jié)構(gòu)信息和不同類型節(jié)點間的異質(zhì)關(guān)系，有利于影響的擴散，使傳播更加廣泛。

圖3 不同算法的擴散結(jié)果

5.3 效率對比

本文在DBLP數(shù)據(jù)集中對比了不同算法之間的時間效率，將種子節(jié)點的數(shù)量k大小分別設(shè)為10，20，30，40，50，對比不同算法選擇出k個種子節(jié)點的運行時間，在表3中展示了在DBLP和YELP數(shù)據(jù)集上的運行結(jié)果。從表3中可以看出所有算法的運行時間隨著k值的增大而增加，但增加幅度較小。ME算法不需要考慮數(shù)據(jù)集中節(jié)點和邊的異質(zhì)性，有著較低的時間復(fù)雜度。Entropy算法的運行時間主要消耗在構(gòu)建同質(zhì)子圖以及確定子圖中節(jié)點的傳播影響概率。MPIE算法需要根據(jù)不同的元路徑構(gòu)建多個同質(zhì)子圖，且根據(jù)不同元路徑構(gòu)造子圖的運行時間不同，總體時間復(fù)雜度過高，未加入對比。MSIM算法的運行時間主要花銷在構(gòu)建節(jié)點的元結(jié)構(gòu)，較于構(gòu)造同質(zhì)子圖，有較低的時間復(fù)雜度。綜合來看MSIM算法在時間效率和性能上有著較好的折中。

表3 運行時間

圖4 參數(shù)分析

5.4 參數(shù)影響分析

本文設(shè)置元結(jié)構(gòu)中不同的元路徑的影響因子的和為1，在DBLP數(shù)據(jù)集和YELP數(shù)據(jù)集中選取了18組參數(shù)，選出k=50個種子節(jié)點并比較它們的影響范圍，實驗結(jié)果如圖4所示，其中DBLP橫坐標表示元路徑APA，APCPA，APTPA的影響因子，YELP橫坐標表示元路徑UU，UBU，UBCatBU，UBCitBU的影響因子。從圖4中可以看出不同的影響因子比值會有不同的擴散結(jié)果。在DBLP網(wǎng)絡(luò)中當(dāng)影響范圍達到最大值時，元路徑APA的影響因子是三種元路徑中的最大值，這表明具有公共論文作品的作者的關(guān)系在擴散過程中起著關(guān)鍵作用，在進行有效性驗證實驗采用AP，APCPA，APTPA的影響因子為0.7，0.2，0.1。在YELP網(wǎng)絡(luò)中當(dāng)影響范圍達到最大值時，元路徑UU具有最大的影響因子，這表明用戶之間的交互在擴散過程中起著關(guān)鍵作用，在進行有效性驗證實驗時采用UU，UBU，UBCaBU，UBCiBU的影響因子為0.5，0.4，0.09，0.01。

6 總結(jié)與展望

本文研究了異質(zhì)信息網(wǎng)絡(luò)中的影響力最大化問題，旨在利用異質(zhì)信息網(wǎng)絡(luò)中豐富的語義信息度量節(jié)點的影響。在此基礎(chǔ)上，提出了一種基于元結(jié)構(gòu)的信息熵模型來度量異質(zhì)信息網(wǎng)絡(luò)中節(jié)點的影響力，即MSIM。該算法通過為節(jié)點構(gòu)造元結(jié)構(gòu)來捕獲異質(zhì)信息網(wǎng)絡(luò)中的豐富的語義信息，并通過路徑熵與結(jié)構(gòu)熵度量節(jié)點的影響。然后在真實世界數(shù)據(jù)集上進行實驗，證明了所提方法的有效性。但在本文中，只考慮了相同類型對像的影響力最大化，因此在未來研究中，可以考慮包含有不同類型對象的節(jié)點集的影響力最大化，這有助于在實際系統(tǒng)中提供更準確影響度量。