基于核心区域扩展的重叠社区发现算法研究

发布时间：2018-04-10 02:20

本文选题：社区发现　切入点：复杂网络　出处：《北京理工大学》2016年硕士论文

【摘要】：社区结构是复杂网络中一个常见的特性,它由一组连接紧密的结点组成,同时这些结点与社区外部结点连接稀疏。通过研究社区结构,研究者能够更深刻地理解网络所对应的复杂系统,因为社区结构往往揭示着网络的组织结构。同时,由于社区结构有着广泛的实际用途,所以在复杂网络中发现社区结构有着重要的研究意义。提出了一种衡量结点中心性的方法。基于结点核心值以及局部扩展框架,提出了一种新的重叠社区发现算法。该算法不仅能够发现重叠社区结构,同时还可发现网络中的部分桥接结点。该算法包括四个步骤:首先,根据结点的核心值将它们降序排序,以形成种子优先级列表;其次,列表顶端的结点被选出,以形成一个社区的核心区域;然后,扩展这个核心区域直到一个社区结构或者桥接结点被发现;最后,分配桥接结点到那些它的大多数邻居所在的社区中。其中,交替执行第二、第三步,直至所有社区都被发现,然后再进行第四步。实验结果证明了算法的有效性。针对当前已有的社区发现算法无法有效处理海量级数据的问题,提出了一种基于局部扩展的并行化算法,并且借助Spark框架将其实现。该算法包含四个步骤:首先,挑选出一组互不相关的中心结点并使用中心结点与它们的邻居所形成的局部网络作为种子;其次,通过删除那些本身连接比较稀疏的局部网络来过滤选出的种子;然后,采用一种批量式的扩展策略来扩展种子,即一次向局部社区中添加一批邻居结点或从社区中删除一批结点;最后,融合相似度比较高的社区。实验结果证明了算法的有效性。
[Abstract]:Community structure is a common feature in complex networks. It consists of a group of closely connected nodes which are sparsely connected to the external nodes of the community.By studying the community structure, researchers can understand the complex system of the network more deeply, because the community structure often reveals the organization structure of the network.At the same time, because community structure has a wide range of practical applications, it is of great significance to find community structure in complex networks.A method of measuring node centrality is proposed.A new overlapping community discovery algorithm is proposed based on node core values and local extension framework.The algorithm can not only find overlapping community structures, but also find some bridging nodes in the network.The algorithm consists of four steps: first, ranking the nodes in descending order according to their core values to form a seed priority list; secondly, the nodes at the top of the list are selected to form the core area of a community; then,The core area is extended until a community structure or bridging node is found; finally, the bridging node is allocated to the community where most of its neighbors live.Alternately, perform step two, step three, until all communities are found, and then step 4.Experimental results show that the algorithm is effective.Aiming at the problem that the existing community discovery algorithms can not deal with the massive data effectively, a parallelization algorithm based on local extension is proposed and implemented with the help of Spark framework.The algorithm consists of four steps: first, selecting a group of unrelated central nodes and using the local network formed by the center node and their neighbors as seeds; secondly,The selected seeds are filtered by deleting the local networks with sparse connections; then, a batch expansion strategy is used to extend the seeds.That is, adding a group of neighbor nodes to the local community or deleting a group of nodes from the community at a time. Finally, the communities with high similarity are fused.Experimental results show that the algorithm is effective.
【学位授予单位】：北京理工大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5

【相似文献】