Understanding how animals interact with their physical and social environment is a major question in ecology, but separating between these factors is often challenging. Observed interaction rates may reflect social behaviour – preferences or avoidance of conspecifics or certain phenotypes. Yet, environmental spatiotemporal heterogeneity also affects individual space use and interaction rates. For instance, clumped and ephemeral resources may force individuals to aggregate independently of sociality. Proximity-based social networks (PBSNs) are becoming increasingly popular for studying social structures thanks to the parallel improvement of biotracking technologies and network randomization methods. While current methods focus on swapping individual identities among network nodes or in the data streams that underlies the network (e.g. individuals movement paths), we still need better tools to distinguish between the contribution of sociality and other factors towards those interactions. We propose a novel method that randomizes path segments among different time stamps within each individual separately (Part I). Temporal randomization of whole path segments (e.g. full days) retains their original spatial structure while decoupling synchronization among individuals. This allows researchers to compare observed dyadic association rates with those expected by chance given explicit space use of the individuals in each dyad. Further, since environmental changes are commonly much slower than the duration of social interactions, we can differentiate between these two factors (Part II). First, an individual's path is divided into successive time windows (e.g. weeks), and days are randomized within each time window. Then, by exploring how the deviations between randomized and observed networks change as a function of time window length, we can refine our null model to account also for temporal changes in the activity areas. We used biased-correlated random walk models to simulate populations of socially indifferent or sociable agents for testing our method for both false-positive and negative errors. Applying the method to a data set of GPS-tracked sleepy lizards (Tiliqua rugosa) demonstrated its ability to reveal the social organization in free-ranging animals while accounting for confounding factors of environmental spatiotemporal heterogeneity. We demonstrate that this method is robust to sampling bias and argue that it is applicable for a wide range of systems and tracking techniques, and can be extended to test for preferential phenotypic assortment within PBSNs.