is_aperiodic#
- is_aperiodic(G)[source]#
Returns True if
G
is aperiodic.A strongly connected directed graph is aperiodic if there is no integer
k > 1
that divides the length of every cycle in the graph.This function requires the graph
G
to be strongly connected and will raise an error if it’s not. For graphs that are not strongly connected, you should first identify their strongly connected components (usingstrongly_connected_components()
) or attracting components (usingattracting_components()
), and then apply this function to those individual components.- Parameters:
- GNetworkX DiGraph
A directed graph
- Returns:
- bool
True if the graph is aperiodic False otherwise
- Raises:
- NetworkXError
If
G
is not directed- NetworkXError
If
G
is not strongly connected- NetworkXPointlessConcept
If
G
has no nodes
Notes
This uses the method outlined in [1], which runs in \(O(m)\) time given \(m\) edges in
G
.References
Examples
A graph consisting of one cycle, the length of which is 2. Therefore
k = 2
divides the length of every cycle in the graph and thus the graph is not aperiodic:>>> DG = nx.DiGraph([(1, 2), (2, 1)]) >>> nx.is_aperiodic(DG) False
A graph consisting of two cycles: one of length 2 and the other of length 3. The cycle lengths are coprime, so there is no single value of k where
k > 1
that divides each cycle length and therefore the graph is aperiodic:>>> DG = nx.DiGraph([(1, 2), (2, 3), (3, 1), (1, 4), (4, 1)]) >>> nx.is_aperiodic(DG) True
A graph created from cycles of the same length can still be aperiodic since the cycles can overlap and form new cycles of different lengths. For example, the following graph contains a cycle
[4, 2, 3, 1]
of length 4, which is coprime with the explicitly added cycles of length 3, so the graph is aperiodic:>>> DG = nx.DiGraph() >>> nx.add_cycle(DG, [1, 2, 3]) >>> nx.add_cycle(DG, [2, 1, 4]) >>> nx.is_aperiodic(DG) True
A single-node graph’s aperiodicity depends on whether it has a self-loop: it is aperiodic if a self-loop exists, and periodic otherwise:
>>> G = nx.DiGraph() >>> G.add_node(1) >>> nx.is_aperiodic(G) False >>> G.add_edge(1, 1) >>> nx.is_aperiodic(G) True
A Markov chain can be modeled as a directed graph, with nodes representing states and edges representing transitions with non-zero probability. Aperiodicity is typically considered for irreducible Markov chains, which are those that are strongly connected as graphs.
The following Markov chain is irreducible and aperiodic, and thus ergodic. It is guaranteed to have a unique stationary distribution:
>>> G = nx.DiGraph() >>> nx.add_cycle(G, [1, 2, 3, 4]) >>> G.add_edge(1, 3) >>> nx.is_aperiodic(G) True
Reducible Markov chains can sometimes have a unique stationary distribution. This occurs if the chain has exactly one closed communicating class and that class itself is aperiodic (see [1]). You can use
attracting_components()
to find these closed communicating classes:>>> G = nx.DiGraph([(1, 3), (2, 3)]) >>> nx.add_cycle(G, [3, 4, 5, 6]) >>> nx.add_cycle(G, [3, 5, 6]) >>> communicating_classes = list(nx.strongly_connected_components(G)) >>> len(communicating_classes) 3 >>> closed_communicating_classes = list(nx.attracting_components(G)) >>> len(closed_communicating_classes) 1 >>> nx.is_aperiodic(G.subgraph(closed_communicating_classes[0])) True