基于弱连接理论与图挖掘技术的软件变更传播研究

Complex networks studies have shown that the network structure has a great influence on the features of the network, and the topologies of large-scale software systems exhibit complex network features such as “small world” and “scale-free”. In this project, we combine the features of network structure and the studies of software change propagation to accomplish four tasks: First, we explore the relationship between the network features and software change propagation in different versions of open source software by collecting the global features of software network and proposing a quantitative definition of software change propagation. Second, based on Granovetter, Friedkin and Lin’s definition of Weak Ties, we propose a definition of Weak Ties that is suitable for the analysis of software change propagation effects. Third, we explore graph mining to find out the frequent patterns of software changes by the analysis the law of software change propagation law, and design efficient mining algorithm by the influence of the weak links on software network. Last, we propose a more accurate prediction method of software change propagation by quantifications of the Weak Ties’ influence on software change propagation because the prediction methods in software engineering area ignore the effect of network structure. This project will contribute to a scientific and comprehensive understanding of the nature of software change propagation as well as provide a reliable basis for future maintenance of software systems.

复杂网络的研究表明，网络结构对于网络的性质有着重要影响，而大型软件的内部拓扑结构具有“小世界”和“无标度”等复杂网络特征，本项目将软件网络结构特征与软件变更传播的研究相结合，进行以下工作：1）以不同版本的开源软件作为研究对象，收集软件网络的全局特征，提出刻画软件变更传播影响的量化指标，探索网络特征与软件变更传播的关系；2）结合Granovetter、 Friedkin、Lin等人提出的弱连接的定义，研究适用于分析软件变更传播影响的弱连接定义；3）分析软件变更传播规律，利用图挖掘技术找出软件变更中的频繁模式，结合弱连接对软件网络的影响，设计更高效的挖掘算法；4）软件工程领域的变更传播预测方法忽视了网络结构的影响，本项目通过量化弱连接对软件变更传播的影响，提出更准确的软件变更传播预测方法。本项目的研究有助于科学、全面地认识软件变更传播的本质规律，为将来软件维护提供可靠依据。

复杂网络的研究表明，网络结构对于网络的性质有着重要影响，而大型软件的内部拓扑结构具有“小世界”和“无标度”等复杂网络特征。本项目提出了适用于分析软件变更传播的弱连接定义，通过量化弱连接对软件变更传播的影响，提出了更准确的软件变更预测方法。同时，将弱连接研究工作应用于其他大型网络数据集，验证了我们弱连接定义描述复杂网络特征的有效性。本课题主要完成了以下科研成果：.1.基于Linux内核源码，统计了每个版本的代码行数、git和开发人员等信息，观察分析了内核的演化趋势。获取了内核版本间增加函数、删除函数、变更函数、增删的行数以及上述变化在各个模块的占比，进而初步分析影响内核演化的因素。.2.本项目提出了描述软件内部网络特征的弱连接定义，即边的不稳定性。同时设计了软件变更传播模型和网络生成模型用于验证边的不稳定性对变更传播的影响。实验结果显示，边的不稳定性更好地描述了影响变更传播的网络特征。.3.将基于边的不稳定性的弱连接研究工作应用于大型网络数据集ego-Twitter、soc-Epinions1、soc-Slashdot0811、web-BerkStan、 web-Google和web-NotreDame。实验结果表明，边不稳定性不仅可以有效地描述软件网络结构特征，而且对于其他网络同样具有普适性。.4.基于复杂网络理论研究了模块与结构稳定性的关系，发现模块变更对结构稳定性可能产生的影响。本项目将社区划分算法运用在Linux内核研究中，提出了社区模块系数发现分析函数变更对内核模块变更的影响。.5.本项目的研究发现，软件网络函数调用图具有整体特征，其中某个函数的变更也会对其他相关函数造成影响，因此提出了基于图挖掘技术和网络嵌入的变更函数预测模型以发现后续版本可能发生变更的函数。.截止2020年12月，在国内外期刊和会议发表11篇论文。其中SCI检索论文3篇（Q1区一篇，影响因子5.91），EI检索论文6篇（CCF C类会议1篇）。培养博士研究生2名，硕士研究生7名。