彭 玲，徐汀榮，喬志偉

(蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006)

隨著互聯(lián)網(wǎng)的發(fā)展，網(wǎng)絡(luò)成為工作和生活中相互聯(lián)系的重要工具，與此同時(shí)，網(wǎng)絡(luò)社區(qū)[1]也應(yīng)運(yùn)而生。網(wǎng)絡(luò)社區(qū)是指基于電腦網(wǎng)絡(luò)的虛擬社會(huì)關(guān)系網(wǎng)絡(luò)的載體，在這種網(wǎng)絡(luò)中，相同類型的節(jié)點(diǎn)之間存在較多的連接，而不同類型節(jié)點(diǎn)之間的連接則相對較少。網(wǎng)絡(luò)社區(qū)通常滿足六度分割理論及150法則[2]等特征，通常是現(xiàn)實(shí)社區(qū)的近似。因此對網(wǎng)絡(luò)社區(qū)的發(fā)現(xiàn)，對了解現(xiàn)實(shí)社會(huì)中的社會(huì)關(guān)系網(wǎng)絡(luò)有著特別重要的意義。

郵件社區(qū)作為一種網(wǎng)絡(luò)社區(qū)，同樣與現(xiàn)實(shí)的社會(huì)關(guān)系網(wǎng)絡(luò)同構(gòu)，滿足小世界網(wǎng)絡(luò)模型[3]，由于電子郵件本身的優(yōu)勢[4]，有利于發(fā)現(xiàn)社會(huì)關(guān)系網(wǎng)絡(luò)的動(dòng)態(tài)特性。目前有關(guān)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的研究較多，具有代表性的方法有Girvan和 Newman提出的基于去邊的 G-N算法[5]、Aaron和Newman的層次聚類的算法以及基于三角環(huán)的Radicchi方法[5]等。但這些算法時(shí)間復(fù)雜度高，不易于處理大規(guī)模的網(wǎng)絡(luò)。

本文從圖論的角度出發(fā)，首先采用基于貪心的圖形聚類算法，通過計(jì)算節(jié)點(diǎn)序列密度變化確定社區(qū)劃分的個(gè)數(shù)及每個(gè)社區(qū)的核心代表節(jié)點(diǎn)，然后以這些核心節(jié)點(diǎn)為中心，采用基于節(jié)點(diǎn)相似度的動(dòng)態(tài)中心調(diào)整算法將節(jié)點(diǎn)劃分到其所屬的社區(qū)中，從而完成對郵件社區(qū)的劃分。

1 基本概念

郵件網(wǎng)絡(luò)是社會(huì)網(wǎng)絡(luò)的一種，可以采取社會(huì)網(wǎng)絡(luò)的相關(guān)方法對郵件網(wǎng)絡(luò)進(jìn)行社區(qū)劃分。為了便于算法的描述，首先對文中使用的社會(huì)網(wǎng)絡(luò)圖及相關(guān)概念進(jìn)行數(shù)學(xué)描述和說明。

(1)網(wǎng)絡(luò)圖。通信結(jié)構(gòu)包括收件人和發(fā)件人的聯(lián)系信息，為了表示通信次數(shù)和方向，本文選擇有權(quán)有向網(wǎng)絡(luò)圖對郵件網(wǎng)絡(luò)進(jìn)行表示。設(shè) G=(V，E，W)，其中，V是全部頂點(diǎn)vi的集合，表示電子郵件的收件人或發(fā)件人；E是所有邊 eij的集合，其中與每個(gè)頂點(diǎn) vi直接相連的頂點(diǎn)被定義為 Ai，則 Ai={vj|eij∈E}；W 為邊的權(quán)重集合，任 意 兩 個(gè) 節(jié) 點(diǎn) vi、vj若 有 e=(vi，vj)或 e=(vj，vi)則 表 明vi、vj之間存在通信聯(lián)系，而 W(e)∈W，可以用郵箱 vi、vj的通信次數(shù)來描述。

