论文部分内容阅读
复杂网络的研究自二十世纪末逐渐兴起,引起了数学、物理、计算机、社会学等科研工作者的广泛关注。社区结构的探测问题是复杂网络研究的一个重要分支。复杂网络中无权社区网络的研究已经不能满足当前对于网络分析的研究需要,而加权社区网络中边的权值表示节点之间的联系强度关系,对加权社区网络划分算法的研究有助于人们对真实网络的理解和发现加权社区网络中隐藏的信息。本文的主要研究内容如下:(1)为了提取加权社区网络中的重要节点,将网络边的权值融入结构洞理论的效率值计算中,设计了基于结构洞理论的重要节点提取算法。该算法首先将k-shell方法与改进后的结构洞效率值进行结合计算出每个节点重要程度的大小,然后根据重要程度对节点进行降序排序,从而达到提取重要节点的目的。最后在Zachary’s Karate club数据集上进行实验,结果表明,本算法比度中心性算法和接近中心性算法在提取重要节点方面的有效性显著提高。(2)针对目前基于相似度的社区网络划分算法存在的未考虑共邻节点、忽略边的权值以及时间复杂度较高等问题,设计了基于共邻节点及邻近度的加权社区网络划分算法。该算法从重要节点出发,结合加权后的局部模块度,通过聚类的方法进行加权社区网络划分。在仿真数据集以及真实数据集上进行实验,结果表明,对于仿真数据集,本算法运行时间比CRMA算法降低了 2.86%;对于Zachary’s Karate club数据集,本算法划分后的社区模块度比CRMA算法提高了4.51%。(3)为了提高加权社区网络划分算法的准确性,在基于共邻节点及邻近度的加权社区网络划分算法的基础上设计了基于遗传算法的加权社区网络划分算法。该算法将合并算子和拆分算子融合到遗传操作中,把加权后的模块度函数作为适应度函数,用寻优算子寻求最优解。在海豚网络数据集上进行实验,在模块度方面,本算法比加权FN算法提高了 4.15%,比WGN算法提高了8.85%,提高了加权社区网络划分算法的准确性。