新闻速递
我院硕士生李寰的论文被算法领域顶会SODA录用
2017.11.13

近日,算法领域最顶级会议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论文,提出了一个新的边中心性度量指标。这一指标利用了图中所有的路径信息,比当前常用的指标具有更好的区分度。论文接着给出了三个几乎线性时间的近似算法,用于计算新指标的节点/边中心性。因此,论文所提出的中心性度量既包含了更多的信息,又能以几乎最优的时间复杂度,快速进行计算。

SODAACM(美国计算机协会)和SIAM(美国工业与应用数学学会)两大国际学术组织联合主办,与STOCFOCS一起被公认为是理论计算机科学的三大顶级学术会议。中国大陆学者每年独立发表的SODA论文比较少。

© 2017 复旦大学计算机科学技术学院 地址:上海市张衡路825号 Tell:+86-21-51355555 Fax:+86-21-51355558 Emall:cs_school@fudan.edu.cn
复旦大学计算机科学技术学院
扫一扫了解学院