论文部分内容阅读
21世纪,人们获取信息的途径不再局限于报纸、广播和电视,随着Twitter、Facebook、Flickr等重要社交网络的出现及迅速发展,社交网络逐渐成为了这个时代承载信息的主要媒介。由于社交网络影响力最大化问题的研究在实际应用中有着重要的指导意义,因此,该问题也成为了计算机科学研究的热点。本文围绕社交网络影响力最大化问题的模型与算法展开研究,具体包括：1.给出影响力最大化问题的形式化定义,针对信息传播方式(途径),分析目前最重要的一些信息传播模型以及影响最大化问题在不同模型下的相应定义,并简要总结影响最大化问题的一些解决方法并分析其利弊,为研究影响力最大化的模型与算法打下理论基础。2.每个节点的不同父节点对该子节点的影响力是不同的,基于此,指出传统信息传播模型假设的不合理性,提出了一种融合节点相关性与节点重要性的PRP模型(PageRank-based Propagation Model,简称PRP模型),该模型考虑到社交网络中任何节点的不同父亲节点对该节点有不同的影响强度,实验表明,基于PRP模型的方法在解决影响最大化问题的效果比传统的基于线性阈值模型、加权级联模型和独立级联模型的方法更好,影响力范围更广。由于PRP模型考虑到了社交网络的实际情况,具有较好的实用价值。3.传统贪心算法及其改进算法在大规模的社交网络中解决影响最大化问题的时间复杂度很高,针对该问题,本文基于概率转移矩阵的思想提出了一种扩展的线性阈值模型,并基于该模型提出了一种新的基于概率转移矩阵的影响最大化算法(An New Algorithm Based onProbability Transfer Matrix Method,简称PTMA)。由于PTMA算法节省了每个时间间隔都要统计活跃节点数目的时间,因此,该算法与其他基本贪心算法相比,节省了算法时间,降低了时间复杂度,效率更高,并适用于大规模社交网络。