Efficiency

[rgrohit]

In class we discussed measuring efficiency in the brain in terms of the paper. Does anyone have ideas on how it might be done in other fields that deal with networks?

[sgomezr]

I've seen two definitions of graph efficiency so far: the used by Crossley et. al[2] in the paper we presented last week and the definition by Latora and Marchiori[1]. Crossley used the definition provided by Sporns, 'a graph's efficiency is the inverse of the average shortest path'. The definition by Latora and Marchiori[1], is more for vertex efficiency and is defined in a similar way: 'Vertex efficiency is the harmonic mean distance between a vertex and all others'. Actually, I think Sporns only reported the definition of efficiency based on a previous paper by Strogartz [3]. Anyways, the definition of efficiency seems to be pretty standard.

In other fields that deal with networks, they tend to talk/measure robustness and resilience of a network after nodes are deleted. I was surprised to see that Crossly et. al had decided to compute graph efficiency after carrying out the targeted and targeted attack instead of computing robustness since studies on the former are far more common. So you may find these last two concepts pretty interesting... references [4] and [5] are good for the definition of robustness. I don't have any paper specifically for the definition of resilience in single graphs, but I've seen it mentioned in other studies.

References:

1. Latora V1, Marchiori M; Efficient behavior of small-world networks, Phys Rev Lett. 2001 Nov 5
2. Crossley et al; The hubs of the human connectome are generally implicated in the anatomy of brain disorders; Brain, 2014
3. D.J. Watts, S.H. Strogatz, Nature 393, 440 (1998)
4. Ellens, W; Kooij, R.E.; Graph measures and network robustness; 2013; arXiv preprint arXiv: 1311.5064
5. Larocca, Sarah; Guikema, Seth; Characterizing and Predicting the Robustness of Power-law Networks; 2013

[SandyaS72]

In things like transportation networks, cost is actually a very concrete measurable thing that factors in to efficiency (based on total length of roads built and resources needed for maintenance, etc) There's also some concept of speed and traffic that's pretty measurable in transportation networks that also must play a role. I wonder what "efficiency" would mean for a social network... maybe something along the lines of emergency phone trees?

[whock]

If we're talking about efficiency then I think flow is important, which @SandyaS72 gets at by mentioning traffic and speed. It seems like there is a relationship between static features like, e.g., path length between nodes and the traffic between them given a certain amount of traffic (i.e. shorter path, more traffic given same flow). But how do path measures, flow, and efficiency all interrelate as free parameters?