顏榴紅 賈靚

【摘 要】

意見領(lǐng)袖在社交網(wǎng)絡(luò)成員中具有巨大影響力，識別意見領(lǐng)袖對于任何社交網(wǎng)絡(luò)，包括在線學(xué)習(xí)共同體，都有重大意義。目前，意見領(lǐng)袖識別方法大多忽略了對學(xué)習(xí)共同體中話題和成員的評分?jǐn)?shù)據(jù)。原因很可能是學(xué)習(xí)共同體平臺缺乏保障評分結(jié)果真實(shí)性的技術(shù)手段，致使研究者無法獲取可靠的評分?jǐn)?shù)據(jù)。本文提出了一種滿足S3（社交性、擴(kuò)展性和安全性）計(jì)算需求的協(xié)議模型，保證評分?jǐn)?shù)據(jù)收集過程和結(jié)果的真實(shí)性和正確性，從而將評分?jǐn)?shù)據(jù)納入意見領(lǐng)袖識別的關(guān)鍵環(huán)節(jié)——影響力分析。在引入評分因素的基礎(chǔ)上，提出了一種新的適用于意見領(lǐng)袖識別的影響力分析方法。

【關(guān)鍵詞】 領(lǐng)袖識別；學(xué)習(xí)共同體；分布式計(jì)算；影響力

【中圖分類號】 G40-057 【文獻(xiàn)標(biāo)識碼】 A 【文章編號】 1009—458x（2015）01—0055—06

一、引言

自20世紀(jì)90年代計(jì)算機(jī)科學(xué)繁榮發(fā)展以來，作為革命性技術(shù)之一的網(wǎng)絡(luò)技術(shù)突飛猛進(jìn)。今天，網(wǎng)絡(luò)與普通人的日常生活緊密相關(guān)，現(xiàn)實(shí)世界的很多社會活動，如商業(yè)、教育和娛樂等，都被映射到網(wǎng)絡(luò)中。對于社會網(wǎng)絡(luò)中開展的活動，通常會存在能對大多數(shù)用戶產(chǎn)生輿論和意見導(dǎo)向的一小群用戶，這些用戶被稱為意見領(lǐng)袖[1][2][3]。對于在線學(xué)習(xí)共同體，意見領(lǐng)袖往往能通過在線學(xué)習(xí)交流形成的直接與間接社會關(guān)系，對其他用戶造成波及效應(yīng)[4]。雖然很多研究著眼于學(xué)習(xí)共同體中意見領(lǐng)袖的識別，但多使用常見的數(shù)據(jù)分析手段，如話題或關(guān)鍵字提取等，而忽略了評分?jǐn)?shù)據(jù)。原因很可能是缺乏可靠的技術(shù)手段保證評分?jǐn)?shù)據(jù)，特別是指定時間段內(nèi)多用戶并發(fā)評分的真實(shí)性。為了全面、精確地反映意見領(lǐng)袖識別過程中的個體關(guān)系，本文提出一種滿足社交性、擴(kuò)展性和安全性的協(xié)議模型，用于確保評分?jǐn)?shù)據(jù)的真實(shí)性和正確性，并探索一種應(yīng)用評分?jǐn)?shù)據(jù)的影響力分析方法。

本文針對學(xué)習(xí)共同體，改進(jìn)了Giurgiua 等提出的[S3]協(xié)議模型[5]，并提出了一種應(yīng)用該協(xié)議模型收集數(shù)據(jù)的影響力分析方法。 該協(xié)議首先將學(xué)習(xí)共同體按用戶參與特性進(jìn)行分組，對各組用戶投票采用先跨組后組內(nèi)的累加式收集，直至完成所有用戶投票收集。該協(xié)議已被證明滿足[S3]計(jì)算要求[6]。本文將[S3]協(xié)議收集的評分?jǐn)?shù)據(jù)引入意見領(lǐng)袖識別過程中一個主要因子（即影響力）的評估，并將其量化為兩部分：一是潛在意見領(lǐng)袖對瀏覽話題用戶的直接影響；二是其對話題回復(fù)用戶的波及效應(yīng)。前者主要取決于瀏覽次數(shù)，后者由回復(fù)用戶的影響力決定，兩者在本質(zhì)上都受評分?jǐn)?shù)據(jù)的影響。

