Converting Combinatorica graph to standard graph type

Question

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?

Answer 1

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

TriangleCount[g_Graph] := Tr[MatrixPower[AdjacencyMatrix[g], 3]]/6

Answer 2

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.