Autonomous and Ubiquitous In-node Learning Algorithms of Active Directed Graphs and Its Storage Behavior

The storage of subgraph structures involves recording the connectivity paths between active nodes, which can only be accomplished by the nodes themselves based on their local perspectives. This necessitates that active nodes individually record activation information upstream and downstream of themselves. Define the activation trace of node $u$ as a path fragment consisting of active fan-in nodes and active fan-out nodes of node $u$. Storing the activation traces of all active nodes during this sample storage process will complete the subgraph storage.

In this paper, we store node activation traces by introducing an index table in each node, a data structure with small capacity, easy access, and simple updating. Figure 2 shows the structure of the index table, which contains two columns: the first for active fan-in nodes and the second for active fan-out nodes. Figure 2a shows that node B’s index table contains no content before storing the samples. Once a sample is stored, its corresponding activation trace is saved in its index table. As shown in Figure 2b, during sample retrieval, if node B receives the same or similar input as the recorded activation traces, it generates the corresponding output based on the historical records in the index table.

Defining an index table inside each node that records upstream and downstream active path pairing relationships may appear straightforward and crude, but it is also biologically feasible. Biological neurons have dendrites that receive inputs from multiple directions and axonal that transmit outputs in different directions, creating a many-to-many connection. Actual physical signaling between upstream and downstream neurons relies on synapses, regulated by combinations of diverse neurotransmitters and ion pumps. These mechanisms precisely control the direction and intensity of positive and negative charge flow. Additionally, differences in synapse location, such as being distal or proximal to the axonal, on dendrites or axons, or on the main pathway or terminal, can precisely control the activation and deactivation of specific action potential transmission pathways. In conclusion, this highly precise and diverse molecular-level and subcellular-level modulation and their combinations equip biological neurons with various pathway control mechanisms at the microcircuit level [22, 23]. As a result, a biological neuron can achieve diverse pathway control of signaling within its small neighborhood, relying on a complex set of electrochemical processes [5]. This has inspired the design of directed graph nodes’ internal behavior, allowing them to function like network routers capable of differentially leading fan-outs based on fan-in variations. An index table with limited storage space is a simple, functional equivalent implementation.

The creation of subgraphs depends on the propagation of stimulus between nodes. Stimulus propagation consists of two aspects: node activation rules, i.e., how nodes are activated, and stimulus propagation rules, i.e., determining the downstream nodes to which the stimulus is propagated. In this paper, the node activation rule employed is a fixed-probability activation model, where a node will be activated with a fixed probability upon receiving input. The node becomes active and begins delivering stimulus to downstream nodes if successfully activated. Two types of stimulus propagation rules are used in this paper: the first reuses similar historical activation traces, and the second employs a weighted random selection algorithm.

The specific process of stimulus propagation among nodes is as follows: each resting state node has a fixed probability of H to be activated after receiving the stimulus. Once a node is activated, if its index table is empty, it randomly selects several downstream nodes with equal probability for stimulus delivery. If the index table is not empty, the similarity between the input and each item in the node index table is calculated first. In this paper, the F1 score [24] is used as a metric to evaluate the similarity of two node sequences. The F1 score is a statistical measure of the accuracy of a binary classification model, which is the harmonic mean of precision and recall. When comparing similarity, either one of the node sequences can be treated as the predicted value and the other as the actual value, and the corresponding F1 score is calculated. Higher scores indicate greater similarity. The corresponding historical activation traces are reused if the maximum similarity exceeds the threshold. Otherwise, a weighted random selection algorithm is used to select downstream nodes for stimulus delivery.

The weighted random selection algorithm is based on the frequency of the downstream node appearing in all active fan-out nodes in the current node index table. The higher the frequency of occurrence, the lower the chance of being selected. The introduction of this algorithm allows each active node to distribute stimulus evenly, thus maximizing network resource utilization. The algorithm pseudo-code is shown in Algorithm 1. The value of $H$ affects the subgraph size. The larger $H$ is, the more nodes participate in subgraph formation and the better the connectivity. However, the corresponding cost of network resources is also larger. In this paper, $H$ is set at 60% for testing.

