摘 要：為深入挖掘互聯(lián)網(wǎng)郵件通聯(lián)關(guān)系，提出了一種基于郵箱活躍度的郵件社區(qū)劃分算法（MAS），并研究了郵件社區(qū)的性質(zhì)與特征。算法采用基于郵箱通聯(lián)活躍頻度的余弦相似度評(píng)估郵箱之間通聯(lián)關(guān)系的相似性，并通過(guò)層次聚類的方法指導(dǎo)郵件社區(qū)聚類，然后對(duì)社區(qū)中心進(jìn)行動(dòng)態(tài)調(diào)整以完成劃分。在有效模擬數(shù)據(jù)集上的實(shí)驗(yàn)表明，該算法有效、合理，可以應(yīng)用于實(shí)際的挖掘應(yīng)用。

關(guān)鍵詞：郵件社區(qū)；社會(huì)網(wǎng)絡(luò)分析；數(shù)據(jù)挖掘；活躍度

中圖分類號(hào)：TP393.098

現(xiàn)代社會(huì)中，互聯(lián)網(wǎng)已經(jīng)深入到人們的生活的各個(gè)方面，成為人們生活、工作不可缺少的一部分。人們?cè)诰W(wǎng)絡(luò)間的通信方式也多種多樣，其中電子郵件是主要通信工具之一。電子郵件之間的相互通信在互聯(lián)網(wǎng)上構(gòu)成了龐大的郵件網(wǎng)絡(luò)。在這個(gè)網(wǎng)絡(luò)中，包含大量電子形式的個(gè)人信息以及郵箱用戶之間相互通信關(guān)系。整個(gè)郵件網(wǎng)絡(luò)又可以劃分出若干的郵件網(wǎng)絡(luò)社區(qū)。網(wǎng)絡(luò)社區(qū)[1]表示在虛擬網(wǎng)絡(luò)中，網(wǎng)民根據(jù)共同的興趣而形成的真實(shí)的社會(huì)團(tuán)體，具有實(shí)際社區(qū)的基本要素，包括人群（網(wǎng)民）、活動(dòng)區(qū)域（網(wǎng)絡(luò)）、互動(dòng)行為、共同的社會(huì)心理基礎(chǔ)等。網(wǎng)民在一定的網(wǎng)絡(luò)空間內(nèi)，圍繞共同的需要和興趣進(jìn)行交流互動(dòng)活動(dòng)，相互之間構(gòu)成的網(wǎng)絡(luò)社區(qū)具有六度分離[2]的特性。郵件社區(qū)作為一種網(wǎng)絡(luò)社區(qū)，也與現(xiàn)實(shí)中對(duì)應(yīng)的社會(huì)關(guān)系網(wǎng)絡(luò)是同構(gòu)的，能夠反映出社會(huì)網(wǎng)絡(luò)中網(wǎng)民活動(dòng)的社區(qū)通信信息和相互交流興趣主題。目前有關(guān)網(wǎng)絡(luò)社區(qū)[1，3]的研究較多，如網(wǎng)頁(yè)社區(qū)研究，主要包括關(guān)聯(lián)網(wǎng)頁(yè)的查找、噪聲網(wǎng)頁(yè)的消除和網(wǎng)頁(yè)關(guān)系聚類等；又如現(xiàn)在應(yīng)用較多的微博網(wǎng)絡(luò)社區(qū)研究，包括微博熱點(diǎn)話題發(fā)現(xiàn)和基于主題聚類[4-6]等；再如垃圾郵件的識(shí)別與過(guò)濾等[7，8]。但是在郵件社區(qū)中，直接利用郵件通聯(lián)關(guān)系進(jìn)行社會(huì)網(wǎng)絡(luò)構(gòu)建的研究和應(yīng)用相對(duì)比較薄弱，然而郵件社區(qū)研究對(duì)于發(fā)現(xiàn)郵件社區(qū)中的犯罪網(wǎng)絡(luò)及分析網(wǎng)絡(luò)核心成員等實(shí)際應(yīng)用具有重要意義。

1 郵箱活躍度分析

郵件網(wǎng)絡(luò)是一種社區(qū)網(wǎng)絡(luò)，由眾多郵件社區(qū)構(gòu)成。郵件社區(qū)是由若干郵箱及郵箱之間的相互通信組成，如果將郵箱看作是節(jié)點(diǎn)，而通信關(guān)系看作是邊，則郵件社區(qū)可以表示為一張圖，有如下與關(guān)系網(wǎng)絡(luò)[9]類似方法的定義。

