GeoJitter: A Flexible Toolkit for Constraint-Aware Node Jittering in Spatial Networks

GeoJitter: A Flexible Toolkit for Constraint-Aware Node Jittering in Spatial Networks | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article GeoJitter: A Flexible Toolkit for Constraint-Aware Node Jittering in Spatial Networks Nina Fiore, Sebastian Neumann, Geoffrey Moores This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-7491233/v1 This work is licensed under a CC BY 4.0 License Status: Under Review Version 1 posted 18 You are reading this latest preprint version Abstract This paper introduces the Python package GeoJitter, which provides region-aware randomization for spatial location of nodes. This package aids in preventing reidentification of private or proprietary information or spatial display of simulated, predicted, or uncertain information. The library is compatible with Networkx and standard shapefiles and will provide tiling solutions if region data is unknown or unavailable. We compare this technique to Census Enumeration Area, Radius, K-Nearest Neighbor (KNN), Degree Preserving, Stochastic Block Model (SBM), and Markov Chain Monte Carlo (MCMC) randomization. Network randomization privacy GIS anonymization Figures Figure 1 Figure 2 Figure 3 1. INTRODUCTION Network visualization is essential for collaboration, communication of research, education, and more. Frequently, datasets include either overly precise location information that poses privacy risks or incomplete geographic data that hinders meaningful analysis. Existing anonymization techniques often compromise structural network properties or struggle in regions with atypical population density. We introduce an algorithm and companion Python package, GeoJitter, that addresses these challenges by enabling privacy-preserving transformations and uncertainty-aware modeling for spatial networks. The name, GeoJitter, denotes the use of random perturbations (“jittering”) to a node’s geospatial location, preserving the structural integrity of the original network while either obfuscating sensitive coordinates or generating plausible spatial configurations from uncertain inputs. This package is optimized for cases in which nodes must be assigned a precise geospatial location within user parameters. To date there is not a tool that easily generates randomized location data for existing nodes using GIS and shapefiles. Whether researchers possess real-world location data that must be obscured for privacy or proprietary reasons or wish to generate this data to test a model or run simulations, GeoJitter provides the utility of controlled spatial randomization that is often impractical with existing tools. In this paper, we show that GeoJitter provides location shifts within user parameters, allowing the researcher to specify parameters to meet anonymity requirements for their specific network data. We identify two main use cases for the tool: (a) Location data exists but must be obscured (jittered) to protect private or proprietary information; and (b) Location data is imprecise or missing and visualization or simulation would benefit from distributing the nodes across their regions. Base Networkx plotting tools do not maintain spatial relationships between nodes and regions, distorting the physical distances within the network. We compare our algorithm to current best practices in terms of privacy metrics, spatial obfuscation methods and network obfuscation methods. Differential privacy and k -anonymity are current privacy metrics in research and industry. Differential privacy (DP) is big data focused and less applicable to this technique; GeoJitter does not provide DP guarantees, but DP algorithms can be run in conjunction with GeoJitter without issue as desired. k -anonymity will be discussed in the background section; it traditionally uses a radius-based randomization, but GeoJitter’s methods guarantee the researcher k -anonymity within their specifications. For spatial obfuscation we compare GeoJitter to Census Enumeration Area, Radius, and K-Nearest Neighbor (KNN) randomization. For network rewiring methods we consider Degree Preserving, Stochastic Block Model (SBM), and Markov Chain Monte Carlo (MCMC) randomization. The remainder of this paper is structured as follows: first, we provide an overview of relevant research and techniques. We then address the primary algorithms and functions of our package and the major use cases. The discussion section addresses comparison of our techniques with similar available alternatives, technical aspects of the algorithms, limitations and future extensions, with emphasis on ethical considerations relating to privacy and anonymity. 2. BACKGROUND 2.1. K -ANONYMITY AND DIFFERENTIAL PRIVACY Privacy-preserving data publishing is an expansive body of work consisting of domain-specific tools across many fields. Broadly, these tools and studies seek to provide rigorous methods for selectively protecting personal information from datasets while maximally communicating relevant characteristics. A common assumption is that smoothing or coarsening data increases information security, but these techniques do not completely prevent data recovery. Brownstein et al. investigate how publicly released, low-resolution disease incidence maps—intended to protect individual privacy—can still be reverse-engineered to approximate the original patient-level geographic data [ 1 ]. The authors introduce an unsupervised classification technique that infers likely point sources of disease cases by analyzing visual patterns in smoothed maps. Despite the aggregation and smoothing (techniques meant to anonymize data), the method from Brownstein et al. can estimate the original geographic coordinates of cases with surprising accuracy—from a presentation quality map, 99.8% of addresses were within 70 meters and from a publication quality map, all addresses were within 14 meters of the predicted location [ 1 ]. Studying human mobility data collected from phone tower, de Montjoye et al. achieve similar results, finding that 95% of the 1.5 million person dataset could be uniquely identified using only four geolocated points [ 2 ]. We find two main foci in the research for creating robust privacy protection: k -anonymity and DP. In her foundational work on k -anonymity, Sweeney demonstrated that seemingly innocuous attributes to uniquely identify a large fraction of a dataset’s individuals when combined [ 3 ]. If any individual record within the data is indistinguishable from k -1 others in the data set, then the data set is considered k -anonymous. Because location data is a highly effective quasi-identifier, even coarsened information such as home ZIP code or neighborhood can drastically increase reidentification risk. The uniqueness of human movement patterns or residential areas, especially in sparsely populated regions, makes location a potent means of re-identification, particularly when aggregated to other (often publicly available) data. Furthermore, aggregation increases privacy concerns. In a field study, Majeed and Lee note that despite the efforts of many disciplines to protect individual privacy, aggregation of datasets increases the risk of re-identification [ 4 ]. They also note the heightened risk of re-identification due to the cycle whereby more detailed data informs the techniques used to extrapolate private data, particularly identity theft, user profiling, and social engineering. DP is a technique intended to guarantee probabilistic privacy within large datasets by ensuring that the output of computations on a dataset do not materially change if any one record is removed or included, and that risk of harm to the individual is not increased by inclusion in a particular database [ 5 ]. Unlike k -anonymity, which addresses data protection at the dataset level, DP addresses it at the computational output level, ensuring that algorithmic results are consistent across similar databases. As such, DP is not an appropriate benchmark for the functions of the GeoJitter library. However, if deemed necessary for a given use case, DP algorithms could be used in the pipeline to ensure this privacy guarantee for other relevant attributes within the data. 2.2. SPATIAL OBFUSCATION TECHNIQUES There does not yet exist a definitive method to guarantee spatial anonymization, but some methods do exist to mitigate re-identification risk. In their proceedings on spatial anonymization, the United Nations Statistical Commission considers census regions as coarsened location surrogates. Census regions vary in resolution depending on geographic region and data source but are generally considered sufficient to serve as a basis for anonymization [ 6 ]. Their proposed method involves aggregating multiple adjacent districts into larger composite areas and reporting only the coarsened geographic information, thereby increasing the uncertainty surrounding any individual’s precise location. To satisfy the k -anonymity criterion, regions are combined to create a new region that contains at least k individuals. Nevertheless, this method exhibits significant limitations in regions with nonuniform population densities. In sparsely populated rural areas, achieving k -anonymity may require the combination of numerous EAs over a large geographic expanse, producing regions so diffuse that the released data loses much of its value for localized spatial analysis. Radius-based anonymization methods have been proposed to address these challenges, wherein the radius for anonymization is dynamically adjusted according to local population density: smaller radii are employed in densely populated urban centers and larger in sparsely populated regions [ 7 ]. Although such adaptive methods improve the balance between privacy preservation and data utility, they introduce additional complexities. In rural contexts, the radii required to satisfy k -anonymity may extend across tens or hundreds of kilometers, resulting once again in overly coarse spatial representations. Furthermore, the implementation of variable-radius approaches often necessitates access to auxiliary demographic information to appropriately calibrate thresholds. This may itself pose privacy risks if improperly managed. The KNN algorithm can be used for spatial anonymization by designating a random location within a region determined by a node’s k neighborhood, but this is substantially radius-based anonymization with radii determined by k neighborhood. Avraam et al. in their 2021 paper used a similar technique, standardizing continuous variables with z-score transformations to find clusters for each node and its k -1 nearest neighbors, plotting the cluster’s centroid as the anonymized location before reversing the transformation [ 7 ]. Linderman et al. explored KNN connections to generate sparser connections while maintaining a giant component and ~ \(\:n\) log log \(\:n\) edges with comparable connectivity, which is a non-spatial randomization technique that may yield privacy benefits in combination with other methods [ 8 ]. 2.3. NETWORK OBFUSCATION TECHNIQUES Network randomization techniques are often used to mitigate the burden of data collection. Randomization and creation of ensembles enable analysis of various attributes without requiring modeling tens of existing networks. The cost of these randomizations is loss of granularity or changes to original attributes. Degree Preserving Randomization, commonly accomplished by random edge swaps [ 9 ],. provides a degree of anonymity for nodes because they cannot be traced by their relationships with their neighbors. The simple elegance of the algorithm and its ability to maintain degree distribution make it an extremely useful tool for analysis and simulation; however, it does not in isolation provide k -anonymity, differential privacy, or another privacy guarantee. Other common rewiring algorithms work similarly, either discarding much of the original structure or leaving enough to risk reidentification. Stochastic Block Modeling (SBM) randomization provides a statistically sound and extremely generalizable approach to network analysis, nesting different levels of network representation to perform different analyses while preserving the overall community structure [ 10 ]. An SBM model of a given network can produce a randomized graph that shares community structure, including intra- and inter-region edge probabilities, with the original. This prevents loss of community relationship information, scales well to networks of all sizes, and is primarily used for community detection. While the nested models of a hierarchical SBM do provide anonymity to individual nodes, the overall structure is reduced to some level of core-periphery representation, which can be detrimental to analyses that do not relate to community structure. In 1986 Frank and Strauss used Markov Chain Monte Carlo (MCMC) estimation with Markov graphs to simulate networks with dependence between edges and conditional independence properties [ 11 ]. In 2002, Snijders proposed algorithmic improvements applying the concept to the exponential random graph model, increasing applicability of the technique by enabling convergence on graphs with multimodal distributions on sufficient statistics [ 12 ]. This can be either simulation , the generation of a MCMC network with given parameters, or estimation , determining the best fit parameters for observed network data. For our purposes, we can assume that to protect data from reidentification one might first estimate the parameters of the real data and then simulate a representative network. As Snijders notes, MCMC algorithms do not always produce satisfactory results, which limit applicability, but also require transformations from the original to a ‘very different graph’ [ 12 ]. 3. METHODS The minimum user input to GeoJitter is a Networkx graph. Shapefiles for desired regions increase specificity of output but require the network to have an attribute identifying the region name of each node. If no region files are specified, the algorithm creates a configurable tiling of rectangular regions to jitter the spatial locations. 3.1. ALGORITHM The Jitter algorithm accepts the network and applicable shapefiles as well as identification of either the existing geospatial coordinates or the nodes’ region attribute. It creates an empty graph, jitters the node locations using the Point Generator algorithm before appending the edge list from the original network. The Jitter algorithm is expected to run in \(\:O\left(ns\right)\) time for regular region structures, or \(\:O\left(n{s}^{2}\right)\) in the worst case, where \(\:n\) is the number of nodes and \(\:s\) is the maximum number of sides to a region’s polygonal approximation. When node attributes do not include region designation, time is increased by a factor of \(\:r\) , the number of regions (or tiles if applicable). Algorithm 1 Jitter function \(\:JITTER(original\_network,\:regions,\:coord\_access,\:region\_access)\) where \(\:original\_network\) is an Nx graph with attributes for location and/or region name, \(\:regions\) (optional) is a set of shapefiles, \(\:coord\_access\) (optional) identifies and formats node coordinate attribute, and \(\:region\_access\) identifies node region attribute. Initialize \(\:new\_network\) as an empty Nx graph for \(\:node\in\:original\_network.nodes\) do $$\:new\_coord\leftarrow\:POINT\_GENERATOR(coord\_access(node),\:\:region\_access(node\left)\right)$$ $$\:original\_network.\text{a}\text{d}\text{d}\_\text{n}\text{o}\text{d}\text{e}(new\_coord,\:\:\text{a}\text{t}\text{t}\text{r}\text{i}\text{b}\text{u}\text{t}\text{e}\_\text{n}\text{a}\text{m}\text{e}\:=node.data)$$ $$\:new\_network.\text{a}\text{d}\text{d}\_\text{e}\text{d}\text{g}\text{e}\text{s}\_\text{f}\text{r}\text{o}\text{m}(original\_network)$$ return \(\:new\_network\) For both shape file and tile region designation, the Jitter algorithm calls our Point Generator algorithm, which defaults to the Dartboard method to designate the new geospatial position for each node. This method identifies a node’s region and the corresponding bounding box, then selects a point at random within the bounding box. To check for coordinates in region requires solving the Point-In-Polygon problem, for which we use the method outlined by Sutherland et al [ 13 ]. For a tiling solution, this point will always be in the desired region; when using shapefiles the algorithm checks if the solution is inside the region. If true, the solution is returned as the new node location attribute; if not, it reselects. Algorithm 2 Point Generator function \(\:POINT\_GENERATOR(region,\:distribution=\text{u}\text{n}\text{i}\text{f}\text{o}\text{r}\text{m},\:max\_iterations=50)\) where \(\:region\) is the respective shapefile/ tile, \(\:distribution\) is the user-selected distribution for random selection, and \(\:max\_iterations\) identifies when the algorithm switches methods from Dartboard to Triangulate. \(\:box\leftarrow\:{[min}_{x},{max}_{x},\:{min}_{y},{max}_{y}]\) of the region’s shapefile or tile Comment Dartboard method for \(\:i\) \(\:\in\:\{0,max\_iterations\}\) do \(\:\left({p}_{x},{p}_{y}\right)\leftarrow\:\text{r}\text{a}\text{n}\text{d}\text{o}\text{m}\:\text{f}\text{r}\text{o}\text{m}\:box\) according to \(\:distribution\) if \(\:({p}_{x},{p}_{y})\) in \(\:region\) do return \(\:({p}_{x},{p}_{y})\) Comment Triangulate method Initialize \(\:triangulated\leftarrow\:\text{m}\text{e}\text{s}\text{h}\left(region\right)\) using the Triangle library [ 14 ] Initialize tile \(\:weights\leftarrow\:\{{w}_{1},\:{w}_{2},\dots\:,{w}_{n}\}\) using percentage of total region area \(\:chosen\_tri\leftarrow\:\) random choice of \(\:triangulated\) tiles using \(\:weights\) Comment Using approach from [ 15 ] If \(\:distribution=\text{u}\text{n}\text{i}\text{f}\text{o}\text{r}\text{m}\) do \(\:\overrightarrow{a},\:\overrightarrow{b},\:\overrightarrow{c}\leftarrow\:\) vertices of \(\:chosen\_tri\) \(\:{r}_{1},{r}_{2}\leftarrow\:\) independent, random numbers $$\:u=1-\sqrt{{r}_{1}}$$ $$\:v=\sqrt{{r}_{1}}-(1-{r}_{2})$$ $$\:w={r}_{2}\sqrt{{r}_{1}}$$ $$\:\left({p}_{x},{p}_{y}\right)\leftarrow\:u\overrightarrow{a}+v\overrightarrow{b}+w\overrightarrow{c}$$ return \(\:({p}_{x},{p}_{y})\) Else do Raise \(\:distribution\_failure\) return \(\:\left({p}_{x},{p}_{y}\right)\) If the algorithm is set for regions and fails to converge in the specified maximum iterations (by default, 50), it switches to the Triangulation method. Using the Triangle library [ 14 ], the shape file region is transformed into a polygon and subdivided into triangle tiles. Then, a random triangle is selected; using the area formula a random point inside that triangle is selected to be the node’s jittered location. This guarantees an acceptable solution in one iteration but is computationally more intensive than the Dartboard Algorithm and slower by a factor of s , where s is the number of sides in the polygonal representation of the region. This uses equations outlined in Osada [ 15 ] when the distribution is set to uniform. Currently, in the non-uniform case, failure of the Dartboard method raises an error. Application across subcomponent triangles of the region mesh will not result in the appropriate distribution over the region. We hope to address this functionality in future updates. To set up the architecture for tiling, the algorithm intakes user-specified arguments for the m x n desired solution or defaults to a 10 x 10 grid. The bounding box of this grid is formed by the minimum and maximum latitude and longitude, which is then subdivided as specified (see Fig. 1 for an example of a 10 x 10 tiling solution on the generated Boston toy network). Each node is then jittered within its assigned tile. This ensures only one perturbation per node when selecting random points within the rectangular tiles. 4. DISCUSSION 4.1. CUSTOMIZATIONS Regional shapefiles are often available at multiple levels of granularity from as fine as census blocks or neighborhoods to nations or global shapefiles that display continents or coastlines. However, areas with uneven population density will often maintain unevenly sized regional designation areas for ease of administration; in the United States, Alaska and California demonstrate this characteristic. Sparsely populated regions can be over ten times the size of the small regions of dense urban areas. Additionally, shape file regions tend to be predicated on human population density, which may not be germane to the user’s network. Here, the user has a choice. If unsatisfied with the applicable regions, they can use the tiling regions to jitter the network. The input parameters of the function allow specification of a usefully sized grid of tiles for the given situation. The package defaults to uniform joint probability of latitude/longitude selection but allows specification of a joint probability surface within the regions. To an extent, the selection of region shapes influences location probability; the regions are conditional on population, which is reflected in node density and the possible jitter distance. Nodes in highly populated urban areas will tend to have small regions with high population and will have shorter jitter distances, which does reflect the probability for location in dense vs. sparse areas. However, if the user wishes to apply a specific distribution (e.g. a joint normal distribution), they may adjust the probabilities accordingly. 4.2. USE CASES GeoJitter enables the user to adjust its parameters based on the specific requirements of their project. The established spatial or network randomization techniques do not provide the same utility: a flexible location randomization technique that improves network visualizations. The limited scope of the tool also makes it easier to fine-tune results. Common network randomization methods disrupt or mask the significant structure of the original network. While this does support privacy, visualizations of these representations may fail to demonstrate key results from analysis. We anticipate utility to come from protecting information privacy from reidentification and from working with uncertainty within data. In the first scenario, our package enables privacy-preserving transformations that retain the structure of the underlying network while obscuring sensitive location data. In the second, users may only have access to simulated, approximate, or uncertain location data, often in the form of bounded regions or probabilistic estimates, and our package provides tools for constructing and working with spatial graphs in the presence of location uncertainty. We anticipate two use cases for our package: too much location data, and not enough location data. Precise geographic coordinates can compromise the anonymity of study participants; including visualization randomization in the study design reduces privacy risks such as those analyzed by Institutional Review Boards and ethics committees. Even in the absence of explicit identifiers such as names, quasi-identifiers (i.e. height, weight, gender, or ethnicity) can be cross-referenced with external datasets to enable re-identification. These linkage attacks are particularly damaging with the combination of multiple, individually innocuous, datasets – increasingly accessible by publication or scraping [ 16 ]. In scenarios such as disease transmission modeling, military logistics, and search and rescue operations, the exact locations of key nodes are often unknown. Instead, analysts work with zones of probable location, relying on partial or indirect evidence to infer spatial distributions. When considering the dependencies and conditional probabilities incurred within a network, traditional spatial graph analysis can be unreliable or misleading. Our library provides tools to formally incorporate spatial uncertainty, allowing users to define uncertainty regions associated with each node. This enables the network analysis to reflect the imprecise nature of the underlying data without discarding relational structure. In the first use case, the network contains precise location data attributes where clear communication of results does not necessitate, or where there is a compelling need to obscure, the location due to privacy or proprietary concerns. After determining an appropriate set of regions, GeoJitter is used to coarsen the shared information. Figure 3 shows an example of a synthetic toy network generated with only region names and the GeoJitter location output. This example uses Boston neighborhood shapefiles published by the City of Boston [17]. In the second use case, the network contains region identifier attributes without precise location (e.g. ZIP code). If the network is synthetic or uses predicted location, regions are assigned upon creation either randomly or based on known probability distributions, often for simulation. Standard plotting tools will overlay all such nodes in a region directly in the center of that region, creating the appearance of a single node with the connectivity of the entire region’s node, as if coarse-graining the entire region to one representative node. In cases where this is undesirable, GeoJitter can be applied to the network and the geospatial perturbation will clarify the internodal relationships during visualization. In Fig. 3 above, 2 node pairs (2–3 and 7–8) share regions but the Point Generator algorithm provides random spacing according to the set distribution. 4.3. LIMITATIONS Because the original network structure (degree distribution, motifs, communities, spanning trees, shortest paths, etc.) is unchanged, it is difficult to rigorously quantify the changes in a meaningful way beyond a geographical change in edge lengths. Based on aggregational reidentification risk, this continuity of structure means that researchers must be cautious in determining how to protect nonspatial network attributes. 4.4. FUTURE EXTENSIONS To allow more flexibility in networks where spatial distances are unevenly distributed, we would like to add functions that would allow the user to specify an input tuple array indicating the desired \(\:m\) \(\:\times\:\) \(\:n\) tiling for each region. This would enable application of region-specific parameters for appropriately sized tilings across the network. In addition to specifying the number of tiles desired within the network’s bounding box, we would like to allow the user to specify the size of the tiles (e.g. 5km x 5km or similar). We are also developing methods that agglomerate regions based on the number of nodes within regions, thereby adjusting for network node density in addition to the regional population density metrics. Currently, the tiling option only supports rectangular tiles. It is possible to support any regular tiling but current exploration has not indicated utility in adding other tiling options. Though the distribution argument currently supports use for a number of known statistical distributions, we have built in an argument to support extension to allow the user to define a 3-dimensional surface representation of location probability. This would enable users to fully specify any distribution of choice. We plan to incorporate full probability surfaces as user defined distributions in future implementations, providing maximum control over generated networks Declarations 5.1. FUNDING No funds, grants, or other support was received. 5.2. CONFLICTS OF INTEREST The authors have no relevant financial or non-financial interests to disclose. 5.3. ETHICS APPROVAL Not applicable. 5.4. CONSENT TO PARTICIPATE Not applicable. 5.5. CONSENT TO PUBLISH Not applicable. 5.6. DATA AND CODE AVAILABILITY Code and examples are available at https://github.com/SebastianNeumann2003/GeoJitter/. 5.7. AUTHORS’ CONTRIBUTION STATEMENTS Conceptualization: Nina Fiore; Methodology: Nina Fiore, Geoffrey Moores; Formal analysis and investigation: Nina Fiore, Geoffrey Moores; Software: Sebastian Neumann, Geoffrey Moores; Visualization: Sebastian Neumann; Writing – original draft: Nina Fiore; Writing – review and editing: Nina Fiore, Geoffrey Moores, Sebastian Neumann; Validation: Nina Fiore, Geoffrey Moores; Project administration: Nina Fiore; Supervision: Nina Fiore, Geoffrey Moores. 5.8. ACKNOWLEDGMENTS Unstructured finite element meshes were created with Triangle version 1.6 (downloaded from http://www.cs.cmu.edu/~quake/triangle.html). References Brownstein JS, Cassa CA, Kohane IS, Mandl KD (2006) “An unsupervised classification method for inferring original case locations from low-resolution disease maps”. International Journal of Health Geographics , 5(1):56. https://doi.org/10.1186/1476-072X-5-56/. de Montjoye YA, Hidalgo C, Verleysen M, Blondel V (2013) “Unique in the Crowd: The privacy bounds of human mobility”. Sci Rep 3, 1376. https://doi.org/10.1038/srep01376/. Sweeney L (2002) “ k -anonymity: A model for protecting privacy”. International Journal on Uncertainty, Fuzziness and Knowledge-Based Systems , 10(5):557–570. Lee S, Majeed A (2021) “Anonymization techniques for privacy preserving data publishing: A comprehensive survey”. IEEE Access . https://ieeexplore.ieee.org/document/9298747/. Dwork C, Roth A (2014) “The Algorithmic Foundations of Differential Privacy”. Found. Trends Theor. Comput. Sci. 9, 3–4 (Aug 2014), 211–407. https://doi.org/10.1561/0400000042/. United Nations Statistical Commission (2021) “Spatial anonymization”. In Statistical Commission: Fifty-second session . https://unstats.un.org/unsd/statcom/52nd-session/documents/BG-3l-Spatial_Anonymization-E.pdf/. Avraam D, Butters O, Wilson R, Burton T, Nicolaides C, Jones E, et al. (2021) “Privacy preserving data visualizations”. EPJ Data Science , 10, 2. https://doi.org/10.1140/epjds/s13688-020-00257-4/. Jaffe A, Kluger Y, Linderman GC, Mishne G, Steinerberger S (2020) “Randomized near-neighbor graphs, giant components and applications in data science”. J Appl Probab . 2020 Jun;57(2):458-476. doi: https://doi.org/10.1017/jpr.2020.21/. Epub 2020 Jul 16. PMID: 32913373; PMCID: PMC7480951. Maslov S, Sneppen K (2002) “Specificity and Stability in Topology of Protein Networks”. Science . 2002 May 3;296(5569):910-3. doi: https://doi.org/10.1126/science.1065103/. PMID: 11988575. Peixoto, T (2014) “Hierarchical Block Structures and High-Resolution Model Selection in Large Networks”. Phys. Rev. X 4 , 011047 – 24 March, 2014. https://doi.org/10.1103/PhysRevX.4.011047/. Frank O, Strauss D (1986) “Markov graphs”. J. Am. Statist. Ass . 1986;81:832–842. Snijders T (2002) “Markov Chain Monte Carlo Estimation of Exponential Random Graph Models”. Journal of Social Structure . 2002 Jun. Sutherland IE, Sproull RF, Schumacker RA (1974) “A characterization of ten hidden-surface algorithms”. ACM Computing Surveys , 6(1):1–55, March 1974. https://doi.org/10.1145/356625.356626/. Shewchuk, JR. (1996) “Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator”. In: Lin MC, Manocha D. (eds) Applied Computational Geometry Towards Geometric Engineering. WACG 1996. Lecture Notes in Computer Science, vol 1148. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0014497/. Osada R, Funkhouser T, Chazelle B, Dobkin D (2002) "Shape Distributions." ACM Transactions on Graphics 21(4) :807-832, October 2002. Vidanage A, Ranbaduge T, Christen P, Randall S (2020) “A privacy attack on multiple dynamic match-key based privacy-preserving record linkage”. International Journal of Population Data Science , 5(1):1345. https://ijpds.org/article/view/1345/. Boston Maps (2025) “Boston Neighborhood Boundaries.” Public record. https://data.boston.gov/dataset/bpda-neighborhood-boundaries/. Additional Declarations No competing interests reported. Cite Share Download PDF Status: Under Review Version 1 posted Editorial decision: Revision requested 27 Oct, 2025 Reviews received at journal 24 Oct, 2025 Reviews received at journal 22 Oct, 2025 Reviews received at journal 15 Oct, 2025 Reviews received at journal 12 Oct, 2025 Reviewers agreed at journal 11 Oct, 2025 Reviews received at journal 11 Oct, 2025 Reviewers agreed at journal 10 Oct, 2025 Reviewers agreed at journal 09 Oct, 2025 Reviewers agreed at journal 08 Oct, 2025 Reviewers agreed at journal 07 Oct, 2025 Reviewers agreed at journal 07 Oct, 2025 Reviewers agreed at journal 17 Sep, 2025 Reviewers invited by journal 15 Sep, 2025 Editor invited by journal 12 Sep, 2025 Editor assigned by journal 04 Sep, 2025 Submission checks completed at journal 04 Sep, 2025 First submitted to journal 29 Aug, 2025 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-7491233","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":518628836,"identity":"788a5000-66a1-4be1-b226-29a2e2941818","order_by":0,"name":"Nina Fiore","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAABDklEQVRIie3Pu2rDMBSA4SME6SLwVgRu8wYFQSAhEFL6JhEFZ+5SOjoYlKWQNU+SKcMJWntZU9xBWTR1cMZCoHUUeyjI7lqofjBYx/4kBBAK/dVM+QggBt2K0pk5zckMm8jEESoqQjJRkfRXUi2J4vUXH4nmzzsj1TsMyt1xvx7B1Zyoh8/1Sqbn2nsKf5r2hFQWhimFzdIm0NdEvT3aXKax9BIBSYdLpUFghJqhdmTLsIVEtiYUSvLlyN2hjfDkB0FHaNspfGupmLxoNsyOd8FbVpIsvsC8pxpItEiIKe51d3CW0aLAcbf/qjf7D8wvF/F0ZzzERTrAgJ7eWT28UU2/uw6e2XWrCIVCof/UN3Sebii9Q8MPAAAAAElFTkSuQmCC","orcid":"","institution":"United States Military Academy","correspondingAuthor":true,"prefix":"","firstName":"Nina","middleName":"","lastName":"Fiore","suffix":""},{"id":518628837,"identity":"6f892428-2d53-48c3-abd2-5ffef69b3a9a","order_by":1,"name":"Sebastian Neumann","email":"","orcid":"","institution":"United States Military Academy","correspondingAuthor":false,"prefix":"","firstName":"Sebastian","middleName":"","lastName":"Neumann","suffix":""},{"id":518628838,"identity":"3e9838eb-7e9b-43de-b54c-906289369e6c","order_by":2,"name":"Geoffrey Moores","email":"","orcid":"","institution":"United States Military Academy","correspondingAuthor":false,"prefix":"","firstName":"Geoffrey","middleName":"","lastName":"Moores","suffix":""}],"badges":[],"createdAt":"2025-08-29 19:38:11","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-7491233/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-7491233/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":91980841,"identity":"7fcd7304-a08b-4a4c-9c20-6bc26b048230","added_by":"auto","created_at":"2025-09-23 10:56:22","extension":"docx","order_by":1,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":421686,"visible":true,"origin":"","legend":"","description":"","filename":"DiscoverNetworksGeoJitter.docx","url":"https://assets-eu.researchsquare.com/files/rs-7491233/v1/a4ca780be19413a31bbce839.docx"},{"id":91981172,"identity":"17111f8f-7ad8-4a59-bf2c-2485b795c0e4","added_by":"auto","created_at":"2025-09-23 11:04:22","extension":"json","order_by":5,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":4469,"visible":true,"origin":"","legend":"","description":"","filename":"af1609fbb9bb406b9de698022e310d76.json","url":"https://assets-eu.researchsquare.com/files/rs-7491233/v1/5b2005f65aa5c9b1750930f3.json"},{"id":91980836,"identity":"3ae2d889-c374-4523-b672-36377ef6f7e5","added_by":"auto","created_at":"2025-09-23 10:56:22","extension":"xml","order_by":6,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":67568,"visible":true,"origin":"","legend":"","description":"","filename":"af1609fbb9bb406b9de698022e310d761enriched.xml","url":"https://assets-eu.researchsquare.com/files/rs-7491233/v1/aafb9310f99489c6da89d716.xml"},{"id":91982215,"identity":"087349ae-a891-463b-868d-b2ccc7b3d222","added_by":"auto","created_at":"2025-09-23 11:12:22","extension":"eps","order_by":7,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":11679,"visible":true,"origin":"","legend":"","description":"","filename":"Fig1.eps","url":"https://assets-eu.researchsquare.com/files/rs-7491233/v1/97ab46d18df63d263c7c08af.eps"},{"id":91980851,"identity":"3dfe0e7d-8a7c-45c1-b830-98f98ad6e327","added_by":"auto","created_at":"2025-09-23 10:56:22","extension":"eps","order_by":8,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":22187439,"visible":true,"origin":"","legend":"","description":"","filename":"Fig2.eps","url":"https://assets-eu.researchsquare.com/files/rs-7491233/v1/6be3d01472436b7e10e0fb8c.eps"},{"id":91980840,"identity":"562bf026-bfd9-48b2-b7ce-575229e34fb5","added_by":"auto","created_at":"2025-09-23 10:56:22","extension":"eps","order_by":9,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":45012,"visible":true,"origin":"","legend":"","description":"","filename":"Fig3a.eps","url":"https://assets-eu.researchsquare.com/files/rs-7491233/v1/03355cea16bdb207a52fc1ba.eps"},{"id":91982216,"identity":"819718d8-397c-48f1-a4bb-1643ffee8e1d","added_by":"auto","created_at":"2025-09-23 11:12:22","extension":"eps","order_by":10,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":801608,"visible":true,"origin":"","legend":"","description":"","filename":"Fig3b.eps","url":"https://assets-eu.researchsquare.com/files/rs-7491233/v1/0bd1c23ac5f252fabaad6459.eps"},{"id":91982549,"identity":"b6588920-3bc5-48c1-a2bc-2eba41491a14","added_by":"auto","created_at":"2025-09-23 11:20:22","extension":"png","order_by":11,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":55177,"visible":true,"origin":"","legend":"","description":"","filename":"floatimage1.png","url":"https://assets-eu.researchsquare.com/files/rs-7491233/v1/8102e65306f24918dd067ef6.png"},{"id":91981174,"identity":"fcd15a56-1e58-458b-aa69-3ff7f58539d4","added_by":"auto","created_at":"2025-09-23 11:04:22","extension":"png","order_by":12,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":125976,"visible":true,"origin":"","legend":"","description":"","filename":"floatimage2.png","url":"https://assets-eu.researchsquare.com/files/rs-7491233/v1/22d4476d7b75f0fca490da63.png"},{"id":91981177,"identity":"287f2a2f-2df2-45c9-a449-f21aff27ca19","added_by":"auto","created_at":"2025-09-23 11:04:22","extension":"jpeg","order_by":13,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":415482,"visible":true,"origin":"","legend":"","description":"","filename":"floatimage3.jpeg","url":"https://assets-eu.researchsquare.com/files/rs-7491233/v1/9fa057db95a58ab6445b15bd.jpeg"},{"id":91980844,"identity":"7cf29741-3c96-46b2-ab13-7ea2a1a3ff6c","added_by":"auto","created_at":"2025-09-23 10:56:22","extension":"png","order_by":14,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":17790,"visible":true,"origin":"","legend":"","description":"","filename":"Onlinefloatimage1.png","url":"https://assets-eu.researchsquare.com/files/rs-7491233/v1/53aa7e48582fd44c8c44311e.png"},{"id":91980842,"identity":"1a9ad4c6-06d7-4f2b-942b-82dc19da0bb2","added_by":"auto","created_at":"2025-09-23 10:56:22","extension":"png","order_by":15,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":24899,"visible":true,"origin":"","legend":"","description":"","filename":"Onlinefloatimage2.png","url":"https://assets-eu.researchsquare.com/files/rs-7491233/v1/1c4e5bbc0541b21cc9fa1067.png"},{"id":91981178,"identity":"2f8b317f-0f60-4a66-9e5e-c1d6df611329","added_by":"auto","created_at":"2025-09-23 11:04:22","extension":"png","order_by":16,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":97855,"visible":true,"origin":"","legend":"","description":"","filename":"Onlinefloatimage3.png","url":"https://assets-eu.researchsquare.com/files/rs-7491233/v1/42f7070385da2a15d730b0c8.png"},{"id":91980846,"identity":"99080e8a-8615-42b1-acee-507b73ac3aaa","added_by":"auto","created_at":"2025-09-23 10:56:22","extension":"xml","order_by":17,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":65782,"visible":true,"origin":"","legend":"","description":"","filename":"af1609fbb9bb406b9de698022e310d761structuring.xml","url":"https://assets-eu.researchsquare.com/files/rs-7491233/v1/0ae9b6a158b1ab0320063e8a.xml"},{"id":91980849,"identity":"c51eab03-dbbe-4c88-8de8-0ed18cc6f235","added_by":"auto","created_at":"2025-09-23 10:56:22","extension":"html","order_by":18,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":79435,"visible":true,"origin":"","legend":"","description":"","filename":"earlyproof.html","url":"https://assets-eu.researchsquare.com/files/rs-7491233/v1/507bc255bff37c6a04657c68.html"},{"id":91980834,"identity":"6b2f3b09-e03d-4ec4-a54a-5e3a5440e0ac","added_by":"auto","created_at":"2025-09-23 10:56:21","extension":"png","order_by":1,"title":"Figure 1","display":"","copyAsset":false,"role":"figure","size":166500,"visible":true,"origin":"","legend":"\u003cp\u003e(a) the creation of a bounding box (Line 1 in Point Generator Algorithm) around a toy network (b) the subdivision of a 10 x 10 tiling grid within the network bounding box\u003c/p\u003e","description":"","filename":"1.png","url":"https://assets-eu.researchsquare.com/files/rs-7491233/v1/950106155bcb054386ba3e2d.png"},{"id":91981171,"identity":"a2d5c218-7a69-40f1-aa4f-c404936b64e2","added_by":"auto","created_at":"2025-09-23 11:04:22","extension":"png","order_by":2,"title":"Figure 2","display":"","copyAsset":false,"role":"figure","size":338176,"visible":true,"origin":"","legend":"\u003cp\u003eThe region of Roxbury, Massachusetts (USA) with (a) uniform, (b) multivariate normal, and (c) power law distributions (upper row) generating 500 sample node locations each (lower row)\u003c/p\u003e","description":"","filename":"2.png","url":"https://assets-eu.researchsquare.com/files/rs-7491233/v1/a53a244bfeceaf72b6129252.png"},{"id":91980838,"identity":"dbadb130-e218-4098-ba43-bf5515aa206c","added_by":"auto","created_at":"2025-09-23 10:56:22","extension":"png","order_by":3,"title":"Figure 3","display":"","copyAsset":false,"role":"figure","size":204488,"visible":true,"origin":"","legend":"\u003cp\u003eGeneration code and geographic plot of synthetic toy network created using only region names and the GeoJitter output\u003c/p\u003e","description":"","filename":"3.png","url":"https://assets-eu.researchsquare.com/files/rs-7491233/v1/9f23df5446cfe6adbf5b0872.png"},{"id":91983240,"identity":"0dde598c-35ee-426b-9dd9-a5ff5a6b05e9","added_by":"auto","created_at":"2025-09-23 11:28:23","extension":"pdf","order_by":0,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":1192793,"visible":true,"origin":"","legend":"","description":"","filename":"manuscript.pdf","url":"https://assets-eu.researchsquare.com/files/rs-7491233/v1/15df5346-c1f6-4c8e-a79b-a19ee328907d.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"GeoJitter: A Flexible Toolkit for Constraint-Aware Node Jittering in Spatial Networks","fulltext":[{"header":"1. INTRODUCTION","content":"\u003cp\u003eNetwork visualization is essential for collaboration, communication of research, education, and more. Frequently, datasets include either overly precise location information that poses privacy risks or incomplete geographic data that hinders meaningful analysis. Existing anonymization techniques often compromise structural network properties or struggle in regions with atypical population density. We introduce an algorithm and companion Python package, GeoJitter, that addresses these challenges by enabling privacy-preserving transformations and uncertainty-aware modeling for spatial networks. The name, GeoJitter, denotes the use of random perturbations (\u0026ldquo;jittering\u0026rdquo;) to a node\u0026rsquo;s geospatial location, preserving the structural integrity of the original network while either obfuscating sensitive coordinates or generating plausible spatial configurations from uncertain inputs. \u003c/p\u003e\n\u003cp\u003eThis package is optimized for cases in which nodes must be assigned a precise geospatial location within user parameters. To date there is not a tool that easily generates randomized location data for existing nodes using GIS and shapefiles. Whether researchers possess real-world location data that must be obscured for privacy or proprietary reasons or wish to generate this data to test a model or run simulations, GeoJitter provides the utility of controlled spatial randomization that is often impractical with existing tools. \u003c/p\u003e\n\u003cp\u003eIn this paper, we show that GeoJitter provides location shifts within user parameters, allowing the researcher to specify parameters to meet anonymity requirements for their specific network data. We identify two main use cases for the tool: (a) Location data exists but must be obscured (jittered) to protect private or proprietary information; and (b) Location data is imprecise or missing and visualization or simulation would benefit from distributing the nodes across their regions. Base Networkx plotting tools do not maintain spatial relationships between nodes and regions, distorting the physical distances within the network.\u003c/p\u003e\n\u003cp\u003eWe compare our algorithm to current best practices in terms of privacy metrics, spatial obfuscation methods and network obfuscation methods. Differential privacy and \u003cem\u003ek\u003c/em\u003e-anonymity are current privacy metrics in research and industry. Differential privacy (DP) is big data focused and less applicable to this technique; GeoJitter does not provide DP guarantees, but DP algorithms can be run in conjunction with GeoJitter without issue as desired. \u003cem\u003ek\u003c/em\u003e-anonymity will be discussed in the background section; it traditionally uses a radius-based randomization, but GeoJitter\u0026rsquo;s methods guarantee the researcher \u003cem\u003ek\u003c/em\u003e-anonymity within their specifications. For spatial obfuscation we compare GeoJitter to Census Enumeration Area, Radius, and K-Nearest Neighbor (KNN) randomization. For network rewiring methods we consider Degree Preserving, Stochastic Block Model (SBM), and Markov Chain Monte Carlo (MCMC) randomization.\u003c/p\u003e\n\u003cp\u003eThe remainder of this paper is structured as follows: first, we provide an overview of relevant research and techniques. We then address the primary algorithms and functions of our package and the major use cases. The discussion section addresses comparison of our techniques with similar available alternatives, technical aspects of the algorithms, limitations and future extensions, with emphasis on ethical considerations relating to privacy and anonymity.\u003c/p\u003e"},{"header":"2. BACKGROUND","content":"\u003cdiv id=\"Sec2\" class=\"Section2\"\u003e\u003ch2\u003e2.1. \u003cem\u003eK\u003c/em\u003e-ANONYMITY AND DIFFERENTIAL PRIVACY\u003c/h2\u003e\u003cp\u003ePrivacy-preserving data publishing is an expansive body of work consisting of domain-specific tools across many fields. Broadly, these tools and studies seek to provide rigorous methods for selectively protecting personal information from datasets while maximally communicating relevant characteristics. A common assumption is that smoothing or coarsening data increases information security, but these techniques do not completely prevent data recovery. Brownstein et al. investigate how publicly released, low-resolution disease incidence maps\u0026mdash;intended to protect individual privacy\u0026mdash;can still be reverse-engineered to approximate the original patient-level geographic data [\u003cspan citationid=\"CR1\" class=\"CitationRef\"\u003e1\u003c/span\u003e]. The authors introduce an unsupervised classification technique that infers likely point sources of disease cases by analyzing visual patterns in smoothed maps. Despite the aggregation and smoothing (techniques meant to anonymize data), the method from Brownstein et al. can estimate the original geographic coordinates of cases with surprising accuracy\u0026mdash;from a presentation quality map, 99.8% of addresses were within 70 meters and from a publication quality map, all addresses were within 14 meters of the predicted location [\u003cspan citationid=\"CR1\" class=\"CitationRef\"\u003e1\u003c/span\u003e]. Studying human mobility data collected from phone tower, de Montjoye et al. achieve similar results, finding that 95% of the 1.5\u0026nbsp;million person dataset could be uniquely identified using only four geolocated points [\u003cspan citationid=\"CR2\" class=\"CitationRef\"\u003e2\u003c/span\u003e]. We find two main foci in the research for creating robust privacy protection: \u003cem\u003ek\u003c/em\u003e-anonymity and DP.\u003c/p\u003e\u003cp\u003eIn her foundational work on \u003cem\u003ek\u003c/em\u003e-anonymity, Sweeney demonstrated that seemingly innocuous attributes to uniquely identify a large fraction of a dataset\u0026rsquo;s individuals when combined [\u003cspan citationid=\"CR3\" class=\"CitationRef\"\u003e3\u003c/span\u003e]. If any individual record within the data is indistinguishable from \u003cem\u003ek\u003c/em\u003e-1 others in the data set, then the data set is considered \u003cem\u003ek\u003c/em\u003e-anonymous. Because location data is a highly effective quasi-identifier, even coarsened information such as home ZIP code or neighborhood can drastically increase reidentification risk. The uniqueness of human movement patterns or residential areas, especially in sparsely populated regions, makes location a potent means of re-identification, particularly when aggregated to other (often publicly available) data.\u003c/p\u003e\u003cp\u003eFurthermore, aggregation increases privacy concerns. In a field study, Majeed and Lee note that despite the efforts of many disciplines to protect individual privacy, aggregation of datasets increases the risk of re-identification [\u003cspan citationid=\"CR4\" class=\"CitationRef\"\u003e4\u003c/span\u003e]. They also note the heightened risk of re-identification due to the cycle whereby more detailed data informs the techniques used to extrapolate private data, particularly identity theft, user profiling, and social engineering.\u003c/p\u003e\u003cp\u003eDP is a technique intended to guarantee probabilistic privacy within large datasets by ensuring that the output of computations on a dataset do not materially change if any one record is removed or included, and that risk of harm to the individual is not increased by inclusion in a particular database [\u003cspan citationid=\"CR5\" class=\"CitationRef\"\u003e5\u003c/span\u003e]. Unlike \u003cem\u003ek\u003c/em\u003e-anonymity, which addresses data protection at the dataset level, DP addresses it at the computational output level, ensuring that algorithmic results are consistent across similar databases. As such, DP is not an appropriate benchmark for the functions of the GeoJitter library. However, if deemed necessary for a given use case, DP algorithms could be used in the pipeline to ensure this privacy guarantee for other relevant attributes within the data.\u003c/p\u003e\u003c/div\u003e\u003cdiv id=\"Sec3\" class=\"Section2\"\u003e\u003ch2\u003e2.2. SPATIAL OBFUSCATION TECHNIQUES\u003c/h2\u003e\u003cp\u003eThere does not yet exist a definitive method to guarantee spatial anonymization, but some methods do exist to mitigate re-identification risk. In their proceedings on spatial anonymization, the United Nations Statistical Commission considers census regions as coarsened location surrogates. Census regions vary in resolution depending on geographic region and data source but are generally considered sufficient to serve as a basis for anonymization [\u003cspan citationid=\"CR6\" class=\"CitationRef\"\u003e6\u003c/span\u003e]. Their proposed method involves aggregating multiple adjacent districts into larger composite areas and reporting only the coarsened geographic information, thereby increasing the uncertainty surrounding any individual\u0026rsquo;s precise location. To satisfy the \u003cem\u003ek\u003c/em\u003e-anonymity criterion, regions are combined to create a new region that contains at least \u003cem\u003ek\u003c/em\u003e individuals.\u003c/p\u003e\u003cp\u003eNevertheless, this method exhibits significant limitations in regions with nonuniform population densities. In sparsely populated rural areas, achieving \u003cem\u003ek\u003c/em\u003e-anonymity may require the combination of numerous EAs over a large geographic expanse, producing regions so diffuse that the released data loses much of its value for localized spatial analysis.\u003c/p\u003e\u003cp\u003eRadius-based anonymization methods have been proposed to address these challenges, wherein the radius for anonymization is dynamically adjusted according to local population density: smaller radii are employed in densely populated urban centers and larger in sparsely populated regions [\u003cspan citationid=\"CR7\" class=\"CitationRef\"\u003e7\u003c/span\u003e]. Although such adaptive methods improve the balance between privacy preservation and data utility, they introduce additional complexities. In rural contexts, the radii required to satisfy \u003cem\u003ek\u003c/em\u003e-anonymity may extend across tens or hundreds of kilometers, resulting once again in overly coarse spatial representations. Furthermore, the implementation of variable-radius approaches often necessitates access to auxiliary demographic information to appropriately calibrate thresholds. This may itself pose privacy risks if improperly managed.\u003c/p\u003e\u003cp\u003eThe KNN algorithm can be used for spatial anonymization by designating a random location within a region determined by a node\u0026rsquo;s \u003cem\u003ek\u003c/em\u003e neighborhood, but this is substantially radius-based anonymization with radii determined by \u003cem\u003ek\u003c/em\u003e neighborhood. Avraam et al. in their 2021 paper used a similar technique, standardizing continuous variables with z-score transformations to find clusters for each node and its \u003cem\u003ek\u003c/em\u003e-1 nearest neighbors, plotting the cluster\u0026rsquo;s centroid as the anonymized location before reversing the transformation [\u003cspan citationid=\"CR7\" class=\"CitationRef\"\u003e7\u003c/span\u003e]. Linderman et al. explored KNN connections to generate sparser connections while maintaining a giant component and ~ \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:n\\)\u003c/span\u003e\u003c/span\u003e log log \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:n\\)\u003c/span\u003e\u003c/span\u003e edges with comparable connectivity, which is a non-spatial randomization technique that may yield privacy benefits in combination with other methods [\u003cspan citationid=\"CR8\" class=\"CitationRef\"\u003e8\u003c/span\u003e].\u003c/p\u003e\u003c/div\u003e\u003cdiv id=\"Sec4\" class=\"Section2\"\u003e\u003ch2\u003e2.3. NETWORK OBFUSCATION TECHNIQUES\u003c/h2\u003e\u003cp\u003eNetwork randomization techniques are often used to mitigate the burden of data collection. Randomization and creation of ensembles enable analysis of various attributes without requiring modeling tens of existing networks. The cost of these randomizations is loss of granularity or changes to original attributes.\u003c/p\u003e\u003cp\u003eDegree Preserving Randomization, commonly accomplished by random edge swaps [\u003cspan citationid=\"CR9\" class=\"CitationRef\"\u003e9\u003c/span\u003e],. provides a degree of anonymity for nodes because they cannot be traced by their relationships with their neighbors. The simple elegance of the algorithm and its ability to maintain degree distribution make it an extremely useful tool for analysis and simulation; however, it does not in isolation provide \u003cem\u003ek\u003c/em\u003e-anonymity, differential privacy, or another privacy guarantee. Other common rewiring algorithms work similarly, either discarding much of the original structure or leaving enough to risk reidentification.\u003c/p\u003e\u003cp\u003eStochastic Block Modeling (SBM) randomization provides a statistically sound and extremely generalizable approach to network analysis, nesting different levels of network representation to perform different analyses while preserving the overall community structure [\u003cspan citationid=\"CR10\" class=\"CitationRef\"\u003e10\u003c/span\u003e]. An SBM model of a given network can produce a randomized graph that shares community structure, including intra- and inter-region edge probabilities, with the original. This prevents loss of community relationship information, scales well to networks of all sizes, and is primarily used for community detection. While the nested models of a hierarchical SBM do provide anonymity to individual nodes, the overall structure is reduced to some level of core-periphery representation, which can be detrimental to analyses that do not relate to community structure.\u003c/p\u003e\u003cp\u003eIn 1986 Frank and Strauss used Markov Chain Monte Carlo (MCMC) estimation with Markov graphs to simulate networks with dependence between edges and conditional independence properties [\u003cspan citationid=\"CR11\" class=\"CitationRef\"\u003e11\u003c/span\u003e]. In 2002, Snijders proposed algorithmic improvements applying the concept to the exponential random graph model, increasing applicability of the technique by enabling convergence on graphs with multimodal distributions on sufficient statistics [\u003cspan citationid=\"CR12\" class=\"CitationRef\"\u003e12\u003c/span\u003e]. This can be either \u003cem\u003esimulation\u003c/em\u003e, the generation of a MCMC network with given parameters, or \u003cem\u003eestimation\u003c/em\u003e, determining the best fit parameters for observed network data. For our purposes, we can assume that to protect data from reidentification one might first estimate the parameters of the real data and then simulate a representative network. As Snijders notes, MCMC algorithms do not always produce satisfactory results, which limit applicability, but also require transformations from the original to a \u0026lsquo;very different graph\u0026rsquo; [\u003cspan citationid=\"CR12\" class=\"CitationRef\"\u003e12\u003c/span\u003e].\u003c/p\u003e\u003c/div\u003e"},{"header":"3. METHODS","content":"\u003cp\u003eThe minimum user input to GeoJitter is a Networkx graph. Shapefiles for desired regions increase specificity of output but require the network to have an attribute identifying the region name of each node. If no region files are specified, the algorithm creates a configurable tiling of rectangular regions to jitter the spatial locations.\u003c/p\u003e\u003cdiv id=\"Sec6\" class=\"Section2\"\u003e\u003ch2\u003e3.1. ALGORITHM\u003c/h2\u003e\u003cp\u003eThe Jitter algorithm accepts the network and applicable shapefiles as well as identification of either the existing geospatial coordinates or the nodes\u0026rsquo; region attribute. It creates an empty graph, jitters the node locations using the Point Generator algorithm before appending the edge list from the original network. The Jitter algorithm is expected to run in \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:O\\left(ns\\right)\\)\u003c/span\u003e\u003c/span\u003e time for regular region structures, or \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:O\\left(n{s}^{2}\\right)\\)\u003c/span\u003e\u003c/span\u003e in the worst case, where \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:n\\)\u003c/span\u003e\u003c/span\u003e is the number of nodes and \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:s\\)\u003c/span\u003e\u003c/span\u003e is the maximum number of sides to a region\u0026rsquo;s polygonal approximation. When node attributes do not include region designation, time is increased by a factor of \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:r\\)\u003c/span\u003e\u003c/span\u003e, the number of regions (or tiles if applicable).\u003c/p\u003e\u003cp\u003e\u003cstrong\u003eAlgorithm 1\u003c/strong\u003e\u003cp\u003eJitter\u003c/p\u003e\u003c/p\u003e\u003cp\u003e\u003cb\u003efunction\u003c/b\u003e \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:JITTER(original\\_network,\\:regions,\\:coord\\_access,\\:region\\_access)\\)\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e\u003cp\u003ewhere \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:original\\_network\\)\u003c/span\u003e\u003c/span\u003e is an Nx graph with attributes for location and/or region name, \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:regions\\)\u003c/span\u003e\u003c/span\u003e (optional) is a set of shapefiles, \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:coord\\_access\\)\u003c/span\u003e\u003c/span\u003e (optional) identifies and formats node coordinate attribute, and \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:region\\_access\\)\u003c/span\u003e\u003c/span\u003e identifies node region attribute.\u003c/p\u003e\u003cp\u003eInitialize \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:new\\_network\\)\u003c/span\u003e\u003c/span\u003e as an empty Nx graph\u003c/p\u003e\u003cp\u003e\u003cb\u003efor\u003c/b\u003e \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:node\\in\\:original\\_network.nodes\\)\u003c/span\u003e\u003c/span\u003e \u003cb\u003edo\u003c/b\u003e\u003cdiv id=\"Equa\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equa\" name=\"EquationSource\"\u003e\n$$\\:new\\_coord\\leftarrow\\:POINT\\_GENERATOR(coord\\_access(node),\\:\\:region\\_access(node\\left)\\right)$$\u003c/div\u003e\u003c/div\u003e\u003cdiv id=\"Equb\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equb\" name=\"EquationSource\"\u003e\n$$\\:original\\_network.\\text{a}\\text{d}\\text{d}\\_\\text{n}\\text{o}\\text{d}\\text{e}(new\\_coord,\\:\\:\\text{a}\\text{t}\\text{t}\\text{r}\\text{i}\\text{b}\\text{u}\\text{t}\\text{e}\\_\\text{n}\\text{a}\\text{m}\\text{e}\\:=node.data)$$\u003c/div\u003e\u003c/div\u003e\u003cdiv id=\"Equc\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equc\" name=\"EquationSource\"\u003e\n$$\\:new\\_network.\\text{a}\\text{d}\\text{d}\\_\\text{e}\\text{d}\\text{g}\\text{e}\\text{s}\\_\\text{f}\\text{r}\\text{o}\\text{m}(original\\_network)$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e\u003cp\u003e\u003cb\u003ereturn\u003c/b\u003e \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:new\\_network\\)\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e\u003cp\u003eFor both shape file and tile region designation, the Jitter algorithm calls our Point Generator algorithm, which defaults to the Dartboard method to designate the new geospatial position for each node. This method identifies a node\u0026rsquo;s region and the corresponding bounding box, then selects a point at random within the bounding box. To check for coordinates in region requires solving the Point-In-Polygon problem, for which we use the method outlined by Sutherland et al [\u003cspan citationid=\"CR13\" class=\"CitationRef\"\u003e13\u003c/span\u003e]. For a tiling solution, this point will always be in the desired region; when using shapefiles the algorithm checks if the solution is inside the region. If true, the solution is returned as the new node location attribute; if not, it reselects.\u003c/p\u003e\u003cp\u003e\u003cstrong\u003eAlgorithm 2\u003c/strong\u003e\u003cp\u003ePoint Generator\u003c/p\u003e\u003c/p\u003e\u003cp\u003e\u003cb\u003efunction\u003c/b\u003e \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:POINT\\_GENERATOR(region,\\:distribution=\\text{u}\\text{n}\\text{i}\\text{f}\\text{o}\\text{r}\\text{m},\\:max\\_iterations=50)\\)\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e\u003cp\u003ewhere \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:region\\)\u003c/span\u003e\u003c/span\u003e is the respective shapefile/ tile, \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:distribution\\)\u003c/span\u003e\u003c/span\u003e is the user-selected distribution for random selection, and \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:max\\_iterations\\)\u003c/span\u003e\u003c/span\u003e identifies when the algorithm switches methods from Dartboard to Triangulate.\u003c/p\u003e\u003cp\u003e\u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:box\\leftarrow\\:{[min}_{x},{max}_{x},\\:{min}_{y},{max}_{y}]\\)\u003c/span\u003e\u003c/span\u003e of the region\u0026rsquo;s shapefile or tile\u003c/p\u003e\u003cp\u003e\u003cstrong\u003eComment\u003c/strong\u003e\u003cp\u003eDartboard method\u003c/p\u003e\u003c/p\u003e\u003cp\u003e\u003cb\u003efor\u003c/b\u003e \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:i\\)\u003c/span\u003e\u003c/span\u003e \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\in\\:\\{0,max\\_iterations\\}\\)\u003c/span\u003e\u003c/span\u003e \u003cb\u003edo\u003c/b\u003e\u003c/p\u003e\u003cp\u003e\u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\left({p}_{x},{p}_{y}\\right)\\leftarrow\\:\\text{r}\\text{a}\\text{n}\\text{d}\\text{o}\\text{m}\\:\\text{f}\\text{r}\\text{o}\\text{m}\\:box\\)\u003c/span\u003e\u003c/span\u003e according to \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:distribution\\)\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e\u003cp\u003e\u003cb\u003eif\u003c/b\u003e \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:({p}_{x},{p}_{y})\\)\u003c/span\u003e\u003c/span\u003e in \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:region\\)\u003c/span\u003e\u003c/span\u003e \u003cb\u003edo\u003c/b\u003e\u003c/p\u003e\u003cp\u003e\u003cb\u003ereturn\u003c/b\u003e \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:({p}_{x},{p}_{y})\\)\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e\u003cp\u003e\u003cstrong\u003eComment\u003c/strong\u003e\u003cp\u003eTriangulate method\u003c/p\u003e\u003c/p\u003e\u003cp\u003eInitialize \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:triangulated\\leftarrow\\:\\text{m}\\text{e}\\text{s}\\text{h}\\left(region\\right)\\)\u003c/span\u003e\u003c/span\u003e using the Triangle library [\u003cspan citationid=\"CR14\" class=\"CitationRef\"\u003e14\u003c/span\u003e]\u003c/p\u003e\u003cp\u003eInitialize tile \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:weights\\leftarrow\\:\\{{w}_{1},\\:{w}_{2},\\dots\\:,{w}_{n}\\}\\)\u003c/span\u003e\u003c/span\u003e using percentage of total region area\u003c/p\u003e\u003cp\u003e\u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:chosen\\_tri\\leftarrow\\:\\)\u003c/span\u003e\u003c/span\u003e random choice of \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:triangulated\\)\u003c/span\u003e\u003c/span\u003e tiles using \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:weights\\)\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e\u003cp\u003e\u003cstrong\u003eComment\u003c/strong\u003e\u003cp\u003eUsing approach from [\u003cspan citationid=\"CR15\" class=\"CitationRef\"\u003e15\u003c/span\u003e]\u003c/p\u003e\u003c/p\u003e\u003cp\u003e\u003cb\u003eIf\u003c/b\u003e \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:distribution=\\text{u}\\text{n}\\text{i}\\text{f}\\text{o}\\text{r}\\text{m}\\)\u003c/span\u003e\u003c/span\u003e \u003cb\u003edo\u003c/b\u003e\u003c/p\u003e\u003cp\u003e\u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\overrightarrow{a},\\:\\overrightarrow{b},\\:\\overrightarrow{c}\\leftarrow\\:\\)\u003c/span\u003e\u003c/span\u003e vertices of \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:chosen\\_tri\\)\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e\u003cp\u003e\u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{r}_{1},{r}_{2}\\leftarrow\\:\\)\u003c/span\u003e\u003c/span\u003e independent, random numbers\u003cdiv id=\"Equd\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equd\" name=\"EquationSource\"\u003e\n$$\\:u=1-\\sqrt{{r}_{1}}$$\u003c/div\u003e\u003c/div\u003e\u003cdiv id=\"Eque\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Eque\" name=\"EquationSource\"\u003e\n$$\\:v=\\sqrt{{r}_{1}}-(1-{r}_{2})$$\u003c/div\u003e\u003c/div\u003e\u003cdiv id=\"Equf\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equf\" name=\"EquationSource\"\u003e\n$$\\:w={r}_{2}\\sqrt{{r}_{1}}$$\u003c/div\u003e\u003c/div\u003e\u003cdiv id=\"Equg\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equg\" name=\"EquationSource\"\u003e\n$$\\:\\left({p}_{x},{p}_{y}\\right)\\leftarrow\\:u\\overrightarrow{a}+v\\overrightarrow{b}+w\\overrightarrow{c}$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e\u003cp\u003e\u003cb\u003ereturn\u003c/b\u003e \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:({p}_{x},{p}_{y})\\)\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e\u003cp\u003e\u003cb\u003eElse do\u003c/b\u003e\u003c/p\u003e\u003cp\u003eRaise \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:distribution\\_failure\\)\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e\u003cp\u003e\u003cb\u003ereturn\u003c/b\u003e \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\left({p}_{x},{p}_{y}\\right)\\)\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e\u003cp\u003eIf the algorithm is set for regions and fails to converge in the specified maximum iterations (by default, 50), it switches to the Triangulation method. Using the Triangle library [\u003cspan citationid=\"CR14\" class=\"CitationRef\"\u003e14\u003c/span\u003e], the shape file region is transformed into a polygon and subdivided into triangle tiles. Then, a random triangle is selected; using the area formula a random point inside that triangle is selected to be the node\u0026rsquo;s jittered location. This guarantees an acceptable solution in one iteration but is computationally more intensive than the Dartboard Algorithm and slower by a factor of \u003cem\u003es\u003c/em\u003e, where \u003cem\u003es\u003c/em\u003e is the number of sides in the polygonal representation of the region. This uses equations outlined in Osada [\u003cspan citationid=\"CR15\" class=\"CitationRef\"\u003e15\u003c/span\u003e] when the distribution is set to uniform. Currently, in the non-uniform case, failure of the Dartboard method raises an error. Application across subcomponent triangles of the region mesh will not result in the appropriate distribution over the region. We hope to address this functionality in future updates.\u003c/p\u003e\u003cp\u003eTo set up the architecture for tiling, the algorithm intakes user-specified arguments for the m x n desired solution or defaults to a 10 x 10 grid. The bounding box of this grid is formed by the minimum and maximum latitude and longitude, which is then subdivided as specified (see Fig.\u0026nbsp;\u003cspan refid=\"Fig1\" class=\"InternalRef\"\u003e1\u003c/span\u003e for an example of a 10 x 10 tiling solution on the generated Boston toy network). Each node is then jittered within its assigned tile. This ensures only one perturbation per node when selecting random points within the rectangular tiles.\u003c/p\u003e\u003cp\u003e\u003c/p\u003e\u003c/div\u003e"},{"header":"4. DISCUSSION","content":"\u003cdiv id=\"Sec8\" class=\"Section2\"\u003e\u003ch2\u003e4.1. CUSTOMIZATIONS\u003c/h2\u003e\u003cp\u003eRegional shapefiles are often available at multiple levels of granularity from as fine as census blocks or neighborhoods to nations or global shapefiles that display continents or coastlines. However, areas with uneven population density will often maintain unevenly sized regional designation areas for ease of administration; in the United States, Alaska and California demonstrate this characteristic. Sparsely populated regions can be over ten times the size of the small regions of dense urban areas. Additionally, shape file regions tend to be predicated on human population density, which may not be germane to the user\u0026rsquo;s network. Here, the user has a choice. If unsatisfied with the applicable regions, they can use the tiling regions to jitter the network. The input parameters of the function allow specification of a usefully sized grid of tiles for the given situation.\u003c/p\u003e\u003cp\u003eThe package defaults to uniform joint probability of latitude/longitude selection but allows specification of a joint probability surface within the regions. To an extent, the selection of region shapes influences location probability; the regions are conditional on population, which is reflected in node density and the possible jitter distance. Nodes in highly populated urban areas will tend to have small regions with high population and will have shorter jitter distances, which does reflect the probability for location in dense vs. sparse areas. However, if the user wishes to apply a specific distribution (e.g. a joint normal distribution), they may adjust the probabilities accordingly.\u003c/p\u003e\u003cp\u003e\u003c/p\u003e\u003c/div\u003e\u003cdiv id=\"Sec9\" class=\"Section2\"\u003e\u003ch2\u003e4.2. USE CASES\u003c/h2\u003e\u003cp\u003eGeoJitter enables the user to adjust its parameters based on the specific requirements of their project. The established spatial or network randomization techniques do not provide the same utility: a flexible location randomization technique that improves network visualizations. The limited scope of the tool also makes it easier to fine-tune results. Common network randomization methods disrupt or mask the significant structure of the original network. While this does support privacy, visualizations of these representations may fail to demonstrate key results from analysis.\u003c/p\u003e\u003cp\u003eWe anticipate utility to come from protecting information privacy from reidentification and from working with uncertainty within data. In the first scenario, our package enables privacy-preserving transformations that retain the structure of the underlying network while obscuring sensitive location data. In the second, users may only have access to simulated, approximate, or uncertain location data, often in the form of bounded regions or probabilistic estimates, and our package provides tools for constructing and working with spatial graphs in the presence of location uncertainty. We anticipate two use cases for our package: too much location data, and not enough location data.\u003c/p\u003e\u003cp\u003ePrecise geographic coordinates can compromise the anonymity of study participants; including visualization randomization in the study design reduces privacy risks such as those analyzed by Institutional Review Boards and ethics committees. Even in the absence of explicit identifiers such as names, quasi-identifiers (i.e. height, weight, gender, or ethnicity) can be cross-referenced with external datasets to enable re-identification. These linkage attacks are particularly damaging with the combination of multiple, individually innocuous, datasets \u0026ndash; increasingly accessible by publication or scraping [\u003cspan citationid=\"CR16\" class=\"CitationRef\"\u003e16\u003c/span\u003e].\u003c/p\u003e\u003cp\u003eIn scenarios such as disease transmission modeling, military logistics, and search and rescue operations, the exact locations of key nodes are often unknown. Instead, analysts work with zones of probable location, relying on partial or indirect evidence to infer spatial distributions. When considering the dependencies and conditional probabilities incurred within a network, traditional spatial graph analysis can be unreliable or misleading. Our library provides tools to formally incorporate spatial uncertainty, allowing users to define uncertainty regions associated with each node. This enables the network analysis to reflect the imprecise nature of the underlying data without discarding relational structure.\u003c/p\u003e\u003cp\u003eIn the first use case, the network contains precise location data attributes where clear communication of results does not necessitate, or where there is a compelling need to obscure, the location due to privacy or proprietary concerns. After determining an appropriate set of regions, GeoJitter is used to coarsen the shared information. Figure\u0026nbsp;\u003cspan refid=\"Fig3\" class=\"InternalRef\"\u003e3\u003c/span\u003e shows an example of a synthetic toy network generated with only region names and the GeoJitter location output. This example uses Boston neighborhood shapefiles published by the City of Boston [17].\u003c/p\u003e\u003cp\u003e\u003c/p\u003e\u003cp\u003eIn the second use case, the network contains region identifier attributes without precise location (e.g. ZIP code). If the network is synthetic or uses predicted location, regions are assigned upon creation either randomly or based on known probability distributions, often for simulation. Standard plotting tools will overlay all such nodes in a region directly in the center of that region, creating the appearance of a single node with the connectivity of the entire region\u0026rsquo;s node, as if coarse-graining the entire region to one representative node. In cases where this is undesirable, GeoJitter can be applied to the network and the geospatial perturbation will clarify the internodal relationships during visualization. In Fig.\u0026nbsp;\u003cspan refid=\"Fig3\" class=\"InternalRef\"\u003e3\u003c/span\u003e above, 2 node pairs (2\u0026ndash;3 and 7\u0026ndash;8) share regions but the Point Generator algorithm provides random spacing according to the set distribution.\u003c/p\u003e\u003c/div\u003e\u003cdiv id=\"Sec10\" class=\"Section2\"\u003e\u003ch2\u003e4.3. LIMITATIONS\u003c/h2\u003e\u003cp\u003eBecause the original network structure (degree distribution, motifs, communities, spanning trees, shortest paths, etc.) is unchanged, it is difficult to rigorously quantify the changes in a meaningful way beyond a geographical change in edge lengths. Based on aggregational reidentification risk, this continuity of structure means that researchers must be cautious in determining how to protect nonspatial network attributes.\u003c/p\u003e\u003c/div\u003e\u003cdiv id=\"Sec11\" class=\"Section2\"\u003e\u003ch2\u003e\u003cb\u003e4.4. FUTURE EXTENSIONS\u003c/b\u003e\u003c/h2\u003e\u003cp\u003eTo allow more flexibility in networks where spatial distances are unevenly distributed, we would like to add functions that would allow the user to specify an input tuple array indicating the desired \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:m\\)\u003c/span\u003e\u003c/span\u003e \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\times\\:\\)\u003c/span\u003e\u003c/span\u003e \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:n\\)\u003c/span\u003e\u003c/span\u003e tiling for each region. This would enable application of region-specific parameters for appropriately sized tilings across the network. In addition to specifying the number of tiles desired within the network\u0026rsquo;s bounding box, we would like to allow the user to specify the size of the tiles (e.g. 5km x 5km or similar). We are also developing methods that agglomerate regions based on the number of nodes within regions, thereby adjusting for network node density in addition to the regional population density metrics. Currently, the tiling option only supports rectangular tiles. It is possible to support any regular tiling but current exploration has not indicated utility in adding other tiling options.\u003c/p\u003e\u003cp\u003eThough the distribution argument currently supports use for a number of known statistical distributions, we have built in an argument to support extension to allow the user to define a 3-dimensional surface representation of location probability. This would enable users to fully specify any distribution of choice. We plan to incorporate full probability surfaces as user defined distributions in future implementations, providing maximum control over generated networks\u003c/p\u003e\u003c/div\u003e"},{"header":"Declarations","content":"\u003cp\u003e\u003cstrong\u003e5.1. FUNDING\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003eNo funds, grants, or other support was received.\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e 5.2. CONFLICTS OF INTEREST\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003eThe authors have no relevant financial or non-financial interests to disclose.\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e 5.3. ETHICS\u003c/strong\u003e \u003cstrong\u003eAPPROVAL\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003eNot applicable.\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e 5.4. CONSENT TO PARTICIPATE\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003eNot applicable.\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e 5.5. CONSENT TO PUBLISH\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003eNot applicable.\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e 5.6. DATA AND CODE AVAILABILITY\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003eCode and examples are available at https://github.com/SebastianNeumann2003/GeoJitter/.\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e 5.7. AUTHORS’ CONTRIBUTION STATEMENTS\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003eConceptualization: Nina Fiore; Methodology: Nina Fiore, Geoffrey Moores; Formal analysis and investigation: Nina Fiore, Geoffrey Moores; Software: Sebastian Neumann, Geoffrey Moores; Visualization: Sebastian Neumann; Writing – original draft: Nina Fiore; Writing – review and editing: Nina Fiore, Geoffrey Moores, Sebastian Neumann; Validation: Nina Fiore, Geoffrey Moores; Project administration: Nina Fiore; Supervision: Nina Fiore, Geoffrey Moores.\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e 5.8. ACKNOWLEDGMENTS\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003eUnstructured finite element meshes were created with Triangle version 1.6 (downloaded from http://www.cs.cmu.edu/~quake/triangle.html).\u003c/p\u003e"},{"header":"References","content":"\u003col\u003e\n\u003cli\u003eBrownstein JS, Cassa CA, Kohane IS, Mandl KD (2006) \u0026ldquo;An unsupervised classification method for inferring original case locations from low-resolution disease maps\u0026rdquo;. \u003cem\u003eInternational Journal of Health Geographics\u003c/em\u003e, 5(1):56. https://doi.org/10.1186/1476-072X-5-56/. \u003c/li\u003e\n\u003cli\u003ede Montjoye YA, Hidalgo C, Verleysen M, Blondel V (2013) \u0026ldquo;Unique in the Crowd: The privacy bounds of human mobility\u0026rdquo;. \u003cem\u003eSci Rep \u003c/em\u003e3, 1376. https://doi.org/10.1038/srep01376/.\u003c/li\u003e\n\u003cli\u003eSweeney L (2002) \u0026ldquo;\u003cem\u003ek\u003c/em\u003e-anonymity: A model for protecting privacy\u0026rdquo;. \u003cem\u003eInternational Journal on Uncertainty, Fuzziness and Knowledge-Based Systems\u003c/em\u003e, 10(5):557\u0026ndash;570. \u003c/li\u003e\n\u003cli\u003eLee S, Majeed A (2021) \u0026ldquo;Anonymization techniques for privacy preserving data publishing: A comprehensive survey\u0026rdquo;. \u003cem\u003eIEEE Access\u003c/em\u003e. https://ieeexplore.ieee.org/document/9298747/.\u003c/li\u003e\n\u003cli\u003eDwork C, Roth A (2014) \u0026ldquo;The Algorithmic Foundations of Differential Privacy\u0026rdquo;. \u003cem\u003eFound. Trends Theor. Comput. Sci. 9, 3\u0026ndash;4\u003c/em\u003e (Aug 2014), 211\u0026ndash;407. https://doi.org/10.1561/0400000042/. \u003c/li\u003e\n\u003cli\u003eUnited Nations Statistical Commission (2021) \u0026ldquo;Spatial anonymization\u0026rdquo;. In \u003cem\u003eStatistical Commission: Fifty-second session\u003c/em\u003e. https://unstats.un.org/unsd/statcom/52nd-session/documents/BG-3l-Spatial_Anonymization-E.pdf/.\u003c/li\u003e\n\u003cli\u003eAvraam D, Butters O, Wilson R, Burton T, Nicolaides C, Jones E, et al. (2021) \u0026ldquo;Privacy preserving data visualizations\u0026rdquo;. \u003cem\u003eEPJ Data Science\u003c/em\u003e, 10, 2. https://doi.org/10.1140/epjds/s13688-020-00257-4/.\u003c/li\u003e\n\u003cli\u003eJaffe A, Kluger Y, Linderman GC, Mishne G, Steinerberger S (2020) \u0026ldquo;Randomized near-neighbor graphs, giant components and applications in data science\u0026rdquo;. \u003cem\u003eJ Appl Probab\u003c/em\u003e. 2020 Jun;57(2):458-476. doi: https://doi.org/10.1017/jpr.2020.21/. Epub 2020 Jul 16. PMID: 32913373; PMCID: PMC7480951.\u003c/li\u003e\n\u003cli\u003eMaslov S, Sneppen K (2002) \u0026ldquo;Specificity and Stability in Topology of Protein Networks\u0026rdquo;. \u003cem\u003eScience\u003c/em\u003e. 2002 May 3;296(5569):910-3. doi: https://doi.org/10.1126/science.1065103/. PMID: 11988575.\u003c/li\u003e\n\u003cli\u003ePeixoto, T (2014) \u0026ldquo;Hierarchical Block Structures and High-Resolution Model Selection in Large Networks\u0026rdquo;. \u003cem\u003ePhys. Rev. X 4\u003c/em\u003e, 011047 \u0026ndash; 24 March, 2014. https://doi.org/10.1103/PhysRevX.4.011047/. \u003c/li\u003e\n\u003cli\u003eFrank O, Strauss D (1986) \u0026ldquo;Markov graphs\u0026rdquo;. \u003cem\u003eJ. Am. Statist. Ass\u003c/em\u003e. 1986;81:832\u0026ndash;842. \u003c/li\u003e\n\u003cli\u003eSnijders T (2002) \u0026ldquo;Markov Chain Monte Carlo Estimation of Exponential Random Graph Models\u0026rdquo;. \u003cem\u003eJournal of Social Structure\u003c/em\u003e. 2002 Jun.\u003c/li\u003e\n\u003cli\u003eSutherland IE, Sproull RF, Schumacker RA (1974) \u0026ldquo;A characterization of ten hidden-surface algorithms\u0026rdquo;. \u003cem\u003eACM Computing Surveys\u003c/em\u003e, 6(1):1\u0026ndash;55, March 1974. https://doi.org/10.1145/356625.356626/. \u003c/li\u003e\n\u003cli\u003eShewchuk, JR. (1996) \u0026ldquo;Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator\u0026rdquo;. In: Lin MC, Manocha D. (eds) Applied Computational Geometry Towards Geometric Engineering. WACG 1996. Lecture Notes in Computer Science, vol 1148. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0014497/. \u003c/li\u003e\n\u003cli\u003eOsada R, Funkhouser T, Chazelle B, Dobkin D (2002) \u0026quot;Shape Distributions.\u0026quot; \u003cem\u003eACM Transactions on Graphics 21(4)\u003c/em\u003e:807-832, October 2002.\u003c/li\u003e\n\u003cli\u003eVidanage A, Ranbaduge T, Christen P, Randall S (2020) \u0026ldquo;A privacy attack on multiple dynamic match-key based privacy-preserving record linkage\u0026rdquo;. \u003cem\u003eInternational Journal of Population Data Science\u003c/em\u003e, 5(1):1345. https://ijpds.org/article/view/1345/. \u003c/li\u003e\n\u003cli\u003eBoston Maps (2025) \u0026ldquo;Boston Neighborhood Boundaries.\u0026rdquo; Public record. https://data.boston.gov/dataset/bpda-neighborhood-boundaries/.\u003c/li\u003e\n\u003c/ol\u003e"}],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":true,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":true,"isAuthorSuppliedPdf":false,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":false,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"discover-networks","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"","sideBox":"Learn more about [Discover Networks](https://link.springer.com/journal/44354)","snPcode":"44354","submissionUrl":"https://submission.springernature.com/new-submission/44354/3","title":"Discover Networks","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Discover Series","inReviewEnabled":true,"inReviewRevisionsEnabled":true},"keywords":"Network randomization, privacy, GIS, anonymization","lastPublishedDoi":"10.21203/rs.3.rs-7491233/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-7491233/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eThis paper introduces the Python package GeoJitter, which provides region-aware randomization for spatial location of nodes. This package aids in preventing reidentification of private or proprietary information or spatial display of simulated, predicted, or uncertain information. The library is compatible with Networkx and standard shapefiles and will provide tiling solutions if region data is unknown or unavailable. We compare this technique to Census Enumeration Area, Radius, K-Nearest Neighbor (KNN), Degree Preserving, Stochastic Block Model (SBM), and Markov Chain Monte Carlo (MCMC) randomization.\u003c/p\u003e","manuscriptTitle":"GeoJitter: A Flexible Toolkit for Constraint-Aware Node Jittering in Spatial Networks","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-09-23 10:56:17","doi":"10.21203/rs.3.rs-7491233/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2025-10-27T12:46:37+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2025-10-24T12:45:31+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2025-10-22T05:49:11+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2025-10-15T16:13:21+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2025-10-12T07:51:51+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"48263688452835758655420312713029930344","date":"2025-10-11T06:41:11+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2025-10-11T05:16:26+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"187618363605460996607824564945003682964","date":"2025-10-10T15:58:01+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"152105654141300998415855946416745437081","date":"2025-10-10T03:38:07+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"181435229707790534563056559933195029115","date":"2025-10-08T04:48:26+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"38549650344643099556182355513955853776","date":"2025-10-08T03:29:46+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"329650663598880109362218248047555610229","date":"2025-10-08T01:47:26+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"160122723797674094289646511544860996095","date":"2025-09-18T03:28:25+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2025-09-15T07:47:49+00:00","index":"","fulltext":""},{"type":"editorInvited","content":"","date":"2025-09-12T17:01:40+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2025-09-04T04:21:51+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2025-09-04T04:21:04+00:00","index":"","fulltext":""},{"type":"submitted","content":"Discover Networks","date":"2025-08-29T19:30:38+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"discover-networks","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"","sideBox":"Learn more about [Discover Networks](https://link.springer.com/journal/44354)","snPcode":"44354","submissionUrl":"https://submission.springernature.com/new-submission/44354/3","title":"Discover Networks","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Discover Series","inReviewEnabled":true,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"fa647f36-40de-4818-a8d1-889625c10e3c","owner":[],"postedDate":"September 23rd, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"under-review","subjectAreas":[],"tags":[],"updatedAt":"2025-12-23T13:24:49+00:00","versionOfRecord":[],"versionCreatedAt":"2025-09-23 10:56:17","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-7491233","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-7491233","identity":"rs-7491233","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}