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

报告人/Speaker: 张家琳(中国科学院计算技术研究所)


报告题目/Title: 社交网络影响力传播模型中局部函数和全局函数的关系


时间/Date & Time: June 19, 2018, 11:00-12:00


地点/Venue:北京科学与工程计算研究院M843会议室


报告摘要/Abstract

在影响力传播模型中,节点通过局部的阈值函数决定是否被激活,若被激活则会将信息进一步传播给邻居。全局来看,最终能影响到的节点个数是初始种子集合的函数。这里,我们关心局部函数和全局函数之间的关系。Kempe, KleinbergTardos (KKT) 曾对一般阈值模型提出过这样的猜想:局部函数的单调性和次模性能推出全局函数也满足单调性和次模性。这个猜想已经被MosselRoch证明是正确的。在这个报告中,我们提出了局部函数次模性的高阶推广,称为AD-k性质。其中,单调性对应AD-1性质,单调性+次模性对应AD-2性质,并提出了KKT猜想的高阶版本:在一般阈值模型中,局部函数满足AD-k性质可以推出全局函数也满足AD-k性质。我们证明了对DAG(有向无环图),这个猜想是正确的。并证明了对任何图,这个猜想对AD-无穷是正确的。


报告人简介/About the speaker:

张家琳,中科院计算所副研究员。她于2010年在清华大学应用数学专业获得博士学位。2010-2012年,在南加州大学做了两年博士后,于2012年加入中科院计算所。主要研究领域是理论计算机科学,主要的研究方向包括:在线算法、社交网络、算法博弈论、组合优化等等。