关联影响力传播最大化方法

社会网络中影响力传播最大化是社会网络分析领域所关注的重要问题。针对多个影响力同时进行传播,且影响力间存在传播促进的情况,提出关联影响力传播最大化问题。首先,对经典线性阈值模型进行扩展,提出关联影响力线性阈值模型对关联影响力传播过程进行建模;其次,定义了关联影响力传播最大化问题,证明了该问题是NP-hard的,以及问题目标函数满足子模性;再次,针对该问题提出基于结点激活贡献估计的求解算法;然后,利用结点激活贡献估计存在相互独立性,进一步提出了并行化求解算法,并在Spark GraphX并行图计算框架上实现了该算法;最后,在真实的社会网络数据集上,通过实验测试验证了所提出方法的有效性。

知识图谱的Top-k摘要模式挖掘方法

知识图谱数据具有体量大、内容丰富、类型多样、缺乏统一模式描述等特点。提取知识图谱模式信息并形成摘要模式,对于提升知识检索、挖掘质量具有重要研究意义。该文首先给出了摘要模式的判定准则以及摘要模式质量的度量标准,提出了面向知识图谱的Top-k摘要模式挖掘问题,并将该问题建模为一个次模函数优化问题;其次,为高效判定摘要模式及度量模式的覆盖质量,提出了基于Pregel编程模型的并行化摘要模式判定和质量度量算法;然后,给出了高效求解Top-k摘要模式挖掘问题的贪心算法;最后,在真实知识图谱数据上对本文方法进行了验证。实验结果表明:该方法在摘要模式的覆盖度和算法执行效率方面优于已有方法。