Network travel time reliability can be represented by a relationship between network space-mean travel time and the standard deviation of network travel time. The primary objective of this paper is to improve estimation of the network travel time reliability with network partitioning. We partition a heterogeneous large-scale network into homogeneous regions (clusters) with well-defined Network Fundamental Diagrams (NFD) using directional and non-directional partitioning approaches. To estimate the network travel time reliability, a linear relationship is estimated that relates the mean travel time with the standard deviation of travel time per unit of distance at the network level. The impact of different partitioning approaches, as well as the number of clusters, on the network travel time reliability relationship are also explored. To estimate individual vehicle travel times, we use two distinct approaches to allocate vehicle trajectories to different time intervals, namely trajectory and sub-trajectory methods. We apply the proposed framework to a large-scale network of Chicago using a 24-h dynamic traffic simulation. Partitioning and travel time reliability estimation are conducted for both morning and afternoon peak periods to demonstrate the impacts of travel demand pattern variations. The numerical results show that the sub-trajectory method for the network travel time reliability estimation and the directional partitioning with three clusters have the highest performance among other tested methods. The analyses also demonstrate that partitioning a heterogeneous network into homogeneous clusters may improve network travel reliability estimation by estimating an independent relationship for each cluster. Also, comparing morning and afternoon peak periods suggests that the estimated parameter for the linear network travel time reliability relationship is directly related to the coefficient of variation of density as a measure of spatial distribution of congestion across the network.