  We investigate a model of evolving random network, introduced by us
previously {[}{\it Phys. Rev. Lett.} {\bf 83}, 5587 (1999){]} . The model is a
generalization of the Bak-Sneppen model of biological evolution, with the
modification that the underlying network can evolve by adding and removing
sites. The behavior and the averaged properties of the network depend on the
parameter $p$, the probability to establish link to the newly introduced site.
For $p=1$ the system is self-organized critical, with two distinct power-law
regimes with forward-avalanche exponents $\tau=1.98\pm 0.04$ and $\tau^\prime =
1.65\pm 0.05$. The average size of the network diverge as power-law when $p\to
1$. We study various geometrical properties of the network: probability
distribution of sizes and connectivities, size and number of disconnected
clusters and the dependence of mean distance between two sites on the cluster
size. The connection with models of growing networks with preferential
attachment is discussed.
