Overview of graph statistics

There are a number of directions we can head toward when we seek to understand the patterns and behaviors within a network. Here are a few of the key questions we might wish to understand:

• What does the overall structure of the network look like? Is it densely connected, or is the network rather sparse?
• Does our network have a high level of randomness, exemplified by few distinct patterns? Or are there very pronounced groups within the network that exhibit advanced levels of clustering?
• Do we see evidence of high degree hubs in the network, as in the case of the Web, with many smaller nodes surrounding the hubs?
• Are certain nodes critical within the structure of the network, perhaps acting as bridges between otherwise disconnected groups?

Each of these questions (and more) can be answered using graph statistics. Our job in this first section of the chapter is to better acquaint ourselves with which statistics to use and when to measure the various behaviors and...