Repository: networkx/networkx
Pull request: Add input validation to `non_randomness()` and clarify its behavior
Fixes #4115.

This PR does three related things:

1. It adds input validation for `k`, the number of communities, in `non_randomness()`. In particular, it raises a `ValueError` when `k` doesn't satisfy `1 <= k < n`. Tests for this scenario are also added.
2. It checks that the value of `p` computed can be interpreted as a probability, i.e. `0 < p < 1`. This avoids the mysterious failure in #4115 and [this SO question](https://stackoverflow.com/questions/71593402/calculating-non-randomness-with-networkx). The test from the issue was added to check this.
3. It improves (imo) the docstring, adding an example of this weird behavior for certain values of `k` and all-round making it more informative.

Problem statement:
non_randomness fail with ValueError: math domain error on simple network
The calculation of non_randomness fails with a simple network.

```python
import networkx as nx
g = nx.Graph()
g.add_edges_from([
    ('A', 'B'),
    ('B', 'C'),
    ('B', 'D'),
    ('D', 'E')
    ])
print(nx.algorithms.non_randomness(g))
```
throws:
```
.venv\lib\site-packages\networkx\algorithms\non_randomness.py in non_randomness(G, k)
     88 
     89     # eq. 4.5
---> 90     nr_rd = (nr - ((n - 2 * k) * p + k)) / math.sqrt(2 * k * p * (1 - p))
     91 
     92     return nr, nr_rd

ValueError: math domain error
```

Hints from issue discussion:
I get:
```
print(nx.non_randomness(g))                                                                                                        
(-1.847759065022571, -5.842436964513824)
```
I too get the correct result. What versions of nx and Python are you using @javieriserte ?
I'm using:
networkx==2.4 and python 3.7.2

I was looking into the code for the problem and i think i found it.

Consider the code below:
```python
import networkx as nx

# Works Fine !!
g = nx.Graph()
edges_case_1 = [
    ('A', 'B'),
    ('B', 'C'),
    ('B', 'D'),
    ('D', 'E')
    ]
g.add_edges_from(edges_case_1)
k = len(tuple(nx.community.label_propagation_communities(g)))
print("Case 1")
print(f"Number of comminities: {k}")
print(f"NonRandomness:{nx.algorithms.non_randomness(g)}")
print("\n")

# Fails !!
g = nx.Graph()
edges_case_2 = [
    ('A', 'B'),
    ('B', 'D'),
    ('B', 'C'),
    ('D', 'E')
]
g.add_edges_from(edges_case_2)
k = len(tuple(nx.community.label_propagation_communities(g)))
print("Case 1")
print(f"Number of comminities: {k}")
try:
    print(f"NonRandomness:{nx.algorithms.non_randomness(g)}")
except Exception as e:
    print(f"Fails with {e}")
```

I have two identical graphs, but the order of the edges is different when they are added to the graph.
For me, the first case is Ok, and the second one fails.

The code of non_randomness function tries to find communities in the graph. In the first case, one community is found, in the second case, two comunities are found. It uses label_propagation_communities function to do this. I don't know why this function gives two different results for the same graph. 

Later in the code the number of communities (k) is used to compute another value ```p = (2 * k * m) / (n * (n - k))``` (where n and m are the number of nodes and edges). And p is used inside a square root ```math.sqrt(2 * k * p * (1 - p))```. In the case that fails,
p is larger than 1 and (1-p) is negative, this makes the square root to be undefined.


