 |
 |
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.