Nodes are considered limited resources in a directed graph, adhering to the first-come, first-served preemption rule. Activating a node can be seen as the occupation of a node resource. When performing stimulus propagation, nodes can acquire the occupancy of downstream nodes to avoid passing stimulus to already occupied nodes. If an active node does not successfully activate any downstream nodes, it returns to a resting state. A change in the state of some active nodes may trigger a chain reaction that causes more active nodes to become resting. This situation is called the avalanche effect. As shown in Figure 3, at $t_{0}$, node B receives a stimulus from node A, then subsequently activated at $t_{1}$. However, because node C has been occupied, node B cannot transmit the stimulus to node C, causing node B to revert to the resting state at the $t_{2}$ moment. At this point, node A is not activating any nodes due to the change in the state of node B. Therefore, at $t_{3}$, node A also becomes resting due to the avalanche effect.

As the number of samples stored in the network increases, new subgraphs may encounter some problems caused by insufficient resources during the generation process, preventing new samples from being stored. The causes of insufficient resources in the network can be broadly classified into four categories:

1. The node index table has a capacity limit. When the number of samples stored in the network reaches a certain level, it becomes hard to store new samples.

2. The network is poorly connected, and the stimulus propagation rule carries a certain level of randomness, as well as the existence of the avalanche effect, which leads to an inability to establish a pathway between the initial nodes.

3. The samples already stored in the network interfere with the samples currently about to be stored. This is because nodes may reuse historical activation traces when they are activated. Although this is an optimization strategy to increase network capacity, it somewhat affects the storage of current samples.

4. Some active nodes take up too many node resources during the current activation, resulting in no resources available for other nodes.

For the first case, the capacity of the index table can be defined as the maximum number of output types that a node can store, as there may be many different inputs corresponding to the same output. The capacity can also be expanded by reasonably discarding and merging the contents of the index table. Specifically, when a node’s index table capacity reaches its upper limit, the node will search for the two most similar activation traces to merge. The similarity here refers to the similarity of the active fan-in nodes in the two activation traces, and merging refers to taking the intersection of the active fan-out nodes of the two activation traces. If the differences between the activation traces are both large, the one with the lowest strength is discarded. The strength here refers to the number of samples that the activation trace has been involved in storing. The more involved, the higher the strength. By reasonably merging and discarding, it is possible to increase network capacity as much as possible at the expense of certain recall accuracy and completeness. The pseudo-code of the algorithm is given by Algorithm 2.

The second and third cases can be solved by introducing a re-pathfinding rule. The re-pathfinding rule allows the initial nodes to re-propagate the stimulus to find a path connecting other initial nodes when it does not successfully activate any downstream node. For the fourth case, the active node can release some occupied resources according to its situation. The resource release algorithm is introduced here to solve this problem. When the number of failed re-pathfindings of an initial node reaches a certain threshold, it will enter a dormant state, indicating that it is currently unable to communicate with other nodes. The node in the dormant state suspends pathfinding until the subgraph stabilizes. Active nodes will release some nodes after the subgraph is stabilized to make resources available to dormant nodes. For example, if an active node has three active fan-out nodes, it can actively release the occupation of two of them. After releasing the redundant resources, the nodes in the dormant state will resume pathfinding until the subgraph stabilizes again. If, after releasing the resources, the dormant node is still unable to establish path connections to other active nodes, the network connectivity is considered poor, or there is a conflict between the current sample and the samples already stored in the network. In this case, the subgraph can still be formed. However, there will be some isolated nodes that cannot establish connections with other nodes, leading to a decrease in the subgraph’s anti-interference ability and fault tolerance. The pseudo-code of the resource release algorithm is given by Algorithm 3. Figure 4 shows the transition relationship between the three node states. Figure 5 presents the flowchart of the algorithm from the node’s perspective, which includes how nodes process the received stimulus and how downstream nodes are selected for stimulus delivery.

The sample storage process consists of two stages: (1) Stimulus propagation stage: the initial nodes propagate stimulus to other nodes along the directed edges until a stable subgraph is formed. (2) Subgraph consolidation stage: All nodes in the subgraph update their internal index tables, recording the activation traces. Figure 6 shows the storage algorithm from the processor’s perspective and the flowchart of the algorithm from the task scheduling perspective. The corresponding pseudo-code is given by Algorithm 4.