二、文獻(xiàn)回顧

多數(shù)意見領(lǐng)袖識別模型都基于社交網(wǎng)絡(luò)中個體關(guān)系分析。個體種類及其關(guān)系取決于研究涉及的范圍。已有研究中必要的個體種類和關(guān)系分別是用戶和用戶間關(guān)系，通常根據(jù)研究涉及范圍的大小完成量化。一些識別模型不僅涉及用戶和話題，而且深入到內(nèi)在的用戶心理類型和外在現(xiàn)實(shí)世界，如SuperedgeRank算法[7]。一些模型僅將用戶及其文檔模型化為個體，并細(xì)致分析了兩種個體的各個因素，如用戶行為、話題相似性等[8]。還有一些模型僅考慮社交網(wǎng)絡(luò)中的某一方面，并對此開展深入研究，如用于量化用戶關(guān)系的距分析[9]。

從模型實(shí)現(xiàn)來看，目前的意見領(lǐng)袖識別大致分為三類：依賴圖的類型、不依賴圖的類型和混合類型。多數(shù)是混合類型。一般情況下，依賴圖的類型借助社交網(wǎng)絡(luò)分析（social network analysis，SNA）對用戶分類，將其互動映射為圖中的節(jié)點(diǎn)后進(jìn)行評估[10][11]。這種類型的缺點(diǎn)是當(dāng)節(jié)點(diǎn)數(shù)增加后，算法的復(fù)雜性和處理圖的代價(jià)過高[12]，如SuperedgeRank算法完全依賴圖中節(jié)點(diǎn)化的superedge實(shí)現(xiàn)，定義了四種個體并將個體集合抽象為層，四層中個體間的關(guān)系由連接個體的superedge體現(xiàn)。當(dāng)個體數(shù)量增加時，superedge（即節(jié)點(diǎn)數(shù)量）呈指數(shù)級增長。具有較平衡性能的混合型使用圖式的數(shù)據(jù)，但采用不依賴圖的算法完成分析，如將用戶間關(guān)系概念化為圖中入度（in-degree）和出度（out-degree），并依此完成距計(jì)算。這個過程只涉及了圖的概念，并未引入圖及其算法。不依賴圖的類型直接分析原始數(shù)據(jù)而不使用圖的概念或算法，如使用原始數(shù)據(jù)直接計(jì)算用戶影響力和活躍程度[13]。

雖然有很多研究著眼于意見領(lǐng)袖識別，但引入用戶投票結(jié)果的很少，主要原因很可能是缺乏可靠的技術(shù)手段收集投票結(jié)果，致使結(jié)果有可能被潛在惡意用戶篡改。目前，涉及[S3]要求的協(xié)議模型大多沒有滿足其計(jì)算要求，例如Benaloth、Rivest和Yao提出的協(xié)議模型僅具備有限的可擴(kuò)展性[14][15][16]；Aberer等描述了一種改進(jìn)的安全機(jī)制，但要求分布式計(jì)算僅在受信任節(jié)點(diǎn)之間展開[17]；Angluin等構(gòu)造的協(xié)議模型涉及[S3]的可擴(kuò)展性，但只具備有限的容錯性[18]；Guerraoui介紹的協(xié)議模型[19]的可擴(kuò)展性比Angluin等構(gòu)造的好，但要求代理節(jié)點(diǎn)具有唯一的身份標(biāo)識，從而降低了隱私性。完全滿足社交性、擴(kuò)展性和安全性的[S3]協(xié)議模型應(yīng)適用于多用戶并發(fā)投票過程，為收集用戶數(shù)據(jù)提供可靠保障。本文通過[S3]協(xié)議模型收集的數(shù)據(jù)作為評分因子引入意見領(lǐng)袖識別過程中的關(guān)鍵因素——影響力分析，并受到了李艷燕提出的意見領(lǐng)袖識別算法的啟發(fā)[20]。

