基于单亲遗传算法的加权复杂网络社区划分问题研究

摘要

目前，复杂网络的研究聚焦着许多科研工作者的目光。随着复杂网络研究工作的深入，人们发现无权网络只能给出定结点间的相互作用存在与否的定性描述，而在实际的网络分析过程中顶点间的关系或相互作用强度的差异对网络功能的实现至关重要。如Internet网络上的宽带流量、科学家合作网中的合作次数等都是影响网络性质的重要因素，而加权网络恰能客观反映更丰富的信息，满足人们的需求。社团结构是复杂网络的重要特征之一，因此对加权网络的社团结构的研究也显得尤为重要。
　　 然而，大多数复杂网络社区划分算法都是针对无权网络提出的，而对于加权网络社区划分的算法还不多。本文提出利用单亲遗传算法对加权复杂网络进行社区划分。
　　 本文中，我们首先介绍加权复杂网络度量的概念，并将广泛应用于无权网络的模块度函数推广到加权网络中，提出新的适应度函数QwF函数来对加权网络社区划分进行评价。其次，分别介绍了无权和加权复杂网络社区结构划分较有代表性的算法。最后，在单亲遗传算法的理论基础上，将应用于无权复杂网络中的编码方案推广到加权复杂网络社区划分中，结合加权复杂网络的特点，提出了新的初始化方法，引入三种寻优算子，提高了算法的效率。