Maximizing Barber’s bipartite modularity is also hard

Modularity introduced by Newman and Girvan (Phys Rev E 69:026113, 2004) is a quality function for community detection in networks. Numerous methods for modularity maximization have been developed so far. In 2007, Barber (Phys Rev E 76:066102, 2007) introduced a variant of modularity called bipartite modularity which is appropriate for bipartite networks. Although maximizing the standard modularity is known to be NP‐hard, the computational complexity of maximizing bipartite modularity has yet to be revealed. In this study, we prove that maximizing bipartite modularity is also NP‐hard. More specifically, we show the NP‐completeness of its decision version by constructing a reduction from a classical partitioning problem.