王童童　李盛恩　王　剛

(山東建筑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院　山東 濟(jì)南 250101)

?

基于社交網(wǎng)絡(luò)節(jié)點(diǎn)中心度挖掘其社區(qū)框架

王童童李盛恩王剛

(山東建筑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院山東 濟(jì)南 250101)

摘要社區(qū)結(jié)構(gòu)作為真實(shí)復(fù)雜網(wǎng)絡(luò)所普遍具有的一個(gè)重要的拓?fù)涮匦裕罱?0年內(nèi)得到了廣泛而深入的研究。為解決社區(qū)挖掘策略時(shí)間復(fù)雜度過高、缺少與用戶交互等問題，討論了社交網(wǎng)絡(luò)節(jié)點(diǎn)中心度、度的冪律分布等特性，提出了“關(guān)鍵子網(wǎng)絡(luò)”和“社區(qū)框架”的概念，設(shè)計(jì)了社區(qū)框架挖掘算法MCF(Mine the Community Framework)和社區(qū)框架鉆取算法DCF(Drill Down the Community Framework)，其中MCF算法用于挖掘社交網(wǎng)絡(luò)的社區(qū)框架，DCF用于對(duì)社區(qū)框架進(jìn)行鉆取，從不同粒度展現(xiàn)社區(qū)結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果和實(shí)驗(yàn)分析表明，MCF算法能夠在較短時(shí)間內(nèi)挖掘出反映復(fù)雜網(wǎng)絡(luò)社區(qū)狀態(tài)的社區(qū)框架，DCF算法可以以用戶交互方式實(shí)現(xiàn)高質(zhì)量的社區(qū)劃分。

關(guān)鍵詞社交網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)節(jié)點(diǎn)中心度社區(qū)框架社區(qū)質(zhì)量

0引言

真實(shí)世界中的許多復(fù)雜系統(tǒng)可以表示成圖或者網(wǎng)絡(luò)，包括社交網(wǎng)絡(luò)、信息網(wǎng)絡(luò)、生物網(wǎng)絡(luò)和技術(shù)網(wǎng)絡(luò)等[1]。經(jīng)驗(yàn)分析表明，這些復(fù)雜網(wǎng)絡(luò)往往是由若干個(gè)節(jié)點(diǎn)組構(gòu)成，節(jié)點(diǎn)組內(nèi)部的連接相對(duì)緊密，而節(jié)點(diǎn)組之間的連接卻相對(duì)比較稀疏。我們稱網(wǎng)絡(luò)的這種拓?fù)涮匦詾樯鐓^(qū)結(jié)構(gòu)，相應(yīng)地，每個(gè)節(jié)點(diǎn)組被稱為一個(gè)社區(qū)。不同的應(yīng)用領(lǐng)域，社區(qū)結(jié)構(gòu)具有不同的內(nèi)涵。比如，社交網(wǎng)絡(luò)中一個(gè)社區(qū)代表了具有相似特征的人群；生物網(wǎng)絡(luò)中的社區(qū)解釋了具有相似功能的生物組織模塊；Web網(wǎng)絡(luò)中的文檔類簇包含了大量的具有相關(guān)主題的Web文檔等[2]。社區(qū)挖掘就是對(duì)這些不同類型復(fù)雜網(wǎng)絡(luò)進(jìn)行處理，挖掘出社區(qū)結(jié)構(gòu)，從而來幫助人們理解復(fù)雜網(wǎng)絡(luò)的功能，發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中隱藏的規(guī)律和預(yù)測(cè)復(fù)雜網(wǎng)絡(luò)的行為[3]。

雖然現(xiàn)在發(fā)展出了大量的社區(qū)挖掘策略，例如GN算法[4]、譜分解算法[5]等，然而這些社區(qū)挖掘算法大部分都是直接針對(duì)完整社交網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行社區(qū)挖掘。例如GN需要反復(fù)計(jì)算整個(gè)網(wǎng)絡(luò)的任意兩點(diǎn)的最短路徑，譜分解算法需要將每一個(gè)節(jié)點(diǎn)在向量空間中加以表示。這樣的處理策略還存在不足之處：首先，使用社區(qū)挖掘策略對(duì)一個(gè)很大的社交網(wǎng)絡(luò)進(jìn)行社區(qū)挖掘需要大量的計(jì)算，計(jì)算時(shí)間長(zhǎng)，例如GN算法時(shí)間復(fù)雜度為O(n2m)，譜分解算法為O(n2)，其中n為節(jié)點(diǎn)個(gè)數(shù)，m為邊的條數(shù)；其次，即使挖掘出社區(qū)結(jié)構(gòu)，這個(gè)社區(qū)結(jié)構(gòu)將涉及所有點(diǎn)的信息，社區(qū)結(jié)構(gòu)過于復(fù)雜；最后，這些社區(qū)挖掘策略在設(shè)置完初始參數(shù)后，就開始計(jì)算，然后返回給用戶整個(gè)網(wǎng)絡(luò)的社區(qū)劃分，計(jì)算過程中，用戶不能進(jìn)行控制，缺乏交互。

