  We use the Bethe approximation to calculate the critical temperature for the
transition from a paramagnetic to a glassy phase in spin-glass models on
real-world graphs. Our criterion is based on the marginal stability of the
minimum of the Bethe free energy. For uniform degree random graphs (equivalent
to the Viana-Bray model) our numerical results, obtained by averaging single
problem instances, are in agreement with the known critical temperature
obtained by use of the replica method. Contrary to the replica method, our
method immediately generalizes to arbitrary (random) graphs. We present new
results for Barabasi-Albert scale-free random graphs, for which no analytical
results are known. We investigate the scaling behavior of the critical
temperature with graph size for both the finite and the infinite connectivity
limit. We compare these with the naive Mean Field results. We observe that the
Belief Propagation algorithm converges only in the paramagnetic regime.
