论文部分内容阅读
在复杂网络中,节点可以被划分成若干组,组内节点之间的连接比较稠密,而不同组节点之间的连接则比较稀少,这样的划分结果被定义为复杂网络的社区结构。 通过对复杂网络社区结构的研究,一方面可以使我们更好地了解和解释现实世界中所呈现出的各种社区现象,如人际关系网络、疾病传播区域;另外一方面我们可以将复杂网络社区结构的研究理论成果应用到具体问题当中去,如可以设计出具有更好特性的实际网络。 在本文中,我们首先介绍了复杂网络社区结构的基本概念,以及用于复杂网络社区结构发现的若干著名算法,总结了不同算法所存在的优缺点。本文的重要成果如下: (1)提出了“基于DNA遗传算法的复杂网络社区结构发现”方法。此算法通过DNA编码的方式来形成DNA链(染色体),每个染色体都是一个潜在的针对问题的可行解。选择出最佳的若干染色体,进行交叉、变异等操作,从而使染色体产生新的特性,按照一定的标准计算染色体的适应度,并通过这种评价函数决定哪个染色体是适合问题的最佳解。该算法无需预知复杂网络的社区数量或者社区内的节点数量,同时实验结果表明该算法具有较高的准确度。 (2)提出了“基于PSO算法的复杂网络社区结构发现”方法。该算法采用“PSO算法”来分析复杂网络社区结构,它收敛速度快、易于实现并且仅有少量参数需要调整,初始化微粒的空间位置后,在复杂空间中对最优解进行搜索,实验结果表明该算法具有较高的收敛性。 我们用Zachary Karate Club和College Football Network模型对以上算法的准确性进行验证。上述两个模型是复杂网络的经典模型,该模型的社区结构是我们确切知晓的。