印世樂

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

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

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2014）22-5301-02

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

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

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

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

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

1.1 Peer pressure 聚類

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

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

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

如下所示算法表示了pressure clustering 的迭代定義。同樣的，這個算法也能用循環(huán)表示通過保存當前的和前一次近似聚類，如果相等則跳出循環(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為一到頂點個數(shù)即n的向量。

2） 計算出每個頂點對其鄰接頂點出度所占比例，記為T矩陣。

3） 求出每個頂點中對其出度貢獻最大的頂點，并賦值為當前頂點，改變后的近似聚類記為C1。

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

2 試驗與分析

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

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

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

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

參考文獻：

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

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

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

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