import%20marimo%0A%0A__generated_with%20%3D%20%220.23.13%22%0Aapp%20%3D%20marimo.App()%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%0A%20%20%20%20return%20(mo%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Adaptive%20Sampling%20for%20Large%20Networks%0A%0A%20%20%20%20Exact%20centrality%20runs%20a%20shortest-path%20traversal%20from%20every%20node%2C%20so%20cost%20grows%20with%20both%20network%20size%20and%20distance%20threshold.%20For%20large%20networks%20at%20long%20thresholds%2C%20%60cityseer%60%20offers%20an%20experimental%20adaptive%20sampling%20mode%3A%20pass%20%60sample%3DTrue%60%20and%20a%20subset%20of%20nodes%20is%20used%20as%20traversal%20sources%2C%20with%20results%20corrected%20by%20inverse-probability%20weighting%20so%20that%20estimates%20remain%20unbiased.%0A%0A%20%20%20%20The%20sampling%20is%20per-node%20adaptive.%20A%20cheap%20pilot%20polls%20the%20network%20with%20a%20small%20number%20of%20bounded%20shortest-path%20traversals%20to%20estimate%20each%20node's%20local%20reach%2C%20and%20the%20Hoeffding%20inequality%20converts%20that%20reach%20into%20the%20minimum%20sampling%20probability%20needed%20to%20keep%20the%20error%20within%20tolerance.%20Sparse%20areas%20are%20sampled%20more%20heavily%20and%20dense%20areas%20less%2C%20so%20precision%20is%20uniform%20across%20the%20network.%20For%20each%20distance%20threshold%2C%20a%20work%20test%20compares%20the%20cost%20of%20properly%20powered%20sampling%20against%20exact%20computation%20and%20selects%20the%20cheaper%3A%20short%20thresholds%20typically%20run%20exactly%2C%20long%20thresholds%20on%20large%20networks%20are%20sampled.%0A%0A%20%20%20%20This%20notebook%20demonstrates%20sampling%20on%20the%20full%20bundled%20street%20network%20through%20the%20high-level%20%5B%60CityNetwork%60%5D(https%3A%2F%2Fcityseer.benchmarkurbanism.com%2Fapi%2Fnetwork)%20class%20and%20validates%20the%20sampled%20results%20against%20an%20exact%20run.%20Sampling%20is%20experimental%3B%20the%20API%20may%20change.%20See%20the%20%5Bguide%5D(https%3A%2F%2Fcityseer.benchmarkurbanism.com%2Fguide%2Fcentrality%23adaptive-sampling)%20and%20the%20%5Bsampling%20reference%5D(https%3A%2F%2Fcityseer.benchmarkurbanism.com%2Fmetrics%2Fsampling).%0A%0A%20%20%20%20The%20bundled%20datasets%20and%20their%20source%20attributions%20are%20documented%20on%20the%20%5Bdatasets%20page%5D(https%3A%2F%2Fcityseer.benchmarkurbanism.com%2Fexamples%2Fdatasets).%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20time%0A%0A%20%20%20%20import%20geopandas%20as%20gpd%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%20%20%20%20from%20cityseer.network%20import%20CityNetwork%0A%20%20%20%20from%20scipy.stats%20import%20spearmanr%0A%0A%20%20%20%20return%20CityNetwork%2C%20gpd%2C%20plt%2C%20spearmanr%2C%20time%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Network%20preparation%0A%0A%20%20%20%20We%20use%20the%20full%20bundled%20street%20network%20(province%20clip%2C%20roughly%2020km%20around%20the%20city)%20and%20mark%20nodes%20inside%20the%20municipal%20boundary%20as%20live%20via%20the%20%60boundary%60%20argument.%20Live%20status%20matters%20here%20for%20two%20reasons%3A%20results%20are%20only%20reported%20for%20live%20nodes%2C%20and%20for%20closeness%20the%20exact%20mode%20skips%20dead%20nodes%20as%20sources%2C%20which%20keeps%20the%20exact%20baseline%20affordable.%20This%20is%20the%20standard%20buffered-network%20setup%20described%20in%20the%20%5Bedge%20rolloff%5D(https%3A%2F%2Fcityseer.benchmarkurbanism.com%2Fguide%2Ffundamentals%23edge-rolloff)%20section.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(CityNetwork%2C%20gpd%2C%20mo)%3A%0A%20%20%20%20data_dir%20%3D%20(mo.notebook_dir()%20%2F%20%22..%22%20%2F%20%22..%22%20%2F%20%22data%22).resolve()%0A%20%20%20%20streets_gpd%20%3D%20gpd.read_file(data_dir%20%2F%20%22madrid_streets%22%20%2F%20%22street_network.gpkg%22)%0A%20%20%20%20streets_gpd%20%3D%20streets_gpd.explode(ignore_index%3DTrue)%0A%20%20%20%20%23%20the%20source%20data%20contains%20a%20small%20number%20of%20exact%20duplicate%20geometries%0A%20%20%20%20streets_gpd%20%3D%20streets_gpd.drop_duplicates(subset%3D%22geometry%22)%0A%20%20%20%20bounds_gpd%20%3D%20gpd.read_file(data_dir%20%2F%20%22madrid_bounds%22%20%2F%20%22madrid_bounds.gpkg%22)%0A%20%20%20%20boundary_poly%20%3D%20bounds_gpd.geometry.iloc%5B0%5D%0A%0A%20%20%20%20cn%20%3D%20CityNetwork.from_geopandas(streets_gpd%2C%20boundary%3Dboundary_poly)%0A%20%20%20%20print(f%22%7Bcn.node_count%7D%20street%20segments%20(dual%20nodes)%2C%20%7Bint(cn.nodes_gdf.live.sum())%7D%20live%22)%0A%20%20%20%20return%20(cn%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Sampled%20computation%0A%0A%20%20%20%20Enable%20sampling%20with%20%60sample%3DTrue%60.%20The%20log%20reports%2C%20per%20distance%2C%20whether%20the%20work%20test%20selected%20exact%20computation%20(%22Full%22)%20or%20sampling%2C%20and%20in%20the%20sampled%20case%20the%20mean%20source%20inclusion%20probability%20%60q%60.%20We%20compute%20a%20single%20harmonic%20closeness%20at%201600m%20and%2010000m%3B%20on%20this%20network%20the%20work%20test%20runs%201600m%20exactly%20and%20samples%2010000m%20at%20a%20mean%20inclusion%20probability%20of%20roughly%20a%20third.%20%60random_seed%60%20makes%20the%20draw%20reproducible.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(cn%2C%20time)%3A%0A%20%20%20%20t0%20%3D%20time.time()%0A%20%20%20%20cn.centrality_shortest(%0A%20%20%20%20%20%20%20%20distances%3D%5B1600%2C%2010000%5D%2C%0A%20%20%20%20%20%20%20%20closeness%3D%7B%22harmonic%22%3A%20%221%2Fc%22%7D%2C%0A%20%20%20%20%20%20%20%20betweenness%3D%7B%7D%2C%0A%20%20%20%20%20%20%20%20sample%3DTrue%2C%0A%20%20%20%20%20%20%20%20random_seed%3D42%2C%0A%20%20%20%20)%0A%20%20%20%20nodes_sampled%20%3D%20cn.to_geopandas()%0A%20%20%20%20t_sampled%20%3D%20time.time()%20-%20t0%0A%20%20%20%20print(f%22sampled%20run%3A%20%7Bt_sampled%3A.1f%7Ds%22)%0A%20%20%20%20return%20nodes_sampled%2C%20t_sampled%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Validation%20against%20an%20exact%20run%0A%0A%20%20%20%20To%20check%20the%20approximation%20quality%20we%20recompute%20the%20sampled%2010000m%20threshold%20exactly%20and%20compare.%20Two%20views%20of%20agreement%20matter%20in%20practice%3A%0A%0A%20%20%20%20-%20**rank%20agreement**%20(Spearman%20rho)%3A%20whether%20the%20sampled%20results%20order%20locations%20the%20same%20way%2C%20which%20is%20what%20most%20comparative%20analyses%20rely%20on%3B%0A%20%20%20%20-%20**relative%20error**%3A%20the%20per-node%20deviation%20of%20the%20sampled%20estimate%20from%20the%20exact%20value.%0A%0A%20%20%20%20The%20default%20tolerance%20%60epsilon%3D0.05%60%20is%20calibrated%20so%20that%20rank%20agreement%20holds%20at%20Spearman%20rho%20of%20at%20least%200.95%20on%20networks%20spanning%20the%20density%20range%20from%20metropolitan%20grids%20to%20sparse%20suburbs.%20Tighten%20%60epsilon%60%20for%20stricter%20agreement%20at%20higher%20cost%2C%20for%20example%20%60epsilon%3D0.03%60%3B%20very%20sparse%20networks%20may%20need%20this.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(cn%2C%20nodes_sampled%2C%20time)%3A%0A%20%20%20%20t0_exact%20%3D%20time.time()%0A%20%20%20%20cn.centrality_shortest(%0A%20%20%20%20%20%20%20%20distances%3D%5B10000%5D%2C%0A%20%20%20%20%20%20%20%20closeness%3D%7B%22harmonic%22%3A%20%221%2Fc%22%7D%2C%0A%20%20%20%20%20%20%20%20betweenness%3D%7B%7D%2C%0A%20%20%20%20)%0A%20%20%20%20%23%20to_geopandas%20snapshots%20are%20independent%2C%20so%20nodes_sampled%20keeps%20the%20sampled%20values%0A%20%20%20%20nodes_exact%20%3D%20cn.to_geopandas()%0A%20%20%20%20assert%20nodes_exact.index.equals(nodes_sampled.index)%0A%20%20%20%20t_exact%20%3D%20time.time()%20-%20t0_exact%0A%20%20%20%20print(f%22exact%20run%20(10000m)%3A%20%7Bt_exact%3A.1f%7Ds%22)%0A%20%20%20%20return%20nodes_exact%2C%20t_exact%0A%0A%0A%40app.cell%0Adef%20_(nodes_exact%2C%20nodes_sampled%2C%20spearmanr%2C%20t_exact%2C%20t_sampled)%3A%0A%20%20%20%20live_mask%20%3D%20nodes_exact.live%0A%20%20%20%20exact_vals%20%3D%20nodes_exact.loc%5Blive_mask%2C%20%22cc_harmonic_10000%22%5D%0A%20%20%20%20sampled_vals%20%3D%20nodes_sampled.loc%5Blive_mask%2C%20%22cc_harmonic_10000%22%5D%0A%20%20%20%20rho%20%3D%20spearmanr(exact_vals%2C%20sampled_vals).statistic%0A%20%20%20%20rel_err%20%3D%20((sampled_vals%20-%20exact_vals).abs()%20%2F%20exact_vals).median()%0A%20%20%20%20print(f%22Spearman%20rho%20(exact%20vs%20sampled%2C%2010000m%2C%20live%20nodes)%3A%20%7Brho%3A.4f%7D%22)%0A%20%20%20%20print(f%22median%20relative%20error%3A%20%7Brel_err%3A.2%25%7D%22)%0A%20%20%20%20print(f%22exact%20%7Bt_exact%3A.1f%7Ds%20vs%20sampled%20%7Bt_sampled%3A.1f%7Ds%20(sampled%20run%20also%20covers%201600m)%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(nodes_sampled%2C%20plt)%3A%0A%20%20%20%20fig%2C%20axes%20%3D%20plt.subplots(1%2C%202%2C%20figsize%3D(13%2C%206.5)%2C%20dpi%3D150)%0A%20%20%20%20for%20ax%2C%20col%20in%20zip(axes%2C%20%5B%22cc_harmonic_1600%22%2C%20%22cc_harmonic_10000%22%5D%2C%20strict%3DFalse)%3A%0A%20%20%20%20%20%20%20%20_dist%20%3D%20col.split(%22_%22)%5B-1%5D%0A%20%20%20%20%20%20%20%20_label%20%3D%20f%22Harmonic%20closeness%2C%20%7B_dist%7D%20m%22%0A%20%20%20%20%20%20%20%20g%20%3D%20nodes_sampled%5Bnodes_sampled.live%5D.copy()%0A%20%20%20%20%20%20%20%20g%5B%22_r%22%5D%20%3D%20g%5Bcol%5D.rank(pct%3DTrue)%0A%20%20%20%20%20%20%20%20g%20%3D%20g.sort_values(%22_r%22)%20%20%23%20strongest%20drawn%20last%0A%20%20%20%20%20%20%20%20g.plot(ax%3Dax%2C%20color%3Dplt.get_cmap(%22OrRd%22)(g%5B%22_r%22%5D)%2C%20linewidth%3D0.15%20%2B%202.25%20*%20g%5B%22_r%22%5D)%0A%20%20%20%20%20%20%20%20ax.set_title(f%22%7B_label%7D%20(sampled%20run)%22%2C%20loc%3D%22left%22)%0A%20%20%20%20%20%20%20%20ax.set_axis_off()%0A%20%20%20%20fig.tight_layout()%0A%20%20%20%20fig%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Betweenness%20engages%20sampling%20sooner%0A%0A%20%20%20%20The%20thresholds%20at%20which%20sampling%20engages%20depend%20on%20what%20is%20being%20computed.%20Closeness%20in%20exact%20mode%20only%20sources%20from%20live%20nodes%2C%20so%20on%20this%20network%20the%20work%20test%20does%20not%20find%20sampling%20worthwhile%20until%20roughly%2010000m.%20Betweenness%20must%20source%20from%20every%20node%2C%20including%20the%20dead%20buffer%20nodes%2C%20so%20its%20exact%20cost%20rises%20much%20more%20steeply%3A%20with%20a%20betweenness%20expression%20in%20the%20run%2C%20the%20planner%20already%20samples%20the%205000m%20threshold%20on%20this%20network%20(at%20a%20mean%20inclusion%20probability%20of%20roughly%20three%20quarters).%20The%20call%20is%20otherwise%20identical%3A%0A%0A%20%20%20%20%60%60%60python%0A%20%20%20%20cn.centrality_shortest(%0A%20%20%20%20%20%20%20%20distances%3D%5B1600%2C%205000%5D%2C%0A%20%20%20%20%20%20%20%20sample%3DTrue%2C%0A%20%20%20%20%20%20%20%20random_seed%3D42%2C%0A%20%20%20%20)%0A%20%20%20%20%60%60%60%0A%0A%20%20%20%20%23%23%20Practical%20notes%0A%0A%20%20%20%20-%20Sampling%20is%20opt-in%20(%60sample%3DTrue%60)%20and%20applies%20per%20distance%20threshold%3B%20you%20can%20mix%20short%20exact%20thresholds%20and%20long%20sampled%20thresholds%20in%20one%20call.%0A%20%20%20%20-%20%60epsilon%60%20trades%20cost%20against%20precision%3B%20%60random_seed%60%20gives%20reproducible%20draws.%0A%20%20%20%20-%20The%20work%20test%20means%20%60sample%3DTrue%60%20is%20safe%20to%20leave%20on%3A%20where%20sampling%20would%20not%20help%2C%20the%20exact%20path%20is%20used%20automatically.%0A%20%20%20%20-%20The%20same%20parameters%20are%20available%20on%20%5B%60centrality_simplest%60%5D(https%3A%2F%2Fcityseer.benchmarkurbanism.com%2Fapi%2Fnetwork%23centrality_simplest)%20and%20on%20the%20lower-level%20functional%20%60networks%60%20module.%0A%20%20%20%20-%20Sampling%20is%20experimental%3A%20behaviour%20and%20defaults%20may%20change%20between%20releases.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A
b258e074f3314ae140597b8b802f5d9e