文獻(xiàn)[6,7]指出在社交網(wǎng)絡(luò)中存在少部分的節(jié)點(diǎn)中心度較高的節(jié)點(diǎn)，其構(gòu)成的子網(wǎng)絡(luò)能夠反映整個(gè)社交網(wǎng)絡(luò)的拓?fù)涮匦?。為了能夠快速?duì)社交網(wǎng)絡(luò)進(jìn)行社區(qū)挖掘，并且讓用戶能夠控制挖掘的粒度，受其啟發(fā)我們提出了關(guān)鍵子網(wǎng)絡(luò)的概念，進(jìn)而提出了MCF算法和DCF算法。MCF算法利用社交網(wǎng)絡(luò)的節(jié)點(diǎn)中心度提取出社交網(wǎng)絡(luò)的關(guān)鍵子網(wǎng)絡(luò)，關(guān)鍵子網(wǎng)絡(luò)的結(jié)點(diǎn)數(shù)和邊數(shù)遠(yuǎn)小于原社交網(wǎng)絡(luò)，同時(shí)保持了原社交網(wǎng)絡(luò)的拓?fù)涮匦浴Ｈ缓罄媒?jīng)典的挖掘算法對(duì)關(guān)鍵子網(wǎng)絡(luò)進(jìn)行社區(qū)挖掘，將獲得的社區(qū)框架作為整個(gè)社交網(wǎng)絡(luò)的社區(qū)概況，這樣可以在很大程度上減少計(jì)算量，縮短計(jì)算時(shí)間。用戶如果想獲得社區(qū)結(jié)構(gòu)的更詳細(xì)信息，可使用DCF算法對(duì)社區(qū)框架添加一些節(jié)點(diǎn)。然后再進(jìn)行計(jì)算，這樣在用戶的控制下，逐步得到整個(gè)社交網(wǎng)絡(luò)的社區(qū)劃分，這種挖掘方式類似于在商務(wù)智能領(lǐng)域獲得成功的OLAP中的下鉆操作。

1社交網(wǎng)絡(luò)與社區(qū)結(jié)構(gòu)

社交網(wǎng)用無向圖G(V,E)來表示，其中V表示參與社交網(wǎng)絡(luò)的參與者，E表示參與者之間的關(guān)系。對(duì)于一個(gè)無向圖，在計(jì)算機(jī)中我們可以使用鄰接矩陣來表示：

(1)

從鄰接矩陣A可知，如果節(jié)點(diǎn)i和節(jié)點(diǎn)j之間存在聯(lián)系，則Aij與Aji都為1，否則都為0，所以鄰接矩陣A是一個(gè)對(duì)稱矩陣。若求得了一個(gè)社交網(wǎng)絡(luò)的鄰接矩陣A，就能夠很容易計(jì)算出每個(gè)節(jié)點(diǎn)的度：設(shè)定 1n是一個(gè)n維并且每一個(gè)元素都為1的列向量，則度向量K=A·1n指明了每一個(gè)節(jié)點(diǎn)的度，其中Ki為節(jié)點(diǎn)i的度。

隨著對(duì)各種網(wǎng)絡(luò)的深入研究，發(fā)現(xiàn)許多實(shí)際網(wǎng)絡(luò)都存在社區(qū)結(jié)構(gòu)，Newman等人給出了社交網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的定義：社區(qū)是社交網(wǎng)絡(luò)中的子網(wǎng)絡(luò)，子網(wǎng)絡(luò)內(nèi)部聯(lián)系緊密，子網(wǎng)絡(luò)之間聯(lián)系稀疏[8]。如圖1的社交網(wǎng)絡(luò)體現(xiàn)了①②③三個(gè)社區(qū)，通過觀察能夠發(fā)現(xiàn)，在社區(qū)內(nèi)部邊的密度要大于社區(qū)之間邊密度。

