Markov chains from probability theory have underlying graphs associated with them, where every vertex is a state of the chain and the edges represent possible transition between the states. We're talking about discrete time Markov chains here, so transitions between states happen at discrete time points, the natural numbers. Now, some chains are aperiodic, meaning that for large enough time points n, the chain could possibly be in every state.
An example of a chain that is not aperiodic is the one below. There are only two states, 1 and 2 and the chain is forced to flip back and forth between them. If the chain starts in state 1, it can only be in state 1 at even time steps and in state 2 at odd time steps.
On the other hand, any chain that has a state with a self-loop is aperiodic. For example, the one here. But there could be chains without any self-loops that are also aperiodic like the one below:
So, there must be an algorithm that, given the underlying graph of a Markov chain as an adjacency list or matrix can efficiently tell if the chain is aperiodic or not.
One option is to take the adjacency matrix and multiply it by itself a bunch of times, keeping an eye out for flip-flopping. But I'm hoping this can be done using the graph alone.
@user3386109 is correct on what he commented, and the assumption that for strongly connected graphs (according to this, that means irreducible Markov-chains), having a self-loop makes it aperiodic. If you look at a state A, start from there (time step 0) and transition among other nodes, if there is any chance you can return to this node at the time step k, then there must be a circuit in the graph with length k that includes the node/state A (a circuit is a cycle, where any node can appear multiple times). We need to find out whether for some large enough N, there is a circuit that has length k and includes A, for all k>N. Imagine if you find one circuit that passes through A. Let's assume the length of this circuit is L. By going along this circuit multiple times, you can get from starting state A to A again in L, 2L, 3L, ..., nL, ... steps, which means that we can be sure that PnL is not 0. This is not sufficient though for cases where k is not a multiple of L, so we need to also consider other length circuits. If you have a different circuit with length M (also going through A), then by just going through both circuits enough times, you can make sure that you can get from A to A in aL+bM steps for any natural number a,b. This actually might be sufficient. For example, if M=4 and N=7, for any number k above 17, you can find a way to go from A to A in k steps, because these two numbers are relatively prime, and according to Bézout's lemma, you can find numbers a,b that aL+bM=k (it doesn't directly come from it, you need to be tricky, but that is not important now). The threshold particularly came from the McDonald's motivated Chicken McNugget theorem.
Now, it turns out we could only care about cycles as circuits contain cycles in themselves (we can split any circuit onto "building cycles"), but we'd have to analyze them "globally", instead of circuits which we need to only analyze "locally" (only the ones passing through A). If you would look at all the circuits passing through A (there is infinitely many of them, if not 0), based on their length, you can decide if state A is aperiodic. If the greatest common divisor of the lengths is 1 (like 4 and 7), so gcd(l1, l2, ... )=1, then the state is aperiodic, because for a large enough N, for any k>N, there exists a (positive) linear combination of the numbers that equal k, basically meaning you can choose to go along circuits certain number of times and you'll arrive back in A after exactly k. Which means the probability of getting from A to A in k steps is Pk>0. In any other case, if gcd(l1, l2, ... )=d>1 it's not possible, since for only those k values is PK>0 that are visible by d. The problem is, there are infinitely many circuits, whereas cycles are limited.
If we have a strongly connected graph, we only need to find if one state is aperiodic, because then all other states and thus the chain is aperiodic. We can prove this: if we know that some state, marked with node V, is aperiodic (so for large N, for any number k>N we can get from V to V in k steps), then we'll show that any other node U is also aperiodic. Since the graph is strongly connected, there is some path from U to V, with length let's say l, and there is also a path from V to U, let's say with length m. Then you can get from U to U in k' steps for any k'>N+m+l by going to V in l steps, going from V to V in k=k'-m-l, k>N steps, and going back to U in m steps. It's basically using the circuits of V to show that U is also aperiodic. (This is also the reason why strongly connected graphs having a self-loop makes them aperiodic.)
H͟e͟r͟e͟ i͟s͟ a͟ c͟l͟a͟i͟m͟: It should be sufficient to look at the cycles in the network and their lengths (there are finitely many of them), and if the lengths are relatively prime, then it's certain that the chain is aperiodic, in any other case it is not aperiodic. I have only proved the second part.
What you have to do: Firstly, reduce the Markov-chain till it is irreducible. You can check if it is irreducible (thus the graph is strongly connected) by Tarjan's algorithm. Then run an algorithm that finds all cycles in the graph (or an approximation, as this could take enormous time). You may instead only look for cycles till their length's greatest common divisors is 1, as that already would mean that the chain is aperiodic. If in the end, the cycle length's GCD is 1, then we have an aperiodic Markov chain, else it is periodic.
This works, but problem is, that solving this problem would take computationally long time in some cases (unless you are working with a few states and transitions only). This is not the fault of the algorithm but the fault of the problem: this problem is at least NP-complete hard, meaning that it can take exponentially many steps to find the solution to some cases. For example, if a cycle we need to find and would be a cycle including all other nodes, then that would include the Hamilton-cycle problem (HAM), which is NP-complete. In complete graphs, you could have exponentially many cycles, but you'd find relatively prime lengths very fast.
I must say one more thing, that it is not true that a graph has to be a strongly connected graph for it to be aperiodic. Imagine the graph of two triangles: 1,2,3 and 4,5,6, with back-and-forth connections between the nodes in the triangle, and a forward connection from state 3 to 4. All states are aperiodic because of the triangles, but you cannot get from nodes 4,5,6 to 1,2,3.
But the good news is that all irreducible Markov-chains are strongly connected.