Node Centralities are parameters that, given a node's position and connections, indicate its importance within a network. The simplest example of node centrality is the degree, which is the number of edges connected to a node; but there are a lot of other ways to measure node centrality, for example betweenness, stress, closeness, centroid, etc..

How many measures for node centralities do you know, that could be applied to a biological network? Can you recommend a good review of reference to compare these measures, and their meaning in a biological context?

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.