一种基于局部信息的分布式社区结构挖掘算法

发布时间：2020-05-26 23:16

【摘要】：复杂系统是现实世界的重要组成部分，复杂网络是对复杂系统的抽象。研究并发掘复杂网络的性质可以帮助人们更好的理解复杂系统。随着社会的网络化以及计算机技术的不断发展，人们对现实世界的建模能力较过去有了长足的发展，这使得网络科学的工作者所接触的网络模型越来越复杂，面对的任务也越来越重。而社区结构是人们认识复杂网络的一个有力工具，从而使得解决复杂网络中的社区结构挖掘问题成为一项积极有意义的工作。现实世界中个人在生活工作中所产生的数据急剧增加，同样它们所需要的信息量也随之增加。面对海量数据，如何在一个可接受的时间内挖掘出特定人群所需要的信息是一个重要的挑战，分布式成为人们处理海量数据的主要方式之一。文中首先分析了复杂网络的基本特征并以此引出复杂网络的社区结构特征；然后分析了现有的社区结构挖掘算法，总结了算法的优缺点。基于全局信息的社区结构挖掘算法需要利用网络的全局信息，因此时空复杂度都较高，而且在复杂网络中全局信息并不容易获得。为此本文研究并实现了一种基于局部信息的社区结构挖掘算法，同时将其推广到分布式平台上进行实现。利用分布式平台的优势，达到时间与空间的良好平衡。文中在Clauset提出的局部模块度概念的基础上提出了一个新的衡量节点是否属于特定社区的函数，应用该函数对Bagrow算法进行改进，改进的算法考虑了节点的更多信息，因此在精确度上取得了进展，但是算法的迭代速度并没有提高。随后文中分析了本地社区中节点的特点并提出了两种启发式方法，应用启发式得出了一种新的算法，新算法在保持准确度的同时提高了算法的迭代速度，而后将其以MapReduce的编程模型进行实现，最后在Hadoop开源平台上实现整个算法，并进行了实验验证。实验结果表明改进算法较原始的Bagrow算法在精确度上有了一定的进步。而算法的MapReduce实现则证明了在数据量逐渐增大时，分布式计算是一个有力的武器。
【图文】：

线图,聚类系数,路径长度

率 p 重新将该边和顶点（从环上随机选择一个顶点）连接起来，相平行的边的出现，即从一个顶点开始到另一个相同的顶点有两个方面衡量图的结构特征，路径长度 L ( p )和聚类系数 C ( p )。其离程度，而 C ( p )衡量相邻节点之间的社区性。当 p 0时有L 当 p 1时有 L ln n lnk，且 C k n 0。以上各式 n) 1，其中 k ln( n)是为了保证随机图是连接的。综上，得出以是高聚类，大世界（big world）的,这是因为 L 随着 n 的增长呈线图是低聚类，小世界（small world）的，因为L随着n的增长只呈会令人产生这样的怀疑:值较大的L总是和值较大的C 相联系。 2.2 揭示了直觉与事实是相反的。从图中可以看出 p 有一个取值域里 L ( p )总是维持一个很小的值randomL 而与此同时 ( )randC p C在正说明了网络的小世界性是存在的。通过对自然存在的网络的了这一区域，从而说明网络中的小世界性是普遍存在的。

网络图,幂律分布,网络图,节点

很多邻居节点的节点。这两个特性László和Réka提出了一个网络增长模型来说明网络中节。该模型的过程是这样的，模型中初始具有0m 个节点，每一步加入一入的节点有0m ( m m)条边，连接模型中已有的 m 个节点。假设一个模型中节点i的概率 p 取决于节点i的度ik ，于是有 ( )i i jp k k k，，中拥有0t m个节点和 mt 条边。这样一来整个网络就将进入一个无标中的一个节点具有k 条边的概率服从指数为 Y 2.9 0.1的幂律分布。
【学位授予单位】：哈尔滨工程大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：N941.4;TP311.13

【参考文献】