摘要
随着移动互联网的快速发展，人们在各种社交媒体上的交流和互动形成了各式各样的社交网络。影响力最大化（InfluenceMaximization，IM）研究是社交网络分析的一个重要领域。其在舆情管理、病毒式营销等领域有着重要的应用背景。经典的影响力最大化研究主要基于中心性的启发式方法，这类方法具备一定的灵活性，但性能往往无法得到保证。基于网络嵌入的方法最近广受关注，这类方法具有优秀的性能表现和可扩展性。不过，大多数基于网络嵌入的影响力最大化研究，并没有考虑到网络中的层级结构信息对节点表示学习的增强作用。此外，这类算法大多是在节点嵌入的基础上，结合节点计数或聚类的方法来研究影响力最大化问题，而这些方法无法适应具有不同结构特征的大规模社交网络。而结合机器学习方法来训练一个回归模型用来预测未知数据的影响力值，具有较好的灵活性和扩展性。因此，本文结合网络嵌入算法的特征提取能力和机器学习的泛化能力来研究影响力最大化问题。本文的主要创新点如下。 针对网络嵌入方法，本文提出了一种基于层级结构随机游走的网络嵌入算法——KCNE。该算法首先使用k核分解方法将网络中的节点划分为不同的层级，并使用定制的随机游走方式来捕获节点的一阶邻域及同层级中的高阶相似节点，以此来为节点生成游走序列；随后将游走序列输入到skip-gram模型中，使学习到的节点表示有效地保留了节点的近邻性和层级结构相似性。在多个数据集上的实验结果表明，在链路预测与节点分类任务上，KCNE算法的性能优于8个经典的网络嵌入算法。此外，参数敏感性分析实验也表明了该算法具有较好的鲁棒性。 为了有效地识别出社交网络中的影响力节点，在结合KCNE算法的基础上，本文提出了一种影响力节点识别算法——KCNE_KNI。该方法首先使用KCNE算法来学习节点的表示，然后进行聚类并通过配额方法采样少量节点，随后通过传染病模型（Susceptible-Infected-Removed，SIR）来模拟样本节点的传播能力，以此来训练一个回归模型用于预测未知数据的值。此外，为了更有效地评估节点的影响力，本文提出了基于局部结构的影响力得分（LocalStructureInfluenceScore，LSIS）来评估节点的重要性。在多个真实数据集上的实验结果表明，在Jaccard相似系数和Kendall’sTau相关系数上，KCNE_KNI算法的性能优于4个基于启发式的中心性算法和6个基于网络嵌入的计数方法。此外，参数敏感性分析实验也表明了KCNE_KNI算法具有较好的鲁棒性。
NETL