graphscope.nx.generators.expanders.paley_graph

graphscope.nx.generators.expanders.paley_graph(p, create_using=None)[source]

Returns the Paley (p-1)/2-regular graph on p nodes.

The returned graph is a graph on Z/pZ with edges between x and y if and only if x-y is a nonzero square in Z/pZ.

If p = 1 mod 4, -1 is a square in Z/pZ and therefore x-y is a square if and only if y-x is also a square, i.e the edges in the Paley graph are symmetric.

If p = 3 mod 4, -1 is not a square in Z/pZ and therefore either x-y or y-x is a square in Z/pZ but not both.

Note that a more general definition of Paley graphs extends this construction to graphs over q=p^n vertices, by using the finite field F_q instead of Z/pZ. This construction requires to compute squares in general finite fields and is not what is implemented here (i.e paley_graph(25) does not return the true Paley graph associated with 5^2).

Parameters:

  • p (int, an odd prime number.) –

  • create_using (NetworkX graph constructor, optional (default=nx.Graph)) – Graph type to create. If graph instance, then cleared before populated.

Returns:

G – The constructed directed graph.

Return type:

graph

Raises:

NetworkXError – If the graph is a multigraph.

References

Chapter 13 in B. Bollobas, Random Graphs. Second edition. Cambridge Studies in Advanced Mathematics, 73. Cambridge University Press, Cambridge (2001).