现实生活中存在各种类型的实体,实体之间的相互联系共同构成了大规模的、互联的、复杂的交互网络,这些网络被统称为信息网络。信息网络实体之间的链接关系蕴涵着丰富的语义信息,分析这些信息有助于发现更多有价值的潜在知识。随着信息网络逐渐呈现大规模化和复杂化,设计开发一种有效的软件程序去探索网络潜在数据结构显得更加必要。信息网络方面的研究工作涉及到很多领域,如聚类、社区挖掘、离群点检测、相似度搜索等。相似度搜索作为信息网络研究中的一个重要方向,在近年已经受到了广泛关注。对于给定的查询实体,相似度搜索的主要任务是研究如何从信息网络中找到top-k个最相似的实体。相似度搜索问题研究对于很多实际应用具有现实意义,如推荐系统、链接关系预测、近似查询等。传统相似度搜索方法依据网络全局信息计算实体相似度,需要很高的时间开销和存储开销,不适用于大规模信息网络,SimRank、 PSimRank、P-Rank等。具有X-Star模式的信息网络(简称X-Star网络)是一种重要类型的信息网络,在现实生活中越来越普遍。X-Star网络包括中心实体和属性实体,实体之间的链接关系包括中心实体之间的链接关系、中心实体与属性实体之间的链接关系。本文围绕X-Star网络中的相似度搜索问题展开研究。X-Star网络中的相似度搜索问题研究的主要任务是根据指定的查询(中心实体)找到top-k个最相似的中心实体。在X-Star网络中,相似的中心实体通常指向相似的属性实体或被相似的属性实体指向。基于这种直观意义,本文提出一种X-Star网络中的相似度搜索方案,针对相似度计算的效率和存储、在线查询处理的执行效率、相似度计算的精确度等几个方面存在的问题展开研究。本文主要研究工作概括如下：1.针对相似度计算的效率和存储问题,提出一种X-Star网络中的相似度计算模型(NetSim),解决了现有相似度计算模型中存在的计算效率低、存储开销大等问题。首先依据网络全局结构信息构建属性实体之间的链接关系,提出了属性网络构建算法。在属性网络基础上,通过借鉴SimRank基本思想计算属性实体相似度。结合属性实体相似度,提出了NetSim相似度计算模型,NetSim依据属性实体相似度计算中心实体相似度。在计算中心实体相似度时不需要物化所有网络实体之间的相似度,显著降低了相似度计算的时间开销和存储开销。在DBLP和Amazon两个数据集上做了大量的实验。实验结果显示,NetSim计算模型的时间开销和存储开销显著低于现有方法,并且具有很好的计算效果。2.针对在线查询处理的执行效率问题,提出一种X-Star网络中的top-k相似度搜索方法,显著降低在线查询处理的执行时间。首先提出了基于NetSim的在线查询处理基本算法(NetSim-baseline),分析了NetSim-baseline算法的时间复杂度,指出影响NetSim-baseline算法时间开销的主要因素。结合分析,提出了剪枝索引(Pruning-index),给出了剪枝索引构建算法。基于剪枝索引提出中心实体相似度近似计算公式,并提出一种基于NetSim的在线查询处理剪枝算法(NetSim-pruning)。对NetSim-pruning算法的相关性质进行了大量理论分析和证明,指出了NetSim-pruning精确度损失的理论上界。NetSim-pruning在保证精确度的前提下,显著降低了在线查询处理的时间开销。在DBLP和Amazo擞据集上的实验结果显示,NetSim-pruning算法的时间开销低,并且具有很好的查询效果。3.针对相似度计算的精确度问题,提出了一种信息网络中的相似度计算模型(E-Rank)。E-Rank计算模型的直观意义是：如果从两个实体出发能够到达共同的实体,那么这两个实体是相似的。E-Rank考虑了实体之间任意距离的相遇情况,同时强调了链接关系重要性,克服了现有方法存在的结构信息利用不充分和链接关系重要性考虑不足等问题。在Enron邮件网络和高能物理理论引文网络两个数据集上做了大量实验。实验结果显示,与现有相似度计算方法相比,E-Rank具有较高的精确度。结合E-Rank与NetSim,提出了一种新的中心实体相似度计算模型(ENetSim)。ENetSim在离线处理阶段采用E-Rank计算属性实体相似度,依据属性实体相似度计算中心实体相似度。在Amazon数据集上的实验结果显示,与NetSim相比,ENetSim提高了中心实体相似度计算结果的精确度。