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

王童童　李盛恩　王　剛

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

?

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

王童童李盛恩王剛

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

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

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

0引言

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

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

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

1社交網(wǎng)絡與社區(qū)結構

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

(1)

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

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

圖1　社區(qū)結構示意圖[8]

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

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

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

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

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

(2)

其中P為社區(qū)挖掘算法所發(fā)現(xiàn)的社區(qū)的集合，m為社交網(wǎng)絡中邊的條數(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ū)考察，我們能夠總結出整個網(wǎng)絡的社區(qū)狀態(tài)。例如在合著網(wǎng)絡中，每一個領域都有很多頂尖學者，可以將這些學者提取出來構成一個網(wǎng)絡來對其進行社區(qū)劃分，用以反映整個網(wǎng)絡的社區(qū)狀態(tài)。我們提取的由重要參與者構成的網(wǎng)絡叫做原社交網(wǎng)絡的關鍵子網(wǎng)絡，其社區(qū)劃分稱之為社區(qū)框架。當想獲得更多社區(qū)細節(jié)時，我們可以向社區(qū)框架中添加節(jié)點進行鉆取。

2.1節(jié)點中心度

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

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

(3)

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

2.2度的冪率分布

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

P(X≤x)～k-γ

(4)

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

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

(5)

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

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

算法1MCF(G,r)

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

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

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

在得到社區(qū)框架后，如果想得到社交網(wǎng)絡社區(qū)結構更加詳細的信息，可以對社區(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ū)結構信息。如想獲得社區(qū)結構更進一步的信息，則對社區(qū)框架繼續(xù)添加節(jié)點，最終直至將所有節(jié)點添加進去，實現(xiàn)對整個網(wǎng)絡的社區(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ū)的距離并添加到相應社區(qū)的時間復雜度為O(n)。當向社區(qū)框架中加入所有節(jié)點的時候，便取得了一個對整個社交網(wǎng)絡的社區(qū)劃分。對此社區(qū)結構劃分的好壞可以通過Q函數(shù)來進行評價。

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

3實驗結果與分析

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

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

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

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

3.2實驗結果

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

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

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

圖4　netscience社區(qū)框架

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

表1　運行時間對比

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

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

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

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

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

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

圖6展示了社區(qū)結構與社區(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ū)結構所對應的曲線可知，社區(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)絡的社區(qū)結構的概況，包括社區(qū)內(nèi)部節(jié)點的相對多少、社區(qū)內(nèi)部邊的密度、社區(qū)之間的聯(lián)系緊密程度。

4結語

通過使用MCF算法，我們能夠快速地在不對整個社交網(wǎng)絡進行社區(qū)挖掘的情況下了解社區(qū)的概況，并能夠使用DCF算法對社區(qū)框架進行鉆取，最終實現(xiàn)對社交網(wǎng)絡的社區(qū)劃分。最后通過實驗驗證了我們所提方案的有效性。然而，我們最終實現(xiàn)的社區(qū)劃分效果相對于成熟的GN算法來說還有待提高，同時我們也發(fā)現(xiàn)，本文所提方案只有應用于符合冪律分布的社交網(wǎng)絡時，才會體現(xiàn)出其性能優(yōu)勢。今后的主要工作是當社交網(wǎng)絡是以加權有向圖表示時，如何可控的快速的發(fā)現(xiàn)其社區(qū)結構，同時如何利用社交網(wǎng)絡進行高效地廣告分發(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] 竇炳琳,李澍淞,張世永.基于結構的社會網(wǎng)絡分析[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] 楊博,劉大有,金弟.復雜網(wǎng)絡聚類方法[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)。王童童，碩士生，主研領域：社交網(wǎng)絡，數(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