定義1 郵件網(wǎng)絡(luò)表示為加權(quán)圖G=（V，E），其中V是頂點(diǎn)集合，E是邊集合。在郵件網(wǎng)絡(luò)中，v∈V代表一個(gè)郵箱，e=（vi，vj）∈E表示郵箱vi和vj之間存在通信聯(lián)系，而w（e）（其中e=（vi，vj））表示郵箱vi到vj的關(guān)聯(lián)頻度，可以用郵箱vi和vj的通信次數(shù)表示。設(shè)Gk是G的子圖，表示一個(gè)社區(qū)。社區(qū)Gk的直徑，記作D（Gk），定義為Gk中所有節(jié)點(diǎn)對(duì)之間距離的最大值。而社區(qū)Gk的節(jié)點(diǎn)對(duì)的平均距離davg（Gk）是所有節(jié)點(diǎn)對(duì)之間距離的平均值。社區(qū)Gk的有效直徑記作Dval（Gk），對(duì)于社區(qū)Gk中至少90%以上節(jié)點(diǎn)對(duì)，它們的距離小于或等于Dval（Gk）。

為分析研究郵件社區(qū)性質(zhì)，本文使用了一組有效的互聯(lián)網(wǎng)郵件模擬數(shù)據(jù)，能真實(shí)反映郵箱間通聯(lián)關(guān)系特性。該數(shù)據(jù)集包含90天共200萬(wàn)郵件通聯(lián)數(shù)據(jù)。對(duì)該數(shù)據(jù)集進(jìn)行郵箱發(fā)送活動(dòng)統(tǒng)計(jì)如下圖所示，部分通聯(lián)次數(shù)為1的郵箱未顯示。統(tǒng)計(jì)發(fā)現(xiàn)，一共4.4W郵箱中，有4千個(gè)郵箱的主動(dòng)發(fā)送次數(shù)大于20。這部分郵箱明顯屬于高活躍郵箱。其余郵箱組成了圖中“長(zhǎng)尾”部分。

僅用郵箱的通聯(lián)次數(shù)來(lái)分析不同郵箱的特性顯然是不足的。本文考慮引入郵箱的活躍度，定義郵箱的活躍特性。

定義2 活躍度t，表示目標(biāo)郵箱在一段時(shí)間內(nèi)的綜合收發(fā)郵件的頻度。依據(jù)現(xiàn)實(shí)社會(huì)人物的活動(dòng)規(guī)律，對(duì)時(shí)間粒度劃分的最小單位為天，定義活躍度t如下

其中tsend是發(fā)送郵件的活躍度，trecv是接收郵件的活躍度，α表示活躍系數(shù)?？紤]發(fā)送郵件者作為主動(dòng)方，而接收郵件作為被動(dòng)方，發(fā)送郵件對(duì)活躍度貢獻(xiàn)應(yīng)略高于接收郵件，因此引入活躍系數(shù)α。發(fā)送活躍度tsend和接收活躍度trecv的計(jì)算方式相同，如下式：

其中si為第i天發(fā)送/接收郵件的次數(shù)，K為平衡因子，當(dāng)沒(méi)有接收和發(fā)送郵件時(shí)設(shè)si=1。該公式中，因?yàn)閟i不能為0（否則活躍度為零），所以不能區(qū)分第i天發(fā)送了一封郵件和沒(méi)有發(fā)送的情況，因此引入了K平衡因子，使得兩種情況有活躍度的差異。如果第i天發(fā)送/接收郵件的次數(shù)為零，則取si=1（不能為0），ki=1；反之，若si≠0，則si保持不變，ki=0；λ為遞減權(quán)重，本文中取值λ=0.3，用于平衡因si=0時(shí)帶來(lái)的誤差。

活躍度可以很好度量突發(fā)性發(fā)送郵件的郵箱和平衡性發(fā)送郵件的郵箱之間的區(qū)別。例如：郵箱A僅在一個(gè)月某一天發(fā)送60封郵件，而郵箱B在一個(gè)月每天都會(huì)發(fā)送1到3封共60封郵件。顯然郵箱B具有更高的活躍性，其計(jì)算得活躍度也更高。

