Re: [igraph] Triad Census -- 003 Counts

[Tamas Nepusz]

Hi Wojciech,

> I'm using triad.census() to test this, as it is my understanding that if 
> every node keeps its in- and out-degrees constant, then (1) the degree 
> distributions will remain the same, and (2) the number of isolates will also 
> remain the same.
So far, so good :)

> As such, running a triad.census() on the original graph and a random 
> configuration model based on the original graph should yield the same count 
> for the 003 triad.
I think this is the point where you are wrong. Sure, isolates will remain 
isolates and as such, every single empty triad that consisted of three isolates 
will remain an empty triad. However, there could be other empty triads that 
consist of vertices with non-zero in- or out-degrees as long as the three 
vertices in the triad do not have edges between themselves, and there is no 
guarantee that such triads will be conserved across all graphs with the same 
in- and out-degree distribution. E.g., consider a directed ring graph of 10 
nodes where the ring is traversable in only one direction. This ring graph will 
have 50 empty triangles, and each vertex has in-degree and out-degree 1. Now, 
consider a graph with 10 nodes where node 2*k and node 2*k+1 are connected with 
two mutual edges (back and forth) for k=0,1,2,3 and 4. The degree distribution 
is the same, but the number of empty triangles is 80 (I can choose from 10 
possibilities for the first vertex, 8 possibilities for the second, 6 
possibilities for the third, but since every empty triad is counted six times 
this way, I have to divide the result by 6, hence the result is 80).

-- 
Tamas