印世樂(lè)

摘要：社區(qū)有助于揭示復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)和個(gè)體間的關(guān)系。研究人員從不同視角提出很多社區(qū)發(fā)現(xiàn)方法，用來(lái)識(shí)別團(tuán)內(nèi)緊密、團(tuán)間稀疏的網(wǎng)絡(luò)結(jié)構(gòu)。該文將Peer pressure 算法應(yīng)用于社區(qū)發(fā)現(xiàn)的研究當(dāng)中，介紹了Peer pressure 算法的步驟和社區(qū)發(fā)現(xiàn)的過(guò)程，最后進(jìn)行了聚類模型的演示。

關(guān)鍵詞：Peer pressure算法；社區(qū)發(fā)現(xiàn)；網(wǎng)絡(luò)圖

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）22-5301-02

在現(xiàn)實(shí)世界中，多種系統(tǒng)都通過(guò)網(wǎng)絡(luò)結(jié)構(gòu)的形式展現(xiàn)出來(lái)，如社會(huì)系統(tǒng)中的人際關(guān)系網(wǎng)、電話網(wǎng)、蛋白質(zhì)交互網(wǎng)、文獻(xiàn)引用網(wǎng)絡(luò)等。這些網(wǎng)絡(luò)具有很高的復(fù)雜性又被稱為復(fù)雜網(wǎng)絡(luò)（Complex Network） 。復(fù)雜網(wǎng)絡(luò)已經(jīng)在多個(gè)領(lǐng)域廣泛應(yīng)用，是重要的多學(xué)科交叉研究領(lǐng)域之一。復(fù)雜網(wǎng)絡(luò)以節(jié)點(diǎn)抽象為實(shí)體，邊抽象為實(shí)體間各種聯(lián)系。社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的一個(gè)特例，其特性已經(jīng)引起廣泛的關(guān)注。其網(wǎng)絡(luò)結(jié)構(gòu)由若干個(gè)社區(qū)組成，各個(gè)社區(qū)之間具有明顯的聯(lián)系稀疏度，相同社區(qū)聯(lián)系緊密而不同社區(qū)聯(lián)系相對(duì)稀疏。社區(qū)發(fā)現(xiàn)的研究對(duì)于深入了解網(wǎng)絡(luò)結(jié)構(gòu)與分析網(wǎng)絡(luò)特征具有有重要意義。

在過(guò)去幾年中，已經(jīng)產(chǎn)生了大量的社區(qū)發(fā)現(xiàn)算法。如Kernighan-Lin 算法極小化簇間連接數(shù)目與簇內(nèi)連接數(shù)目之差，GN 算法的規(guī)則則是簇間連接的邊介數(shù)大于簇內(nèi)連接的邊介數(shù)。

但以這上些方法均需要預(yù)先估計(jì)社區(qū)數(shù)目，進(jìn)行參數(shù)的設(shè)定，如K（社區(qū)個(gè)數(shù)）等。該文提出一種基于Peer pressure算法的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)的聚類方法。該算法不需要任何的參數(shù)設(shè)定。

1 基于Peer pressure的社區(qū)發(fā)現(xiàn)

由于社區(qū)結(jié)構(gòu)一般都表示成復(fù)雜網(wǎng)絡(luò)圖，故對(duì)社區(qū)結(jié)構(gòu)聚類就是對(duì)一個(gè)網(wǎng)絡(luò)圖進(jìn)行聚類。圖聚類是圖結(jié)構(gòu)分類的無(wú)監(jiān)督學(xué)習(xí)過(guò)程，簡(jiǎn)單地說(shuō)，對(duì)圖進(jìn)行聚類就是要把圖中相對(duì)連接緊密的結(jié)點(diǎn)及其相關(guān)的邊分組形成一個(gè)子圖，子圖內(nèi)各結(jié)點(diǎn)具有較高的連接度，而子圖之間各結(jié)點(diǎn)的連接度則相對(duì)較低。

1.1 Peer pressure 聚類

Peer pressure聚類利用一個(gè)給定的事實(shí)：于一個(gè)近似的圖的任何一個(gè)合適的聚類，頂點(diǎn)的聚類任務(wù)和它主要的相鄰頂點(diǎn)聚類是相似的。如圖1所示，除了頂點(diǎn)4以外，所有的頂點(diǎn)都在合適的聚類中。

如果圖1中每個(gè)頂點(diǎn)的入度邊被驗(yàn)證是這個(gè)圖起源的聚類，那么這個(gè)聚類能被認(rèn)為是次優(yōu)的。除了頂點(diǎn)4外，在各自類別中所有的頂點(diǎn)都有最大的入度邊。另外，如果頂點(diǎn)4調(diào)整到紅色聚類里面，那么這個(gè)聚類可以被看成是最優(yōu)的。每個(gè)頂點(diǎn)都有從自身所在聚類中的主要入度邊。如圖2所示。