圖1　社區(qū)結(jié)構(gòu)示意圖[8]

社交網(wǎng)絡(luò)的一個(gè)社區(qū)，往往反映了在這個(gè)社交網(wǎng)絡(luò)中，具有共同興趣愛好，或者其他共同特性的一群個(gè)體。通過研究社交網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)我們能夠了解社交網(wǎng)絡(luò)的深層結(jié)構(gòu)，及其內(nèi)部錯(cuò)綜復(fù)雜的關(guān)系。為此發(fā)展出了很多的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)策略，基于其原理可分為基于劃分的、基于模塊性優(yōu)化、基于標(biāo)簽傳播、基于動(dòng)力學(xué)和基于仿生計(jì)算的方法等[9]。

然而對(duì)于同一個(gè)社交網(wǎng)絡(luò)我們應(yīng)用不同的社區(qū)劃分方法會(huì)得到不同的社區(qū)劃分，即使使用相同的社區(qū)挖掘策略有時(shí)也會(huì)得到不同的社區(qū)劃分，為了衡量對(duì)一個(gè)網(wǎng)絡(luò)社區(qū)劃分的好壞，基于社區(qū)內(nèi)部聯(lián)系緊密社區(qū)之間聯(lián)系稀疏的思想，Newman和Girvan提出了著名的模塊度函數(shù)即Q函數(shù)[10]。其定義為：

假定社交網(wǎng)絡(luò)被某種挖掘策略分解成n個(gè)社區(qū)，定義一個(gè)n×n的對(duì)稱矩陣E=(eij)。其中eij表示社交網(wǎng)絡(luò)中位于社區(qū)i和社區(qū)j之間的邊數(shù)占總邊數(shù)的比例；E中對(duì)角線上的元素之和稱為該矩陣的跡，即：Tre=∑ieii，它表示社交網(wǎng)絡(luò)中位于社區(qū)內(nèi)部的邊數(shù)占總邊數(shù)的比例；定義矩陣E中每行或者每列中各個(gè)元素之和為ai=∑eij，它所表示社交網(wǎng)絡(luò)中與第i個(gè)社區(qū)中節(jié)點(diǎn)相連的邊在所有邊中所占的比例。在此基礎(chǔ)上定義網(wǎng)絡(luò)劃分的模塊度為：

式中‖e2‖表示矩陣e2中所有元素之和。Tre表示網(wǎng)絡(luò)中位于社區(qū)內(nèi)部邊數(shù)所占圖中總邊數(shù)的比例，‖e2‖表示社區(qū)內(nèi)部邊數(shù)所占總邊數(shù)比例的期望。如果社區(qū)內(nèi)部邊數(shù)的比例不大于任意連接時(shí)的期望值則Q=0。Q的最大值為1，Q越接近1，則說明網(wǎng)絡(luò)的社區(qū)劃分的質(zhì)量越好，即社區(qū)內(nèi)部聯(lián)系越緊密。在實(shí)際網(wǎng)絡(luò)中該值通常位于0.3到0.7之間。

模塊度函數(shù)表示在節(jié)點(diǎn)上的式子為：

(2)

其中P為社區(qū)挖掘算法所發(fā)現(xiàn)的社區(qū)的集合，m為社交網(wǎng)絡(luò)中邊的條數(shù)。若節(jié)點(diǎn)i和j其度分別為ki與kj，則(ki×kj)/2m計(jì)算了兩節(jié)點(diǎn)之間有邊的概率，因此公式中減數(shù)部分計(jì)算了社區(qū)內(nèi)部邊的條數(shù)的期望。

2社區(qū)框架的挖掘及鉆取

現(xiàn)實(shí)世界中，我們發(fā)現(xiàn)每一個(gè)社區(qū)中都有很多在該社區(qū)中具有重要地位的焦點(diǎn)人物，他們管理組織社區(qū)并經(jīng)常與其他社區(qū)的參與者互動(dòng)。通過對(duì)這些重要參與者的社區(qū)考察，我們能夠總結(jié)出整個(gè)網(wǎng)絡(luò)的社區(qū)狀態(tài)。例如在合著網(wǎng)絡(luò)中，每一個(gè)領(lǐng)域都有很多頂尖學(xué)者，可以將這些學(xué)者提取出來構(gòu)成一個(gè)網(wǎng)絡(luò)來對(duì)其進(jìn)行社區(qū)劃分，用以反映整個(gè)網(wǎng)絡(luò)的社區(qū)狀態(tài)。我們提取的由重要參與者構(gòu)成的網(wǎng)絡(luò)叫做原社交網(wǎng)絡(luò)的關(guān)鍵子網(wǎng)絡(luò)，其社區(qū)劃分稱之為社區(qū)框架。當(dāng)想獲得更多社區(qū)細(xì)節(jié)時(shí)，我們可以向社區(qū)框架中添加節(jié)點(diǎn)進(jìn)行鉆取。

