王 剛

(安康學(xué)院，陜西 安康 725000)

1 概 述

針對社區(qū)發(fā)現(xiàn)的研究是當(dāng)前國內(nèi)外研究的熱點(diǎn)之一[1]。社會(huì)網(wǎng)絡(luò)(social networks)是指社會(huì)中個(gè)人之間、組織之間或者個(gè)人與組織之間比較持久、穩(wěn)定的社會(huì)關(guān)系模式，通常表示為節(jié)點(diǎn)的集合，同一社區(qū)節(jié)點(diǎn)集合之間的連接較多，如果節(jié)點(diǎn)集合之間連接較少，則認(rèn)為屬于不同的社區(qū)。研究網(wǎng)絡(luò)中的社區(qū)有助于分析網(wǎng)絡(luò)行為，對于個(gè)性化推薦具有重要的意義。

目前主要的社區(qū)發(fā)現(xiàn)算法有譜平分法[2-3]、KL算法、層次聚類法、GN算法等。譜平分法由于涉及到許多矩陣特征向量的計(jì)算,計(jì)算的時(shí)間復(fù)雜度可達(dá)O(n3),在大數(shù)據(jù)環(huán)境中,它的效率成為瓶頸。有研究人員從社會(huì)學(xué)角度研究了社區(qū)結(jié)構(gòu)，研究了人際之間的信任關(guān)系及提取[4],對相似度計(jì)算方法進(jìn)行改進(jìn)[5-6]，采取角色連接輪廓方法從結(jié)構(gòu)上進(jìn)行劃分,發(fā)現(xiàn)它們屬于外圍串類型。也有研究人員利用社會(huì)網(wǎng)絡(luò)個(gè)體間的關(guān)系類別和個(gè)體間對應(yīng)社會(huì)屬性相似度引入關(guān)系模型來進(jìn)一步量化團(tuán)隊(duì)成員個(gè)體間的關(guān)系強(qiáng)度[7]。此外，還有學(xué)者對從朋友關(guān)系、距離變化等角度發(fā)現(xiàn)社區(qū)結(jié)構(gòu)進(jìn)行研究[8-9]。上述研究能在一定條件和背景下發(fā)現(xiàn)成員之間的關(guān)系和結(jié)構(gòu)，這些算法注重于網(wǎng)絡(luò)節(jié)點(diǎn)的信息，如出度、入度[10]，而對社區(qū)結(jié)構(gòu)的動(dòng)態(tài)、不對稱、模糊的特性考慮不夠。通常認(rèn)為，結(jié)構(gòu)上臨近的節(jié)點(diǎn)，應(yīng)該屬于一個(gè)社區(qū)，而且關(guān)系是對稱的，即：如果a信任b,那么b就信任a。而實(shí)際應(yīng)用中，考慮到一些具體的關(guān)系[11]，上述結(jié)論不一定有效，如應(yīng)用GN算法，可能會(huì)把邊“a→b”作為兩個(gè)社區(qū)的分界線，如果a和b本身屬于事件非常重要的成員，把他們分割到兩個(gè)社區(qū)就不合適。因此，結(jié)合社區(qū)結(jié)構(gòu)的動(dòng)態(tài)、不對稱、模糊的特性，探討一種新的方法很有必要。根據(jù)信息熵理論，隨著網(wǎng)絡(luò)節(jié)點(diǎn)的擴(kuò)充，信息量增加，網(wǎng)絡(luò)蘊(yùn)含不確定信息的概率就會(huì)增加[12]。因此，一個(gè)社區(qū)內(nèi)部，由于成員的增加，出現(xiàn)不確定性信息的概率應(yīng)該增加，熵就增加，反之，則減少。一個(gè)社區(qū)內(nèi)部，由于信息交流頻繁，表現(xiàn)為一個(gè)穩(wěn)定的綜合體，不確定信息出現(xiàn)的概率不會(huì)劇烈增加或減少，這使得根據(jù)節(jié)點(diǎn)集合熵的變化來確定不同的社區(qū)成為可能。判斷一個(gè)節(jié)點(diǎn)是否屬于一個(gè)社區(qū)，可以通過判斷節(jié)點(diǎn)加入社區(qū)后社區(qū)熵的變化來確定。