Stimulus propagation stage: Table II demonstrates a complete process of generating a stable subgraph through continuous iteration of the initial nodes. At the time $t_{0}$, the initial nodes are activated, and downstream nodes are chosen for stimulus propagation according to the weighted random selection algorithm. The subsequent $t_{1}$ and $t_{2}$ moments represent the continuous stimulus propagation in the network. At the time $t_{3}$, since downstream nodes B and C of node H have been occupied by other nodes, node H cannot perform stimulus transfer. Therefore, according to the node resource-grabbing rules, node H transitions from the active state to the resting state. At the time $t_{4}$, downstream node H, excited by node J, reverts to a resting state. At this point, node J does not activate any nodes, and due to the avalanche effect, its state also becomes a resting state. After the end of time $t_{4}$, node D will no longer propagate stimulus. However, as the initial node, it will follow the re-pathfinding rules, searching for a new path and attempting to participate in the subgraph formation. When re-pathfinding reaches a certain number of attempts, the node will enter a dormant state. Here, it is assumed that node D has entered a dormant state and will halt pathfinding until the subgraph is stable. It can be observed that at time $t_{4}$, the subgraph is already stable since there will be no change in node states. At this point, it is necessary for other active nodes in the network to release redundant resources, providing node D the opportunity to re-engage in the subgraph formation. At the time $t_{5}$, node A, which originally occupied both node E and node G resources, can choose to release the occupation of either of the two nodes. Assuming that node E is released, node E will become resting, and the stimulus from node E to node B will also vanish. However, because node B is an initial node, its state will not change. After the resource is released, node D resumes pathfinding and node J is activated at time $t_{6}$. At the time $t_{7}$, node H is activated by node J, and the stimulus is passed to the initial node B, forming a path. At this moment, the connected subgraph between active nodes becomes stable, no dormant nodes are present in the network, and the stimulus propagation stage concludes.

Subgraph Consolidation Stage: The primary task of this stage is to store a stable subgraph structure in the network. When the subgraph achieves a stable state, each active node will have corresponding active fan-in and active fan-out nodes, which are activation traces. Storing the subgraph is completed by updating the activation trace of each node in the node’s internal index table. The pseudo-code of the index table update algorithm is provided by Algorithm 2, and the pseudo-code of subgraph generation and preservation is given by Algorithm 4.

The process of sample retrieval closely resembles sample storage. However, the sample retrieval process is simpler, only including the stimulus propagation stage. During the stimulus propagation stage, it will not be activated when a node receives a stimulus transfer from an upstream node and cannot find a similar entry in its internal index table. The initial nodes will not enter the dormant state, and no nodes will release excessively occupied resources. In summary, the sample retrieval algorithm will not cause any changes to the existing network. However, it will only perform stimulus propagation based on the activation traces stored in the internal index table of the node. Since the sample retrieval algorithm process is very similar to the storage algorithm, only the specified part mentioned above needs to be omitted. Therefore, no separate pseudo-code is provided here.

Let $G_{i}=(V_{i},E_{i})$ represent the subgraph generated of the $i$th sample, where $V_{i}$ denotes the set of nodes, and $E_{i}$ denotes the set of edges. Let $G^{\prime}_{i}=(V^{\prime}_{i},E^{\prime}_{i})$ represent the subgraph generated during the retrieval of the $i$th sample. Define the accuracy $P_{i}=\frac{|E_{i}\cap E^{\prime}_{i}|}{|E^{\prime}_{i}|}$. Define the completeness $C_{i}=\frac{|E_{i}\cap E^{\prime}_{i}|}{|E_{i}|}$. Define an isolated node as an initial node in the subgraph with both in-degree and out-degree equal to zero. Define the sample representation quality, $Q$, as the percentage of non-isolated nodes relative to the initial nodes. If the number of initial nodes in the sample is $s$, and the number of isolated nodes in the subgraph generated by the sample is $l$, then $Q=\frac{s-l}{s}$. In capacity testing, each stored sample should satisfy a high sample representation quality and high completeness and accuracy during sample retrieval to be considered successfully stored by the network. Based on this, we can define the reliable capacity of the network. Let the reliable capacity, $T$, represent the maximum number of samples that the network can successfully store, and for each stored sample, it satisfies $Q_{i}>0.9$, $i\in[1,T]$, $\bar{P}=\frac{\sum_{i=1}^{T}P_{i}}{T}>0.9$, $\bar{C}=\frac{\sum_{i=1}^{T}C_{i}}{T}>0.9$.

