如今,我们处在信息化世界,数据无处不在。一个人在线或离线所进行的任何行为都需要数据,或者产生数据。这些数据是可以被收集的。这样的例子数不胜数:网页的历史浏览记录,社交网络(微博,微信,Facebook,QQ)的活动,信用卡交易,电话,智能手机的GPS记录等等。除了个人的日常活动所产生的数据之外,无论是由人类或自然产生的数据,都可以被收集。比如,大脑的神经活动,人体内所有化学反应,网络和网络流量,以及道路交通数据等。随着计算机科学技术的发展,这些数据被记录和处理,以便获得知识。分析结果往往被用于推荐系统或异常检测。然而,输入数据的规模和数据的多样性给算法的管理和计算带来了前所未有的挑战,在很多领域,非结构化数据正在成为数据的主要存在形式。大图数据,如大脑的神经元突触或者蛋白质的化学反应网络,用户为节点,用户间的朋友关系为边的社交网络等是非结构化数据的典型代表,这些网络的规模取决于节点的数目和节点之间的链接数目,由于网络的一些基本特性有别于以往普通网络的特征,如小世界、无标度特性等,因此这类网络也被称为“复杂网络”。通过对各类复杂网络的研究,网络科学得到了前所未有的发展,让我们对复杂系统有了比以往更深刻的理解。面向复杂网络的相关技术需要更加快速、通用的算法和更高效的运算平台。社团效应是复杂网络,尤其是社会网络的一个重要特征,所谓社团效应是指网络包含很多内聚的子网,这些子网内部联系紧密,而子网之间联系稀疏,这些内聚的子网通常被称作社团或者簇。社团发现或者是社团聚类是描述复杂网络所迈出的第一步。社团发现提供了解决现实世界问题的一种手段。它有许多应用,我们列举最常见的。第一类应用涉及海量数据的组织,比如建立社交网络上的好友列表。文档分类是另一个例子,特别是文档之间存在网络结构,如文档互引(维基百科页,科学文章…)。在相关分析完成以后,可以构建网络。推荐是另一个重要的应用。这可能包括在社交网络上的朋友推荐或在线购物网站上的产品推荐。至于搜索引擎,不仅提供相关推荐,但也会提供其他推荐。社团发现和以及重要网页的识别发挥了核心作用。预测,与推荐很相似,但又有所不同。我们可以预测未知的蛋白质在生物系统中的作用,如果某些未知的蛋白质出现在已知的蛋白质社团中,那么我们就可以猜测未知蛋白质的功能。我们还可以预测哪些客户会改变他们的电话运营商:如果一个客户群的重要的客户改变电话运营商,那么我们可以预测该客户群体的其它客户是否也改变电话运营商。我们还可以预测社交网络上的友谊关系:如果2个人处于同一个社团,但他们不是朋友,那么他们很可能成为未来的朋友。然后,结合推荐和预测的结果,发送朋友连接给这些人,这么做是非常有用的。复杂网络的社团发现在很多领域都发挥着作用。社团在网络结构中的作用是非常重要的。因此,传统的分类方法可以使用,特别是关于节点划分的构建方法,可以最大限度的遵循划分标准。在评价划分好坏的标准的时候,我们参考的是Newman在2004年提出的模块度的概念。研究表明很难对社区检测算法的进行精确分类,但我们可以简单分为:层次算法,优化算法(使用纽曼的模块度),凝聚算法和从经典聚类算法衍生出来的算法,如基于密度的聚类和基于代理的聚类。大多数关于复杂网络研究的问题与地理或SNA的研究问题类似:如何形成网络?它的特性是什么?有哪些角色或者最核心的链接?他们的脆弱性体现在哪里9等等。网络的类型以及研究方法不同,那么上述问题的答案也就不同。关于数据集,越大越好。研究者们提出了许多方法和措施,其中一些是现有的方法,或甚至现有的公认的方法(比如聚类系数)的改进与适应。研究网络的规模需要扩大。例如,clique检测算法对于大型网络是不合适的;统计模型比如ERGM对于大型网络也是不适用的。Newman和Girvan提出的图分割算法(最成功的算法之一):计算图的介数,删除介数最大的边,然后重新计算介数,继续删除介数最大的边,以此重复。通过计算模块度检查相关分割是否合理。当每个顶点都被划分到一个内部联系紧密的社团的时候,那么就没有必要继续进行分割。网络中有数以百万计的节点,不可能对单个节点进行可视化分析。如何对这类网络进行社团划分,并提出有效的算法,研究者们做出了很多尝试。这些算法使用的方法来自于不同的学科,如物理,生物学,计算机科学,应用数学和社会学。然而,考虑到算法的健壮性,并不是所有的算法能够在在实践中使用。社团发现与传统的数据聚类和图划分是类似的。在一个合理的时间对一个一个规模很大的图进行社团划分,也是一个NP难的问题。因此,对算法进行优化,使时间复杂度和空间复杂度处于多项式级别,是被研究者们强烈呼吁的。许多这些算法寻求最大限度的优化Newman-Girvan提出模块度的值。模块度方法是衡量一个网络将被划分成哪些社团。模块化方法通过搜索一个或多个高模块度的子网络,然后将这些子网络划分成社团。比利时的研究人员提出了一种新的算法,从算法速度方面看,优于其他已知算法。它可以应用在规模超大的数据集上:一个典型的2百万节点的网络只花费了2分钟进行计算。他被称为Louvain方法,得名于研究人员的工作地点(Louvain,Belgian)Louvain算法通过测试已知的社团结构的网络证明了算法的准确性。该算法适用于不同规模的数据集。研究者使用该算法测试了比利时移动运营商(260万用户)的网络以及基于由斯坦福网页爬虫收集的网页形成的网络(118万节点和十亿链接)。对社团发现的很多研究以二分网络作为起始点。Fortunato(Fortunato,2009年)穷举了研究清单。大多数较新的算法,最大限度的提高模块度的值。模块度的概念由纽曼(纽曼,2006年)提出,并首先广泛的应用在二分网络图上。然后,一些研究者将模块度从二分图开始扩展到其它网络(Murata,2010 Suzuki等,2009)。然而,从Barber(Barber,2007)对于二分图的模块化概念的表达派生自纽曼,并吸收了其它传统的方法如模拟退火算法(Guimerd和al.,2007),频谱聚类(Barber,2007),遗传算法(Nicosia和al.,2009年),标签传播算法(LiuXin和aL,2010),或二分谱分析算法(LEICHT和al.,2007)。从二分图衍生出的加权重叠社团检测扩展了分割算法。Pal la(PaMa和al.,2005.)使用k核分析。Davis(Davis和al.,2008)在图中使用随机游走。Gregory(Gregory,2009)使用标签传播算法。有的学者提出的方法更加具体。Wu(Wu和al.,2012)探索已划分社团之间的恢复问题。Richard(Richard和al.,2006)提出自旋相互作用波特模型和模拟退火相结合的算法。Lancichinetti(Lancichinetti和al.,2009)优化局部统计函数。很难找到既包括对二分图又包括社团恢复的文献。本论文对复杂网络中的社团发现,进行了相关研究。一些人建议使用聚类技术来解决这个问题。在所有基于聚类的技术中,基于密度的聚类不可忽视。聚类分析最重要的技术是K均值,凝聚层次聚类和DBSCAN。所述DBSCAN算法依以簇的密度作为基础。这种算法可以处理大型数据集,即使在有噪声数据的前提下,能够识别出不同大小和形状的簇。设计该算法DBSCAN的目的是要发现数据库中的簇和异常值。一个点的密度通过计算该簇半径以内的点的数目以及最小的点数获得。然而,DBSGAN最初开发在单机上运行。机器学习,聚类,这些算法对于大规模数据集很有用。毫无疑问,将DBSGAN从单机算法改为分布式算法的研究也不少。许多论文阐述了使用不同的方法将DBSCAN并行化,一些描述的是主从配置,另一些人则提出了完全分布式的并行算法。例如,mBSCAN使用三角不等式性质迅速减少邻近搜索空间,而无需使用空间索引。"n-OBSCAN通过首先使用CLARANS去分割数据集以减少每个分区的搜索空间,而不是在扫描整个数据集的方法对DBSCAN算法进行了改进。GRIDBSCAN构造一个网格,将相似性比较高的数据点分配到同一网格中,然后运用DBSCAN分别处理每个网格。这些算法提高DBSCAN的效率,但仍然没有足够的效率来处理海量的数据。许多论文提出了不同的方法以解决DBSCAN的并行化执行。M.Chen,X.Gao和H.Li,提出了一种新的并行DBSCAN算法-P-DBSCAN,它采用基于空间接入方式的优先R-tree,以支持区域查询,成功地嵌入Hadoop框架到DBSCAN算法来解决可扩展性问题。他们的实验结果表明,P-DBSCAN比原始算法DBSCAN更加高效。单台PC机运行速度提升40%,两台PC机速度提升60%。此外,并行算法比DBSCAN有更好的可扩展性。P-DBSCAN可用于大型数据库的聚类分析。Patwary等人提出了另外一种并行DBSCAN的算法(PDSDBSCAN),该算法使用了图算法相关概念。一方面,这种方法能够更好的处理工作量的负载均衡;另外一方面,通过不相交的数据结构克服了DBSCAN必须按照顺序处理数据的问题。Andrade等人提出了GDBSCAN,该算法实现DBSCAN图形处理单元的并行化。虽然这种算法的时间复杂度高于基于数据索引结构的DBSCAN算法,但是从执行时间来看,该算法运行速度更快。并行化DBSCAN算法,以解决其扩展性问题是非常困难的。ApacheSpark,—个用于快速通用的计算平台,已经成为Hadoop更好的替补。在速度方面,Spark比MapReduce更有效率,而且扩展了更多类型的计算,包括交互式查询和流处理。从那时起,基于Spark这个框架实现的DBSCAN的改进版本不断被提出。I rv i ng Cordova和Teng-Sheng Moh提出了一种基于Apache Spark的DBSCAN并行化算法。本论文构建了一个系统,该系统可以帮助用户在指定的数据集上运行发现算法,并将结果在web浏览器上进行展示。本论文主由两部分工作组成:1.运用Seala编程语言实现I rv i ng和Teng-Sheng提出的基于Apache Spark的DBSCAN并行化算法,这个算法将会解决原始DBSCAN算法的可扩展性问题,同时提升了计算能力。2.其次是实现了一个Web网站应用,根据用户的输入数据集,进行社团划分,取后将结果展现在网页上。论文1-2章分别对研究背景和关键技术做了相关介绍,论文第3章是本系统的需求分析。本论文对功能需求进行分析,同时对本系统用于社团发进行可行性分析。系统的整体分析是必要的,用于限定功能要求和描述相关用例。本系统的目标是满足网络数据分析和并进行可视化,主要功能如下:加载一个数据集,通过浏览器发出算法执行命令到集群,进行计算;将算法结果进行可视化处理后呈现在网页上,选择某一个社团,通过查询后台数据库访问社团的具体信息。论文第4章是本系统的体系结构以及核心模块设计。本系统的服务器端用Node,js服务器管理。该服务器负责访问或者修改数据。本系统架构平台包括一个管道和过滤器结构,其中包含一个数据源,众多的过滤器用于处理数据。通过使用流处理的方式,可以实现非阻塞方式对数据进行处理。Node,js服务器可以处理文件或者修改文件,即使该文件处于上传的过程中。本系统的架构采用客户端-服务器模式,客户端是胖或瘦服务器均可。使用JavaScript对客户端和服务端的通信进行操作。客户端发送请求,服务器端处理请求,并提交作业到集群上运行,最后将输出结果到数据库。最后传回的原始数据到客户端。系统将这些数据进行处理成相应的格式,然后通过以网络的形式进行可视化结果。客户端是采取基于MV*模型的web应用程序模式。它的原理是客户端处理来自数据库的数据,仅仅返回未处理的原始数据用于展示。然后将数据显示在web页面上。该MV*术语指的是MVC模式中的模型层和控制层,它在服务器端分离视图以及数据管理应用广泛。该MV*术语表明,这种模式的实现不同于纯MVC模式的实现。在这个架构中,从服务器端到客户端的GUI逻辑尤为重要。客户端包含HTM5和CSS的网页作为用户界面。客户端使用了Knockout(K0)这个JavaScript类库。该类库可以用于创建丰富的,响应式的用户编辑页面。最后,使用D3.js(另外一个可视化JavaScript类库),产生动态交互式的数据展现在浏览器中。第5章是社团发现平台的实现。用Scala实现DBSCAN算法,因为Apache Spark本身是用Seala语言写的。Seala语言在Apache Spark平台上互操作性比较好。DBSCAN算法实现时,需要使用sbt进行编译,将所有编译后的二进制文件和依赖jar包进行归档处理,生成一个可运行的jar文件。然后将这个jar文件部署在服务器端和客户端。然而,绝大多数的开发者使用命令行向Spark集群提交作业。本系统web应用最大的挑战就是通过服务器端提交作业,让集群运行作业。用Spark原生支持的提交作业是很轻松的,因为它本身就是那么设计的。通过打开一个命令行,对Spark作业进行提交的方式并不适合node.」s的编程方式。由于ApacheSpark底层依赖于Hadoop集群,所以算法的输出被保存到了Hadoop分布式文件系统上。我们对输出结果进行提取,然后保存到mongoDB数据库中,以方便web程序调用。第6章为测试阶段,详细介绍了数据集的细节,运算算法的环境(硬件)。数据集采用的是斯坦福网络数据集,Louvain和DBSCAN算法都使用了该数据集。对试验结果进行分析,表明DBSCAN比Louvain算法更快。但是,计算效率和计算速度取决于用户对于DBSCAN算法eps因子的选择,这使得算法评估变得有点困难。我们未来的工作可能是找到一个解决方案来克服不同eps参数的选择,在DBSCAN算法的计算时产生不同的结果,削弱eps参数对算法运行结果的影响。通过计算不同密度数据集的eps因子的值,从而提高算法的运行速度,提高社团发现的效率。另一项工作是对本系统进行完善。使得该系统可以进行更多的分析,例如进行用户推荐分析和欺诈检测分析。