(3)節(jié)點(diǎn)的密度。設(shè)節(jié)點(diǎn) i∈H?V，則 i關(guān)于 H的局部密度為：

其中，wij為節(jié)點(diǎn) i向節(jié)點(diǎn) j發(fā)送郵件的次數(shù)，而 wji為節(jié)點(diǎn)j向節(jié)點(diǎn)i發(fā)送郵件的次數(shù)。

D(H)表示H內(nèi)密度最弱的節(jié)點(diǎn)集合。

(4)網(wǎng)絡(luò)社區(qū)中心。在一個(gè)包含m個(gè)節(jié)點(diǎn) v1，…，vm的社區(qū)中，設(shè)Xi記錄郵箱vi與其他郵箱的通信次數(shù)，則社區(qū)中心：

它是社區(qū)中的節(jié)點(diǎn)與其他節(jié)點(diǎn)相互關(guān)聯(lián)的平均值，是整個(gè)社區(qū)的代表節(jié)點(diǎn)。

(5)社區(qū)密度及社區(qū)有效直徑[3]。設(shè)Gk是G的子圖，表示一個(gè)社區(qū)。社區(qū)Gk的密度記作D(Gk)，定義為所有節(jié)點(diǎn)出入度之和與節(jié)點(diǎn)個(gè)數(shù)之比，即：

社區(qū)有效直徑記作R(Gk)，定義為Gk中至少有90%以上的節(jié)點(diǎn)對，它們的距離小于或等于R(Gk)。

(6)節(jié)點(diǎn)v與社區(qū)中心vˉ的相似度。為了便于公式的描述，設(shè)X記錄了節(jié)點(diǎn)v與其他節(jié)點(diǎn)的通信次數(shù)，Y記錄了社區(qū)中心與其他節(jié)點(diǎn)的平均通信次數(shù)。則：

2 挖掘社會(huì)關(guān)系網(wǎng)絡(luò)

基于電子郵件的社會(huì)網(wǎng)絡(luò)分析可以分為兩個(gè)步驟：(1)利用郵件日志信息構(gòu)建有向有權(quán)社會(huì)網(wǎng)絡(luò)，網(wǎng)絡(luò)圖中頂點(diǎn)表示電子郵件的收件人或發(fā)件人，連線表示兩節(jié)點(diǎn)之間存在收發(fā)聯(lián)系；(2)使用改進(jìn)的算法來挖掘隱含在此網(wǎng)絡(luò)圖中的社會(huì)關(guān)系，即對網(wǎng)絡(luò)圖進(jìn)行社區(qū)挖掘。

2.1 構(gòu)建社會(huì)關(guān)系網(wǎng)絡(luò)

根據(jù)電子郵件地址直接構(gòu)造一個(gè)有向有權(quán)圖，圖中頂點(diǎn)表示聯(lián)系人，連線表示頂點(diǎn)之間聯(lián)系的收發(fā)頻率。為了減少噪聲節(jié)點(diǎn)對整個(gè)網(wǎng)絡(luò)的影響，在構(gòu)圖之前，通過設(shè)定閾值，選取收發(fā)郵件大于該閾值的節(jié)點(diǎn)，然后構(gòu)造社會(huì)關(guān)系網(wǎng)絡(luò)圖并通過鄰接表和逆鄰接表進(jìn)行存儲(chǔ)，從而有利于節(jié)省空間并方便節(jié)點(diǎn)的出入度計(jì)算(在本文中，選取 indeg(vi)≥3以及 outdeg(vi)≥3的節(jié)點(diǎn)，即閾值為3)。

2.2 郵件社區(qū)劃分

郵件社區(qū)劃分的基本思想：從圖的劃分以及聚類的角度出發(fā)，分別從節(jié)點(diǎn)的密度變化和節(jié)點(diǎn)對之間的相似度進(jìn)行考察，并采取社區(qū)中心動(dòng)態(tài)調(diào)整的技術(shù)，主要分為以下步驟：

