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

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

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

3.移動(dòng)計(jì)算與新型終端北京市重點(diǎn)實(shí)驗(yàn)室，北京 100190

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

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

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

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

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

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

本文主要貢獻(xiàn)包括：

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

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

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

1 相關(guān)工作

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

1.1 信息傳播模型

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

1.2 信息傳播預(yù)測(cè)

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

1.3 影響力傳播

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

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

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

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

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

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

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

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

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

2.1 概念定義

2.1.1 基本元素

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

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

2.1.2 用戶行為

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

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

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

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

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

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

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

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

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

（4）當(dāng)acttype=Actno時(shí)，mid為空。

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

2.1.3 用戶類型

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

（1）社交關(guān)系場(chǎng)景：在社交關(guān)系場(chǎng)景中使用到的用戶類型包括兩種：關(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）信息傳播場(chǎng)景：用戶在信息傳播場(chǎng)景中有兩種不同的用戶類型：影響者和被影響者。假設(shè)用戶v轉(zhuǎn)發(fā)或轉(zhuǎn)述了用戶u發(fā)布的信息M，則稱用戶u為影響者，用戶v為被影響者。

2.1.4 隱私設(shè)置

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

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

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

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

2.2.1 信息傳播方式

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

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

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

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

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

2.2.2 傳播模型定義

在現(xiàn)實(shí)的社交網(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ò)傳播模型，如獨(dú)立級(jí)聯(lián)模型[1]中，每條邊只對(duì)應(yīng)一個(gè)屬性，這種局限性使得難以在該模型下區(qū)分轉(zhuǎn)發(fā)關(guān)系和轉(zhuǎn)述關(guān)系。因此，為了支持轉(zhuǎn)述行為，本文的社交網(wǎng)絡(luò)傳播模型在獨(dú)立級(jí)聯(lián)模型的基礎(chǔ)上進(jìn)行擴(kuò)展，通過引入邊的類型以及類型對(duì)應(yīng)的概率分布來描述用戶行為，以便更好地研究社交網(wǎng)絡(luò)下的信息傳播和隱私泄漏。

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

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

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

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

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

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

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

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

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

如定義2 所示，對(duì)于到達(dá)方式，因?yàn)閭鞑ヂ窂缴现淮嬖谵D(zhuǎn)發(fā)關(guān)系，在信息M的傳播過程中，接收用戶對(duì)信息所設(shè)置的黑名單，會(huì)并入到信息M的黑名單中，因此信息M即使被多輪轉(zhuǎn)發(fā)也不會(huì)對(duì)黑名單中的用戶可見；對(duì)于泄漏方式，因?yàn)檗D(zhuǎn)述關(guān)系難以追蹤，所以與到達(dá)方式相比，確定信息是否泄漏到黑名單節(jié)點(diǎn)更加困難。

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

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

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

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

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)建方法

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

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

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

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

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

3.1 方法概述

3.1.1 問題定義

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

定義7（信息傳播網(wǎng)絡(luò)構(gòu)建問題）已知一個(gè)用戶us發(fā)布信息M的行為Actions=，該行為發(fā)生后，社交網(wǎng)絡(luò)中其他用戶按照時(shí)間排序所形成的轉(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é)點(diǎn)操作）向傳播網(wǎng)絡(luò)中添加節(jié)點(diǎn)的操作定義為Gafter=AddNode(G,nodeold,nodenew,rtype) 。其中G表示操作前的傳播網(wǎng)絡(luò)；Gafter表示操作后的傳播網(wǎng)絡(luò)；rtype表示將要添加的關(guān)系，取值集合為{Forwarded,Mentioned}；nodeold表示G中的一個(gè)節(jié)點(diǎn)，將作為新添加關(guān)系的影響者；nodenew表示添加的新節(jié)點(diǎn)，將作為新添加關(guān)系的被影響者。

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

3.1.2 方法步驟

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

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

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

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

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

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

（5）如果acttype=Actpost，則為信息M'新建節(jié)點(diǎn)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ā)布時(shí)間相近：兩條信息的發(fā)布時(shí)間間隔較短。

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

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

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

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

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

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

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

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

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

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

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

3.3 信息傳播預(yù)測(cè)

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

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

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

（2）信息M的等同信息或衍生信息到達(dá)用戶u時(shí)，用戶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é)點(diǎn)集合，ER是R的邊集合，滿足以下條件：

（1）R是一個(gè)有向圖；

（2）VR=V；

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

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

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

4.1 方法概述

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

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

