Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2009

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: Reading csv with ;
  • Next by Date: Re: Some function like Position[] but uses criteria, not
  • Previous by thread: Re: number of Trangles in a graph-network
  • Next by thread: Re: number of Trangles in a graph-network