對于確定節(jié)點(diǎn)a、b之間關(guān)系的緊密程度，有許多方法，如計(jì)算余弦相似度、皮爾遜相似度系數(shù)等。通常的相似度計(jì)算方法不能很好地解決應(yīng)用數(shù)據(jù)的動(dòng)態(tài)模糊性，而貝葉斯概率在描述個(gè)體之間關(guān)系的動(dòng)態(tài)和模糊性方面有一定的優(yōu)勢，因此文中提出了一種融合貝葉斯概率和熵的社區(qū)發(fā)現(xiàn)算法，并將其與余弦相似度計(jì)算方法進(jìn)行比較。

2 信息熵及貝葉斯網(wǎng)絡(luò)的建立

2.1 信息熵

1948年，香農(nóng)第一次將熵這一概念引入到信息論中，從此，熵這一概念被作為信息的度量，在自然科學(xué)和社會(huì)科學(xué)等領(lǐng)域應(yīng)用廣泛，并成為一些新學(xué)科的理論基礎(chǔ)[13-14]。當(dāng)一種信息出現(xiàn)概率更高的時(shí)候，表明它被傳播得更廣泛，或者說，被引用的程度更高。

一個(gè)信源發(fā)送出什么信息是不確定的，衡量它可以用其出現(xiàn)的概率來度量，信息熵概率公式表示為：

(1)

其中，x表示隨機(jī)變量，與之相對應(yīng)的是所有可能輸出的集合，定義為符號集H(x)；p(x)表示輸出概率函數(shù)。

信息熵用來度量系統(tǒng)的有序化程度，一個(gè)系統(tǒng)越是有序，信息熵就越低，系統(tǒng)越是混亂，信息熵就越高。

2.2 貝葉斯概率與貝葉斯網(wǎng)絡(luò)的生成

貝葉斯概率是由貝葉斯理論所提供的一種對概率的解釋，它將概率定義為主體對一個(gè)命題的信任程度。貝葉斯網(wǎng)絡(luò)通常表示為有向無環(huán)圖，刻畫一組變量的聯(lián)合概率分布，每個(gè)變量在貝葉斯網(wǎng)絡(luò)中表示為一個(gè)節(jié)點(diǎn)，網(wǎng)絡(luò)弧表示斷言“此變量在給定其直接前驅(qū)時(shí)，條件獨(dú)立于其非后繼”，當(dāng)Y到X存在一條有向的路徑,稱X是Y的后繼。對每個(gè)變量有一個(gè)條件概率表，表示該變量在給定其立即前驅(qū)時(shí)的概率分布[15]。貝葉斯法則提供了計(jì)算假設(shè)概率的方法，提供了從先驗(yàn)概率p(h)以及p(D)和p(D|h)計(jì)算后驗(yàn)概率p(h|D)的方法。

貝葉斯公式表示為：

(2)

當(dāng)前推薦系統(tǒng)通常采用關(guān)聯(lián)規(guī)則挖掘方法，可能產(chǎn)生大量的序列模式。序列模式只是項(xiàng)集(Item set)的簡單組合，依據(jù)支持度和可信度進(jìn)行剪枝，而支持度和可信度依據(jù)項(xiàng)的個(gè)數(shù)計(jì)算得來，這樣有些序列模式可能被認(rèn)為毫無意義而被剪枝，如因果關(guān)系。由于刻畫項(xiàng)之間深層關(guān)系存在的局限性，由于沒有達(dá)到支持度閾值而被剪枝，而項(xiàng)之間的因果關(guān)系是非常重要的關(guān)系，不能簡單憑借數(shù)量來判斷，應(yīng)該根據(jù)概率來判斷是否剪枝。

[15] Hasan Alwi, Dendy Sugono, Politik Bahasa:Rumusan Seminar Politik Bahasa, Jakarta: Pusat Bahasa, 2003, pp. xii-xiv.

