A *graph* is a mathematical construct composed of one or more *nodes*
(or *vertices*) connected together by one or more *links*
(or *edges*). Graphs are an effective way to describe
communication without getting lost in the weeds. They can be used
to model connectivity and provide a comprehensive view of that
connectivity while abstracting away details such as packet sizes and
session length. Additionally, graph attributes such as centrality can
be used to identify critical nodes in a network. Finally, many
important protocols (in particular, SMTP and routing) rely on
algorithms that model their particular network as a graph.

This chapter is focused on the analytic properties of graphs. We begin by describing what a graph is and then developing examples for major attributes: shortest paths, centrality, clusters, and clustering coefficient.

A graph is a mathematical representation of a collection of objects
and their interrelationships. Originally developed in 1736 by
Leonhard Euler to address the problem of crossing the bridges of
Koenigsberg,^{1} graphs have since been used to model everything from the core members of conspiracies to the frequency of sounds uttered in the English language. Graphs are an extremely powerful and flexible descriptive tool, and that power comes because they are extremely fungible. Researchers in mathematics, engineering, and sociology have developed an extensive set of constructed and observed graph attributes ...

Start Free Trial

No credit card required