Graphing

The next chapter, or rather the next few chapters, in Algorithms for Dummies, by John Paul Mueller and Luca Massaron, is all about graphing but not in the typical way we regard graphing. Instead of a typical line or bar chart that we are familiar with, these Python graphs can be regarded as images of connections and nodes or networks.

Examples of what can be constituted as graphs are: maps, traffic flows, telephone menu or any menu system, applications or wizards, recipes, chemical relationships, social relationships, emails, twitter tweets, blood flows, mutation cycles and on and on. There are subgraphs and loops, cycles, directed and undirected graphs, mixed graphs.

Yes, graphs are more than we typically think of as graphs.

The main concept out of this first chapter on graphs is the concept of importance or centrality. There are algorithms that can compute which part of the graph is important and should be analyzed. The importance or centrality can stem from the number of connections at each node or what is referred to as the nodes’ degrees. There is also the concept of clustering: which group of nodes has the greatest clustering. Sometimes, it’s the distances or closeness that can be important, especially in maps and traffic. Other times, it might be the betweenness, useful for transfers or figuring out where to strengthen or weaken the structure.

Because there are different ways to calculate centrality, it is important that the one you choose suits your goals or truly highlights what is important.

The other important thing about graphs is that there will be times when you have to convert the graphs into a more suitable number format so that any packages you import (such as NumPy or SciPy) can utilize the graph information. You might need to convert the graph into a matrix, but, depending on the number of nodes, this matrix might become extremely large. There’s a method of converting graphs into a sparse representation where only connections are listed in the array or matrix; this is very useful for conserving your resources. Finally, there is a dictionary of lists which apparently developers use.

So far, that’s the high level concepts that I got from the book (as well as some useful programs to draw the graphs, to compute the various centrality, and to convert the graphs into number formats). There are three more chapters on graphs one of which concerns web pages. That should be interesting.