Assume the network has $n$ nodes, each node has an internal index table with a capacity of $K$, and each subgraph contains, on average, $s$ initial nodes and $c$ communication nodes. For every subgraph stored in the network, there will be an increase or modification in the internal index table entries of the activated nodes. Considering this as a resource, the total number of resources in the network is $nK$, and each subgraph occupies $s+c$ resources. Without considering resource reuse or optimization measures, the network will consume $s+c$ resources for every stored sample, so the network capacity can be roughly represented as $\frac{nK}{s+c}$. If resource reuse is allowed, the calculation of network capacity becomes more complex. In an extreme case, where the resources occupied by the current subgraph are all reused, the upper bound of the network capacity can be roughly expressed as the combination number $\tbinom{nK}{s+c}$. The network capacity obtained from these two different calculation methods differs greatly. In actual testing, there are many other influencing factors, such as different network connectivity and conflicts between samples. Therefore, a theoretical network capacity analysis is difficult, and a specific analysis should be conducted in conjunction with actual testing situations.

Table III shows the performance of sample retrieval after storing 1,000 samples in networks. The node index table size is set to $K=20$. The scale of a single sample refers to the size of the initial node set. As shown in Table III, the capacity of sparse graphs is typically larger than that of dense graphs with the same node size. The primary distinction between sparse and dense graphs lies in the number of directed edges within the network, which directly influences network connectivity. This can also be observed from the average number of weakly connected components in the subgraphs presented in Table III. For networks with the same node size, the more edges they have, the fewer weakly connected components their subgraphs have on average. Generally, the subgraphs generated by samples are not necessarily connected but are composed of multiple connected components. Weakly connected components (WCCs) are defined as components where undirected edges replace all directed edges, and any two points within the component are reachable from one another. The number of connected components reflects the aggregation of the subgraph. A greater number of connected components indicates a more dispersed subgraph, while a smaller number of connected components signifies a more clustered subgraph.

The connectivity or structure of subgraphs is undeniably a crucial factor influencing network capacity, as it determines the resource usage of each subgraph. There are two main factors that impact subgraph connectivity: the scale of a single sample and network connectivity. Table III demonstrates that a larger scale of a single sample and better network connectivity will reduce network capacity. This observation is intuitive for the former but counterintuitive for the latter. However, when the scale of a single sample node is 0 or network connectivity is extremely poor, the network capacity tends to be 0. This suggests that the relationship between network capacity and subgraph connectivity is not linear.

Figure 7 shows the changes in network capacity and subgraph structure as the number of edges in a network increases. The node size of the network is 500, and the single sample scale is 60. It can be observed that the network capacity first rises and then declines, eventually stabilizing near the theoretical capacity value in the simple case, which is $\frac{nK}{s+c}$. During the stage of network capacity growth, both the average number of WCCs and the average number of nodes in the subgraph decrease, suggesting that the subgraph progressively transitions from ”dispersed” to ”clustered.” Subsequently, there is a sharp decline in network capacity, and the average number of WCCs in the subgraph also drops dramatically. This indicates that the network connectivity has reached a critical point, with almost all nodes in the subgraph belonging to the same WCC. As a result, the ”agglomeration effect” emerges. It means most initial nodes can connect directly without passing through other communicating nodes. When the network capacity reaches its peak, the average number of nodes in the subgraphs is close to the scale of a single sample, and the number of WCCs is slightly above 1.

