Dynamics of neural networks over undirected graphs.

Abstract

In this paper we study the dynamical behavior of neural networks such that their interconnections are the incidence matrix of an undirected finite graph G=(V,E) (i.e., the weights belong to {0,1}). The network may be updated synchronously (every node is updated at the same time), sequentially (nodes are updated one by one in a prescribed order) or in a block-sequential way (a mixture of the previous schemes). We characterize completely the attractors (fixed points or cycles). More precisely, we establish the convergence to fixed points related to a parameter α(G), taking into account the number of loops, edges, vertices as well as the minimum number of edges to remove from E in order to obtain a maximum bipartite graph. Roughly, α(G')<0 for any G' subgraph of G implies the convergence to fixed points. Otherwise, cycles appear. Actually, for very simple networks (majority functions updated in a block-sequential scheme such that each block is of minimum cardinality two) we exhibit cycles with non-polynomial periods.