1. Introduction
Knowledge that is central in learning and teaching often starts with factual knowledge of agents, objects, and events, and how they are related. This is equally true in such different areas of learning and instruction as, for example, in physics [
1,
2,
3] and history [
4,
5]. The familiarization of new key concepts involves making connections with what is already known and how new items and terms can be integrated into more extensive knowledge structures [
6,
7,
8]. In that process, associative recall and memorization of thematic connections and relationships between knowledge items (e.g., words, terms or concepts) create an interlinked system of knowledge items, which is referred to as associative network [
9,
10,
11,
12]. The knowledge processing may then continue with more organized strategies, eventually leading to more integrated knowledge systems [
6,
7,
8].
The formation of associative connections between knowledge items can be thought to occur as pairwise (dyadic) thematic word or term associations, which are established on the basis of thematic resemblance or kinds of taxonomic family resemblance, Consequently, associative knowledge is often modelled as a complex network of interlinked words and terms, where the associative connection becomes activated through the spreading of activation between words and terms that are related, for example, either thematically or taxonomically [
9,
10,
11,
12]. The idea of spreading activation [
11,
12] within semantic and associative networks has been utilized in several areas of cognitive psychology in modeling retrieval and memorization of knowledge or words (see [
12,
13] and the references therein). According to spreading activation, when one word or term in a semantic or associative network is activated, that activation spread to other words, through connections within the semantic network and so it affects the state of the network [
11,
12,
13]. Thus, spreading activation has provided a dynamic and systemic perspective on associative knowledge networks, guiding attention on how different parts of the networks are interacting or communicating.
Spreading activation has been modelled as a diffusion or random walk process in a network, where a random walker (e.g., information that is mediated and causes activation) that starts from a given node propagates to nodes that are accessible through links connecting the nodes [
12,
13]. In this study, we suggest a model, where the focus is shifted from spreading activation as a process to holistic states of the network, where pairwise activations between nodes in course of spreading activation are equated with state of the system. To this state, we refer in what follows as the systemic state. The basic picture of spreading process is similar as in random walk based models, but modelling through systemic states quantifies the dynamically changing state of the network and brings it in focus. In constructing the systemic states, we follow recent advances to model diffusion-like dynamics on complex networks [
14,
15,
16,
17,
18,
19]. In that approach, the connectivities within the networks (i.e., nodes and links between nodes) are taken as starting point to describe how a network becomes activated when diffusion spreads, and the normalized probabilities that describe the activations of links at a given instant are associated with a systemic state.
One important question and open problem in spreading activation is to quantify how it is affected by different types of sub-structures within the network, most typically parts of the network that belong to taxonomically or thematically different categories (i.e., different types of words or terms). This is essentially a problem that is related to a comparison of networks [
17,
18,
19]. Based on systemic states of a network, it is possible to construct information theoretic entropic measures in order to quantify the differences between networks, one of the most robust and widely used being Jensen–Shannon divergence, which is a symmetric relative entropy between two different states [
14,
15,
16,
17,
18,
19]. The relative entropy measures the information lost, when two networks are joined, in comparison to information that is contained in original state. Here, we generalize the Jensen–Shannon relative entropy for the model of nonlinear spreading activation and the systemic states corresponding it.
In this study, we show that the generalization provided in the present study have good resolving power and sensitivity in exploring the role of sub-structures in spreading activation in associative networks. As a concrete example, in order to demonstrate the viability of analysis that is based on systemic states, we use empirical data from a recently reported case of university students’ associative knowledge regarding the history of science [
3]. Such a network has an interestingly complex structure and a rich internal community structure organized around key items (often persons) in the network. However, it proved to be difficult to quantify the role of relationships between persons, scientific ideas, and inventions, and general historical events in the formation of the whole network [
3]. Here, attention is on roles of the different type of relations between key items in the network and how they constitute the sub-structures within the network as a whole. The systemic states constructed to describe spreading activation are used as a starting point to quantify the the importance of the sub-networks for spreading activation in a complete network.
2. Methods: Systemic States and Their Comparison
The model for spreading activation, which allows for exploring associative networks and the role of its substructure in spreading activation, is developed in three steps. First, we introduce the quantities that describe the connectivity of the network, the so-called adjacency matrix A and diagonal matrix D for node degrees, and on basis of them, graph Laplacian L describing diffusion-like spreading is introduced. Second, based on graph Laplacian L, generalized systemic states are constructed. Third, and, finally, relative information theoretic entropy (generalized Jensen–Shannon–Tsallis divergence) is introduced to compare systemic states.
2.1. Graph Laplacian and Diffusive Spreading
The role of a given node in spreading activation is related to its capacity (or activity) to channel information to other nodes within a network. This depends on how a given node is connected within a network and how it can communicate through the connections; how activation spreads throughout the network. Spreading activation can be modeled using a diffusion-like propagator, which is based on a graph Laplacian [
18,
19]. The graph Laplacian
of a network is defined in terms of adjacency matrix
with elements
, where
if nodes
i and
j are connected and, otherwise,
. In what follows, symmetric adjacency matrices are assumed. The diagonal matrix
is composed of elements
, where
is the degree of node
i. The matrix elements of the so defined graph Laplacian are thus given by
, where
is Kronecker’s delta as usual. The graph Laplacian
can be interpreted as a discrete Laplacian operator describing random walk in a network, analogous to ordinary Laplacian operator
in a normal diffusion equation [
20,
21].
Next, we represent the property of node that describes it role in diffusive spreading as a vector
in a network of N nodes. The property
can be associated with a probability that a random walker in a network stays in a node or, alternatively, as a capacity of node to retain the information (i.e., to block the diffusion) [
18,
19]. Note that it is not necessary to define the property
in more detail, because the focus of interest will be the diffusion propagator, which can be used in order to describe the diffusion (spreading) dynamics of the network.
The diffusion process in a network, by using graph Laplacian
L, can now v described by discrete difference equation [
20,
21] (see also refs. [
18,
19])
This equation has a solution , where has a role analogous to time and is the initial state. According to this picture, the propagator regulates how property that is described by spreads out in that diffusion process. In what follows, the propagator and its generalization are in focus.
2.2. Systemic States and Activity
We now generalize the diffusion equation in Equation (
1), so that the property
of nodes to affecting spreading activation is taken into account non-linearly, so that high values of
become reduced (i.e., their role in retardation is diminished) in relation to values that are low. This means that nodes that facilitate spreading are allowed to become even more important for it. In that case, the evolution equation in Equation (
1) for the property
of interest generalizes to (as compared with e.g., [
22])
The value
corresponds to the spreading activation that parallels with normal diffusion. It is straightforward to show that a (normalized) solution of Equation (
2) is
(for initial state
), where
with
as the normalization factor. In Equation (
3), the expression
is the q-generalized matrix exponential, which, in the limit
, approaches the normal matrix exponential [
23,
24]. The propagator
has the central role in regulating the spreading activation when modeled as a diffusion or random walk process. Consequently, we now take the solution
in Equation (
3) to represent the systemic state of the network in the stage of spreading activation that corresponds to given value of time-like parameter
and refer to it as q-generalized systemic state in what follows. The q-generalized systemic state is mathematically well-defined positive semidefinite matrix possessing eigenvalues that are equal or larger than zero (and, thus, a proper density matrix) [
23,
24]. A similar description of networks through a state corresponding to a normal matrix exponential in the limit
is provided in reference [
19]. The model for spreading activation based on Equations (2) and (3) can be taken as a generalization of such a description.
In order to define the changing, dynamic activity
of a node
i in spreading activation, we note that the diagonal values
of systemic state are in a diffusion-picture proportional to average probability of return to a node [
18,
19]; the lower the diagonal value of the systemic state for node
i, the more important it is that the node is in activation spreading. This notion allows for us to define the dynamic activity
of a node
i as
The dynamic activity is then the basic quantity for monitoring the role of individual nodes in activation spreading, with a high value of (i.e., low value of ) corresponding to high activity and a low value a low activity.
2.3. Divergence for Comparisons
We next ask how two different systemic states
and
of the network can be compared. An obvious approach is to use relative information theoretic entropy as a measure of difference (see, e.g., [
14,
15,
18,
19]. Relative information theoretic entropy quantifies the difference between information that is contained in initial states in comparison to the state obtained by completely mixing the initial states. Thus, it is a measure of maximal loss of information in mixing. Relative entropies are widely used in a comparison of networks, because they provide a well-defined macrolevel description of difference and take the networks as a whole into account in quantifying the differences [
14,
15,
18,
19]. Here, a method of comparison based on relative information theoretic entropy is generalized for the q-geenralized systemic states defined in Equation (
3).
The q-generalized states in Equation (
3) are closely related to a q-qeneralized (non-extensive) Tsallis-entropy [
23,
24], and they emerge as density matrices that extremize Tsallis-entropy. In that picture, parameter
q can be related to the degree of non-extensivity, often originating, e.g., from fractality or compartmentalization of the system [
24]. However, deeper discussion is not necessary here, and we can treat
q simply as parameter controlling the non-linearity in Equation (
2). However, to connect the q-generalized state to Tsallis-entropy, we allow the q-index
for Tsallis-entropy to differ from value of
q in Equations (2) and (3), and only afterwards, fix the connection between the two indices. The Tsallis-entropy with index
is
Depending on constraints posed on maximization, the Tsallis entropy, which is maximized by
, may have index
different from
q [
23,
24,
25]. Here, we choose to pose the linear constraints on extremization of the Tsallis-entropy, by requiring: (1) the conservation of probability
and (2) constancy of expectation values of the Laplacian
. [
23,
24,
25]. An alternative would be to adopt the so-called escort-probabilities [
23,
24,
25], but we choose to avoid that choice. With the choice of linear constraints, the index
is [
23,
24,
25]
The relation in Equation (
5) between indices
q and
is typical to the so-called dual forms of Tsallis-distributions, encountered when so-called escort probabilities are excluded in favor for the ordinary probabilities and expectation values related to them [
23,
24,
25]. In the limit
reduces to von Neumann entropy
, where
is the natural logarithm.
We can now proceed to define a symmetric version of relative information theoretic entropy for a comparison of states
and
, and that is compatible with the Tsallis-entropy with index
. This is a q-generalization
of Jensen–Shannon–Tsallis relative entropy [
14,
15,
18,
19]
where the first term at right is the entropy of the mixed state
and the last term an average of entropies that correspond to initial states. In what follows,
defined in Equation (
7) is referred as q-generalized Jensen–Shannon–Tsallis divergence (q-JST divergence in short) and is the basis for comparison of different systemic states of the network. Note that, in defining
, the index
is different from q-index for states
and
, thus weighting low-probability states of interest more than the ordinary Jensen–Shannon divergence (
) (compare with refs. [
14,
15], where
is treated as a free parameter).
The different mathematical quantities that are used in the step-by-step derivation above are summarized in
Table 1 for reference. Of these, the activity
and q-JST divergence
are used in exploring an example of an associative network.
4. Discussion
A comparison of networks is an important problem in many areas of network science [
14,
15,
16,
17,
18,
19]. In this study, we suggested a method of analysis of networks and their comparison based on systemic states of network, which are constructed to model spreading activation [
9,
10,
11,
12]. Spreading activation picture can be modeled as diffusion-like process, where the extent of spreading is described in terms of diffusion propagator, in the form of a density matrix that takes into account all connections between the terms included in the system (network) [
18,
19]. Here, the q-generalized systemic states are constructed in the form of a diffusion-propagator, which allows for weighting the role nodes in spreading activation differently, with values of
corresponding to normal diffusion and
cases where a role of high activity nodes is emphasized in spreading. The diffusion propagator is a holistic and complete description of the whole network describing its changing state in spreading activation. Consequently, the propagator can be taken as a systemic state describing the network.
On basis of the q-generalized systemic states, it becomes possible construct an associated q-generalization of the usual Jensen–Shannon relative entropy (divergence) measuring the difference between the states [
18,
19]. The q-generalized divergence is based on Tsallis-entropy with index
that results from a specific choice of (linear) constraints, related to so-called dual-forms in Tsallis-statistic. A practical motivation for introducing the relation
is to achieve an optimal resolution for quantifying the differences between q-generalized states, the dual index
in q-generalized divergence weights more the important states occurring with low probability, when
. The best resolving power of differences is achieved when
and, correspondingly,
.
The viability and advantages of the approach based on q-generalized systemic states and divergences is demonstrated here by applying it in the recently studied case of university students’ associative knowledge of history of science, represented as an agglomerated network [
3]. It was shown that an analysis that is based on systemic states for spreading activation has the potential to be better than conventional approaches based on use of exponential states (
) in revealing and quantifying the role of different sub-networks in spreading activation in associative networks (and, consequently, in similar kinds of complex networks in general). The optimal resolving power to detect global differences was achieved when
(
). The results of the analysis were fully compatible with the more traditional analysis [
3], but it was shown that systemic states provide better insight on roles the sub-networks have in a complete network, through their activity in spreading activation. Moreover, the method provides robust and reliable way to quantify such differences, with the possibility of much potential in quantitative analysis and comparisons of complex systems that can be represented in the form of networks.
5. Conclusions
The systemic approach for analyzing complex networks, as suggested here, is based on the construction of systemic, holistic states to describe the network, from a perspective of diffusion-like spreading activation. The method quantifies the notion of spreading activation, central for many applications related to associative knowledge networks. The new results contained in the present study are: (1) q-generalized systemic states that are constructed as diffusion propagator solutions of a non-linear discrete diffusion equation describing spreading activation, and (2) q-generalized relative information theoretic entropy measure for quantifying differences between systemic states, which is constructed as a Jensen–Shannon–Tsallis divergence for the q-generalized states. The q-generalized systemic states contain two parameters q and , which can be used to tune the states sensitive to desired scales, from local to global connectivity, corresponding to extent of spreading activation, thus providing new tools for robust quantitative characterization of complex networks from a systemic perspective.
Finally, the method was applied in the case of a recently empirically studied associative knowledge network, with the results demonstrating the viability of the method and its sensitivity on global, systemic level properties of the network in the course of spreading activation. In summary, the approach that is suggested here embodies the spreading activation view on networks and provides a quantification in terms of systemic states. The results of application demonstrate not only the viability of the proposed method, but also its better sensitivity on the details of the networks not easily captured by more conventional analysis methods.