The identification of price zones is a critical issue for designing efficient mechanisms in network-constrained electricity markets. It consists of identifying nodes in zones that share similar Locational Marginal Prices (LMPs) and are physically connected by transmission lines. This paper proposes a methodology based on graph theory to identify price zones and the corresponding transmission tie-lines interconnecting them considering the changing pattern of LMPs. A mathematical characterization of network-constrained electricity market based on LMPs is proposed to construct a market-aware graph. Then, a spectral clustering methodology is applied to identify the price zones. The effectiveness of the proposed approach is illustrated on a 118-node test system.