Since the seminal work of Watts & Strogatz and others in the late 90s [1], graph-theoretic analyses have been performed on many complex dynamic networks, including brain structures. Most studies have focused on functional connectivity defined between whole brain regions, using imaging techniques such as fMRI, EEG or MEG [2]. Only very few studies have attempted to look at the structure of neural networks on the level of individual neurons [3,4]. To the best of our knowledge, these studies have only considered undirected connectivity networks and have derived connectivity based on estimates on small subsets or even pairs of neurons from the recorded networks. Here, we investigate scale-free and small-world properties of neuronal networks, based on multi-electrode recordings from the awake monkey on a larger data set than in previous approaches. We estimate effective, i.e. causal, interactions by fitting Generalized Linear Models on the neural responses to natural stimulation, incorporating effects from the neurons’ self-history, coupling terms and modulation by the external stimulus. The resulting connectivity matrix is directed and a link between two neurons represents a causal influence from one neuron to the other, given the observation of all other neurons from the population. We use this connectivity matrix to estimate scale-free and small-world properties of the network samples. For this, the quantity proposed by [5] for quantifying small-world-ness is generalized to directed networks. We find that the networks under consideration lack scale-free behavior, but show a small, but significant small-world structure. Finally, we show that the experimental design of multi-electrode recordings typically enforces a particular network structure that can have a considerate impact on how the small-world structure of the network should be evaluated. Since for multi-electrode recordings the sampling of neurons is not uniform across the population (one electrode usually captures signals from a small local population), we expect the wiring probability between neurons of the same local spot to be much higher than the wiring probability between neurons from different electrodes. Thus, random graphs that take the different wiring probabilities into account can serve as a more refined null model than the homogeneous Erdös-Renyi random graphs that are usually proposed as reference models to evaluate small-world properties. Moreover, as the set of recorded neurons in a given experiment always represents only a subpopulation of the overall network, we investigate how the evaluation of small-world structure is affected by this undersampling bias.