2.1節(jié)點(diǎn)中心度

中心度就是用來評(píng)價(jià)一個(gè)社交網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的概念。它是關(guān)于參與者在社交網(wǎng)絡(luò)中的中心型位置的測(cè)量概念，反映的是不同參與者在社交網(wǎng)絡(luò)中位置或者優(yōu)勢(shì)的差異[6]。現(xiàn)在已經(jīng)存在很多對(duì)社交網(wǎng)絡(luò)中心度進(jìn)行測(cè)量的方法，有些側(cè)重于局部的參與者，如局部點(diǎn)中心度；有些側(cè)重整體網(wǎng)絡(luò)結(jié)構(gòu)，如總體中心度。局部點(diǎn)中心度簡(jiǎn)稱為點(diǎn)中心度，其所反映的是某個(gè)節(jié)點(diǎn)的關(guān)系的集中程度，或者是說一個(gè)參與者在社會(huì)網(wǎng)絡(luò)中的主導(dǎo)情況，點(diǎn)中心度越大，此參與者越居于中心位置。總體中心度指的是某節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)中與其他各個(gè)節(jié)點(diǎn)的距離，它所反映的是各個(gè)參與者之間的關(guān)系密切程度，通常使用節(jié)點(diǎn)之間的最短路徑來進(jìn)行衡量。本文主要關(guān)注的是某參與者的局部主導(dǎo)性，因此我們將采用節(jié)點(diǎn)中心度作為衡量其重要性的標(biāo)準(zhǔn)。

由于核心節(jié)點(diǎn)處于社交網(wǎng)絡(luò)關(guān)系中的核心位置，與很多節(jié)點(diǎn)存在多種形式的直接連接，所以可以運(yùn)用社交網(wǎng)絡(luò)中各節(jié)點(diǎn)的度數(shù)，對(duì)節(jié)點(diǎn)的節(jié)點(diǎn)中心度做最簡(jiǎn)單的測(cè)量。我們可以通過下面的公式對(duì)任意節(jié)點(diǎn)i的節(jié)點(diǎn)中心度進(jìn)行計(jì)算：

(3)

節(jié)點(diǎn)的節(jié)點(diǎn)中心度越大，代表其越是該網(wǎng)絡(luò)的核心節(jié)點(diǎn)。

2.2度的冪率分布

19世紀(jì)，著名的經(jīng)濟(jì)學(xué)家Pareto在研究了個(gè)人財(cái)富的統(tǒng)計(jì)分布后，提出了著名的帕累托定律(20/80法則)，即80%的社會(huì)財(cái)富僅僅掌握在20%的人手中。個(gè)人財(cái)富值X不小于某個(gè)特定數(shù)值x的概率與x的常數(shù)次冪存在著反比關(guān)系：

P(X≤x)～k-γ

(4)

1932年，哈佛大學(xué)的語言學(xué)家Zifi發(fā)現(xiàn)如果將單詞出現(xiàn)的頻率按照由小到大的順序進(jìn)行排列，則每個(gè)單詞出現(xiàn)的頻率和其序號(hào)存在著類似于帕累托定律的分布：P(k)～k-γ，這就是著名的Zifi分布。在社交網(wǎng)絡(luò)、萬維網(wǎng)、以及新陳代謝網(wǎng)絡(luò)等網(wǎng)絡(luò)中度的分布同樣具有這種冪律分布特性P(k)～k-γ(通常2≤γ≤3)[7]，其中P(k)為度數(shù)為k的節(jié)點(diǎn)占總節(jié)點(diǎn)個(gè)數(shù)的比率。例如，好萊塢演員合作網(wǎng)絡(luò)的度分布中γ=2.3；www萬維網(wǎng)的度分布中γ=2.1；美國(guó)西部電力網(wǎng)絡(luò)的度分布中γ=4。