定義3 郵箱間的活躍頻度dt，表示兩個(gè)郵箱之間在一段時(shí)間內(nèi)綜合收發(fā)郵件的頻率，定義如下。

與活躍度定義相同，tsend是發(fā)送郵件的活躍度，trecv是接收郵件的活躍度，α表示活躍系數(shù)。本文提到活躍度，不特殊說(shuō)明均指兩郵箱間的活躍頻度。

2 基于活躍度的相似度

郵件社區(qū)具有一定的小世界特征[10]。即同一個(gè)郵件社區(qū)內(nèi)，不同郵箱之間進(jìn)行通信的行為具有很高的相似性；同一郵件社區(qū)內(nèi)，必然會(huì)存在一個(gè)或多個(gè)具有高活躍性的郵箱，這些郵箱直接或者間接加強(qiáng)其他郵箱之間的聯(lián)系；同一郵件社區(qū)內(nèi)，郵箱與一定數(shù)量的同一社區(qū)其他郵箱存在直接通信聯(lián)系更為緊密。這些郵箱的特性，我們可以使用郵箱的相似度來(lái)度量。而郵件社區(qū)的劃分正是以郵箱間相似度為基礎(chǔ)，即相似特征的郵箱即劃為同一社區(qū)。

郵箱與郵箱之間的通信行為相似度由兩個(gè)郵箱與其他郵箱之間的關(guān)系來(lái)度量。設(shè)G表示郵件網(wǎng)絡(luò)，其中包含n個(gè)郵箱，分別為v1，v2，…，vn，那么G可以表示為一個(gè)n×n矩陣X。X的元素xij則表示郵箱vi和郵箱vj之間的關(guān)系權(quán)重，xij為某時(shí)間段內(nèi)郵箱vi向郵箱vj發(fā)送郵件的活躍度。xij不僅僅只是通聯(lián)次數(shù)的關(guān)系，還包含了兩個(gè)郵箱之間活躍頻繁次數(shù)的特征。矩陣X中，第i個(gè)行向量Xi={xi1，xi2，…，xin}記錄了郵箱vi與社區(qū)中其他郵箱的活躍度。由于一個(gè)郵箱一般不向自己發(fā)送郵件，這導(dǎo)致矩陣X的對(duì)角線上元素大部分為0。本文使用余弦定義來(lái)計(jì)算郵箱vi和郵箱vj的相似度sim（vi，vj），即有下式：

其中Xi、Xj表示郵箱vi和郵箱vj在矩陣X中對(duì)應(yīng)的行向量。由于主對(duì)角線元素為大部分為0的影響，向量Xi與Xj的點(diǎn)積使得郵箱vi和郵箱vj相互通信大部分會(huì)為0而被忽略，為此本文將xii都置1，是相似度更有效。

由以上相似度可知，對(duì)于郵箱vi，自我相似度為1，即sim（vi，vi）=1；與郵箱vj共同關(guān)聯(lián)的郵箱越多，對(duì)應(yīng)關(guān)聯(lián)郵箱通聯(lián)關(guān)系的活躍度越接近，則通信聯(lián)系越相似，即sim（vi，vj）越接近于1；與郵箱vj沒(méi)有共同關(guān)聯(lián)的郵箱時(shí)，sim（vi，vj）=0。

定義4 在一個(gè)包含n個(gè)節(jié)點(diǎn)v1，v2，…，vn的社區(qū)中，社區(qū)中心c表示為c=max（DDvi+DBvi+DCvi），其中DDvi表示點(diǎn)度中心度（degree centrality）、DBvi表示中間中心度（betweenness centrality）和DCvi表示接近中心度（closeness centrality）[11-13]。c是社區(qū)中的節(jié)點(diǎn)與其他節(jié)點(diǎn)相互關(guān)聯(lián)度最高的節(jié)點(diǎn)，是社區(qū)的中心節(jié)點(diǎn)。

3 郵件社區(qū)算法改進(jìn)

有了相似度的計(jì)算方法，就可以采用基于活躍度的郵件社區(qū)劃分算法MAS（Mail Activity Similarity）對(duì)郵件社區(qū)進(jìn)行劃分。算法的主要思想，是采用基于活躍度度量郵箱相似性建立社區(qū)并動(dòng)態(tài)調(diào)整社區(qū)中心，本文采用的社區(qū)劃分算法實(shí)際上是一種基于郵件行為相似度的聚類算法。

