張云飛，李 勁，岳 昆，羅之皓，劉惟一

1.云南大學 信息學院，昆明 650091

2.云南大學 軟件學院，昆明 650091

3.云南省軟件工程重點實驗室，昆明 650091

1 引言

針對目前萬維網環(huán)境下社會網絡信息傳播研究中存在的問題，有三個層面上的問題需要進行研究[1]：（1）信息與行為交叉層面，主要關注多模態(tài)信息主題的用戶偏好模型；（2）網絡與行為交叉層面，主要研究基于用戶親密度度量的網絡模型構建；（3）信息、行為及網絡交叉層面，主要揭示主題和網絡環(huán)境約束下影響力傳播機制，并最終建立有效、安全的社會網絡信息的全局傳播機制。其中，影響力傳播模型是揭示影響傳播機制的微觀基礎，而有效、安全的信息傳播機制是研究的最終目標和核心內容。

近年來，許多學者針對面向多信息源發(fā)布的信息全局傳播機制及其預測模型，以影響力傳播范圍及傳播速度最大化為目標的關鍵結點集選取等問題開展了積極探索，并取得了一系列成果，極大地促進了社會網絡影響力傳播機制問題的研究[2-5]。然而，社會網絡中傳播的各種影響力之間不是完全獨立的：既有影響力傳播之間的對抗，也會有一種影響力的傳播促進另一種影響力傳播的情況。為有效地分析社會網絡中多種影響力傳播機制，以多種影響力下的社會網絡影響力傳播模型，及多影響力傳播模型下的傳播優(yōu)化[6-14]等問題引起了關注，取得了一些初步的研究成果。

例如，文獻[6]擴展經典的線性閾值模型（linear threshold model，LT），給出了用于描述社會網絡中正、負影響競爭傳播現象的競爭線性閾值模型，提出影響力傳播的新問題：影響傳播抑制最大化問題（influence blocking maximization），證明了IBM的目標函數滿足子模性（submodularity），給出了解決IBM問題的高效近似算法。文獻[7]基于影響力傳播的獨立級聯模型（independent cascade model）建立了多競爭級聯模型（multiple competitive independent cascade model，MCICM），提出影響傳播抑制問題（eventual influence limitation，EIL），給出MCICM模型下，EIL問題目標函數滿足子模性的充分條件，以及EIL問題的近似求解算法。由于影響力傳播與抑制行為的本質是傳播方與抑制方之間的一種博弈關系，文獻[8-9]以傳播方和抑制方的種子集作為策略空間，將傳播與抑制決策建模為零和博弈，并提出了博弈Nash均衡的近似求解算法。最近，文獻[10]針對社會網絡中影響力傳播抑制問題，擴展了經典的線性閾值模型，提出了一種新型的影響力傳播、抑制模型，并給出了此模型上的影響傳播的最優(yōu)抑制方法。文獻[11]假設競爭網絡中r個分組獨立選擇種子，每個分組可以感知對手但不能感知對手策略，當結點受到一些分組影響時就不再受其他分組影響。討論了在更符合實際的假設下，競爭影響傳播最大化問題。

值得注意的是以上研究主要針對兩種處于競爭狀態(tài)下的影響力的對抗傳播。對于網絡中多種影響力傳播時，存在相互促進的情況，以及此情況下的傳播優(yōu)化問題，研究較少。Narayanam等人[12]研究了通過社交網絡推廣兩組商品，其中一組商品對另一組商品的傳播有促進作用時，如何選擇兩組商品的種子，使傳播總收益最大。Lu等人[13]通過擴展經典的獨立級聯模型，提出了Com-IC模型，并討論了Com-IC下影響力之間促進和競爭傳播的情況。Zarezade等人[14]研究了網絡中不同的級聯傳播行為之間合作或競爭關系，并提出了一種采用Hawkes process隨機過程對關聯級聯過程進行建模、分析的方法。