三、以評分為基礎(chǔ)的用戶影響力分析

學(xué)習(xí)共同體中的用戶可被六種性質(zhì)描述：持久性、集中性、專業(yè)性、新穎性、影響力和活躍性[21]，其中的決定性因素，同時也是諸多研究者注意的焦點(diǎn)是影響力。除影響力以外，具有其他高特性的用戶很難在學(xué)習(xí)共同體用戶中產(chǎn)生波及效應(yīng)。

1. 影響力的界定

學(xué)習(xí)共同體中用戶活動及關(guān)系主要由文本信息和評分體系體現(xiàn)。典型的文本數(shù)據(jù)包括發(fā)布文檔和回復(fù)。評分?jǐn)?shù)據(jù)包括對文檔和用戶的直接評分和類似文檔瀏覽次數(shù)的間接評分。令[u]表示用戶，[p]表示文檔，[t]表示使用類似LDA[22]的軟件從[p]中提取的、或直接由發(fā)布用戶標(biāo)記的話題或關(guān)鍵字，則[Pt，u]表示由[u]發(fā)布的、主要與[t]相關(guān)的文檔集合；[Rp]表示對[p]的回復(fù)集合；[Vp，u]表示瀏覽過由[u]發(fā)布的[p]的用戶集合；[U]表示所有用戶集合；[T]表示某一特定時刻；[Ratingu1，u2∈（-1，1）]表示歸一化的[u1]對[u2]的評分；[Ratingu1，u2]的正、零和負(fù)值分別表示[u1]對[u2]有正面的印象、沒有印象和負(fù)面的印象；[S]表示集合[S]的基數(shù)。在時刻[T]的[u]的影響力[Influence（u）T]定義如下：

2. [S3]計(jì)算的相關(guān)定義

為能正確計(jì)算[Rating?]，應(yīng)開發(fā)滿足[S3]計(jì)算要求的協(xié)議。以下定義詳細(xì)描述了[S3]計(jì)算要求。節(jié)點(diǎn)[P]是平臺中的認(rèn)證用戶，即通過平臺對個人身份和單位核實(shí)的用戶個體。節(jié)點(diǎn)與個體一一對應(yīng)。在平臺中節(jié)點(diǎn)具有兩個基本權(quán)利：① 與任一節(jié)點(diǎn)通信，且信息無法被其他節(jié)點(diǎn)截獲；② 標(biāo)注任一節(jié)點(diǎn)。標(biāo)注是指當(dāng)某節(jié)點(diǎn)的非法行為被察覺時，有所察覺的節(jié)點(diǎn)對存在非法行為的節(jié)點(diǎn)進(jìn)行描述。該描述對任一節(jié)點(diǎn)可見，但描述與被描述節(jié)點(diǎn)之間必須存在過通信。如果描述為真，則被描述節(jié)點(diǎn)的平臺內(nèi)信譽(yù)下降，描述成為被描述節(jié)點(diǎn)可見個人信息的一部分，保存一段時間后描述將被刪除；如果描述為假，描述節(jié)點(diǎn)的平臺內(nèi)信譽(yù)下降，被限制描述一段時間并且被平臺標(biāo)注。這種用戶相互監(jiān)督和系統(tǒng)有限介入的模式的有效性已被各種社交網(wǎng)絡(luò)所證明，如在線游戲[23]、推薦系統(tǒng)[24]和垃圾電子郵件過濾[25]等。

