The all-terminal reliability is the probability that all nodes in the whole network remain connected, and it is instructive to analyze the operational risk of the whole network. The exact calculation of the all-terminal reliability is an NP-hard problem, and it's not suitable for analyzing the reliability of the large-scale network. This paper presents a method of calculating the allterminal reliability of the large-scale smart grid communication system (SGCS) based on the complex network theory. The network is divided into many communities before calculating the all-terminal reliability, and the all-terminal reliability of communities is calculated instead of the whole network. The use of complex network community structure of the SGCS can effectively reduce the complexity of the topology, and simplify the complexity of the all-terminal reliability's algorithm. Compared with the traditional approximate all-terminal reliability calculation methods, the algorithm has greatly reduced the time complexity and improved the accuracy of result.