图作为一种重要的数据结构,常用于刻画自然界或社会中事物间的复杂关系。随着信息技术的发展,图模型逐渐覆盖生活各个方面,相关数据迅速增加,如社交、交通、蛋白质之间相互作用等都可以用图模型进行刻画。挖掘图中信息可以帮助人们优化推荐系统、设计高效网络、预测蛋白质功能等。如何高效的进行图挖掘已经成为一个研究热点。随着图数据增加,求解图挖掘问题的算法近年来也得到了长足发展。根据求解基本策略不同主要分为优化算法和启发式算法。但优化算法面对大规模问题时仍然存在搜索效率低的问题,启发式算法也面临易陷入局部最优解等问题。无论基于优化的算法还是启发式算法,如何提高算法效率,高效进行图挖掘问题求解是当前亟待解决的问题。生物启发一直都是推动算法发展的重要动力。最近研究中,一种名为多头绒泡菌的粘菌在觅食过程中展现出自组织、自优化等智能特性引起广泛关注。利用多头绒泡菌仿生模型,本文对现有图挖掘算法进行优化,以期提高算法效率。本文着眼于图挖掘中子图挖掘问题和图聚类问题进行研究。首先对多头绒泡菌仿生模型的图挖掘能力进行进一步探究,扩展其求解问题范围。然后利用多头绒泡菌仿生模型的特性,对代表性的图挖掘问题设计了针对性的算子和算法,对当前图挖掘算法进行优化。本文的主要贡献包括以下两个方面:1)针对子图挖掘中典型的组播树问题,本文提出了基于多头绒泡菌仿生模型的遗传交叉算子,以提高遗传算法的局部搜索能力。首先对多头绒泡菌仿生模型进行了修改,使得模型可以求解最短路径树问题。之后针对多头绒泡菌最短路径树模型计算复杂度较高的问题,优化了模型中的迭代过程。最后基于优化后的多头绒泡菌最短路径树模型,本文提出了一种新的遗传交叉算子(PMcrossover),并将PMcrossover嵌入到三种典型的遗传算法中。通过和原算法在四个数据集上进行对比,说明基于多头绒泡菌的交叉算子可以有效的提高算法的搜索效率和鲁棒性,验证了PMcrossover的有效性。2)针对图聚类中典型的社团挖掘问题,本文从优化算法中的进化算法和启发式算法中的马尔可夫聚类算法两个方面进行求解。进化算法以遗传算法和蚁群算法为代表。为了探究多头绒泡菌仿生模型在图聚类问题上的潜力,本文对多头绒泡菌网络模型进行修改,使得其可以一定程度上区分社团间和社团内的边。之后将多头绒泡菌仿生模型对边的识别作为先验知识整合到了遗传算法的初始化过程和蚁群算法的启发式因子中,提出了进化算法优化策略。对于启发式算法,本文以马尔可夫聚类算法为代表。通过进一步研究发现,多头绒泡菌模型中的正反馈系统和马尔可夫聚类算法中的动态系统基于类似的基本假设。根据这个特点,模仿多头绒泡菌仿生模型中的正反馈关系,在马尔可夫聚类算法中建立了新的反馈流。同时,本文对典型马尔可夫聚类算法中主要算子进行优化,提出多头绒泡菌启发的马尔可夫聚类算法。最后在12个数据集上,从准确率、鲁棒性、时间复杂度等方面验证了提出方法的效果。综上,本文在对多头绒泡菌仿生模型进行研究的基础上,充分挖掘其图挖掘潜力,并对现有进化算法和马尔可夫聚类算法进行优化,对典型的子图挖掘问题和图聚类问题进行求解。同时,通过广泛实验证明了基于多头绒泡菌模型的优化策略能有效提高图挖掘算法的搜索效率和鲁棒性,多头绒泡菌启发的算法能高效的完成图挖掘任务。