Erdős and Rényi [26] demonstrated that when $p>\frac{(1+\epsilon)\ln n}{n}$, the ER random graph $G(n,p)$ is almost always connected. To ensure that the subgraphs generated by the samples have a high probability of only 1 WCC, it needs to guarantee that $p>\frac{(1+\epsilon)\ln s}{s}$, where $s$ represents the scale of a single sample, which is 60. Let’s take $p=\frac{\ln s}{s}\approx 0.07$. The generated subgraph in this scenario is shown in Figure 8a. If we take $p=0.04$, corresponding to the $p$ when the network capacity reaches its peak, the generated subgraph is shown in Figure 8b. It can be found that the essence of large capacity is actually the permutation and combination of multiple WCCs. When $p$ is slightly less than $\frac{\ln s}{s}$, the subgraphs generated by the samples are composed of a small number of WCCs. Assuming the subgraph is evenly divided into $t$ WCCs, the size of each WCC is $\frac{s+c}{t}$. The network capacity can be perceived as selecting $t$ WCCs from all possible ones. This is essentially a Uniform disordered grouping problem. The calculation result is shown in formula 1. Although the actual capacity is significantly smaller than this value, it still demonstrates the huge storage potential of the network.

Figure 9 demonstrates the capacity difference between a sparse graph and a dense graph, both with the same number of nodes. It can be observed that in the sparse graph, the average completeness of sample retrieval drops below 80% when the number of stored samples exceeds 8000. In contrast, for the dense graph, the average completeness of sample retrieval declines below 80% when the number of stored samples approaches 300. This capacity difference between the two networks further confirms that the arrangement and combination of WCCs are the essences of large capacity. Although the dense graph has more connections, its displayed capacity is not directly proportional to the number of resources owned by the network. Conversely, the sparse graph has only a small number of connections, but the network capacity achieved by the arrangement and combination of multiple connected subgraphs is several times that of the dense graph. This indicates that a sparse connection is a more reasonable mode, which can effectively save resources and obtain a larger network capacity. Moreover, the biological neuron network of the human brain also follows a sparse connection mode, implying that sparse connections are efficient and maximize the use of resources.

The fault tolerance testing primarily explores the effect of sample retrieval when the input is incomplete or has noise. The network used in the experiment is an ER random graph with 500 nodes and 3101 (sparse graph) and 12606 (dense graph) edges, respectively. The experiment first stores 1000 samples in the network, then modifies the sample inputs during the retrieval process. Finally, compare how the average accuracy and completeness change when the sample input is incomplete or has noise. There are three categories of modifications to inputs:

1. Removing a part of the original sample input to explore the impact of incomplete inputs on sample retrieval performance.

2. Adding extra noisy nodes to the original sample to investigate the impact of noise on retrieval.

3. Removing part of the original sample input and replacing it with an equal number of noisy nodes to examine the impact of sample retrieval in this mixed scenario.

Figure 10 shows that as more sample inputs are missing, the accuracy and completeness of retrieval decrease to varying degrees in both sparse and dense graphs. The change trends of the two networks are generally similar, and the decline in accuracy is relatively gentle. When the proportion of missing parts reaches 80% of the input, the rate of accuracy decline increases significantly. Compared to Figure 10b, Figure 10a has higher completeness and accuracy when the proportion of missing inputs is between 0.0 and 0.1. This is because the network capacity of the dense graph is small, making it difficult to achieve high reading accuracy and completeness after storing 1000 samples. The overall decline rate of completeness is greater than that of accuracy, indicating that the erroneous content obtained during retrieval does not increase as the proportion of missing inputs increases. This suggests that the algorithm is relatively reliable when facing missing sample inputs, although the rapid decline in completeness represents a significant amount of correct content that cannot be read. However, even when the proportion of missing inputs is as high as 80%, the retrieval accuracy can still be maintained at around 40% to 50%, which means that even if there are numerous missing inputs, almost half of the read content is correct and reliable.

Figure 11 shows the impact of increasing noise nodes. It can be observed that these additional noise nodes have relatively little effect on the accuracy and completeness of sample retrieval. The decline rate of completeness is lower than that of accuracy because adding noise nodes generally do not directly disrupt the original subgraph structure but makes the final subgraph larger. This demonstrates that the network has a relatively strong resistance to noise and is sensitive to the absence of sample inputs.

Figure 12 presents the performance of both incomplete and contained noise nodes in the sample input under sparse and dense graphs, respectively. It can be seen that the decline rate of accuracy and completeness, in this case, is the fastest, indicating that the impact of missing inputs and the effect of noise nodes can be superimposed.

