近日，信息科学与技术学院四川省云计算与智能技术高校重点实验室李天瑞、郑宇教授指导的2015级博士生纪圣塨同学及其合作者，以共同第一作者在《美国科学院院刊》（Proceedings of the National Academy of Sciences of the United States of America, PNAS）上发表题为”Local structure can identify and quantify influential global spreaders in large scale social networks”的研究论文。PNAS创刊于1914年，被公认为四大名刊之一（Nature、Science、Cell、PNAS），是被引用次数最多的综合学科文献之一。
现代在线社交网络规模巨大（微信、微博、Facebook、Twitter等的用户数已超过十亿量级），在如此巨大的网络中如何精确并快速地量化用户在整个网络中的影响力，进而找到最有影响力的个体或群体，成为一个极具挑战性的问题。传统的方法在量化用户在网络的影响力时往往需要社交网络的全局结构数据。但由于社交网络巨大，并且在时刻变化着，获得全局的网络结构几乎是不可能的，即使可以获得，其计算复杂度也难以承受。
纪圣塨同学及其合作者，利用统计物理学中的“渗流相变”理论，进行理论推导与算法设计，从而能够精确并快速地量化用户在整个网络中的全局影响力。该方法只需要社交网络的局部（local）信息就能够精确地量化用户在整个网络的全局（global）影响力，其时间复杂度与网络规模无关，即使在超过十亿量级的社交网络中也能够快速地量化用户的影响力。
基于该方法，他们还设计了PBGA算法，来寻找最优的M个初始用户，使得其综合的全局影响力最大。同样地，PBGA算法的时间复杂度也与网络规模无关。在微博、Facebook、QQ等实际社交网络的实验结果显示，如下图所示，PBGA算法的时间复杂度确实不随网络规模增大而增大。基于简单的估算，对于全局的Facebook或Twitter网络，PBGA算法比经典贪心算法（NGA）快将近1010倍（100亿倍）。基于其高效性，PBGA算法在社交网络上的广告投放、营销、流感防控等等与信息传播相关的领域都将具有重要的应用。该论文的发表是西南交通大学云计算与智能技术高校重点实验室在人工智能领域方面的又一重要成果。
近年来，四川省云计算与智能技术高校重点实验室一直致力于云计算、大数据、人工智能等方面的研究与应用，取得了一批重要学术成果，包括在国际一流期刊PNAS, Artificial Intelligence, IEEE Transactions on Pattern Analysis and Machine Intelligence, IEEE Transaction on Knowledge and Data Engineering, IEEE Transactions on Evolutionary Computation, IEEE Transactions on Fuzzy Systems, IEEE Transactions on Image Processing, IEEE Transactions on Information Forensics & Security, IEEE Transactions on Cybernetics, IEEE Transactions on Vehicular Technology, Information Science等发表40余篇学术论文，先后入选ESI热点论文3篇，ESI高被引论文14篇和扩展版ESI高被引论文20篇，出版编著6部，主编出版SCI期刊专辑9部等。而且特别重视人才培养质量，已培养上百名研究生，遍布海内外，就业单位包括国际知名研究机构如微软亚洲研究院，一流高校如四川大学和行业骨干企业如华为、阿里巴巴、腾讯、百度等。培养的学生中曾获得竢实扬华奖章2人，中国人工智能学会优秀博士论文提名奖1次，ACM成都分会优秀博士论文奖4次，IEEE成都分会优秀学生论文奖4次，国际会议优秀论文奖3次和优秀张贴论文奖2次，全国会议优秀论文奖3次，2015年天池大数据“新浪微博互动预测大赛”冠军（奖金20万元），2016年国际人工智能联合会议竞赛（社会影响力分析）亚军，ACM-ICPC亚洲区预选赛金牌，首届“顶嵌杯”全国嵌入式系统C语言编程大赛唯一的特等奖（大赛最高奖）和多次在全国性竞赛中获得第一名的好成绩等。
论文链接：http://www.pnas.org/content/early/2018/07/02/1710547115.short
