# graph theory operations to explore structure of a graph

I'm analyzing experimental data, and I've produced graphs that look similar to the attached sketch. When I look at the graph, I see structure in the connections (connections tend to be local, there is one central collection of nodes and three branches).

I'm wondering if anyone can point me toward areas of graph theory that might help me to quantify this structure. Note that there are sometimes spurious edges connecting distant parts of the graph (such edges are rare and no examples are shown in the sketch), so I'm hoping to find methods that can tolerate such things.

## 1 Answer

There are a handful of common metrics when analyzing graphs and networks.

• Clustering coefficient: given a vertex $i$ in the graph and two neighbors $j$, $k$ of $i$, what are the odds that $j$ and $k$ are also connected? Analogy: knowing that Gertrude Stein and Ernest Hemingway are both friends of mine, what are the chances that they're friends with each other?
• Degree distribution: plot a histogram of the degrees of all the nodes in the graph. What does it look like? For example, internet sites with connectivity defined by links have a degree distribution such that $P[\textrm{degree}(i) = k] \propto k^{-\gamma}$ for some constant $\gamma$; this is called a scale-free network. By contrast, Erdos-Renyi graphs' degrees are Poisson-distributed.
• Breadth: on average, how long does it take to get from one arbitrary vertex to another? In many networks (social, neural, ...), the distance is proportional to $\log n$ for a network of size $n$.
• Robustness: on average, how many edges do you have to remove at random for your network to become disconnected? On average, how many connected components can your graph be split into if you get to choose $k$ edges to remove?

This list is, of course, not exhaustive. I also highly recommend using software like Graphviz to make graph drawings.

Things to google: network theory, small world network, Watts-Strogatz model, Barabasi-Albert model, scale-free network, Erdos-Renyi model, block two-level Erdos-Renyi model.