2.3社區(qū)框架的挖掘

(5)

其中函數(shù)max(V)計(jì)算了社交網(wǎng)絡(luò)的最大度數(shù)，Vk為度為k的節(jié)點(diǎn)集合。當(dāng)取得該關(guān)鍵子網(wǎng)絡(luò)后我們可以使用已有社區(qū)挖掘策略對(duì)其進(jìn)行社區(qū)挖掘獲得其社區(qū)劃分，得到的社區(qū)劃分稱之為原社交網(wǎng)絡(luò)的社區(qū)框架。算法描述如算法1。

我們稱算法1為MCF算法，在之后的實(shí)驗(yàn)中驗(yàn)證了該社區(qū)框架能夠反映一個(gè)社交網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)概況，如社交網(wǎng)絡(luò)中每個(gè)社區(qū)的相對(duì)大小，社區(qū)內(nèi)的聯(lián)系緊密程度以及不同社區(qū)之間的聯(lián)系情況。

算法1MCF(G,r)

1.輸入社交網(wǎng)絡(luò)數(shù)據(jù)G，比率r

4.輸出社區(qū)框架P

2.4社區(qū)框架的鉆取

在得到社區(qū)框架后，如果想得到社交網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)更加詳細(xì)的信息，可以對(duì)社區(qū)框架進(jìn)行鉆取，即向社區(qū)框架中添加度數(shù)較小的點(diǎn)。對(duì)于一個(gè)新添加的點(diǎn)，為了判定其屬于社區(qū)框架的哪一個(gè)社區(qū)，需要定義一個(gè)距離函數(shù)來進(jìn)行判斷。一種最簡(jiǎn)單的方式是如果新加入的節(jié)點(diǎn)i與社區(qū)框架中某一社區(qū)p中相連的點(diǎn)有d′個(gè)，則節(jié)點(diǎn)i到社區(qū)的距離為d(i,p)=d′。但是，按其定義如果節(jié)點(diǎn)i與社區(qū)p越遠(yuǎn)，其聯(lián)系越緊密，這與直觀感覺是相互違背的。因此，定義社區(qū)p與節(jié)點(diǎn)i的距離為p中與i相連點(diǎn)的個(gè)數(shù)d′的倒數(shù)，即：

(6)

在對(duì)社區(qū)框架進(jìn)行鉆取時(shí)，首先向社區(qū)框架中添加不屬于社區(qū)框架的，但是度數(shù)相對(duì)于其他節(jié)點(diǎn)最大的節(jié)點(diǎn)集合Vk，即：

Vk={i|i∈V且i?V′且ki=max(V-V′)}

(7)

其中函數(shù)max(V-V′)求得節(jié)點(diǎn)集V-V′中節(jié)點(diǎn)的最大度數(shù)。Vk添加完成，則新產(chǎn)生的社區(qū)框架較原社區(qū)框架包含更多的社區(qū)結(jié)構(gòu)信息。如想獲得社區(qū)結(jié)構(gòu)更進(jìn)一步的信息，則對(duì)社區(qū)框架繼續(xù)添加節(jié)點(diǎn)，最終直至將所有節(jié)點(diǎn)添加進(jìn)去，實(shí)現(xiàn)對(duì)整個(gè)網(wǎng)絡(luò)的社區(qū)劃分，算法描述如算法2。

算法2DCF(P)

1.輸入待下鉆社區(qū)框架P

2.求得并添加節(jié)點(diǎn)集Vk

(1)對(duì)Vk中的每一個(gè)節(jié)點(diǎn)計(jì)算其到社區(qū)框架中每個(gè)社區(qū)的

距離

(2)將Vk中的每一個(gè)節(jié)點(diǎn)添加到距離其最近的社區(qū)

(3)形成新的社區(qū)框架P′

3.P=P′

4.如果需要進(jìn)一步鉆取則跳轉(zhuǎn)到2繼續(xù)執(zhí)行，否則輸出新的社區(qū)

框架P

我們將以上對(duì)社區(qū)框架進(jìn)行鉆取的算法2稱之為DCF算法。在DCF算法中計(jì)算節(jié)點(diǎn)到社區(qū)的距離并添加到相應(yīng)社區(qū)的時(shí)間復(fù)雜度為O(n)。當(dāng)向社區(qū)框架中加入所有節(jié)點(diǎn)的時(shí)候，便取得了一個(gè)對(duì)整個(gè)社交網(wǎng)絡(luò)的社區(qū)劃分。對(duì)此社區(qū)結(jié)構(gòu)劃分的好壞可以通過Q函數(shù)來進(jìn)行評(píng)價(jià)。

