***** To join INSNA, visit http://www.insna.org *****
I don't have a satisfactory answer to your question but as a matter of
fact I was just reading yesterday an old paper on cost-minimal trees
in a restricted class of graphs, DAGs with a unique source, that might
2011/10/5 Christophe Prieur <[log in to unmask]>:
> ***** To join INSNA, visit http://www.insna.org *****
> Hi Socnet,
> Does anybody have any idea of what happens when one computes a minimum spanning tree in terms of betweenness?
> I guess this has been tried in many variations on many kinds of networks, including social ones.
> [Barthélemy & Flammini, 2006] build different kinds of trees on what they call traffic networks, trading off between betweenness and geographic distance.
> It is related to MST and betweenness but betweenness is recomputed at each step of the building process. And the graphs are generated, not empirical.
> [Newman, 2004]'s community detection algorithm actually builds a spanning tree with a betweenness-greedy algorithm.
> The result however is not necessarily the tree whose total weights are the highest in terms of betweenness. But i think it would be interesting to compare in which cases it differs much. And it's likely somebody has had the same idea during the past decade :)
> Now would it have some relevance to, unlike Newan, build a spanning tree whose total weights are not the highest but the lowest?
> Taking the highest betweenness as the biggest branches as does Newman is logical and suggests that low betweenness means proximity, which makes sense.
> Maybe doing the contrary is just pointless. Maybe not?
> If someone has ideas or refs, i'd be glad to hear.
> Christophe Prieur, [log in to unmask]
> Liafa, Université Paris-Diderot http://liafa.fr/~prieur/
> [user experience research, social networks, (large) graph algorithms]
> SOCNET is a service of INSNA, the professional association for social
> network researchers (http://www.insna.org). To unsubscribe, send
> an email message to [log in to unmask] containing the line
> UNSUBSCRIBE SOCNET in the body of the message.
SOCNET is a service of INSNA, the professional association for social
network researchers (http://www.insna.org). To unsubscribe, send
an email message to [log in to unmask] containing the line
UNSUBSCRIBE SOCNET in the body of the message.