與上述研究工作不同，本文研究：已知網絡中影響力B的傳播種子集，且影響力A和B之間存在傳播促進關系，對于影響力A，如何有效地選擇傳播種子集，使得影響力A的傳播范圍最大化?；诖耍疚奶岢鲫P聯影響力傳播最大化問題（correlational influence maximization，CIM）。首先，對經典線性閾值模型進行擴展，提出關聯影響力線性閾值模型（correlational linear threshold model，CLT），用CLT模型對網絡中關聯影響力傳播過程進行建模。其次，證明了CIM問題是NP-hard的，并進一步證明了該問題的目標函數滿足子模性?；诖?，提出了針對關聯影響力最大化的種子集挖掘算法。此外，為有效提高算法的執(zhí)行效率，提出了基于結點激活貢獻估計的最大化算法。由于結點激活貢獻估計是相互獨立的，進一步地，提出了并行化的基于結點激活貢獻估計的最大化算法。最后，采用Spark GraphX并行圖計算平臺實現了相關算法，在真實的社會網絡數據集上通過實驗驗證了所提出的方法的可行性和有效性。

2 關聯影響力線性閾值模型

一般地，社會網絡中同時存在多種影響進行傳播，這些影響之間可能不是相互獨立，有些影響力之間在傳播行為上存在相互促進的關系。為描述相互間具有傳播促進作用的影響力在社會網絡中的傳播情況，本文對社會網絡影響力傳播的經典模型線性閾值模型[2]進行了擴展，提出了一種新型的影響力傳播模型，即關聯影響力線性閾值模型。

設帶權有向圖G=(V,E)是一個社會網絡，其中V為結點集，表示網絡中的個體，E為有向邊集，表示個體間的影響關系，每條邊e(u,v)有相應權重wu,v>0，表示u對v影響程度。為描述方便，設A和B為兩種不同的影響力，其中B為A的關聯影響，且對A有促進作用，作為對LT的擴展。設每條邊有3個權值：表示網中只有A在傳播時，u對v影響力度；表示網中B傳播時，u對v影響力度；表示當v被B激活時u對v影響力度。當時，說明如果結點v被B激活后，u對v的A激活影響程度增強，那么說影響力B對影響力A有傳播促進作用。

一般地，結點v獨立地從[0,1]中等概率選取激活閾值。與經典的LT模型類似，在時刻t，記INA(v)、INB(v)分別為v處于A、B激活態(tài)的入鄰居結點集。當，且時，v被A激活；如果v已被B激活，INA(v)≠? 且時，v被A激活。顯然，當成立時，網絡中結點被A激活的概率提高。因此，網絡中同時有A、B在傳播時，A影響范圍的期望值將增大。

可以發(fā)現邊e(u,v)的屬性wu,v是反映u、v間影響程度重要的量。下面給出wu,v的一種衡量方法。先從網絡結構角度給出相鄰結點間緊密度的衡量方法。

設網絡G=(V,E)中，。那么，用衡量u對v的緊密度。注意到，。其中 |N(v)?N(u)|表示結點u與v共同鄰居的數量，加1表示u與v是一對鄰居，同時也保證了λu,v的合理性。

相鄰結點間傳遞信息時，其影響程度除了與結點間的緊密度有關外，還與信息本身是否容易被接受有關。下面從商品信息的角度，給出商品信息接受率的衡量方法。

假定A商品的交易數為mA，B商品的交易數為mB，同時購買A和B的交易數mAB，商品的總交易數為n。記A商品信息的接受率pA|?=mAn，B商品信息的接受率pB=mBn，接受B后A的接受率pA|B=mABmB。商品信息的接受率體現商品信息的平均接受程度。

根據結點間的緊密度及商品接受率的概念，給出wu,v的一種計算方法。設u∈IN(v)，當v未被B激活時，；當u被B激活時，pA|B。如果pA|B>pA|?，在有B傳播的情況下，就可能增大結點被A激活的概率，擴大A的傳播范圍。

下面通過一個例子來說明CLT模型在某確定圖上關聯影響力的傳播過程，如圖1、圖2所示。

Fig.1 Example of influence diffusion under LT model圖1 LT模型影響力傳播示例

Fig.2 Example of influence diffusion under CLT model圖2 CLT模型影響力傳播示例

如圖1所示，設v1是A影響種子結點。A影響按照LT模型進行傳播，t=3時，圖中被A激活的結點為{v1,v3,v4}。圖2中，t=0時，v1被A激活，{v2,v3,v4,v5}最終被B激活。假定對于任意結點，均有影響力按照CLT模型進行傳播。在t=3時，與圖1所示結果不同，網絡中所有結點均A激活，即B影響力對A影響力的傳播起到了促進作用。