It is known that neurons in the biological brain may experience various functional failures. How does this affect memory? This section primarily examines how the performance of sample retrieval changes when the network is damaged to different degrees. The test includes two main aspects: damage to some nodes and damage to some directed edges. The experiment first stores 1000 samples in the network, then deletes a certain proportion of nodes or directed edges and subsequently attempts to retrieve these samples while recording average accuracy and completeness changes. The network used in the experiment is an ER random graph with 500 nodes and 3101 edges (sparse graph) or 12606 edges (dense graph).

After a node or a directed edge is deleted, the activation traces recorded in the node’s internal index table will be affected. Assume that an index table contains two items: A,B,C → X,Y,Z and B,C,D → U,X,Z. If nodes A, D, and Z are deleted, does it need to delete the corresponding node in the activation trace recorded in its index table? If deleted, then these two items will become: B,C → X,Y and B,C → U,X. It can be observed that the input parts of these two items are the same, so addressing the different output parts is a challenge. Usually, during the initial period after network damage, nodes are hard to respond, and at this time, the original traces stored in the node index table will not change. As the damage duration increases, nodes may gradually make corresponding adaptive adjustments to the damaged network. Given the above two different situations, this paper proposes four restoration schemes, as shown in Table IV, and compares these four solutions.

Figure 13 demonstrates the impact of partial node damage on sample retrieval performance. Figure 13a and Figure 13b respectively display the changes in average accuracy and completeness of sample retrieval in the sparse graph for the four restoration schemes. In terms of average accuracy, the scheme that maintains the original traces performs the best, the scheme that takes the union performs the worst, and the other two schemes exhibit similar performance. Conversely, in terms of average completeness, the results are reversed. The scheme that takes the union performs the best, while the one that maintains the original traces performs the worst. This is because the union-taking scheme increases the number of activated nodes, which includes both incorrect and correct nodes. The former leads to a decrease in accuracy, while the latter leads to an increase in completeness. Figure 13c and Figure 13d present the results on the dense graph, revealing that when the network has a large number of edges, the differences between the four restoration schemes progressively diminish. This occurs because when network connectivity is high, the number of communication nodes in the subgraph generated by the sample is small, with most initial nodes being directly connected. Consequently, the accuracy remains consistently high. The frequency at which each node is shared by different samples is also reduced, so when a node is deleted, the number of samples it affects decreases, making the differences between the four solutions less noticeable.

Figure 14 shows the impact of partial directed edge damage on sample retrieval. Since a node only has a local view, it can receive and transmit the information of neighboring nodes solely through its fan-in and fan-out edges. Node damage can be understood as the interruption of all fan-in and fan-out connections, so the impact on neighboring nodes is essentially the same, whether node damage or directed edge damage. Consequently, the same restoration schemes can be used. Figure 14a and Figure 14b respectively display the changes in average accuracy and completeness of sample retrieval for the four restoration schemes in the sparse graph. Their trends are almost consistent with Figure 13a and Figure 13b. Regarding accuracy, the notable difference between the two is that in the interval [0.8,1.0], Figure 14a maintains relatively high accuracy. Regarding completeness, the curve of Figure 14b is comparatively flat. Figure 14c and Figure 14d are the results of dense graphs. The results are also consistent with those of Figure 13c and Figure 13d. The difference is the same as that observed in the sparse graph, which indicates that the network is significantly more tolerant of directed edge damage than node damage, as nodes hold information while edges do not.

The information storage and retrieval algorithm proposed in this paper is closely related to the network structure. Firstly, the algorithm utilizes the subgraph structure as the information storage carrier, and secondly, the subgraph formation depends on stimulus propagation. Both of these characteristics emphasize the importance of the network structure for the algorithm. Therefore, different network structure characteristics are key factors affecting the algorithm’s performance.

Figure 15 showcases six classic network structures. Figure 15a is the ER graph with $p=0.1$. Figure 15b represents a globally coupled network, also known as a fully connected network. Figure 15c shows the nearest-neighbor coupled network, characterized by $N$ nodes arranged in a ring, with each node establishing connections to its left and right $L$ neighbors, respectively. Figure 15d illustrates a star coupled network, featuring a central node to which all other nodes are connected. This characteristic causes any path between two points in the network to include the central node, creating a bottleneck for the entire network capacity. Figure 15e presents a one-dimensional Kleinberg network [27], a small-world network [28]. The network is constructed by adding a few random edges to the nearest-neighbor coupled network. Figure 15f displays the Price network [29], which is a scale-free network. The network’s generation relies on the preferential attachment mechanism, where newly added nodes are more likely to connect to nodes with higher degrees. Since each newly added directed edge point from the new node to the old node, there are no loops in the network, leading to a significant decrease in network connectivity and capacity.

