摘要：因特网和Web2.0技术的飞速发展催生了在线社交网络的迅速普及,如Facebook、Twitter、新浪微博等。大规模在线社交网络已经在很多方面开始影响人们的生活方式,特别是在信息的扩散和传播方面,吸引众多学者对其进行研究。本文对社交网络进行了两方面的研究：节点影响力的评价研究和节点影响最大化研究。以微博网络为代表的新型在线社交网络中存在高影响力节点,对信息在网络中的传播起着至关重要作用。快速高效地找出这些节点有助于研究舆情控制、研究网络个体关系,有助于使网络中信息更有效地传播。在评价节点影响力的问题中,传统的度中心性方法虽然简单但是效果不好；介数中心性具有准确的评价效果,但是计算节点的介数值需要基于网络的全局信息,计算开销大,在大规模网络中并不适用。本文在节点影响力评价问题中基于PageRank算法的投票思想,提出了精确高效的节点影响力排序算法评价网络中节点的影响力。根据在线社会网络中边关系的复杂性,本文在SIR传播模型基础上提出不同边具有不同感染概率的新型传播模型。在新浪微博真实用户关系数据集中,本文提出的新型排序算法相比介数中心性和PageRank算法具有更好的性能表现。在市场营销中,利用用户之间的“口碑效应”的“病毒式营销”方案得到了众多学者的关注。如何有效选择k个节点组成种子集合使得影响范围最广是当前的热点问题,称为节点影响最大化问题。Kempe证明影响最大化是NP-hard,并提出了贪心算法,具有较好结果。对于贪心算法计算开销大,不适用于大规模社会网络的问题,混合式算法有效解决了时间开销问题。混合式算法分为启发阶段和贪心阶段,利用线性阈值模型影响力积累特性,在启发阶段利用节点邻域信息选取最具“潜力”节点,这些激活的“潜力”节点所具有的影响力能够让周围的未激活节点更容易被激活,使得最后种子集合的激活范围更广。本文提出NPG算法在启发阶段充分利用节点邻域信息,考虑节点的连接强度和出边邻居传播能力差异性,提出更有效的“潜力”节点选取策略。在贪心阶段,NPG算法通过每一轮提前对当前种子集合进行传播,得到当前的激活集合,避免对集合中的节点计算边际收益,大大减少了重复的计算量,提高了贪心阶段的效率。