通過使用MCF算法挖掘出社交網(wǎng)絡(luò)的社區(qū)框架，我們能夠在不對(duì)整個(gè)社交網(wǎng)絡(luò)進(jìn)行社區(qū)劃分的情況下獲得其社區(qū)概況，這樣使計(jì)算量大為減小。即使用戶想得到更加詳細(xì)的社區(qū)信息，我們也可以使用DCF算法對(duì)已有的社區(qū)框架進(jìn)行可控鉆取獲得，從而使用戶可以從不同層次對(duì)社區(qū)結(jié)構(gòu)進(jìn)行考察，最終我們能夠?qū)崿F(xiàn)社交網(wǎng)絡(luò)的社區(qū)劃分。下面將通過實(shí)驗(yàn)驗(yàn)證該方法的有效性。

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

3.1實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)使用的數(shù)據(jù)集是netscinece合作網(wǎng)絡(luò)[5]，由Newman于2006年統(tǒng)計(jì)得出，該網(wǎng)絡(luò)描述了來自不同領(lǐng)域的科學(xué)家之間的合作關(guān)系。其中包含了1589個(gè)節(jié)點(diǎn)和2742條邊，如圖2所示，圖中間的黑點(diǎn)部分是由大量的離散點(diǎn)聚集形成。由Newman提出的具有開創(chuàng)性意義的GN社區(qū)挖掘策略具有較高的社區(qū)挖掘精度，并且得到了相關(guān)學(xué)者的廣泛認(rèn)可和應(yīng)用，所以文中將選用其作為相應(yīng)的實(shí)驗(yàn)對(duì)比算法。

我們首先考察生成社區(qū)框架(MCF算法)和實(shí)現(xiàn)下鉆(DCF算法)所需時(shí)間與GN算法所需時(shí)間的對(duì)比情況，分析通過社區(qū)框架下鉆實(shí)現(xiàn)的社區(qū)劃分在劃分效果上與GN算法的對(duì)比情況。然后考察社區(qū)框架能否反映出完整社交網(wǎng)絡(luò)的社區(qū)概況。

圖2　netscience合作網(wǎng)絡(luò)[5]

3.2實(shí)驗(yàn)結(jié)果

圖3展示了在netsicence社交網(wǎng)絡(luò)中節(jié)點(diǎn)的度分布。首先，該社交網(wǎng)絡(luò)中度數(shù)為3的節(jié)點(diǎn)數(shù)量最多，其實(shí)際意義是與三個(gè)人有過合作的學(xué)者最多。其次，該社交網(wǎng)絡(luò)含有少量的度數(shù)比較高的節(jié)點(diǎn)，這些節(jié)點(diǎn)代表了發(fā)表論文比較多且有較高影響力的學(xué)者。從圖中的曲線走勢(shì)我們可以得出該網(wǎng)絡(luò)的節(jié)點(diǎn)度分布基本符合冪律分布的特性。

圖3　netscience節(jié)點(diǎn)度分布

在MCF算法中，我們按0.2的比率提取關(guān)鍵子網(wǎng)絡(luò)G′(V,E)，并對(duì)其進(jìn)行社區(qū)劃分。得到的關(guān)鍵子網(wǎng)絡(luò)含有359個(gè)節(jié)點(diǎn)(占總節(jié)點(diǎn)個(gè)數(shù)的22.59%)，1171條邊(占總邊數(shù)的42.71%)，對(duì)其使用GN算法進(jìn)行社區(qū)劃分得到了7個(gè)大的社區(qū)以及大量的小的社區(qū)，共49個(gè)社區(qū)，如圖4所示。隨后在該社區(qū)框架基礎(chǔ)之上通過使用DCF算法依次添加V4、V3、V2、V1實(shí)現(xiàn)了對(duì)整個(gè)社交網(wǎng)絡(luò)的社區(qū)劃分。

圖4　netscience社區(qū)框架

