Testing Centrality



In [1]:

    
%matplotlib inline



In [1]:

    
# %load testShortestPath2.py
from rasterGraphCreate import *
import matplotlib

from matplotlib import pyplot

if __name__ == "__main__":
    
    arraySize = 100

    startNode = 4
    destNode = 8080

    startNode1 = 90
    destNode1 = 8008

    startNode2 = 30
    destNode2 = 9080

    raster = np.zeros((arraySize,arraySize))

    measureX = np.linspace(0,5, arraySize)
    measureY = measureX.copy()
    kx,ky = np.meshgrid(measureX, measureY)

    raster += np.exp(-pow(kx-0.5, 2)/.5  - pow(ky-2.5,2)/2.)
    raster += np.exp(-pow(kx-2.5, 2)/.5  - pow(ky-2.5,2)/2.)
    raster += np.exp(-pow(kx-4.5, 2)/.5  - pow(ky-2.5,2)/2.)
    #raster += np.exp(-pow(measureX-0.5, 2)/5.  - pow(measureY-0.7,2)/5.)

    raster += 0.1*np.random.random(raster.shape)

    pyplot.ion()
    pyplot.imshow(raster.transpose(),cmap=pyplot.cm.coolwarm)

    def weightFn(arr, v1index, v2index):
        return (raster[v1index] + raster[v2index])/2.

    g = createGraph(raster, weightFunction=weightFn)


    vlist, elist = shortest_path(g, g.vertex(startNode), g.vertex(destNode), weights=g.ep.edgeCost)
    print g.vertex(4)
    print [vert for vert in g.vertex(destNode).out_neighbours()]

    xs = []
    ys = []
    for vertex in vlist:
        index = g.vertex_index[vertex]
        row,col = getRowCol(index, arraySize)

        xs.append(row)
        ys.append(col)

    pyplot.hold(True)

    pyplot.plot(xs, ys,'white',linewidth=2)

    vlist, elist = shortest_path(g, g.vertex(startNode1), g.vertex(destNode1), weights=g.ep.edgeCost)
    print g.vertex(4)
    
    print [vert for vert in g.vertex(destNode).out_neighbours()]

    xs = []
    ys = []
    for vertex in vlist:
        index = g.vertex_index[vertex]
        row,col = getRowCol(index, arraySize)

        xs.append(row)
        ys.append(col)

    pyplot.hold(True)

    pyplot.plot(xs, ys,'red',linewidth=2)



    vlist, elist = shortest_path(g, g.vertex(startNode2), g.vertex(destNode2), weights=g.ep.edgeCost)
    
    xs = []
    ys = []
    for vertex in vlist:
        index = g.vertex_index[vertex]
        row,col = getRowCol(index, arraySize)

        xs.append(row)
        ys.append(col)

    pyplot.hold(True)

    pyplot.plot(xs, ys,'k',linewidth=2)


    pyplot.xlim(-1,arraySize)
    pyplot.ylim(0,arraySize)
    pyplot.show()









    



4
[<Vertex object with index '8081' at 0x7f32b4b51ad0>, <Vertex object with index '8179' at 0x7f32965368d0>, <Vertex object with index '8180' at 0x7f3296536950>, <Vertex object with index '8181' at 0x7f32965369d0>, <Vertex object with index '8079' at 0x7f3296536a50>, <Vertex object with index '7979' at 0x7f3296536ad0>, <Vertex object with index '7980' at 0x7f3296536b50>, <Vertex object with index '7981' at 0x7f3296536bd0>]
4
[<Vertex object with index '8081' at 0x7f32b37a1ed0>, <Vertex object with index '8179' at 0x7f32b37a1e50>, <Vertex object with index '8180' at 0x7f32b37a1dd0>, <Vertex object with index '8181' at 0x7f32b37a1d50>, <Vertex object with index '8079' at 0x7f32b37a1cd0>, <Vertex object with index '7979' at 0x7f32b37a1c50>, <Vertex object with index '7980' at 0x7f32b37a1bd0>, <Vertex object with index '7981' at 0x7f32b37a1b50>]

We are using a synthetic example to explore shortest paths. The figure above shows a simple raster which can be thought of as two regions separated by two 'hills' and a valley in between them.

Three paths from one side to another, marked in red, white and black are calculated. As you can observe, all of them pass through a certain region in the valley. We want to see if this region can be highlighted somehow.

For this we use Betweenness centrality.



In [2]:

    
import graph_tool.centrality as centrality

#Calculate centrality
vp, ep = centrality.betweenness(g, weight = g.ep['edgeCost'])



In [3]:

    
from pylab import *
output = createRaster(g, vp, arraySize, arraySize)

imshow(output.transpose(), cmap= cm.coolwarm)
colorbar()









    Out[3]:





<matplotlib.colorbar.Colorbar instance at 0x7f3295870ea8>

The betweenness centrality measure shows 'hotspots' or natural 'highways' in the map which facilitate movement. As the above figure shows, the central region through which most paths seem to pass is highlighted. The tops of the hills have almost no shortest paths passing through them.