The article [referenced in the docstring](https://epubs.siam.org/doi/10.1137/1.9781611972795.61) discusses this quantity in Theorem 1 where they show that a quantity follows a normal distribution in the limit k << n and n large.  So clearly, this case doesn't follow that.  Perhaps we should include a maximum limit on p (not 1, or we divide by 0 and have the same problem).  Or, we could raise an exception when the value is bigger than 1.  
What makes the most sense here?  
What does it mean to have an infinite nonrandomness?

The different results for different orders of the same graph must be due to a community algorithm that depends on ordering of edges/nodes. I haven't looked at this in this case yet. But many of those methods do depend on ordering. So I'm not so surprised.

Commit message: Punctuation and capitalization in docs

Patch to review:
diff --git a/doc/reference/algorithms/non_randomness.rst b/doc/reference/algorithms/non_randomness.rst
index 090707cdf19..79ac8d1a9e3 100644
--- a/doc/reference/algorithms/non_randomness.rst
+++ b/doc/reference/algorithms/non_randomness.rst
@@ -1,5 +1,5 @@
 **************
-non-randomness
+Non-randomness
 **************
 
 .. automodule:: networkx.algorithms.non_randomness
diff --git a/networkx/algorithms/non_randomness.py b/networkx/algorithms/non_randomness.py
index 13799115774..b5cd838fbdb 100644
--- a/networkx/algorithms/non_randomness.py
+++ b/networkx/algorithms/non_randomness.py
@@ -1,4 +1,4 @@
-r"""Computation of graph non-randomness"""
+r"""Computation of graph non-randomness."""
 
 import math
 
@@ -12,45 +12,56 @@
 @not_implemented_for("multigraph")
 @nx._dispatchable(edge_attrs="weight")
 def non_randomness(G, k=None, weight="weight"):
-    """Compute the non-randomness of graph G.
+    """Compute the non-randomness of graph `G`.
 
-    The first returned value nr is the sum of non-randomness values of all
+    The first value $R_G$ is the sum of non-randomness values of all
     edges within the graph (where the non-randomness of an edge tends to be
     small when the two nodes linked by that edge are from two different
     communities).
 
-    The second computed value nr_rd is a relative measure that indicates
-    to what extent graph G is different from random graphs in terms
-    of probability. When it is close to 0, the graph tends to be more
-    likely generated by an Erdos Renyi model.
+    The second value $R_G^*$ is a relative measure that indicates
+    to what extent `G` is different from a random graph in terms
+    of probability. The closer it is to 0, the higher the likelihood
+    the graph was generated by an Erdős--Rényi model.
 
     Parameters
     ----------
     G : NetworkX graph
-        Graph must be symmetric, connected, and without self-loops.
+        Graph must be undirected, connected, and without self-loops.
 
-    k : int
-        The number of communities in G.
-        If k is not set, the function will use a default community
-        detection algorithm to set it.
+    k : int or None, optional (default=None)
+        The number of communities in `G`.
+        If `k` is not set, the function uses a default community detection
+        algorithm (:func:`~networkx.algorithms.community.label_propagation_communities`)
+        to set it.
 
-    weight : string or None, optional (default=None)
+    weight : string or None, optional (default="weight")
         The name of an edge attribute that holds the numerical value used
-        as a weight. If None, then each edge has weight 1, i.e., the graph is
+        as a weight. If `None`, then each edge has weight 1, i.e., the graph is
         binary.
 
     Returns
     -------
-    non-randomness : (float, float) tuple
-        Non-randomness, Relative non-randomness w.r.t.
-        Erdos Renyi random graphs.
+    (float, float) tuple
+        The first value is $R_G$, the non-randomness of the graph,
+        the second is $R_G^*$, the relative non-randomness
+        w.r.t. the Erdős--Rényi model.
 
     Raises
     ------
+    NetworkXNotImplemented
+        If the input graph is directed or a multigraph.
+
     NetworkXException
-        if the input graph is not connected.
+        If the input graph is not connected.
+
     NetworkXError
-        if the input graph contains self-loops or if graph has no edges.
+        If the input graph contains self-loops or has no edges.
+
+    ValueError
+        If `k` is not in $\\{1, \\dots, n-1\\}$, where $n$ is the number of nodes,
+        or if `k` is such that the computed edge probability
+        $p = \\frac{2km}{n(n-k)}$ does not satisfy $0 < p < 1$.
 
     Examples
     --------
@@ -58,40 +69,93 @@ def non_randomness(G, k=None, weight="weight"):
     >>> nr, nr_rd = nx.non_randomness(G, 2)
     >>> nr, nr_rd = nx.non_randomness(G, 2, "weight")
 
+    When the number of communities `k` is not specified,
+    :func:`~networkx.algorithms.community.label_propagation_communities`
+    is used to compute it.
+    This algorithm can give different results depending on
+    the order of nodes and edges in the graph.
+    For example, while the following graphs are identical,
+    computing the non-randomness of each of them yields different results:
+
+    >>> G1, G2 = nx.Graph(), nx.Graph()
+    >>> G1.add_edges_from([(0, 1), (1, 2), (1, 3), (3, 4)])
+    >>> G2.add_edges_from([(0, 1), (1, 3), (1, 2), (3, 4)])
+    >>> [round(r, 6) for r in nx.non_randomness(G1)]
+    [-1.847759, -5.842437]
+    >>> [round(r, 6) for r in nx.non_randomness(G2)]
+    Traceback (most recent call last):
+     ...
+    ValueError: invalid number of communities for graph with 5 nodes and 4 edges: 2
+
+    This is because the community detection algorithm finds
+    1 community in ``G1`` and 2 communities in ``G2``.
+    This can be resolved by specifying the number of communities `k`:
+
+    >>> [round(r, 6) for r in nx.non_randomness(G2, k=1)]
+    [-1.847759, -5.842437]
+
     Notes
     -----
-    This computes Eq. (4.4) and (4.5) in Ref. [1]_.
-
-    If a weight field is passed, this algorithm will use the eigenvalues
-    of the weighted adjacency matrix to compute Eq. (4.4) and (4.5).
+    If a `weight` field is passed, this algorithm will use the eigenvalues
+    of the weighted adjacency matrix instead.
+
+    The output of this function corresponds to (4.4) and (4.5) in [1]_.
+    A lower value of $R^*_G$ indicates a more random graph;
+    one can think of $1 - \\Phi(R_G^*)$ as the similarity
+    between the graph and a random graph,
+    where $\\Phi(x)$ is the cumulative distribution function
+    of the standard normal distribution.
+
+    Theorem 2 in [2]_ states that for any graph $G$
+    with $n$ nodes, $m$ edges, and $k$ communities,
+    its non-randomness is bounded below by the non-randomness of an
+    $r$-regular graph (a graph where each node has degree $r$),
+    and bounded above by the non-randomness of an $l$-complete graph
+    (a graph where each community is a clique of $l$ nodes).
 
     References
     ----------
     .. [1] Xiaowei Ying and Xintao Wu,
            On Randomness Measures for Social Networks,
            SIAM International Conference on Data Mining. 2009
+           https://doi.org/10.1137/1.9781611972795.61
+    .. [2] Ying, Xiaowei & Wu, Leting & Wu, Xintao. (2012).
+           A Spectrum-Based Framework for Quantifying Randomness of Social Networks.
+           IEEE Transactions on Knowledge and Data Engineering 23(12):1842--1856.
+           https://dl.acm.org/doi/abs/10.1109/TKDE.2010.218
     """
     import numpy as np
 
     # corner case: graph has no edges
     if nx.is_empty(G):
-        raise nx.NetworkXError("non_randomness not applicable to empty graphs")
+        raise nx.NetworkXError("graph has no edges")
     if not nx.is_connected(G):
-        raise nx.NetworkXException("Non connected graph.")
+        raise nx.NetworkXException("graph is not connected")
     if len(list(nx.selfloop_edges(G))) > 0:
-        raise nx.NetworkXError("Graph must not contain self-loops")
+        raise nx.NetworkXError("graph contains self-loops")
+
+    n = G.number_of_nodes()
+    m = G.number_of_edges()
 
     if k is None:
         k = len(tuple(nx.community.label_propagation_communities(G)))
+    elif not 1 <= k < n:
+        err = f"invalid number of communities for graph with {n} nodes: {k}"
+        raise ValueError(err)
 
     # eq. 4.4
     eigenvalues = np.linalg.eigvals(nx.to_numpy_array(G, weight=weight))
     nr = float(np.real(np.sum(eigenvalues[:k])))
 
-    n = G.number_of_nodes()
-    m = G.number_of_edges()
     p = (2 * k * m) / (n * (n - k))
 
+    if not 0 < p < 1:
+        # See gh-4115
+        err = (
+            f"invalid number of communities for graph with {n} nodes and {m} edges: {k}"
+        )
+        raise ValueError(err)
+
     # eq. 4.5
     nr_rd = (nr - ((n - 2 * k) * p + k)) / math.sqrt(2 * k * p * (1 - p))
 
diff --git a/networkx/algorithms/tests/test_non_randomness.py b/networkx/algorithms/tests/test_non_randomness.py
index 2f495be28d5..6ec261d3de9 100644
--- a/networkx/algorithms/tests/test_non_randomness.py
+++ b/networkx/algorithms/tests/test_non_randomness.py
@@ -24,7 +24,7 @@ def test_non_randomness(k, weight, expected):
 def test_non_connected():
     G = nx.Graph([(1, 2)])
     G.add_node(3)
-    with pytest.raises(nx.NetworkXException, match="Non connected"):
+    with pytest.raises(nx.NetworkXException, match=r"not connected"):
         nx.non_randomness(G)
 
 
@@ -32,11 +32,24 @@ def test_self_loops():
     G = nx.Graph()
     G.add_edge(1, 2)
     G.add_edge(1, 1)
-    with pytest.raises(nx.NetworkXError, match="Graph must not contain self-loops"):
+    with pytest.raises(nx.NetworkXError, match=r"contains self-loops"):
         nx.non_randomness(G)
 
 
 def test_empty_graph():
     G = nx.empty_graph(1)
-    with pytest.raises(nx.NetworkXError, match=".*not applicable to empty graphs"):
+    with pytest.raises(nx.NetworkXError, match=r"has no edges"):
         nx.non_randomness(G)
+
+
+@pytest.mark.parametrize("k", [-1, 0, 3, 4])
+def test_k(k):
+    G = nx.path_graph(3)
+    with pytest.raises(ValueError, match=r"invalid.*graph with 3 nodes:"):
+        nx.non_randomness(G, k=k)
+
+
+def test_k_probability():
+    G = nx.Graph([(0, 1), (1, 3), (1, 2), (3, 4)])
+    with pytest.raises(ValueError, match=r"invalid.*graph with 5 nodes and 4 edges: 2"):
+        nx.non_randomness(G, k=2)


Code review comments:
diff_hunk: @@ -12,86 +12,150 @@
 @not_implemented_for("multigraph")
 @nx._dispatchable(edge_attrs="weight")
 def non_randomness(G, k=None, weight="weight"):
-    """Compute the non-randomness of graph G.
+    """Compute the non-randomness of graph `G`.
 
-    The first returned value nr is the sum of non-randomness values of all
+    The first value $R_G$ is the sum of non-randomness values of all
     edges within the graph (where the non-randomness of an edge tends to be
     small when the two nodes linked by that edge are from two different
     communities).
 
-    The second computed value nr_rd is a relative measure that indicates
-    to what extent graph G is different from random graphs in terms
-    of probability. When it is close to 0, the graph tends to be more
-    likely generated by an Erdos Renyi model.
+    The second value $R_G^*$ is a relative measure that indicates
+    to what extent `G` is different from a random graph in terms
+    of probability. The closer it is to 0, the higher the likelihood
+    the graph was generated by an Erdős--Rényi model.
 
     Parameters
     ----------
     G : NetworkX graph
-        Graph must be symmetric, connected, and without self-loops.
+        Graph must be undirected, connected, and without self-loops.
 
-    k : int
-        The number of communities in G.
-        If k is not set, the function will use a default community
-        detection algorithm to set it.
+    k : int or None, optional (default=None)
+        The number of communities in `G`.
+        If `k` is not set, the function uses a default community detection
+        algorithm (:func:`~networkx.algorithms.community.label_propagation_communities`)
+        to set it.
 
-    weight : string or None, optional (default=None)
+    weight : string or None, optional (default="weight")
         The name of an edge attribute that holds the numerical value used
-        as a weight. If None, then each edge has weight 1, i.e., the graph is
+        as a weight. If `None`, then each edge has weight 1, i.e., the graph is
         binary.
 
     Returns
     -------
-    non-randomness : (float, float) tuple
-        Non-randomness, Relative non-randomness w.r.t.
-        Erdos Renyi random graphs.
+    (float, float) tuple
+        The first value is $R_G$, the non-randomness of the graph,
+        the second is $R_G^*$, the relative non-randomness
+        w.r.t. the Erdős--Rényi model.
 
     Raises
     ------
+    NetworkXNotImplemented
+        If the input graph is directed or a multigraph.
+
     NetworkXException
-        if the input graph is not connected.
+        If the input graph is not connected.
+
     NetworkXError
-        if the input graph contains self-loops or if graph has no edges.
+        If the input graph contains self-loops or has no edges.
+
+    ValueError
+        If `k` is not in $\\{1, \\dots, n-1\\}$, where $n$ is the number of nodes,
+        or if `k` is such that the computed edge probability
+        $p = \\frac{2km}{n(n-k)}$ does not satisfy $0 < p < 1$.
 
     Examples
     --------
     >>> G = nx.karate_club_graph()
     >>> nr, nr_rd = nx.non_randomness(G, 2)
     >>> nr, nr_rd = nx.non_randomness(G, 2, "weight")
 
+    When the number of communities `k` is not specified,
+    :func:`~networkx.algorithms.community.label_propagation_communities`
+    is used to compute it.
+    This algorithm can give different results depending on
+    the order of nodes and edges in the graph.
+    For example, while the following graphs are identical,
+    computing the non-randomness of each of them yields different results:
+
+    >>> G1, G2 = nx.Graph(), nx.Graph()
+    >>> G1.add_edges_from([(0, 1), (1, 2), (1, 3), (3, 4)])
+    >>> G2.add_edges_from([(0, 1), (1, 3), (1, 2), (3, 4)])
+    >>> [round(r, 6) for r in nx.non_randomness(G1)]
+    [-1.847759, -5.842437]
+    >>> [round(r, 6) for r in nx.non_randomness(G2)]
+    Traceback (most recent call last):
+     ...
+    ValueError: invalid number of communities for graph with 5 nodes and 4 edges: 2
+
+    This is because the community detection algorithm finds
+    1 community in ``G1`` and 2 communities in ``G2``.
+    This can be resolved by specifying the number of communities `k`:
+
+    >>> [round(r, 6) for r in nx.non_randomness(G2, k=1)]
+    [-1.847759, -5.842437]
+
     Notes
     -----
-    This computes Eq. (4.4) and (4.5) in Ref. [1]_.
-
-    If a weight field is passed, this algorithm will use the eigenvalues
-    of the weighted adjacency matrix to compute Eq. (4.4) and (4.5).
+    If a `weight` field is passed, this algorithm will use the eigenvalues
+    of the weighted adjacency matrix instead.
+
+    The output of this function corresponds to (4.4) and (4.5) in [1]_.
+    A lower value of $R^*_G$ indicates a more random graph;
+    one can think of $1 - \\Phi(R_G^*)$ as the similarity
+    between the graph and a random graph,
+    where $\\Phi(x)$ is the cumulative distribution function
+    of the standard normal distribution.
+
+    Theorem 2 in [2]_ states that for any graph $G$
+    with $n$ nodes, $m$ edges, and $k$ communities,
+    its non-randomness is bounded below by the non-randomness of an
+    $r$-regular graph (a graph where each node has degree $r$),
+    and bounded above by the non-randomness of an $l$-complete graph
+    (a graph where each community is a clique of $l$ nodes).
 
     References
     ----------
     .. [1] Xiaowei Ying and Xintao Wu,
            On Randomness Measures for Social Networks,
            SIAM International Conference on Data Mining. 2009
+           https://doi.org/10.1137/1.9781611972795.61
+    .. [2] Ying, Xiaowei & Wu, Leting & Wu, Xintao. (2012).
+           A Spectrum-Based Framework for Quantifying Randomness of Social Networks.
+           IEEE Transactions on Knowledge and Data Engineering 23(12):1842--1856.
+           https://dl.acm.org/doi/abs/10.1109/TKDE.2010.218
     """
     import numpy as np
 
     # corner case: graph has no edges
     if nx.is_empty(G):
-        raise nx.NetworkXError("non_randomness not applicable to empty graphs")
+        raise nx.NetworkXError("graph has no edges")
     if not nx.is_connected(G):
-        raise nx.NetworkXException("Non connected graph.")
+        raise nx.NetworkXException("graph is not connected")
     if len(list(nx.selfloop_edges(G))) > 0:
-        raise nx.NetworkXError("Graph must not contain self-loops")
+        raise nx.NetworkXError("graph contains self-loops")
+
+    n = G.number_of_nodes()
+    m = G.number_of_edges()
 
     if k is None:
         k = len(tuple(nx.community.label_propagation_communities(G)))
+    elif not 1 <= k < n:
path: networkx/algorithms/non_randomness.py
text: @user1:
Should this just be an `if`? If `k` >> `n` this approach doesn't really apply, correct? Might as well fail early on user-provided values too.

@author:
I'm not sure I understand your reasoning. Making it an `if` just means the value of `k` generated by the community detection gets checked as well, but I made the assumption it won't return less than 1 or more than `n-1` communities and so it wouldn't ever catch anything. I guess it could be that the returned number of communities is exactly `n` though? I'm not familiar enough to say for sure.

@author:
I've updated it to just be an `if`, that way the value set by `label_propagation_communities` gets checked as well.

diff_hunk: @@ -12,86 +12,150 @@
 @not_implemented_for("multigraph")
 @nx._dispatchable(edge_attrs="weight")
 def non_randomness(G, k=None, weight="weight"):
-    """Compute the non-randomness of graph G.
+    """Compute the non-randomness of graph `G`.
 
-    The first returned value nr is the sum of non-randomness values of all
+    The first value $R_G$ is the sum of non-randomness values of all
     edges within the graph (where the non-randomness of an edge tends to be
     small when the two nodes linked by that edge are from two different
     communities).
 
-    The second computed value nr_rd is a relative measure that indicates
-    to what extent graph G is different from random graphs in terms
-    of probability. When it is close to 0, the graph tends to be more
-    likely generated by an Erdos Renyi model.
+    The second value $R_G^*$ is a relative measure that indicates
+    to what extent `G` is different from a random graph in terms
+    of probability. The closer it is to 0, the higher the likelihood
+    the graph was generated by an Erdős--Rényi model.
 
     Parameters
     ----------
     G : NetworkX graph
-        Graph must be symmetric, connected, and without self-loops.
+        Graph must be undirected, connected, and without self-loops.
 
-    k : int
-        The number of communities in G.
-        If k is not set, the function will use a default community
-        detection algorithm to set it.
+    k : int or None, optional (default=None)
+        The number of communities in `G`.
+        If `k` is not set, the function uses a default community detection
+        algorithm (:func:`~networkx.algorithms.community.label_propagation_communities`)
+        to set it.
 
-    weight : string or None, optional (default=None)
+    weight : string or None, optional (default="weight")
         The name of an edge attribute that holds the numerical value used
-        as a weight. If None, then each edge has weight 1, i.e., the graph is
+        as a weight. If `None`, then each edge has weight 1, i.e., the graph is
         binary.
 
     Returns
     -------
-    non-randomness : (float, float) tuple
-        Non-randomness, Relative non-randomness w.r.t.
-        Erdos Renyi random graphs.
+    (float, float) tuple
+        The first value is $R_G$, the non-randomness of the graph,
+        the second is $R_G^*$, the relative non-randomness
+        w.r.t. the Erdős--Rényi model.
 
     Raises
     ------
+    NetworkXNotImplemented
+        If the input graph is directed or a multigraph.
+
     NetworkXException
-        if the input graph is not connected.
+        If the input graph is not connected.
+
     NetworkXError
-        if the input graph contains self-loops or if graph has no edges.
+        If the input graph contains self-loops or has no edges.
+
+    ValueError
+        If `k` is not in $\\{1, \\dots, n-1\\}$, where $n$ is the number of nodes,
+        or if `k` is such that the computed edge probability
+        $p = \\frac{2km}{n(n-k)}$ does not satisfy $0 < p < 1$.
 
     Examples
     --------
     >>> G = nx.karate_club_graph()
     >>> nr, nr_rd = nx.non_randomness(G, 2)
     >>> nr, nr_rd = nx.non_randomness(G, 2, "weight")
 
+    When the number of communities `k` is not specified,
+    :func:`~networkx.algorithms.community.label_propagation_communities`
+    is used to compute it.
+    This algorithm can give different results depending on
+    the order of nodes and edges in the graph.
+    For example, while the following graphs are identical,
+    computing the non-randomness of each of them yields different results:
+
+    >>> G1, G2 = nx.Graph(), nx.Graph()
+    >>> G1.add_edges_from([(0, 1), (1, 2), (1, 3), (3, 4)])
+    >>> G2.add_edges_from([(0, 1), (1, 3), (1, 2), (3, 4)])
+    >>> [round(r, 6) for r in nx.non_randomness(G1)]
+    [-1.847759, -5.842437]
+    >>> [round(r, 6) for r in nx.non_randomness(G2)]
+    Traceback (most recent call last):
+     ...
+    ValueError: invalid number of communities for graph with 5 nodes and 4 edges: 2
+
+    This is because the community detection algorithm finds
+    1 community in ``G1`` and 2 communities in ``G2``.
+    This can be resolved by specifying the number of communities `k`:
+
+    >>> [round(r, 6) for r in nx.non_randomness(G2, k=1)]
+    [-1.847759, -5.842437]
+
     Notes
     -----
-    This computes Eq. (4.4) and (4.5) in Ref. [1]_.
-
-    If a weight field is passed, this algorithm will use the eigenvalues
-    of the weighted adjacency matrix to compute Eq. (4.4) and (4.5).
+    If a `weight` field is passed, this algorithm will use the eigenvalues
+    of the weighted adjacency matrix instead.
+
+    The output of this function corresponds to (4.4) and (4.5) in [1]_.
+    A lower value of $R^*_G$ indicates a more random graph;
+    one can think of $1 - \\Phi(R_G^*)$ as the similarity
+    between the graph and a random graph,
+    where $\\Phi(x)$ is the cumulative distribution function
+    of the standard normal distribution.
+
+    Theorem 2 in [2]_ states that for any graph $G$
+    with $n$ nodes, $m$ edges, and $k$ communities,
+    its non-randomness is bounded below by the non-randomness of an
+    $r$-regular graph (a graph where each node has degree $r$),
+    and bounded above by the non-randomness of an $l$-complete graph
+    (a graph where each community is a clique of $l$ nodes).
 
     References
     ----------
     .. [1] Xiaowei Ying and Xintao Wu,
            On Randomness Measures for Social Networks,
            SIAM International Conference on Data Mining. 2009
+           https://doi.org/10.1137/1.9781611972795.61
+    .. [2] Ying, Xiaowei & Wu, Leting & Wu, Xintao. (2012).
+           A Spectrum-Based Framework for Quantifying Randomness of Social Networks.
+           IEEE Transactions on Knowledge and Data Engineering 23(12):1842--1856.
+           https://dl.acm.org/doi/abs/10.1109/TKDE.2010.218
     """
     import numpy as np
 
     # corner case: graph has no edges
     if nx.is_empty(G):
-        raise nx.NetworkXError("non_randomness not applicable to empty graphs")
+        raise nx.NetworkXError("graph has no edges")
path: networkx/algorithms/non_randomness.py
text: @user1:
Changing exception messages is a recipe for bogging down review as it's (arguably) unnecessary code churn unrelated to the main changes.

I don't have strong feelings in this case, but generally speaking I'd recommend avoiding such changes to avoid distracting side-discussions during review. If you feel very strongly about updating an exception message, the best way to go about it (IMO) is to open a dedicated PR for it!

@author:
You're right that it's an unnecessary change. I'm juggling two feelings here: the very strong feeling I have about the lack of standardization of error messages (and types for that matter) across the repo on one hand, and the desire to keep changes as small and "meaningful" as possible (with the added problem that changes, especially to exception types, can break things for downstream users) on the other. I'm not sure whether anyone else shares these concerns, or how to best go about alleviating them, so I appreciate your perspective!