摘  要： 根據(jù)圖聚類節(jié)點(diǎn)的密度變化確定核心節(jié)點(diǎn)，構(gòu)成連通子圖并確定郵件網(wǎng)絡(luò)社區(qū)劃分的個(gè)數(shù)及初始社區(qū)中心點(diǎn)，通過(guò)社區(qū)中心動(dòng)態(tài)調(diào)整的方法將非核心節(jié)點(diǎn)劃分至所屬社區(qū)。實(shí)驗(yàn)證明了該郵件網(wǎng)絡(luò)社區(qū)劃分的有效性和可行性。
關(guān)鍵詞： 圖聚類；郵件社區(qū)劃分；動(dòng)態(tài)中心

    隨著互聯(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)之間的連接則相對(duì)較少。網(wǎng)絡(luò)社區(qū)通常滿足六度分割理論及150法則[2]等特征，通常是現(xiàn)實(shí)社區(qū)的近似。因此對(duì)網(wǎng)絡(luò)社區(qū)的發(fā)現(xiàn)，對(duì)了解現(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)勢(shì)[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ā)，首先采用基于貪心的圖形聚類算法，通過(guò)計(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ū)中，從而完成對(duì)郵件社區(qū)的劃分。
1 基本概念
    郵件網(wǎng)絡(luò)是社會(huì)網(wǎng)絡(luò)的一種，可以采取社會(huì)網(wǎng)絡(luò)的相關(guān)方法對(duì)郵件網(wǎng)絡(luò)進(jìn)行社區(qū)劃分。為了便于算法的描述，首先對(duì)文中使用的社會(huì)網(wǎng)絡(luò)圖及相關(guān)概念進(jìn)行數(shù)學(xué)描述和說(shuō)明。
 
  

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)的算法來(lái)挖掘隱含在此網(wǎng)絡(luò)圖中的社會(huì)關(guān)系，即對(duì)網(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)對(duì)整個(gè)網(wǎng)絡(luò)的影響，在構(gòu)圖之前，通過(guò)設(shè)定閾值，選取收發(fā)郵件大于該閾值的節(jié)點(diǎn)，然后構(gòu)造社會(huì)關(guān)系網(wǎng)絡(luò)圖并通過(guò)鄰接表和逆鄰接表進(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)對(duì)之間的相似度進(jìn)行考察，并采取社區(qū)中心動(dòng)態(tài)調(diào)整的技術(shù)，主要分為以下步驟：
    (1)通過(guò)檢測(cè)網(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)集合。因此，通過(guò)分析最小密度值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í)行步驟。
   
    找出了所有滿足條件的核心節(jié)點(diǎn)集，可以通過(guò)多種方法將這些核心節(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ū)劃分算法。

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é)郵箱用戶的隱私問(wèn)題，對(duì)郵箱地址進(jìn)行了MD5轉(zhuǎn)換，并且對(duì)于每個(gè)郵箱mailbox，均由一個(gè)郵箱編碼mailboxlD唯一標(biāo)識(shí)。
    本實(shí)驗(yàn)的實(shí)驗(yàn)環(huán)境為2．80 GHz Pentium CPU，1GB內(nèi)存，80 GB硬盤，操作系統(tǒng)為Microsoft Windows XP，程序開(kāi)發(fā)平臺(tái)為Myeclipse。社區(qū)劃分結(jié)果的每一項(xiàng)由兩個(gè)字段組成：郵箱編碼mailboxlD和社區(qū)標(biāo)號(hào)CommunitylD。
    圖1是enron數(shù)據(jù)集構(gòu)成的社會(huì)網(wǎng)絡(luò)圖，圖2顯示了本文參數(shù)對(duì)enron數(shù)據(jù)集社區(qū)劃分最終結(jié)果的影響。由圖可以看出，不同的?鄣值對(duì)確定社區(qū)劃分?jǐn)?shù)量影響不大。

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

    由表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ù)則相對(duì)比較平均。圖3中G-N算法得出的社區(qū)密度最小為5，最大約為20；而本文算法得出的最小值約為10，并且最大峰值為25?？梢?jiàn)，本文算法在enron上劃分的社區(qū)內(nèi)部聯(lián)系更加緊密。圖4說(shuō)明了G-N算法與ENCD算法得出的社區(qū)有效直徑均相當(dāng)，因此本文算法用于網(wǎng)絡(luò)社區(qū)劃分是可行的。
4 分析與評(píng)估
    郵件社區(qū)的劃分本質(zhì)上是稀疏圖聚類的問(wèn)題，而此類劃分又是NP完全問(wèn)題[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ù)集上測(cè)試的結(jié)果表明，本文方法執(zhí)行效率要優(yōu)于G-N算法。
    本文提出了一種新型的基于核心圖聚類算法的郵件網(wǎng)絡(luò)社區(qū)劃分，首先通過(guò)計(jì)算節(jié)點(diǎn)的密度變化找出滿足條件的核心節(jié)點(diǎn)，然后將這些核心節(jié)點(diǎn)集劃分為核心圖，最后通過(guò)節(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í)生活中是極為常見(jiàn)的。
參考文獻(xiàn)
[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]. Physical Review 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.