摘  要： 根據圖聚類節點的密度變化確定核心節點，構成連通子圖并確定郵件網絡社區劃分的個數及初始社區中心點，通過社區中心動態調整的方法將非核心節點劃分至所屬社區。實驗證明了該郵件網絡社區劃分的有效性和可行性。
關鍵詞： 圖聚類；郵件社區劃分；動態中心

    隨著互聯網的發展，網絡成為工作和生活中相互聯系的重要工具，與此同時，網絡社區[1]也應運而生。網絡社區是指基于電腦網絡的虛擬社會關系網絡的載體，在這種網絡中，相同類型的節點之間存在較多的連接，而不同類型節點之間的連接則相對較少。網絡社區通常滿足六度分割理論及150法則[2]等特征，通常是現實社區的近似。因此對網絡社區的發現，對了解現實社會中的社會關系網絡有著特別重要的意義。
    郵件社區作為一種網絡社區，同樣與現實的社會關系網絡同構，滿足小世界網絡模型[3]，由于電子郵件本身的優勢[4]，有利于發現社會關系網絡的動態特性。目前有關網絡社區發現的研究較多，具有代表性的方法有Girvan和Newman提出的基于去邊的G-N算法[5]、Aaron和Newman的層次聚類的算法以及基于三角環的Radicchi方法[5]等。但這些算法時間復雜度高，不易于處理大規模的網絡。
    本文從圖論的角度出發，首先采用基于貪心的圖形聚類算法，通過計算節點序列密度變化確定社區劃分的個數及每個社區的核心代表節點，然后以這些核心節點為中心，采用基于節點相似度的動態中心調整算法將節點劃分到其所屬的社區中，從而完成對郵件社區的劃分。
1 基本概念
    郵件網絡是社會網絡的一種，可以采取社會網絡的相關方法對郵件網絡進行社區劃分。為了便于算法的描述，首先對文中使用的社會網絡圖及相關概念進行數學描述和說明。
 
  

2 挖掘社會關系網絡
    基于電子郵件的社會網絡分析可以分為兩個步驟：(1)利用郵件日志信息構建有向有權社會網絡，網絡圖中頂點表示電子郵件的收件人或發件人，連線表示兩節點之間存在收發聯系；(2)使用改進的算法來挖掘隱含在此網絡圖中的社會關系，即對網絡圖進行社區挖掘。
2.1 構建社會關系網絡
    根據電子郵件地址直接構造一個有向有權圖，圖中頂點表示聯系人，連線表示頂點之間聯系的收發頻率。為了減少噪聲節點對整個網絡的影響，在構圖之前，通過設定閾值，選取收發郵件大于該閾值的節點，然后構造社會關系網絡圖并通過鄰接表和逆鄰接表進行存儲，從而有利于節省空間并方便節點的出入度計算(在本文中，選取indeg(vi)≥3以及outdeg(vi)≥3的節點，即閾值為3)。
2.2 郵件社區劃分
    郵件社區劃分的基本思想：從圖的劃分以及聚類的角度出發，分別從節點的密度變化和節點對之間的相似度進行考察，并采取社區中心動態調整的技術，主要分為以下步驟：
    (1)通過檢測網絡圖中節點的密度變化，確定聚類個數及聚類核心；
    (2)節點的劃分和各社區中心的調整。
2.2.1 聚類個數及聚類核心求解算法
    假設每一個郵件網絡圖中都存在一個被稱為“聚類核心點”的高密集區域，這些聚類核心點被密度稀疏的點所包圍。則聚類核心中的節點被稱為核心節點，核心節點的集合為核心節點集，而包含這些核心節點的子圖叫做核心子圖。
    根據式(1)、(2)求解出每個節點的局部密度以及集合H中密度最弱的節點集合。因此，通過分析最小密度值D(H)的變化，可以近似地求出所有的核心節點集。即如果密度最小的節點存在于稀疏區域，則當刪除該節點時D值會增大，那么下一個被刪除的節點必將存在于密度更高的節點區域內。如果某個節點的刪除引起D值的急劇下降，則該節點很有可能存在于密度較高的區域，也有可能因為節點的刪除導致了周圍其他節點的密度下降。算法(1)給出了計算密度序列變化的執行步驟。
   
    找出了所有滿足條件的核心節點集，可以通過多種方法將這些核心節點集劃分為核心子圖并最終確定聚類個數及聚類核心點。由于郵件網絡圖為稀疏圖，由核心節點所構成的連通子圖稱為核心子圖，核心子圖個數為聚類個數，則核心子圖中的節點就為聚類核心點。