表1給出了MCF算法、DCF算法以及使用GN算法直接對(duì)整個(gè)社交網(wǎng)絡(luò)進(jìn)行社區(qū)劃分所需時(shí)間的對(duì)比情況。通過表1能夠發(fā)現(xiàn)社區(qū)框架的挖掘所需時(shí)間僅為GN算法所需時(shí)間的28.1%，對(duì)社區(qū)框架進(jìn)行下鉆所需時(shí)間為GN算法的34%，總的時(shí)間比GN減少40%。

表1　運(yùn)行時(shí)間對(duì)比

表2展示了通過下鉆所得社區(qū)結(jié)構(gòu)與使用GN算法所得社區(qū)結(jié)構(gòu)質(zhì)量在Q函數(shù)上的體現(xiàn)情況。觀察可得GN算法所得到的社區(qū)結(jié)構(gòu)在質(zhì)量方面要略好于通過下鉆所得到的社區(qū)，但是兩者差距并不是很明顯。

表2　社區(qū)質(zhì)量對(duì)比

綜合表1和表2，本文提出的算法可以在較少的時(shí)間上挖掘出一個(gè)社交網(wǎng)絡(luò)的社區(qū)框架，并能夠通過鉆取社區(qū)框架實(shí)現(xiàn)對(duì)整個(gè)網(wǎng)絡(luò)的社區(qū)劃分，而且，社區(qū)結(jié)構(gòu)質(zhì)量接近GN算法所得到的社區(qū)結(jié)構(gòu)質(zhì)量。

下面的實(shí)驗(yàn)通過對(duì)比社區(qū)結(jié)構(gòu)與社區(qū)框架的相關(guān)數(shù)據(jù)，驗(yàn)證了所得到的社區(qū)框架能夠反映整個(gè)網(wǎng)絡(luò)的社區(qū)概況。實(shí)驗(yàn)數(shù)據(jù)中的社區(qū)框架由MCF算獲得，社區(qū)結(jié)構(gòu)由DCF對(duì)社區(qū)框架挖掘獲得。其編號(hào)由程序產(chǎn)生。

圖5展示了社區(qū)結(jié)構(gòu)與社區(qū)框架中對(duì)應(yīng)社區(qū)的成員數(shù)目的對(duì)比情況，從圖中可以看出社區(qū)框架中社區(qū)的相對(duì)大小能夠反映社區(qū)結(jié)構(gòu)相應(yīng)社區(qū)的相對(duì)大小。例如，社區(qū)框架中編號(hào)為3、12、46、49的社區(qū)是相對(duì)較大的社區(qū)，而其對(duì)應(yīng)社區(qū)結(jié)構(gòu)中的社區(qū)也是相應(yīng)的大社區(qū)。

圖5　社區(qū)內(nèi)節(jié)點(diǎn)個(gè)數(shù)對(duì)比

圖6展示了社區(qū)結(jié)構(gòu)與社區(qū)框架的社區(qū)內(nèi)部邊密度對(duì)比情況。所謂的社區(qū)內(nèi)部邊密度指的是社區(qū)內(nèi)部邊的條數(shù)與社區(qū)內(nèi)部點(diǎn)的個(gè)數(shù)的商，其在netscience中的現(xiàn)實(shí)意義是：在社區(qū)內(nèi)部成員之間的合作密切程度，邊密度越大說明社區(qū)成員之間的合作越密切。通過觀察發(fā)現(xiàn)圖中兩條曲線基本吻合的，但是也出現(xiàn)了很多不一致的情況，如社區(qū)21-28，這種不吻合主要是由社區(qū)規(guī)模太小，在統(tǒng)計(jì)上不準(zhǔn)確造成的，通過觀察圖5可以發(fā)現(xiàn)社區(qū)21-28這幾個(gè)社區(qū)的規(guī)模都非常的小。

圖6　社區(qū)內(nèi)部邊密度對(duì)比

圖7展示了49號(hào)社區(qū)與其他社區(qū)之間的聯(lián)系情況，這里僅列出了與之有聯(lián)系的社區(qū)的編號(hào)。通過觀察社區(qū)結(jié)構(gòu)所對(duì)應(yīng)的曲線可知，社區(qū)49與社區(qū)2、22、43、48之間存在聯(lián)系，其中與社區(qū)48的聯(lián)系最為緊密。我們觀察社區(qū)框架同樣能夠得到類似的信息，在社區(qū)框架中社區(qū)49與22、43、48之間存在聯(lián)系，其中與社區(qū)48聯(lián)系最為緊密。

圖7　社區(qū)之間邊的條數(shù)對(duì)比

