纷繁复杂的大自然和人类社会中,很多系统都是由一些相对独立的个体与其周围的环境构成的。所以,要对系统进行分析,必须要将个体特性与他们的作用环境考虑在一起。自然科学、社会科学中很多存在相互作用关系的系统都可以用较为真实、全面的复杂网络模型来刻画,这样就可以将非常复杂的系统,利用结构明显且可视化效果相对较好的数学图结构来呈现。复杂网络中的链路预测是一个基础性理论问题,也是数据挖掘领域的一个重要方向,从生物科学到计算科学都有广泛的应用。近几年才兴起的网络重构是链路预测的一个重要研究方向。网络重构要解决的问题是当我们获得的网络连边信息不全或者有虚假连边的情况时,如何通过已知的网络信息来还原较为真实的网络。这样能帮助人们更好地研究网络的性质,或者根据网络的结构进行改造或控制,使网络能够按照人们期望的方式来运行。本文主要研究了网络重构两个方面的内容,其中重点是关于具有社团结构网络的重构算法的研究;作为此工作的拓展性研究,本文又进一步分析了现有经典链路预测算法,在网络重构中的错边识别能力。主要成果如下:(1)本文提出一种针对具有社团结构的网络行之有效的重构方法。现有的链路预测算法在重构网络时,多数仅从网络的结构属性进行考虑,很少考虑网络的功能重构情况。而且,现有的经典算法,多数在发掘网络社团间边的能力比较差。对于具有社团结构的网络,网络中社团间的边对于社团间传递信息非常重要,例如社团间边缺失可能导致网络信息流通不畅。本文的算法以一些经典算法为基础,结合网络性质,进行了有针对性的改变,在实现网络较好的结构重构的同时,利用边平均介数来反映网络功能重构效果,尽量保证网络功能重构的真实性。在算法中本文还加入了学习机制来保证算法的准确性和普适性。(2)本文还分析了现有的一些经典算法在网络错边识别方面的表现。目前,相关领域的学者已经提出了很多链路预测的算法,他们的主要建模角度是利用节点间的相似性,更好地预测网络中的未知连边或未来连边。然而要实现网络较好的重构效果,还需要考虑如何识别网络中的错误连边。我们计算对比了 21种经典算法在不同网络上、不同划分比例下的连边预测和错边识别的能力。确定了在两个方面表现都相对较好的算法。本文针对具有社团结构的网络提出了一种切实有效的网络重构方法,丰富了社团结构网络重构的方法,同时在一定程度上实现了网络的功能重构。在实际应用中,很多现实的网络系统都有集团结构,例如,空手道俱乐部网络、物理学家合作网、万维网等,这些网络中对于社团间边的预测尤为重要。对经典算法重构性能的研究,有助于相关领域学者对经典算法有较为全面的认识,同时能帮助人们在应用算法时选择合适的算法。总体来说本文为相关学者提供了新的构造链路预测算法的思路,人们可以在考虑网络结构性质的同时,尝试结合网络的功能性质,必将有所发现。