2.2.2 社區劃分算法
    算法(2)描述了郵件網絡社區劃分步驟，ENCD(Email Network Community Detecting)郵件網絡社區劃分算法。

3 社區劃分實驗
    本文所選實驗數據集為enron郵件數據集以及蘇州大學2009年2月至5月之間的郵件日志內容。其中在http://www-2.cs.cmu.edu/~enron/可下載到enron數據集，它包括預處理后的151個節點以及252 759條邊。蘇州大學郵件日志內容有183 925個節點以及391 347條邊，內容含校內郵箱間的郵件收發信息以及相關的校外郵箱的郵件收發信息。
    在本實驗中，由于考慮到蘇州大學郵箱用戶的隱私問題，對郵箱地址進行了MD5轉換，并且對于每個郵箱mailbox，均由一個郵箱編碼mailboxlD唯一標識。
    本實驗的實驗環境為2．80 GHz Pentium CPU，1GB內存，80 GB硬盤，操作系統為Microsoft Windows XP，程序開發平臺為Myeclipse。社區劃分結果的每一項由兩個字段組成：郵箱編碼mailboxlD和社區標號CommunitylD。
    圖1是enron數據集構成的社會網絡圖，圖2顯示了本文參數對enron數據集社區劃分最終結果的影響。由圖可以看出，不同的?鄣值對確定社區劃分數量影響不大。

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

    由表1可以看出，本文提出算法在社區劃分個數方面與G-N相當。但是，G-N算法用于enron數據集所發現的社區結果中，有兩個社區中的節點只有1個，還有一個社區的節點個數為2個。這顯然與社區劃分步驟(1)矛盾，而本文提出的算法所求出的每個社區中節點個數則相對比較平均。圖3中G-N算法得出的社區密度最小為5，最大約為20；而本文算法得出的最小值約為10，并且最大峰值為25。可見，本文算法在enron上劃分的社區內部聯系更加緊密。圖4說明了G-N算法與ENCD算法得出的社區有效直徑均相當，因此本文算法用于網絡社區劃分是可行的。
4 分析與評估
    郵件社區的劃分本質上是稀疏圖聚類的問題，而此類劃分又是NP完全問題[6]。Girvan和Newman提出的基于去邊的G-N算法，在圖劃分上得取得了很好的效果，但是時間復雜度較高，為O(E2V)，其中，E為網絡圖中邊數、V為節點數。因此，不利于大規模的網絡社區發現。而本文算法(1)由于使用了鄰接表及逆鄰接表結構，所以，時間復雜度為O(|E|+|V|log|V|)+O(|V|)+O(|Ec|)，其中Ec為核心圖中的連接邊數。算法(2)時間復雜度為O(E)。所以最壞的間復雜度為O(|E|+|V|log|V|)。蘇州大學郵件數據集上測試的結果表明，本文方法執行效率要優于G-N算法。
    本文提出了一種新型的基于核心圖聚類算法的郵件網絡社區劃分，首先通過計算節點的密度變化找出滿足條件的核心節點，然后將這些核心節點集劃分為核心圖，最后通過節點相似度將未劃分的節點劃分到最相似的子圖中。在enron以及蘇州大學郵件數據集上的結果表明，本文算法在社區劃分的質量上與G-N算法相當，但是執行效率要高于G-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] 陳紹宇，宋佳興，劉衛東，等.關系網絡:一種基于小世界模型的社會關系網絡[J].計算機應用研究，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.