基于节点相似性的社区发现算法研究

发布时间：2021-01-18 05:42

　　现实生活中许多系统可以表示成复杂网络,如社会关系网、蛋白质互作用网、交通运输网等,复杂网络分析在社会学,生物学等领域有着广泛的应用。社区结构是复杂网络的重要特征之一,即一个网络可以分成若干个社区,每个社区内部的节点之间连接相对紧密,各社区间的节点连接相对稀疏。设计有效的社区发现算法可以发现社会网络中的社区结构、生物网络中的蛋白质功能模块等,有助于深入研究各种类型复杂网络的功能模块及其演化特征,对准确地理解并分析复杂系统的拓扑结构及动力学特性具有十分重要的理论意义和应用价值。针对复杂网络中的社区发现问题,本文主要包括以下两方面内容:（1）对网络中节点间的相似性进行合理度量是社区发现的核心问题。针对此,给出了一种基于节点间点不重复路径的节点相似性指标,以此为基础,提出了一种基于节点间路径度量的图聚类算法（a graph clustering algorithm based on local paths between nodes in complex networks,PGC）,包括节点相似性计算、中心节点选择、初始社区划分和社区优化四个主要过程。采用节点间点不重复路径对节点相似性进行度量... 

【文章来源】：山西大学山西省

【文章页数】：67 页

【学位级别】：硕士

【部分图文】：

v和v间的点重复路径={,,}Pvvvvvv

ij所以，当iv 和jv 在 G 中不存在连边时，iv 和jv 间不存在长度为 3 的点重复路径。综合情形 1 和情形 2，可得(3)(3)(3)1, ( ), ( )ij i j i jijij i jd d vv E Gavv E G ，其中(3)ija 表示节iv 和jv 间所有长度为 3 的路径数，(3)ij 表示iv 和jv 间所有长度为 3 的点不重复路径。证毕由引理 3 可得，节点iv 和jv 间的长度为 3 的点重复路径的数目与它们的度成正。节点度越大，经过该节点的点重复路径越多，这导致采用 Katz、LP、LS 等指标节点相似性进行度量时，网络中的大度节点通常与其邻域中节点的相似性偏高。如 3.2 所示网络 G，根据公式(2.8)，有7 8 7 15(v , v ) 4.6 (v , v) 4.2LS LSS S ，在 LS 指标，由于计算了由大度节点8v 引起的较多点重复路径，节点7v 倾向于与度数较大的节8v 有更高的相似性。而实际上，边7 8v v 为图 G 的桥，具有较高的边介数。通常由介较高的边连接的两个节点更倾向于分属不同的社区[20]。

选择 k=2 作为最终的社区个数。图 3.3 ( )h hP c 随 h 变化的曲线图3.3 算法描述选择社区中心之后，根据定义 1 给出的相似性指标 SLP，计算网络中的其它非中心节点与 k 个社区中心的相似性，并将其分配至与其相似性最高的中心节点所在社区中，得到初始社区划分结果。为了对算法划分社区的质量进行监督，选择基于互补熵的社区评价函数[30]作为优化目标对当前社区划分结果 进行评价，如公式(2.10)所示。算法迭代进行，直至 F( )趋于稳定，得到最终的社区发现结果。本节给出基于“中心-扩展”策略的图聚类方法 PGC，包括节点相似性计算、中


本文编号：2984388