Creating a Graph from Address Data

Question

What's the best / easiest way to create a graph from address data? For example, if I have 100 houses from all across a city is there any easy way to determine the shortest distance between two houses and all that good stuff? Would this require changing the data into coordinates and using GIS software or can I get away with using Python or R?

Answer 1

Speaking as a Graph/Complex Networks guy I'd recommend Networkx package in Python. This is the main library I used for my master thesis and my research during last 2 years. As long as your graph is not gigantic (millions of nodes) you can handle it using Networkx.

But what you need is not only the library but a philosophy to convert your data into a graph. What is your data exactly? If you have some addresses, what would be the node and what would define an edge? This is important actually. Graph is not constructed from your addresses unless you have a definition for vertices and edges.

When you convert your data into a graph Networkx provides you all fancy algorithms for everything (shortest path, community detection, statistical analysis, etc).

If you provide info in the comment here I'll answer your question in details.

Answer 2

Here's a simple solution using the R package ggmap.

start <- '95 clark st, new haven, ct'
end <- 'maison mathis, new haven, ct'
legs <- route(start,end, alternatives = TRUE)

Will find routes from start to end.

      m    km     miles seconds   minutes       hours  startLon startLat    endLon   endLat leg route
1    60 0.060 0.0372840       7 0.1166667 0.001944444 -72.91617 41.31511 -72.91678 41.31541   1     A
2   718 0.718 0.4461652      95 1.5833333 0.026388889 -72.91678 41.31541 -72.92100 41.30979   2     A
3   436 0.436 0.2709304      64 1.0666667 0.017777778 -72.92100 41.30979 -72.92555 41.31171   3     A
4   431 0.431 0.2678234      68 1.1333333 0.018888889 -72.92555 41.31171 -72.92792 41.30829   4     A
5    60 0.060 0.0372840       7 0.1166667 0.001944444 -72.91617 41.31511 -72.91678 41.31541   1     B
6  1276 1.276 0.7929064     179 2.9833333 0.049722222 -72.91678 41.31541 -72.92430 41.30543   2     B
7   421 0.421 0.2616094      62 1.0333333 0.017222222 -72.92430 41.30543 -72.92869 41.30729   3     B
8   129 0.129 0.0801606      28 0.4666667 0.007777778 -72.92869 41.30729 -72.92792 41.30829   4     B
9    60 0.060 0.0372840       7 0.1166667 0.001944444 -72.91617 41.31511 -72.91678 41.31541   1     C
10  421 0.421 0.2616094      58 0.9666667 0.016111111 -72.91678 41.31541 -72.91924 41.31211   2     C
11  522 0.522 0.3243708     101 1.6833333 0.028055556 -72.91924 41.31211 -72.92502 41.31382   3     C
12  240 0.240 0.1491360      33 0.5500000 0.009166667 -72.92502 41.31382 -72.92555 41.31171   4     C
13  431 0.431 0.2678234      68 1.1333333 0.018888889 -72.92555 41.31171 -72.92792 41.30829   5     C

And then we can find the length of time estimated to walk there with something like this.

tapply(legs$minutes, legs$route, max)

Hope this helps!

Answer 3

If you have latitude/longitude coordinate data, there should be no problem accomplishing this using great circle calculations which could indeed be accomplished in Python, R, or essentially any other language.

Here is an article on several methods and calculations for this:

Calculate distance, bearing and more between Latitude/Longitude points

The main issue with street address data alone is of course the lack of contextual information regarding the physical layout of the streets. Given a sufficiently complete scale map of the relevant area, you could also calculate a distance. That said, the haversine formula discussed in the article above would have a greater accuracy unless the scale map mentioned was also plotted as the surface of a sphere.