Toward optimal community detection: From trees to general weighted networks

Many networks including the Internet, social networks, and biological relations are found to be naturally divided into communities of densely connected nodes, known as community structure. Since Newman’s sug-gestion of using modularity as a measure to qualify the goodness of com-munity structures, many efficient methods to maximize modularity have been proposed but without optimality guarantees. In this paper, we study exact and theoretically near-optimal algorithms for maximizing modular-ity. In the first part, we investigate the complexity and approximability of the problem on tree graphs. Somewhat surprisingly, the problem is still NP-complete on trees. We then provide a polynomial time algorithm for uniform-weighted trees, a pseudo-polynomial time algorithm and a PTAS for trees with arbitrary weights. In the second part, we propose sparse metric, a set of linear programming formulations for general graphs. By exploiting the graph connectivity structure, sparse metrics helps to reduce substantially the number of constraints, thus, vastly improve the running time for solving linear programming and integer programming. As a re-sult, networks of thousands of vertices can be solved in minutes while the current largest instance solved with mathematical programming has less than 250 vertices.