论文部分内容阅读
复杂网络的研究是现今科学研究中的一个重要研究方向。复杂网络中存在着大量的社团结构。发现复杂网络中的社团结构是了解整个复杂网络结构和功能的重要途径。随着信息量的急剧增长,经典的社团发现算法由于时间复杂度高,已经无法完成大规模复杂网络的社团发现,研究准确度高且时间复杂度低的大规模复杂网络的社团发现算法迫在眉睫。由于社团中的重要节点在社团中具有很大的影响力,所以发现社团中的重要节点对网络的安全、控制和监管具有重要意义。然而常见的重要节点发现算法考虑因素片面单一,且是用于寻找全网中的重要节点,因此,就需要探索考虑因素周全的社团中重要节点的发现算法。经典的社团发现算法主要研究的是无权网。无权网无法体现出网络中节点之间的连接强度,且大多真实的网络是加权网。这些网络用加权网络模型描述更加合理,因此本文在对复杂网络进行社团发现前先对具有社团结构的加权网建模。考虑到两点间的连接次数、共同邻点的个数和点权的影响,本文建立了基于共同邻点的加权网模型。本文分别对3个标准测试网络用基于共同邻点的加权网模型建模,验证了此模型中节点的度和点权都符合幂律分布。目前大多数的社团发现算法利用全局模块度对节点进行社团划分,时间复杂度高,本文提出了基于邻边的局部社团发现算法。结合局部社团的邻边特性,本文提出了局部社团的判断函数,并对加权网的边进行社团划分,发现重叠社团。然后定义了重叠点的归属判断函数对重叠点进一步划化,从而得到非重叠社团。本文对3个标准测试网络和2个大规模网络用基于邻边的局部社团发现算法划分社团,并与经典的社团发现算法对比。仿真结果表明,本文算法不仅准确度高且时间复杂度低,大大提高了算法的执行效率,适合发现大规模复杂网络中的社团。在划分得到的社团中,发现社团中的重要节点。针对常见的重要节点发现算法考虑因素片面单一,本文结合节点的连接状态、节点在社团中的位置、节点的权重及其邻居节点的影响,提出了社团中重要节点的发现算法。本文定义了加权网中的接近度因子、度中心性因子和邻点影响的附加因素,提出了社团中节点的重要度函数,利用此函数发现社团中的重要节点。通过对3个标准测试网络和2个大规模网络的仿真,发现了社团中的重要节点。与常见的重要节点发现算法相比,本文算法更合理且易区分开节点的重要度,适合用于大规模的复杂网络中。