基于Spark的大规模复杂网络的社区发现算法的研究与改进

发布时间：2020-04-21 07:22

【摘要】：复杂网络是计算机学界比较经典的研究领域之一,研究者们将现实生活中的一些具体现象抽象为复杂网络,通过复杂网络的拓扑结构、节点或边包含的隐式或者显式的信息,来抽取出人们感兴趣并且能为社会带来巨大价值的信息。例如,通过人群接触的复杂网络确定某些传染病的传染源以及传播势头,利用知识图谱获取某一学科的发展趋势以及与其它学科的交叉情况等。在复杂网络领域中,社区发现是目前最基础、最广泛的研究。社区发现,是根据已有的知识将复杂网络划分为若干个子模块,一个模块成为一个社区,里面包含一些关系密切的节点与连接边。社区发现可以理解成一种基于复杂网络的无监督的聚类算法。随着模块度概念、谱聚类算法的提出,社区发现算法在21世纪初期迅猛发展,各种各样的社区发现算法被提出并得到论证。优秀的社区发现算法可以提高复杂网络社区划分的指标标准,从性能方面也可以提高发现效率,减少时间开销。但是随着大数据时代的降临,复杂网络的规模也是快速发展。在进行实际操作时,单机的计算能力无法满足人们的需求,即使进一步优化算法,在单机条件下也无法带来质的飞跃。因此,如果将计算交给大数据计算平台,就可以满足人们对规模巨大的复杂网络进行高效计算的需求。大数据时代产生了许多大数据计算框架平台,其中,Spark因为计算速度快,生态圈丰富,从而获得了大数据业内的广泛认可。并且,Spark计算平台拥有的相关图计算组件GraphX,可以帮助实现算法同步化。基于上述知识,本文提出基于Spark的大规模复杂网络的社区发现算法的研究与改进。本文首先对一个无权值的复杂网络进行加权预处理;其次选取经典的高效社区发现算法——标签传播算法,进行包括标签初始化、标签传播和标签更新策略、迭代收敛策略等多方面的优化工作,进而建立一个新的社区发现算法模型;然后,将算法接入Spark,通过GraphX编程实现算法同步化,并建立Spark实验平台;最后,通过经典的复杂网络数据和规模较大的复杂网络数据进行实验,与一些经典的社区发现算法进行对比,验证提出的算法是否有效,并且通过大规模复杂网络数据集来验证基于Spark GraphX平台确实大幅度提高了在复杂网络中进行社区发现的计算性能。
【图文】：

示意图,复杂网络,示意图

第一章引言第一章引言研究背景随着信息科技的不断发展和人工智能水平的提高，人类进入了一个万物代，尤其近 5 年以来，物联网、车联网等词汇越来越多的出现在我们的这些先进的概念都可以抽象成复杂网络。“物”与“车”相当于复杂网点，而节点之间的联系（比如设备之间的物理连线，，车与车之间的信息交看做复杂网络中两个节点之间的连线。不仅如此，世界本身就可以看做的复杂网络，它由许多节点（实体）和边（实体之间实际或者抽象的关，而我们就生活在这个巨大的复杂网络之中。

社交,示例,社区

图 1.2 社交网络示例图 1.3 知识图谱示例发现复杂网络中的社区需要用到社区发现算法。社区发现算法是一种无监督学习算法，其目的是聚合在复杂网络中相似的节点。除了理论研究价值之外，该算法在现实生活中同样有着重要的意义：在社交网络中，通过社区发现可以发现关联性强的群体，可以对群体进行组推荐；在电话网络中，公安机关通过社区发现可以划分出联系紧密的社会人群，在已知少数犯罪嫌疑人的情况下，可以根据他们所在的社区侦查出团伙，提高办案效率；在突发传染病的情况下，可以通过对人群进行社区划分锁定传染病源出现的社区，确定高危人群，利于传染病及时的防护与控制。目前，对于复杂网络社区发现算法的研究很多，很多学者对一些基础算法做了足够的改进，并且效果优良。但是随着社会的发展，科技的进步以及信息的不断积累，各行各业的数据呈现迅速增长的趋势，一些类复杂网络结构的数据规模也越来越大，其拓扑结构也越来越复杂。以社交网络为例，由于 2010 年后智能
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【参考文献】