(1)通過檢測網(wǎng)絡(luò)圖中節(jié)點(diǎn)的密度變化，確定聚類個(gè)數(shù)及聚類核心；

(2)節(jié)點(diǎn)的劃分和各社區(qū)中心的調(diào)整。

2.2.1 聚類個(gè)數(shù)及聚類核心求解算法

假設(shè)每一個(gè)郵件網(wǎng)絡(luò)圖中都存在一個(gè)被稱為“聚類核心點(diǎn)”的高密集區(qū)域，這些聚類核心點(diǎn)被密度稀疏的點(diǎn)所包圍。則聚類核心中的節(jié)點(diǎn)被稱為核心節(jié)點(diǎn)，核心節(jié)點(diǎn)的集合為核心節(jié)點(diǎn)集，而包含這些核心節(jié)點(diǎn)的子圖叫做核心子圖。

根據(jù)式(1)、(2)求解出每個(gè)節(jié)點(diǎn)的局部密度以及集合H中密度最弱的節(jié)點(diǎn)集合。因此，通過分析最小密度值D(H)的變化，可以近似地求出所有的核心節(jié)點(diǎn)集。即如果密度最小的節(jié)點(diǎn)存在于稀疏區(qū)域，則當(dāng)刪除該節(jié)點(diǎn)時(shí)D值會(huì)增大，那么下一個(gè)被刪除的節(jié)點(diǎn)必將存在于密度更高的節(jié)點(diǎn)區(qū)域內(nèi)。如果某個(gè)節(jié)點(diǎn)的刪除引起D值的急劇下降，則該節(jié)點(diǎn)很有可能存在于密度較高的區(qū)域，也有可能因?yàn)楣?jié)點(diǎn)的刪除導(dǎo)致了周圍其他節(jié)點(diǎn)的密度下降。算法(1)給出了計(jì)算密度序列變化的執(zhí)行步驟。

輸入：圖 G=(V，E，W)。

輸出：節(jié)點(diǎn)密度變化D及對應(yīng)的節(jié)點(diǎn)集合M。

算法：

①H初始值為所有節(jié)點(diǎn)，參數(shù)t；

②repeat；

③ 根 據(jù) 式(1)、(2)計(jì) 算 d(i，H)和 D(t)，Mt={i|i∈H∧D(t)=d(i，H)}；

④如果集合Mt包含2個(gè)或以上相互連接的單個(gè)子圖，則取相互之間連接數(shù)最小的節(jié)點(diǎn)集合；

⑤H=H-Mt，t=t+1；

⑥until集合H為空

計(jì)算出節(jié)點(diǎn)密度變化序列之后，可以通過式(6)來識別核心節(jié)點(diǎn)集。

其中，?為 0到 1之間的可調(diào)參數(shù)，并且參數(shù)?的選擇必須要保證社區(qū)劃分滿足以下兩條規(guī)則[5]：(1)最小組件規(guī)則。社區(qū)中節(jié)點(diǎn)個(gè)數(shù)必須≥6；(2)社區(qū)穩(wěn)定性規(guī)則。社區(qū)節(jié)點(diǎn)個(gè)數(shù)約120最為穩(wěn)定。若集合Mt滿足式(6)，則集合Mt為一核心節(jié)點(diǎn)集。

找出了所有滿足條件的核心節(jié)點(diǎn)集，可以通過多種方法將這些核心節(jié)點(diǎn)集劃分為核心子圖并最終確定聚類個(gè)數(shù)及聚類核心點(diǎn)。由于郵件網(wǎng)絡(luò)圖為稀疏圖，由核心節(jié)點(diǎn)所構(gòu)成的連通子圖稱為核心子圖，核心子圖個(gè)數(shù)為聚類個(gè)數(shù)，則核心子圖中的節(jié)點(diǎn)就為聚類核心點(diǎn)。

2.2.2 社區(qū)劃分算法

