《电子邮件网络研究在社团区分基础上的系统构建及其实现分析.doc》由会员分享，可在线阅读，更多相关《电子邮件网络研究在社团区分基础上的系统构建及其实现分析.doc（8页珍藏版）》请在三一文库上搜索。
1、电子邮件网络研究在社团区分基础上的系统构建及其实现分析-第一章 绪 论本章主要阐述了复杂网络在我们现实世界的普遍存在性，社团划分被提出的背景，和社团划分对于理解复杂网络的重要意义，以及对我们生活的积极影响。介绍了社团划分算法的发展现状，以及现有算法一些不足之处。在最后介绍了本论文的主要研究内容与组织结构。1.1 研究背景及意义无论是在自然界中，还是在我们的社会生活中，关系网络都是广泛存在的1。在自然界中，例如新陈代谢网络2, 3、食物链网络4、以及神经网络5等等。在我们的社会生活中，例如 Inter6、万维网7, 8、论文引用网络9、电力网络5, 10、以及社交网络10。这些网络描述的事物不同
2、，所处的研究领域不同，但是他们有一个共同特性，就是这些网络具有很强的聚集性和无规则性等特性。这些网络中节点之间的连接拥有不同权重和方向，并且这些节点之间的连接千变万化。这给人们理解复杂网络带来了很大的障碍。社团结构是复杂网络非常重要的特征，有助于人们理解和分析复杂网络，社团划分算法就是用于在复杂网络中发现复杂网络的社团结构。这些复杂网络可能是有向的，也可能是无向的，可能是有权的，也可能是无权的。随着社会的发展，人与人之间的联系越来越紧密，关系网络在我们当代人们生活中也在不断的延伸，其复杂程度也在日益增加。特别是近些年来计算机网络的出现，这使得人与人之间的关系网络更加复杂。这些人与人之间的关系网
3、络包含了很多有意义的特性。通过研究表明，在关系网络中这些特性有很强的聚簇表现，所以根据这些特性，可以对网络进行社团划分。对划分出的社团进行分析，可以提取出这些社团的特有信息，从而来服务于我们的现实生活。对于个人来说，现在社交网络越来越流行，我们通过社交网络中用户之间的关系，可以把用户分成一个个小社团，例如他们有同样的喜好，从而为他们推荐好友，推荐游戏，书籍，影片，工作等。对于企业来说：可以通过分析用户购买的商品之间的关系，当一些用户购买了一些商品之后可以向其推荐一些相关商品，如果用户没有找到相关商品或所商品已售完，向用户推荐一些替代商品。对于国家安全：根据违法分子的关系网络对他们进行团伙划分，
4、从而提高抓捕的准确度，进而保卫国家和保障人民的人身与财产安全。由于社团划分对于了解网络有非常重要的意义，近些年来，关于社团划分的新理论层出不穷，一些新的算法不断涌现，但是由于社团划分是一个比较复杂的处理过程，所有算法都能逃不过两个限制时间和空间。特别是对于大的网络，数以亿计的节点要求的不仅仅是算法的准确度，同时也要求算法的效率和实用性。所以找到一种快速、准确，并且要求其空间消耗足够合理的算法就非常重要。人们之间的关系网络化在将来会继续加深，并且其复杂程度也将不断加大。对于社团划分的研究必将会持续下去，并且会被不断推广用于各种关系网络分析中。所以研究设计快速准确的社团划分算法，提高网络分析的效率
5、，无论对于现在还是将来都是件非常有意义的工作。.1.2 研究现状关于网络社团结构的研究可以追溯到 1955 年，当时 Weiss 和 Jacobson 对政府部门的网络结构进行了研究11。从那个时候开始，关于网络社团结构的研究越来越引起人们的兴趣。到 20 世纪末，对于网络社团结构的研究在人们的生活和研究中已变得非常重要，并变成了社会学和生物学的一个非常热门的课题，它被广泛应用于各个方面。对网络的深入研究有助于理解这些网络系统的特征，这对于我们的现实生活有非常重要的意义。真实网络与随机网络有很大的不同。在随机网络中任意一对节点之间存在连接的概率是相等的，所以边在各个节点之间的分布是十分均匀的1
6、2。例如，一个顶点邻居的数量，或称之为度，是成二项式分布的。所以对于随机网络中大部分节点来说，有相等或相似的度。然而真实网络不同于随机网络，它们显示了很大的非均匀性，这就说明它们具有很强的结构特征1314。一些节点有很大的度，而另一些节点却有较小的度。在一些比较特殊的子网络中包含了更多的边，而这些子网络之间却有很少的边将它们连接起来，这样就把其社团结构特性表露无疑。社团也被称为簇或者模块，它是由一组具有共同属性或在网络图中扮演相似角色的节点构成的。早期比较经典常用的理论是朋友的朋友很可能是我的朋友，具体来说就是如果有甲乙丙丁四个人，甲与乙是朋友，乙与丙是朋友，与丁相比，那么丙更可能与甲是朋友，
7、但是这种算法有其局限性。然而，在现在的实生活中，由于社会和技术的发展，网络的复杂程度越来越大，简单直观的分析算法已经不在适用。这就对新算法的要求越来越迫切。特别是有些网络的节点数常常多达百万甚至上亿，而节点与节点之间的关系更是复杂，要处理这么大的数据量，一些新的方法在不断的涌现。目前按照划分出来社团的结果可以把算法分为三大类：无重叠社团划分算法，局部社团划分算法，重叠社团划分算法。1.2.1 无重叠社团划分算法对于无重叠社团的划分早期比较有影响的算法是由 Girvan 和 Nean 在其论文15中提出的。他的主要思想是：节点与节点之间都是通过最短路径相互联系的，如果很多节点之间的最短路径都经过
8、某些边的话，说明这些边很可能是社团与社团之间相互连接的边；因为在社团内部节点之间有很多边，所以社团内部节点与节点之联系最短路径经过的边相对分散，从而造成社团内每条边被经过的次数相对均等16。这个算法影响比较大，曾被广泛应用和研究。Nean 和 Girvan 在 2004 年 2 月提出了一个模块属性的测量方法17。在文中他们引入了一个变量 Q，这个变量用于衡量从网络中划分到的社团模块性。这个变量被称为模块度，其原理是计算模块内聚性与随机划分结果的内聚性的差值来估测当前获得社团结果的合理性。当 Q 的值为 0 的时候说明这个网络是一个随机网络其模块性很差。当值为非 0 时说明这个网络是不同于随机
9、网络的。在测试中显示在此属性值大于 0.3 的网络会表现出比较明显的模块性。但是它们并没有提出一个好的划分算法。虽然Girvan 和 Nean在论文15中提出的算法在小型网络中有较高的应用价值，但是其运行效率比较低，要用于处理有数以亿记的顶点的网络其处理速度还是比较慢的。2004 年 3 月在 Nean 在论文18提出了一个全新的算法，他们引入了 Nean 和 Girvan 在 2004 年 2 月在其论文中提到的测量值变量 Q17。在之前的算法中 Q 只是一个测量变量，所以要找到最佳社团划分结果就要进行社团枚举。但是这个问题是个 NP 困难问题，所以这种算法并没有可行性。然而这这个算法中使用
10、了一个近似算法贪心算法。算法起始时每个顶点属于一个单独的社团，之后开始合并社团。合并社团的原则是：当前两个社团合并时使 Q 增加的量比其他任何两个社团合并时 Q 所增加的量都大时，则合并这两个社团。对于一个有 n- 个节点的网络，经过 n-1 次合并就可以把所有社团合并成一个社团了。但并不是所有网络都能最终合成一个社团，应该是普遍不能合成一个社团。因为在合并到一定程度的时候，再进行社团合并时 Q 值就会减小。因此当社团合并不能在引起 Q 值增加的时候算法也就停止了。整个处理过程就像一棵树，叶子是原始网络中的顶点，中间的节点是中间合并得到的社团，从而使社团划分的算法效率大大提高。.第二章 复杂网
11、络经典社团划分算法介绍由于对复杂网络社团结构的研究不断深入，许多学者从不同的角度入手提出了很多不同的算法来对复杂网络进行社团划分，例如 GN 算法，K-clique 算法、Louvain 算法等等。有些算法所运用的思想在后来的社团划分算法中被多次借鉴；有些算法是通过对早期算法的改进发展而来的，基本思想没有改变。本文提出的算法同样是在先前算法基础上得到的。本章在这里首先介绍了论文中所涉及到的复杂网络的基本概念和相关术语，然后介绍了几种在社团划分算法研究领域影响比较大的算法。2.1 复杂网络概述2.1.1 复杂网络的基本概念定义我们所接触的复杂网络都可以描述为由节点和边组成的图结构 G (V ,
12、E)，其中V 是一个集合，它包含了图中所有节点，E 也是一个集合，它包含了图中所有边。图在计算机中常常用两种数据结构来保存邻接表和邻接矩阵。由于关系网络是一个数据量巨大的网络，并且边的数量远远低于节点数量的平方，所以处理关系网络的时候邻接表存储结构更为适合。如果定义 表示网络中边的总数，如公式（2-2）所示。2.2.2算法思想算法主要通过分层移动节点划分社团，然后用社团构造超点，在高一层次上超点就成为新的节点参与社团划分。算法的主要流程如图 2-2，首先初始化网络信息和读取社团信息。判断社团是否已经具有社团信息，如果已经具有社团信息，依据信息对社团进行初始化，否则，将每个节点设为一个社团，计算
13、社团结构的模块度，进行该层次的节点迁移，节点迁移结束后再次计算模块度，之后将同一个社团中的节点合并为超点，判断前后模块度是否发生变化，若发生变化，继续下一层处理，否则算法结束。该过程一层一层迭代，直到模块度不再发生变化。总体来说迭代过程主要包括两个步骤（如图 2-2）。第一步：对各个节点进行检测，把节点加入到会使模块度值增加最大的社团中；第二步：将各社团形成一个超点。在第一步中首先计算当前社团结构的模块度值，然后随机产生检测点序列，依据监测点序列依次检测每个节点。将节点从原-社团中取出，分别计算当前节点加入到各个与之相连接的社团后所产生的模块度增量，在这些社团中挑选一个对应模块度增量最大的社团
14、，将当前节点加入到该社团中，当所有检测序列检测结束后，计算当前状况下的模块度，之后查看是否有节点发生移动，并且检测模块度的增量是否超过阈值。如果有节点发生移动，并且模块度增量超过阈值，重新遍历检测序列，否则结束。流程图如图 2-3。.第三章 社团划分算法研究. 26 3.1 改进的 Louvain 社团划分算法. 263.1.1Louvain 算法的不足. 26 3.1.2 算法思想. 27 3.1.3 实验与结果分析. 29 3.1.3.1 合成数据. 29 3.1.3.2 某机构的邮件数据. 30 3.1.3.3 结果分析. 30 3.1.4 算法总结. 31 3.2 基于局部算法划分重叠
15、社团. 31 3.2.1 k-clique 算法的不足之处. 31 3.2.2 算法思想. 31 3.2.2.1 网络节点预处理. 32 3.2.2.2 构造社团. 32 3.2.3 实验与结果. 35 3.2.3.1 GN 网络数据集 . 36 3.2.3.2 colleges football 网络. 36 3.2.3.3 结果分析. 37 3.2.4 算法总结. 38 3.3 本章小结. 38 第四章 电子邮件网络分析系统的设计与实现. 39 4.1 用到的框架和技术. 39 4.1.1 Spring 框架 . 39 4.1.2 Hibernate 框架 . 41 4.1.3 JNI .
16、 43 4.2 系统总体介绍 . 44 4.2.1 系统架构. 44 4.2.2 系统功能. 46 4.3 邮件预处理模块. 46 4.3.1 处理流程. 47 4.3.2 重要的数据结构. 48 4.4 社团划分模块. 48 4.4.1 处理流程. 49 4.4.2 重要的数据结构. 50 4.5 关键节点探测模块. 52 4.5.1 处理流程. 52 4.5.2 重要的数据结构. 53 4.6 数据库. 54 4.6.1 数据库表的组成. 54 4.6.2 数据库表的关系结构. 55 4.7 本章小结. 56 第五章 电子邮件网络分析系统测试-本章是对电子邮件网络分析系统各个功能模块的功能
17、测试，主要包括预处理模块测试、社团划分模块独立测试、关键节点模块独立测试、社团划分和关键节点探测模块的联合测试。5.1 功能测试5.1.1 邮件预处理功能测试邮件预处理是处理数据的，通过处理邮件提取邮件头和正文信息并将结果导入数据库，邮件预处理功能测试图如图 5-1。其中“打开”按钮会调用一个对话框来选择要处理的邮件包。当选择了一个邮件包后，邮件包的路径会显示在“打开”按钮左边的文本框中，邮件包内部的邮件目录结构会显示在下面的邮件目录结构中。下面的导入按钮用于将选择的邮件导入数据库，点击按钮后会弹出一个包信息配置对话框，要求配置相关信息邮件、标注、包名，如图 5-2。右边上部分显示的是邮件包中
18、各个邮件的邮件头信息。当选择一封邮件后，会在下面显示相应邮件的正文信息。最下面是一个进度条，用于显示邮件导入时的进度。5.1.2社团划分功能独立测试社团划分是了解关系网络结构的一个重要方法，在获取关系网络的数据后，对网络进行社团划分获取网络的社团结构，并以图形化的方式展示在窗口界面上，如图 5-3。每一种颜色分别代表一个社团，下面的圆饼图显示了各个社团中节点数占节点总数的百分比。图形显示部分的左上角的图标工具的功能依次是修改背景、显示标签、统计网络数据、形成报表、打印图形、各个社团信息。.第六章 结束语关系网络普遍存在于我们的日常生活中，特别是近些年来随着通信技术的进步和新通信手段的普及，人们
19、之间的联系越来越复杂，日常生活中的关系网络规模越来越大，这引起了更多的学者关注复杂网络特性的研究，现在对于复杂网络研究已经取得了一些成果，但是这些成果只是这一学科的冰山一角，所以关于复杂网络的很多特征属性还等待着人们去发现和研究，然而社团结构一直是这门学科的研究热点。6.1 全文总结在科学理论层面，通过学习研究先前提出的算法，了解到了社团划分算法的核心理论和这些算法的不足之处，据此本文提出了两种算法用于划分复杂网络中的社团结构，并通过实验验证了算法的高效性。在工程技术方面，运用所掌握的技术和知识设计了电子邮件网络分析系统，搭建了系统的整体框架，同时应用所掌握的和提出的算法实现了电子邮件网络分析
20、系统的关系网络关系分析模块。概括起来，论文主要贡献包括理论和工程两个方面：1）提出了两种适用于复杂网络的社团划分算法。第一种是改进的 Louvain 社团划分算法，该算法通过剪纸判断解决了 Louvain 算法的冗余计算问题，有效提高了算法的执行速度，并且保持了划分算法结果的准确率。第二种是基于局部算法划分重叠社团的算法，该算法通过构建社团核心，之后依据个邻居节点的内向性扩展社团，最后对社团进行修整，从而实现了重叠社团算法，解决了无重叠社团算法所不能解决的问题，并且通过与其他算法进行对比，该算法在准确率和召回率上有明显优势。2）设计了电子邮件网络分析系统并实现了该系统的网络关系分析模块。该系统使用 Spring 框架关系类对象，使用 Hibernate 来管理数据库的操作，通过 JNI 调用各种网络关系分析算法。并提供将数据可视化功能，通过对 Prefuse 框架的扩展，实现了各种关系网络分析数据的可视化，将关系网络以及分析结果以图形方式显示在主界面上，同时对各种分析数据进行统计显示在统计区域，并形成报告文档。.