The problem of partitioning a building into clusters is considered in this paper, with reference to its decentralized thermal control. Optimal control schemes for these systems are often centralized and address both the thermal comfort and energy efficiency requirements. However, due to robustness considerations, a decentralized architecture may be preferred for large scale systems, which is at best sub-optimal. Therefore, the 'degree of decentralization' governs the trade-off between optimality and robustness. This paper proposes a combinatorial optimization based systematic methodology for obtaining an optimal degree of decentralization on the basis of two metrics - one for optimality (defined as Coupling Loss Factor) and one for robustness (defined as Mean Cluster Size). The methodology was evaluated on a building model and results were found to be in agreement with the physics of the underlying thermal interactions.