Algorithms

This page contains information and notions about actor-based implementation of graph algorithms in Elixir. My specific interest in these algorithms is driven by the need to find and display "related" nodes (e.g., Wikipedia topics) 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 (e.g., Neo4j) and related tools (e.g., Gremlin).

Note: 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...

Beginnings

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.

Diagram Layout

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 community 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

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)

Path Finding

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 B. 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.

Transition-based modeling

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, reinforcement learning, etc.

Resources

The Resources 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!

Topic revision: r21 - 12 Apr 2016, RichMorin
This site is powered by Foswiki Copyright © by the contributing authors. All material on this wiki is the property of the contributing authors.
Foswiki version v2.1.6, Release Foswiki-2.1.6, Plugin API version 2.4
Ideas, requests, problems regarding CFCL Wiki? Send us email