算法(2)描述了郵件網(wǎng)絡(luò)社區(qū)劃分步驟，ENCD(Email Network Community Detecting)郵件網(wǎng)絡(luò)社區(qū)劃分算法。

輸入：圖 G=(V，E，W)。

輸出：社區(qū)號及每個(gè)社區(qū)對應(yīng)的節(jié)點(diǎn)。

算法：

①輸入求出的核心子圖個(gè)數(shù)K及核心子圖節(jié)點(diǎn)；

②repeat；

③for t=(T，T-1，K，2，1)；

④ for每個(gè)社區(qū)中心cj； //尋找與集合中相似度最大的社區(qū)中心cj

⑤ if集合 Mt中包含非核心節(jié)點(diǎn)記作 xi，計(jì)算 xi與 cj的相似度，若 Sim(xi，cj)≥β則將 xi的社區(qū)號記為 j并將其加入到社區(qū)cj中； //考慮了一個(gè)節(jié)點(diǎn)屬于多個(gè)社區(qū)的情況

⑥for社區(qū)網(wǎng)絡(luò)中每個(gè)社區(qū)community[j]

⑦調(diào)整該社區(qū)的社區(qū)中心； //根據(jù)式(3)計(jì)算

⑧until所有的社區(qū)中心均未改變。

3 社區(qū)劃分實(shí)驗(yàn)

本文所選實(shí)驗(yàn)數(shù)據(jù)集為enron郵件數(shù)據(jù)集以及蘇州大學(xué)2009年2月至5月之間的郵件日志內(nèi)容。其中在http://www-2.cs.cmu.edu/～enron/可下載到 enron數(shù)據(jù)集，它包括預(yù)處理后的151個(gè)節(jié)點(diǎn)以及252 759條邊。蘇州大學(xué)郵件日志內(nèi)容有183 925個(gè)節(jié)點(diǎn)以及391 347條邊，內(nèi)容含校內(nèi)郵箱間的郵件收發(fā)信息以及相關(guān)的校外郵箱的郵件收發(fā)信息。

在本實(shí)驗(yàn)中，由于考慮到蘇州大學(xué)郵箱用戶的隱私問題，對郵箱地址進(jìn)行了MD5轉(zhuǎn)換，并且對于每個(gè)郵箱mailbox，均由一個(gè)郵箱編碼mailboxlD唯一標(biāo)識。

本實(shí)驗(yàn)的實(shí)驗(yàn)環(huán)境為 2.80 GHz Pentium CPU，1GB內(nèi)存，80 GB硬盤，操作系統(tǒng)為 Microsoft Windows XP，程序開發(fā)平臺為Myeclipse。社區(qū)劃分結(jié)果的每一項(xiàng)由兩個(gè)字段組成：郵箱編碼mailboxlD和社區(qū)標(biāo)號CommunitylD。

圖1是enron數(shù)據(jù)集構(gòu)成的社會(huì)網(wǎng)絡(luò)圖，圖2顯示了本文參數(shù)對enron數(shù)據(jù)集社區(qū)劃分最終結(jié)果的影響。由圖可以看出，不同的?值對確定社區(qū)劃分?jǐn)?shù)量影響不大。

表1顯示了使用本文算法與G-N算法在enron以及蘇州大學(xué)郵件數(shù)據(jù)集上的結(jié)果比較，其中?取值0.26。modularity[5]為算法的評價(jià)指標(biāo)之一，通常為(0，1)的小數(shù)，且值越大說明社區(qū)劃分的質(zhì)量越高。圖3描述了本文算法與G-N算法在enron數(shù)據(jù)集上社區(qū)密度的對比。圖4是在enron數(shù)據(jù)集上社區(qū)有效直徑的對比圖。

表1 G-N與ENCD算法在相同數(shù)據(jù)集上的結(jié)果對比

