1
$\begingroup$

I'm trying to count triangles in random d-regular graphs. Combinatorica has a function RegularGraph, which gives me the random graph and IGraphM has a function IGCliqueSizeCounts that'll count k-cliques in a graph.

So in theory, Needs["Combinatorica"]; Needs["IGraphM"]; IGCliqueSizeCounts[RegularGraph[d, n]][[3]] should be what I need. The only issue is that it seems as though RegularGraph is giving a graph type that IGCliqueSizeCounts doesn't recognize. Anyone know how to get around this?

$\endgroup$
1
  • $\begingroup$ Welcome to the Mathematica Stack Exchange. Which Mathematica version are you using? You can use $Version command to find out. $\endgroup$
    – Syed
    Commented Apr 13, 2022 at 14:50

2 Answers 2

2
$\begingroup$

To count the number of triangles in a WL Graph, you can use

TriangleCount[g_Graph] := Tr[MatrixPower[AdjacencyMatrix[g], 3]]/6
$\endgroup$
0
$\begingroup$

Beware that Combinatorica's RegularGraph does not sample regular graphs uniformly. This is stated in the Combinatorica Book which you should get if you use Combinatorica. The statistics of triangle counts you get this way will not be representative of the triangle counts of all $k$-regular graphs. To better understand why this sampling is not uniform, first see how it works (Combinatorica Book), then check the gentle introduction to this topic in this paper.

IGraph/M has functions which can be used for uniform sampling. Note that IGKRegularGame will again not sample uniformly. IGDegreeSequenceGame has one method that samples uniformly, namely "ConfigurationModelSimple". This is fast for small degrees (e.g. 3-regular), but quickly becomes unusably slow for larger ones.

Yet another way is to first generate one graph with the given degrees using IGRealizeDegreeSequence then reshuffle it using IGRewire. In the limit of an infinite number of reshuffling steps, this method samples uniformly. In practice, maybe 10 or more times the number of edges will be a good guideline for how many reshuffling steps to make. This method works reasonable fast for larger degrees as well.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.