Print

Print


Dear Ed,

Yes, you can calculate precisely the thing you describe, and it does
indeed work very well as a way of finding clusters in many networks.
The only catch is that you need to recompute betweennesses for edges
after each one is removed, otherwise the algorithm has some nasty
pathologies and often produces garbage.  The technique is described
in detail in a paper by Michelle Girvan and myself, which has not
appeared in print yet, but you can find it online here:

  http://arxiv.org/abs/cond-mat/0112110

(I guess you missed Michelle's talk about this work in New Orleans -
see what you miss if you leave before the end.)

Best wishes,
Mark.

--
Prof. M. E. J. Newman
Santa Fe Institute
Santa Fe, New Mexico



Ed Vielmetti wrote:
>
> I'm experimenting with locating clusters in a network and
> analyzing a structure for fragility by removing links between
> pairs of nodes that each have high betweenness.  The algorithm
> is pretty easy; look at the list of nodes ranked by betweenness,
> determine if the top two nodes have a link, if so snip it; if
> not, search iteratively through the list for the pair of links
> with the highest combination.
>
> Is there any standard metric that computes link centrality
> directly?  (A reference would be good.)  Intuitively it would
> seem to be the "path that's in the most geodesics in the
> network", and so it should be just about as hard to compute as
> node centrality.  Google on "link centrality" turns up nothing.
>
> The motivation for thinking of links as items in their own right
> is simply that from telecommunications networks, where the
> circuit between two devices is the source of at least as much
> cause for analysis as the endpoints.