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

[Tamas Nepusz]

Hi Magnus,

The bottleneck in your code is most likely graph.neighborhood, which calls
subgraph() (well, igraph_subgraph in C) in the background. In igraph 0.5.x,
igraph_subgraph() copies the entire graph and deletes the vertices *not* in
the subgraph, which is pretty inefficient for large graphs. This has been
rectified in the development version already, but until then, you should
find an alternative solution that does not involve graph.neighborhood.

One thing that you could try is to derive ego.vcount from degree(g) since
the size of the first-order ego network is always one larger than the degree
of the central vertex. (Alternatively, you could use neighborhood.size).
ego.ecount is trickier, but you can try something like this (untested and
I'm not an expert in R):

neighborhood.ecount <- function(g, vertex) {
  neis <- neighbors(g, vertex, mode="all")
  neis <- c(neis, vertex)
  length(E(g) [ neis %--% neis ])
}

Applying this function to every element in the range 0:vcount(g)-1 should
then give you the number of edges in the ego network of each vertex.

Cheers,
T.

On 09/23/2011 08:13 PM, Magnus Thor Torfason wrote:
> 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)
> }
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>