社交网络信息源检测算法研究

作     者：唐磐石 

作者单位：电子科技大学 

学位级别：硕士

导师姓名：李建平

授予年度：2016年

学科分类：08[工学] 080402[工学-测试计量技术及仪器] 0804[工学-仪器科学与技术] 

主      题：社交网络 信息流控制 观察点部署策略 信息源检测 

摘      要：互联网技术的发展,给人们的社交方式带来了巨大的改变,尤其是大批移动社交平台的出现例如微博、微信、QQ等,吸引了大量用户参与其中。这些用户来自社会的各个领域,通过这些社交平台参与社交,形成了各种各样规模宏大的社交网络。这些社交网络的出现为大量信息传播提供了更快速和范围更广的途径。社交网络信息源检测一直是非常热门的话题,检测出信息源,我们可以从源头上管理信息的分发以及保障社交网络健康发展。目前,基于现有社交网络拓扑来检测信息源成为社交网络研究中非常热门的方向。本文提出一种自适应观察点部署策略,使观察点的部署方案能根据网络拓扑的改变动态调整。然后,通过这些部署的观察点,记录消息在网络中的传播信息,计算肯德尔相关系数,实现单信息源检测。本论文的主要工作如下:(1)观察点部署策略研究。观察点部署问题的研究是基于r覆盖率最优化策略。其关键是提出一种方案,使得观察点集的r覆盖率达到最大。具体是建立数学模型将观察点集选取问题转换成集合覆盖问题,目前解决集合覆盖问题常用的一种方法是贪婪算法,但考虑到网络中节点的重要性,为了降低计算时间成本,优先考虑那些重要性较高的节点,它们对观察点集合的覆盖率影响远大于重要性低的节点,根据这种思想提出基于启发策略的贪婪算法。评价节点的重要性指标有很多,本文中使用度中心性来,先定义一个阈值,度小于这个阈值的节点不予考虑,相比较贪婪算法,基于启发策略的贪婪算法可以加快收敛,提高时间效率。(2)社交网络中单信息源的检测研究。在单信息源网络中,由于信息的发布者是唯一的,因此观察点收到信息的时间和观察点到信息源的距离有关。在大部分的社交网络中,节点之间的距离越短,信息在节点之间的传播时间越短。基于这种思想,对观察点收到消息的实际时间和观察点到候选信息源的距离之间的关系进行量化,计算出肯德尔相关系数,实现单信息源检测。另外,本文也提出基于时间差的单信息源检测算法。(3)实验验证本文提出的信息源检测算法。分别用模拟网络和实际网络验证本文提出的信息源检测算法。结果表明提出的算法既降低程序运行耗费时间同时提高了信息源检测准确率。