高 昂，梁 英，謝小杰，王梓森，李錦濤

1.中國科學院計算技術(shù)研究所，北京 100190

2.中國科學院大學計算機科學與技術(shù)學院，北京 100049

3.移動計算與新型終端北京市重點實驗室，北京 100190

社交網(wǎng)絡(luò)作為一種新興的網(wǎng)絡(luò)傳媒，不僅大大加快了信息傳播的速度，也使信息能夠更高效和廣泛地傳播。人們將社交網(wǎng)絡(luò)廣泛應(yīng)用于推薦系統(tǒng)、病毒式營銷、廣告投放、專家發(fā)現(xiàn)等領(lǐng)域，充分享受信息傳播帶來的種種益處。然而，信息的快速傳播給用戶帶來許多便利的同時，也造成了隱私泄漏的隱患。

在現(xiàn)有的社交網(wǎng)絡(luò)中，信息發(fā)布者為保護其隱私，可以通過設(shè)置僅對指定好友可見等方式來限制能看到信息的對象。但大部分社交平臺都提供了轉(zhuǎn)發(fā)功能，允許看到信息的對象繼續(xù)轉(zhuǎn)發(fā)該信息，從而造成隱私泄漏。

一些社交平臺提供了設(shè)置不可見對象的功能，即使信息經(jīng)過多次轉(zhuǎn)發(fā)，對于指定的對象仍不可見。例如，假設(shè)A發(fā)送了一條信息，B再轉(zhuǎn)發(fā)來自A的信息，C再轉(zhuǎn)發(fā)來自B的信息，D是B或C的好友，但如果A設(shè)置了對象D不可見，那么D也沒法通過B或C的轉(zhuǎn)發(fā)來看見這條信息。然而，這樣的功能并不能完全阻止隱私泄漏的發(fā)生。例如，如果B不是直接轉(zhuǎn)發(fā)A，而是用自己的語言描述了A發(fā)送的信息中的信息后進行發(fā)送，假設(shè)D是B或者某個轉(zhuǎn)發(fā)B信息的人的好友，那么D就能夠看到這條信息，從而獲取A的隱私，在本文中將這種行為稱為轉(zhuǎn)述?？梢?，在社交網(wǎng)絡(luò)中用戶的轉(zhuǎn)發(fā)和轉(zhuǎn)述行為都有可能造成隱私泄漏，而且通過轉(zhuǎn)述行為造成的隱私泄漏很難被發(fā)現(xiàn)或阻止。

當前對社交網(wǎng)絡(luò)的研究主要集中于影響力最大化和隱私保護，然而，現(xiàn)有影響力傳播相關(guān)的研究沒有考慮用戶的隱私保護需求，隱私保護相關(guān)的研究沒有關(guān)注用戶的影響力；同時，現(xiàn)有的信息傳播模型很難有效建模社交網(wǎng)絡(luò)中隱私泄漏傳播過程。這為社交網(wǎng)絡(luò)的研究帶來了三點挑戰(zhàn)：（1）如何保障用戶的個性化隱私保護需求；（2）如何最大化用戶發(fā)布的信息的影響力；（3）如何平衡隱私保護和信息傳播的矛盾。

例如，用戶在社交網(wǎng)絡(luò)上發(fā)布信息或推薦系統(tǒng)推送信息時，如何選擇相關(guān)用戶（種子節(jié)點）推送信息，使得所發(fā)布的信息通過社交網(wǎng)絡(luò)傳播能讓更多的人看到（影響力最大化），同時不被黑名單用戶捕捉；同樣，通過病毒營銷做品牌推薦時，如何選擇社交網(wǎng)絡(luò)中感興趣的投放用戶（種子節(jié)點）推送信息，使得傳播的人數(shù)最多（影響力最大化），且避免傳播到非目標用戶群體（黑名單用戶）。

為了解決上述問題，本文首先以獨立級聯(lián)模型為基礎(chǔ)，設(shè)計了支持轉(zhuǎn)發(fā)行為、轉(zhuǎn)述行為的社交網(wǎng)絡(luò)信息傳播模型，實現(xiàn)對隱私泄漏來源的補充和修正；然后基于社交網(wǎng)絡(luò)信息傳播模型，提出了一種信息傳播網(wǎng)絡(luò)構(gòu)建方法，實現(xiàn)對轉(zhuǎn)發(fā)行為、轉(zhuǎn)述行為融合建模，有效支撐包含轉(zhuǎn)述關(guān)系的信息傳播機制；最后，基于支持轉(zhuǎn)述行為的信息傳播網(wǎng)絡(luò)，提出了一種支持隱私保護的影響力最大化方法，通過節(jié)點泄漏概率上限計算，結(jié)合隱私保護約束和啟發(fā)式影響力最大化算法來選擇種子集合，實現(xiàn)在滿足隱私保護約束的同時，最大化信息傳播的影響力。通過在爬取的新浪微博數(shù)據(jù)集上進行實驗驗證和實例分析，結(jié)果表明本文方法能夠確保在保護用戶隱私的情況下，最大化傳播影響力。

本文主要貢獻包括：

（1）提出了一種支持轉(zhuǎn)述關(guān)系的社交網(wǎng)絡(luò)信息傳播模型，針對僅有轉(zhuǎn)發(fā)方式激活新節(jié)點的社交網(wǎng)絡(luò)傳播模型，增加了模型對轉(zhuǎn)述行為的支持，能夠有效建模社交網(wǎng)絡(luò)中的轉(zhuǎn)發(fā)和轉(zhuǎn)述行為，為通過轉(zhuǎn)述行為傳播造成的隱私泄漏追蹤提供數(shù)學模型支持。

（2）提出了一種支持轉(zhuǎn)述行為的信息傳播網(wǎng)絡(luò)構(gòu)建方法，通過求解用戶關(guān)注網(wǎng)絡(luò)的轉(zhuǎn)發(fā)邊、轉(zhuǎn)述邊及無行為的三分類問題，判斷網(wǎng)絡(luò)中用戶是否參與傳播，預測消息傳播到用戶時的傳播行為概率分布，補充了傳統(tǒng)社交網(wǎng)絡(luò)信息傳播途徑遺漏問題。

（3）提出了一種支持隱私保護的社交網(wǎng)絡(luò)信息傳播影響力最大化方法LocalGreedy，通過遞增策略構(gòu)造種子集合，計算節(jié)點局部影響子圖，快速計算種子集合傳播產(chǎn)生的影響力，提出節(jié)點泄漏態(tài)概率上限計算方法，確保種子集合滿足隱私保護約束限制，減少了時間開銷，平衡了影響力和隱私保護的矛盾。

1 相關(guān)工作

當前對社交網(wǎng)絡(luò)的信息傳播和隱私保護的相關(guān)研究主要分為四部分，包括：信息傳播模型、信息傳播預測、影響力傳播和社交網(wǎng)絡(luò)訪問控制。

1.1 信息傳播模型

典型的應(yīng)用于社交網(wǎng)絡(luò)的信息傳播模型包括獨立級聯(lián)模型[1]、線性閾值模型[2]和傳染病模型[3]。左遙等[4]以獨立級聯(lián)模型為基礎(chǔ)，提出了一種用于描述社會化問答網(wǎng)站知識傳播過程的傳播網(wǎng)絡(luò)模型，并進一步給出了一種社會化問答網(wǎng)站知識傳播網(wǎng)絡(luò)推斷方法。蔡淑琴等[5]基于線性閾值模型和價值共創(chuàng)理論，提出了一種針對負面口碑特征的社會化網(wǎng)絡(luò)傳播及企業(yè)價值共創(chuàng)策略的模型，并通過仿真實驗，分析了影響負面口碑在社交網(wǎng)絡(luò)中爆發(fā)的主要影響因素。趙劍華等[6]以傳統(tǒng)的SIR（susceptible infected recovered）傳染病模型為基礎(chǔ)，綜合考慮用戶的心理特征和行為因素，提出了一種新的社交網(wǎng)絡(luò)輿情傳播動力學模型，并選用粒子群算法，以2016 年微博上發(fā)生的熱點事件為例，求解模型參數(shù)的最優(yōu)解，并進行實驗數(shù)據(jù)驗證。線性閾值模型的隨機性僅取決于節(jié)點被影響閾值的隨機性，且在閾值選擇上有較大的困難；傳染病模型僅適用于對傳播過程的宏觀描述，但未考慮具體的傳播路徑；而獨立級聯(lián)模型通過使用邊上的概率來描述信息傳播的強度或發(fā)生的可能性，具有較好的擴展性。因此，獨立級聯(lián)模型將作為本文提出的信息傳播模型的基礎(chǔ)。

