S³協(xié)議模型在學習共同體意見領袖識別中的應用

顏榴紅 賈靚

【摘 要】

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

【關鍵詞】 領袖識別；學習共同體；分布式計算；影響力

【中圖分類號】 G40-057 【文獻標識碼】 A 【文章編號】 1009—458x（2015）01—0055—06

一、引言

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

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

二、文獻回顧

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

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

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

三、以評分為基礎的用戶影響力分析

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

1. 影響力的界定

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

2. [S3]計算的相關定義

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

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

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

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

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

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

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

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

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

合并完成后，驗證下式是否成立：

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

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

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

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

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

五、結(jié)語

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

[參考文獻]

[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

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

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

責任編輯 日 新

責任校對 日 新