igraph-help
[Top][All Lists]

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

 From: Gábor Csárdi Subject: Re: [igraph] weak ties / structural holes in Igraph Date: Mon, 26 Sep 2011 11:43:15 -0400

```Isn't the simplest to calculate the local transitivity of the
vertices? This is implemented and fast, and for each vertex gives the
density of its ego network, right?

Best,
Gabor

On Mon, Sep 26, 2011 at 4:42 AM, Tamas Nepusz <address@hidden> wrote:
> 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
>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>>
>
> _______________________________________________
> igraph-help mailing list
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>

--
Gabor Csardi <address@hidden>     MTA KFKI RMKI

```