  Random walks can reveal communities or clusters in networks, because they are
more likely to stay within a cluster than leave it. Thus, one family of
community detection algorithms uses random walks to measure distance between
pairs of nodes in various ways, and then applies K-Means or other generic
clustering methods to these distances. Interestingly, information processing in
the brain may suggest a simpler method of learning clusters directly from
random walks. Drawing inspiration from the hippocampus, we describe a simple
two-layer neural learning framework. Neurons in one layer are associated with
graph nodes and simulate random walks. These simulations cause neurons in the
second layer to become tuned to graph clusters through simple associative
learning. We show that if these neuronal interactions are modelled a particular
way, the system is essentially a variant of K-Means clustering applied directly
in the walk-space, bypassing the usual step of computing node
distances/similarities. The result is an efficient graph clustering method.
Biological information processing systems are known for high efficiency and
adaptability. In tests on benchmark graphs, our framework demonstrates this
high data-efficiency, low memory use, low complexity, and real-time adaptation
to graph changes, while still achieving clustering quality comparable to other
algorithms.
