Community Detection by L0-penalized Graph Laplacian
报 告 人:: 席瑞斌
报告地点:: 数学与统计学院四楼学术报告厅
报告时间:: 2017年05月06日星期六16:30-17:00

Community detection in network analysis aims at partitioning nodes in a network into K disjoint communities. Most currently available algorithms assume that K is known, but choosing a correct K is generally very difficult for real networks. In this paper, we propose a tightness criterion, a novel model free criterion, and an efficient algorithm to maximize this criterion for community detection. This tightness criterion is closely related with the graph Laplacian with L0 penalty. Our method does not require a known K and can properly detect communities in networks with outliers.The theoretical result guarantees that, under the degree corrected stochastic block model, even for networks with outliers, the maximizer of the tightness criterion can extract communities with small misclassification rates even when the number of communities grows to infinity as the network size grows. Numerical results show that the proposed method work considerably better than other community detection methods. Application to a college football data and a yeast protein-protein data also reveals that the proposed method performs significantly better.



发 布 人:科研助理 发布时间: 2017-05-04