I'm reading graph theory and I found a concept named average path length. Basically, it is the average of all the shortest lengths between any two nodes of a graph. In case two nodes are not connected, the length between them is set to zero (i.e., $d(v_i, v_j) = 0$).
I find this definition not meaningful because a connected graph may have the average path length higher than an unconnected graph. Should the shortest distance between two unconnected nodes be set to a large value?
My questions are:
- Is there another definition of the average path length, or is the above definition correct?
- In determining whether a graph is a small world graph, should we take into account the average path length in case the graph is unconnected?
As you say, that definition doesn't make much sense: if you want to be able to get easily between nodes then having a pair of nodes which are inaccessible from each other is a bad thing, not a good thing.
A more sensible (and I would have thought more usual) definition is that $d(v_i,v_j)=\infty$ if there is no path from $v_i$ to $v_j$. This means any disconnected graph has infinite average path length. When faced with a disconnected graph, it therefore makes more sense to view it as a collection of different connected graphs and look at the average path length of the components. After all, if there is no connection between two parts of a network, what makes you think it is all the same network to start with?
A reference for this definition is here. Finding out which definition is more prevalent is likely to be difficult, since many of the papers that look at average path length work with networks which are known to be connected (for example, preferential attachment networks), and so they probably won't bother to specify what happens with unconnected ones.