论文部分内容阅读
近年来,复杂网络作为交叉学科在很多领域得到了快速的发展,特别是在计算机领域得到了学者们的重视和研究。现实世界中的Internet、神经网络、蛋白网络、社交网络等可看作组成单元抽象为节点,组成单元之间的关系抽象为边的复杂网络。复杂网络的“小世界效应”,“无标度特性”和“社区结构”成为复杂网络的研究热点。随着复杂网络研究的不断深入,应用领域的不断拓展,如新陈代谢途径预测、Web社区挖掘、搜索引擎、开源软件等,新兴的领域的网络问题成为新的研究方向,主要包括:1)软件领域的网络特性;2)软件领域的网络模型演化;3)大规模复杂网络需要高社区发现精度和低复杂度问题;4)重叠社区结构的重叠程度和结果的质量问题等。本文围绕开源软件领域的网络特性、网络模型的演化和复杂网络社区发现问题展开研究,解决了开源软件网络的特性分析和开源软件网络演化模型中的相关问题,并提出了新的复杂网络的社区发现算法。本文的主要研究成果包括:1)选取两款面向对象开源软件框架Web Work和Spring作为研究对象,无(有)向图节点代表类,边代表类间的依赖、关联等关系,将系统抽象为网络图,并对其拓扑结构进行分析。研究表明无(有)向网络具有较大的聚类系数和较小的平均路径长度,具有小世界特性。实验结果表明:度分布统计特性仍然具有无标度特性。2)提出了一种基于局域事件的软件网络演化模型。该模型以面向对象软件系统为研究对象,对BA无标度网络模型进行改进,增加了节点和边的变化等局域事件,并应用该模型模拟软件网络的演化过程。实验结果表明,该模型演化生成网络的度分布服从衰减幂律分布,与真实软件网络的度分布基本一致,能较好地描述真实软件的演化增长情况。因此,该模型可以用于对面向对象软件网络演化进行模拟和评价。3)提出了一种马尔科夫随机游走蚂蚁社区检测算法。该算法受马尔可夫随机游走模型理论的启发,蚂蚁位于群集内任何节点的概率将大于蚂蚁位于群集外的概率。通过随机游走,揭示了网络结构。该算法是一种随机方法,它使用了在网络中的蚂蚁遍历期间收集的信息。在不同的数据集上验证算法,包括计算机生成的网络和现实世界的网络。结果表明,算法运行速度适中,提供了可接受的时间复杂度,其结果在实践中表现良好。4)提出了一种基于k-clique(派系)和遗传算法的复杂网络社区。该算法基于k-clique对种群初始化,采用(μ+λ)选择策略和Q函数来选择下一代种群,然后,对所形成的社区进行聚类,实现了社区划分。在基准网络和真实网络上完成了算法有效性验证实验。该算法可以提高种群初始化的精度和效率,父代在进化过程中形成的优良性状不会被破坏,并可有效地遗传给子代个体。同时,该算法减少了社区划分的搜索空间,提高了搜索效率。5)提出了一种基于Page Rank和节点聚类系数的重叠社区发现算法。算法使用Page Rank算法对节点的影响力进行排序,可以稳定社区发现结果,节点的聚类系数是一个与节点相关的值,使用节点的聚类系数修改算法的参数并限制每个节点拥有最多标签的数量,可以提高社区挖掘的质量。在人工网络和真实世界的网络上测试,实验验证了该算法能够有效地检测出重叠社区,并具有可接受的时间效率和算法复杂度。6)提出了一种基于k-clique的局部优化重叠社区发现算法。该算法假设clique是社区核心,采用密度最大的单个节点作为初始社区,使用基于适应度函数的局部优化搜索策略,在自然社区扩展时都添加k-clique,从而实现重叠社区的发现。提高了算法的搜索效率。在人工网络和真实世界的网络上进行了实验,实验结果表明该算法得到了更好的重叠社区发现精度。