学院新闻

近日，高瓴人工智能学院师生有2篇论文被CCF-A类会议SIGMOD（2020）录用。2020年国际数据管理大会 （ACM SIGMOD International Conference on Management of Data）将于2020年6月14日-6月19日在美国波特兰召开 。SIGMOD是中国计算机学会（CCF）推荐的A类国际学术会议，是数据库领域最顶级的会议，中国大陆高校历年以第一单位身份发表的论文数量均为个位数。

论文介绍

第一作者：王涵之（博士生）

通讯作者：魏哲巍教授

作      者：王涵之，魏哲巍，袁野，杜小勇，文继荣

论文题目：Exact Single-Source SimRank Computation on Large Graphs

论文概述：SimRank 是一种图节点相似度的度量算法，以其直观的设计思想和高质量的相似度计算结果而被广泛应用于web网络挖掘、社交网络分析、垃圾邮件检测等场景中。然而，SimRank定义式的计算复杂度较高，无法支持超过十万节点的大规模图集，这在很大程度上限制了SimRank的应用范围。本篇论文提出了首个可在千万节点十亿条边的超大规模图集上以高概率精确计算单源SimRank的算法 ExactSim，终结了十余年来SimRank研究领域无法获得大图上单源SimRank精确值(Ground Truth)的局面，为今后SimRank近似算法的性能衡量提供了标杆。

论文介绍

通讯作者：王思博教授（香港中文大学），魏哲巍教授

参与作者：陈明（硕士生）

作      者：郭钦填，王思博，魏哲巍，陈明

论文题目：Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened

论文概述：影响力最大化 (Influence Maximalization)问题的目标在于寻找社交网络中最具影响力的k个节点，以使选出的节点可以尽可能多地影响到网络上的其它节点，这在广告投放、疫情预测等领域都有广泛应用。影响力最大化算法的核心步骤在于随机反向可达集(Reverse Reachable Set)的生成，其生成的效率和反向可达集的大小直接影响整个算法的时间消耗和可扩展性。本篇论文基于独立级联模型（Independent-Cascade model），改进了单个反向可达集的采样效率，并且在保证结果准确度的前提下缩小了反向可达集的大小，从而降低了所有社交影响力最大化算法的时间复杂度，提升了算法的可扩展性。