香港中文大学Jeffrey Xu Yu教授应邀来访并做学术报告

2019年3月22日,香港中文大学Jeffrey Xu Yu教授应邀来计算机所做了题为“Finding Max Cliques in Massive Graphs”的学术报告。

学术报告现场

Jeffrey Xu Yu教授主要介绍了大图上计算最大团的相关问题和高效算法。首先,针对极大团(Maximal Clique)的枚举问题,Yu教授介绍了基于H*-graph索引的外存(External Memory)算法,该方法采用递归选择子图、计算子图上的所有极大团、最后将子图删除的基本思路,通过利用h-index思想建立索引(H*-graph),保证了算法的低I/O复杂度。其次,对大图上计算最大团(Maximum Clique)问题,针对目前分治限界(Branch & Bound)算法效率的不足,提出了随机最大团(Randomized Maximum Clique,RMC)算法计算精确解。通过同时利用上界和下界进行搜索剪枝和基于界限的采样算法,以及若干启发式的规约策略,算法在若干大规模真实图上取得了显著性能提升。

Jeffrey Xu Yu,香港中文大学系统工程和工程管理系教授、系主任。主要研究方向包括图挖掘和查询、图模式匹配和社交网络分析等。曾任数据库领域顶级期刊TKDE、VLDB Journal等的副主编,现为TODS、WWW Journal等期刊副主编。

 

 

CLOSE

上一篇 下一篇