Gossip-based Wireless Sensor Networks (GWSN) are complex systems of inherently random nature. Planning and de-signing GWSN requires a fast and adequately accurate mechanism to estimate system performance. As a first contribu-tion, we propose a performance analysis technique that simulates the gossip-based propagation of each single piece of data in isolation. This technique applies to GWSN in which the dissemination of data from a specific sensor does not de-pend on dissemination of data generated by other sensors. We model the dissemination of a piece of data with a Stochas-tic-Variable Graph Model (SVGM). SVGM is a weighted graph abstraction in which the edges represent stochastic varia-bles that model propagation delays between neighboring nodes. Latency and reliability performance properties are ob-tained efficiently through a stochastic shortest path analysis on the SVGM model using Monte Carlo (MC) simulation. The method is accurate and fast, applicable for both partial and complete system analysis. It outperforms traditional discrete-event simulation. As a second contribution, we propose a centrality-based stratification method that combines structural network analysis and MC partial simulation, to further increase efficiency of the system-level analysis while maintaining adequate accuracy. We analyzed the proposed performance evaluation techniques through an extensive set of experi-ments, using a real deployment and simulations at different levels of abstraction.