This chapter concerns itself with graphs in the mathematical rather than the visual sense. A graph is simply a set of vertices connected by the edges and the simplicity of this abstraction means that graphs are everywhere. They are an effective model for structures as diverse as the hyperlink structure of the web, the physical structure of the internet, and all sorts of networks: roads, telecommunications, and social networks.

Thus, network analysis is hardly new, but it has become particularly popular with the rise of social network analysis. Among the largest sites on the web are social networks, and Google, Facebook, Twitter, and LinkedIn all make use of large-scale graph processing to mine their users' data. The huge importance of targeted advertising for the monetization of websites means that there is a large financial reward for companies that effectively infer internet users' interests.

In this chapter...