Algorithms For Dummies

 Exploring the World of Graphs

Measuring Graph Functionality

After you can visualize and understand a graph, you need to consider the question 

of which parts of the graph are important. After all, you don’t want to spend your 

time performing analysis on data that doesn’t really matter in the grand scheme 

of things. Think about someone who is analyzing traffic flow to improve the street 

system. The intersections represent vertexes and the streets represent edges 

along which the traffic flows. By knowing how the traffic flows, that is, which 

vertexes and edges see the most traffic, you can start thinking about which roads 

to widen and which need more repair because more traffic uses them.

However, just looking at individual streets isn’t enough. A new skyscraper may 

bring with it a lot of traffic that affects an entire area. The skyscraper represents 

a  central  point  around  which  traffic  flow  becomes  more  important.  The  most 

important vertexes are those central to the new skyscraper. Calculating centrality, 

the most important vertexes in a graph, can help you understand which parts of 

the graph require more attention. The following sections discuss the basic issues 

you must consider when measuring graph functionality, which is the capability of 

the graph to model a specific problem.