  The Bak-Sneppen model displaying punctuated equilibria in biological
evolution is studied on random complex networks. By using the rate equation and
the random walk approaches, we obtain the analytic solution of the fitness
threshold $x_c$ to be 1/(<k>_f+1), where <k>_f=<k^2>/<k> (=<k>) in the quenched
(annealed) updating case, where <k^n> is the n-th moment of the degree
distribution. Thus, the threshold is zero (finite) for the degree exponent
\gamma <3 (\gamma > 3) for the quenched case in the thermodynamic limit. The
theoretical value x_c fits well to the numerical simulation data in the
annealed case only. Avalanche size, defined as the duration of successive
mutations below the threshold, exhibits a critical behavior as its distribution
follows a power law, P_a(s) ~ s^{-3/2}.
