Re: number of Trangles in a graph-network

*To*: mathgroup at smc.vnet.net*Subject*: [mg99446] Re: number of Trangles in a graph-network*From*: Peter Pein <petsie at dordos.net>*Date*: Wed, 6 May 2009 05:21:08 -0400 (EDT)*References*: <gtefaf$197$1@smc.vnet.net> <gtnk4g$3m4$1@smc.vnet.net>

Peter Pein schrieb: > Luca Cinacchio schrieb: >> Greetings, >> >> having a graph (network, i.e. one created with RandomGraph) wich can have >> not connected nodes, I would like to count the total number of triangles >> inside the graph. >> I gave a look to Combinatorica and its related book by Pemmaraju Skiena, >> but I did'nt find any solution (maybe I am wrong). Do you know if there is >> a easy way to answer this problem with Mathematica and/or Combinatorica? >> Thanks in advance. >> > > It seems I'm writing too fast today :( > > I've got a slightly faster method: > > In[2]:= SeedRandom[123]; > rg=RandomGraph[32,1/2]; > In[4]:= (* this is from my 1st posting *) > Timing@Total[ReplaceList[rg[[1]],{___,{{a_,b_}},___,{{a_,c_}},___,{{b_,c_}},___}:>1]] > Out[4]= {5.98437,573} > > and faster but a little bit more brain-twisting: > > In[5]:= > countTriangles[g_Graph]:=Total@ReplaceList[g[[1]],{___,{{a_,b_}},r___/;Length[{r}]>1}:>Count[Split[Sort[Reverse/@Flatten[{r},1]],#1[[1]]===#2[[1]]&][[All,All,2]],{___,a,___,b,___}]] > In[6]:= Timing@countTriangles[rg] > Out[6]= {0.100006,573} > > don't try this with my first method: > > In[7]:= Timing[countTriangles[RandomGraph[100,2/3]]] > Out[7]= {16.705,45453} > > > Cheers, > Peter > Hi Luca, sometimes it seems I'm sitting on my eyes ... 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