随着各种在线社会网络的飞速发展,社会网络研究的节点规模上升到了数百万甚至是千万级。在线社会网络具有规模巨大,链路众多,关系复杂等特点。网络演化和结构特征研究是在线社会网络研究的两个重要方面,并可进一步扩展成为演化模型、关键用户识别和链路预测这三个问题。其中,网络演化研究的实质是网络的生成机制,具体包括网络中各组成部分之间的关系及其整体特征,是从局部对网络的宏观整体研究。中心性和用户行为是刻画网络演化的两个重要指标,其中,中心性既对社会网络的演化有着重要的影响,也是衡量用户重要性的关键指标之一,用户行为则是另一个评估用户重要性的关键指标,也是链路预测的关键依赖条件之一。在此基础上,网络演化、关键用户识别和链路预测这三个问题形成了一个有机的整体。本文主要针对网络演化和结构特征两个方面所涉及的上述三个问题进行深入研究,提出一系列模型与算法。本文的主要创新点工作和成果包括：网络演化方面(1)针对现有网络演化模型难以准确刻画在线社会网络加速增长过程中老用户对新用户产生关注关系这一问题,依次提出了概率复制增长模型、加速复制增长模型和带更新过程的加速概率复制增长模型,通过解析计算、模拟仿真和实际网络测量,结果均显示了上述模型与真实在线社会网络拓扑特征的一致性,能够很好的刻画真实网络的演化进程。(2)针对当前尚缺乏网络拓扑特性数学刻画方法这一问题,给出了针对前面所提出的三个网络演化模型的度分布、平均最短路径和簇聚集系数的解析方法,通过理论分析得出上述三个拓扑特征增长规律的同时,也对基于加速增长机制的演化模型网络特征的理论分析提供了借鉴和参考。网络结构特征方面(3)针对目前在线社会网络关键用户识别算法识别率低、排序片面等问题,考虑用户间动态“提及”关系及其频率的相对重要性,通过迭代方式量化了在线社会网络用户的关键性,在此基础上,提出了一种基于用户关系的关键用户识别算法,并给出了算法收敛性和时间复杂度分析。和主流算法对比,该算法可以避免僵尸粉欺骗、名人的普通朋友重要性偏高、排序片面等问题,能够更好地识别出在线社会网络中的关键用户。(4)针对现有在线社会网络链路预测准确度和精确度较低的问题,提出了一个基于用户行为特征的稀疏学习算法。该算法以用户关注关系作为分类特征基础,考虑用户间的“提及”关系,引入用户行为特征矩阵作为约束条件,利用核投影机(KPM)算法实现从高维Hilbert空间到最佳D维空间的选取,在此基础上实现用户间的有效链路预测。我们给出了该算法的表示定理并证明了算法的收敛性。实验结果表明,该算法链路预测准确度、精确度优于通用的SVM算法和TKPM算法。