北京科学与工程计算研究院学术报告之六十二

报告人/Speaker: 孙晓明(中国科学院计算技术研究所)


报告题目/Title: 社交网络中累积激活与影响力最大化


时间/Date & Time: June19, 2018, 16:00—17:00


地点/Venue:北京科学与工程计算研究院M842报告厅


报告摘要/Abstract

影响力最大化旨在从社交网络中选择k个种子节点,使得这k个种子节点通过传播产生的影响范围最大。这个问题已经被广泛研究,但是大多的工作专注于一次传播模型,然而许多现实传播中用户需要经过多次累积影响才能做最终的决定。在此背景下,我们提出了一类累积激活模型:关于某一产品的信息在社交网络中按照独立级联模型被多次传播;每一用户都对应一个阈值,如果他/她所接收到的信息超过自身的阈值则被激活,否则不被激活。在此模型下我们讨论了两类组合优化问题:种子个数最小问题和激活节点最大问题。对第一个问题我们给出了贪心算法并分析了近似比,对第二个问题我们给出了不可近似性证明。最后我们在一系列真实的社交网络数据上做了对比试验,实验结果表明我们提出的近似算法比其它基准算法效果更好。


报告人简介/About the speaker:

孙晓明,中科院计算所研究员。主要研究领域:算法与计算复杂性,量子计算,社交网络算法研究,判定树复杂性等。曾获首批国家自然科学基金优秀青年基金资助,中国密码学会优秀青年奖、密码创新奖二等奖,入选中组部首批万人计划青年拔尖人才。目前担任CCF理论计算机专委会副主任,学术工作委员会主任助理,中国密码学会青年工作委员会委员,国际学术会议COCOON指导委员会委员,还担任《软件学报》,《计算机研究与发展》,《JCST》等杂志编委和《中国科学:信息科学》青年编委。