75
Computer CD Software and Applications
special study
本刊约稿
现
代社会中,互联网已经深入到人们的生活的
各个方面,成为人们生活、工作不可缺少的
一部分。人们在网络间的通信方式也多种多
样,其中电子邮件是主要通信工具之一。电子邮件之间的
相互通信在互联网上构成了庞大的邮件网络。在这个网络
中,包含大量电子形式的个人信息以及邮箱用户之间相互
通信关系。整个邮件网络又可以划分出若干的邮件网络社
区。网络社区
[1]
表示在虚拟网络中,网民根据共同的兴趣
而形成的真实的社会团体,具有实际社区的基本要素,包
括人群(网民)、活动区域(网络)、互动行为、共同的
社会心理基础等。网民在一定的网络空间内,围绕共同的
需要和兴趣进行交流互动活动,相互之间构成的网络社区
具有六度分离
[2]
的特性。邮件社区作为一种网络社区,也
与现实中对应的社会关系网络是同构的,能够反映出社会
网络中网民活动的社区通信信息和相互交流兴趣主题。目
前有关网络社区
[1,3]
的研究较多,如网页社区研究,主要
包括关联网页的查找、噪声网页的消除和网页关系聚类
等;又如现在应用较多的微博网络社区研究,包括微博热
点话题发现和基于主题聚类
[4-6]
等;再如垃圾邮件的识别与
过滤等
[7,8]
。但是在邮件社区中,直接利用邮件通联关系
进行社会网络构建的研究和应用相对比较薄弱,然而邮件
社区研究对于发现邮件社区中的犯罪网络及分析网络核心
成员等实际应用具有重要意义。
1 邮箱活跃度分析
邮件网络是一种社区网络,由众多邮件社区构成。邮
件社区是由若干邮箱及邮箱之间的相互通信组成,如果将
邮箱看作是节点,而通信关系看作是边,则邮件社区可以
表示为一张图,有如下与关系网络
[9]
类似方法的定义。
定义1 邮件网络表示为加权图G=(V,E),其中V
是顶点集合,E是边集合。在邮件网络中,v∈V代表一个
邮箱,e=(v
i
,v
j
)∈E表示邮箱v
i
和v
j
之间存在通信联系,
而w(e)(其中e=(v
i
,v
j
))表示邮箱v
i
到v
j
的关联频
度,可以用邮箱v
i
和v
j
的通信次数表示。设G
k
是G的子图,
表示一个社区。社区G
k
的直径,记作D(G
k
),定义为G
k
中所有节点对之间距离的最大值。而社区G
k
的节点对的平
均距离d
avg
(G
k
)是所有节点对之间距离的平均值。社区
Gk的有效直径记作D
val
(G
k
),对于社区Gk中至少90%以
基于邮箱活跃度的邮件社区划分研究
高源 / 华北计算技术研究所 信息技术应用系统部
摘 要:为深入挖掘互联网邮件通联关系,提出了一种基于邮箱活跃度的邮件社区划分算法(MAS),并研究了邮件社
区的性质与特征。算法采用基于邮箱通联活跃频度的余弦相似度评估邮箱之间通联关系的相似性,并通过层次聚类的
方法指导邮件社区聚类,然后对社区中心进行动态调整以完成划分。在有效模拟数据集上的实验表明,该算法有效、
合理,可以应用于实际的挖掘应用。
关键词:邮件社区;社会网络分析;数据挖掘;活跃度
上节点对,它们的距离小于或等于D
val
(G
k
)。
为分析研究邮件社区性质,本文使用了一组有效的互
联网邮件模拟数据,能真实反映邮箱间通联关系特性。该
数据集包含90天共200万邮件通联数据。对该数据集进行
邮箱发送活动统计如下图所示,部分通联次数为1的邮箱
未显示。统计发现,一共4.4W邮箱中,有4千个邮箱的主
动发送次数大于20。这部分邮箱明显属于高活跃邮箱。其
余邮箱组成了图中“长尾”部分。
图1 邮箱发送次数统计
仅用邮箱的通联次数来分析不同邮箱的特性显然是
不足的。本文考虑引入邮箱的活跃度,定义邮箱的活跃特
性。
定义2 活跃度t,表示目标邮箱在一段时间内的综合收
发邮件的频度。依据现实社会人物的活动规律,对时间粒
度划分的最小单位为天,定义活跃度t如下
t=αt
send
+(1-α)t
recv
(1)
其中t
send
是发送邮件的活跃度,t
recv
是接收邮件的活跃
度,α表示活跃系数。考虑发送邮件者作为主动方,而接
收邮件作为被动方,发送邮件对活跃度贡献应略高于接收
邮件,因此引入活跃系数α。发送活跃度t
send
和接收活跃度
t
recv
的计算方式相同,如下式:
(2)
◆
中图分类号:TP393.098
计算机光盘软件与应用19期内页-出版.indd 75 2013-11-8 14:25:01
75
Computer CD Software and Applications
special study
本刊约稿
现
代社会中,互联网已经深入到人们的生活的
各个方面,成为人们生活、工作不可缺少的
一部分。人们在网络间的通信方式也多种多
样,其中电子邮件是主要通信工具之一。电子邮件之间的
相互通信在互联网上构成了庞大的邮件网络。在这个网络
中,包含大量电子形式的个人信息以及邮箱用户之间相互
通信关系。整个邮件网络又可以划分出若干的邮件网络社
区。网络社区
[1]
表示在虚拟网络中,网民根据共同的兴趣
而形成的真实的社会团体,具有实际社区的基本要素,包
括人群(网民)、活动区域(网络)、互动行为、共同的
社会心理基础等。网民在一定的网络空间内,围绕共同的
需要和兴趣进行交流互动活动,相互之间构成的网络社区
具有六度分离
[2]
的特性。邮件社区作为一种网络社区,也
与现实中对应的社会关系网络是同构的,能够反映出社会
网络中网民活动的社区通信信息和相互交流兴趣主题。目
前有关网络社区
[1,3]
的研究较多,如网页社区研究,主要
包括关联网页的查找、噪声网页的消除和网页关系聚类
等;又如现在应用较多的微博网络社区研究,包括微博热
点话题发现和基于主题聚类
[4-6]
等;再如垃圾邮件的识别与
过滤等
[7,8]
。但是在邮件社区中,直接利用邮件通联关系
进行社会网络构建的研究和应用相对比较薄弱,然而邮件
社区研究对于发现邮件社区中的犯罪网络及分析网络核心
成员等实际应用具有重要意义。
1 邮箱活跃度分析
邮件网络是一种社区网络,由众多邮件社区构成。邮
件社区是由若干邮箱及邮箱之间的相互通信组成,如果将
邮箱看作是节点,而通信关系看作是边,则邮件社区可以
表示为一张图,有如下与关系网络
[9]
类似方法的定义。
定义1 邮件网络表示为加权图G=(V,E),其中V
是顶点集合,E是边集合。在邮件网络中,v∈V代表一个
邮箱,e=(v
i
,v
j
)∈E表示邮箱v
i
和v
j
之间存在通信联系,
而w(e)(其中e=(v
i
,v
j
))表示邮箱v
i
到v
j
的关联频
度,可以用邮箱v
i
和v
j
的通信次数表示。设G
k
是G的子图,
表示一个社区。社区G
k
的直径,记作D(G
k
),定义为G
k
中所有节点对之间距离的最大值。而社区G
k
的节点对的平
均距离d
avg
(G
k
)是所有节点对之间距离的平均值。社区
Gk的有效直径记作D
val
(G
k
),对于社区Gk中至少90%以
基于邮箱活跃度的邮件社区划分研究
高源 / 华北计算技术研究所 信息技术应用系统部
摘 要:为深入挖掘互联网邮件通联关系,提出了一种基于邮箱活跃度的邮件社区划分算法(MAS),并研究了邮件社
区的性质与特征。算法采用基于邮箱通联活跃频度的余弦相似度评估邮箱之间通联关系的相似性,并通过层次聚类的
方法指导邮件社区聚类,然后对社区中心进行动态调整以完成划分。在有效模拟数据集上的实验表明,该算法有效、
合理,可以应用于实际的挖掘应用。
关键词:邮件社区;社会网络分析;数据挖掘;活跃度
上节点对,它们的距离小于或等于D
val
(G
k
)。
为分析研究邮件社区性质,本文使用了一组有效的互
联网邮件模拟数据,能真实反映邮箱间通联关系特性。该
数据集包含90天共200万邮件通联数据。对该数据集进行
邮箱发送活动统计如下图所示,部分通联次数为1的邮箱
未显示。统计发现,一共4.4W邮箱中,有4千个邮箱的主
动发送次数大于20。这部分邮箱明显属于高活跃邮箱。其
余邮箱组成了图中“长尾”部分。
图1 邮箱发送次数统计
仅用邮箱的通联次数来分析不同邮箱的特性显然是
不足的。本文考虑引入邮箱的活跃度,定义邮箱的活跃特
性。
定义2 活跃度t,表示目标邮箱在一段时间内的综合收
发邮件的频度。依据现实社会人物的活动规律,对时间粒
度划分的最小单位为天,定义活跃度t如下
t=αt
send
+(1-α)t
recv
(1)
其中t
send
是发送邮件的活跃度,t
recv
是接收邮件的活跃
度,α表示活跃系数。考虑发送邮件者作为主动方,而接
收邮件作为被动方,发送邮件对活跃度贡献应略高于接收
邮件,因此引入活跃系数α。发送活跃度t
send
和接收活跃度
t
recv
的计算方式相同,如下式:
(2)
◆
中图分类号:TP393.098
计算机光盘软件与应用19期内页-出版.indd 75 2013-11-8 14:25:01