Modularity maximization using completely positive programming

详细信息    查看全文

• 作者：Sakineh Yazdanparast ; ^{syazdanp@mtu.edu} ; Timothy C. Havens
• 关键词：Community detection ; Modularity maximization ; Completely positive programming ; Quadratic programming ; Linear programming
• 刊名：Physica A: Statistical Mechanics and its Applications
• 出版年：2017
• 出版时间：1 April 2017
• 年：2017
• 卷：471
• 期：Complete
• 页码：20-32
• 全文大小：833 K
• 卷排序：471

文摘

Community detection is one of the most prominent problems of social network analysis. In this paper, a novel method for Modularity Maximization (MM) for community detection is presented which exploits the Alternating Direction Augmented Lagrangian (ADAL) method for maximizing a generalized form of Newman’s modularity function. We first transform Newman’s modularity function into a quadratic program and then use Completely Positive Programming (CPP) to map the quadratic program to a linear program, which provides the globally optimal maximum modularity partition. In order to solve the proposed CPP problem, a closed form solution using the ADAL merged with a rank minimization approach is proposed. The performance of the proposed method is evaluated on several real-world data sets used for benchmarks community detection. Simulation results shows the proposed technique provides outstanding results in terms of modularity value for crisp partitions.