https://github.com/anvaka/similar-cities Skip to content Navigation Menu Toggle navigation Sign in * Product + GitHub Copilot Write better code with AI + Security Find and fix vulnerabilities + Actions Automate any workflow + Codespaces Instant dev environments + Issues Plan and track work + Code Review Manage code changes + Discussions Collaborate outside of code + Code Search Find more, search less Explore + All features + Documentation + GitHub Skills + Blog * Solutions By company size + Enterprises + Small and medium teams + Startups By use case + DevSecOps + DevOps + CI/CD + View all use cases By industry + Healthcare + Financial services + Manufacturing + Government + View all industries View all solutions * Resources Topics + AI + DevOps + Security + Software Development + View all Explore + Learning Pathways + White papers, Ebooks, Webinars + Customer Stories + Partners + Executive Insights * Open Source + GitHub Sponsors Fund open source developers + The ReadME Project GitHub community articles Repositories + Topics + Trending + Collections * Enterprise + Enterprise platform AI-powered developer platform Available add-ons + Advanced Security Enterprise-grade security features + GitHub Copilot Enterprise-grade AI features + Premium Support Enterprise-grade 24/7 support * Pricing Search or jump to... Search code, repositories, users, issues, pull requests... Search [ ] Clear Search syntax tips Provide feedback We read every piece of feedback, and take your input very seriously. [ ] [ ] Include my email address so I can be contacted Cancel Submit feedback Saved searches Use saved searches to filter your results more quickly Name [ ] Query [ ] To see all available qualifiers, see our documentation. Cancel Create saved search Sign in Sign up Reseting focus You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert {{ message }} anvaka / similar-cities Public * Notifications You must be signed in to change notification settings * Fork 2 * Star 29 Visualization of cities with similar road networks anvaka.github.io/similar-cities/ 29 stars 2 forks Branches Tags Activity Star Notifications You must be signed in to change notification settings * Code * Issues 0 * Pull requests 0 * Actions * Projects 0 * Security * Insights Additional navigation options * Code * Issues * Pull requests * Actions * Projects * Security * Insights anvaka/similar-cities main BranchesTags [ ] Go to file Code Folders and files Name Name Last commit Last commit message date Latest commit History 5 Commits public public src src .browserslistrc .browserslistrc .eslintrc.js .eslintrc.js .gitignore .gitignore README.md README.md babel.config.js babel.config.js deploy.sh deploy.sh package-lock.json package-lock.json package.json package.json vue.config.js vue.config.js View all files Repository files navigation * README Similar cities This website shows cities that have similar road networks. grid similarities Play with it here: https://anvaka.github.io/similar-cities/ Definition of the similarity The similarity of two graphs is defined by counting number of anonymous walks on each graph and then computing generalized Jaccard similarity of the count vectors. Let me interpret the statement above. Imagine there is a slightly drunk person walking in a city. They start at random position in the first city, take a very short walk, say 4 intersections, and stop. At each intersection they pick a random direction. They don't remember the names of the intersections, or any previous walks that they've done. However during a single walk, they remember each intersection by assigning it a number. It could go like this: Intersection 1: Decided to go to intersection 2 Intersection 2: Decided to go to intersection 3 Intersection 3: Decided to go back to intersection 2 Intersection 2: Stop The entire walk can be labeled by sequence of intersection numbers: 1,2,3,2. Now, we remember that sequence 1,2,3,2 happened one time. Let's repeat the walking process a few thousand times, starting at arbitrary nodes. Every time we get a sequence we add plus one to the number of times we've seen this sequence before. Then we repeat the same process for the second city! At the end we get two counters of sequences, one for each city. We assume that the more times the same sequence appears in both cities - the more similar are those cities. This doesn't take into account road lengths or directions. Just a general local structure of the walk. In practice, I took not 4 intersections, but 8. This gives approximately 4,000 possible unique sequences. Each sequence has a reserved spot in a vector, with number of times the sequence appeared. The vectors are used to compute the generalized Jaccard similarity. Data and code The entire algorithm that finds graph similarity is available here The cities are indexed from OpenStreetMap using code in anvaka/ similar-cities-data repository. There are ~2,500 cities captured by the crawler. As is results are pretty interesting, but extending the dataset would probably yield even better results. If you know how to reliably get all roads within city boundaries form OpenStreetMap, please share. Local build First - you need to clone/fork this repository and then: npm install Compiles and hot-reloads for development npm start Thanks! * Stay tuned for updates: https://twitter.com/anvaka * If you like my work and would like to support it - https:// www.patreon.com/anvaka About Visualization of cities with similar road networks anvaka.github.io/similar-cities/ Resources Readme Activity Stars 29 stars Watchers 3 watching Forks 2 forks Report repository Releases No releases published Packages 0 No packages published Languages * JavaScript 66.5% * Vue 27.4% * HTML 5.4% * Shell 0.7% Footer (c) 2024 GitHub, Inc. Footer navigation * Terms * Privacy * Security * Status * Docs * Contact * Manage cookies * Do not share my personal information You can't perform that action at this time.