由表1可以看出，本文提出算法在社區(qū)劃分個(gè)數(shù)方面與G-N相當(dāng)。但是，G-N算法用于enron數(shù)據(jù)集所發(fā)現(xiàn)的社區(qū)結(jié)果中，有兩個(gè)社區(qū)中的節(jié)點(diǎn)只有1個(gè)，還有一個(gè)社區(qū)的節(jié)點(diǎn)個(gè)數(shù)為2個(gè)。這顯然與社區(qū)劃分步驟(1)矛盾，而本文提出的算法所求出的每個(gè)社區(qū)中節(jié)點(diǎn)個(gè)數(shù)則相對比較平均。圖3中G-N算法得出的社區(qū)密度最小為5，最大約為20；而本文算法得出的最小值約為10，并且最大峰值為25?？梢?，本文算法在enron上劃分的社區(qū)內(nèi)部聯(lián)系更加緊密。圖4說明了G-N算法與ENCD算法得出的社區(qū)有效直徑均相當(dāng)，因此本文算法用于網(wǎng)絡(luò)社區(qū)劃分是可行的。

4 分析與評估

郵件社區(qū)的劃分本質(zhì)上是稀疏圖聚類的問題，而此類劃分又是NP完全問題[6]。Girvan和Newman提出的基于去邊的G-N算法，在圖劃分上得取得了很好的效果，但是時(shí)間復(fù)雜度較高，為O(E2V)，其中，E為網(wǎng)絡(luò)圖中邊數(shù)、V為節(jié)點(diǎn)數(shù)。因此，不利于大規(guī)模的網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)。而本文算法(1)由于使用了鄰接表及逆鄰接表結(jié)構(gòu)，所以，時(shí)間復(fù)雜度為 O(|E|+|V|log|V|)+O(|V|)+O(|Ec|)，其中Ec為核心圖中的連接邊數(shù)。算法(2)時(shí)間復(fù)雜度為O(E)。所以最壞的間復(fù)雜度為O(|E|+|V|log|V|)。蘇州大學(xué)郵件數(shù)據(jù)集上測試的結(jié)果表明，本文方法執(zhí)行效率要優(yōu)于G-N算法。

本文提出了一種新型的基于核心圖聚類算法的郵件網(wǎng)絡(luò)社區(qū)劃分，首先通過計(jì)算節(jié)點(diǎn)的密度變化找出滿足條件的核心節(jié)點(diǎn)，然后將這些核心節(jié)點(diǎn)集劃分為核心圖，最后通過節(jié)點(diǎn)相似度將未劃分的節(jié)點(diǎn)劃分到最相似的子圖中。在enron以及蘇州大學(xué)郵件數(shù)據(jù)集上的結(jié)果表明，本文算法在社區(qū)劃分的質(zhì)量上與G-N算法相當(dāng)，但是執(zhí)行效率要高于G-N。此外，本文算法還支持一個(gè)節(jié)點(diǎn)屬于多個(gè)社區(qū)的情況，而這種情況在現(xiàn)實(shí)生活中是極為常見的。

[1]ZHANG Y C， YU Xj， HOU L Y.Web communities:Analysis and construction[M].Berlin:Springer，2005.

[2]STROGATZ S H.Exploring complex networks[J].Nature，2001(410):268-276.

[3]陳紹宇，宋佳興，劉衛(wèi)東，等.關(guān)系網(wǎng)絡(luò):一種基于小世界模型的社會(huì)關(guān)系網(wǎng)絡(luò)[J].計(jì)算機(jī)應(yīng)用研究，2006，23(5):194-197.

[4]ALSTYNE M V，ZHANG J.EmailNet:A system for automatically mining social networks from organizational email communication[C].In NAACSOS2003，2003.

[5]MARK E J，NEWMAN M.Finding and evaluating community structure in networks [M].PhysicalReview E，69.026113，2004.

[6]GIRVAN M，NEWMAN M.Community structure in social and biological networks[J].Proc.Natl.Acad.Sci.USA 2002(99):8271-8276.