Improving heuristics for network modularity maximization using an exact algorithm

详细信息    查看全文

• 作者：Sonia Cafieri ; Pierre Hansen ; Leo Liberti
• 关键词：Clustering ; Bipartition ; Network ; Graph ; Community ; Modularity ; Heuristic ; Exact algorithm ; Matheuristic
• 刊名：Discrete Applied Mathematics
• 出版年：30 January, 2014
• 年：2014
• 卷：163
• 期：part_P1
• 页码：65-72
• 全文大小：249 K

文摘

Heuristics are widely applied to modularity maximization models for the identification of communities in complex networks. We present an approach to be applied as a post-processing to heuristic methods in order to improve their performances. Starting from a given partition, we test with an exact algorithm for bipartitioning if it is worthwhile to split some communities or to merge two of them. A combination of merge and split actions is also performed. Computational experiments show that the proposed approach is effective in improving heuristic results.