  Graphs are a powerful mathematical model, and they are used to represent
real-world structures in various fields. In many applications, real-world
structures with high connectivity and robustness are preferable. For enhancing
the connectivity and robustness of graphs, two operations, adding edges and
anchoring nodes, have been extensively studied. However, merging nodes, which
is a realistic operation in many scenarios (e.g., bus station reorganization,
multiple team formation), has been overlooked. In this work, we study the
problem of improving graph cohesiveness by merging nodes. First, we formulate
the problem mathematically using the size of the $k$-truss, for a given $k$, as
the objective. Then, we prove the NP-hardness and non-modularity of the
problem. After that, we develop BATMAN, a fast and effective algorithm for
choosing sets of nodes to be merged, based on our theoretical findings and
empirical observations. Lastly, we demonstrate the superiority of BATMAN over
several baselines, in terms of speed and effectiveness, through extensive
experiments on fourteen real-world graphs.
