Re: [igraph] Bridges between clusters

[Gábor Csárdi]

How about using this paper by our own Dr Nepusz? :)
http://arxiv.org/abs/0707.1646

Gabor

On Tue, Jun 24, 2014 at 5:24 AM, Stephan Schlögl
<address@hidden> wrote:
> Hello all,
> I'm doing sna on a network of Twitter users and the follower relations
> between them (using igraph for R). The network reveals clusters that can be
> easily explained by country or at least the language they use.
> I'm interested in the users who connect those clusters and looking for a
> metric that can find them. As for now I've been thinking of two approaches:
>
> Betweenness centrality
> BC somehow represents the concept of "bridges" I am looking for. Since my
> interest lies especially in the bridges between clusters I'd just base this
> calculation on the paths between clusters. e.g. If users A and B are part of
> cluster 1 and C and D part of Cluster 2, I'd compute the shortest paths for
> A-C, A-D, B-C,B-D but not A-B,C-D. I thought this would reduce number of
> paths considerably and make BC feasible for the network (IGRAPH DNW- 11206
> 1991845 --). Some simple estimations show that it does not. It would still
> take about half a year to compute that.
>
> Modularity on the level of vertices
> I understand that modularity is a metric for graphs and their partitions as
> a whole. But can it be used for individual nodes anyway? The "fraction of
> edges" within a cluster could be based on the neighborhood of each
> individual node "minus the expected value of the same quantity in a network
> with the same community divisions but random connections between the
> vertices" (Newman/Girvan 2004). A low modularity on node level would then
> mean that the node is some sort of bridge and nodes with high modularity are
> the least "cosmopolitan" ones.
>
> So, here are my questions:
> Do you think one of these approaches measures what I'm looking for
> (Bridges)?
> Are there other metrics I could use for this?
> Is modularity on the level of nodes possible or even already implemented in
> igraph?
> If the modularity on the level of nodes is doable but not implemented, how
> is the "expected value [..] in a network of with the same community
> divisions but random connections" to be computed for specific nodes.
>
>
> thank you for your help and the great piece of software you are developing!
>
> Beste regards,
> stephan
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help