1.2 信息傳播預測

信息傳播預測是指通過一定的方法學習社交網(wǎng)絡(luò)中用戶的興趣和行為規(guī)律，從而對用戶是否會參與某條信息的傳播進行預測。按照基本假設(shè)的不同，用戶信息傳播預測的研究可分為4 類：基于用戶歷史行為的預測、基于用戶文本興趣的預測、基于用戶所受群體影響的預測以及基于聯(lián)合特征學習的預測。Pan 等[7]通過捕捉用戶歷史行為中與傳播相關(guān)的特征，結(jié)合協(xié)同過濾和傳播過程的特點建立聯(lián)合推薦模型，從而預測基于轉(zhuǎn)發(fā)行為的信息傳播過程。Zhang 等[8]提出了一種結(jié)合用戶文本、網(wǎng)絡(luò)結(jié)構(gòu)和時間等信息的傳播預測方法，利用非參數(shù)統(tǒng)計模型對轉(zhuǎn)發(fā)行為進行推斷，進而預測信息傳播過程。Bian等[9]定義了興趣導向的影響、社會導向的影響和流行病導向的影響，并基于這三種影響的綜合分析來決定用戶是否執(zhí)行轉(zhuǎn)發(fā)操作。Luo 等[10]基于聯(lián)合特征學習，聯(lián)合考慮轉(zhuǎn)發(fā)歷史、用戶影響力、時間和用戶興趣等因素，在一個學習排名的框架內(nèi)，研究各因素對轉(zhuǎn)發(fā)行為的影響。信息傳播預測方法較為豐富，是社交網(wǎng)絡(luò)信息傳播分析的重要組成部分。但是，現(xiàn)有研究往往將轉(zhuǎn)發(fā)作為信息傳播的唯一方式，而忽略了其他可能的傳播行為。

1.3 影響力傳播

影響力傳播刻畫影響力在社交網(wǎng)絡(luò)中的傳播模式，即節(jié)點的狀態(tài)如何影響網(wǎng)絡(luò)中相鄰節(jié)點的狀態(tài)，并將該狀態(tài)在網(wǎng)絡(luò)上進行擴散。優(yōu)化影響力的傳播是影響力傳播建模的主要目的，而影響力最大化問題是該研究的核心內(nèi)容，目前的研究方法主要分為三類：根據(jù)傳播模型的具體特點設(shè)計啟發(fā)式算法；對蒙特卡洛貪心算法進行效率優(yōu)化；以社區(qū)發(fā)現(xiàn)作為中間步驟，將影響力問題從用戶級別轉(zhuǎn)化到社區(qū)級別。啟發(fā)式算法基于直觀或經(jīng)驗構(gòu)造，旨在有限時間、空間損耗下對影響力最大化問題給出可行解。Jung 等[11]通過綜合影響排序、影響估計方法，提高算法運行的魯棒性及穩(wěn)定性；Goyal 等[12]通過引入多個優(yōu)化策略，以在較短運行時間和較低內(nèi)存使用下保證最大化影響力種子集合質(zhì)量。由于貪心策略無法在較短時間內(nèi)迅速處理包含百萬量級的大規(guī)模網(wǎng)絡(luò)輸入，因此對蒙特卡洛貪心算法的優(yōu)化常通過降低運行時間[13]，或使用基于草圖[14]的方法解決影響力最大化問題。影響力問題向社區(qū)級別轉(zhuǎn)化的方式從解決啟發(fā)式算法無法提供性能保證的角度出發(fā)，最大化影響力。Shang 等[15]通過預先計算用戶社區(qū)影響，自頂向下選取種子集合，進而實現(xiàn)影響力最大化；Li等[16]提出了一種基于社區(qū)發(fā)現(xiàn)的種子選擇算法，實現(xiàn)了對最大化問題中種子集合的有效選擇。影響力最大化問題未考慮用戶的隱私保護需求，但相關(guān)研究中的啟發(fā)式算法相對于其他方法通常有著更快的運行時間和更好的可擴展性，因此本文使用影響力最大化的啟發(fā)式算法作為基礎(chǔ)，提出支持隱私保護的社交網(wǎng)絡(luò)信息傳播方法。

1.4 社交網(wǎng)絡(luò)訪問控制

社交網(wǎng)絡(luò)中用戶的隱私包括個人信息和交流信息，為了保證用戶的信息只被用戶信任的人訪問，需要實現(xiàn)用戶節(jié)點間的信息訪問控制進行隱私保護。Singh 等[17]設(shè)計了一種支持高可用性和實時內(nèi)容傳播的集中式社交網(wǎng)絡(luò)模型，通過學習用戶的社交行為來決定用戶的隱私。Aiello 等[18]提出了一種基于分布式散列表的在線社交網(wǎng)絡(luò)架構(gòu)LotusNet，通過一個靈活細粒度的自主訪問控制單元來控制私有資源，使得用戶可以更簡便地調(diào)整他們的隱私設(shè)置。然而在實際中，無論是集中式解決方案還是分布式解決方案都不能像預期的那樣保護普適社交網(wǎng)絡(luò)通信。為此，一類由二維信任度進行訪問控制的方案被提出[19-20]，通過利用信息節(jié)點屬性計算節(jié)點間二維信任度，并根據(jù)二維信任度實現(xiàn)對用戶隱私的訪問控制。但是，現(xiàn)有針對隱私問題的訪問控制研究主要通過對用戶信息采取受限訪問或信任管理措施，忽略了保護用戶隱私的同時最大化信息的影響力傳播。

綜上所述，在已有的信息傳播預測研究中，研究者未考慮將轉(zhuǎn)述作為信息傳播方式的可能性，這會造成對傳播信息進行溯源時傳播路徑的遺漏，從而在信息傳播建模中發(fā)生轉(zhuǎn)述行為時，無法捕捉隱私信息的泄漏。在影響力最大化問題研究中，各式算法雖從不同角度探索最大化影響力的最佳方案，卻忽略了傳播過程中的隱私保護問題。而對于社交網(wǎng)絡(luò)，用戶隱私作為最常見的信息載體，缺少隱私保護措施的影響力傳播方案顯然難以直接應(yīng)用于實際環(huán)境。雖然現(xiàn)有的社交網(wǎng)絡(luò)訪問控制研究可以應(yīng)用于用戶隱私保護，但是研究者僅關(guān)注用戶隱私保護問題，忽略了用戶影響力需求。因此，本文針對現(xiàn)有信息傳播模型不能很好建模用戶隱私泄漏產(chǎn)生的原因，以及相關(guān)研究難以平衡用戶隱私保護和信息傳播需求的問題，開展了支持隱私保護的社交網(wǎng)絡(luò)信息傳播方法研究，在支持最大化信息影響力傳播的同時保護用戶隱私。本文方法的主要應(yīng)用：

（1）對于個人用戶：發(fā)布信息時，只需指定黑名單用戶，算法就能自動給出信息的推送對象，使得信息不會泄漏到黑名單用戶。

（2）對于商家：通過將非目標用戶設(shè)置為黑名單，可使用算法發(fā)現(xiàn)社交網(wǎng)絡(luò)中哪些用戶更有進行廣告投放的價值，進行精準推送。

2 支持轉(zhuǎn)述行為的信息傳播模型

在用戶發(fā)布信息后，關(guān)注用戶的好友是信息的直接接收者，信息通過好友的轉(zhuǎn)發(fā)和轉(zhuǎn)述行為進行傳播。在現(xiàn)有僅考慮轉(zhuǎn)發(fā)行為的傳播模型中，用戶的黑名單對象仍能通過傳播過程中的轉(zhuǎn)述行為獲取用戶信息。因此，本文的研究問題是構(gòu)建支持轉(zhuǎn)述行為的傳播模型，使得信息在滿足隱私保護約束條件下，最大化信息傳播的影響力。