于是，基于CLT模型，本文提出一個新的社會網絡影響力傳播優(yōu)化問題，即：CLT下的關聯影響力傳播最大化問題。具體地，令G=(V,E)是一個帶權有向圖，表示社會網絡。分別表示CLT模型中結點集V上的A、B兩種影響閾值隨機向量。當θA與θB取某具體值時，得到確定圖g，所有確定圖組成隨機網絡集G，g∈G。設A、B影響力的種子集分別記為SA、SB，兩種影響力按照CLT模型在G中進行傳播。最終，被A激活的結點集記為：。由于θA和θB是隨機向量，因此是一個隨機變量。用該隨機變量的期望值作為A影響力的傳播效用，記為：

于是，關聯影響力傳播最大化問題可定義為：

定義1（最大化問題的定義）設A、B影響力按照CLT進行影響力傳播。給定B影響種子集SB的情況下，求解A影響傳播效用最大化的種子集SA，使得：

定理1（最大化問題的復雜性）關聯影響力傳播最大化問題是NP-hard的。

證明在CLT模型中，當SB=? 時，CLT模型退化為經典的LT模型。因此，LT是CLT的一個特例。Kempe等人[2]證明了LT模型的影響力最大化問題是NP-hard問題，因此，式（1）描述的CLT的影響力最大化問題也是NP-hard的。

定理2（效用函數的性質）在CLT中，給定SB的條件下，A影響傳播效用函數inf(SA,SB)是關于SA的非負、單調、子模函數。

下面證明在CLT中，給定SB的情況下，A影響力傳播效用函數inf(SA,SB)是子模函數。

證明由CLT中影響力傳播過程可知，在確定圖g中，由種子集SB可以確定B的傳播范圍。任意結點v是否處于B激活態(tài)將影響其入邊傳播的A影響權重，進而影響v被A激活的可能性。因此，可先給定SB，獨立進行B影響力傳播，然后再進行A影響力傳播。任意結點v及其入邊A激活結點u∈INA(v)，將u對v的影響權重記為wu,v。那么，如果當前v未被B激活，則u對v的傳播影響權重設為。如果當前v已被B激活，同時，則u對v的影響權重設為。此時，從SA出發(fā)，A影響力將按照LT模型進行傳播，最終得到A的傳播范圍。在所有的網絡集G中得到inf(SA,SB)。由于Kempe等人證明了LT下影響力傳播效用函數是子模的[2]，因此在CLT下，關聯影響力傳播效用函數inf(SA,SB)也是關于SA的子模函數。

3 關聯影響力最大化算法

本章給出求解關聯影響力最大化問題的算法。由于B的傳播也是隨機事件，首先給出能保證種子傳播效果的基于貪心策略的最大化算法。其次，為提高算法效率提出了基于結點激活貢獻估計的最大化算法。鑒于不同結點的激活貢獻值相互獨立，進一步提出基于圖計算框架Spark GraphX[15]的并行最大化算法。

3.1 基于貪心策略的關聯影響力傳播最大化算法

由定義1及定理2可知，求解SA可歸結為一個子模函數優(yōu)化問題。于是，給定種子集SB的情況下，以inf(SA,SB)作為子模目標函數，以結點對于當前解的期望邊際傳播收益作為貪心選擇標準，由子模函數優(yōu)化理論[16]可知，用貪心法可得(1-1e)-近似解。由于CLT是一個隨機模型，因此算法先隨機生成激活閾值向量θA、θB，每一對閾值向量確定一個網絡g。結點的期望邊際傳播收益由結點對于當前解在隨機網絡集G上的期望值來決定。給定g，算法以SB作為種子集按照LT模型進行B影響力傳播，確定g中被B激活的結點。如果，則將置為v的入邊A影響權重，并根據LT模型對g上每個結點的A影響傳播效用進行估計，進而確定邊際傳播收益值。最終，算法根據結點當前解的期望邊際傳播收益選擇值最大的新結點加入到SA。

算法1Greedy(G,SB,k)

輸入：網絡G(V,E),B影響種子集SB,A影響種子集大小k。

輸出：A影響種子集SA。

3.2 基于結點激活貢獻估計的關聯影響力傳播最大化算法

為提高算法效率，本文提出一種基于結點激活貢獻估計的影響最大化算法。其中結點激活貢獻值估計是該算法計算密集環(huán)節(jié)。由于不同結點的激活貢獻估計是相互獨立的，可進行并行計算，進一步提出基于圖計算框架Spark GraphX[15]的并行最大化算法。

