[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## [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!]

**[igraph] Adding two functions to igraph?**,
*Gang Su* **<=**