研究思路是基于時間相近、位置相鄰、內(nèi)容相似規(guī)則推斷轉(zhuǎn)述關(guān)系，通過好友關(guān)系進行消息傳播預測，利用轉(zhuǎn)發(fā)、轉(zhuǎn)述關(guān)系構(gòu)成消息傳播網(wǎng)絡(luò)，并基于貪心策略計算種子集合獲取信息傳播范圍，最終通過局部影響子圖與泄漏概率上限計算使社交網(wǎng)絡(luò)信息傳播過程滿足隱私保護約束的同時最大化傳播影響力。首先給出本文的概念定義。

2.1 概念定義

2.1.1 基本元素

信息是社交網(wǎng)站中的基本單元，它由社交網(wǎng)絡(luò)的用戶所發(fā)布，可能完全公開（對所有人可見），也可能只對部分人可見，表示為M，信息的發(fā)布用戶表示為User(M)。每條信息有唯一標識符，記作mid。在本文中，信息僅針對用戶文本，M和mid間一一對應(yīng)，對M和mid不作區(qū)分，根據(jù)上下文不同可以混用。

用戶是社交網(wǎng)站的使用者，也是信息發(fā)布者。每個用戶有唯一標識符，記為uid，并用集合U表示社交網(wǎng)絡(luò)的用戶集合。在本文中，uid和u間一一對應(yīng)，對uid和u不作區(qū)分，根據(jù)上下文不同可以混用。

2.1.2 用戶行為

當用戶在社交網(wǎng)絡(luò)中發(fā)布一條原創(chuàng)信息M時，將該行為記為Actpost。當社交網(wǎng)絡(luò)中的用戶接收到一條信息時，可能會產(chǎn)生不同的行為，這里將其區(qū)分為三種類型：

（1）轉(zhuǎn)發(fā)（Forward）：用戶u收到信息后，通過社交網(wǎng)絡(luò)提供的轉(zhuǎn)發(fā)功能來進一步傳播該信息，該行為記作Actforward。用Forward(M) 表示信息M的轉(zhuǎn)發(fā)信息集合，則M'∈Forward(M)表示信息M'是信息M的轉(zhuǎn)發(fā)信息。

（2）轉(zhuǎn)述（Mention）：用戶u收到信息后，發(fā)布了一條新信息，但該新信息與用戶u收到的原信息包含相似的信息，該行為記作Actmention。雖然這種行為從形式上是發(fā)布了一條全新的信息，但這里將其視為一種對所收到信息進行傳播的行為，與Actpost進行區(qū)分。用Mention(M)表示信息M的轉(zhuǎn)述信息集合，則M'∈Mention(M)表示信息M'是信息M的轉(zhuǎn)述信息。

（3）無行為（No Action）：用戶u收到信息后，未以任何形式在社交網(wǎng)絡(luò)中對該信息進行傳播，該行為記作Actno。

定義1（用戶行為）社交網(wǎng)絡(luò)中的用戶行為被定義為式（1）的四元組：

其中，uid是觸發(fā)行為的用戶的標識符；acttype是用戶行為的類型，其取值范圍如式（2）；time是用戶產(chǎn)生該行為的時間；mid是用戶產(chǎn)生行為的信息的標識符，主要有四種情況：

（1）當acttype=Actpost時，mid是用戶發(fā)布的原創(chuàng)信息的標識符；

（2）當acttype=Actforward時，mid是用戶轉(zhuǎn)發(fā)后的信息的標識符；

（3）當acttype=Actmention時，mid是用戶轉(zhuǎn)述后的信息的標識符；

（4）當acttype=Actno時，mid為空。

例1如圖1 所示，以新浪微博為例，用戶“_奶啤超好喝的”發(fā)布了一條信息（參見圖1（a）），接收到信息的用戶“p123TAT”可能存在三種行為：轉(zhuǎn)發(fā)（參見圖1（b））、轉(zhuǎn)述（參見圖1（c））和無行為。

2.1.3 用戶類型

在社交網(wǎng)絡(luò)的不同場景中，用戶會扮演不同的角色類型，下面分社交關(guān)系場景和信息傳播場景進行說明：

（1）社交關(guān)系場景：在社交關(guān)系場景中使用到的用戶類型包括兩種：關(guān)注者、被關(guān)注者。關(guān)注者（Follower）是關(guān)注了用戶u的社交網(wǎng)絡(luò)用戶，用Follower(u)表示用戶u的關(guān)注者集合，F(xiàn)ollower(u)?U。被關(guān)注者（Followee）是被用戶u關(guān)注的社交網(wǎng)絡(luò)用戶，用Followee(u) 表示被用戶u關(guān)注的被關(guān)注者集合，F(xiàn)ollowee(u)?U。

（2）信息傳播場景：用戶在信息傳播場景中有兩種不同的用戶類型：影響者和被影響者。假設(shè)用戶v轉(zhuǎn)發(fā)或轉(zhuǎn)述了用戶u發(fā)布的信息M，則稱用戶u為影響者，用戶v為被影響者。

2.1.4 隱私設(shè)置

用戶u在社交網(wǎng)絡(luò)中發(fā)布的信息M只會被一部分社交網(wǎng)絡(luò)用戶直接接收到，并顯示在其關(guān)注者動態(tài)中，收到信息M的用戶集合記作Viewer(M)，Viewer(M)?Follower(u)，默認情況下Viewer(M)=Follower(u)。

定義2（信息的黑名單）對于信息M，用戶對信息設(shè)置的黑名單記作Blacklist(M)，Blacklist(M)?U，黑名單被用作用戶的隱私保護。當信息M是原創(chuàng)信息時，Viewer(M)=Follower(u)–Blacklist(M)。對于一個信息轉(zhuǎn)發(fā)序列，u是信息Ml的發(fā)布者，那么即對信息設(shè)置的黑名單在信息被轉(zhuǎn)發(fā)多輪時仍然有效。

在不同的應(yīng)用場景下，隱私有著不同的定義。本文將隱私泄漏對象定義為用戶在發(fā)布信息時設(shè)置的黑名單節(jié)點。用戶通過設(shè)置黑名單實現(xiàn)對隱私的傳播控制，對于用戶發(fā)布的信息M，如果在傳播過程中，黑名單節(jié)點接收到信息的概率超過用戶預先設(shè)定的泄漏概率上限，則稱隱私發(fā)生了泄漏。

2.2 社交網(wǎng)絡(luò)信息傳播模型

2.2.1 信息傳播方式

定義3（信息傳播網(wǎng)絡(luò)）信息M的傳播網(wǎng)絡(luò)是一個有向無環(huán)圖GM：

（1）V是網(wǎng)絡(luò)中所有節(jié)點(node)的集合，其中每個node定義如式（4）。

其中，uid是用戶標識符；msgtype描述用戶在信息傳播過程中發(fā)布的信息的類型，取值集合為{Equaled,Derived}，Equaled 表示用戶發(fā)布的信息是信息M的等同信息；Derived 表示用戶發(fā)布的信息是信息M的衍生信息；time表示用戶發(fā)布信息的時間。

（2）E是網(wǎng)絡(luò)中所有關(guān)系(relation)的集合：圖GM中從nodein到nodeout的邊代表信息在用戶之間的傳播方式，定義為：

其中，nodein表示傳播的上游節(jié)點，即影響者；nodeout表示傳播的下游節(jié)點，即被影響者；rtype表示該關(guān)系的類型，rtype∈{Forwarded,Mentioned}，F(xiàn)orwarded 代表的是nodeout節(jié)點對應(yīng)信息是nodein節(jié)點對應(yīng)信息的轉(zhuǎn)發(fā)，Mentioned 代表的是nodeout節(jié)點對應(yīng)信息是nodein節(jié)點對應(yīng)信息的轉(zhuǎn)述。

2.2.2 傳播模型定義