3.1 社區(qū)劃分算法

正如前文所述，本文用稀疏矩陣X表示一個(gè)社區(qū)網(wǎng)絡(luò)，并用向量Xi表示社區(qū)網(wǎng)絡(luò)中的某一郵箱vi的與網(wǎng)絡(luò)中其余郵箱通聯(lián)關(guān)系的活躍度集合。本文描述郵件社區(qū)劃分的算法如下。

算法1 基于MAS社區(qū)劃分算法。

輸入：由n×n的矩陣X表示的郵件社區(qū)網(wǎng)絡(luò)

輸出：郵件社區(qū)劃分結(jié)果。每一項(xiàng)包括郵箱及其所屬的社區(qū)序號(hào)

方法：

1） 輸入劃分社區(qū)數(shù)目k；

2） 選取k個(gè)節(jié)點(diǎn)作為初始社區(qū)中心節(jié)點(diǎn)；

3） repeat

4） for郵件網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)xi： //xi為社區(qū)網(wǎng)絡(luò)中的節(jié)點(diǎn)

5） for每個(gè)社區(qū)中心cj //尋找與節(jié)點(diǎn)xi相似度最大的社區(qū)中心cj

6） if 節(jié)點(diǎn)xi與社區(qū)中心cj具有最大相似度， then

7） 將節(jié)點(diǎn)xi的社區(qū)序號(hào)設(shè)置為j；

8） end if

9） end for

10） end for

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

12） 調(diào)整該社區(qū)的社區(qū)中心cj； //cj的調(diào)整方法參見(jiàn)文中定義4

13） end for

14） until所有的社區(qū)中心不再改變；

15）輸出社區(qū)劃分結(jié)果；

3.2 動(dòng)態(tài)調(diào)整中心改進(jìn)

動(dòng)態(tài)中心調(diào)整是一個(gè)及其消耗時(shí)間的過(guò)程，當(dāng)郵件網(wǎng)絡(luò)增大時(shí)，每一個(gè)節(jié)點(diǎn)都會(huì)再次與所有社區(qū)中心做相似比較。這個(gè)過(guò)程及其耗時(shí)，本文考慮縮減比較次數(shù)來(lái)提高劃分效率。

將每個(gè)社區(qū)再次按照距離劃分出鄰近社區(qū)，當(dāng)社區(qū)或者這個(gè)社區(qū)的鄰近社區(qū)中心節(jié)點(diǎn)改變時(shí)，才有必要計(jì)算社區(qū)內(nèi)節(jié)點(diǎn)到鄰近社區(qū)中心節(jié)點(diǎn)的距離，而其余社區(qū)不再考慮。我們將算法1作修改如下：

算法2 基于MAS社區(qū)劃分算法改進(jìn)。

輸入：由n×n的矩陣X表示的郵件社區(qū)網(wǎng)絡(luò)

輸出：郵件社區(qū)劃分結(jié)果。每一項(xiàng)包括郵箱及其所屬的社區(qū)序號(hào)

方法：

1）輸入劃分社區(qū)數(shù)目k；

2）選取k個(gè)節(jié)點(diǎn)作為初始社區(qū)中心節(jié)點(diǎn)，初始化臨近社區(qū)為所有社區(qū)，并網(wǎng)絡(luò)節(jié)點(diǎn)所屬劃為某一社區(qū)；

3）repeat

4）for郵件網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)xi： //xi為社區(qū)網(wǎng)絡(luò)中的節(jié)點(diǎn)

5） for xi所屬社區(qū)所有鄰近社區(qū)中心cj //尋找與節(jié)點(diǎn)xi相似度最大的鄰近社區(qū)中心cj

6） if 節(jié)點(diǎn)xi與社區(qū)中心cj具有最大相似度，then

7） 將節(jié)點(diǎn)xi的社區(qū)序號(hào)設(shè)置為j；

8） end if

9） end for

10）end for

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

12） 調(diào)整該社區(qū)的社區(qū)中心cj；

13） 調(diào)整鄰近社區(qū)集合

14）end for

15）until所有的社區(qū)中心不再改變；

16）輸出社區(qū)劃分結(jié)果；

4 優(yōu)化調(diào)整

