基于信任度的并行化社區(qū)發(fā)現(xiàn)算法

余紫丹，虞慧群

(1．華東理工大學(xué)計(jì)算機(jī)科學(xué)與工程系，上海200237;2．上海市計(jì)算機(jī)軟件評(píng)測重點(diǎn)實(shí)驗(yàn)室，上海201112)

1 概述

社交網(wǎng)絡(luò)作為人類最復(fù)雜的網(wǎng)絡(luò)之一，與其他的網(wǎng)絡(luò)的不同之處在于，它是由多個(gè)社區(qū)組成的。社區(qū)形成的原因多種多樣，但社區(qū)最重要的基礎(chǔ)，是信任關(guān)系。信任是人類社會(huì)活動(dòng)的基石，社區(qū)內(nèi)的信任關(guān)系維系了社區(qū)的存在、發(fā)展。

目前社會(huì)性網(wǎng)絡(luò)中對(duì)信任的研究還處于起步階段，研究成果較少，鮮有提供準(zhǔn)確計(jì)算信任度的度量方法。文獻(xiàn)［1］提出利用FOAF(Friend of a Friend)在基于Web的社交網(wǎng)絡(luò)中計(jì)算沒有直接聯(lián)系用戶之間的信任度關(guān)系，但是其信任度僅有信任、不信任兩種取值使其很難用于現(xiàn)實(shí)的社交網(wǎng)絡(luò)環(huán)境中;文獻(xiàn)［2］提出了在基于地理位置的社會(huì)性網(wǎng)絡(luò)中結(jié)合鏈接關(guān)系與社會(huì)聲譽(yù)來決策信任度的機(jī)制，但該機(jī)制只適用于特定的網(wǎng)絡(luò)，缺乏普適性。文獻(xiàn)［3］提出的PGP(Pretty Good Privacy)模型把信任的主動(dòng)權(quán)留給用戶自己，通過基于推薦者的網(wǎng)狀信任模型來進(jìn)行信任等級(jí)的判斷。

然而，在PGP的信任模型內(nèi)，信任鏈的長度最大為2，信任度衡量粒度也只有信任、不信任2種選擇，難以應(yīng)用在社交網(wǎng)絡(luò)上。針對(duì)于此，目前已有不少根據(jù)信任推薦模型的社交網(wǎng)絡(luò)信任度計(jì)算方法，例如文獻(xiàn)［4］提出一種如何挑選可信賴用戶進(jìn)行信任推薦的算法。文獻(xiàn)［5］利用節(jié)點(diǎn)之間的鏈接關(guān)系來發(fā)現(xiàn)2個(gè)目標(biāo)用戶之間的最優(yōu)可信信任路徑，但未考慮次要信任路經(jīng)對(duì)兩者信任關(guān)系帶來的影響。但是，由于社交網(wǎng)絡(luò)中用戶的組織關(guān)系比較復(fù)雜，多數(shù)由PGP模型發(fā)展而來的基于信任推薦的算法，對(duì)信任推薦的路徑復(fù)雜度予以回避，或者只考慮一個(gè)中間推薦者的情況，沒有對(duì)存在多個(gè)中間推薦者、形成多信任推薦路徑組合的情況進(jìn)行考慮;又或者只能適用于小規(guī)模數(shù)量的網(wǎng)絡(luò)。為了解決在大規(guī)模社交網(wǎng)絡(luò)下的多信任推薦路徑組合的復(fù)雜情況，必須利用并行化的計(jì)算方法，統(tǒng)一考慮所有信任推薦路徑的情況。

Hadoop是Apache基金會(huì)基于MapReduce計(jì)算模型而完成的一個(gè)處理大規(guī)模數(shù)據(jù)的分布式系統(tǒng)架構(gòu)。它提供了高可靠的分布式存儲(chǔ)系統(tǒng)HDFS和一種分布式計(jì)算平臺(tái)，用戶只要實(shí)現(xiàn)相應(yīng)的 Map、Reduce函數(shù)即可實(shí)現(xiàn)高性能的分布式算法，而不必過多了解底層細(xì)節(jié)。函數(shù)必須滿足Map函數(shù)的輸出與Reduce函數(shù)的輸入類型相同。