在現(xiàn)實的社交網(wǎng)絡(luò)中，信息的傳播往往不局限于社交網(wǎng)絡(luò)中的轉(zhuǎn)發(fā)功能，還存在著轉(zhuǎn)述關(guān)系。轉(zhuǎn)發(fā)關(guān)系易于追蹤和控制，而轉(zhuǎn)述關(guān)系難以追蹤與控制。而在傳統(tǒng)的社交網(wǎng)絡(luò)傳播模型，如獨立級聯(lián)模型[1]中，每條邊只對應(yīng)一個屬性，這種局限性使得難以在該模型下區(qū)分轉(zhuǎn)發(fā)關(guān)系和轉(zhuǎn)述關(guān)系。因此，為了支持轉(zhuǎn)述行為，本文的社交網(wǎng)絡(luò)傳播模型在獨立級聯(lián)模型的基礎(chǔ)上進行擴展，通過引入邊的類型以及類型對應(yīng)的概率分布來描述用戶行為，以便更好地研究社交網(wǎng)絡(luò)下的信息傳播和隱私泄漏。

定義4（社交網(wǎng)絡(luò)傳播模型）定義社交網(wǎng)絡(luò)傳播模型為有向圖G=(V,E,T,P)，其中V表示社交網(wǎng)絡(luò)中的節(jié)點且V=U，eu,v∈E表示社交網(wǎng)絡(luò)中從節(jié)點u指向節(jié)點v的有向邊，tu,v∈T表示節(jié)點u和v間連邊的類型，每條邊eu,v僅能屬于一種類型。其中連邊類型與社交網(wǎng)絡(luò)中用戶的動作類型一一對應(yīng)，Tp對應(yīng)Actforward，Tq對應(yīng)Actmention，Tr對應(yīng)Actno。

Pu,v表示節(jié)點u和節(jié)點v的連邊類型的概率分布，其中u,v∈V。當節(jié)點u變?yōu)榛钴S態(tài)時，其有且僅有一次機會嘗試以Pu,v的概率分布影響節(jié)點v。

其中，pu,v表示eu,v是一條轉(zhuǎn)發(fā)邊的概率；qu,v表示eu,v是一條轉(zhuǎn)述邊的概率；ru,v表示eu,v是一條普通邊（無行為）的概率。

對于一條即將發(fā)布的新信息M，基于社交網(wǎng)絡(luò)信息傳播模型，通過用戶行為的概率分布對信息傳播進行預測，可以確定信息M的傳播過程，從而為最大化影響力和隱私保護提供支持。

定義5（泄漏路徑）定義R(G,u,v)表示社交網(wǎng)絡(luò)G上從節(jié)點u到節(jié)點v的路徑集合。對一條路徑P=，若存在tni,ni+1=Tr，則該路徑為非有效路徑。對于其他情況，若存在tni,ni+1=Tq，即在路徑上存在轉(zhuǎn)述邊，則該路徑P是一條泄漏路徑，否則P是一條傳播路徑。

注意，正常情況下包含轉(zhuǎn)述關(guān)系的傳播路徑無法追蹤，定義泄漏路徑是為了在傳播過程中對包含轉(zhuǎn)述關(guān)系的傳播路徑和只包含轉(zhuǎn)發(fā)關(guān)系的傳播路徑進行區(qū)分，并不意味著信息發(fā)生了泄漏。

在社交網(wǎng)絡(luò)G中選取一定數(shù)量節(jié)點構(gòu)成種子集合S，其中S?V，假設(shè)存在路徑集合使節(jié)點v的狀態(tài)被影響，則影響的方式有兩種：

（1）到達：H(G,S,v)中包含傳播路徑，但不包含泄漏路徑，產(chǎn)生概率用P(G,S,v)表示，簡寫為P(S,v)，v被稱為到達態(tài)節(jié)點。

（2）泄漏：H(G,S,v)中包含至少一條泄漏路徑，產(chǎn)生概率用Q(G,S,v)表示，簡寫為Q(S,v)，v被稱為泄漏態(tài)節(jié)點。

如定義2 所示，對于到達方式，因為傳播路徑上只存在轉(zhuǎn)發(fā)關(guān)系，在信息M的傳播過程中，接收用戶對信息所設(shè)置的黑名單，會并入到信息M的黑名單中，因此信息M即使被多輪轉(zhuǎn)發(fā)也不會對黑名單中的用戶可見；對于泄漏方式，因為轉(zhuǎn)述關(guān)系難以追蹤，所以與到達方式相比，確定信息是否泄漏到黑名單節(jié)點更加困難。

定義6（影響力）定義IG(S)表示選取S作為社交網(wǎng)絡(luò)G上信息傳播的種子集合時產(chǎn)生的總影響力，其中：

式（8）的約束條件中，O表示社交網(wǎng)絡(luò)中的關(guān)鍵節(jié)點集合，表示黑名單對象，O?V。參數(shù)τj表示用戶希望在選擇種子節(jié)點集合S時，如果能夠保證信息泄漏到節(jié)點oj的概率不超過τj，則種子集合S是合法的。O中每個節(jié)點都對應(yīng)一項隱私保護約束，是一種更一般化的黑名單設(shè)置。集合F社交網(wǎng)絡(luò)中的可選節(jié)點集合，F(xiàn)?V，在實際應(yīng)用中通常對應(yīng)信息發(fā)布者的關(guān)注者集合。需要注意的是，種子集合S必須是集合F的子集，即S?F。

影響力通過到達方式獲得的影響力與泄漏方式獲得的影響力之和計算而得出。在滿足隱私保護約束前提下，通過求解種子集合S，使得用戶發(fā)布的信息在社交網(wǎng)絡(luò)信息傳播模型中獲得最大的影響力。隱私保護約束由發(fā)布信息的用戶設(shè)定，包括限制獲取信息的黑名單節(jié)點oj以及信息泄漏到oj的概率上限τj。黑名單節(jié)點的個數(shù)等于在影響力最大化計算時的隱私保護約束個數(shù)，在每個黑名單節(jié)點上，接收信息的概率都不能超過用戶預先設(shè)定的泄漏概率上限。

例2圖2 所示的是基于社交網(wǎng)絡(luò)傳播模型構(gòu)建的信息傳播過程，用戶0 為發(fā)布信息M的節(jié)點，設(shè)可選節(jié)點集合F={1,2,3}，種子集合S={1,2}，關(guān)鍵節(jié)點集合O={7}，信息由種子集合S獲取，并傳播到了其他節(jié)點上。對于路徑P1=<2,5> 和P2=<2,5,6>，因為只存在轉(zhuǎn)發(fā)邊，所以P1和P2是傳播路徑，節(jié)點5 和節(jié)點6 是到達態(tài)節(jié)點；對于路徑P3=<1,4>，P4=<1,4,7> 和P5=<2,5,7>，因為存在轉(zhuǎn)發(fā)邊，所以P3、P4和P5是泄漏路徑，節(jié)點4 和節(jié)點7 是泄漏態(tài)節(jié)點。在保證信息M傳播到黑名單節(jié)點7 的概率小于預先設(shè)定的上限的情況下，信息M傳播的總影響力大小可由傳播路徑P1、P2和泄漏路徑P3、P4和P5的概率和計算得出。

Fig.2 Process of information communication based on model of social network communication圖2 基于社交網(wǎng)絡(luò)傳播模型構(gòu)建的信息傳播過程

3 支持轉(zhuǎn)述行為的傳播網(wǎng)絡(luò)構(gòu)建方法

對于用戶即將發(fā)布的新信息，為了在滿足預先設(shè)定的隱私保護約束的同時，最大化信息傳播的影響力，需要基于社交網(wǎng)絡(luò)傳播模型，對信息的傳播過程進行預測。而社交網(wǎng)絡(luò)傳播模型依賴于用戶行為的概率分布，因此需要構(gòu)建已發(fā)布信息的傳播網(wǎng)絡(luò)來訓練用戶行為分類器，從而獲得用戶行為的概率分布。構(gòu)建支持轉(zhuǎn)述行為的信息傳播網(wǎng)絡(luò)的具體步驟為：

