Re: [igraph] weak ties / structural holes in Igraph

[Magnus Thor Torfason]

Hi Gabor and others,

It's an interesting thread, I've been doing some work using 
ego-network-type measures, including the constraint() measure.

An alternative to get at the aspect of the ego-network structure that 
constraint() measures is ego-network-density. It is in some ways more 
intuitive than the constraint people and some people prefer it. The 
other day I threw together a quick and dirty implementation of this 
function (see at the bottom of the mail). However, my implementation 
depends crucially on graph.neighborhood(), which did not work very well 
for my graph of several hundred thousand vertices.

So I wonder if there is an implementation available for this that allows 
me to calculate ego network density for the whole graph without 
requiring the generation of vcount(g) sub-graphs. I also wonder if I'm 
still correct in assuming that graph.neighborhood() is infeasible to use 
for me on a 100K node network?

Best,
Magnus

ps. Thanks again Gabor and Tamas, for igraph and your continued support 
of the program and this list.


########################
# Function to calculate ego network density
# Probably not the most efficient, and may not even
# be 100% correct. Caveat emptor.
########################
ego.density = function(g)
{
    l.ego.graphs              = graph.neighborhood(g,1)
    ego.ecount                = sapply(l.ego.graphs, ecount)
    ego.vcount                = sapply(l.ego.graphs, vcount)
    ego.friend.count          = ego.vcount - 1
    ego.friend.tie.count.max  = ego.friend.count*(ego.friend.count-1)/2
    ego.friend.tie.count.real = ego.ecount - ego.friend.count
    ego.density.result        =
             ego.friend.tie.count.real/ego.friend.tie.count.max
    return(ego.density.result)
}