This page contains information and notions about actor-based implementation
of graph algorithms
My specific interest in these algorithms is driven by the need
to find and display "related" nodes (e.g., Wikipedia
in very large graphs such as Ontiki
Michel Raynal's Distributed Algorithms for Message-Passing Systems
and Wan Fokkink's Distributed Algorithms: An Intuitive Approach
are accessible and highly relevant resources.
Neither book is focused on the actor model,
but the needed accomodations appear to be fairly trivial.
In the notes below, particular attention paid to property graphs,
as used by graph databases
and related tools (e.g., Gremlin
I don't expect to get into many of these areas any time soon, if ever.
However, I'd love
to chat with anyone who wants to give it a try...
I'm currently working on developing a Data Model
using the first exercise in Dr. Raynal's book
(1.1.2 - Learning the Communication Graph
See my Distributed Algorithms
subweb for more information.
Let's say that we want to generate 2D (or 3D!) diagrams of a property graph.
A supervisory actor could analyze edge crossings
and emit advice and/or directives for node layout.
Node and edge actors could emit messages about where they are located
and respond to messages from "neighbors", in order to avoid collisions.
Botanical Modeling, Fractals, etc.
It occurs to me that some of the algorithms in The Algorithmic Beauty of Plants
(e.g, branching, space filling) could be adapted to use collections of agents.
Books like The Secret Garden
and The Private Life of Plants
show us that plants exhibit heuristic behavior (e.g, avoiding collisions).
It might be interesting to model (sets of) plants, using combinations
of algorithmic and heuristic approaches.
More generally, many kinds of natural systems can be modeled
by the interaction of fractals with the environment.
Cellular Automata, Neural Networks, etc.
The artificial intelligence
has developed algorithms that are inspired by and (more or less :-)
based on the behavior of collections of neurons
Hierarchical Temporal Memory
Hierarchical Temporal Memory (HTM
) employs a variety
of cortical learning algorithms
It seems plausible that some of these could be usefully emulated in Elixir.
In particular, a variation on sparse distributed representations
might be a good match (:-) for Elixir's pattern support.
Spreading activation is a method for searching associative networks, neural networks, or semantic networks.
The search process is initiated by labeling a set of source nodes (e.g., concepts in a semantic network)
with weights or "activation" and then iteratively propagating or "spreading" that activation ...
Spreading activation models are used in cognitive psychology to model the fan out effect.
Spreading activation can also be applied in information retrieval,
by means of a network of nodes representing documents and terms contained in those documents.
-- Spreading Activation (WP)
We can use a variant on spreading activation to find multiple paths between nodes A and B.
This might be used in a system such as Ontiki to find nodes which are related to A and/or B.
The total relevance of a node might be calculated by adding up the aggregate activation
it receives from the initial nodes.
Thus, nodes which sit on a path between A and
B might have higher relevance scores
than nodes which are only related to node A or
See Path Finding
for more details.
Social Networks, etc.
Graph databases such as Neo4j are already being used for analysis of social networks.
I suspect that actor-based algorithms could be used to offload the analysis,
providing increased performance, robustness, and scalability.
There is a lot of interesting work in transition systems
Discrete-Time Markov Chains
, in particular,
seem like a plausible match for actor-based graph algorithms.
I'm particularly interested in actor-critic algorithms
page contains a number of links to related information.
This wiki page is maintained by Rich Morin
an independent consultant specializing in software design, development, and documentation.
Please feel free to email
comments, inquiries, suggestions, etc!