（1）對于用戶已經(jīng)發(fā)布的信息，通過轉(zhuǎn)述關(guān)系推斷，構(gòu)建信息的傳播網(wǎng)絡(luò)，獲取三種用戶行為：轉(zhuǎn)發(fā)、轉(zhuǎn)述和無行為的標注數(shù)據(jù)。

（2）利用構(gòu)建好的訓練數(shù)據(jù)，通過提取用戶屬性、發(fā)布內(nèi)容和網(wǎng)絡(luò)拓撲結(jié)構(gòu)等特征，訓練用戶行為分類器。

（3）對于即將發(fā)布的新信息，基于用戶關(guān)注關(guān)系網(wǎng)絡(luò)，結(jié)合社交網(wǎng)絡(luò)信息傳播模型，通過用戶行為分類器對用戶的三種行為轉(zhuǎn)發(fā)、轉(zhuǎn)述和無行為的概率分布進行預測，構(gòu)建信息的傳播過程。

一旦確定了信息傳播過程，就可以通過選取合適的種子集合，使得經(jīng)由種子集合傳播的信息到達黑名單節(jié)點的概率小于泄漏概率上限，在保證隱私保護約束的同時，最大化影響力。

3.1 方法概述

3.1.1 問題定義

構(gòu)建傳播網(wǎng)絡(luò)的難點在于，從社交網(wǎng)絡(luò)獲取到的用戶行為只有Actpost和Actforward兩種，而實際上所獲取到的全部Actpost（原創(chuàng)發(fā)布行為）中有一部分應(yīng)當屬于Actmention（轉(zhuǎn)述行為），與傳播網(wǎng)絡(luò)相關(guān)，需要進行區(qū)分。

定義7（信息傳播網(wǎng)絡(luò)構(gòu)建問題）已知一個用戶us發(fā)布信息M的行為Actions=，該行為發(fā)生后，社交網(wǎng)絡(luò)中其他用戶按照時間排序所形成的轉(zhuǎn)發(fā)行為列表Lf，發(fā)布行為列表Lp和任意社交網(wǎng)絡(luò)中用戶u的關(guān)注用戶集合Follower(u)，其中Follower(u)?U，信息傳播網(wǎng)絡(luò)的構(gòu)建問題即是推斷該信息M的傳播網(wǎng)絡(luò)GM。

定義8（添加節(jié)點操作）向傳播網(wǎng)絡(luò)中添加節(jié)點的操作定義為Gafter=AddNode(G,nodeold,nodenew,rtype) 。其中G表示操作前的傳播網(wǎng)絡(luò)；Gafter表示操作后的傳播網(wǎng)絡(luò)；rtype表示將要添加的關(guān)系，取值集合為{Forwarded,Mentioned}；nodeold表示G中的一個節(jié)點，將作為新添加關(guān)系的影響者；nodenew表示添加的新節(jié)點，將作為新添加關(guān)系的被影響者。

傳播網(wǎng)絡(luò)構(gòu)建過程主要通過添加節(jié)點操作完成，初始時建立代表用戶us發(fā)布信息M的節(jié)點，之后按照時間順序?qū)⑿畔⑺绊懙墓?jié)點加入到網(wǎng)絡(luò)中。

3.1.2 方法步驟

傳播網(wǎng)絡(luò)構(gòu)建的主要過程是將信息M發(fā)布后其他用戶發(fā)布的等同信息與衍生信息與之進行關(guān)聯(lián)。對于轉(zhuǎn)發(fā)行為列表Lf，列表中的信息包含了其整個轉(zhuǎn)發(fā)序列的關(guān)系，因此很容易添加到傳播網(wǎng)絡(luò)中。對于發(fā)布行為列表Lp，根據(jù)定義4，其中的一部分信息是信息M的衍生信息，對應(yīng)行為類型Actmention，需要添加到傳播網(wǎng)絡(luò)GM中。而另一部分則是其他用戶的原創(chuàng)信息，對應(yīng)行為類型Actpost，與傳播網(wǎng)絡(luò)GM無關(guān)。

傳播網(wǎng)絡(luò)構(gòu)建的基本思路是依據(jù)時間順序，依次嘗試將當前Action中的信息與傳播網(wǎng)絡(luò)中的已有節(jié)點建立關(guān)系?；静襟E如下：

（1）建立傳播網(wǎng)絡(luò)GM的初始節(jié)點， ；

（2）將列表Lf與列表Lp合并后排序得到列表L；

（3）遍歷列表L，假設(shè)當前遍歷到的行為是，記nodeold為傳播網(wǎng)絡(luò)中發(fā)布信息M'的節(jié)點；

（4）如果acttype=Actmention，則為信息M'新建節(jié)點nodenew，并更新信息傳播網(wǎng)絡(luò)GM=AddNode(GM,nodeold,nodenew,Forwarded)；

（5）如果acttype=Actpost，則為信息M'新建節(jié)點nodenew，并更新信息傳播網(wǎng)絡(luò)GM=AddNode(GM,nodeold,nodenew,Mentioned)。

3.2 轉(zhuǎn)述關(guān)系推斷

社交網(wǎng)絡(luò)中的用戶行為數(shù)據(jù)中不包含轉(zhuǎn)述行為，需要推斷哪些原創(chuàng)信息是其他信息的轉(zhuǎn)述。轉(zhuǎn)述關(guān)系的推斷基于以下原則：

（1）發(fā)布時間相近：兩條信息的發(fā)布時間間隔較短。

（2）網(wǎng)絡(luò)位置相鄰：轉(zhuǎn)述信息的發(fā)布者是原始信息發(fā)布者的關(guān)注者。

（3）信息內(nèi)容相似：兩條信息的主要內(nèi)容相似。

對于Actiona=與Actionb=，當且僅當三個規(guī)則均滿足時，推斷Actionb是Actiona引起的轉(zhuǎn)述行為。判斷Actionb是否是Actiona引起的轉(zhuǎn)述行為，由轉(zhuǎn)述關(guān)系推斷規(guī)則推斷：

（1）時間相近規(guī)則：ta

（2）位置相鄰規(guī)則：ub∈Follower(ua)。

（3）內(nèi)容相似規(guī)則：Similar(Ma,Mb)=true。

時間相近與位置相鄰規(guī)則的判斷易于實現(xiàn)，本文不予贅述，下面討論內(nèi)容相似規(guī)則計算方法。

