Fast algorithm to identify cluster synchrony through fibration symmetries in large information-processing networks
Recent studies revealed an important interplay between the detailed structure of fibration symmetric circuits and the functionality of biological and non-biological networks within which they have be identified. The presence of these circuits in complex networks are directed related to the phenomenon of cluster synchronization, which produces patterns of synchronized group of nodes. Here we present a fast, and memory efficient, algorithm to identify fibration symmetries over information-processing networks. This algorithm is specially suitable for large and sparse networks since it has runtime of complexity $O(M\log N)$ and requires $O(M+N)$ of memory resources, where $N$ and $M$ are the number of nodes and edges in the network, respectively. We propose a modification on the so-called refinement paradigm to identify circuits symmetrical to information flow (i.e., fibers) by finding the coarsest refinement partition over the network. Finally, we show that the presented algorithm provides an optimal procedure for identifying fibers, overcoming the current approaches used in the literature.
Code (1)
Similar Papers 제목 키워드 기반
Breathing cluster in complex neuron-astrocyte networks
Brain activities are featured by spatially distributed neural clusters of coherent firings and a spontaneous switching of the clusters between the synchrony and asynchrony states. Evidences from {\it in vivo} experiments…
Omnivore: An Optimizer for Multi-device Deep Learning on CPUs and GPUs
We study the factors affecting training time in multi-device deep learning systems. Given a specification of a convolutional neural network, our goal is to minimize the time to train this model on a cluster of commodity …
A fast and efficient Modal EM algorithm for Gaussian mixtures
In the modal approach to clustering, clusters are defined as the local maxima of the underlying probability density function, where the latter can be estimated either non-parametrically or using finite mixture models. Th…
ClusteringGlobal and local synchrony of coupled neurons in small-world networks
Synchronous firing of neurons is thought to play important functional roles such as feature binding and switching of cognitive states. Although synchronization has mainly been investigated using model neurons with simple…
Asynchronous Gathering of Opaque Robots with Mobility Faults
We consider the fundamental benchmarking problem of gathering in an $(N,f)$-fault system consisting of $N$ robots, of which at most $f$ might fail at any execution, under asynchrony. Two seminal results established impos…