Social network analysis is quickly becoming an established framework to study the structure of animal social systems. To explore the social network of a population, observers must capture data on the interactions or associations between individuals. Sampling decisions significantly impact the outcome of data collection, notably the amount of data available from which to construct social networks. However, little is known about how different sampling methods, and more generally the extent of sampling effort, impact the robustness of social network analyses. Here, we generate proximity networks from data obtained via nearly continuous GPS tracking of members of a wild baboon troop (Papio anubis). These data allow us to produce networks based on complete observations of interindividual distances between group members. We then mimic several widely used focal animal sampling and group scanning methods by subsampling the complete data set to simulate observational data comparable to that produced by human observers. We explore how sampling effort, sampling methods, network definitions and levels and types of sampling error affect the correlation between the estimated and complete networks. Our results suggest that for some scenarios, even low levels of sampling effort (5-10 samples/individual) can provide the same information as high sampling effort (>64 samples/individual). However, we find that insufficient data collected across all potentially interacting individuals, certain network definitions (how edge weights and distance thresholds are calculated) and misidentifications of individuals in the network can generate spurious network structure with little or no correlation to the underlying or 'real' social structure. Our results suggest that data collection methods should be designed to maximize the number of potential interactions (edges) recorded for each observation. We discuss the relative trade-offs between maximizing the amount of data collected across as many individuals as possible and the potential for erroneous observations.