3.2.1 結點激活貢獻的估計方法

先定義結點的入邊對結點激活的貢獻值。

定義2（邊的激活貢獻）設v是確定圖g中的任意處于未激活態(tài)的結點。IN(v)是v的處于激活態(tài)的入鄰居結點集。設u是v的任意處于未激活態(tài)的入結點。則結點u通過邊e(u,v)對v的激活貢獻值記為AC(u,v)∈[0,1]，并定義如下：

注意到，定義2中v是未激活結點，定義中總有，否則v應處于激活態(tài)。此外，如果u被激活后，可由入邊e(u,v)直接激活v，由式（2）可知，此時AC(u,v)=1。

進一步地，可以基于邊的激活貢獻來定義結點的激活貢獻。具體地，對于結點u∈V，可由該結點所有出邊的激活貢獻值之和來定義u的激活貢獻值。同時，考慮任意結點u對其l-步鄰居的激活影響，可定義結點的l-步激活貢獻，記為ACl(u)，定義如下：

定義3（結點的激活貢獻）令OUT(v)是結點v的出邊鄰居集。記v的l-步激活貢獻值為ACl(v)(l≥2)，計算公式如下：

其中，當l=1時，結點v對其1-步鄰居的潛在貢獻值為：。直觀地，AC1(v)反映了結點v從未激活轉換為激活狀態(tài)時，對其1-步鄰居結點的影響。

下面，舉例說明CLT模型中，結點激活貢獻值的估計方法。

圖3中已處于A激活態(tài)的結點為{v1,v2}，已處于B激活態(tài)的結點為{v5,v6}。任意有向邊e(u,v)的權重表示結點間的A影響權重。此外，設，。針對未激活結點v3，計算其激活貢獻值以及。

Fig.3 Example of estimation of activation contributions of vertices under CLT model圖3 CLT中結點激活貢獻值估計示例

首先，由定義2可知，有向邊e(3,4)對v4的激活貢獻為，得AC(3,4)=1，說明v4一定會被激活。類似地，得到AC(3,5)=。進一步，由定義3得到AC1(v3)=1.25。同理，得AC(4 ,5)=0.625，AC1(v4)=0.625，AC1(v5)=0。因此，由定義3得到。

3.2.2 基于結點激活貢獻估計的影響最大化算法

基于結點激活貢獻估計的影響最大化算法（activation contribution based algorithm，ACA）的基本流程與算法1類似，時間復雜度為，其中D為以結點為中心l步的平均邊數，顯然D?R。ACA與Greedy最大的區(qū)別在于，在ACA中，用結點的激活貢獻估計值ACl(v)取代了算法1中結點的邊際效用估計。因此與Greedy相比，ACA的算法效率得到了很大提高。

此外，需要說明的是，當結點激活貢獻估計的步長l=1時，ACA算法其實是陳等人提出的基于閾值的啟發(fā)式影響力最大化算法（threshold-based heuristic algorithm for influence maximization，TBH）[5]針對CLT模型的擴展。由文獻[5]結論可知，TBH算法證明選出種子集在傳播效果上接近Kempe[2]的貪心算法。

算法2ACA(G,SB,k,l)

輸入：網絡G(V,E),B影響種子集SB，A影響種子集大小k，激活貢獻值步長l。

輸出：A影響種子集SA。

Fig.4 Example ofACAalgorithm execution圖4 ACA算法執(zhí)行示例

下面給出一個ACA算法執(zhí)行的示例。如圖4，開始時v1、v2均未被A激活，此時選取種子。根據定義3可得AC2(v1)=0.347，AC2(v2)=1.251，AC2(v3)=0.458，AC2(v4)=0.278，AC2(v5)=0，AC2(v6)=0.111。因此，選取激活貢獻值最大的結點v2作為種子。接下來，v2變?yōu)锳激活結點，v5、v6為B激活結點。由于v2對v4、v5的影響，當v2被A激活后，其指向v4、v5的有向邊的激活貢獻發(fā)生改變。于是重新計算這些邊和未激活結點的激活貢獻，可得：AC2(v1)=0.875，AC2(v3)=0.934，AC2(v4)2=0.192，AC2(v5)=0，AC2(v6)=0.077。此時，選擇最大激活貢獻值的v3作為種子。由此，得到的兩個種子為{v2,v3}。