以上實(shí)驗(yàn)驗(yàn)證了社區(qū)框架能夠反映社交網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)的概況，包括社區(qū)內(nèi)部節(jié)點(diǎn)的相對(duì)多少、社區(qū)內(nèi)部邊的密度、社區(qū)之間的聯(lián)系緊密程度。

4結(jié)語

通過使用MCF算法，我們能夠快速地在不對(duì)整個(gè)社交網(wǎng)絡(luò)進(jìn)行社區(qū)挖掘的情況下了解社區(qū)的概況，并能夠使用DCF算法對(duì)社區(qū)框架進(jìn)行鉆取，最終實(shí)現(xiàn)對(duì)社交網(wǎng)絡(luò)的社區(qū)劃分。最后通過實(shí)驗(yàn)驗(yàn)證了我們所提方案的有效性。然而，我們最終實(shí)現(xiàn)的社區(qū)劃分效果相對(duì)于成熟的GN算法來說還有待提高，同時(shí)我們也發(fā)現(xiàn)，本文所提方案只有應(yīng)用于符合冪律分布的社交網(wǎng)絡(luò)時(shí)，才會(huì)體現(xiàn)出其性能優(yōu)勢(shì)。今后的主要工作是當(dāng)社交網(wǎng)絡(luò)是以加權(quán)有向圖表示時(shí)，如何可控的快速的發(fā)現(xiàn)其社區(qū)結(jié)構(gòu)，同時(shí)如何利用社交網(wǎng)絡(luò)進(jìn)行高效地廣告分發(fā)和流行病控制也是我們感興趣的一個(gè)研究方向。

參考文獻(xiàn)

[1] Burt R S,Kilduff M.Social network analysis:Foundations and frontiers on advantage[J].Annual review of psychology,2013,64(2):527-547.

[2] Fortunato S.Community detection in graphs[J].Physics Reports,2010,486(3):75-174.

[3] 竇炳琳,李澍淞,張世永.基于結(jié)構(gòu)的社會(huì)網(wǎng)絡(luò)分析[J].計(jì)算機(jī)學(xué)報(bào),2012,35(4):741-753.

[4] Girvan M,Newman M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.

[5] Newman M E J.Finding community structure in networks using the eigenvectors of matrices[J].Physical review E,2006,74(3):036104.

[6] Opsahl T,Agneessens F,Skvoretz J.Node centrality in weighted networks:Generalizing degree and shortest paths[J].Social Networks,2010,32(3):245-251.

[7] Barabási A L,Albert R.Emergence of scaling in random networks[J].science,1999,286(5439):509-512.

[8] Newman M E J.The structure and function of complex networks[J].SIAM review,2003,45(2):167-256.

[9] 楊博,劉大有,金弟.復(fù)雜網(wǎng)絡(luò)聚類方法[J].軟件學(xué)報(bào),2009,20(1):54-66.

[10] Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Physical review E,2004,69(2):026113.

收稿日期：2015-01-05。國(guó)家自然科學(xué)基金項(xiàng)目(61170052)。王童童，碩士生，主研領(lǐng)域：社交網(wǎng)絡(luò)，數(shù)據(jù)挖掘。李盛恩，教授。王剛，碩士生。

中圖分類號(hào)TP311.13

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.07.020

MINING COMMUNITY FRAMEWORK BASED ON SOCIAL NETWORKS’ NODE CENTRALITY

Wang TongtongLi Sheng’enWang Gang

(SchoolofComputerScienceandTechnology,ShandongJianzhuUniversity,Jinan250101,Shandong,China)

AbstractAs an important topological characteristic which the real complex networks commonly have, community structure has been widely and thoroughly studied in recent 10 years. To solve the problems of community mining strategy that its time complexity is too high and lacks the interaction with users, etc., we discussed the node centrality, node’s power-law degree distribution and other characteristics of social networks, and proposed the concepts of "critical sub-network" and "community framework". Moreover, we designed the community framework mining (CFM) algorithm and the community framework drilling (CFD) algorithm. Among them, the CFM algorithm is used to mine the community framework of social networks, and CFD is used for drilling the community framework and to demonstrate the community structure from different granularities. Experimental results and analysis showed that, in a relatively short time the CFM algorithm could be used to mine out the community framework reflecting the complex networks community state, while the CFD algorithm could implement high-quality community partition in the way of user interaction.

KeywordsSocial networksCommunity structureNode centralityCommunity frameworkCommunity quality