本文根據(jù)社交網(wǎng)絡(luò)內(nèi)社區(qū)的特點(diǎn)，在現(xiàn)有的點(diǎn)對(duì)點(diǎn)之間信任模型的基礎(chǔ)上，結(jié)合傳統(tǒng)在P2P領(lǐng)域的經(jīng)典算法，提出計(jì)算社交網(wǎng)絡(luò)上用戶間信任度的方法，并在此基礎(chǔ)上進(jìn)行社區(qū)擴(kuò)散，最終所有節(jié)點(diǎn)所屬社區(qū)趨于穩(wěn)定，并得到最終的社區(qū)劃分結(jié)果。由于計(jì)算機(jī)內(nèi)存限制及算法復(fù)雜度較高，本文利用MapReduce計(jì)算框架來解決這一問題。

2 算法設(shè)計(jì)

本文是針對(duì)大規(guī)模社交網(wǎng)絡(luò)而提出的一種并行化的基于信任度的社區(qū)劃分算法，用途在于分析類似于微博這樣的社交網(wǎng)絡(luò)內(nèi)部的社區(qū)結(jié)構(gòu)，以幫助發(fā)現(xiàn)網(wǎng)絡(luò)隱藏規(guī)律和預(yù)測變化。在此首先介紹信任度的計(jì)算方法，然后描述算法整體框架，針對(duì)框架中每個(gè)模塊涉及到的MapReduce過程，給出對(duì)應(yīng)設(shè)計(jì)及偽代碼實(shí)現(xiàn)。

2．1 信任度的傳播與計(jì)算

首先構(gòu)建一個(gè)社會(huì)網(wǎng)絡(luò)有向無權(quán)圖G=(V，E)，其中V表示頂點(diǎn)(用戶)集合，且共有|V|=n個(gè)用戶節(jié)點(diǎn)，E表示用戶有向關(guān)系的集合，eij表示連接vi，vj2個(gè)頂點(diǎn)的邊。若eij=1，則說明節(jié)點(diǎn)vi到節(jié)點(diǎn)vj之間存在著一條邊，也就說明用戶i對(duì)用戶j進(jìn)行了關(guān)注，用戶i對(duì)用戶j有一個(gè)信任關(guān)系。

目前關(guān)于社交網(wǎng)絡(luò)內(nèi)的信任及其一些特性并沒有權(quán)威的定義，本文首先對(duì)信任作如下假設(shè):

假設(shè)1一個(gè)用戶節(jié)點(diǎn)在初始時(shí)，共有總和為1的信任額度，且平均分配給其所有關(guān)注著的用戶;

假設(shè)2任意2個(gè)用戶之間的信任度，是由他們之間的所有信任推薦路徑?jīng)Q定的。一條路徑上的信任度會(huì)逐漸衰減，多條信任路徑上的信任度會(huì)疊加。

根據(jù)這兩條假設(shè)，易得如下推論:

推論1若用戶i對(duì)用戶j進(jìn)行了關(guān)注，而用戶i共關(guān)注了個(gè)用戶，則i對(duì)j的初始信任度為:

特殊的，不考慮用戶自己對(duì)自己的信任情況，即Tru0(i，i)=0。

推論2信任度能以2種方式傳播:串聯(lián)，并聯(lián)。串聯(lián)會(huì)隨著中間節(jié)點(diǎn)的增加而衰減，以圖1中第1種傳播方式為例，得到用戶1對(duì)用戶4的信任度為:

并聯(lián)會(huì)導(dǎo)致信任度隨著路徑的疊加而增加，以圖1中第2種傳播方式為例，得到用戶1對(duì)用戶8的信任度為:

圖1 信任度傳播方式

所以，對(duì)于任意2個(gè)節(jié)點(diǎn)，必須先找到這2個(gè)節(jié)點(diǎn)之間所有可能的信任推薦路徑，然后再根據(jù)串行、并行的不同給出信任度最終結(jié)果。

