Spectral clustering is a modern clustering approach, with many successful applications such as document clustering and image segmentation. However, it is not without challenges such as high computational complexity and parameter tuning. Ever since its introduction, much effort has been spent on making spectral clustering scalable (in memory and speed) to large data sets while there is little work on parameter tuning. In this paper, we address the parameter tuning challenge of spectral clustering (including the landmark-based scalable methods). Specifically, we propose a new criterion for tuning the scale parameter used in a similarity function such as Gaussian and cosine. Experiments demonstrate the effectiveness of the proposed tuning technique.