Similar(M',M)函數(shù)通過設(shè)置信息的文本相似度函數(shù)DocSim(M',M) 的閾值Thdoc和單詞相似度函數(shù)WordSim(M',M)的閾值Thword實現(xiàn)，式（9）給出轉(zhuǎn)述關(guān)系推斷規(guī)則中內(nèi)容相似規(guī)則的計算方法。

其中，信息的文本相似度函數(shù)形式為DocSim:{}→[0,1]。DocSim(M',M)的計算如式（10）。

式中，vM、vM'分別為信息M、M'的文本表示，vM、vM'∈Rd。信息的單詞相似度函數(shù)形式為WordSim:{}→[0,1]。WordSim(M',M)的計算如式（11）。

式中，wordlist(M)、wordlist(M')分別為信息M、M'的單詞序列。

3.3 信息傳播預測

為了做到既能保護用戶在社交網(wǎng)絡(luò)中的隱私又最大化用戶的影響力，當用戶輸入將要發(fā)布在社交網(wǎng)絡(luò)中的信息時，需要能夠?qū)υ撔畔⒃诰W(wǎng)絡(luò)節(jié)點間的傳播方式進行預測。

定義9（信息傳播預測問題）已知一個用戶將要產(chǎn)生的發(fā)布信息行為Actions=，社交網(wǎng)絡(luò)中所有用戶的歷史行為列表Lh，社交網(wǎng)絡(luò)中所有用戶的關(guān)注用戶集合Follower(u),u∈U，輸出：

（1）信息M的等同信息或衍生信息到達用戶u時，用戶u轉(zhuǎn)發(fā)該信息給用戶v的概率pu,v，u∈U,v∈Follower(u)；

（2）信息M的等同信息或衍生信息到達用戶u時，用戶u轉(zhuǎn)述該信息給用戶v的概率qu,v，u∈U,v∈Follower(u)。

定義10（用戶關(guān)注關(guān)系網(wǎng)絡(luò)R）R=(VR,ER)記作社交網(wǎng)絡(luò)的用戶關(guān)注關(guān)系網(wǎng)絡(luò)，VR是R的節(jié)點集合，ER是R的邊集合，滿足以下條件：

（1）R是一個有向圖；

（2）VR=V；

（3）v∈Follower(u)?(u,v)∈ER。

信息傳播的預測問題，可以轉(zhuǎn)換為社交網(wǎng)絡(luò)中用戶關(guān)注關(guān)系網(wǎng)絡(luò)R的三分類問題，即將R中所有邊的類型對應(yīng)到傳播網(wǎng)絡(luò)中轉(zhuǎn)發(fā)邊、轉(zhuǎn)述邊或無行為三種類型中，這些邊的類型由定義4（社交網(wǎng)絡(luò)傳播模型）中的3 種行為（轉(zhuǎn)發(fā)行為Tp、轉(zhuǎn)述行為Tq和無行為Tr）激活新節(jié)點后生成，再通過生成訓練樣本、提取樣本特征、訓練分類模型完成分類。其中生成訓練樣本可以通過使用歷史數(shù)據(jù)構(gòu)建的傳播網(wǎng)絡(luò)獲得，這里不再贅述。本文使用的特征參考了文獻[21]中提出的內(nèi)容特征、拓撲結(jié)構(gòu)特征、交互特征以及用戶特征。

4 支持隱私保護的影響力最大化方法（Local-Greedy）

4.1 方法概述

根據(jù)定義4 的信息傳播模型以及隱私保護約束限制，算法的優(yōu)化目標如式（12）：

式（12）中，IG(S)表示種子集合S在社交網(wǎng)絡(luò)G上產(chǎn)生的影響力大小；F表示種子節(jié)點的可選集合，即種子集合S必須是F的一個子集；O表示網(wǎng)絡(luò)中的關(guān)鍵節(jié)點集合，默認情況下為設(shè)置的黑名單，用戶希望信息以盡可能低的概率泄漏到集合O中的節(jié)點；Q(S,oj)≤τj表示隱私保護約束，即選取的種子集合S必須保證信息泄漏到節(jié)點oj的概率小于τj，集合O中的每個元素都對應(yīng)一項隱私保護約束。

隱私保護約束限制下的影響力最大化問題的難點主要有三點：

（1）如何選擇種子節(jié)點集合，集合F的子集個數(shù)有2|F|個，枚舉所有的子集會造成巨大的時間開銷；

（2）如何估計種子節(jié)點集合產(chǎn)生的影響力的大小，并在社交網(wǎng)絡(luò)上產(chǎn)生盡可能高的影響力；

（3）如何保證算法生成的種子集合能夠滿足隱私保護約束的要求。

為應(yīng)對隱私保護約束限制下的影響力最大化問題的三個難點，本節(jié)提出了支持隱私保護的影響力最大化方法LocalGreedy。針對種子集合選取時枚舉所有子集的問題，基于貪心策略遞增構(gòu)造種子集合，避免枚舉造成的時間開銷；給出計算節(jié)點的局部影響子圖的方法，快速估計通過種子集合傳播產(chǎn)生的影響力；為確保種子集合滿足隱私保護約束限制，提出了推導節(jié)點泄漏態(tài)概率上限的計算方法，判斷種子集合是否滿足隱私保護約束，避免使用蒙特卡洛方法產(chǎn)生的時間開銷。本節(jié)依次按照種子集合選擇策略、影響大小估計方法以及節(jié)點泄漏概率上限計算，分三方面進行算法設(shè)計。

4.2 種子集合選擇策略

為應(yīng)對4.1 節(jié)中的難點（1），本文采用遞增的方法生成種子集合S，初始時令S為空集，并在每輪迭代過程中向集合S添加一個元素。每輪迭代時，在所有添加后滿足隱私泄漏條件約束的節(jié)點中，選擇讓影響力增量最大的元素。定義Δ(S)表示算法每次選擇的依據(jù)如式（13）：

種子集合的選擇基于貪心策略，其依據(jù)主要體現(xiàn)在以下兩方面：

（1）隱私保護約束與集合S存在單調(diào)性，當集合S不符合隱私保護約束的限制時，集合S的任意超集也不符合隱私保護約束的限制，因此從空集開始遞增構(gòu)造，可以及時中止算法，避免多余的計算；

（2）IG(S)同時滿足單調(diào)性和子模性，因此每次選擇使得IG(S)遞增量最大的元素添加具有一定的理論保證。

4.3 影響力計算方法

傳統(tǒng)的蒙特卡洛方法在時間效率上十分低效，本節(jié)提出一個非蒙特卡洛模擬的方法，快速計算選定種子節(jié)點集合后每個節(jié)點狀態(tài)的概率分布。對于一條長度為l-1 的路徑P=，定義函數(shù)，稱為路徑P的影響權(quán)重，表示當把路徑上的每條邊的兩個屬性相加合成一個時，該路徑出現(xiàn)的概率大小。

定義11（最大理想路徑）對于社交網(wǎng)絡(luò)G=(V,E,T,P)中從節(jié)點u到節(jié)點v的所有路徑R(G,u,v)，定義最大理想路徑為節(jié)點u到節(jié)點v間影響權(quán)重最大的路徑MIP(u,v)，具體如式（14）。

考慮單個節(jié)點v被影響的概率，當wp(MIP(u,v))很小時，即使節(jié)點u被影響，信息經(jīng)過其到達節(jié)點v的概率通常也會很小，也就是說節(jié)點v是否被影響與節(jié)點u是否被影響基本無關(guān)。那么在估計節(jié)點v被影響的概率時，可以只考慮其鄰近區(qū)域的節(jié)點和邊構(gòu)成的子圖。

定義12（局部影響子圖） 對于信息傳播模型G=(V,E,T,P)包含節(jié)點v的子圖，定義節(jié)點v關(guān)于θ的局部影響子圖如式（15）。

其中，θ是一個參數(shù)，MIA(θ,v) 由所有滿足約束wp(MIP(u,v))>θ的路徑MIP(u,v)取并集得到。

顯然當θ越小時，MIA(θ,v)所表示的節(jié)點v的局部影響子圖所包含的邊越多。并且根據(jù)定義，局部影響子圖MIA(θ,v)是樹形結(jié)構(gòu)，因此可以使用動態(tài)規(guī)劃在線性時間復雜度下計算節(jié)點v被影響的概率。

本文所提影響力計算方法在僅考慮MIA(θ,v)中的節(jié)點和邊的情況下計算節(jié)點v最后處于各狀態(tài)的概率，處于到達狀態(tài)的概率表示為ap(S,v,MIA(θ,v))，處于泄漏狀態(tài)的概率表示為aq(S,v,MIA(θ,v))。在不引起混淆的情況下，將ap(S,v,MIA(θ,v))簡寫為ap(v)，將aq(S,v,MIA(θ,v))簡寫為aq(v)。更進一步，通過計算所有節(jié)點的局部影響子圖獲取各個節(jié)點的ap(S,v,MIA(θ,v))和aq(S,v,MIA(θ,v))，可以在不使用蒙特卡洛模擬的情況下，得到種子集合S產(chǎn)生的總的影響力大小的估計值：

通過式（16）可以在不使用蒙特卡洛方法的情況下，高效估計種子節(jié)點集合產(chǎn)生的影響力，算法效率僅與節(jié)點數(shù)n和節(jié)點的平均鄰接區(qū)域大小Bθ有關(guān)，時間復雜度為O(n×Bθ)。加上計算每個節(jié)點的局部影響子圖的復雜度，總復雜度為O(n×Bθ×lbBθ)。

4.4 節(jié)點泄漏概率上限計算

考慮節(jié)點集合O中的任一節(jié)點o，要想使得Q(S,o)<τ，那么對于節(jié)點o的入鄰居集合Nin(o)，其中的元素處于泄漏狀態(tài)的概率不應(yīng)過大。定義uq(v)表示Q(S,v)的上限，則可以通過以下規(guī)則來推斷uq(v)的范圍，使每個節(jié)點獲得一個盡可能小的上限，下面給出計算條件。

（1）如果oj∈O，則uq(oj)≤τj；

（2）如果uq(v)≤x，則?u∈Nin(v)，uq(u)≤x/(pu,v+qu,v)。

uq(v)的值越小則可以通過檢驗式（17）的條件是否滿足，更大地提升算法的效果和效率。

具體地，本文所提節(jié)點泄漏概率上限計算方法使用uq(v)來判斷當前的種子集合是否會違反隱私保護約束帶來的限制，即檢查?u∈V,aq(v,θ,MIA(θ,u))≤uq(v)條件是否得到滿足。

節(jié)點泄漏概率上限計算方法的本質(zhì)是對最短路徑算法的一種擴展，通過將原本僅對關(guān)鍵節(jié)點的限制推廣至全圖，從而在獲取到uq(v)之后，就可以與本文所提影響力計算方法結(jié)合，估計種子集合產(chǎn)生的影響力的同時判斷是否滿足隱私保護約束。

5 實驗與效果評估

5.1 實驗數(shù)據(jù)

為了構(gòu)建傳播網(wǎng)絡(luò)，需要真實的社交網(wǎng)絡(luò)數(shù)據(jù)，這里選擇使用爬蟲爬取新浪微博中用戶的公開信息作為實驗數(shù)據(jù)。爬取的數(shù)據(jù)可以分成3 類：微博數(shù)據(jù)、個人信息數(shù)據(jù)和社交關(guān)系數(shù)據(jù)。最終爬取到的微博數(shù)據(jù)中用戶總數(shù)為2 903 403，微博總數(shù)為23 068 115條，其中轉(zhuǎn)發(fā)微博有7 006 235 條。爬取的微博內(nèi)容均為用戶在2018 年國慶期間所發(fā)布的內(nèi)容。

對于轉(zhuǎn)述關(guān)系推斷，根據(jù)時間相近、位置相鄰規(guī)則獲取微博數(shù)據(jù)子集。并利用內(nèi)容相似規(guī)則，推斷轉(zhuǎn)述信息，作為轉(zhuǎn)述關(guān)系的標注數(shù)據(jù)，由于多數(shù)包含相同語義的轉(zhuǎn)述信息的單詞相似度較低，為確保推斷正確的同時獲得更多標注數(shù)據(jù)，經(jīng)過多次調(diào)整，將文本相似度閾值設(shè)置為Thdoc=0.7，單詞相似度閾值設(shè)置為Thword=0.12，推斷出258 179 條轉(zhuǎn)述信息。然后，按照2∶1∶10 的比例生成轉(zhuǎn)發(fā)、轉(zhuǎn)述和無行為3 種類型的訓練數(shù)據(jù)，并使用GDBT（gradient Boosting decision tree）[22]和交叉驗證來訓練用戶行為分類器，得到accuracy、micro-F1 和macro-F1 分別為81.2%、84.4%和80.9%，能夠滿足后續(xù)預測用戶在接收信息時產(chǎn)生的行為概率分布的需求。

因為在現(xiàn)有微博數(shù)據(jù)集上無法獲得用戶設(shè)置的黑名單節(jié)點，所以在進行實驗評估時，通過隨機的方式進行模擬。

隱私保護約束個數(shù)（黑名單節(jié)點個數(shù)）默認情況下為3 個，對應(yīng)的隱私保護參數(shù)（泄漏概率上限）的默認取值范圍為[0,0.1]。不同的算法在進行對比時，使用同一組隱私保護約束和參數(shù)。

5.2 實驗設(shè)計

5.2.1 評價指標與實驗環(huán)境

本文使用以微博數(shù)據(jù)為基礎(chǔ)構(gòu)建的傳播網(wǎng)絡(luò)作為實驗用的社交網(wǎng)絡(luò),并使用3 種指標進行評價：

（1）影響力指標：對于算法生成的種子集合S，使用種子集合S滿足隱私保護約束限制時的影響力IG(S)的均值作為評價指標，稱作影響力指標。影響力指標越大時，算法產(chǎn)生的種子集合在傳播過程中產(chǎn)生的影響力越大，效果越好。

（2）綜合指標：考慮到算法的目標有兩個，最大化傳播產(chǎn)生的影響力和滿足隱私保護約束下的限制，這里定義函數(shù)F(G,S)作為算法的評價指標，以下均簡寫為F(S)，稱作綜合指標：

即當種子集合S不滿足隱私保護約束限制時，F(xiàn)(S)為0，其他情況下F(S)等于種子集合S在網(wǎng)絡(luò)上產(chǎn)生的影響力大小IG(S)。對于綜合指標，當算法產(chǎn)生的種子集合S滿足隱私保護約束限制的概率越大時，該指標越大，說明算法效果越好。除此之外，當算法產(chǎn)生的種子集合S產(chǎn)生的影響力越大時，該指標也越大。因此，F(xiàn)(S)是對算法的隱私保護效果和傳播影響力大小的綜合考量指標。

（3）運行時間指標：對于效果相近的算法，更短的運行時間意味著更好的效率，實驗統(tǒng)計各算法的運行時間以評估其效率。

本文的實驗均在單機平臺下完成，包括Ubuntu 16.04.10 操作系統(tǒng)，1 塊Intel Xeon Silver 4110 CPU，2塊NVIDIA GeForce GTX 1080Ti (11 GB) GPU，32 GB內(nèi)存。所有算法均使用Python3.6 實現(xiàn)。

5.2.2 對比實驗設(shè)計

現(xiàn)有的影響力最大化方法主要分為3 種：啟發(fā)式算法、蒙特卡洛方法的優(yōu)化方法、基于社群的算法。由于基于社群的算法難以擴展到用戶隱私保護需求的情形中，而基于蒙特卡洛的方法具有一定的理論保證，且基于節(jié)點度和節(jié)點在網(wǎng)絡(luò)中的距離是常見啟發(fā)式算法中的依據(jù)，因此本文的對比實驗選取了具有代表性的3 種蒙特卡洛方法：SimulateGreedy 算法、Degree 算法[21]、Distance 算法[21]。其中Degree 算法、Distance 算法均為啟發(fā)式算法，算法中的蒙特卡洛模擬部分僅用來判斷種子集合是否滿足隱私保護約束。

（1）SimulateGreedy 算法：依據(jù)貪心規(guī)則遞增地構(gòu)造種子集合，需要使用蒙特卡洛來估計影響力大小以及是否滿足隱私保護約束限制。

（2）Degree 算法：以節(jié)點的度數(shù)為主要依據(jù)的度啟發(fā)算法，一開始將所有節(jié)點按節(jié)點度數(shù)從大到小進行排序，然后順次嘗試加入種子集合中，需要進行蒙特卡洛模擬。

（3）Distance 算法：以節(jié)點到其他所有節(jié)點的平均距離為主要依據(jù)的啟發(fā)式算法，一開始將所有節(jié)點按從小到大進行排序，然后順次嘗試加入種子集合中，需要進行蒙特卡洛模擬。

（4）LocalGreedy 算法（本文算法）：初始時使用算法CalculateBound 計算每個節(jié)點的uq(v)，估計種子集合影響力時使用算法LocalInfluence。該算法也遞增地構(gòu)造種子集合，但不再需要蒙特卡洛模擬。

SimulateGreedy 算法使用蒙特卡洛方法來計算種子集合的影響力，當模擬輪數(shù)較大時有較好的理論保證。節(jié)點的度數(shù)以及節(jié)點到其他節(jié)點的平均距離是影響力計算研究中經(jīng)常使用的特征，在影響力最大化研究中也經(jīng)常被作為算法設(shè)計的依據(jù)，因此本文將Degree算法與Distance算法作為對比算法。

5.3 結(jié)果與分析

除了使用F(S)和IG(S)作為判斷算法的效果好壞的依據(jù)外，實驗中還依據(jù)算法的運行時間來評價其效率。

（1）鄰近子圖大小參數(shù)θ對算法的影響

因為LocalGreedy 算法通過參數(shù)θ來計算每個節(jié)點的局部影響子圖，所以不同的參數(shù)θ意味著不同大小的鄰近子圖，從而對算法的效果和效率產(chǎn)生影響。圖3 和圖4 分別繪制了以鄰近子圖大小參數(shù)θ作為橫坐標時，算法的影響力指標和運行時間的折線圖。

Fig.3 Influence of θ on effect of LocalGreedy圖3 鄰近子圖大小θ對LocalGreedy 算法效果的影響

Fig.4 Influence of θ on running time of LocalGreedy圖4 鄰近子圖大小θ對LocalGreedy 算法運行時間的影響

當LocalGreedy 算法的參數(shù)θ越大時，節(jié)點的局部影響子圖越小，考慮的邊數(shù)會減少，因而效果會變差，但運行時間會縮短。圖3 與圖4 展示的實驗結(jié)果符合預期。綜合圖3 與圖4 的結(jié)果，當θ=5E-5 時，算法在運行時間與影響力上取得較好的均衡。

（2）算法各指標對比

圖5、圖6、圖7 分別繪制了以可選集合大小作為橫坐標時，算法的運行時間、影響力指標、綜合指標的折線圖。

Fig.5 Comparison of algorithms running time圖5 算法運行時間對比

Fig.6 Comparisons of algorithms influence index圖6 算法影響力對比

Fig.7 Comparisons of algorithms composite index圖7 算法綜合指標對比

從圖5 中可以看出，隨著可選集合大小的增長，SimulateGreedy 算法的運行時間的增長趨勢最大，Degree 算法和Distance 算法基本相當，本文算法也就是LocalGreedy 算法增長趨勢最小。從運行的絕對時間來看，也是本文算法最好，Degree 算法與Distance算法相當接近，SimulateGreedy算法需要的時間最長。

當可選集合大小變大時，因為可以用作種子集合的節(jié)點變多，算法的效果應(yīng)當越來越好，這從圖6和圖7 都得到了驗證。另外，從圖中還可以看出，運行時間最長的SimulateGreedy 算法在效果上稍好于兩種啟發(fā)式算法，而基于節(jié)點度數(shù)的啟發(fā)式算法又更優(yōu)于基于平均距離的啟發(fā)式算法。結(jié)合上述的算法效果對比可以得出結(jié)論，本文算法不僅在運行時間上相對于主流算法有明顯提升，并且在效果上有一定的優(yōu)勢。

（3）隱私保護約束對算法的影響

當關(guān)鍵節(jié)點集合O越大時，隱私保護的約束個數(shù)越多，算法求解過程中的限制越多。圖8 和圖9 分別繪制了以隱私保護約束個數(shù)作為橫坐標時，算法的影響力指標和運行時間對比的折線圖。當隱私保護的約束個數(shù)變多時，本文算法的運行時間有極小的增長趨勢，運行時間優(yōu)勢明顯。并且在各種不同隱私保護約束個數(shù)的情況下，本文算法的效果仍優(yōu)于其他算法。

Fig.8 Influence of the number of privacy protection constraints on effect圖8 隱私保護約束個數(shù)對效果的影響

Fig.9 Influence of the number of privacy protection constraints on running time圖9 隱私保護約束個數(shù)對時間的影響

圖10 展示了改變隱私保護參數(shù)τ的大小時，算法的綜合指標的變化情況。τ值越大時，隱私保護的約束越弱，算法生成的種子集合越容易滿足隱私保護約束限制，從而產(chǎn)生更高的影響力。本文算法在τ≤0.04 時效果與其他算法相當，對于更大的τ值，本文算法在效果上具有一定的優(yōu)勢。

Fig.10 Influence of privacy protection parameter on composite index圖10 隱私保護參數(shù)大小對綜合指標的影響

5.4 實例展示

本節(jié)選取新浪微博用戶關(guān)注網(wǎng)絡(luò)中一個包含80個用戶節(jié)點，985 條關(guān)注關(guān)系的子圖進行實例展示。設(shè)置可選節(jié)點集合F={1,2,3,4,5,6,7,8,9,10}，集合F同時也是要在社交網(wǎng)絡(luò)中發(fā)布信息的用戶的關(guān)注者集合。并設(shè)置關(guān)鍵節(jié)點集合（黑名單用戶集合）O={29,30}，其中標號為29 的用戶微博名為四囍丸子，標號為30 的用戶微博名為奶啤超好喝的，用戶希望信息在傳播過程中不會泄漏到這兩名用戶。

在圖11、圖12 中，綠色節(jié)點表示種子集合中的節(jié)點，藍色節(jié)點表示黑名單用戶，橙色節(jié)點表示節(jié)點處于到達態(tài)，紅色節(jié)點表示節(jié)點處于泄漏態(tài)，其余未受影響的節(jié)點未在圖中畫出。圖中的藍色邊表示轉(zhuǎn)發(fā)關(guān)系，橙色邊代表轉(zhuǎn)述關(guān)系。

圖11 展示了無隱私保護約束時的傳播過程，此時S=F，可選集合中的所有節(jié)點均加入種子集合中，即用戶將信息發(fā)布給所有關(guān)注者。從圖中可以看出，信息泄漏到了節(jié)點編號為29 和30 的兩個黑名單用戶。下面分析信息如何泄漏到節(jié)點30 的黑名單用戶，從信息傳播路徑可以看到，存在泄漏路徑<3,15,21,30>，其中邊(21,30)為轉(zhuǎn)述邊（泄漏路徑中包含至少一條轉(zhuǎn)述邊），信息通過轉(zhuǎn)述邊泄漏到了節(jié)點30對應(yīng)的用戶。如果只考慮轉(zhuǎn)發(fā)關(guān)系，雖然存在傳播路徑<3,11,28,30>，但是因為節(jié)點30 是黑名單中的用戶，信息對該用戶不可見，不會認為產(chǎn)生了隱私泄漏。

圖12（a）展示了為黑名單中用戶添加隱私保護約束后的傳播過程，此時算法為了滿足隱私保護約束，并最大化傳播影響力，輸出S={1,2,6,7,8}，可選節(jié)點集合中容易形成泄漏路徑的節(jié)點未被算法選擇為信息到達節(jié)點。例如節(jié)點3，微博用戶名可口俊凱，該節(jié)點有較高概率通過節(jié)點11 形成到節(jié)點29 的泄漏路徑，以及通過節(jié)點15 形成到節(jié)點30 的泄漏路徑。從圖中還可以看出，算法輸出的種子集合不僅滿足了用戶的隱私保護需求（不存在從種子節(jié)點到黑名單節(jié)點的泄漏路徑），并且還產(chǎn)生了大的影響力，被影響的節(jié)點數(shù)并沒有明顯減少。

Fig.11 Diffusion process without privacy protection constraints圖11 無隱私保護約束時的傳播過程

Fig.12 Diffusion process with privacy protection constraints圖12 隱私保護約束的傳播過程

圖12（b）展示了添加新的黑名單節(jié)點（編號20）后的傳播過程，此時算法輸出S={1,6,7,8}，容易形成到節(jié)點20 的泄漏路徑的節(jié)點2 被排除。實例展示了本文算法可以使社交網(wǎng)絡(luò)用戶在信息不泄漏到一部分特定用戶的情況下，讓信息在其他用戶中取得較高的影響力。

6 結(jié)束語

針對社交網(wǎng)絡(luò)信息傳播過程中，最大化影響力傳播與用戶隱私保護的矛盾，提出了一種支持轉(zhuǎn)述關(guān)系的社交網(wǎng)絡(luò)信息傳播模型和推斷方法，以及種子集合選擇算法IncrementGreedy、局部影響計算算法LocalInfluence和節(jié)點泄漏概率算法CalculateBound，并在此基礎(chǔ)上提出了LocalGreedy 算法。在爬取的新浪微博數(shù)據(jù)集上進行了實驗驗證和實例分析，結(jié)果表明LocalGreedy 算法能夠確保在保護用戶隱私的情況下，最大化傳播的影響力。

未來研究工作將基于本文提出的模型和方法，進一步挖掘社交網(wǎng)絡(luò)信息傳播的特點和隱私泄漏的原因，考慮信息在傳播過程中信息量的變化，并在傳播網(wǎng)絡(luò)構(gòu)建過程中引入更多的特征。