然而，在真實(shí)的社交網(wǎng)絡(luò)中，信任推薦路徑并不是可以任意長度的，根據(jù)六度分隔理論，人們最多通過5個(gè)中間人就能互相認(rèn)識(shí)，事實(shí)上，現(xiàn)實(shí)世界中的信任隨著信任鏈的長度的增長而迅速衰減［6］。本文假設(shè)信任推薦路徑的長度最大為4，也就是最多經(jīng)過3個(gè)中間人的信任推薦是有效的。盡管對(duì)路徑長度的限制縮小了信任推薦路徑的可能性，但針對(duì)任意2個(gè)用戶，通過深度優(yōu)先搜索，來窮盡他們的所有可能的信任推薦路徑，從算法復(fù)雜度來講是不可取的。

對(duì)于之前描述的社交網(wǎng)絡(luò)圖而言，若將該網(wǎng)絡(luò)G分成k份，分別為k個(gè)節(jié)點(diǎn)集合φ={N1，N2，…，Nk}。若該劃分具有對(duì)于每個(gè)Ni∈φ，都滿足Ni內(nèi)的節(jié)點(diǎn)信任鏈密集、與Ni外信任鏈稀疏的特性，則稱φ為G的基于信任鏈的社區(qū)劃分。

從上面關(guān)于信任度的概念可以知道，最初始的信任度矩陣只與圖的鄰接矩陣有關(guān)，由于鄰接矩陣為:

因此可以得到初始信任度矩陣為:

接下來考慮存在著一個(gè)中間推薦者來進(jìn)行信任度間接傳播的情況，用戶 i，j，考慮經(jīng)過節(jié)點(diǎn){1，2，…，n}信任鏈路徑，可得:

這等價(jià)于2個(gè)初始信任度矩陣相乘后的矩陣上［i，j］元素，直觀的角度來看，初始信任度表示了用戶之間的信任關(guān)系，可以畫成一個(gè)二部圖，而當(dāng)2個(gè)初始信任度矩陣相乘時(shí)，可以將這樣的信任傳播過程可以畫成如圖2所示的三部圖。Tru1(i，j)的幾何含義，便是節(jié)點(diǎn)i到節(jié)點(diǎn)j之間所有可能的信任推薦路徑上的權(quán)值之和。類似的，若考慮用戶i，j存在著2個(gè)中間推薦者來進(jìn)行信任度間接傳播的情況，則如圖3所示。

圖2 初始信任度矩陣相乘時(shí)形成的傳播圖

圖3 存在2個(gè)中間推薦者時(shí)的信任傳播圖

用戶i，j需要尋找2個(gè)中間節(jié)點(diǎn)來做信任推薦，可以得到:

這等價(jià)于3個(gè)初始信任度矩陣相乘后的矩陣上［i，j］元素。

以此類推，可以得到:Truk=(Tru0)k+1。

這樣，就得到了最終的信任度計(jì)算公式:

這樣，問題就從路徑搜索問題，轉(zhuǎn)換為大矩陣相乘問題。

2．2 算法整體框架

在得出如何求解任意2個(gè)用戶之間的信任度后，給出如下的算法框架，對(duì)基于信任度的并行化社區(qū)算法予以描述。

如圖4所示，該算法首先通過用戶之間的關(guān)注關(guān)系構(gòu)造初始信任度矩陣，并且通過信任度的兩種傳播方式來更新信任度矩陣，然后在最終形成的信任度矩陣上，通過社區(qū)標(biāo)簽的迭代擴(kuò)散，得到最終的社區(qū)劃分矩陣。

圖4 算法整體框架

圖4中M和R表示MapReduce過程中的Mapper和Reducer。下面對(duì)這4個(gè)步驟的算法作簡要說明。

2．2．1 數(shù)據(jù)預(yù)處理模塊

一般從社交網(wǎng)絡(luò)上得到的數(shù)據(jù)是以＜User ID，follower 1，follower 2，…＞這樣的格式存儲(chǔ)在文本中的，每一行都是一個(gè)用戶及他所關(guān)注的所有對(duì)象。社交網(wǎng)絡(luò)的矩陣維度一般在千萬級(jí)別，其內(nèi)部十分稀疏。故利用MapReduce并行化處理文本，轉(zhuǎn)為初始信任度矩陣，采用三元組存儲(chǔ)。偽代碼如下所示:

2．2．2 信任度更新模塊

信任度矩陣公式本質(zhì)是大矩陣的乘法運(yùn)算，參考文獻(xiàn)［7］及式(7):

