[igraph] RE: A measure of closeness

[David Edwards]

Dear all

I have a large undirected graph for which the nodes fall into a number of 
classes. I would like to know whether the nodes in each class tend to clump - 
to be close to each other. What would be a good measure of 'closeness'? If it 
could be calculated efficiently then I could compare the observed value with 
values obtained by permuting the class assignments.

Does anyone have a suggestion? Is this a known problem - if so, excuse my 
ignorance.


Med venlig hilsen / Regards 
David Edwards



-----Original Message-----
From: address@hidden [mailto:address@hidden On Behalf Of address@hidden
Sent: Wednesday, February 10, 2010 6:02 PM
To: address@hidden
Subject: igraph-help Digest, Vol 43, Issue 8

Send igraph-help mailing list submissions to
        address@hidden

To subscribe or unsubscribe via the World Wide Web, visit
        http://lists.nongnu.org/mailman/listinfo/igraph-help
or, via email, send a message with subject or body 'help' to
        address@hidden

You can reach the person managing the list at
        address@hidden

When replying, please edit your Subject line so it is more specific than "Re: 
Contents of igraph-help digest..."


Today's Topics:

   1. Visiting NYC/Boston (not entirely spam) (G?bor Cs?rdi)
   2. Re: a few questions about saving and plotting a 50k nodes
      network (Tamas Nepusz)
   3. Re: Missing packages on the website (G?bor Cs?rdi)
   4. community detection (zhengjun chen)
   5. Betweennes centrality (maximum and normalization) (Stefan Kroeger)
   6. Re: Betweennes centrality (maximum and normalization)
      (G?bor Cs?rdi)
   7. Re: Betweennes centrality (maximum and normalization)
      (Colin Garroway)


----------------------------------------------------------------------

Message: 1
Date: Wed, 10 Feb 2010 10:33:48 +0100
From: G?bor Cs?rdi <address@hidden>
Subject: [igraph] Visiting NYC/Boston (not entirely spam)
To: Help for igraph users <address@hidden>
Message-ID:
        <address@hidden>
Content-Type: text/plain; charset=ISO-8859-1

Dear All,

I'll be in New York City and/or Boston on 22-23 March this year, so if somebody 
from NYC/Boston fancies having a chat about igraph/R/networks/whatever, 
possibly together with a coffee/beer/tee/whatever, then please let me know, not 
on the mailing list, but in private.

Thanks! Best,
Gabor

-- 
Gabor Csardi <address@hidden>     UNIL DGM




------------------------------

Message: 2
Date: Wed, 10 Feb 2010 13:45:43 +0000
From: Tamas Nepusz <address@hidden>
Subject: Re: [igraph] a few questions about saving and plotting a 50k
        nodes   network
To: Help for igraph users <address@hidden>
Message-ID: <address@hidden>
Content-Type: text/plain; charset=us-ascii

Hi Yannick,

> I'm currently analysing this graph (with R) :
> [...]
> First, is it a good move to save everything as graph attributes as above ?
I don't think you'll do any harm if you do that. If it fits into the memory of 
your computer, then why not.

> > plot(g.sw.gcc)
> Erreur : impossible d'allouer un vecteur de taille 261.5 Mo [...] What 
> is wrong ? Is this graph too big ?
Probably yes. I have never tried plotting a graph of this size using R
-- chances are that you would be getting an intangible mess of edges anyway, no 
matter how good the layout is. Note that it doesn't really matter how large 
your graph is when you save it, as R might be allocating several auxiliary data 
structures when plotting the graph itself, and these may exceed the memory 
limits. I don't know how plotting in R works and what's going on behind the 
scenes, but my impression is that this simply won't work in R (or any other 
general purpose graph drawing package).

Once, when I had to plot a very large graph for illustration purposes (~70K 
vertices, ~500K edges), I came up with a Python script that drew the graph 
itself based on a pre-calculated layout using Python's bindings to the Cairo 
library.