傳統(tǒng)上，peer pressure聚類是通過(guò)圖的近似迭代產(chǎn)生。通過(guò)給定一個(gè)近似聚類， 在這個(gè)聚類中，每個(gè)頂點(diǎn)對(duì)它所有的鄰接點(diǎn)進(jìn)行第一次投票。統(tǒng)計(jì)這些投票，通過(guò)他們獲得的最多的投票來(lái)移動(dòng)頂點(diǎn)，從而產(chǎn)生一個(gè)新的近似聚類。通過(guò)這樣的不斷迭代從確定每個(gè)頂點(diǎn)所在的類，通常是連續(xù)的產(chǎn)生兩個(gè)相同的近似聚類。

如下所示算法表示了pressure clustering 的迭代定義。同樣的，這個(gè)算法也能用循環(huán)表示通過(guò)保存當(dāng)前的和前一次近似聚類，如果相等則跳出循環(huán)。

1.2 社區(qū)發(fā)現(xiàn)建模

基于Peer pressure 算法的社區(qū)發(fā)現(xiàn)模型從網(wǎng)絡(luò)圖出發(fā)，使用引文關(guān)系作為子圖分割的依據(jù)。Peer pressure 算法的思想如下：

1） 文章引用圖抽象為鄰接矩陣V輸入matlab中，并初始化向量C為一到頂點(diǎn)個(gè)數(shù)即n的向量。

2） 計(jì)算出每個(gè)頂點(diǎn)對(duì)其鄰接頂點(diǎn)出度所占比例，記為T矩陣。

3） 求出每個(gè)頂點(diǎn)中對(duì)其出度貢獻(xiàn)最大的頂點(diǎn)，并賦值為當(dāng)前頂點(diǎn)，改變后的近似聚類記為C1。

4） 重復(fù)2、3步，看C1是否發(fā)生變化。不變則迭代結(jié)束，輸出C1，否則繼續(xù)進(jìn)行迭代。

2 試驗(yàn)與分析

為了演示該社區(qū)發(fā)現(xiàn)模型，從新浪微博中抓取、篩選和過(guò)濾若干用戶，這些用戶分別關(guān)注了以下四個(gè)種類的話題：體育類、財(cái)經(jīng)類、軍事類、飲食類，根據(jù)他們的關(guān)注關(guān)系構(gòu)建了圖3 所示的復(fù)雜圖，嘗試通過(guò)Peer pressure 算法進(jìn)行聚類。

如圖4所示，該算法經(jīng)過(guò)三次迭代算出計(jì)算結(jié)果，最終的結(jié)果為節(jié)點(diǎn)1、節(jié)點(diǎn)3、節(jié)點(diǎn)5、節(jié)點(diǎn)7聚為一類，節(jié)點(diǎn)2、節(jié)點(diǎn)4、節(jié)點(diǎn)6、節(jié)點(diǎn)8聚為一類，節(jié)點(diǎn)10、節(jié)點(diǎn)12、節(jié)點(diǎn)16聚為一類，節(jié)點(diǎn)9、節(jié)點(diǎn)14聚為一類，節(jié)點(diǎn)11、節(jié)點(diǎn)13、節(jié)點(diǎn)15聚為一類，一共聚出5類。

真實(shí)的社區(qū)結(jié)構(gòu)是節(jié)點(diǎn)9、節(jié)點(diǎn)11、節(jié)點(diǎn)13、節(jié)點(diǎn)14和節(jié)點(diǎn)15在一個(gè)社區(qū)，其余的社區(qū)結(jié)構(gòu)都分析對(duì)了。由此可見(jiàn)該算法基本上可以正確地劃分社區(qū)網(wǎng)絡(luò)。

這種基于過(guò)Peer pressure 算法的社區(qū)發(fā)現(xiàn)方法，不需要任何參數(shù)的設(shè)置，可以自動(dòng)識(shí)別社區(qū)數(shù)目。實(shí)驗(yàn)結(jié)果表明，該算法能夠比較準(zhǔn)確的識(shí)別網(wǎng)絡(luò)中的社區(qū)，具有一定的研究及使用價(jià)值。

參考文獻(xiàn)：

[1] 楊楠.Web社區(qū)發(fā)現(xiàn)技術(shù)綜述[J].計(jì)算機(jī)研究與發(fā)展，2005（4）.

[2] 楊柳.基于無(wú)偏Q值反饋的社區(qū)劃分算法[J].東南大學(xué)學(xué)報(bào)：自然科學(xué)版，2011（1）.

[3] 胡健，鄧志娟.一種新型簡(jiǎn)單圖社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法[J].計(jì)算機(jī)工程與應(yīng)用，2009（5）.

[4] 謝鋒.基于GN算法的文獻(xiàn)聚類研究[J].信息科技，2013（1）.