給出一種大規(guī)模矩陣乘法算法，通過2輪MapReduce，在第1輪中，將矩陣A的行元素與矩陣B的對(duì)應(yīng)列元素相乘，在第2輪中，將相乘的結(jié)果累加起來，形成更新后的信任度矩陣。大規(guī)模矩陣乘法的流程如圖5所示。

在這樣的矩陣乘法基礎(chǔ)上，給出如下偽代碼，以進(jìn)行信任度矩陣的迭代計(jì)算，并通過累加，得到最終信任度。

2．2．3 社區(qū)傳播模塊

在得到用戶兩兩之間的最終信任度后，這里給出一種社區(qū)劃分的算法，首先賦予每個(gè)節(jié)點(diǎn)一個(gè)獨(dú)立的社區(qū)id，在每一輪迭代時(shí)，每個(gè)節(jié)點(diǎn)的社區(qū)id由其信任的那些節(jié)點(diǎn)決定，信任度越大對(duì)該節(jié)點(diǎn)的影響越大。通過這樣的社區(qū)id更新，相互信任度較高的節(jié)點(diǎn)集合會(huì)迅速對(duì)社區(qū)id達(dá)成共識(shí)，形成社區(qū)。每輪迭代只依賴于上一輪的社區(qū)id分配結(jié)果，利用三維數(shù)組＜User id，Community id，w＞將社區(qū)分配存儲(chǔ)下來，w是用戶被分配到該社區(qū)的強(qiáng)度，初始值為1，在迭代過程中與信任度相乘，并更新。若每一條數(shù)據(jù)分配12個(gè)字節(jié)，可以表示三維數(shù)組每維范圍為［1～232］，足以記錄千萬用戶數(shù)量級(jí)時(shí)的社區(qū)分配情況，在數(shù)據(jù)規(guī)模千萬級(jí)時(shí)需要百兆級(jí)別的內(nèi)存，故可以在每輪迭代前將用戶的社區(qū)id分配結(jié)果放在內(nèi)存中，通過get-Social-Id(User id)這樣的方法讀取。然后在Mapper端計(jì)算一個(gè)節(jié)點(diǎn)所有可能的社區(qū)id，并更新其對(duì)應(yīng)的權(quán)重，在Reducer端完成對(duì)社區(qū)id的選擇，當(dāng)各用戶的社區(qū)id分配穩(wěn)定后(更改社區(qū)id的用戶數(shù)量小于用戶總數(shù)n×10-3)循環(huán)終止，在得到最終的社區(qū)id分配，并將其輸出。用戶節(jié)點(diǎn)更新社區(qū)id的偽代碼如下:

2．3 算法分析

算法采用信任度推薦者模型迭代計(jì)算任意2個(gè)用戶的信任度，然后在此基礎(chǔ)上采用社區(qū)傳播的方式進(jìn)行社區(qū)劃分，相較于傳統(tǒng)的直接在網(wǎng)絡(luò)關(guān)系圖上進(jìn)行圖聚類的算法而言，本文算法在第一輪的迭代過程中，加強(qiáng)了簇內(nèi)用戶之間鏈接關(guān)系，而在第2輪的迭代過程中，處在簇內(nèi)中心位置、與周圍信任度都較高的節(jié)點(diǎn)，會(huì)迅速將簇標(biāo)簽信息(社區(qū)ID)傳播到整個(gè)簇內(nèi)用戶節(jié)點(diǎn)，使得社區(qū)結(jié)構(gòu)自然地呈現(xiàn)出來。

本文算法的復(fù)雜度，主要取決于迭代過程中計(jì)算大矩陣乘法的復(fù)雜度。通過針對(duì)矩陣乘法設(shè)計(jì)的偽代碼可知，若令No［Ai］代表矩陣A的第i行中非零值的個(gè)數(shù)，則本文所用稀疏矩陣相乘算法的時(shí)間復(fù)雜度為，與矩陣的實(shí)際稀疏程度相關(guān)。

3 實(shí)驗(yàn)與結(jié)果分析

3．1 實(shí)驗(yàn)環(huán)境及實(shí)驗(yàn)數(shù)據(jù)

