Parameter off by one in dorogovtsev_goltsev_mendes_graph

[dfacoet]

Current Behavior

The parameter n of dorogovtsev_goltsev_mendes_graph is off by one. According to the docs and the original paper,

for a given n: - Total number of nodes = 3 * (3**n + 1) / 2 - Total number of edges = 3 ** (n + 1)

However that's not the case, e.g.

[len(nx.dorogovtsev_goltsev_mendes_graph(i).nodes) for i in range(4)]
# Output: [2, 3, 6, 15]

[len(nx.dorogovtsev_goltsev_mendes_graph(i).edges) for i in range(4)]
# Output: [1, 3, 9, 27]

instead of [3, 6, 15, 42] and [3, 9, 27, 81] respectively.

Expected Behavior

dorogovtsev_goltsev_mendes_graph(n) should return what is currently returned by dorogovtsev_goltsev_mendes_graph(n+1), as claimed in the docs. n=-1 should be a valid value (as in the paper).

[len(nx.dorogovtsev_goltsev_mendes_graph(i).nodes) for i in range(4)]
# Output: [3, 6, 15, 42]


### Environment

<!--- Please provide details about your local environment -->

Python version: 3.12
NetworkX version: 3.3

[rossbar]

Thanks for raising @dfacoet - I think the crux of the issue is the interpretation of n, which is different than t in the paper. Full disclosure: I added these docs back in #6450 based on my interpretation of the arXiv paper in the context of the existing implementation.

The paper does indeed make reference to t = -1 (this is probably most clearly depicted in figure 1) which I interpreted as the initial condition. Essentially, n represents the "generation", i.e. the number of transitions between states, whereas t from the paper is used to denote the states themselves. So n=0 represents "no transitions", meaning you are at the initial condition, denoted by the paper as t = -1. In other words, the current interpretation is: "what is the graph that results after n steps of the DGM procedure have been applied". I agree that this could be made more explicit in the docstring.

Note that the docs were added to explain the current implementation ex post facto, which is >19 years old(!) and predates the project's migration to github.

IMV this is a documentation issue - the docs should be expanded to clearly explain the difference between the graph state (which the paper denotes with "time step", t) and the "generation number", n, used in the function.

[Peiffap]

I see your point @rossbar; the original implementation clearly wasn't an oversight; it just assigned a different meaning to the generation parameter. From a quick Google search, it appears that Wolfram MathWorld uses the same parameter as the current implementation, i.e. starting at n = 0. GitHub also finds about 4.1k matches for "dorogovtsev_goltsev_mendes_graph," which makes me hesitant to push a breaking change.

I agree that the documentation should still explicitly mention this difference (and that the formulas for number of edges and nodes should be corrected, obviously). If this sounds good to everyone, I'll update #7473 accordingly.

[dschult]

You might not get notified when people give thumbs up! to your comment, so I'll post that there are 3 thumbs up for @Peiffap suggestion to update the PR accordingly. :) Thanks!