随着七桥问题的迎刃而解,人们对于图论的研究也逐渐兴起。由于网络应用图模型来进行研究可以更加清晰明确,因此,在社会网络、生物网络、信息网络等方面,图论有着广泛的应用,而社区发现又依赖于图论。在日常生活中,存在着形形色色的与社区相似的组织机构,比如班级、城镇、省市等。互联网兴起后又出现了虚拟形式的社区。对社区的相关信息进行挖掘已然成为现如今各领域中的十分热门的研究方向。根据是否有重叠节点这一特性,可以将社区分为重叠社区和非重叠社区。在日常工作生活中,重叠社区最为普遍,非重叠社区出现的概率相对小很多,所以学者们对于重叠社区的研究较为广泛。但是对于非重叠社区的研究又为重叠社区的研究提供了理论基础,很多重叠社区发现方法是基于非重叠社区发现方法提出来的。Palla等人首先发现并提出了社区重叠现象,并提出了一种用于重叠社区发现的方法。此后,应用于重叠社区发现的算法不断涌现,比如基于团渗透的社区发现算法、基于点聚类的社区发现算法、基于边聚类的社区发现算法等等。在基于边聚类的社区发现算法中,Link SCAN算法由于其将普通的图映射成连接空间图,将原始图中的结构联系准确地传递到经过映射后的连接空间图中,使得聚类的效果更真实,能够更加清晰地对重叠社区进行划分。传统的LinkSCAN算法只对原始图进行一次映射,并在其基础上进行聚类操作。本文提出的Multi-LinkSCAN算法在传统算法的基础上,通过自定义的方式,能够对原始图进行多次映射,在最终层数的连接空间图上进行聚类,使得社区的划分效果更加精准。但是LinkSCAN算法和Multi-LinkSCAN映射后所得到的连接空间图中,点和边的数量,呈指数级别的增长,这使得在求相似度矩阵、欧式距离以及聚类过程中的时空复杂度较原始图高出很多,导致运算时耗激增。此时通过应用分布式并行计算框架Spark,对大矩阵相乘、邻接交互矩阵、邻接相似度矩阵、欧式距离、层次聚类这五个方面的求解进行分布式的改进,以此来提高运算效率。同时本文采用阿里云E-MapReduce产品进行Spark集群的搭建,其在易用性、成本、资源整合、安全方面均优于普通的Spark物理集群搭建,为实验提供了良好的平台基础。