I believe that the newman_watts_strogatz_graph function incorrectly implements this network model. In the current implementation, self-loops and multi-edges are not allowed. However the paper by Newman and Watts stated "we also explicitly allow there to be more than one bond between any two vertices, or a bond which connects a vertex to itself." The original contributor seems unsure by commenting "is that the correct NWS model?"
The problem seemingly comes from an incorrect citation. Right now the reference used is:
which in fact uses the original Watts-Strogatz model, not the Newman-Watts variant.
The correct citation in which the Newman-Watts variant was proposed should be:
Newman, M.E.J., Watts, D.J.: Scaling and percolation in the small-world network model. Phys.Rev. E60(6), 7332–7342 (1999). DOI 10.1103/PhysRevE.60.7332
The aforementioned citation is in section II, paragraph 4 of the latter.
I guess the confusion might have come from these papers having the same in-text citation due to the exact same author and year.
To make sure it's not a difference in naming convention, I looked at several publications that uses the Newman-Watts model and confirmed they all uses the version that allows self-loops and multi-edges. But I hope someone can look into the references and double check for me.
It would be easy to fix the code: when initializing the graph, set create_using to nx.multigraph(), and getting rid of the lines that rejects self-loops or multi-edges. I wrote the fixed code but I'm not sure how to upload it to the package, even after reading the contributor guide. (I'm a math student with no prior experience in large-scale collaborative development with git.) I wish someone can give me more instructions on that.
p.s. I recently implemented a generator for Klemm-Eguiluz networks. (ref: Klemm, Konstantin, and Victor M. Eguiluz. "Growing scale-free networks with small-world behavior." Physical Review E 65.5 (2002): 057102.) If I successfully figured out how to contribute via git I can share the code as a function under nx.generators.
Best,
Ming