Should self-edges be considered when computing clustering?

[rlratzel]

This came up in a code review for the nx-cugraph backend.

Should the degree value for a node include self-edges when computing clustering?

@eriknw and I were thinking "no", but perhaps there's a reason it should?

[eriknw]

This question is for basically every function in clustering.py. There are no tests for these functions with graphs with self-edges, so maybe tests should be added and desired behavior confirmed so all backends can benefit.

[dschult]

The docs for that function clustering: docs say that self-loops are ignored and a quick check of the code agrees with that. I didn't check all the functions in that module though.

[eriknw]

Thanks! I should do a better job reading the docs ;) . Sometime this year I'll try to make a PR to increase coverage of cugraph and graphblas backends and to handle missing cases such as this.

[dschult]

And we should have tests for self-loops in probably every function in the library -- we've talked about having that be a GSOC project, but it hasn't happened. And yes -- a PR to increase coverage and to handle missing cases would be nice. !:)

[Schefflera-Arboricola]

This question is for basically every function in clustering.py

for all the functions in cluster.py :

• triangles, average_clustering, clustering : Mentioned in docs that they ignore self-loops
• transitivity, generalized_degree : uses the _triangles_and_degree_iter function in which self-loops are not considered(vs = set(v_nbrs) - {v}), as the set vs is constructed by subtracting the node v from the set of neighbors v_nbrs. This implies that the node v itself is not included in the set of neighbors vs, and therefore, self-loops are implicitly ignored
• square_clustering : do not ignore self-loops (considers all pairs of nodes u and w in the combinations of neighbors of node v (combinations(G[v], 2)).)

import networkx as nx
G = nx.path_graph(5)
print(nx.square_clustering(G))
G.add_edges_from([(0,0),(1,1),(2,2)])
print(nx.square_clustering(G))

# {0: 0, 1: 0.0, 2: 0.0, 3: 0.0, 4: 0}
# {0: 1, 1: 0.5, 2: 0.2, 3: 0.0, 4: 0}