協(xié)議模型[T]的隱私性由協(xié)議模型[D]保證。因此，存在滿足[S3]計(jì)算要求的協(xié)議模型，基于此，本文構(gòu)造了適用于學(xué)習(xí)共同體的協(xié)議模型[LC]。

四、[LC]協(xié)議模型

1. [LC]協(xié)議模型概述

[LC]的活動圖如圖1所示，包括3個階段：階段1：構(gòu)建群和生成代理，階段2：生成本地合集和階段3：處理代標(biāo)識的合集。

2. [LC]協(xié)議模型的階段1：構(gòu)建群和生成代理

根據(jù)已有研究[27][28]，當(dāng)[n]個節(jié)點(diǎn)被隨機(jī)分配到[n]個大小為[n]的群時，低信譽(yù)節(jié)點(diǎn)也將被隨機(jī)分配到各群。協(xié)議模型[LC]的節(jié)點(diǎn)分配根據(jù)學(xué)習(xí)共同體進(jìn)行。如果分布式計(jì)算不涉及某些共同體內(nèi)部的數(shù)據(jù)，則采用上述方法分配節(jié)點(diǎn)；如果涉及，則[n]個節(jié)點(diǎn)按共同體進(jìn)行分配，例如[ni]個節(jié)點(diǎn)參與了共同體[i]，那么這[ni]個節(jié)點(diǎn)將被分配至[ni]個大小為[ni]的群。由于[LC]協(xié)議模型需要特定群參與階段3，這個特定群根據(jù)節(jié)點(diǎn)的聲譽(yù)生成，即無論是否涉及共同體內(nèi)部數(shù)據(jù)，在分配節(jié)點(diǎn)之前，選出[n]個聲譽(yù)最高的節(jié)點(diǎn)組成特定群，剩下的[n-n]個節(jié)點(diǎn)按照上述方法分配（如圖2所示）。

分配完成的群組成一個封閉有序的環(huán)。對于任意群中的任意節(jié)點(diǎn)[P]，[P]可以向其所在群中的任意節(jié)點(diǎn)發(fā)送信息，也可以向位于環(huán)中緊鄰[P]所在群的后續(xù)[K]個群以及每個群中的[L]個節(jié)點(diǎn)發(fā)送信息。所有[K×L]個節(jié)點(diǎn)稱為[P]的代理。這些代理的選擇優(yōu)先考慮與P常聯(lián)系的正常信譽(yù)節(jié)點(diǎn)，根據(jù)其交互的頻率[F]和聲譽(yù)[R]計(jì)算[Rαln （F）]其中[F，R，α>1]，按該值從大到小的順序選擇[K×L]個節(jié)點(diǎn)作為代理，并拒絕低信譽(yù)節(jié)點(diǎn)。[α>1]保證[R]對結(jié)果具有較大的影響，[ln （F）]削弱了[F]對結(jié)果的影響。

3. [LC]協(xié)議模型的階段2：生成本地合集

合并完成后，驗(yàn)證下式是否成立：

其中，[δV]是[V]中任意兩點(diǎn)間距離的最大值，且[k∈N]，判斷合并后的輸入是否還在[（U，d）]中，即[v1 ? ...? vk∈V]是否成立。根據(jù)[?]的性質(zhì)，[V?U]成立。如果上式成立，則將合并后的輸入被發(fā)送至代理所在群的所有節(jié)點(diǎn)，否則觸發(fā)警報(bào)。如果有節(jié)點(diǎn)收到了源自同一節(jié)點(diǎn)的生成輸入和逆輸入，則兩者的合并結(jié)果為空。每個節(jié)點(diǎn)合并收到的輸入形成本地合集。階段2適用于所有群，階段3是由聲望群發(fā)起的。圖3描述了階段2的活動。

4. [LC]協(xié)議模型的階段3：處理代標(biāo)識的合集

