对象间的相似度计算是当前数据挖掘领域的重要研究课题之一。近年来,在Google网页排名算法PageRank的推动下,基于网页链接分析的普适相似度模型研究热潮席卷全球,以SimRank SimFusion、Penetrating-Rank(以下简称P-Rank)为代表的新相似度模型相继问世,成为目前国内外共同关注的热点问题。随着Internet网络规模的日异膨胀与应用需求的不断提高,这些新出现的相似度模型理论已端倪渐显,但尚有一系列科学技术难题亟待解决,主要包括算法的时空复杂度优化、误差与稳定性分析、规模可扩性问题等。针对这类相似度模型的核心理论与算法优化问题进行研究,可为网页排名、协同过滤、搜索引擎优化、网络图聚类等提供坚实的理论和技术基础,具有重要的科研和应用价值。本文针对三种基于链接的新相似度模型(即SimRank、SimFusion、P-Rank),旨在深入研究这些相似度计算的优化问题,其中包括：相似度解的精度控制、加快迭代的收敛速度、降低计算时间与内存空间的代价、实现并行计算与增量算法等。结合这三种模型递归定义的特点,本文重点对相似度高效计算的关键技术进行研究,通过矩阵优化等途径,在可控精度下提高相似度算法性能并降低其代价开销。此外,本文还对这些相似度模型进行改进,研究并实现了具有可控精度、高稳定性、低时空复杂度特点的结构相似度改进算法。主要研究成果如下1)提出了SimRank相似度计算的优化方法。利用矩阵形式表示SimRank方程,设计出一种新的SimRank迭代范式,可以指数级加快SimRank解的收敛速度。通过建立低维的Krylov子空间,把原SimRank方程(n×n维)投影到这个低维子空间(r×r维)计算,从而使计算时间由原来的O(Knm)降为(?)(rm＋r2n＋Kr3),内存空间由O(n2)降为O(rn),其中n,m是图的总结点数和边数,r(《n)是邻接矩阵的秩,K是总迭代次数。为进一步降低SimRank时间复杂度,对无向图的SimRank进行优化,借助邻接矩阵的特征向量分解,将计算时间再降到(?)(rm+Kr2),同时实现无向图的SimRank并行算法。2)改进了SimFusion模型并优化其相似度算法。针对原SimFusion模型中存在的两个问题——同构网络中的发散解、异构网络的平凡解.提出一种改进的SimFusion模型(下称SimFusion+),通过引入一致邻接矩阵(UAM)和“推迟行归一化”操作,确保SimFusion+方程解的存在唯一性。为解决SimFusion+计算的优化问题,利用UAM矩阵的主特征向量表示SimFusion+相似度,把计算时间从原先的p(Kn3)降为O(n2),内存空间由O(n2)降到O(n)。还探索了SimFusion+的近似算法与增量算法,分别适用于大型与动态网络图上的相似度计算,解决了SimFusion+算法的规模可扩性问题。3)优化了P-Rank模型的计算。通过矩阵形式给出P-Rank相似度的两种表现形式——逆矩阵式、幂级数式。基于P-Rank逆矩阵式,利用转移矩阵的奇异值分解,提出一种新的P-Rank确定性算法,把计算时间由原来的O(Kn4)降为O(v4n2+v2n),同时给出误差估计,其中v(《n)是一个时间与精度权衡参数。基于P-Rank幂级数式,结合Monte Carlo法,提出一种规模可扩的P-Rank随机算法,把计算时间进一步降到O(Nn),其中N是样本大小。还通过定义P-Rank条件数并估计其上界,研究P-Rank相似度的稳定性。在无向图中,利用矩阵对角变换,提出一种P-Rank非迭代算法,把时间再降为O(vn2)。在人工与实际数据集上的实验结果表明,基于链接结构的三种相似度模型经算法优化与模型改进后,具有时空复杂度低、稳定性强、规模可扩、精度可控等特点,其计算性能比原先的算法提高若干数量级,这些模型在大规模网络图上计算有显著的加速效果。尤其是提出的并行和增量相似度算法能有效降低代价开销,改善相似度在多处理器、动态网络图中的计算性能。相关研究成果为结构相似度的计算提供了较好的解决方案和理论分析基础,可肖接适用基于网页链接的搜索引擎算法设计与实现。