Variable selection in Bayesian networks is necessary to assure the quality of the learned network structure. Cinicioglu & Shenoy (2012) suggested an approach for variable selection in Bayesian networks where a score, Sj, is developed to assess each variable whether it should be included in the final Bayesian network. However, with this method the variables without parents or children are punished which affects the performance of the learned network. To eliminate that drawback, in this paper we develop a new score, NSj. We measure the performance of this new heuristic in terms of the prediction capacity of the learned network, its lift over marginal and evaluate its success by comparing it with the results obtained by the previously developed Sj score. For the illustration of the developed heuristic and comparison of the results credit score data is used.