在ACA算法中，結點激活貢獻估計是整個算法的計算密集環(huán)節(jié)。注意到各個結點的激活貢獻的估計實際上是相互獨立的，允許進行并行計算。因此，進一步提出了基于并行圖計算框架Spark GraphX[15]的并行化ACA算法（parallel activation contribution based algorithm，PACA）。

PACA采用并行消息機制實現邊和結點激活貢獻值的計算，極大地提高了算法的執(zhí)行效率。在計算結點多步激活貢獻值時，可通過在圖上采用多次迭代實現。具體地，設u的出鄰居為v，首先計算u和v的1-步激活貢獻，通過GraphX中結點間的消息傳遞機制，將v的1-步激活貢獻發(fā)送給u。此時，u可以計算其2-步激活貢獻。算法3為PACA算法的描述。

算法3PACA(G,SB,k,n)

輸入：G(V,E)，圖G;SB，B信息種子集；k，待求A信息種子數；n，考慮n步鄰居。

輸出：SA，A信息種子集。

4 實驗結果

4.1 實驗環(huán)境設置

在3個真實的網絡數據集[17]HepTh、Web-Stan和Pokec上對本文提出的模型和算法進行測試和驗證。表1給出了實驗數據集的具體信息。HepTh是電子出版物arXiv出版的高能物理領域論文間的引用關系網；Web-Stan是斯坦福大學網頁間的鏈接關系數據；Pokec是Pokec社交網絡數據。Market是超市購物數據集[18]，實驗中傳播的超市Peanuts商品信息設為A，Beer為其關聯商品信息設為B。根據第2章方法得到pA|?=0.186 38，pA|B=0.570 96。針對以上數據集，在Spark平臺上，采用Scala語言實現相關算法。程序執(zhí)行環(huán)境為：浪潮服務器，共有40個Cores，每個Core的主頻為2.2 GHz，服務器的內存為750 GB。

Table 1 Statistics of experimental data sets表1 實驗數據集的統(tǒng)計信息

4.2 關聯影響傳播的有效性

首先對關聯影響傳播模型的有效性進行驗證，即比較不給定B影響源、給定B影響源兩種不同情況下，A影響力傳播的范圍。實驗方案是：在3個網絡中，按結點度數排序，選取最大度的前10個結點作為B影響種子集。首先，不預先給定B影響源信息，用貪心算法[2]分別選取大小分別為4、8、12、16、20的A影響種子集，影響力按照經典的LT模型傳播。其次給定B影響源信息，按照本文提出的的算法1選取大小分別為4、8、12、16、20的A影響種子集，影響力按照本文CLT模型傳播。其中|G |的個數取2 000。最終，在不考慮關聯影響與考慮關聯影響兩種情況下選出種子A影響力傳播范圍的實驗結果如圖5～圖7所示。

由實驗結果可知，相比較LT模型下A影響力的傳播結果，考慮B影響源，選取同樣大小的種子集在CLT模型下被A激活的結點更多。這說明借助關聯影響源B，可使得A影響力得到更好的傳播。這一事實在HepTh和Pokec實驗結果得以充分體現。在Web-Stan網絡數據中，選取12個以上種子時，借助關聯影響源選擇種子，顯然傳播能力更強。

4.3 PACA算法

Fig.6 Range of information propagation under LT and CLT(Web)圖6 LT與CLT傳播范圍對比（Web）

Fig.7 Range of information propagation under LT and CLT(Pokec)圖7 LT與CLT傳播范圍對比（Pokec）

本節(jié)從種子集選取效果、鄰居選擇策略以及并行加速比三方面對本文提出的PACA算法進行驗證。

4.3.1 不同算法的傳播效果

在3個網絡數據集HepTh、Web-Stan和Pokec上，對PACA-1、PACA-2、PACA-3、MaxDegree、Random 5種算法的種子集選取效果進行了比較。其中，PACA-l為采用l步長進行結點激活貢獻估計的PACA算法。由于PACA-1可看作文獻[5]提出的TBH算法針對CLT模型擴展的并行實現，由文獻[5]結果可知，TBH算法與Greedy算法選出的種子集具有相當的傳播效果，且TBH算法效率很高。因此，在對比實驗中省去了同Greedy算法的對比。

實驗選擇度最大的10個結點作為B種子集，關注A種子集的選取。每種算法選擇4、8、12、16、20個A的種子，在G中，以最終被A激活結點數的平均值作為傳播效果的指標，分析算法種子集選取的優(yōu)劣。實驗結果如圖8～圖10所示。

