  Community detection is one of the pivotal tools for discovering the structure
of complex networks. Majority of community detection methods rely on
optimization of certain quality functions characterizing the proposed community
structure. Perhaps, the most commonly used of those quality functions is
modularity. Many heuristics are claimed to be efficient in modularity
maximization, which is usually justified in relative terms through comparison
of their outcomes with those provided by other known algorithms. However as all
the approaches are heuristics, while the complete brute-force is not feasible,
there is no known way to understand if the obtained partitioning is really the
optimal one. In this article we address the modularity maximization problem
from the other side --- finding an upper-bound estimate for the possible
modularity values within a given network, allowing to better evaluate suggested
community structures. Moreover, in some cases when then upper bound estimate
meets the actually obtained modularity score, it provides a proof that the
suggested community structure is indeed the optimal one. We propose an
efficient algorithm for building such an upper-bound estimate and illustrate
its usage on the examples of well-known classical and synthetic networks, being
able to prove the optimality of the existing partitioning for some of the
networks including well-known Zachary's Karate Club.
