【作者】王中义

【论文题目】软件系统函数调用关系的复杂性研究

【摘要】近年来，国内外众多专家学者普遍认为复杂网络已成为研究复杂系统最为重要、最富挑战性的课题之一。随着小世界网络模型和无标度网络模型的提出，复杂网络领域再次掀起了新一轮的研究热潮。研究表明，诸如互联网、新陈代谢网、科学家合作网和人际关系网等各种真实复杂网络均具有小世界效应和无标度网络特征。 软件源程序中的函数调用关系图是一个复杂网络。有证据显示软件系统中在源程序的类层次或函数层次上表现出幂律分布。本论文采用复杂网络的方法来研究软件源程序中函数调用关系。论文对两个大型开源的太空仿真软件Celestia和Stellarium的源程序中函数调用关系图进行了实例验证，发现其表现出小世界及无标度特性，这与其它已经验证过的社会关系网、生物网和技术网非常相似。论文首先分析了复杂网络的主要特征，重点描述了复杂网络的四个经典模型：随机图模型、小世界网络模型、无标度网络模型以及加权网络模型。通过对两款开源软件的源程序中函数调用关系的分析，提出函数调用关系图生成算法，编写Perl程序并结合Gephi软件实现函数调用关系图的生成，对函数调用关系图进行实证研究。然后论文中对函数调用图的平均路径长度、度分布及聚类系数等相关指标进行计算和分析，最终得出结论：软件源程序中函数调用关系图符合幂律分布，该图属于无标度网络，并具有小世界效应。