Re: [igraph] key players in networks

[Gabor Csardi]

Ok, I read the paper, the measures are not very difficult,
although optimizing them is a different question.
Here is how to calculate DF and DR:

df <- function(g) {
  n <- vcount(g)
  spmat <- shortest.paths(g)
  spmat[spmat==n] <- Inf
  dists <- spmat[upper.tri(spmat)]
  1-2*sum(1/dists)/n/(n-1)
}

dr <- function(g, k) {
  n <- vcount(g)
  spmat <- shortest.paths(g, k)
  dkj <- apply(spmat, 2, min)
  dkj <- dkj[ dkj != 0 ]
  dkj[dkj==n] <- Inf
  sum(1/dkj)/n
}

df works well for the two toy graphs:

g1 <- graph.full(5) %du% graph.full(5)
g2 <- graph.ring(5, circ=FALSE) %du% graph.ring(5, circ=FALSE)

I couldn't try them for the two real networks in the paper, because
i couldn't find the data, for the second one even the cited reference 
is missing from the bibliography. 

Now you can try to make up some optimization function using 
'delete.vertices' from igraph and the 'df' and 'dr' functions 
defined as above. If k is small (2-4) then you can brute force 
all cases, for larger k and larger networks a more sophisticated 
algorithm might be needed. Unfortunately i don't know any R 
functions doing 'subgraph optimization' like this.

Best,
Gabor

On Thu, Sep 13, 2007 at 10:55:59AM +0200, Gabor Csardi wrote:
> Simone,
> 
> hmmm, igraph has many functions for centrality, some simple ones like
> degree and closeness and some more sophisticated like page rank and
> Burt's constraints. 
> 
> The new measures in the mentioned paper are not included yet.
> I'll include them if the interest/work ratio is above my threshold,
> thanks for the reference. 
> 
> But be aware that these measures work for you only if you're
> interested in exactly the same functional roles they were developed
> for. Ie. if you're interested in the vertices you'll end up most of
> the time by randomly walking on the network then page rank is better,
> etc. (if my (mis)conceptions about page rank are right).
> 
> Gabor
> 
> On Tue, Sep 11, 2007 at 01:57:58PM +0200, Simone Gabbriellini wrote:
> > Hi all,
> > 
> > I need to identify key players in my networks..
> > I found some procedures by Borgatti, described in the article  
> > "Identifying sets of key players in a social network"..
> > 
> > does igraph already has a function to find key players in networks?
> > 
> > regards,
> > Simone
> > 
> > 
> > _______________________________________________
> > igraph-help mailing list
> > address@hidden
> > http://lists.nongnu.org/mailman/listinfo/igraph-help
> 
> -- 
> Csardi Gabor <address@hidden>    MTA RMKI, ELTE TTK
> 
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help

-- 
Csardi Gabor <address@hidden>    MTA RMKI, ELTE TTK