Fig.8 Propagation ability of seed sets selected by different algorithms(HepTh)圖8 不同算法的傳播范圍對比（HepTh）

Fig.9 Propagation ability of seed sets selected by different algorithms(Web)圖9 不同算法的傳播范圍對比（Web）

Fig.10 Propagation ability of seed sets selected by different algorithms(Pokec)圖10 不同算法的傳播范圍對比（Pokec）

由實驗結果可知，PACA系列算法選取種子傳播效果較好，明顯優(yōu)于MaxDegree與Random算法。利用PACA-2選取種子在大多數時候得到的種子集要優(yōu)于PACA-1，甚至會優(yōu)于PACA-3。而PACA-3考慮了網絡中的更多信息，但選出種子集的傳播效果卻不穩(wěn)定。如在Pokec中選取16與20個種子時，其選出種子的效果甚至低于PACA-1。導致這一結果的原因是進行激活貢獻估計的步長越長，結點間的關系越復雜，反而使估算效果時好時壞。

4.3.2 PACA算法的執(zhí)行效率

實驗目的主要是對比串行的ACA和并行的PACA兩種算法的執(zhí)行時間。對ACA與PACA選取4、8、12、16、20個A的種子，對比選出種子耗費的時間。兩種算法在進行激活貢獻估計時，均考慮了估計步長l=1,2,3這3種情況。PACA算法采用40核并行執(zhí)行。實驗結果如圖11～圖13所示。

Fig.11 Execution time ofACAand PACAalgorithms(HepTh)圖11 ACA與PACA執(zhí)行時間比較（HepTh）

由實驗結果知，PACA算法效率明顯優(yōu)于ACA算法。網絡規(guī)模越大，采用并行算法執(zhí)行效率優(yōu)勢更加明顯。

4.3.3 并行算法的并行加速比

在并行核數分別為1、8、16、24、32、40時，利用PACA算法選出20個種子耗費的時間計算出并行的加速比與并行效率。實驗結果如圖14、圖15所示。

加速比Sp用于表示利用并行與對應的單核執(zhí)行算法比較，速度快了多少，計算公式為Sp=T1/Tp。其中，p為并行的CPU核數，T1為單核執(zhí)行算法的時間，Tp為當有p個處理器時，并行算法的執(zhí)行時間。由圖14所示可知，并行核數增加時，加速比增加，但加速比增加的速率在減小。此外，并行效率用來說明當并行核數增加時，相比通信和同步上的花費，實際參與計算的處理器的利用程度，其計算公式為Ep=Sp/p。

Fig.12 Execution time ofACAand PACAalgorithms(Web)圖12 ACA與PACA執(zhí)行時間比較（Web）

Fig.13 Execution time ofACAand PACAalgorithms(Pokec)圖13 ACA與PACA執(zhí)行時間比較（Pokec）

Fig.14 Parallel speed-up ratio of PACA圖14 PACA算法的并行加速比比較

Fig.15 Parallel efficiency of PACA圖15 PACA算法的并行效率比較

對比3個數據集的實驗結果，可以發(fā)現處理較大規(guī)模的網絡時，并行的加速效果更顯著。當并行數增加到一定程度后，并行所帶來的效率提升就將變得不明顯。

5 總結與展望

影響力傳播的建模和分析及其控制是當前社會網絡研究的重要內容。針對多個影響力同時進行傳播，且影響力間存在傳播促進的情況，提出關聯影響力傳播最大化問題，并給出了相應的種子集挖掘算法。在實際社會網絡數據集上驗證了算法，實驗結果表明本文提出方法的有效性。

在本文研究的基礎上，未來可以在以下幾個方面繼續(xù)開展研究。本文給出的關聯影響力傳播模型，主要針對一方傳播促進另一方的情況。但是現實網絡中存在關聯影響力兩者之間互相促進的傳播情況。該情況下，傳播的收益函數是非子模的，無法保證貪心算法的近似度。因此，討論該情況下傳播模型的性質，給出有效的種子選擇算法，成為亟待解決的問題。此外，PACA算法中激活貢獻估算時的步長設置并非越大越好。如何針對網絡結構設置合適的估算步長，從而有效地提升種子集搜索的質量也是需要進一步討論的問題。