For everyone like me who didn't understand the difference between an individual in a high k-shell and a hub: http://en.wikipedia.org/wiki/K-core clarifies it nicely. (it didn't help for searching that core and shell got interchanged :))
That is, you can be a hub in a low k-shell, if say, you live in a town where everyone knows everyone but only the mailman ever leaves town.
Edit: in other words, this says that it's not about how many people you know, but how many highly-connected people you know. That's exactly what is usually informally meant by "well-connected".
Figure 1d in the linked-to paper illustrates the difference between high k-shell and high k nicely.
To quote from the paper (where k = # of edges a node has): "We start by removing all nodes with degree k = 1. After removing all
the nodes with k = 1, some nodes may be left with one link, so we continue pruning the
system iteratively until there is no node left with k = 1 in the network. The removed nodes,
along with the corresponding links, form a k-shell with index kS = 1. In a similar fashion,
we iteratively remove the next k-shell, kS = 2, and continue removing higher k-shells until
all nodes are removed. As a result, each node is associated with a unique kS index, and the
network can be viewed as the union of all k-shells."
Facebook and other large online networks should make an app with such interesting profile & network analysis data. Since it is available only to individuals they won't be letting too much out anyway they are still the gold mine of the data.
> It's easy to imagine that because the links that form
between various individuals in a society are not governed
by any overarching rules, they must have a random
structure.
I don't find that easy to imagine at all. Social systems are full of rules.
That is, you can be a hub in a low k-shell, if say, you live in a town where everyone knows everyone but only the mailman ever leaves town.
Edit: in other words, this says that it's not about how many people you know, but how many highly-connected people you know. That's exactly what is usually informally meant by "well-connected".