深圳壓寨網(wǎng)絡(luò)有限公司 王唐云

基于聚類(lèi)算法的社團(tuán)發(fā)現(xiàn)算法研究

深圳壓寨網(wǎng)絡(luò)有限公司 王唐云

互聯(lián)網(wǎng)、云計(jì)算、大數(shù)據(jù)技術(shù)的快速發(fā)展，使人類(lèi)社會(huì)加速進(jìn)入信息化時(shí)代。復(fù)雜網(wǎng)絡(luò)是信息發(fā)展的產(chǎn)物之一，其可以描述人類(lèi)社會(huì)的各種系統(tǒng)，比如電力網(wǎng)絡(luò)、通信網(wǎng)絡(luò)、社交網(wǎng)絡(luò)等，利用復(fù)雜網(wǎng)絡(luò)可以幫助人們分享智慧信息帶帶來(lái)的便捷性，比如Twitter、Facebook、微信、QQ、微博等社團(tuán)應(yīng)用工具促進(jìn)人類(lèi)社交，滿(mǎn)足人們多樣化、興趣化、智能化交友需求。社團(tuán)發(fā)現(xiàn)作為復(fù)雜網(wǎng)絡(luò)處理的重要手段，其可以提高信息利用精準(zhǔn)性。經(jīng)過(guò)多年研究和發(fā)展，社團(tuán)發(fā)現(xiàn)引入了先進(jìn)的聚類(lèi)技術(shù)，采用譜聚類(lèi)、K均值、信息論等多種聚類(lèi)算法，更好的從復(fù)雜網(wǎng)絡(luò)搜尋人們期望的模型和信息，具有重要的作用和意義。

聚類(lèi)算法；社團(tuán)發(fā)現(xiàn)；譜聚類(lèi)；K均值；信息論

1.引言

復(fù)雜網(wǎng)絡(luò)是社會(huì)交際、電力工業(yè)、基因組織等復(fù)雜系統(tǒng)的一個(gè)具體表現(xiàn)形式，復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)可以描述復(fù)雜系統(tǒng)中的實(shí)體，節(jié)點(diǎn)之間的邊可以描述實(shí)體之間的關(guān)系［1］。復(fù)雜網(wǎng)絡(luò)可以描述現(xiàn)實(shí)世界中的許多系統(tǒng)，比如生物系統(tǒng)中的蛋白質(zhì)交互網(wǎng)絡(luò)、神經(jīng)元網(wǎng)絡(luò)、基因調(diào)控網(wǎng)絡(luò)，社會(huì)系統(tǒng)中的人際關(guān)系網(wǎng)絡(luò)、流行病傳播網(wǎng)絡(luò)、科學(xué)家合作網(wǎng)絡(luò)，計(jì)算機(jī)系統(tǒng)中的萬(wàn)維網(wǎng)、電子商務(wù)網(wǎng)、朋友圈網(wǎng)，電力系統(tǒng)中的電力通信網(wǎng)絡(luò)等，復(fù)雜網(wǎng)絡(luò)研究涉及多個(gè)學(xué)科，包括社會(huì)學(xué)、計(jì)算機(jī)學(xué)、心理學(xué)、統(tǒng)計(jì)學(xué)、圖形學(xué)、生物學(xué)等，隨著對(duì)復(fù)雜網(wǎng)絡(luò)的進(jìn)一步研究，在小世界現(xiàn)象和無(wú)標(biāo)度性之后，人們發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)存在另外一個(gè)特性，就是其拓?fù)浣Y(jié)構(gòu)呈現(xiàn)出社團(tuán)結(jié)構(gòu)，也即是復(fù)雜網(wǎng)絡(luò)社團(tuán)之間的聯(lián)系是相對(duì)稀疏的，社團(tuán)內(nèi)部的連接相對(duì)稠密［2］。社團(tuán)發(fā)現(xiàn)可以積極的利用算法尋找復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)，這樣就可以研究整個(gè)網(wǎng)絡(luò)的功能，更好的組織復(fù)雜系統(tǒng)，具有十分重要的意義。

2.社團(tuán)發(fā)現(xiàn)及其應(yīng)用

復(fù)雜網(wǎng)絡(luò)中的社團(tuán)發(fā)現(xiàn)是指在一個(gè)網(wǎng)絡(luò)中，使用某種技術(shù)可以將聯(lián)系較為緊密的節(jié)點(diǎn)劃分為一個(gè)社團(tuán)中，也可以把聯(lián)系較少的節(jié)點(diǎn)劃分為不同的社團(tuán)中，也即是盡可能的保持社團(tuán)內(nèi)部節(jié)點(diǎn)結(jié)構(gòu)緊密和社團(tuán)之間的節(jié)點(diǎn)邏輯獨(dú)立。社團(tuán)發(fā)現(xiàn)可以準(zhǔn)確的揭示復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的組織關(guān)系，比如具有共同的愛(ài)好和興趣，屬于一個(gè)工作種類(lèi)，屬于同一個(gè)省市縣區(qū)域等；社團(tuán)發(fā)現(xiàn)也可以提高網(wǎng)絡(luò)的搜索性能，實(shí)現(xiàn)信息過(guò)濾、追蹤熱點(diǎn)話題、采集和分析網(wǎng)絡(luò)輿情；社團(tuán)發(fā)現(xiàn)也可以發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)系統(tǒng)中相關(guān)的結(jié)構(gòu)單一等［3］。復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)如圖1所示。

圖1 復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)