本文實(shí)驗(yàn)在由10個(gè)節(jié)點(diǎn)組成的Hadoop集群上進(jìn)行，集群中每臺(tái)機(jī)器硬件環(huán)境相同，配置信息如表1所示。

表1 集群基礎(chǔ)配置

清華大學(xué)唐杰教授通過隨機(jī)抽取100個(gè)新浪微博用戶，抓取他們的關(guān)注者和粉絲，并最終發(fā)布了一個(gè)有1 787 444個(gè)用戶節(jié)點(diǎn)、308 489 739條關(guān)注關(guān)系的社交網(wǎng)絡(luò)數(shù)據(jù)［8］。

此外，還有一些經(jīng)典的小型社交網(wǎng)絡(luò)數(shù)據(jù)集［9］，Zachary數(shù)據(jù)集為美國一所大學(xué)的空手道俱樂部成員間關(guān)系的網(wǎng)絡(luò);LesMis數(shù)據(jù)集為《悲慘世界中》人物關(guān)系網(wǎng)絡(luò);Dolphin數(shù)據(jù)集為62只海豚組成的種群中，各成員交流頻度的社交網(wǎng)絡(luò)［10］。

3．2 精準(zhǔn)度對(duì)比

首先在數(shù)據(jù)集上證明本文算法劃分社區(qū)的準(zhǔn)確性，針對(duì)各類數(shù)據(jù)集，應(yīng)用本文算法與傳統(tǒng)的Label-Propagation算法、Random-Walk算法和 Fast-Greedy算法進(jìn)行實(shí)驗(yàn)［11］，以證明本文算法社區(qū)劃分的準(zhǔn)確度。這3種傳統(tǒng)算法均是針對(duì)單機(jī)環(huán)境設(shè)計(jì)完成的。由于Random-Work算法需要計(jì)算任意2個(gè)節(jié)點(diǎn)之間的距離，而Fast-Greedy算法需要迭代計(jì)算整體網(wǎng)絡(luò)圖的模塊度值，隨著節(jié)點(diǎn)數(shù)目的增加，這2種算法導(dǎo)致的時(shí)間耗費(fèi)越來越大，在面對(duì)大規(guī)模微博數(shù)據(jù)集時(shí)，不能夠在有限的時(shí)間內(nèi)完成。相對(duì)的，LP算法由于有著接近線性的時(shí)間復(fù)雜度，不需要計(jì)算復(fù)雜的優(yōu)化公式，因而在微博數(shù)據(jù)集下，只令本文算法與LP算法進(jìn)行比較。

社區(qū)劃分并無準(zhǔn)確的判斷標(biāo)準(zhǔn)，現(xiàn)行的常見做法是采用Q函數(shù)［11］來評(píng)判社區(qū)的質(zhì)量，具體結(jié)果如表2所示。由實(shí)驗(yàn)結(jié)果可知，本文算法在Q函數(shù)評(píng)價(jià)標(biāo)準(zhǔn)下，較LP，RW，F(xiàn)G算法而言，有著更好的社區(qū)劃分效果。

表2 各數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果比較

3．3 可擴(kuò)展性

3．3．1 運(yùn)行時(shí)間隨數(shù)據(jù)集大小的變化

將微博數(shù)據(jù)集上所有的節(jié)點(diǎn)分為10份，每輪實(shí)驗(yàn)分別輸入1份 ～10份數(shù)據(jù)，觀察算法隨數(shù)據(jù)規(guī)模變化所耗費(fèi)的時(shí)間，實(shí)驗(yàn)結(jié)果如圖6所示。其中，輸入數(shù)據(jù)比例=輸入數(shù)據(jù)量/總數(shù)據(jù)量。

圖6 不同輸入數(shù)據(jù)量下算法執(zhí)行時(shí)間

實(shí)驗(yàn)結(jié)果表明，本文算法在千萬規(guī)模的數(shù)據(jù)集上，未存在計(jì)算時(shí)間急劇增多的問題，有較強(qiáng)的處理大規(guī)模社交網(wǎng)絡(luò)的能力。

3．3．2 運(yùn)行時(shí)間隨節(jié)點(diǎn)數(shù)目的變化

將集群機(jī)器的數(shù)目改變，觀察算法運(yùn)行時(shí)間與機(jī)器數(shù)量的關(guān)系。