貝葉斯概率在描述事件因果關(guān)系方面具有優(yōu)勢，所以采用貝葉斯條件概率來描述項(xiàng)之間的概率關(guān)系，依據(jù)概率的大小，尋找社區(qū)中的項(xiàng)集合，這樣就能發(fā)現(xiàn)和挖掘項(xiàng)之間的因果關(guān)系，并用于推薦系統(tǒng)中，從而克服其他方法的局限性。

以商品推薦為例，利用算法1構(gòu)建了用戶貝葉斯關(guān)系網(wǎng)絡(luò)圖，它以用戶為節(jié)點(diǎn)，節(jié)點(diǎn)之間的邊表示用戶之間的貝葉斯關(guān)聯(lián)概率，形成的有向圖如圖1所示。

圖1 用戶關(guān)系邊有向圖

算法1：生成貝葉斯關(guān)系網(wǎng)絡(luò)有向圖。

Begin:

(1)一條記錄包含多個(gè)商品，構(gòu)成節(jié)點(diǎn)U={Ui},Ui={gk}

End

3 社區(qū)結(jié)構(gòu)的發(fā)現(xiàn)

社區(qū)內(nèi)各要素的內(nèi)部及其相互間具有相對穩(wěn)定的關(guān)系，個(gè)體成員之間因?yàn)榛?dòng)而形成相對穩(wěn)定的結(jié)構(gòu)，由于蘊(yùn)含有的共同信念和意愿，成員之間表現(xiàn)出強(qiáng)的趨一性。根據(jù)熵理論，由于系統(tǒng)的穩(wěn)定和凝聚性，新的信息加入會(huì)對原系統(tǒng)的熵造成波動(dòng)，如果新加入的節(jié)點(diǎn)與原系統(tǒng)能融入在一起，或接近度比較高，熵值的波動(dòng)就較小，否則熵值的波動(dòng)就較大?？梢愿鶕?jù)熵值的變化程度來決定新加入的節(jié)點(diǎn)是否被系統(tǒng)接納。該算法隨機(jī)確定一個(gè)節(jié)點(diǎn)為棧頂，建立一個(gè)棧，采用遞歸的思想，根據(jù)節(jié)點(diǎn)加入時(shí)熵值的變化，用閾值進(jìn)行剪枝，超過閾值的節(jié)點(diǎn)不會(huì)加入到已有社區(qū)集合，滿足條件時(shí)結(jié)束遞歸，輸出產(chǎn)生的社區(qū)。

Begin

(1)k=0

(2)建立節(jié)點(diǎn)堆棧S

(3)確定棧頂U(kuò)0，U0可以隨機(jī)選取

(4)選取U0的鄰節(jié)點(diǎn){Uk}

(7)輸出標(biāo)記為True的邊E(H0,Hk)

(8)k=k+1,選取標(biāo)記為False的邊節(jié)點(diǎn)Hk，作為棧頂，轉(zhuǎn)步驟3,直到所有節(jié)點(diǎn)標(biāo)記完成或社區(qū)數(shù)滿足要求

End

算法采用堆棧的形式遍歷了關(guān)系網(wǎng)絡(luò)圖，屬于一個(gè)社區(qū)的邊進(jìn)行了標(biāo)記。算法可以發(fā)現(xiàn)不能劃分到社區(qū)的孤立點(diǎn)，對應(yīng)到事件集合中的某些離散值獨(dú)立的事件。算法在實(shí)際運(yùn)行過程中能夠發(fā)現(xiàn)滿足要求的社區(qū)。

4 實(shí) 驗(yàn)

實(shí)驗(yàn)對上述算法的正確性進(jìn)行測試，同時(shí)展示發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)，并與其他算法進(jìn)行比較，展示該算法的有效性。

實(shí)驗(yàn)選取圖書館圖書借閱記錄10條，每條記錄包括借閱人員的學(xué)號，專業(yè)，借閱書籍類別。利用算法1計(jì)算出讀者之間的關(guān)系矩陣，矩陣的值Uij為有向邊Ui→Uj之間的條件概率，可見Uij不一定等于Uji，如圖2所示。