郵件網(wǎng)絡(luò)中必然會(huì)存在離散的節(jié)點(diǎn)，這樣的節(jié)點(diǎn)與網(wǎng)絡(luò)中的其他節(jié)點(diǎn)關(guān)聯(lián)頻度較小，與其他任意一個(gè)社區(qū)中心的相似度都很低，影響社區(qū)劃分的質(zhì)量；郵件社區(qū)初始社區(qū)中心節(jié)點(diǎn)的選取也影響社區(qū)劃分的質(zhì)量；矩陣計(jì)算時(shí)間復(fù)雜度較高，特別隨著網(wǎng)絡(luò)規(guī)模增大，矩陣計(jì)算需要的時(shí)間和空間消耗急劇增大。

針對(duì)這些問(wèn)題，本文采取優(yōu)化解決如下：

（1）對(duì)噪聲節(jié)點(diǎn)進(jìn)行預(yù)處理。在郵件網(wǎng)絡(luò)中，存在少數(shù)極其不活躍的節(jié)點(diǎn)，稱之為噪聲節(jié)點(diǎn)或孤立節(jié)點(diǎn)。在社區(qū)劃分中將關(guān)聯(lián)頻度小于某個(gè)閾值的噪聲節(jié)點(diǎn)過(guò)濾掉，以避免社區(qū)劃分因噪聲節(jié)點(diǎn)的存在而影響整個(gè)社區(qū)劃分的質(zhì)量。

（2）選擇合理的初始社區(qū)中心節(jié)點(diǎn)。在初始化階段，本文挑選在整個(gè)網(wǎng)絡(luò)中邊的度數(shù)大于某個(gè)閾值的k個(gè)節(jié)點(diǎn)作為最初的中心節(jié)點(diǎn)，并保證這些節(jié)點(diǎn)在步長(zhǎng)為2的路徑上不相關(guān)聯(lián)。這極大地減少了程序中更新中心點(diǎn)迭代次數(shù)，大大降低了時(shí)間復(fù)雜度，實(shí)驗(yàn)表明該方法可有效地縮小各個(gè)社區(qū)的有效直徑和平均距離，使得各個(gè)社區(qū)劃分的質(zhì)量得到提高。

（3）使用稀疏矩陣的表示和計(jì)算，從而簡(jiǎn)化矩陣計(jì)算帶來(lái)的巨大開(kāi)銷。保證實(shí)驗(yàn)在可控時(shí)間范圍內(nèi)進(jìn)行。同時(shí)為降低計(jì)算復(fù)雜度，對(duì)大數(shù)的冪運(yùn)算和乘方運(yùn)算采用近似運(yùn)算替代，縮短計(jì)算時(shí)間。

下面針對(duì)具體優(yōu)化進(jìn)行實(shí)驗(yàn)。

5 實(shí)驗(yàn)

基于以上理論基礎(chǔ)以及優(yōu)化策略，對(duì)一組模擬郵件網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行分析，該網(wǎng)絡(luò)包括90天共200萬(wàn)郵件通聯(lián)數(shù)據(jù)。實(shí)驗(yàn)中將社區(qū)網(wǎng)絡(luò)用有向圖表示。

本實(shí)驗(yàn)的實(shí)驗(yàn)環(huán)境為3.40GHz Inter（R） Core（TM） i7 3770 CPU，4G內(nèi)存，1TB硬盤，操作系統(tǒng)為Windows XP SP3，程序開(kāi)發(fā)平臺(tái)為Python2.7。社區(qū)劃分結(jié)果的每一項(xiàng)由兩個(gè)字段組成：郵箱和社區(qū)編號(hào)CID。

5.1 優(yōu)化有效性驗(yàn)證

采用第3節(jié)MAS改進(jìn)算法進(jìn)行社區(qū)劃分實(shí)驗(yàn)。對(duì)實(shí)驗(yàn)數(shù)據(jù)集郵件的關(guān)聯(lián)頻度和點(diǎn)度中心度進(jìn)行統(tǒng)計(jì)分析后，按規(guī)律將節(jié)點(diǎn)的關(guān)聯(lián)頻度的閾值設(shè)置為2，初始的中心節(jié)點(diǎn)的度的閾值設(shè)置為20。通過(guò)實(shí)驗(yàn)得到優(yōu)化前后的兩組實(shí)驗(yàn)數(shù)據(jù)，分別對(duì)它們的有效直徑和平均距離做對(duì)比，以驗(yàn)證第4節(jié)中所述社區(qū)劃分優(yōu)化策略的有效性。如圖2和圖3所示，圖中均按照值由大到小排列，長(zhǎng)尾部分的社區(qū)省略。

