In this study, optimal water quality sensor placement is performed based on the sensitivity of flow direction under different water demands for detecting accidental water quality contamination. First, Betweenness Centrality (BC), a network analysis method, is used for determining optimal locations considering a network’s connectivity. Second, sensor locations are optimized for minimizing the contaminant intrusion detection time using the travel time matrix and the Multi-Objective Genetic Algorithm (MOGA). These methods were applied to two water distribution networks. It was found that the BC method generates optimal locations close to the water sources and the water main, whereas the MOGA-based method generates optimal sensor locations far away from the sources. These results support the following conclusions. First, the installation priority of gauges can be determined with a more objective standard using the aforementioned two methods. Second, given specific objectives, the two models can be used as alternative decision-making tools for sensor installation.