Fault diagnosis on large-scale and complex networks is a challenging task, as it requires efficient and accurate inference from huge data volumes. Active probing is a cost-efficient tool for fault diagnosis. However almost all existing probing-based techniques face the following problems: 1) performing inaccurately in noisy networks; 2) generating additional traffic to the network; 3) high cost computation. To address these problems, we propose an efficient probe selection algorithm for fault diagnosis based on Bayesian network. Moreover, two approaches which could significantly reduce the computational complexity of the probe selection process are provided. Finally, we implement the new proposed algorithm and a former representative probing-based algorithm (BPEA algorithm) on different settings of networks. The results show that, the new algorithm performs much faster than BPEA does without sacrificing the diagnostic quality, especially in large, noisy and multiple-fault networks. Fault diagnosis on large-scale and complex networks is a challenging task, as it requires efficient and accurate inference from huge data volumes. However almost all existing probing-based techniques face the following problems 2) generating additional traffic to the network; 3) high cost computation. To address these problems, we propose an efficient probe selection algorithm for fault diagnosis based on Bayesian network. Moreover, two approaches which could significantly reduce the computational complexity of the probe selection process are provided. Finally, we implement the new proposed algorithm and a former representative probing-based algorithm (BPEA algorithm) on different settings of networks. The results show that, the new algorithm extends much faster than BPEA does not sacrificing the diagnostic quality, especially in large, noisy and multiple-fault networks.