igraph-help
[Top][All Lists]

## [igraph] Adding two functions to igraph?

 From: Gang Su Subject: [igraph] Adding two functions to igraph? Date: Thu, 08 May 2008 16:59:09 -0400 User-agent: Thunderbird 2.0.0.14 (Windows/20080421)

```Dear Developers:

It's me again. I read a paper the other day:
research.yahoo.com/files/w_s_NATURE.pdf
and a newman's paper on random graph.

```
In this paper they proposed 2 feature values that can distinguish a random graph from a real world one:
```Clustering coefficient and Characteristic edge length.

```
I just tried on my real world data and Erdos.renyi random graph with same number of edges and nodes
```I wrote two functions (works, not optimal, no error handling):

cluster.coefficient <- function(g){
vs <- as.matrix(0:(vcount(g)-1));
return(mean(apply(vs, MARGIN=1,
function(x){
nei.vs <- neighbors(g, x);
#print(nei.vs);
g.s <- subgraph(g, nei.vs);
v.g.s <- vcount(g.s);
if(v.g.s > 1){
return(ecount(g.s)*2/(v.g.s*(v.g.s-1)));
}
else
{
```
#This needs to be taken care of; That is, how do we handle those with only 1 neighbor?'leaves'
```       return(0);
}
}
)));
}

characteristic.path.length <- function(g){
v.count <- vcount(g);
sum(shortest.paths(g))/(v.count*(v.count-1)*2);
};

```
For erdos.renyi random graph the cluster.coefficient ~ p so it's way smaller than real world graphs (unless the edge is really dense), same applies to the characteristic path length which is the avg path length connecting arbitrary node pairs. These functions may be very useful for graph analysis and i suggest to be incorporated.
```
Gang [Keep spamming igraph email list!]

```