社團(tuán)應(yīng)用領(lǐng)域非常多，最為常見(jiàn)的應(yīng)用就是社交網(wǎng)絡(luò)、基因組織、客戶(hù)關(guān)系管理等方面。比如，在電子商務(wù)領(lǐng)域，如果根據(jù)每一個(gè)客戶(hù)購(gòu)買(mǎi)同類(lèi)型商品的興趣進(jìn)行劃分和組織，可以很快的識(shí)別出這些客戶(hù)的群體，同時(shí)發(fā)現(xiàn)這些客戶(hù)歸屬的朋友圈，像這些客戶(hù)及其朋友推薦商品，可以更好的提高電商營(yíng)銷(xiāo)的精準(zhǔn)程度，提高電商網(wǎng)站的成交率［4］。

3.基于聚類(lèi)的社團(tuán)發(fā)現(xiàn)算法研究

3.1譜聚類(lèi)算法

社團(tuán)網(wǎng)絡(luò)是一個(gè)圖結(jié)構(gòu)，譜聚類(lèi)算法主要思想來(lái)源與譜圖劃分。假設(shè)G是一個(gè)擁有N個(gè)節(jié)點(diǎn)的復(fù)雜網(wǎng)絡(luò)，則G可以使用一個(gè)N×N的拉普拉斯矩陣L進(jìn)行描述，lii表示矩陣節(jié)點(diǎn)Vi的度，規(guī)定Vi與Vj連通，則lij=-1，否則lij=0，因此矩陣L與鄰接矩陣A的關(guān)系為L(zhǎng)=K-A，矩陣K只能描述對(duì)角線節(jié)點(diǎn)對(duì)應(yīng)的連通度值，其余元素規(guī)定為0.由于矩陣L每一行或每一列元素之和均為0，則L存在一個(gè)零特征值和一個(gè)全為1的特征向量。如果G可以被劃分為M個(gè)費(fèi)重疊社團(tuán)Gm，則這些社團(tuán)之間不存在連接，則網(wǎng)絡(luò)G的拉普拉斯矩陣可以劃分為M個(gè)對(duì)角矩陣，每一個(gè)對(duì)角矩陣表示一個(gè)社團(tuán)。

3.2K均值算法

K均值也是社團(tuán)發(fā)現(xiàn)常用的算法，其可以將復(fù)雜網(wǎng)絡(luò)建模為一個(gè)矩陣S，假設(shè)該矩陣包括了h個(gè)社團(tuán)，首先初始化矩陣S的m個(gè)特征值為社團(tuán)的核心節(jié)點(diǎn)，也即是聚類(lèi)中心，則h個(gè)社團(tuán)的K均值算法矩陣如公式（1）所示：

在K均值算法聚類(lèi)執(zhí)行過(guò)程中，可以設(shè)置不同的特征權(quán)重，一般能夠優(yōu)化突出較為重要的特征貢獻(xiàn)，特征權(quán)重向量如公式（2）所示：

通過(guò)分析，K均值聚類(lèi)的目標(biāo)函數(shù)如公式（3）所示：

在復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)過(guò)程中，K均值算法可以迭代執(zhí)行，直到獲取最優(yōu)解或次優(yōu)解，滿(mǎn)足人們的需求。

圖2 社團(tuán)發(fā)現(xiàn)原理

3.3信息論算法

假設(shè)復(fù)雜網(wǎng)絡(luò)X包含T個(gè)社團(tuán)，每一個(gè)社團(tuán)都存在Y個(gè)相關(guān)變量進(jìn)行度量，因此社團(tuán)發(fā)現(xiàn)可以使用信息論進(jìn)行形式化描述：給定變量X和相關(guān)變量Y及其聯(lián)合概率分布P（X，Y），在將變量X中的節(jié)點(diǎn)壓縮到T個(gè)社團(tuán)中時(shí)，需要盡可能的保存相關(guān)變量Y的信息，也即是盡可能的最小化互信息I（X；T）且最大化保存互信息I（Y；T），社團(tuán)發(fā)現(xiàn)過(guò)程如圖2所示。

利用互信息開(kāi)展社團(tuán)發(fā)現(xiàn)的目標(biāo)函數(shù)可以設(shè)置為公式（4）。

4.結(jié)束語(yǔ)

社團(tuán)發(fā)現(xiàn)可以有效處理復(fù)雜網(wǎng)絡(luò)信息，尋求人們期望的知識(shí)。社團(tuán)發(fā)現(xiàn)已經(jīng)在電子商務(wù)推薦系統(tǒng)、社交網(wǎng)絡(luò)服務(wù)系統(tǒng)、輿情信息研判分析系統(tǒng)中得到廣泛普及和使用，利用聚類(lèi)算法可以提高這些系統(tǒng)的準(zhǔn)確度，為人們提供更好的服務(wù)。

［1］黃健斌，孫鶴立，Dustin BORTNER，等.從鏈接密度遍歷序列中挖掘網(wǎng)絡(luò)社團(tuán)的層次結(jié)構(gòu)［J］.軟件學(xué)報(bào)，2011，22（5）：951-961.

［2］賈宗維，崔軍.一種發(fā)現(xiàn)社團(tuán)結(jié)構(gòu)的快速凝聚聚類(lèi)算法［J］.湘潭大學(xué)自然科學(xué)學(xué)報(bào)，2012，34（4）：103-107.

［3］董哲，伊鵬.采用鏈路聚類(lèi)的動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法［J］.西安交通大學(xué)學(xué)報(bào)，2014，48（8）：73-79.

［4］付立東.核k-means聚類(lèi)檢測(cè)復(fù)雜網(wǎng)絡(luò)社團(tuán)算法［J］.計(jì)算機(jī)科學(xué)，2010，37（9）：212-213.一化函數(shù)。從解空間的定義看以得出，目標(biāo)函數(shù)的具有一個(gè)形式解，如果想得到具體的解，還需要借助具體的算法等。