[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## [igraph] Bridges between clusters

**From**: |
Stephan Schlögl |

**Subject**: |
[igraph] Bridges between clusters |

**Date**: |
Tue, 24 Jun 2014 11:24:47 +0200 |

**User-agent**: |
Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.5.0 |

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] Bridges between clusters**,
*Stephan Schlögl* **<=**