由以上看出，優(yōu)化后的算法對(duì)郵件社區(qū)劃分在質(zhì)量上有提高。郵件社區(qū)總的平均距離，優(yōu)化前為3.1462，優(yōu)化后為2.8784，有明顯的減小；優(yōu)化前部分社區(qū)有效直徑過(guò)大，最大為8，優(yōu)化后有效直徑的大小均不大于6，絕大部分不大于5，社區(qū)大小更加均勻。

實(shí)驗(yàn)結(jié)果表明，算法的優(yōu)化有利于社區(qū)劃分，縮小了社區(qū)的有效直徑和平均距離，提高了聚類效果。

5.2 郵箱社區(qū)有向圖劃分

本實(shí)驗(yàn)的目標(biāo)是以基于通信次數(shù)的郵件劃分算法為基礎(chǔ)，來(lái)測(cè)試基于MAS的劃分算法性能，并以基于通信次數(shù)相似度的劃分算法為例進(jìn)行對(duì)比實(shí)驗(yàn)。其中，預(yù)設(shè)聚類數(shù)目k=500，選取一個(gè)月、兩個(gè)月、三個(gè)月的時(shí)長(zhǎng)跨度，分別進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如表1。

其中三個(gè)月實(shí)驗(yàn)有效直徑和平均距離的對(duì)比結(jié)果如圖4和5所示。

從兩圖中不難看出：基于相似度度量的聚類算法構(gòu)建的社區(qū)內(nèi)部有效直徑基本保持在5以下，平均距離保持在4.0以下。由表1中可以看出，隨著時(shí)間跨度的增加，數(shù)據(jù)集合增大，穩(wěn)定郵件社區(qū)有效直徑和平均距離逐漸縮小并趨于穩(wěn)定。

同時(shí)，基于MAS的聚類算法有效的加入了郵箱間通聯(lián)行為活躍度上的特征，用MAS計(jì)算出的結(jié)果更能體現(xiàn)郵件間的時(shí)間趨近程度，所以基于MAS的聚類算法發(fā)現(xiàn)的社區(qū)，其有效直徑和平均距離更小更穩(wěn)定，能有效發(fā)現(xiàn)高質(zhì)量的社區(qū)。

其中，基于通信次數(shù)的聚類算法和基于MAS的算法指導(dǎo)郵件社區(qū)聚類，在三個(gè)月時(shí)間跨度基礎(chǔ)上得到的平均有效直徑分別為3.967和3.833，整體平均距離為2.966和2.866。實(shí)驗(yàn)結(jié)果顯示：使用MAS方法，郵件網(wǎng)絡(luò)中所有社區(qū)的平均有效直徑降低了約0.13個(gè)單位，平均距離減小了近0.10個(gè)單位。

6 分析與評(píng)估

郵件社區(qū)的劃分是一種圖聚類問(wèn)題[14]，本文中算法是一種動(dòng)態(tài)模型聚類算法，通過(guò)社區(qū)中心的動(dòng)態(tài)調(diào)整來(lái)逐步優(yōu)化郵件社區(qū)，具有更快的社區(qū)聚類速度，同時(shí)引入了基于時(shí)間的相似度擬合，更符合郵件通聯(lián)的特征。

本文通過(guò)有效數(shù)據(jù)來(lái)驗(yàn)證MAS算法的合理性和有效性，并與最為常見(jiàn)的基于通信次數(shù)的郵件社區(qū)聚類算法進(jìn)行比較，進(jìn)一步驗(yàn)證MAS算法郵件社區(qū)劃分具有更優(yōu)的性能，特別是在明顯時(shí)間跨度上具有更好的性能。

由以上實(shí)驗(yàn)可以看出，郵件社區(qū)就是一種介于規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)的小世界網(wǎng)絡(luò)[2]。郵件社區(qū)的節(jié)點(diǎn)具有高度耦合性，符合網(wǎng)絡(luò)社區(qū)的特性，呈現(xiàn)六度分離[2]特征。而各個(gè)社區(qū)之間的關(guān)聯(lián)相對(duì)松散，并且相似度低于郵件社區(qū)內(nèi)部相似度，說(shuō)明郵件網(wǎng)絡(luò)中的確具有社區(qū)性質(zhì)，并且該郵件社區(qū)劃分算法及其優(yōu)化方法具有合理性。郵件的社區(qū)性質(zhì)和劃分結(jié)果為進(jìn)一步的社區(qū)分析、社區(qū)節(jié)點(diǎn)行為分析提供了有力的基礎(chǔ)。

