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 effciency 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 tradeoff 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 asMean Cluster Size). The methodology was evaluated on a detailed building case study to obtain the decentralized control architectures for different values of wall insulation parameters. The results are found to be in agreement with the physics of the underlying thermal interactions.