基于核心图聚类的邮件网络社区发现
摘 要：根据图聚类节点的密度变化确定核心节点，构成连通子图并确定邮件网络社区划分的个数及初始社区中心点，通过社区中心动态调整的方法将非核心节点划分至所属社区。实验证明了该邮件网络社区划分的有效性和可行性。
关键词：图聚类；邮件社区划分；动态中心
随着互联网的发展，网络成为工作和生活中相互联系的重要工具，与此同时，网络社区[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 聚类个数及聚类核心求解算法