階段1構(gòu)造的聲望群發(fā)起了階段3。階段2結(jié)束后，所有節(jié)點(diǎn)的真實(shí)輸入保存于本地合集中。階段3的目的是通過處理代標(biāo)識的合集，最終使每個節(jié)點(diǎn)都擁有只包括所有節(jié)點(diǎn)真實(shí)輸入的本地合集，最終在本地對[n]個真實(shí)輸入完成[f]的運(yùn)算。

聲望群中沒有非法節(jié)點(diǎn)，因此可以保證其每個節(jié)點(diǎn)合并得到的本地合集都是相同的。每個節(jié)點(diǎn)對其合集添加唯一的標(biāo)識信息，形成標(biāo)識合集。標(biāo)識合集被每個節(jié)點(diǎn)發(fā)送給對應(yīng)的[K×L]個代理。對于每個收到標(biāo)識合集的代理，如果是首次收到，則將本地合集與標(biāo)識合集合并，然后發(fā)送給隔壁群中對應(yīng)的[L]個代理；如果收到兩次以上，該代理會檢查合集的標(biāo)識是否與上一次相同，如果相同則在群內(nèi)廣播，然后拋棄合集，否則觸發(fā)警報(bào)。這一過程在圖4中稱為“處理代標(biāo)識的合集”。該處理過程反復(fù)進(jìn)行，直到每個節(jié)點(diǎn)都收到了其他[n-1]個節(jié)點(diǎn)的真實(shí)輸入為止。

在上述3個階段中，一旦觸發(fā)警報(bào)，說明合集被參與計(jì)算的低信譽(yù)節(jié)點(diǎn)篡改，計(jì)算結(jié)果將不能保證正確，警報(bào)觸發(fā)后整個計(jì)算會終止，系統(tǒng)會查找參與生成該合集的低信譽(yù)節(jié)點(diǎn)，并標(biāo)注這些節(jié)點(diǎn)。根據(jù)Giurgiu等的理論[30]，協(xié)議模型[LC]具有[ ]-可擴(kuò)展性、[ ]-準(zhǔn)確性和隱私性，滿足[S3]計(jì)算要求。

五、結(jié)語

本文提出了一種分析網(wǎng)絡(luò)學(xué)習(xí)共同體中用戶影響力因素的方法，并構(gòu)造了名為[LC]的[S3]協(xié)議模型。該協(xié)議模型收集的可靠的投票數(shù)據(jù)被用于影響力分析。通過本文提出的結(jié)合用戶投票數(shù)據(jù)的影響力分析方法，可以構(gòu)建一種涵蓋用戶間關(guān)系的精細(xì)的意見領(lǐng)袖識別模型。本文從理論上探討了應(yīng)用[LC]協(xié)議模型評分?jǐn)?shù)據(jù)的影響力分析，仍需進(jìn)一步實(shí)證研究驗(yàn)證其有效性。今后的研究還可以將用戶持久性、集中性、專業(yè)性、新穎性和活躍性模型化，以完善適用于學(xué)習(xí)共同體的意見領(lǐng)袖識別方法。

[參考文獻(xiàn)]

[1][4][8][13][20][22][26] Y. Li， S. Ma， Y. Zhang， R. Huang. Kinshuk， “An improved mix framework for opinion leader identification in online learning communities”， Knowledge-Based Syst.， vol. 43， 2013， pp. 43-51.

[2][7] N. Ma， Y. Liu， “SuperedgeRank algorithm and its application in identifying opinion leader of online public opinion supernetwork”， Expert Syst. with Applicat.， vol. 41， no. 4， 2014， pp. 1357-1368.

[3][9] Y. S. Kim， V. L. Tran， “Assessing the ripple effects of online opinion leaders with trust and distrust metrics”， ， Expert Syst. with Applicat.， vol. 40， no. 9， 2013， pp. 3500-3511.

[5][6][21][30] A. Giurgiua， R. Guerraouia， K. Huguenina，A.-M. Kermarrecb， “Computing in social networks”， Inform. And Computation， vol. 234， pp. 3-16， Feb. 2014.