隱私保護(hù)約束限制下的影響力最大化問題的難點(diǎn)主要有三點(diǎn)：

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

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

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

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

4.2 種子集合選擇策略

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

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

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

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

4.3 影響力計(jì)算方法

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

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

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

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

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

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

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

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

4.4 節(jié)點(diǎn)泄漏概率上限計(jì)算

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

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

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

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

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

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

5 實(shí)驗(yàn)與效果評(píng)估

5.1 實(shí)驗(yàn)數(shù)據(jù)

為了構(gòu)建傳播網(wǎng)絡(luò)，需要真實(shí)的社交網(wǎng)絡(luò)數(shù)據(jù)，這里選擇使用爬蟲爬取新浪微博中用戶的公開信息作為實(shí)驗(yàn)數(shù)據(jù)。爬取的數(shù)據(jù)可以分成3 類：微博數(shù)據(jù)、個(gè)人信息數(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)容。

對(duì)于轉(zhuǎn)述關(guān)系推斷，根據(jù)時(shí)間相近、位置相鄰規(guī)則獲取微博數(shù)據(jù)子集。并利用內(nèi)容相似規(guī)則，推斷轉(zhuǎn)述信息，作為轉(zhuǎn)述關(guān)系的標(biāo)注數(shù)據(jù)，由于多數(shù)包含相同語義的轉(zhuǎn)述信息的單詞相似度較低，為確保推斷正確的同時(shí)獲得更多標(biāo)注數(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 種類型的訓(xùn)練數(shù)據(jù)，并使用GDBT（gradient Boosting decision tree）[22]和交叉驗(yàn)證來訓(xùn)練用戶行為分類器，得到accuracy、micro-F1 和macro-F1 分別為81.2%、84.4%和80.9%，能夠滿足后續(xù)預(yù)測(cè)用戶在接收信息時(shí)產(chǎn)生的行為概率分布的需求。

因?yàn)樵诂F(xiàn)有微博數(shù)據(jù)集上無法獲得用戶設(shè)置的黑名單節(jié)點(diǎn)，所以在進(jìn)行實(shí)驗(yàn)評(píng)估時(shí)，通過隨機(jī)的方式進(jìn)行模擬。

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

5.2 實(shí)驗(yàn)設(shè)計(jì)

5.2.1 評(píng)價(jià)指標(biāo)與實(shí)驗(yàn)環(huán)境

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

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

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

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

（3）運(yùn)行時(shí)間指標(biāo)：對(duì)于效果相近的算法，更短的運(yùn)行時(shí)間意味著更好的效率，實(shí)驗(yàn)統(tǒng)計(jì)各算法的運(yùn)行時(shí)間以評(píng)估其效率。

本文的實(shí)驗(yàn)均在單機(jī)平臺(tái)下完成，包括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 實(shí)現(xiàn)。

5.2.2 對(duì)比實(shí)驗(yàn)設(shè)計(jì)

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

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

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

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

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

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

5.3 結(jié)果與分析

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

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

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

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

Fig.4 Influence of θ on running time of LocalGreedy圖4 鄰近子圖大小θ對(duì)LocalGreedy 算法運(yùn)行時(shí)間的影響

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

（2）算法各指標(biāo)對(duì)比

圖5、圖6、圖7 分別繪制了以可選集合大小作為橫坐標(biāo)時(shí)，算法的運(yùn)行時(shí)間、影響力指標(biāo)、綜合指標(biāo)的折線圖。

Fig.5 Comparison of algorithms running time圖5 算法運(yùn)行時(shí)間對(duì)比

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

Fig.7 Comparisons of algorithms composite index圖7 算法綜合指標(biāo)對(duì)比

從圖5 中可以看出，隨著可選集合大小的增長(zhǎng)，SimulateGreedy 算法的運(yùn)行時(shí)間的增長(zhǎng)趨勢(shì)最大，Degree 算法和Distance 算法基本相當(dāng)，本文算法也就是LocalGreedy 算法增長(zhǎng)趨勢(shì)最小。從運(yùn)行的絕對(duì)時(shí)間來看，也是本文算法最好，Degree 算法與Distance算法相當(dāng)接近，SimulateGreedy算法需要的時(shí)間最長(zhǎng)。

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

（3）隱私保護(hù)約束對(duì)算法的影響

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

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

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

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

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

5.4 實(shí)例展示

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

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

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

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

Fig.11 Diffusion process without privacy protection constraints圖11 無隱私保護(hù)約束時(shí)的傳播過程

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

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

6 結(jié)束語

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

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