U1U2U3U4U5U6U7U8U9U10U110.20.40.10.40.50.30.10.20.5U20.7510.50.250.750.50.750.7500.75U30.570.2810.140.570.5700.280.140.14U40.20.20.210.20.400.200.4U50.570.430.570.1410.570.430.280.140.57U60.630.250.50.250.510.250.130.250.5U70.380.38000.380.2510.130.380.38U80.250.750.50.250.50.250.2510.50.25U90.6600.1700.170.330.50.3310.17U100.630.380.130.250.50.50.380.250.131

圖2 用戶關(guān)系矩陣

把信息熵的閾值設(shè)置為0.5，發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)如圖3所示。

圖3 基于信息熵變化發(fā)現(xiàn)的社

由于不具有出入度的特征，所以不能根據(jù)出度、入度來發(fā)現(xiàn)社區(qū)結(jié)構(gòu)。

相似度計(jì)算方法也是發(fā)現(xiàn)社區(qū)結(jié)構(gòu)的一種常用方法。為便于對比研究，文中選用余弦相似度計(jì)算方法來發(fā)現(xiàn)社區(qū)結(jié)構(gòu)。采用與方法1同樣的數(shù)據(jù)，該方法采用余弦相似度計(jì)算出節(jié)點(diǎn)之間的相似度，并根據(jù)相似度大小發(fā)現(xiàn)社區(qū)結(jié)構(gòu)，如圖4所示。

圖4 基于余弦相似度的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)

從兩種方法發(fā)現(xiàn)的結(jié)果來看，兩種結(jié)果存在一些共同點(diǎn)，也存在一些差異。兩種方法都發(fā)現(xiàn)了U2，U5,U6,U10屬于一個(gè)社區(qū)，方法1發(fā)現(xiàn)U1,U3與U5,U6,U10屬于一個(gè)社區(qū),不同之處在于，方法1發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)是有向圖，方法2發(fā)現(xiàn)的結(jié)構(gòu)是無向圖。在實(shí)際生活中，有向圖顯然具有更好的科學(xué)性，描述的信息更準(zhǔn)確。如圖3中，U5到U6有一條有向邊，而U6到U5沒有有向邊。本實(shí)驗(yàn)中，如果U5發(fā)生，U6發(fā)生的概率為0.57，圖3無法描述這些信息。所以方法1具有較大的優(yōu)越性。方法2之所以沒有發(fā)現(xiàn)U1,U3,是因?yàn)楸舜酥g相似度較低，而方法1計(jì)算的是彼此之間的概率，所以被發(fā)現(xiàn)的可能性較大。

從兩種方法對比來看，方法1能夠發(fā)現(xiàn)更有價(jià)值的社區(qū)結(jié)果，同時(shí)對成員之間的關(guān)系進(jìn)行描述，方法2不能做到這點(diǎn)。

5 結(jié)束語

提出的方法既能發(fā)現(xiàn)社區(qū)結(jié)構(gòu)，也能發(fā)現(xiàn)社區(qū)內(nèi)成員之間的動(dòng)態(tài)模糊關(guān)系，這里用貝葉斯概率來描述成員之間的關(guān)系，采用了信息熵變化趨勢來發(fā)掘社區(qū)成員。現(xiàn)實(shí)中，社區(qū)成員之間的關(guān)系有很多，如關(guān)聯(lián)關(guān)系、因果關(guān)系、相反關(guān)系等，深入發(fā)掘這些關(guān)系并用于個(gè)性化推薦系統(tǒng)尤為重要。文中只用余弦相似度進(jìn)行了對比，對該方法進(jìn)行了改進(jìn)，還需要與其他相似度計(jì)算方法進(jìn)行對比。所用的樣本記錄遠(yuǎn)稱不上大數(shù)據(jù)，在大數(shù)據(jù)環(huán)境下該方法表現(xiàn)如何有待進(jìn)一步探索。根據(jù)熵的變化判斷成員是否屬于一個(gè)社區(qū)，熵閾值確定很重要，如何確定更好的閾值，使得發(fā)現(xiàn)的結(jié)果有更好的可用性，也是目前所有社區(qū)發(fā)現(xiàn)方法面臨的問題。