I'll put some answers to get this discussion started.

• The Wikipedia page describes 4 node centrality measures: Degree, Betweenness, Closeness and Eigenvector.

• I like the description of different Node Centrality measures in the supplementary materials of the paper for Centiscape, a plugin for Cytoscape. There are good description of the possible biological meanings of each measure

• a tool called CentiBin can calculate various measures of Node Centralities. Its documentation and its related publication are a good source to be started.

Here is what I can offer from someone who once gave me advice for a similar question:

Here are some topological graph measures that you may find useful. The more commonly used measures are at the top.

• The degree distribution (i.e. a histogram showing how many nodes have degree 1, degree 2, etc...). Most biological networks tend to have a power-law degree-distribution (and are hence called 'scale-free' networks)
• What is the diameter of the graph (maximum length of any of the shortest paths between any 2 nodes)? What is the radius? [http://en.wikipedia.org/wiki/Distance_(graph_theory)]
• Clustering coefficients (http://en.wikipedia.org/wiki/Clustering_coefficient)
• What is the distribution of local clustering coefficients of the nodes?
• What is the global clustering coefficient of the whole graph?
• Is the network fully connected (single connected component) or are some parts disconnected from the rest (multiple connected components) [http://en.wikipedia.org/wiki/Connected_component_(graph_theory)]
• Connectivity: how well does the graph stay connected if you knock out nodes or edges?
• Vertex Connectivity [http://en.wikipedia.org/wiki/K-vertex-connected_graph ]
• Edge Connectivity [http://en.wikipedia.org/wiki/K-edge-connected_graph]
• You could investigate various measures of centrality [http://en.wikipedia.org/wiki/Centrality] for all the nodes, or some subset that you are more interested in. (Google's PageRank is a variant of the eigenvector centrality measure.)
• What is the Cheeger Constant of the graph (http://en.wikipedia.org/wiki/Cheeger_constant_(graph_theory)) This measures how "bottlenecked" it is.