If I were you and I really needed a visualisation of the graph, I would try 
plotting the graph without the edges first. In other words, create an empty 
graph with the same number of vertices and plot that, using your precalculated 
DrL layout. If R fails to do that, maybe GraphViz can 
(http://www.graphviz.org), but I don't know how to pass a predefined layout to 
GraphViz, or whether it's even possible or not.

> Thirdly, do you have any recommendations, when using 
> closeness.estimate or betweenness.estimate, in the choice of cutoffs ?
I'm not aware of such recommendations in the literature.

--
Tamas




------------------------------

Message: 3
Date: Wed, 10 Feb 2010 16:16:40 +0100
From: G?bor Cs?rdi <address@hidden>
Subject: Re: [igraph] Missing packages on the website
To: Help for igraph users <address@hidden>
Message-ID:
        <address@hidden>
Content-Type: text/plain; charset=ISO-8859-1

On Tue, Feb 9, 2010 at 12:46 AM, Tamas Nepusz <address@hidden> wrote:
>> Ahh...that would mean that my c compiling didn't work or at least
>> wasn't installed in the right place. So instead of bzr, I took the
>> latest build from googlecode (latest c source)
> ...which seems to imply that the nightly builds of the C library are not 
> being updated properly anymore. The last nightly build was uploaded on the 
> 15th of January, but I'm 100% sure that there were changes in the C core 
> since then.
>
> Now, the thing is that the Python nightlies are uploaded from a different 
> computer (my desktop machine at the university) than the C and R nightlies 
> (Gabor's machine somewhere in Switzerland), and it seems that the latter one 
> is b0rked. Gabor, can you check why the C nightlies are not uploaded properly 
> anymore?
[...]

It was a scheduled downtime, only a bit longer than expected, because
the admin had to search for a new place for the machine. Now it is
back online.

Best,
Gabor

-- 
Gabor Csardi <address@hidden>     UNIL DGM




------------------------------

Message: 4
Date: Wed, 10 Feb 2010 10:31:02 -0500
From: zhengjun chen <address@hidden>
Subject: [igraph] community detection
To: Help for igraph users <address@hidden>
Message-ID:
        <address@hidden>
Content-Type: text/plain; charset="iso-8859-1"

Hi,

I run "fastgreedy" community detection algorithm. I get the "merges" and
"modularity".
Then I use igraph_community_to_membership () to create a membership vector
from a community structure dendrogram.
My question is how to fill the parameter steps in this function. Right now I
use the value corresponding largest modularity.
I find that there are several largest modularity values in my case. In other
words, several steps have the same modularity.
They do not have the same resulting membership. So, which steps I should
choose?

-- 
Thanks
zhengjun
-------------- next part --------------
An HTML attachment was scrubbed...
URL: 
http://lists.gnu.org/pipermail/igraph-help/attachments/20100210/61671973/attachment.html

------------------------------

Message: 5
Date: Wed, 10 Feb 2010 17:05:38 +0100
From: Stefan Kroeger <address@hidden>
Subject: [igraph] Betweennes centrality (maximum and normalization)
To: Help for igraph users <address@hidden>
Message-ID: <address@hidden>
Content-Type: text/plain; charset=ISO-8859-1

Hi,

I hope it's okay to ask a pretty special question to betweenes
centrality (BC) and not directly related to igraph.

(mention: I deal with the node-related BC in undirected graphs.)

my two problems/questions are:
(i) Is the highest measure BC of network, also the theoretical hightest
reachable (maximum) BC for the graph?

(ii) Is there a way to normalize the betweennes centrality measures to
be able to compare between different graph?


thanks a lot
Stefan




------------------------------

Message: 6
Date: Wed, 10 Feb 2010 17:12:39 +0100
From: G?bor Cs?rdi <address@hidden>
Subject: Re: [igraph] Betweennes centrality (maximum and
        normalization)
To: address@hidden, Help for igraph users <address@hidden>
Message-ID:
        <address@hidden>
Content-Type: text/plain; charset=ISO-8859-1

Stefan, I am not sure that I understand your questions correctly, but
I think Freeman's paper might answer them:

Centrality in social networks conceptual clarification
Linton C. Freeman
Social Networks, 1979

Gabor

ps. google for it to get a PDF if you don't have sciencedirect access

On Wed, Feb 10, 2010 at 5:05 PM, Stefan Kroeger <address@hidden> wrote:
> Hi,
>
> I hope it's okay to ask a pretty special question to betweenes
> centrality (BC) and not directly related to igraph.
>
> (mention: I deal with the node-related BC in undirected graphs.)
>
> my two problems/questions are:
> (i) Is the highest measure BC of network, also the theoretical hightest
> reachable (maximum) BC for the graph?
>
> (ii) Is there a way to normalize the betweennes centrality measures to
> be able to compare between different graph?
>
>
> thanks a lot
> Stefan
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>



-- 
Gabor Csardi <address@hidden>     UNIL DGM




------------------------------

Message: 7
Date: Wed, 10 Feb 2010 11:19:31 -0500
From: Colin Garroway <address@hidden>
Subject: Re: [igraph] Betweennes centrality (maximum and
        normalization)
To: Help for igraph users <address@hidden>
Message-ID:
        <address@hidden>
Content-Type: text/plain; charset="iso-8859-1"

Maybe something like this for normalization in R?  From the R recipes on the
igraph wiki (http://igraph.wikidot.com/r-recipes#toc1).

centrality.norm<-function(graph,type=c("degree","closeness","betweenness"),centralization=FALSE)
{
    result<-NA
    g<-graph
    cent<-centralization
    if (!is.igraph(g)) {stop("Not a graph object")}
    if (type[[1]] == "degree") {
        if (!cent) result <- degree(g)/(vcount(g)-1)
        else result <-
(sum(max(degree(g))-degree(g)))/((vcount(g)-1)*(vcount(g)-2))}
    else if (type[[1]] == "betweenness") {
        temp <- 2*betweenness(g)/((vcount(g)-1)*(vcount(g)-2))
        if (!cent) result <- temp
        else  result <- sum(max(temp)-temp)/(vcount(g)-1)}
    else if (type[[1]] == "closeness") {
        if (!cent) result <- closeness(g)
        else result <-
(2*vcount(g)-3)*(sum(max(closeness(g))-closeness(g)))/((vcount(g)-1)*(vcount(g)-2))}
    else {stop("this type is unavailable or mispelled")}
    return(result)
}


Colin



On 10 February 2010 11:12, G?bor Cs?rdi <address@hidden> wrote:

> Stefan, I am not sure that I understand your questions correctly, but
> I think Freeman's paper might answer them:
>
> Centrality in social networks conceptual clarification
> Linton C. Freeman
> Social Networks, 1979
>
> Gabor
>
> ps. google for it to get a PDF if you don't have sciencedirect access
>
> On Wed, Feb 10, 2010 at 5:05 PM, Stefan Kroeger <address@hidden> wrote:
> > Hi,
> >
> > I hope it's okay to ask a pretty special question to betweenes
> > centrality (BC) and not directly related to igraph.
> >
> > (mention: I deal with the node-related BC in undirected graphs.)
> >
> > my two problems/questions are:
> > (i) Is the highest measure BC of network, also the theoretical hightest
> > reachable (maximum) BC for the graph?
> >
> > (ii) Is there a way to normalize the betweennes centrality measures to
> > be able to compare between different graph?
> >
> >
> > thanks a lot
> > Stefan
> >
> >
> > _______________________________________________
> > igraph-help mailing list
> > address@hidden
> > http://lists.nongnu.org/mailman/listinfo/igraph-help
> >
>
>
>
> --
> Gabor Csardi <address@hidden>     UNIL DGM
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>



-- 
Colin Garroway (PhD candidate)
Wildlife Research and Development Section
Ontario Ministry of Natural Resources
Trent University, DNA Building
2140 East Bank Drive
Peterborough, ON, K9J 7B8
Canada
http://sites.google.com/site/colingarroway2/home
-------------- next part --------------
An HTML attachment was scrubbed...
URL: 
http://lists.gnu.org/pipermail/igraph-help/attachments/20100210/186567f8/attachment.html

------------------------------

_______________________________________________
igraph-help mailing list
address@hidden
http://lists.nongnu.org/mailman/listinfo/igraph-help


End of igraph-help Digest, Vol 43, Issue 8
******************************************