伴随着互联网的普及和Web2.0技术的推广应用,在线社交网络(Online Social Network)已经逐步代替传统媒体成为信息传播的重要媒介和大众社会交流的主要平台。人们传递和获取信息的能力得到了前所未有的提高,信息通过用户之间的交互以扩散的模式进行快速传播,并在用户社交影响力的催化下动态演化,形成了不可忽视的舆论导向。社交网络中,极具传播影响力的重要节点对网络的结构和功能有着巨大的影响,应用复杂网络的理论和方法确定网络中的重要节点,探究社交网络中的信息传播规律,并利用这些规律合理引导信息传播,寻求导致影响力最大化的节点集合,有助于我们更好地理解这些复杂系统的特征,并对其进行更好地预测和控制。对实现最大化有用信息的受众,最大化产品推广的投入产出,遏制虚假信息和病毒的扩散具有十分重要的意义。相关研究结果在推荐系统、产品营销、公共健康、专家发现、突发事件检测和广告投放等领域有重要应用。国内外研究者在社交网络影响力分析领域开展了大量研究,也取得了丰硕的成果。但随着社交网络规模的日益扩张、用户数据的指数级增长、异构网络的融合发展等诸多因素的出现,此问题的研究也面临着新的挑战。(1)网络规模的指数级增长对节点影响力度量算法的效率提出更高要求,一些基于网络全局结构的度量算法性能较好,但时间复杂度很高,无法适用于当前复杂的网络环境;现有的基于网络局部结构的节点影响力度量对于节点的“簇中心性”识别较好,但对“桥连”特征挖掘不够充分。因此,在合理选择影响力相关因素的基础上,设计能比肩基于网络全局度量算法效果的精准、高效局部度量指标是研究者亟需解决的问题。(2)目前结合多个指标的节点影响力度量算法大都采用构造多元函数的方式将多种度量指标相结合,固定的函数形式影响了算法的普适性,排序学习算法为节点影响力排序问题提供了一种新的思路。利用排序学习融合体现节点影响力特征的多项度量,构建具有广泛适用范围的节点影响力度量模型有待进一步研究。(3)社交网络用户之间存在着友好和对立关系,网络中不平衡的边对节点影响力传播有着重要作用,已有研究成果缺乏对节点影响力和网络中不平衡边之间相互作用机理的研究。因此,网络不平衡性度量及不平衡边的识别问题亟待解决,其对节点影响力的促进和抑制作用需要进一步探讨。(4)在社交网络信息传播过程中,用户间信息传播概率的取值是诸多因素共同作用的结果,如用户间的协同作用、信息传播者的网络地位及行为、待激活节点与信息源的距离等。目前的研究成果较少考虑上述因素,协同机理下的信息传播规律还有许多未能从理论上做出合理的解释,亟需提出更加符合实际信息传播模式的传播模型,基于合理传播模型的高效影响力最大化问题近似算法也有待进一步探讨。本文以国家自然科学基金为依托,针对上述问题,围绕社交网络中影响力传播这一主题,在节点影响力度量和影响力最大化两个方面展开研究。首先,分析了网络中节点的结构特征,综合节点的半局部中心性和聚类系数,设计了一种高效的归一化局部中心性节点影响力度量算法;其次,在上述工作的基础上,进一步强化节点“桥连”属性的挖掘,利用排序学习方法构建了多指标融合的节点影响力度量模型;再次,考虑到节点之间的友好、对立关系是节点影响力分析中不可忽视的因素,提出了基于文化算法的社交网络不平衡边的识别方法,讨论了节点影响力和不平衡边演化之间的关系,为节点影响力度量指标从无符号社交网络到符号社交网络的推广提供方法和理论支撑;最后,分析社交网络上信息传播的影响力衰减现象,考虑协同效应对传播概率的影响,提出了基于协同效应的三步级联模型,探讨了此模型下的影响力最大化问题,设计了基于协同效应的三层累积影响力最大化算法。本文的主要工作和创新点包括以下四个方面:(1)提出了一种归一化的局部中心性节点影响力度量算法。针对网络规模指数级增长带来的算法效率问题,本文分析网络中最具传播影响力节点的特征,探讨节点聚类系数和节点影响力的相关性,提出了一种归一化的局部中心性节点影响力度量算法(normalized local centrality,NLC),综合节点的半局部中心性和聚类系数来度量节点影响力。不同于已有的基于局部网络的中心性度量算法,NLC同时考虑了节点局部网络的拓扑信息和最近邻节点的影响力反馈。具体而言,节点局部网络包括此节点和其四阶邻居节点,局部网络的拓扑信息包括局部网络内的节点数目和节点间的拓扑连接特性。最近邻节点的影响力反馈通过最近邻节点的传播影响力加权和进行度量。为消除不同指标取值范围的差异,本文对节点局部网络的特征指标进行归一化处理,避免了其他算法中因为确定参数值而导致的额外开销。为验证NLC算法的性能,本文在8个网络上进行实验,选择传染病模型(susceptible-infected-recovered,SIR)进行信息传播过程仿真,得到节点的真实传播影响力,以此为基准比较了NLC和其他6个影响力度量算法(DC、BC、CC、KS、LC和LSC)的性能。实验表明,NLC能更加准确的挖掘网络中的重要节点,具有稳定的性能,表现优于其他6种算法。(2)提出了一种基于Listwise和网络表示学习的多指标融合节点影响力度量模型。目前,重要节点识别算法主要基于多个度量指标的加权和或多元函数的形式进行设计,这类做法一方面会引入新的参数,增加算法的复杂度,另一方面,面对社交网络结构的多样化,固定的函数模式难以保证度量算法的通用性和普适性。针对上述问题,本文构建了基于Listwise和网络表示学习的多指标融合节点影响力度量模型(multi-index measure based on Listwise and network representation,MLNR),该模型选取了三种节点影响力度量指标:NLC算法来挖掘节点局部网络特征;基于网络表示学习的BIGCLAM模型来挖掘节点的“桥连”属性;网络约束系数来体现邻居拓扑对节点重要性的影响。为有效融合三种指标,引入了排序学习算法Listwise将上述三个指标作为学习特征,通过排序学习获得参数,经过交叉验证得到最终的参数值,构建多指标融合的节点影响力度量模型。实验表明,该模型能得到更加准确的节点影响力序列,对于大规模社交网络,其排序得到的top-k节点相较于其他算法能导致更大范围的影响力传播,具有更强的实用性,并且在模拟Sybil攻击的噪声数据集上也表现出了很好的鲁棒性。(3)提出了一种基于文化算法的社交网络不平衡边的识别算法,并分析了节点影响力和不平衡边演化之间的关系。社交网络中节点间的友好、对立关系是节点影响力分析中不可忽视的因素。本文基于结构平衡理论,针对边具有正负属性的社交网络的不平衡性度量进行研究,提出了一种基于文化算法的社交网络不平衡边的识别算法(culture algorithm for signed network balance,CA-SNB)。该算法利用伊辛自旋玻璃模型(Ising spin glass model)构造优化函数,描述网络的状态,设计了一种具有双层进化结构的文化算法进行求解,通过对节点进行符号划分寻求最小的不平衡边数,并识别边的位置,实现了在计算网络不平衡度的同时确定不平衡区域。在真实网络上的实验表明,该算法收敛速度较快,其得到的最优解可以更加准确的描述网络所处的演化状态。在此基础上,本文讨论了节点影响力和不平衡边演化之间的关系,这一工作为节点或边的度量指标从无符号社交网络到符号社交网络的推广、基于用户情感极性的节点影响力度量以及社交网络推荐和舆情分析等关键问题的研究提供方法和理论支撑。(4)针对大规模社交网络中影响力最大化问题,提出了一种基于协同效应的三步级联模型并基于此模型设计了三层累积影响力最大化算法。协同效应在社交网络中普遍存在,它能够增大节点之间的信息传播概率,并在一定条件下导致信息在社交网络上的爆炸式传播。此外,信息传播过程中存在着影响力衰减的现象,信息传播的三度影响理论(three-step influence theory)在很多实际信息传播过程中得到了验证。基于上述两点,本文首先讨论了协同作用对传播概率的影响;其次,以新浪微博数据为例验证了信息传播的三度影响理论,在此基础上,提出了一种基于协同效应的三步级联模型(synergism-based three-step cascade model,TSSCM);然后,探讨了TSSCM下的影响力最大化问题,提出了一种基于协同效应的三层累积影响力最大化算法(three-layer collective influence with synergism,CI_TSL),该算法在Collective Influence的基础上增加协同效应和传播动力学分析,更加完善的定义了影响力累积现象;最后,基于TSSCM模型和IC模型,本文在6个大规模社交网络上,从种子节点集合的传播影响力以及算法的运行时间方面验证了本文所提模型的合理性和影响力最大化算法的有效性。