A locally optimal hierarchical divisive heuristic for bipartite modularity maximization

作     者：Costa, Alberto Hansen, Pierre 

作者机构：Ecole Polytech LIX F-91128 Palaiseau France HEC Montreal Gerad Montreal PQ H3T 2A7 Canada 

出 版 物：《OPTIMIZATION LETTERS》 (最优化通信)

年 卷 期：2014年第8卷第3期

页      面：903-917页

核心收录：

学科分类：0810[工学-信息与通信工程] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 08[工学] 070104[理学-应用数学] 081001[工学-通信与信息系统] 0701[理学-数学] 

基　　金：Digiteo 2009-14D Digiteo 2009-55D 

主　　题：Bipartite graphs Clustering Modularity maximization 

摘      要：Given a set of entities, cluster analysis aims at finding subsets, also called clusters or communities or modules, entities of which are homogeneous and well separated. In the last ten years clustering on networks, or graphs, has been a subject of intense study. Edges between pairs of vertices within the same cluster should be relatively dense, while edges between pairs of vertices in different clusters should be relatively sparse. This led Newman to define the modularity of a cluster as the difference between the number of internal edges and the expected number of such edges in a random graph with the same degree distribution. The modularity of a partition of the vertices is the sum of the modularities of its clusters. Modularity has been extended recently to the case of bipartite graphs. In this paper we propose a hierarchical divisive heuristic for approximate modularity maximization in bipartite graphs. The subproblem of bipartitioning a cluster is solved exactly;hence the heuristic is locally optimal. Several formulations of this subproblem are presented and compared. Some are much better than others, and this illustrates the importance of reformulations. Computational experiences on a series of ten test problems from the literature are reported.