Abstract
Critical network cascades, as an instance of percolation, are ubiquitous in nature. As
such, they occur in the brain, and nearly any self-organized or naturally-occurring system
characterized by interactions.
Cascades have also been described as a simple model of decision making. Together
with information diffusion, their simplicity, and their ubiquity in nature, this makes them
a very interesting starting point for a theory of information processing in natural systems.
In the brain cascades may occur as neuronal avalanches, while in social networks they
can be manifested as epidemics, idea or rumor spreading, or viral consumption behavior.
Of course, they may occur in granular media such as sand or snow as avalanches, or in
chemical processes or many other systems.
Therefore, we may also reasonably ask why cascades do not play a large role in modern
artificial statistical- or machine- learning, and how we may conduct basic research into
information processing by natural systems. Here we take some steps to understand how
critical network cascades can process information. We do this by studying a simple,
theoretical model of critical network cascades, the Linear Threshold Model (LTM).
We show that Boolean logic can be computed by the LTM. Also a universal basis
(functional completeness) can be obtained by the LTM, by including a new type of
antagonistic node to create the antagonistic LTM (ALTM). We observe that the global
cascade frequency in the ALTM is approximately the inverse of that in the LTM.
Subsequently, we investigate the LTM as a classification and learning model, with
global cascades as the classifier, and identify sources of efficiency in learning. We
observe that certain types of error do not exist, and that Euclidean constraints can
increase efficiency significantly. We also note that the LTM automatically maps between
information encodings.
We then examine the phase space of Boolean functions computed by nodes in the
LTM (and mix of LTM/ALTM nodes), observing a decreasing exponential rank-ordering
of function frequency, inversely related to a function’s decision tree complexity. Thus
the LTM performs computational cascades, computed by simple sub-networks which are
logical automata or logic motifs. Using these motifs, we predict function probability by
the number of required paths, and that the number of paths of a function is its decision
tree complexity. We show that the Boolean function’s reflection asymmetry gives us this
complexity, and that the probability is proportional to that of the nodes belonging to
the giant connected component (GCC). Thus we arrive at the deeper observation that
symmetry breaking in the system (formation of the GCC) leads to symmetry breaking of
functions (complexity) computed.