近日，算法领域最顶级会议 ACM-SIAM Symposium on Discrete Algorithms (SODA)公布了 2018 年论文录用情况，我院 2016 级硕士生李寰和指导老师章忠志的论文 “Kirchhoff index as a measure of edge centrality in weighted networks: Nearly linear time algorithms” 被接收，这是第一篇以复旦大学为唯一作者单位的 SODA 论文。
这篇 SODA 论文的主题是关于网络（图）中心性度量与算法。中心性在社交网络、生物网络等领域中有着十分重要的应用，设计中心性的度量方法及相关算法是近年来相关领域的研究热点。常见的中心性度量方法往往存在以下缺陷：要么由于度量方法本身所包含的信息量不够，无法很好地区分出节点/边的相对重要性，比如基于最短路径的中心性度量；要么因为度量方法包含的信息量大，需要很高的计算时间复杂度，比如基于电流的边中心性度量。为了克服当前研究的不足，李寰和章忠志的 SODA 论文，提出了一个新的边中心性度量指标。这一指标利用了图中所有的路径信息，比当前常用的指标具有更好的区分度。论文接着给出了三个几乎线性时间的近似算法，用于计算新指标的节点/边中心性。因此，论文所提出的中心性度量既包含了更多的信息，又能以几乎最优的时间复杂度，快速进行计算。
SODA 由 ACM（美国计算机协会）和 SIAM（美国工业与应用数学学会）两大国际学术组织联合主办，与 STOC、FOCS 一起被公认为是理论计算机科学的三大顶级学术会议。中国大陆学者每年独立发表的 SODA 论文比较少。