Evaluation parameters for different network structures typically include average path length and clustering coefficient.

Average Path Length: Defined as the average of the shortest path lengths between any two points in the network. The default shortest path length is usually positive infinity if the two nodes are disconnected. This special case is common in directed graphs. To prevent the calculation result from being positive infinity, this paper uses the harmonic mean [30] of the distance between any two nodes in the network to represent the average path length.

$N$ represents the number of network nodes, and $d(i,j)$ represents the shortest distance between node $i$ and node $j$. $GE$ represents network communication efficiency, with its essential idea being that the closer the node path distance in the network, the higher the communication efficiency. The average path length calculated by the formula 2 [30] solves the problem of the value being positive infinity when the network is disconnected. Therefore, it is more suitable for evaluating directed graph network structure.

Clustering coefficient: This metric is used to measure whether the nodes in the network exhibit aggregation characteristics. This paper adopts the calculation method of the clustering coefficient in directed graphs proposed by Fagiolo [31].

Table V displays the test results of six network models with different structures but similar scales. The number of nodes in all test networks is 1000, and the single sample scale is 60. The ER random graph exhibits a small clustering coefficient and average path length, while the nearest-neighbor coupled network has a large clustering coefficient and average path length. The Kleinberg directed small-world network has a large clustering coefficient and a small average path length. Kleinberg’s directed small-world and nearest-neighbor coupled network demonstrate relatively excellent network capacity among these six network types. Figure 16 illustrates examples of sample storage corresponding to the two networks. A common feature observed in both networks is the presence of numerous small WCCs. As previously mentioned in the network capacity analysis, the essence of large network capacity lies in the arrangement and combination of WCCs. Since both networks have relatively high clustering coefficients, it is quite easy to form small components locally. Each subgraph can be considered a combination of several small components, resulting in a higher network capacity. The reason for the higher capacity of the Kleinberg network is that, due to its lower average path length, it is easier to form some large WCCs. These large WCCs not only exhibit higher distinguishability but also have a higher resource reuse rate for their nodes, thus positively impacting the improvement of network capacity. In contrast, these characteristics are not present in the ER random graph. Due to its low clustering coefficient and average path length, most weakly connected components formed by the ER random graph are large in scale. This is the difference in capacity caused by different network structures.

In this paper, we employ subgraphs as physical carriers for information storage and leverage nodes’ autonomous adaptive learning behavior to achieve a large-capacity and stable directed graph storage model. The individual nodes’ learning behavior does not need a global view, meaning that the tiny algorithms operating within each node do not work under strong central control and are entirely decentralized. Both the learning behavior and the supporting hardware resources are fine-grained and distributed and can, in theory, be highly parallel in physical implementation.

The storage capacity of the network depends on factors such as connectivity and network structure. The dense graph has better connectivity, the subgraphs generated by the samples are usually gathered together, and the communication nodes are rarely used. The measured capacity at this time is low, approaching the theoretical capacity limit that disallows resource reuse. Sparse graphs exhibit poor connectivity, and the sample-generated subgraphs are generally more dispersed, often consisting of several weakly connected components. In this case, the sample-generated subgraphs can be viewed as a permutation of connected components, significantly increasing the network capacity. Tests have shown that a sparse random directed graph with 500 nodes and 3101 edges can store nearly 8000 memory samples with over 80% accuracy and completeness. In contrast, a dense graph with 500 nodes and 12606 edges can only store around 300 memory samples.

Sparse graphs have fewer resources than dense graphs, but the actual number of samples they can store is tens of times more than dense graphs. It demonstrates that resource abundance is not the sole factor determining network capacity. The network’s structural properties, such as connectivity, clustering coefficient, and average path length, are also crucial. Biological neuronal networks exhibit sparse connections and show large capacity and low power consumption characteristics. To some extent, this paper also provides a possible explanation for how biological neuronal networks can achieve memory functions.