[Top][All Lists]

[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,

reply via email to

[Prev in Thread] Current Thread [Next in Thread]