[10] P. A. C. Smith， “Knowledge sharing and strategic capital the importance and identification of opinion leaders”， The Learning Organization， vol. 12， no. 6， 2005， pp. 563-574.

[11] F. Bodendorf， C. Kaiser， “Detecting opinion leaders and trends in online social networks”， In Proc. of the 2nd ACM workshop on social web search and mining， 2009， pp. 65-68.

[12] J. M. Kleinberg， “Authoritative sources in a hyperlinked environment”， J. of the ACM， vol. 46， no. 5， 1999， pp. 604-632.

[14] J.Benaloh， “Secret sharing homomorphisms： keeping shares of a secret”， in Proc. of the 6th Annu. Int. Conf. Advances in Cryptology， London， UK， 1986， pp. 251-260.

[15] R. Rivest， A. Shamir， Y. Tauman， “How to share a secret”， Commun. of ACM， vol. 22， no. 11， pp. 612-613， Nov. 1979.

[16] A. Yao， “Protocols for secure computations”， in Proc. of the 23rd IEEE Annu. Symp. on Found. of Comput. Sci.， Washington， DC， USA， 1982， pp. 160-164.

[17] L.-H. Vu， K. Aberer， S. Buchegger， A. Datta， “Enabling secure secret sharing indistributed online social networks”， in Proc. of the 25th Annu. Comput. Security Applic. Conf.， Honolulu， Hawaii， USA， 2009， pp. 419-428.

[18] D. Angluin， J. Aspnes， Z. Diamadi， M. J. Fischer， R. Peralta， “Computation in networks of passively mobile finite-state sensors”， Distrib. Comput.，vol. 4， no.18， 2006， pp. 235-253.

[19] R. Guerraoui， E. Ruppert， “Names Trump Malice： tiny mobile agents can tolerate Byzantine failures”， in Proc. of the 36th Int. Colloq. on Automata， Languages and Programming， Rhodes， Greece， 2009， pp. 484-495.

[23] P. Kabus， W. W. Terpstra， M. Cilia， A. Buchmann， “Addressing cheating in distributed MMOGs”， in Proc. of the 4th Ann. Workshop on Network and Syst. Support for Games， New York， USA， 2005， pp. 1-6.

[24] N. Tran， B. Min， J. Li， L. Subramanian， Sybil-resilient online content voting， in Proc. of the 6th USENIX Symp. on Networked Syst. Design and Implementation， Boston， USA， 2009， pp. 15-28.

[25] M. Sirivianos， K. Kim， X. Yang， “SocialFilter： introducing social trust to collaborative spam mitigation”， in Proc. of the 30th IEEE Int. Conf. Comput. Commun.， Shanghai， China， 2011， pp. 2300-2308.

[27] Z. Galil， M. Yung， “Partitioned encryption and achieving simultaneity by partitioning”， Inf. Process. Lett.， vol. 26， no. 2， pp. 81-88， 1987.

[28] I. Gupta， K. Birman， P. Linga， A. Demers， R. van Renesse Kelips， “Building an efficient and stable P2P DHT through increased memory and back-ground overhead”， in Proc. of the Second Int. Workshop on Peer-to-Peer Syst.， Berkeley， CA， USA ， 2003， pp. 160-169.

[29] C. Delporte-Gallet， H. Fauconnier， R. Guerraoui， E. Ruppert， “Secretive birds： privacy in population protocols”， in Proc. of the 11th Int. Conf. Principles of Distributed Syst.， Guadeloupe， French West Indies， 2007， pp. 329-342.

收稿日期：2014-08-15

作者簡介：顏榴紅，常州大學(xué)外國語學(xué)院（213164）。

賈靚，常州大學(xué)信息科學(xué)與工程學(xué)院（213164）。

責(zé)任編輯 日 新

責(zé)任校對 日 新