各位数院研究生同学：

研究生学术午餐会是在学院领导的大力支持下，由研究生会负责组织的系列学术交流活动。午餐会每次邀请

一位同学作为主讲人，面向全院各专业背景的研究生介绍自己科研方向的基本问题、概念和方法，并汇报近

期的研究成果和进展，是研究生展示自我、促进交流的学术平台。研究生会已经举办了三十二期活动，我们将

于2018年9月27日周四举办第三十三期学术午餐会活动，欢迎感兴趣的老师和同学积极报名参加。

 

Bio：刘浩洋，北京大学数学科学学院 2018 级博士研究生。本科毕业于北京大学（2012 级数学科学学院，计算

数学），并留校读研（2016 数学科学学院计算数学硕士），于今年申请硕转博。导师为文再文老师（北京国际

数学中心），主要研究方向为优化与并行计算，侧重于算法的设计和实现。曾获2016-2017 年度，国家奖学金

（硕）及2017-2018 年度，校长奖学金。本次午餐会所报告的论文刚刚获得 2018 中国工业与应用数学学会（CSIAM）

第十六届年会的学生论文奖。

 

Abstract: Consider the community detection problem under either the stochastic block model (SBM)

assumption or the degree-correlated stochastic block model (DCSBM) assumption. The modularity

maximization formulation for the community detection problem is NP-hard in general. To solve this,

we propose a sparse and low-rank completely positive relaxation for the modularity maximization problem,

we then develop an efficient row-by-row (RBR) type block coordinate descent (BCD) algorithm to solve

the relaxation and prove an $\mathcal{O}(1/\sqrt{N})$ convergence rate to a stationary point where $N$ is

the number of iterations. A fast rounding scheme is constructed to retrieve the community structure from a

solution to the above relaxation. Non-asymptotic high probability bounds on the misclassification rate are

established to justify our approach. We further develop an asynchronous parallel RBR algorithm to speed up

the convergence. Extensive numerical experiments on both synthetic and real world networks show that the

proposed approach enjoys advantages in both clustering accuracy and numerical efficiency.  Our numerical

results indicate that the newly proposed method is a quite competitive alternative for the community

detection problem on sparse networks with over 50 million nodes.

 

报名方式：请有意参加的同学于2018年9月26日（周三）中午12点前填写报名问卷，复制问卷链接

https://www.wjx.top/jq/28399206.aspx至浏览器或点击阅读原文进入问卷报名。