7 結(jié)語(yǔ)

本算法得到的結(jié)果表明利MAS算法進(jìn)行郵件社區(qū)劃分是有效并且合理的。實(shí)驗(yàn)結(jié)果表明，郵件社區(qū)網(wǎng)絡(luò)與現(xiàn)實(shí)社會(huì)網(wǎng)絡(luò)是同構(gòu)的，呈現(xiàn)明顯的聚集現(xiàn)象。MAS算法具有較高準(zhǔn)確性，僅從郵件通聯(lián)特性出發(fā)，涉及較少的郵件內(nèi)容分析，從而算法更為簡(jiǎn)潔易于擴(kuò)展。下一步工作從算法上，可以研究該算法的擴(kuò)展，MAS與其余相似度算法的結(jié)合；從步驟上，可以研究郵件社區(qū)中發(fā)現(xiàn)主題內(nèi)容和社區(qū)的核心人物的分析，并進(jìn)一步考慮進(jìn)行分布式擴(kuò)展以增加社區(qū)劃分的效率。

參考文獻(xiàn)：

[1]Zhang Yanchun，Yu X J，Hou Jingyu.Web communities： Analysis and construction [M].Berlin：Springer，2005：56-92.

[2]司徒俊峰.Internet的小世界網(wǎng)絡(luò)研究[J].情報(bào)技術(shù)，2004，23（12）：86-88.

[3]Lin Hui，F(xiàn)an Weiguo， Wallace L. An Empirical study of web-based knowledge community success[C].//Proceedings of the 40th Annual Hawaii International Conference on System Sciences：HICSS 2007. Washington： IEEE Computer Society，2007：178.

[4]康書龍.基于用戶行為及關(guān)系的社交網(wǎng)絡(luò)節(jié)點(diǎn)影響力評(píng)價(jià)[D].北京：北京郵電大學(xué)，2011.

[5]熊會(huì)會(huì).基于復(fù)雜網(wǎng)絡(luò)的微博客信息傳播機(jī)制研究[D].廣東：華南理工大學(xué)，2012.

[6]伊衍騰，李學(xué)明，蔡孟松.基于用戶關(guān)系與屬性的微博意見(jiàn)領(lǐng)袖挖掘方法[J].計(jì)算機(jī)工程，2013，39（4）：184-189.

[7]Fulu Li，Mo-Han Hsieh. An Empirical Study of Clustering Behavior of Spammers and Group-based Anti-Spam Strategies[C].//Proceedings of the 40th Annual Hawaii International Conference on System Sciences： HICSS 2007. Washington：IEEE Computer Society，2007：73.

[8]HSIAOAW F， CHANG TM， HUA GH. A cluster-based approach to filtering spam under skewed class distributions[C]//Proceedings of the 40th Annual Hawaii International Conference on System Sciences： HICSS 2007. Washington： IEEE Computer Society，2007：53.

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

[10]李軍利，趙紅領(lǐng)，范明.郵件社區(qū)劃分和小世界網(wǎng)絡(luò)[J].計(jì)算機(jī)應(yīng)用，2008，28（6）：146-149

[11]Freeman L C （1979）. Centrality in social networks： Conceptual clarification[M]. Social Networks， 1（3）， 215-239.

[12]Newman M E J（2005）， A measure of betweenness centrality based on random walks[M].Social Network， 27， pp. 39-54.

[13]Girvan M，Newman M E J. Community structure in social and biological networks[J].In Proceedings of the National Academy of Sciences of the United States of America，USA，2002.

[14]Han J，M Kamber.范明，孟小峰，譯.數(shù)據(jù)挖掘：概念與技術(shù)[M].北京：機(jī)械工業(yè)出版社，2001.

作者簡(jiǎn)介：高源（1988-），男，四川省江油市人，碩士研究生，主要研究領(lǐng)域：數(shù)據(jù)挖掘。

作者單位：華北計(jì)算技術(shù)研究所 信息技術(shù)應(yīng)用系統(tǒng)部，北京 100083