A Role for Chordless Cycles in the Representation and
Retrieval of Information
John L. Pfaltz
Dept. of Computer Science
University of Virginia
ABSTRACT cycles” which we believe play a prominent role in the rep-
This paper explains how very large network structures can resentation of biological information, and which we believe
be reduced, or consolidated, to an assemblage of chordless can be exploited in computer applications as well. In Section
cycles (cyclic structures without cross connecting links), that 2.1 we sketch the mathematical foundations for this notion,
is called a trace, for storage and later retreival. After de- which is based on concepts of “closure”. In Section 2.2 we
veloping a basic mathematical framework, it illustrates the present computer code that will reduce any network to its
reduction process using a most general (with directed and constituent chordless cycles. Then in Section 2.3 we can de-
undirected links) network. scribe the desirable properties of representing information
A major theme of the paper is that this approach appears by these cycles and indicate their role in biological memory.
to model actual biological memory, as well as offering an Our goal in this paper is to use some relatively abstract
attractive digital solution. graph-theoretic concepts to effectively model, and bring to-
gether, both biological and computer applications.
Keywords
2. REPRESENTATION AND STORAGE OF
Closure, biological memory, reduction, consolidation, recall,
trace, subgraph matching, directed graphs INFORMATION
Our basic understanding of the world, whether visual,
1. INTRODUCTION oral, or tactile, is neural in nature. The representation of
data in regular arrays is, to a large extent, an artifact of
A central tenet of database theory is that it is the re-
computer architecture and the ease of algebraic manipula-
lationships between various entities that constitute real in-
tion. So we begin with the assumption that all “information”
formation. It is the foundation of the relational model [7].
is a graph structure of some form.
But, in those situations where there are millions of entities
To our knowledge, there has been no agreement as to what
and the relationships are relatively sparse, the familiar array
neural configurations correspond to any specific empirical
style representation of data simply won’t work. We turn to
sensations or mental concepts; but there have been many
graph, or network, type representations. In other situations,
studies documenting that all perception and cognition corre-
such as social network analysis, the data is naturally graph
late with neural activity, even detailing its occurrence with
structured. In any case, we are concerned with the retreival
specific locations within the brain [11, 16, 15, 18, 21, 39,
of specific “chunks” of the stored information.
40]. However, we are fairly confident that whatever neural
We will contend that retrieval of information from a stor-
networks do correspond to specific sensations, concepts or
age medium is not a single, unified operation; that there are
knowledge, they are very large — probably in the millions
at least two distinct phases. First the desired information
of elements, or possibly even billions, as discussed in [43].
must be identified and located within the storage medium.
We are talking about a very large data space!
We call this “information access” and address it in Section
The most general mathematical model of neural activity
3. Then it must be read out or, in the case of biological
appears to be a directed graph. So the fundamental assump-
memory, reconstituted. This latter step we call “recall” and
tion of this paper is that, at its most basic level, information
discuss it in Section 4.
retrieval involves locating and obtaining rich directed graph
However, this paper is less concerned with actual retrieval
structures based on simpler representations which serve as
than discovering graph structures which facilitate this pro-
query keys. We are not retrieving array-type information to
cess. In Section 2.3 we introduce the concept of “chordless
display on a spread sheet.
For this paper we assume that the network structure is
the “information”, independent of any edge or node labels.
2.1 Information as Relationships
Information and knowledge are essentially relational. El-
2017, Copyright is with the authors. Published in the Workshop Proceed- ements, or neurons, are related to other elements. To our
ings of the EDBT/ICDT 2017 Joint Conference (March 21, 2017, Venice, knowledge, neurons are not “labeled”. In contrast, most sub-
Italy) on CEUR-WS.org (ISSN 1613-0073). Distribution of this paper is
permitted under the terms of the Creative Commons license CC-by-nc-nd graph matching algorithms assume their nodes, or elements,
4.0 are labeled [8, 24, 43]. These labels can be used to prune
in plain graph search procedures [8], or the basis for hash- can be combined with little loss of information. We say that
based join algorithms [41, 42]. Because we assume unlabeled y has subsumed z, or equivalently that z belongs to y. By
and unweighted edges, this paper can be regarded as an ex- y.β we mean all nodes, z that belong to y, that is have been
ercise in pure graph theory. However, we believe it provides combined. Readily y ∈ y.β. The pseudo code for a process
insights into both biological and computer retrieval. we call “reduction”, and denote by ω, is shown below in Fig-
There seem to be many different kinds of relationships; ure 2. The outer loop terminates when every element y is
however, we abstract them all by a single relational sym-
bol, η. By y.η we mean the set of all elements related to while there exist subsumable nodes
y. For set valued operators, such as η, we use a suffix no- {
for_each y in N
tation. It helps remind us that they are not scalar valued {
functions. If we represent information as a network N , y.η get {y}.nbhd
would denote the neighbors of y in N . So one can read y.η for_each z in {y}.nbhd - {y}
simply as y’s neighbors. (For mathematical convenience we {
assume η is reflexive, so y ∈ y.η.) Visually, η represents the if ({z}.nbhd contained_in {y}.nbhd
edges of the graph, or relational network. (We use the terms { // z is subsumed by y
combine z with y
node and element and graph and network interchangeably.) add z to {y}.beta
It is unknown whether information networks are directed }
or undirected. To assume a measure of generality we will }
assume they are mixed, with some links being directed and }
some undirected. While Figure 1 is far too small to be a real }
information network, we will use it to illustrate concepts of
this paper. Arrow heads denote directed edges; if there are
Figure 2: Pseudo code of the reduction, ω, process.
y C
f o
u D itself a closed set. A network with this property is said to
k
p z
be irreducible. A C ++ version of this code has been applied
b
to a variety of social networks [33, 34]. The actual code is
g l v E
“set based” where constructs such as y.nbhd and y.beta are
q A
c
implemented as bit strings. Thus operations are effectively
h m w F O(1). There is no apriori constraint on set size, but we have
a
e
s
not executed operations with sets of cardinality > 50, 000.
B
i r It can be rigorously demonstrated that the reduction of a
n
network, N , which we denote by T = N .ω is unique (upto
d t x
j isomorphism). ω is a well-defined function over the space of
all networks. We call T the trace of the network N .
Figure 3 illustrates the trace T of the network N of Figure
Figure 1: A representative “information network”.
1. Emboldened solid links, or edges, connect the nodes that
none the link is bi-directional, or symmetric.
y C
An important principle for interpreting information net- o
f
works is the concept of “closure”. Closure is well defined in u D
k
mathematics [6, 26, 22]. There are many different kinds of p
b z
closure operators; the most intuitive is the convex hull of ge-
g l v E
ometric figures [2]. We will use the fundamental relational
q A
operator, η, to define a closure operator, ϕ. Specifically, c
h m w F
y.ϕ = {z|z.η ⊆ y.η} (1) e
a s B
i r
that is, z is an element of y closure, y.ϕ, if all elements
related to z are also related to y. (ϕ can be extended to d n
t x
j
arbitrary sets, Y , by Y.ϕ = ∪y∈Y {y.ϕ}.) The concept of
neighborhood closure underlies the entire development of
this paper. In the network of Figure 1, c.ϕ = {abc}, p.ϕ = Figure 3: A network N with mixed relational links.
{op} and g.ϕ = {bgl}. It is worth convincing yourself why Solid links represent those retained after reduction
this is so. For a more detailed development see [34, 37, by ω.
38], where it is shown that computing closure, ϕ, is a local
operation. remain in T after the reduction process; thiner dashed lines
connect the nodes that have been combined with others..
2.2 Consolidation Dashed lines enclose the 7 non-trivial β-sets; for example
As defined by (1), an element z in y closure, y.ϕ, is rela- c.β = {a, b, c} and z.β = {v, y, z, D, C}.
tionally connected to no more elements than y itself. Con- Observe that a new link (f, c) was created to preserve
sequently, those elements within a network which are con- path connectivity through b. We also see that ϕ and β are
tained in the closure of other elements contribute very little distinct operators since although c.ϕ = c.β, g.ϕ ⊂ g.β.
to the information content conveyed by the network. They Of the original 32 nodes, only 17 remain after reduction
which represents a considerable storage compaction. through z terminating in a chordless cycle of length ≥ 4.
The reduction process, ω, has a number of desirable com- Even when the relation is non-symmetric, chordless cycles
putational properties. Because the closure operator, ϕ, is dominate the reduced representation.
local (it need only interrogate adjacent elements), it can be Are chordless cycles really fundamental in the representa-
executed as a parallel process. (The code of Figure 2 that tion of biological information?
we have actually used is sequential1 , but it is evident how We can provide no definitive answer to that question. We
to convert the outer loop.) This is particularly important can point out that protein polymer molecules composed of
for biological information storage and retrieval. The paral- chordless cycles exist in every cell of our bodies [45]. One
lel application of a similar closure based process within the example is a 154 node phenylalaninic-glycine-repeat (nuclear
visual pathway is described in [36]. pore protein), N , which is shown in Figure 4. This is not at
We have devoted considerable space to a description of ω
because, in addition to preparing information for storage,
we believe it plays a prominent role in retrieval as described
in the next sections.
In the literature devoted to human “memory”, there has
been considerable research suggesting that there is a process
that converts short-term memory into long-term memory. It
is usually called “consolidation” [1, 4, 9, 25, 28]. It appears
to be quite similar to the reduction process described above,
whence the subsection heading is “consolidation”.
2.3 Chordless Cycles
A chordless cycle is most easily visualized as a string of
pearls with no cross connections. More precisely, a chord-
less cycle is a sequence < y1 , y2 , . . . , yn , y1 > of elements
yi , 1 ≤ i ≤ n of length n ≥ 4 where there exist no links
(chords) of the form (yi , yk ) k 6= i ± 1, i, k 6= 1, n.2 It is
better to just think of them as paths with no single edge Figure 4: A 3D rendering of a 154 node protein
cross connections. In Figure 3, the sequence, or path, < polymer molecule.
c, g, m, i, d, c > is a chordless cycle of length 5 The sequence
< n, q, p, u, z, A, B, x, t, n > is a chordless cycle of length 9. all like the dense network of Figure 1. Nevertheless, one can
If the relation η between elements is symmetric, it can be easily see the chordless loops, with various linear tendrils
proven [34, 35] that if N is irreducible (i.e., every node is attached to them. When these are removed by ω, there
a closed set) then every node y is either (1) isolated, (2) were 107 remaining elements involved in the chordless cycle
an element of a chordless cycle of length ≥ 4, or (3) an el- structure.
ement on a path between two such chordless cycles. Thus If we count [10, 23] the numbers of chordless cycles of
the trace (consolidation or reduction) of a symmetric rela- length n in the reduction of Figure 4, we obtain the distri-
tional network is a collection of interlinked chordless cycles. bution of Figure 5. The average cycle length is 44.9 in this
In Granovetter’s analysis of social networks [19], these are
the “weak ties”.
2400
When η is symmetric, ω readily preserves path connectiv- 11
00
0
1
00
11
00
11
00
11
0
1
2200 00
11
00
11
00
11
0
1
00
1100
11
ity within T . It also preserves the distance between elements 00
11
0
100
11
0
1
00
11
00
11 0
1
00
11
0
100
11
0
1
00
11
00
11 0
1
00
11
2000 0
1
0
10
100
11
0
1
00
11
00
11
00
110
1
00
11
0
1
0
10
10
1
00
11
00
11 0
1
00
11
as measured by shortest paths [35], together with the center 0
1
0
10
1
0
1
0
1
0
1
0
100
11
0
1
00
11
00
11
0
100
11
0
1
00
11
00
11
0
1
00
11
0
1
00
11
0
1
0
1
1800 00
110
10
1
0
10
100
11
0
1
00
11
00
11 0
1
00
11
00
11 0
10
1
of N as determined by distance which will be found in T , 00
11
00
110
10
1
0
10
10
1
00
11
00
11
00
110
1
00
110
10
1
00
110
1
0
10
1
0
10
10
1
00
11
00
11
00
110
1
00
110
1
0
10
1
0
1
0
10
10
1
00
11
00
11 0
1
00
11 0
1
# of cycles of length n
1600 00
110
10
1
0
10
100
11
0
1
00
11
00
11 0
1
00
11
00
11 0
10
1
as will those centers as defined by “betweenness” [5, 13, 14]. 00
11
00
110
10
1
0
10
10
1
00
11
00
11 0
1
00
11
00
11 0
10
1
0
1
00
11
00
110
10
1
0
10
10
1
00
11
00
11
00
110
1
00
110
10
1
0
1
1400 00
11
00
110
1
0
10
1
0
10
10
1
00
11
00
11
00
110
1
00
110
1
0
10
1
0
1
00
11 0
1
0
10
10
1
00
11
00
11
00
110
1
00
11 0
1
0
1
Symmetry of the relation η is a powerful property. But, 00
11
00
11
00
110
1
0
10
1
0
1
0
1
0
1
0
1
0
10
1
00
11
00
11
00
11
0
1
00
11
00
11
0
1
00
11
0
1
00
11
0
1
0
10
1
0
1
0
1
00
11
00
11
00
11 0
10
1
0
10
100
11
0
1
00
11
00
11 0
1
00
110
10
1
0
10
1
1200 00
11
00
11
00
11 0
1 0
100
11
0
1
00
11 0
1
00
110
10
1
0
10
1
to better model real relationships we have relaxed this con- 00
11
00
11
00
11
00
11
00
11
00
110
1
0
1
0
1
0
1
0
1
0
100
11
0
100
11
0
1
00
11
00
11
0
100
11
0
1
00
11
0
1
00
11
0
1
00
11
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
10
1
1000 00
11
00
1100
11
00
11
00
11 0
10
1
0
100
11
0
100
11
0
1
00
11 0
1
00
110
10
1
0
10
10
1
straint throughout to allow directed (non-symmetric) con- 00
1100
11
00
11
00
11 0
10
1
0
1
0
1
0
100
11
0
100
11
0
1
00
11 0
1
00
110
10
1
0
10
10
1
00
11
0
100
11
00
11
00
11 0
10
1
0
100
11
0
100
11
0
1
00
11
00
11 0
1
00
110
10
1
0
10
10
1
00
11
0
100
11
00
11
00
11 0
10
1
0
10
100
11
0
1
00
11
00
11 0
1
00
110
10
1
0
10
10
1
800 00
11
0
100
11
00
11
00
11 0
10
1
0
10
100
11
0
1
00
11
00
11 0
1
00
110
10
1
0
10
10
1
00
11
0
1
nections. Under these conditions the preceding characteriza- 00
11
0
100
11
00
11
00
11 0
10
1
0
10
100
11
0
1
00
11
00
11 0
1
00
110
10
1
0
1 0
1
00
11
0
1
00
11
0
100
11
00
11
00
11 0
10
1
0
10
100
11
0
1
00
11
00
11 0
1
00
110
10
1
0
1 0
1
00
11
00
11
0
1
00
11
0
1
0
100
11
00
11
00
11
00
110
10
1
0
10
100
11
0
1
00
11
00
11 0
1
00
110
10
1
0
1 0
1
00
11
00
11
0
1
600 0
1
00
11
0
1
0
100
11
00
11 0
10
1
0
10
100
11
0
1
00
11 0
1
00
110
10
1
0
1 0
1
tion of irreducible networks is no longer valid. For instance, 0
1
00
11
0
10
1
0
100
11
00
11
00
11
00
11
0
100
11
00
110
1
0
10
1
0
100
11
0
100
11
0
1
00
11
00
11
0
100
11
0
1
00
11
0
1
00
11
0
1
00
11
0
1
0
1
0
1
0
1
0
1
0
1
00
11
00
11
0
10
1
00
11
00
11
0
10
1
0
10
10
1
00
11
00
11
0
100
11
00
110
10
1
0
100
11
0
100
11
0
1
00
11 0
1
00
110
10
1
0
100
11
00
11
0
10
1
00
11
400 0
10
10
1
00
11
00
1100
11
00
110
10
1
0
100
11
0
100
11
0
1 0
10
10
100
11
00
11
0
10
1
the node f in Figure 3 is not an element of a chordless cycle. 0
1
0
1
0
10
10
1
0
1
00
11
00
11
0
1
0
100
11
00
11
00
11
00
11
00
110
1
0
1
0
1
0
1
0
1
0
1
00
11
00
11
0
1
00
11
00
11
0
1
00
11
00
11
0
1 0
1
00
11
00
11
0
1 0
1
0
1
0
1
0
1
0
1
0
1
0
1
00
11
00
11
00
11
0
10
1
00
11
00
11
0
1 00
11
00
11
00
110
10
1
0
10
1
00
11
0
1
0
1
00
11
00
11
00
110
10
1
0
100
11
00
11
0
1 00
11
00
11
0
1 0
10
10
1
0
1 0
1
00
11
00
11
0
1 00
11
00
11
200 00
11
00
11
00
110
10
1
0
10
1
00
11
0
1
0
1
00
11
00
11 0
1
0
100
11
00
1100
11
00
11 0
1
0
1 0
1
00
11
00
11
0
1 00
11
00
110
1
In the case of non-symmetric networks we must ensure 1
000
11
00
11
0
1
0
100
11
00
11
00
11
00
11
0
1
0
10
1
0
1
0
1
0
1
0
1
00
11
0
10
1
0
1
00
11
0
1
0
1
00
11
00
11
00
11
00
11
00
11
00
11
0
1
0
10
1
0
1
0
1
0
1
0
1
0
10
1
00
11
00
11
00
11
0
1
00
11
00
11
0
1
00
11
0
1
00
11
0
1
0
10
1
0
1
0
1
0
1
0
1
00
11
00
11
0
10
1
00
11
00
11
0
1
00
11
00
110
1
00
11
00
110
10
1
1
0
1
01
0
11
00
11
00
11
00
11
001
0
1
01
0
11
00
1
0
11
00
1
011
00
11
001
01
0
1
000
11
0
1
0
100
11
00
11
110
1
00 1
00
1
00
11
01
1 0
0
100
11
00
11 0
1
00 1
11 0
0
10
100
11
0
1
00
11
00
11
00
110
10
10
1
00 1
11 0 0
1
00
11
00
11
0
1 00
11
00
110
10
11
0
path connectivity through subsumed nodes. Let y subsume
cycle length, n 5 10 15 20 25 30 35 40 45 50 55 60 65
z, i.e. z.η ⊆ y.η. For all x such that z ∈ x.η we ensure
that y ∈ x.η. This is always true when η is symmetric, but
required the creation of the edge (f, c) in Figure 3. In this Figure 5: The distribution of chordless cycles in a
case, we can show [38] that if N is irreducible then for all 107 element network.
y, if there exists z ∈ y.η, z 6= y, there must exist a path network; the modal length is 48; and the 4 longest chord-
1
It can be shown that worst case sequential behavior is less cycles have length 65. It is clear that the combinatorial
O(n2 ), but actual performance is much better with a maxi- possibilities based on cycle lengths alone would permit the
mum of 6 iterations to reduce 1,000 node real networks. representation of a considerable amount of information.
2 These are only indications that chordless cycle structures
A graph with no chordless cycles is said to be chordal.
There is an extensive literature on chordal graphs, e.g. [27] might be an important component of relational information
representation. The following sections will show how they Imagine “sliding” an unlabeled 600 irreducible subgraph
can be involved with the retrieval process. around over an irreducible million node network to find a
match, if one exists.
A method that we are beginning to explore involves the
3. INFORMATION ACCESS network providing information about its own irreducible struc-
Information cannot be retrieved unless it is first identi- ture. To do this we label each edge with the length of the
fied and located within storage. Pointers and URLs identify “shortest” chordless cycle of which it is a member. This is
storage locations. But, lacking these, one must search based not an artificial data label, but an element of the network
on the “content” of the desired information. An early, and representation itself. Thus, in the irreducible network of Fig-
still common, mechanism is to attach key words or hash ure 3, the edge (q, p) would be labeled with a 7 because it is
tags to the information, which are then used to create an a member of the chordless 7-cycle < q, p, k, g, c, d, i, m, q >.
easily searchable index [3, 17, 30, 31], in the case of hashed This same edge is a member of longer cycles such as the
storage, to directly control the storage location [12] or to 9-cycle, < q, p, u, z, A, B, x, t, n, q >, but we only label with
perform hash-joins in relational databases [42]. respect to the shortest.
As access speeds have increased so dramatically, both of The edge (m, q) would be labeled with a 4, as would the
the preceding access techniques have often been superceded edge (m, p). Each edge in the reduced search key, K.ω, of
by simple linear search and comparison. Figure 7 must be labeled with a 4.
But, this still presumes that the “content identification” is Each edge label of the search key must be exactly equal
based on specific terms, or tokens. If important information to the corresponding edge label in the larger network. So,
is based on relationships, as we have asserted in Section 1, based solely on the edge labeling, the only possible matches
then such token based search is rather limited. for this reduced key of Figure 7 in the reduced network of
Suppose we wish to retrieve within a relational network. Figure 3 are the 4-cycles < g, m, p, k, g >, < n, q, m, i, n >
We may assume that the search key, K, is itself relational. and < w, A, B, x, w >.
It might look like Figure 6, but very much larger! Edge labeling with respect to shortest chordless cycle length
7
eliminates fruitless search expansion, but it can’t indicate
4
likely places to begin the comparison. The central retrieval
2 problem is identifying likely nodes within the larger network
6 8
to initiate the search comparison.
3 We believe that the solution lies with the imbedded “tri-
1 angles”. Even though they are not chordless cycles of length
5
≥ 4 of which an irreducible network is comprised, they do
exist, provided each edge is a member of a distinct chord-
Figure 6: A structural search key, K.
less cycle of length ≥ 4. In the reduced network of Figure 3
there is one embedded triangle, that is < q, p, m, q >, with
Reduction of K by ω yields its trace K.ω, as shown in associated cycle labels < 7, 4, 4 >. There is no embedded
Figure 7. It is a simple cycle on the nodes < 4, 3, 6, 7, 4 >. triangle in the reduced search key of Figure 7. This is un-
4 7
usual; but it is because the search key is “too small”. Our
observation is that most reduced networks of 20 nodes, or
2
6
more, have at least one embedded triangle. The network of
8
Figure 4 has five, with associated cycle lengths of < 8, 6, 4 >,
3 < 12, 5, 5 >, < 12, 7, 4 >, < 14, 10, 7 > and < 16, 8, 6 >. If
1
5
the reduced search key contains any embedded triangle, it
must match one of these.
Figure 7: Its reduction, K.ω. In our JMC approach to information access, we 1) as-
sociate with each edge (functional relationship) in η the
length of the shortest chordless cycle to which it belongs;
Comparing Figure 7 with the trace of Figure 3, we see the
and 2) create an external index of shortest length triples
obvious subgraph matching: 3 ↔ m, 4 ↔ g, 6 ↔ p and
corresponding to embedded triangles. Assuming the search
7 ↔ k. In this small example there is only one possible
key is sufficently well specified to include an embedded tri-
matching chordless cycle. In the kinds of large networks we
angle, we first search this index of triples to identify one, or
envision this is not so simple!
more, plausible search regions within the multi-million node
Imagine a 1,000 node seach key which reduces to a key
reduced network constituting the data store.
trace K.ω, of say, 600 nodes. To find a matched subgraph
This access mechanism is now being implemented, so its
in a reduced network of several million nodes is a combina-
actual efficency is still unknown. We believe it has consider-
torialy impossible task. All subgraph matching algorithms,
able promise. More uncertain is whether the edge labeling
known to the author, assume some form of node and/or
and triangle index can be maintained in real time as the
edge labeling to initiate the search location and to control
network changes dynamically [34]. Our hope is that if the
the expanding search [8, 24, 43]. Various forms of auxil-
network changes are continuous [32], then there exist effec-
liary indices provide direct access to graph elements match-
tive update procedures.
ing those labels. However, while the retrieval of informa-
The approach described in this section seems quite ap-
tion from a graph structured data store implicitly assumes
propriate to biological recall as well. We see “Mary” in the
a labeled graph, we have focused in this paper on the rela-
market. This is a visual experience involving many relation-
tionships embodied in the network itself. There are no data
ships. A rapid, almost instantaneous, search through our
labels.
memory yields a much larger relational information struc- Clearly, there are significant advantages, in terms of many
ture, including her name, her age and the names of her 3 fewer nodes and links, to representing network data in this
children. This is often called semantic memory in the liter- fashion. Readily, real information stores, whether computer
ature [16]. generated or biological, may have differentiated (i.e. labeled)
nodes and links. Nevertheless, this first treatment of the
4. RETRIEVAL OF RELATIONAL INFOR- problem as a purely abstract, graph theoretic issue has value.
It provides a theoretical basis for more applied work.
MATION We have suggested that subsets of the stored informa-
We suppose that a reduced trace, T = N .ω, or a portion tion can be identified and retreived by similarly reducing the
of it, has been identified as in the preceding section. During search key. Then, in Section 3, using graph-theoretic proper-
the reduction process, ω, used to consolidate the network in- ties arising from the fact that irreducible networks consisting
formation we need not store only the resulting trace. We can of chordless cycles, we have sketched an access method that
also represent various steps in the reduction process. Our might support retrieval based solely on relational structure.
own code, for example, records y.β for each retained node y. In biological organisms, this or an associative memory ap-
Thus, if the trace of Figure 3 was accessed given the key of proach may be used.
Figure 7 then we would know that c.β = {a, b, c}. Moreover, The next to last paragraph of Section 4.1 mentions a re-
we know the order in which a and b were subsumed by c. construction process ε which functions as a kind of inverse
From this, a very close approximation of the original net- operator to ω. This may be the most important observa-
work of Figure 1 can be recreated. But, there will still be tion of the paper. We are just beginning to explore it. If
some loss of information. For instance, the connection be- there is a way, given a trace T , to reconstruct a network
tween f and b would be lost. More complete information N 0 which closely approximates the original network N , this
could be stored with each subsuming node, though at some could have profound implications for both computed and
increased storage expense. Alternatively, the complete infor- biological applications.
mation network, N , could be stored, with the trace network,
T , separately stored as an easily searchable index.
It is our belief that with information structures of this
6. REFERENCES
[1] Sir Fredrick Bartlett. Remembering: A Study in
size, retrieval of close approximations, i.e. the trace itself, Experimental and Social Psychology. Cmbridge Univ.
will be sufficient for most applications. Press, Cambridge, UK, 1932. Paperback version, 1967.
[2] Jon L. Bentley. Approximation Algorithms for Convex
4.1 Biological Recall Hulls. Comm. ACM, 25(1), Jan. 1982.
[3] Christian Böhm. A Cost Model to Query Processing in
Biological recall is likely to be somewhat different from
High Dimensional Spaces. ACM Trans. on Database Sys.,
a largely deterministic computer recall. There is some ev- 25(2):129–178, June 2000.
idence that biological organisms only store an abbreviated [4] Clive R. Braham and Eloucine Messaoudi. BDNF function
trace and that the memory, as we experience it, is somehow in adult synaptic plasticity; The synaptic consolidation
“recreated” [20]. This helps explain why human memories hypothesis. Progress in Neurobiology, 76(2):99–125, 2005.
can be distorted in specific detail, yet correct in their overall [5] Ulrik Brandes. A Faster Algorithm for Betweeness
structure. Centrality. J.Mathematical Sociology, 25(2):163–177, 2001.
In [38], the author describes a semi-random expansion pro- [6] G. Burosch, J. Demetrovics, G.O.H. Katona, D.J.
Kleitman, and A. Sapozhenko. On the Number of
cess, ε, that fills in subsumed nodes to create a richer net-
Databases and Closure Operations. Theoret. Comput. Sci.,
work N 0 . In many respects, ε is an inverse operator to ω. 78(2):377–381, Jan. 1991.
Given a trace, T , T .ω −1 defines the collection of all networks [7] E. F. Codd. A Relational Model for Large Shared Data
{N ∗ } such that N ∗ .ω = T . ε constructs a single network, Banks. Comm. ACM, 13(6):377–387, June 1970.
N 0 , within this collection. Thus, given an initial network, [8] L. P. Cordella, P. Foggia, C. Sansone, and M. Vento. A
N , ε will “retrieve” N 0 which may, or may not, be (isomor- (sub)graph isomorphism algorithm for matching large
phic to) N . However, we are assured that N 0 .ω = T = N .ω, graphs. IEEE Trans. Pattern Analysis and Machine Intell.,
or N .ω.ε.ω = N .ω = T . 26(10):1367–1372, 2004.
[9] Robert G. Crowder. Principles of Learning and Memory.
Such a semi-random “retrieval” process may be completely
Psychology Press, New York, 2015.
inappropriate in computer applications, but it seems to model [10] Elisângela Silva Dias, Diane Castonguay, Humberto Longo,
biological recall rather well. Our memories often are con- and Walid A. R. Jradi. Efficient enumeration of chordless
fused with respect to detail, even when they they are gener- cycles. arXiv:1309.1051v4, 24 Nov. 2014.
ally correct. It also supports the notion of “re-consolidation” [11] Yadin Dudai. The Neurobiology of Memory: Concepts,
which asserts than long-term memories are repeatedly re- Findings, Trends. Oxford University Press, Oxford, 1989.
written, unless deliberately distorted in our (semi)conscious [12] R. J. Enbody and H. C. Du. Dynamic hashing schemes.
mind [28, 29, 44]. COMPSUR, 20(2):85–113, June 1988.
[13] Linton C. Freeman. A Set of Measures of Centrality Based
on Betweenness. Sociometry, 40(1):35–41, 1977.
5. SUMMARY [14] Linton C. Freeman. Centrality in Social Networks,
The representation of complex networks by a trace com- Conceptual Clarification. Social Networks, 1:215–239,
prised of chordless cycles has a firm, well defined basis. We 1978/79.
know that there exists an effective procedure ω to reduce a [15] J.D.E. Gabrieli. Cognitive Neuroscience of Human Memory.
Annual Review of Psychology, 49:87–115, 1998.
network N to its trace T by local and easily parallelizable [16] John D.E. Gabrieli, John E. Desmond, Jonathan B. Demb,
code, such as might be found in the visual pathway. It is also Anthony D. Wagner, Maria V. Stone, Chandan J. Vaidya,
known that such chordless cycle assemblages exist as protein and Gary H. Glover. Functional Magnetic Resonance
polymers in all the cells of the body, including synapses. Imaging of Semantic Memory Processes in the Frontal
Lobes. Psychological Science, 7(5):278–283, Seot, 1996. Mathematics for Applications, 6(1):(to appear), 2017.
[17] Volker Gaede and Oliver Günther. Multidimensional Access [39] Dale Purves, George J. Augustine, David Fitzpatrick, and
Methods. Computer Surveys, 30(2):170–231, June 1998. et al. Neuroscience. Sinauer Assoc., Sunderland, MA, 2008.
[18] Michael S. Gazzaniga, Richard B. Ivry, George R. Mangun, [40] Edmund T. Rolls and Alessandro Treves. Neural Networks
and Megan S. Steven. Cognitive Neuroscience, The Biology and Brain Function. Oxford Univ. Press, Oxford, 1998.
of the Mind. W.W. Norton, New York, 2009. [41] Donovan A. Schneider and David J. DeWitt. A
[19] Mark S. Granovetter. The Strength of Weak Ties. Amer. J. performance evaluation of four parallel join algorithms in a
of Sociology, 78(6):1360–1380, 1973. shared-nothing multiprocessor environment. In Proc. 1990
[20] Machael E. Hasselmo. How we remember: brain ACM SIGMOD Conf., pages 110–121, Atlantic City, NJ,
mechanisms of episodic memory. MIT Press, Cambridge, May 1990.
MA, 2012. [42] Dennis Shasha and Tsong-Li Wang. Optimizing equijoin
[21] Michael E. Hasselmo. Encoding: Models linking neural queries in distributed databases where relations are hash
mechanisms to behavior . In H.L. Roediger III, Y. Dudai, partitioned. ACM Trans. on Database Sys., 16(2):279–308,
and S.M. Fitzpatrick, editors, Science of Memory: June 1991.
Concepts, pages 123–127. 2007. [43] Zhao Sun, Hongzhi Wang, Haixun Wang, Bin Shao, and
[22] Yannis Ioannidis, Raghu Ramakrishan, and Linda Winger. Jianzhong Li. Efficient Subgraph Matching on Billion Node
Transitive closure algorithms based on graph traversal. Graphs. Proceedings of the VLDB Endowment,
ACM Trans. on Database Sys., 18(3):512–576, Sept. 1993. 5(9):788–799, 2012. Originally presented at VLDB Conf.,
[23] Walid A. R. Jradi, Elisângela S. Dias, Diane Castonguay, Istanbul, Turkey, 2012.
Humberto Longo, and Hugo A. D. do Nascimento. A [44] Natalie C. Tronson and Jane R. Taylor. Molecular
GPU-based parallel algorithm for enumerating all chordless mechanisms of memory reconsolidation. Nature Review
cycles in graphs. arXiv:submit, 1288731:1–15, June 2015. Neuroscience, 8(4):262–275, 2007.
[24] Michihiro Kuramochi and George Karypis. Frequent [45] Karstan Weis. The Nuclear Pore Complex: Oily Spaghetti
Subgraph Discovery. In Proc.IEEE Conf. on Data Mining, or Gummy Bear? Cell, 130:405–407, August 10 2007.
ICDM 2001, pages 313–320, San Jose, CA, 2001.
[25] Joseph E. LeDoux. Consolidation: Challenging the
traditional view. In H.L. Roediger III, Y. Dudai, and S.M.
Fitzpatrick, editors, Science of Memory: Concepts, pages
171–175. 2007.
[26] Norman M. Martin and Stephen Pollard. Closure Spaces
and Logic. Kluwer Academic, Boston, 1996.
[27] Terry A. McKee. How Chordal Graphs Work. Bulletin of
the ICA, 9:27–39, 1993.
[28] Lynn Nadel. Consolidation: The demise of the fixed trace .
In H.L. Roediger III, Y. Dudai, and S.M. Fitzpatrick,
editors, Science of Memory: Concepts, pages 177–181.
2007.
[29] Karim Nader and Oliver Hardt. Asingle standard for
memory: the case for reconsolidation. Nature Reviews
Neuroscience, 10:224–234, 2009. doi:10.1038/nrn2590.
[30] Ratko Orlandic and John L. Pfaltz. Compact 0-complete
trees: A new method for searching large files. Technical
Report IPC TR-88-001, Institute for Parallel Computation,
Univ. of Virginia, Jan. 1988.
[31] Ratko Orlandic and Byunggu Yu. A Retrieval Technique
for High-Dimensional Data and Partially Specified Queries.
IEEE Trans. on Data and Knowledge Engineering,
42(1):1–21, Jan. 2002.
[32] John Pfaltz and Josef Šlapal. Transformations of discrete
closure systems. Acta Math. Hungar., 138(4):386–405, 2013.
[33] John L. Pfaltz. Finding the Mule in the Network. In Reda
Alhajj and Bob Werner, editors, Intern. Conf on Advances
in Social Network Analysis and Mining, ASONAM 2012,
pages 667–672, Istanbul, Turkey, August 2012.
[34] John L. Pfaltz. Mathematical Continuity in Dynamic Social
Networks. Social Network Analysis and Mining (SNAM),
3(4):863–872, Dec. 2013.
[35] John L. Pfaltz. The Irreducible Spine(s) of Discrete
Networks. In Xuemin Li, Yannis Manolopoulos, Divesh
Srivastava, and Guangyan Huang, editors, Web Information
Systems Engineering - WISE 2013, volume LNCS # 6984,
Part 2, pages 104–117), Nanjing, PRC, Oct. 2013.
[36] John L. Pfaltz. The Role of Continuous Processes in
Cognitive Development. Mathematics for Applications,
4(4):129–152, 2015. DOI:10.13164/ma.2015.11.
[37] John L. Pfaltz. Using Closed Sets to Model Cognitive
Behavior. In Tapabrata Ray, Ruhul Sarker, and Xiaodong
Li, editors, Proc. Australian Conf. on Artificial Life and
Computational Intelligence (ACALCI 2016), volume LNCS
9592, pages 13–26, Canberra, ACT, 2016.
[38] John L. Pfaltz. Two Network Transformations.