论文部分内容阅读
摘 要：为深入挖掘互联网邮件通联关系，提出了一种基于邮箱活跃度的邮件社区划分算法（MAS），并研究了邮件社区的性质与特征。算法采用基于邮箱通联活跃频度的余弦相似度评估邮箱之间通联关系的相似性，并通过层次聚类的方法指导邮件社区聚类，然后对社区中心进行动态调整以完成划分。在有效模拟数据集上的实验表明，该算法有效、合理，可以应用于实际的挖掘应用。
关键词：邮件社区；社会网络分析；数据挖掘；活跃度
中图分类号：TP393.098
现代社会中，互联网已经深入到人们的生活的各个方面，成为人们生活、工作不可缺少的一部分。人们在网络间的通信方式也多种多样，其中电子邮件是主要通信工具之一。电子邮件之间的相互通信在互联网上构成了庞大的邮件网络。在这个网络中，包含大量电子形式的个人信息以及邮箱用户之间相互通信关系。整个邮件网络又可以划分出若干的邮件网络社区。网络社区[1]表示在虚拟网络中，网民根据共同的兴趣而形成的真实的社会团体，具有实际社区的基本要素，包括人群（网民）、活动区域（网络）、互动行为、共同的社会心理基础等。网民在一定的网络空间内，围绕共同的需要和兴趣进行交流互动活动，相互之间构成的网络社区具有六度分离[2]的特性。邮件社区作为一种网络社区，也与现实中对应的社会关系网络是同构的，能够反映出社会网络中网民活动的社区通信信息和相互交流兴趣主题。目前有关网络社区[1，3]的研究较多，如网页社区研究，主要包括关联网页的查找、噪声网页的消除和网页关系聚类等；又如现在应用较多的微博网络社区研究，包括微博热点话题发现和基于主题聚类[4-6]等；再如垃圾邮件的识别与过滤等[7，8]。但是在邮件社区中，直接利用邮件通联关系进行社会网络构建的研究和应用相对比较薄弱，然而邮件社区研究对于发现邮件社区中的犯罪网络及分析网络核心成员等实际应用具有重要意义。
1 邮箱活跃度分析
邮件网络是一种社区网络，由众多邮件社区构成。邮件社区是由若干邮箱及邮箱之间的相互通信组成，如果将邮箱看作是节点，而通信关系看作是边，则邮件社区可以表示为一张图，有如下与关系网络[9]类似方法的定义。
定义1 邮件网络表示为加权图G=（V，E），其中V是顶点集合，E是边集合。在邮件网络中，v∈V代表一个邮箱，e=（vi，vj）∈E表示邮箱vi和vj之间存在通信联系，而w（e）（其中e=（vi，vj））表示邮箱vi到vj的关联频度，可以用邮箱vi和vj的通信次数表示。设Gk是G的子图，表示一个社区。社区Gk的直径，记作D（Gk），定义为Gk中所有节点对之间距离的最大值。而社区Gk的节点对的平均距离davg（Gk）是所有节点对之间距离的平均值。社区Gk的有效直径记作Dval（Gk），对于社区Gk中至少90%以上节点对，它们的距离小于或等于Dval（Gk）。
为分析研究邮件社区性质，本文使用了一组有效的互联网邮件模拟数据，能真实反映邮箱间通联关系特性。该数据集包含90天共200万邮件通联数据。对该数据集进行邮箱发送活动统计如下图所示，部分通联次数为1的邮箱未显示。统计发现，一共4.4W邮箱中，有4千个邮箱的主动发送次数大于20。这部分邮箱明显属于高活跃邮箱。其余邮箱组成了图中“长尾”部分。
仅用邮箱的通联次数来分析不同邮箱的特性显然是不足的。本文考虑引入邮箱的活跃度，定义邮箱的活跃特性。
定义2 活跃度t，表示目标邮箱在一段时间内的综合收发邮件的频度。依据现实社会人物的活动规律，对时间粒度划分的最小单位为天，定义活跃度t如下
其中tsend是发送邮件的活跃度，trecv是接收邮件的活跃度，α表示活跃系数。考虑发送邮件者作为主动方，而接收邮件作为被动方，发送邮件对活跃度贡献应略高于接收邮件，因此引入活跃系数α。发送活跃度tsend和接收活跃度trecv的计算方式相同，如下式：
其中si为第i天发送/接收邮件的次数，K为平衡因子，当没有接收和发送邮件时设si=1。该公式中，因为si不能为0（否则活跃度为零），所以不能区分第i天发送了一封邮件和没有发送的情况，因此引入了K平衡因子，使得两种情况有活跃度的差异。如果第i天发送/接收邮件的次数为零，则取si=1（不能为0），ki=1；反之，若si≠0，则si保持不变，ki=0；λ为递减权重，本文中取值λ=0.3，用于平衡因si=0时带来的误差。
活跃度可以很好度量突发性发送邮件的邮箱和平衡性发送邮件的邮箱之间的区别。例如：邮箱A仅在一个月某一天发送60封邮件，而邮箱B在一个月每天都会发送1到3封共60封邮件。显然邮箱B具有更高的活跃性，其计算得活跃度也更高。
定义3 邮箱间的活跃频度dt，表示两个邮箱之间在一段时间内综合收发邮件的频率，定义如下。
与活跃度定义相同，tsend是发送邮件的活跃度，trecv是接收邮件的活跃度，α表示活跃系数。本文提到活跃度，不特殊说明均指两邮箱间的活跃频度。
2 基于活跃度的相似度
邮件社区具有一定的小世界特征[10]。即同一个邮件社区内，不同邮箱之间进行通信的行为具有很高的相似性；同一邮件社区内，必然会存在一个或多个具有高活跃性的邮箱，这些邮箱直接或者间接加强其他邮箱之间的联系；同一邮件社区内，邮箱与一定数量的同一社区其他邮箱存在直接通信联系更为紧密。这些邮箱的特性，我们可以使用邮箱的相似度来度量。而邮件社区的划分正是以邮箱间相似度为基础，即相似特征的邮箱即划为同一社区。
邮箱与邮箱之间的通信行为相似度由两个邮箱与其他邮箱之间的关系来度量。设G表示邮件网络，其中包含n个邮箱，分别为v1，v2，…，vn，那么G可以表示为一个n×n矩阵X。X的元素xij则表示邮箱vi和邮箱vj之间的关系权重，xij为某时间段内邮箱vi向邮箱vj发送邮件的活跃度。xij不仅仅只是通联次数的关系，还包含了两个邮箱之间活跃频繁次数的特征。矩阵X中，第i个行向量Xi={xi1，xi2，…，xin}记录了邮箱vi与社区中其他邮箱的活跃度。由于一个邮箱一般不向自己发送邮件，这导致矩阵X的对角线上元素大部分为0。本文使用余弦定义来计算邮箱vi和邮箱vj的相似度sim（vi，vj），即有下式： 其中Xi、Xj表示邮箱vi和邮箱vj在矩阵X中对应的行向量。由于主对角线元素为大部分为0的影响，向量Xi与Xj的点积使得邮箱vi和邮箱vj相互通信大部分会为0而被忽略，为此本文将xii都置1，是相似度更有效。
由以上相似度可知，对于邮箱vi，自我相似度为1，即sim（vi，vi）=1；与邮箱vj共同关联的邮箱越多，对应关联邮箱通联关系的活跃度越接近，则通信联系越相似，即sim（vi，vj）越接近于1；与邮箱vj没有共同关联的邮箱时，sim（vi，vj）=0。
定义4 在一个包含n个节点v1，v2，…，vn的社区中，社区中心c表示为c=max（DDvi+DBvi+DCvi），其中DDvi表示点度中心度（degree centrality）、DBvi表示中间中心度（betweenness centrality）和DCvi表示接近中心度（closeness centrality）[11-13]。c是社区中的节点与其他节点相互关联度最高的节点，是社区的中心节点。
3 邮件社区算法改进
有了相似度的计算方法，就可以采用基于活跃度的邮件社区划分算法MAS（Mail Activity Similarity）对邮件社区进行划分。算法的主要思想，是采用基于活跃度度量邮箱相似性建立社区并动态调整社区中心，本文采用的社区划分算法实际上是一种基于邮件行为相似度的聚类算法。
3.1 社区划分算法
正如前文所述，本文用稀疏矩阵X表示一个社区网络，并用向量Xi表示社区网络中的某一邮箱vi的与网络中其余邮箱通联关系的活跃度集合。本文描述邮件社区划分的算法如下。
算法1 基于MAS社区划分算法。
输入：由n×n的矩阵X表示的邮件社区网络
输出：邮件社区划分结果。每一项包括邮箱及其所属的社区序号
方法：
1） 输入划分社区数目k；
2） 选取k个节点作为初始社区中心节点；
3） repeat
4） for邮件网络中的每个节点xi： //xi为社区网络中的节点
5） for每个社区中心cj //寻找与节点xi相似度最大的社区中心cj
6） if 节点xi与社区中心cj具有最大相似度， then
7） 将节点xi的社区序号设置为j；
8） end if
9） end for
10） end for
11） for社区网络中的每个社区community[j]
12） 调整该社区的社区中心cj； //cj的调整方法参见文中定义4
13） end for
14） until所有的社区中心不再改变；
15）输出社区划分结果；
3.2 动态调整中心改进
动态中心调整是一个及其消耗时间的过程，当邮件网络增大时，每一个节点都会再次与所有社区中心做相似比较。这个过程及其耗时，本文考虑缩减比较次数来提高划分效率。
将每个社区再次按照距离划分出邻近社区，当社区或者这个社区的邻近社区中心节点改变时，才有必要计算社区内节点到邻近社区中心节点的距离，而其余社区不再考虑。我们将算法1作修改如下：
算法2 基于MAS社区划分算法改进。
输入：由n×n的矩阵X表示的邮件社区网络
输出：邮件社区划分结果。每一项包括邮箱及其所属的社区序号
方法：
1） 输入划分社区数目k；
2） 选取k个节点作为初始社区中心节点，初始化临近社区为所有社区，并网络节点所属划为某一社区；
3） repeat
4） for邮件网络中的每个节点xi： //xi为社区网络中的节点
5） for xi所属社区所有邻近社区中心cj //寻找与节点xi相似度最大的邻近社区中心cj
6） if 节点xi与社区中心cj具有最大相似度，then
7） 将节点xi的社区序号设置为j；
8） end if
9） end for
10） end for
11） for社区网络中的每个社区community[j]
12） 调整该社区的社区中心cj；
13） 调整邻近社区集合
14） end for
15） until所有的社区中心不再改变；
16） 输出社区划分结果；
4 优化调整
邮件网络中必然会存在离散的节点，这样的节点与网络中的其他节点关联频度较小，与其他任意一个社区中心的相似度都很低，影响社区划分的质量；邮件社区初始社区中心节点的选取也影响社区划分的质量；矩阵计算时间复杂度较高，特别随着网络规模增大，矩阵计算需要的时间和空间消耗急剧增大。
针对这些问题，本文采取优化解决如下：
（1）对噪声节点进行预处理。在邮件网络中，存在少数极其不活跃的节点，称之为噪声节点或孤立节点。在社区划分中将关联频度小于某个阈值的噪声节点过滤掉，以避免社区划分因噪声节点的存在而影响整个社区划分的质量。
（2）选择合理的初始社区中心节点。在初始化阶段，本文挑选在整个网络中边的度数大于某个阈值的k个节点作为最初的中心节点，并保证这些节点在步长为2的路径上不相关联。这极大地减少了程序中更新中心点迭代次数，大大降低了时间复杂度，实验表明该方法可有效地缩小各个社区的有效直径和平均距离，使得各个社区划分的质量得到提高。 （3）使用稀疏矩阵的表示和计算，从而简化矩阵计算带来的巨大开销。保证实验在可控时间范围内进行。同时为降低计算复杂度，对大数的幂运算和乘方运算采用近似运算替代，缩短计算时间。
下面针对具体优化进行实验。
5 实验
基于以上理论基础以及优化策略，对一组模拟邮件网络数据进行分析，该网络包括90天共200万邮件通联数据。实验中将社区网络用有向图表示。
本实验的实验环境为3.40GHz Inter（R） Core（TM） i7 3770 CPU，4G内存，1TB硬盘，操作系统为Windows XP SP3，程序开发平台为Python2.7。社区划分结果的每一项由两个字段组成：邮箱和社区编号CID。
5.1 优化有效性验证
采用第3节MAS改进算法进行社区划分实验。对实验数据集邮件的关联频度和点度中心度进行统计分析后，按规律将节点的关联频度的阈值设置为2，初始的中心节点的度的阈值设置为20。通过实验得到优化前后的两组实验数据，分别对它们的有效直径和平均距离做对比，以验证第4节中所述社区划分优化策略的有效性。如图2和图3所示，图中均按照值由大到小排列，长尾部分的社区省略。
由以上看出，优化后的算法对邮件社区划分在质量上有提高。邮件社区总的平均距离，优化前为3.1462，优化后为2.8784，有明显的减小；优化前部分社区有效直径过大，最大为8，优化后有效直径的大小均不大于6，绝大部分不大于5，社区大小更加均匀。
实验结果表明，算法的优化有利于社区划分，缩小了社区的有效直径和平均距离，提高了聚类效果。
5.2 邮箱社区有向图划分
本实验的目标是以基于通信次数的邮件划分算法为基础，来测试基于MAS的划分算法性能，并以基于通信次数相似度的划分算法为例进行对比实验。其中，预设聚类数目k=500，选取一个月、两个月、三个月的时长跨度，分别进行实验。实验结果如表1。
其中三个月实验有效直径和平均距离的对比结果如图4和5所示。
从两图中不难看出：基于相似度度量的聚类算法构建的社区内部有效直径基本保持在5以下，平均距离保持在4.0以下。由表1中可以看出，随着时间跨度的增加，数据集合增大，稳定邮件社区有效直径和平均距离逐渐缩小并趋于稳定。
同时，基于MAS的聚类算法有效的加入了邮箱间通联行为活跃度上的特征，用MAS计算出的结果更能体现邮件间的时间趋近程度，所以基于MAS的聚类算法发现的社区，其有效直径和平均距离更小更稳定，能有效发现高质量的社区。
其中，基于通信次数的聚类算法和基于MAS的算法指导邮件社区聚类，在三个月时间跨度基础上得到的平均有效直径分别为3.967和3.833，整体平均距离为2.966和2.866。实验结果显示：使用MAS方法，邮件网络中所有社区的平均有效直径降低了约0.13个单位，平均距离减小了近0.10个单位。
6 分析与评估
邮件社区的划分是一种图聚类问题[14]，本文中算法是一种动态模型聚类算法，通过社区中心的动态调整来逐步优化邮件社区，具有更快的社区聚类速度，同时引入了基于时间的相似度拟合，更符合邮件通联的特征。
本文通过有效数据来验证MAS算法的合理性和有效性，并与最为常见的基于通信次数的邮件社区聚类算法进行比较，进一步验证MAS算法邮件社区划分具有更优的性能，特别是在明显时间跨度上具有更好的性能。
由以上实验可以看出，邮件社区就是一种介于规则网络和随机网络的小世界网络[2]。邮件社区的节点具有高度耦合性，符合网络社区的特性，呈现六度分离[2]特征。而各个社区之间的关联相对松散，并且相似度低于邮件社区内部相似度，说明邮件网络中的确具有社区性质，并且该邮件社区划分算法及其优化方法具有合理性。邮件的社区性质和划分结果为进一步的社区分析、社区节点行为分析提供了有力的基础。
7 结语
本算法得到的结果表明利MAS算法进行邮件社区划分是有效并且合理的。实验结果表明，邮件社区网络与现实社会网络是同构的，呈现明显的聚集现象。MAS算法具有较高准确性，仅从邮件通联特性出发，涉及较少的邮件内容分析，从而算法更为简洁易于扩展。下一步工作从算法上，可以研究该算法的扩展，MAS与其余相似度算法的结合；从步骤上，可以研究邮件社区中发现主题内容和社区的核心人物的分析，并进一步考虑进行分布式扩展以增加社区划分的效率。
参考文献：
[1]Zhang Yanchun，Yu X J，Hou Jingyu.Web communities： Analysis and construction [M].Berlin：Springer，2005：56-92.
[2]司徒俊峰.Internet的小世界网络研究[J].情报技术，2004，23（12）：86-88.
[3]Lin Hui，Fan 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]康书龙.基于用户行为及关系的社交网络节点影响力评价[D].北京：北京邮电大学，2011.
[5]熊会会.基于复杂网络的微博客信息传播机制研究[D].广东：华南理工大学，2012.
[6]伊衍腾，李学明，蔡孟松.基于用户关系与属性的微博意见领袖挖掘方法[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]陈绍宇，宋佳兴，刘卫东等.关系网格：一种基于小世界模型的社会关系网络[J].计算机应用研究，2006，23（5）：194-197.
[10]李军利，赵红领，范明.邮件社区划分和小世界网络[J].计算机应用，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.范明，孟小峰，译.数据挖掘：概念与技术[M].北京：机械工业出版社，2001.
作者简介：高源（1988-），男，四川省江油市人，硕士研究生，主要研究领域：数据挖掘。
作者单位：华北计算技术研究所 信息技术应用系统部，北京 100083
关键词：邮件社区；社会网络分析；数据挖掘；活跃度
中图分类号：TP393.098
现代社会中，互联网已经深入到人们的生活的各个方面，成为人们生活、工作不可缺少的一部分。人们在网络间的通信方式也多种多样，其中电子邮件是主要通信工具之一。电子邮件之间的相互通信在互联网上构成了庞大的邮件网络。在这个网络中，包含大量电子形式的个人信息以及邮箱用户之间相互通信关系。整个邮件网络又可以划分出若干的邮件网络社区。网络社区[1]表示在虚拟网络中，网民根据共同的兴趣而形成的真实的社会团体，具有实际社区的基本要素，包括人群（网民）、活动区域（网络）、互动行为、共同的社会心理基础等。网民在一定的网络空间内，围绕共同的需要和兴趣进行交流互动活动，相互之间构成的网络社区具有六度分离[2]的特性。邮件社区作为一种网络社区，也与现实中对应的社会关系网络是同构的，能够反映出社会网络中网民活动的社区通信信息和相互交流兴趣主题。目前有关网络社区[1，3]的研究较多，如网页社区研究，主要包括关联网页的查找、噪声网页的消除和网页关系聚类等；又如现在应用较多的微博网络社区研究，包括微博热点话题发现和基于主题聚类[4-6]等；再如垃圾邮件的识别与过滤等[7，8]。但是在邮件社区中，直接利用邮件通联关系进行社会网络构建的研究和应用相对比较薄弱，然而邮件社区研究对于发现邮件社区中的犯罪网络及分析网络核心成员等实际应用具有重要意义。
1 邮箱活跃度分析
邮件网络是一种社区网络，由众多邮件社区构成。邮件社区是由若干邮箱及邮箱之间的相互通信组成，如果将邮箱看作是节点，而通信关系看作是边，则邮件社区可以表示为一张图，有如下与关系网络[9]类似方法的定义。
定义1 邮件网络表示为加权图G=（V，E），其中V是顶点集合，E是边集合。在邮件网络中，v∈V代表一个邮箱，e=（vi，vj）∈E表示邮箱vi和vj之间存在通信联系，而w（e）（其中e=（vi，vj））表示邮箱vi到vj的关联频度，可以用邮箱vi和vj的通信次数表示。设Gk是G的子图，表示一个社区。社区Gk的直径，记作D（Gk），定义为Gk中所有节点对之间距离的最大值。而社区Gk的节点对的平均距离davg（Gk）是所有节点对之间距离的平均值。社区Gk的有效直径记作Dval（Gk），对于社区Gk中至少90%以上节点对，它们的距离小于或等于Dval（Gk）。
为分析研究邮件社区性质，本文使用了一组有效的互联网邮件模拟数据，能真实反映邮箱间通联关系特性。该数据集包含90天共200万邮件通联数据。对该数据集进行邮箱发送活动统计如下图所示，部分通联次数为1的邮箱未显示。统计发现，一共4.4W邮箱中，有4千个邮箱的主动发送次数大于20。这部分邮箱明显属于高活跃邮箱。其余邮箱组成了图中“长尾”部分。
仅用邮箱的通联次数来分析不同邮箱的特性显然是不足的。本文考虑引入邮箱的活跃度，定义邮箱的活跃特性。
定义2 活跃度t，表示目标邮箱在一段时间内的综合收发邮件的频度。依据现实社会人物的活动规律，对时间粒度划分的最小单位为天，定义活跃度t如下
其中tsend是发送邮件的活跃度，trecv是接收邮件的活跃度，α表示活跃系数。考虑发送邮件者作为主动方，而接收邮件作为被动方，发送邮件对活跃度贡献应略高于接收邮件，因此引入活跃系数α。发送活跃度tsend和接收活跃度trecv的计算方式相同，如下式：
其中si为第i天发送/接收邮件的次数，K为平衡因子，当没有接收和发送邮件时设si=1。该公式中，因为si不能为0（否则活跃度为零），所以不能区分第i天发送了一封邮件和没有发送的情况，因此引入了K平衡因子，使得两种情况有活跃度的差异。如果第i天发送/接收邮件的次数为零，则取si=1（不能为0），ki=1；反之，若si≠0，则si保持不变，ki=0；λ为递减权重，本文中取值λ=0.3，用于平衡因si=0时带来的误差。
活跃度可以很好度量突发性发送邮件的邮箱和平衡性发送邮件的邮箱之间的区别。例如：邮箱A仅在一个月某一天发送60封邮件，而邮箱B在一个月每天都会发送1到3封共60封邮件。显然邮箱B具有更高的活跃性，其计算得活跃度也更高。
定义3 邮箱间的活跃频度dt，表示两个邮箱之间在一段时间内综合收发邮件的频率，定义如下。
与活跃度定义相同，tsend是发送邮件的活跃度，trecv是接收邮件的活跃度，α表示活跃系数。本文提到活跃度，不特殊说明均指两邮箱间的活跃频度。
2 基于活跃度的相似度
邮件社区具有一定的小世界特征[10]。即同一个邮件社区内，不同邮箱之间进行通信的行为具有很高的相似性；同一邮件社区内，必然会存在一个或多个具有高活跃性的邮箱，这些邮箱直接或者间接加强其他邮箱之间的联系；同一邮件社区内，邮箱与一定数量的同一社区其他邮箱存在直接通信联系更为紧密。这些邮箱的特性，我们可以使用邮箱的相似度来度量。而邮件社区的划分正是以邮箱间相似度为基础，即相似特征的邮箱即划为同一社区。
邮箱与邮箱之间的通信行为相似度由两个邮箱与其他邮箱之间的关系来度量。设G表示邮件网络，其中包含n个邮箱，分别为v1，v2，…，vn，那么G可以表示为一个n×n矩阵X。X的元素xij则表示邮箱vi和邮箱vj之间的关系权重，xij为某时间段内邮箱vi向邮箱vj发送邮件的活跃度。xij不仅仅只是通联次数的关系，还包含了两个邮箱之间活跃频繁次数的特征。矩阵X中，第i个行向量Xi={xi1，xi2，…，xin}记录了邮箱vi与社区中其他邮箱的活跃度。由于一个邮箱一般不向自己发送邮件，这导致矩阵X的对角线上元素大部分为0。本文使用余弦定义来计算邮箱vi和邮箱vj的相似度sim（vi，vj），即有下式： 其中Xi、Xj表示邮箱vi和邮箱vj在矩阵X中对应的行向量。由于主对角线元素为大部分为0的影响，向量Xi与Xj的点积使得邮箱vi和邮箱vj相互通信大部分会为0而被忽略，为此本文将xii都置1，是相似度更有效。
由以上相似度可知，对于邮箱vi，自我相似度为1，即sim（vi，vi）=1；与邮箱vj共同关联的邮箱越多，对应关联邮箱通联关系的活跃度越接近，则通信联系越相似，即sim（vi，vj）越接近于1；与邮箱vj没有共同关联的邮箱时，sim（vi，vj）=0。
定义4 在一个包含n个节点v1，v2，…，vn的社区中，社区中心c表示为c=max（DDvi+DBvi+DCvi），其中DDvi表示点度中心度（degree centrality）、DBvi表示中间中心度（betweenness centrality）和DCvi表示接近中心度（closeness centrality）[11-13]。c是社区中的节点与其他节点相互关联度最高的节点，是社区的中心节点。
3 邮件社区算法改进
有了相似度的计算方法，就可以采用基于活跃度的邮件社区划分算法MAS（Mail Activity Similarity）对邮件社区进行划分。算法的主要思想，是采用基于活跃度度量邮箱相似性建立社区并动态调整社区中心，本文采用的社区划分算法实际上是一种基于邮件行为相似度的聚类算法。
3.1 社区划分算法
正如前文所述，本文用稀疏矩阵X表示一个社区网络，并用向量Xi表示社区网络中的某一邮箱vi的与网络中其余邮箱通联关系的活跃度集合。本文描述邮件社区划分的算法如下。
算法1 基于MAS社区划分算法。
输入：由n×n的矩阵X表示的邮件社区网络
输出：邮件社区划分结果。每一项包括邮箱及其所属的社区序号
方法：
1） 输入划分社区数目k；
2） 选取k个节点作为初始社区中心节点；
3） repeat
4） for邮件网络中的每个节点xi： //xi为社区网络中的节点
5） for每个社区中心cj //寻找与节点xi相似度最大的社区中心cj
6） if 节点xi与社区中心cj具有最大相似度， then
7） 将节点xi的社区序号设置为j；
8） end if
9） end for
10） end for
11） for社区网络中的每个社区community[j]
12） 调整该社区的社区中心cj； //cj的调整方法参见文中定义4
13） end for
14） until所有的社区中心不再改变；
15）输出社区划分结果；
3.2 动态调整中心改进
动态中心调整是一个及其消耗时间的过程，当邮件网络增大时，每一个节点都会再次与所有社区中心做相似比较。这个过程及其耗时，本文考虑缩减比较次数来提高划分效率。
将每个社区再次按照距离划分出邻近社区，当社区或者这个社区的邻近社区中心节点改变时，才有必要计算社区内节点到邻近社区中心节点的距离，而其余社区不再考虑。我们将算法1作修改如下：
算法2 基于MAS社区划分算法改进。
输入：由n×n的矩阵X表示的邮件社区网络
输出：邮件社区划分结果。每一项包括邮箱及其所属的社区序号
方法：
1） 输入划分社区数目k；
2） 选取k个节点作为初始社区中心节点，初始化临近社区为所有社区，并网络节点所属划为某一社区；
3） repeat
4） for邮件网络中的每个节点xi： //xi为社区网络中的节点
5） for xi所属社区所有邻近社区中心cj //寻找与节点xi相似度最大的邻近社区中心cj
6） if 节点xi与社区中心cj具有最大相似度，then
7） 将节点xi的社区序号设置为j；
8） end if
9） end for
10） end for
11） for社区网络中的每个社区community[j]
12） 调整该社区的社区中心cj；
13） 调整邻近社区集合
14） end for
15） until所有的社区中心不再改变；
16） 输出社区划分结果；
4 优化调整
邮件网络中必然会存在离散的节点，这样的节点与网络中的其他节点关联频度较小，与其他任意一个社区中心的相似度都很低，影响社区划分的质量；邮件社区初始社区中心节点的选取也影响社区划分的质量；矩阵计算时间复杂度较高，特别随着网络规模增大，矩阵计算需要的时间和空间消耗急剧增大。
针对这些问题，本文采取优化解决如下：
（1）对噪声节点进行预处理。在邮件网络中，存在少数极其不活跃的节点，称之为噪声节点或孤立节点。在社区划分中将关联频度小于某个阈值的噪声节点过滤掉，以避免社区划分因噪声节点的存在而影响整个社区划分的质量。
（2）选择合理的初始社区中心节点。在初始化阶段，本文挑选在整个网络中边的度数大于某个阈值的k个节点作为最初的中心节点，并保证这些节点在步长为2的路径上不相关联。这极大地减少了程序中更新中心点迭代次数，大大降低了时间复杂度，实验表明该方法可有效地缩小各个社区的有效直径和平均距离，使得各个社区划分的质量得到提高。 （3）使用稀疏矩阵的表示和计算，从而简化矩阵计算带来的巨大开销。保证实验在可控时间范围内进行。同时为降低计算复杂度，对大数的幂运算和乘方运算采用近似运算替代，缩短计算时间。
下面针对具体优化进行实验。
5 实验
基于以上理论基础以及优化策略，对一组模拟邮件网络数据进行分析，该网络包括90天共200万邮件通联数据。实验中将社区网络用有向图表示。
本实验的实验环境为3.40GHz Inter（R） Core（TM） i7 3770 CPU，4G内存，1TB硬盘，操作系统为Windows XP SP3，程序开发平台为Python2.7。社区划分结果的每一项由两个字段组成：邮箱和社区编号CID。
5.1 优化有效性验证
采用第3节MAS改进算法进行社区划分实验。对实验数据集邮件的关联频度和点度中心度进行统计分析后，按规律将节点的关联频度的阈值设置为2，初始的中心节点的度的阈值设置为20。通过实验得到优化前后的两组实验数据，分别对它们的有效直径和平均距离做对比，以验证第4节中所述社区划分优化策略的有效性。如图2和图3所示，图中均按照值由大到小排列，长尾部分的社区省略。
由以上看出，优化后的算法对邮件社区划分在质量上有提高。邮件社区总的平均距离，优化前为3.1462，优化后为2.8784，有明显的减小；优化前部分社区有效直径过大，最大为8，优化后有效直径的大小均不大于6，绝大部分不大于5，社区大小更加均匀。
实验结果表明，算法的优化有利于社区划分，缩小了社区的有效直径和平均距离，提高了聚类效果。
5.2 邮箱社区有向图划分
本实验的目标是以基于通信次数的邮件划分算法为基础，来测试基于MAS的划分算法性能，并以基于通信次数相似度的划分算法为例进行对比实验。其中，预设聚类数目k=500，选取一个月、两个月、三个月的时长跨度，分别进行实验。实验结果如表1。
其中三个月实验有效直径和平均距离的对比结果如图4和5所示。
从两图中不难看出：基于相似度度量的聚类算法构建的社区内部有效直径基本保持在5以下，平均距离保持在4.0以下。由表1中可以看出，随着时间跨度的增加，数据集合增大，稳定邮件社区有效直径和平均距离逐渐缩小并趋于稳定。
同时，基于MAS的聚类算法有效的加入了邮箱间通联行为活跃度上的特征，用MAS计算出的结果更能体现邮件间的时间趋近程度，所以基于MAS的聚类算法发现的社区，其有效直径和平均距离更小更稳定，能有效发现高质量的社区。
其中，基于通信次数的聚类算法和基于MAS的算法指导邮件社区聚类，在三个月时间跨度基础上得到的平均有效直径分别为3.967和3.833，整体平均距离为2.966和2.866。实验结果显示：使用MAS方法，邮件网络中所有社区的平均有效直径降低了约0.13个单位，平均距离减小了近0.10个单位。
6 分析与评估
邮件社区的划分是一种图聚类问题[14]，本文中算法是一种动态模型聚类算法，通过社区中心的动态调整来逐步优化邮件社区，具有更快的社区聚类速度，同时引入了基于时间的相似度拟合，更符合邮件通联的特征。
本文通过有效数据来验证MAS算法的合理性和有效性，并与最为常见的基于通信次数的邮件社区聚类算法进行比较，进一步验证MAS算法邮件社区划分具有更优的性能，特别是在明显时间跨度上具有更好的性能。
由以上实验可以看出，邮件社区就是一种介于规则网络和随机网络的小世界网络[2]。邮件社区的节点具有高度耦合性，符合网络社区的特性，呈现六度分离[2]特征。而各个社区之间的关联相对松散，并且相似度低于邮件社区内部相似度，说明邮件网络中的确具有社区性质，并且该邮件社区划分算法及其优化方法具有合理性。邮件的社区性质和划分结果为进一步的社区分析、社区节点行为分析提供了有力的基础。
7 结语
本算法得到的结果表明利MAS算法进行邮件社区划分是有效并且合理的。实验结果表明，邮件社区网络与现实社会网络是同构的，呈现明显的聚集现象。MAS算法具有较高准确性，仅从邮件通联特性出发，涉及较少的邮件内容分析，从而算法更为简洁易于扩展。下一步工作从算法上，可以研究该算法的扩展，MAS与其余相似度算法的结合；从步骤上，可以研究邮件社区中发现主题内容和社区的核心人物的分析，并进一步考虑进行分布式扩展以增加社区划分的效率。
参考文献：
[1]Zhang Yanchun，Yu X J，Hou Jingyu.Web communities： Analysis and construction [M].Berlin：Springer，2005：56-92.
[2]司徒俊峰.Internet的小世界网络研究[J].情报技术，2004，23（12）：86-88.
[3]Lin Hui，Fan 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]康书龙.基于用户行为及关系的社交网络节点影响力评价[D].北京：北京邮电大学，2011.
[5]熊会会.基于复杂网络的微博客信息传播机制研究[D].广东：华南理工大学，2012.
[6]伊衍腾，李学明，蔡孟松.基于用户关系与属性的微博意见领袖挖掘方法[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]陈绍宇，宋佳兴，刘卫东等.关系网格：一种基于小世界模型的社会关系网络[J].计算机应用研究，2006，23（5）：194-197.
[10]李军利，赵红领，范明.邮件社区划分和小世界网络[J].计算机应用，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.范明，孟小峰，译.数据挖掘：概念与技术[M].北京：机械工业出版社，2001.
作者简介：高源（1988-），男，四川省江油市人，硕士研究生，主要研究领域：数据挖掘。
作者单位：华北计算技术研究所 信息技术应用系统部，北京 100083