從圖7可以看出，隨著機(jī)器數(shù)目的增加，算法的運(yùn)行時(shí)間相應(yīng)減少，這證明算法有很強(qiáng)的可擴(kuò)展性。從上面的分析中可以看出，本文算法無論是在算法效率還是所得社區(qū)模塊度上都要明顯好于基準(zhǔn)算法的效果，原因在于本文在第一步迭代信任度的過程中，加強(qiáng)了不直接相鄰節(jié)點(diǎn)相互關(guān)聯(lián)的潛在信息，避免直接進(jìn)行社區(qū)擴(kuò)散時(shí)可能導(dǎo)致的局部最優(yōu)問題，取得了較好的結(jié)果。

圖7 不同執(zhí)行機(jī)器數(shù)目下算法執(zhí)行時(shí)間

4 結(jié)束語

本文設(shè)計(jì)并實(shí)現(xiàn)了一種并行化的社區(qū)發(fā)現(xiàn)算法。該算法首先參考PGP算法里的推薦者信任模型，提出一種根據(jù)鏈接關(guān)系計(jì)算用戶之間信任度的方法，并在此基礎(chǔ)上，進(jìn)行社區(qū)擴(kuò)散，將處在社交網(wǎng)絡(luò)潛在社區(qū)內(nèi)中心位置、與周圍信任度都較高的節(jié)點(diǎn)的社區(qū)ID傳播到整個(gè)潛在社區(qū)中，得到社區(qū)劃分的結(jié)果。本文還利用了Hadoop集群對(duì)算法進(jìn)行并行化設(shè)計(jì)，使得算法具有較好的可擴(kuò)展性。在數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文算法既在準(zhǔn)確度上有所提高，也有處理大規(guī)模社交網(wǎng)絡(luò)的能力。然而，在真實(shí)的社交網(wǎng)絡(luò)中，可能還存在著重疊部分，本文的算法無法適用于社區(qū)重疊的情況，需要作進(jìn)一步的改善。

［1］ Jennifer G，James H．Inferring Binary Trust Relationships in Web Based Social Networks［J］．ACM Transactions on Internet Technology，2006，6(4):497-529．

［2］ Symeonidis P，Ntempos D，Manolopoulos Y．Locationbased Social Networks［M］//Symeonidis P，Ntempos D，Manolopallos Y．Recommender Systems for Location-based Social Networks．New York，USA:Springer，2014:35-48．

［3］ Zimmermann P．Pretty Good Privacy User’s Guide［Z］．1993．

［4］ Jiang W，Wu J，Wang G．RATE:Recommendation-aware Trust Evaluation in Online SocialNetworks［C］//Proceedings of the 12th IEEE International Symposium on Network Computing and Applications．Washington D．C．，USA:IEEE Press，2013:149-152．

［5］ Liu G，Wang Y，Orgun M A，et al．Finding the Optimal Social Trust Path for the Selection of Trustworthy Service Providersin Complex SocialNetworks［J］．IEEE Transactions on Services Computing，2013，6(2):152-167．

［6］ 田俊峰，魯玉臻，李 寧．基于推薦的信任鏈管理模型［J］．通信學(xué)報(bào)，2011，32(10):1-9．

［7］ Buluc A，GilbertJR．ParallelSparse Matrix-matrix Multipli-cation and Indexing:Implementation and Experiments［J］．SIAM Journal on Scientific Computing，2012，34(4):170-191．

［8］ Zhang Jing，Liu Biao，Tang Jie，et al．Social Influence Locality for Modeling Retweeting Behaviors［C］//Proceddings of IJCAI’13．Menlo Park，USA:AAAI Press，2013．

［9］ Fortunato S．Community Detection in Graphs［J］．Physics Reports，2010，486(3):75-174．

［10］ Lusseau D，Newman M E J．Identifying the Role that Animals Play in Their Social Networks［J］．Proceedings of the Royal Society of London Series B-biological Sciences，2004，271(6):477-481．

［11］ 楊 博，劉大有，劉際明，等．復(fù)雜網(wǎng)絡(luò)聚類方法［J］．軟件學(xué)報(bào)，2009，20(1):54-66．