王童童　李盛恩　王　剛

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

?

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

王童童李盛恩王剛

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

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

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

0引言

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

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

文獻[6,7]指出在社交網(wǎng)絡(luò)中存在少部分的節(jié)點中心度較高的節(jié)點，其構(gòu)成的子網(wǎng)絡(luò)能夠反映整個社交網(wǎng)絡(luò)的拓撲特性。為了能夠快速對社交網(wǎng)絡(luò)進行社區(qū)挖掘，并且讓用戶能夠控制挖掘的粒度，受其啟發(fā)我們提出了關(guān)鍵子網(wǎng)絡(luò)的概念，進而提出了MCF算法和DCF算法。MCF算法利用社交網(wǎng)絡(luò)的節(jié)點中心度提取出社交網(wǎng)絡(luò)的關(guān)鍵子網(wǎng)絡(luò)，關(guān)鍵子網(wǎng)絡(luò)的結(jié)點數(shù)和邊數(shù)遠小于原社交網(wǎng)絡(luò)，同時保持了原社交網(wǎng)絡(luò)的拓撲特性。然后利用經(jīng)典的挖掘算法對關(guān)鍵子網(wǎng)絡(luò)進行社區(qū)挖掘，將獲得的社區(qū)框架作為整個社交網(wǎng)絡(luò)的社區(qū)概況，這樣可以在很大程度上減少計算量，縮短計算時間。用戶如果想獲得社區(qū)結(jié)構(gòu)的更詳細信息，可使用DCF算法對社區(qū)框架添加一些節(jié)點。然后再進行計算，這樣在用戶的控制下，逐步得到整個社交網(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)系。對于一個無向圖，在計算機中我們可以使用鄰接矩陣來表示：

(1)

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

隨著對各種網(wǎng)絡(luò)的深入研究，發(fā)現(xiàn)許多實際網(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)了①②③三個社區(qū)，通過觀察能夠發(fā)現(xiàn)，在社區(qū)內(nèi)部邊的密度要大于社區(qū)之間邊密度。

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

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

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

假定社交網(wǎng)絡(luò)被某種挖掘策略分解成n個社區(qū)，定義一個n×n的對稱矩陣E=(eij)。其中eij表示社交網(wǎng)絡(luò)中位于社區(qū)i和社區(qū)j之間的邊數(shù)占總邊數(shù)的比例；E中對角線上的元素之和稱為該矩陣的跡，即：Tre=∑ieii，它表示社交網(wǎng)絡(luò)中位于社區(qū)內(nèi)部的邊數(shù)占總邊數(shù)的比例；定義矩陣E中每行或者每列中各個元素之和為ai=∑eij，它所表示社交網(wǎng)絡(luò)中與第i個社區(qū)中節(jié)點相連的邊在所有邊中所占的比例。在此基礎(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ù)的比例不大于任意連接時的期望值則Q=0。Q的最大值為1，Q越接近1，則說明網(wǎng)絡(luò)的社區(qū)劃分的質(zhì)量越好，即社區(qū)內(nèi)部聯(lián)系越緊密。在實際網(wǎng)絡(luò)中該值通常位于0.3到0.7之間。

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

(2)

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

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

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

2.1節(jié)點中心度

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

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

(3)

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

2.2度的冪率分布

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

P(X≤x)～k-γ

(4)

1932年，哈佛大學的語言學家Zifi發(fā)現(xiàn)如果將單詞出現(xiàn)的頻率按照由小到大的順序進行排列，則每個單詞出現(xiàn)的頻率和其序號存在著類似于帕累托定律的分布：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é)點占總節(jié)點個數(shù)的比率。例如，好萊塢演員合作網(wǎng)絡(luò)的度分布中γ=2.3；www萬維網(wǎng)的度分布中γ=2.1；美國西部電力網(wǎng)絡(luò)的度分布中γ=4。

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

(5)

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

我們稱算法1為MCF算法，在之后的實驗中驗證了該社區(qū)框架能夠反映一個社交網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)概況，如社交網(wǎng)絡(luò)中每個社區(qū)的相對大小，社區(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)更加詳細的信息，可以對社區(qū)框架進行鉆取，即向社區(qū)框架中添加度數(shù)較小的點。對于一個新添加的點，為了判定其屬于社區(qū)框架的哪一個社區(qū)，需要定義一個距離函數(shù)來進行判斷。一種最簡單的方式是如果新加入的節(jié)點i與社區(qū)框架中某一社區(qū)p中相連的點有d′個，則節(jié)點i到社區(qū)的距離為d(i,p)=d′。但是，按其定義如果節(jié)點i與社區(qū)p越遠，其聯(lián)系越緊密，這與直觀感覺是相互違背的。因此，定義社區(qū)p與節(jié)點i的距離為p中與i相連點的個數(shù)d′的倒數(shù)，即：

(6)

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

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

(7)

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

算法2DCF(P)

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

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

(1)對Vk中的每一個節(jié)點計算其到社區(qū)框架中每個社區(qū)的

距離

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

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

3.P=P′

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

框架P

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

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

3實驗結(jié)果與分析

3.1實驗數(shù)據(jù)

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

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

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

3.2實驗結(jié)果

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

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

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

圖4　netscience社區(qū)框架

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

表1　運行時間對比

表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ì)量對比

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

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

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

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

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

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

圖7展示了49號社區(qū)與其他社區(qū)之間的聯(lián)系情況，這里僅列出了與之有聯(lián)系的社區(qū)的編號。通過觀察社區(qū)結(jié)構(gòu)所對應(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ù)對比

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

4結(jié)語

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

參考文獻

[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)的社會網(wǎng)絡(luò)分析[J].計算機學報,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].軟件學報,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。國家自然科學基金項目(61170052)。王童童，碩士生，主研領(lǐng)域：社交網(wǎng)絡(luò)，數(shù)據(jù)挖掘。李盛恩，教授。王剛，碩士生。

中圖分類號TP311.13

文獻標識碼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