Petroleum distribution is an essential component of national infrastructure, directly influencing transportation, industry, and energy security. Network-based methods enable the analysis of structural properties of distribution networks compared with conventional routing approaches, such as point-point or standard vehicle routing problems (VRP). The study highlights the importance of network analysis using graph theory to optimize petroleum distribution systems and determine the optimal locations for establishing new depots by minimizing travel distance. This study focuses on the Gampaha District located in the western province of Sri Lanka, a region with high population density. A total of 66 fuel stations, including one terminal, were modeled as a weighted graph, where nodes represent stations and edges denote routes weighted by shortest-path distances obtained from Google Maps. While this approach reflects the road structure, it does not explicitly account for traffic congestion or road weight limits. Four centrality measures were used to identify structural properties of the network. Degree centrality revealed highly connected hubs, and closeness centrality identified the locations that can be approached within the shortest time. Betweenness centrality measures the frequency with which a particular node or edge is included in the shortest path. Eigenvector centrality determined how central the depot is to the system. To enhance regional efficiency, community structures within the network were detected using spectral clustering techniques. The eigengap heuristic was used to initially determine the optimal number of clusters. Within each cluster, the most suitable node for depot establishment was selected based on normalized centrality rankings, and its stability was measured using sensitivity analysis. The sensitivity analysis showed that the degree centrality was the most stable measurement. Four optimal clusters were identified, and the most influential nodes within each cluster were determined. Accordingly, Welisara, Gampaha, Katunayake, and Ja-Ela are the most suitable cities for establishing new depots. Overall, the findings demonstrate that the analysis is helpful for the strategic planning of petroleum distribution systems.