基于两阶段启发的社交网络影响最大化问题求解方法

摘要

本发明公开了基于两阶段启发的社交网络影响最大化问题求解方法，属于社交网络分析领域。该方法的处理过程如下：利用线性阈值模型的累积特性，将整个影响最大化算法过程分成两个阶段：(1)度折启发阶段。使用度折策略选取度数最大的种子节点，然后利用种子结点在整个网络中进行节点激活并将节点的影响力积累下来；(2)影响力启发阶段。选取影响力最大的节点作为目标节点，然后利用目标节点进行节点的激活。为了加快算法的求解速度，本发明在影响力启发阶段设计了一种近似估计节点影响力的计算方法。本发明能有效、快速的发掘出社交网络中的初始种子节点，有效的解决社交网络中的影响最大化问题，可用于市场营销，舆情监控和广告投放等领域。

主权项

基于两阶段启发的社交网络影响最大化问题求解方法，其特征在于包括下述步骤：第一步，输入网络数据，计算各节点的“度数”，该度数需要经过一定的折扣计算，并对节点按照“度数”递减排列；第二步，选取“度数”排在前k₁的节点作为种子节点加入种子节点集S，然后利用S根据线性阈值模型的传播过程对未激活节点进行激活，最后将激活的节点加入激活节点集A中；第三步，更新各未激活节点所受影响力；第四步，计算各节点产生的影响力，并对节点按照影响力的大小递减排列；第五步，清空种子节点集S，选取影响力排在前k₂的节点作为种子节点加入种子节点集S，然后利用S根据线性阈值模型的传播过程对未激活节点进行激活，最后将激活的节点加入激活节点集A中。