Re: number of Trangles in a graph-network
- To: mathgroup at smc.vnet.net
- Subject: [mg99599] Re: number of Trangles in a graph-network
- From: Peter Pein <petsie at dordos.net>
- Date: Fri, 8 May 2009 00:21:07 -0400 (EDT)
- References: <gtefaf$197$1@smc.vnet.net> <gtnk4g$3m4$1@smc.vnet.net> <gtrkpm$1d7$1@smc.vnet.net>
Peter Pein schrieb:
>
> Hi Luca,
>
> sometimes it seems I'm sitting on my eyes ...
>
indeed ... :(
> Here is a natural and really speedy way to get the desired result:
>
> SeedRandom[123];
> rg=RandomGraph[100,2/3];
>
> this is my last vesion:
>
> countTriangles[rg]//AbsoluteTiming
> {24.137618,49063}
>
> And the trace of the third power of the adjacency counts every triangle six
> times (abc,bca,cab,cba,acb,bac):
>
> Tr[MatrixPower[ToAdjacencyMatrix[rg],3]]/6//AbsoluteTiming
> {0.201834,49063}
>
>
> Peter
>
a (hopefully) last comment:There should be the option Type->Simple in the call
to To AdjacencyMatrix to avoid problems with 1- and 2-gons inside the graph
(shame on me).
Tr[MatrixPower[ToAdjacencyMatrix[rg,Type->Simple],3]]/6
should give correct results.
sorry for being too vague,
Peter