Computation of balanced equivalence relations and their lattice for a coupled cell network

Hiroko Kamei, Peter J. A. Cock

    Research output: Contribution to journalArticle

    11 Citations (Scopus)

    Abstract

    A coupled cell network describes interacting (coupled) individual systems (cells). As in networks from real applications, coupled cell networks can represent inhomogeneous networks where different types of cells interact with each other in different ways, which can be represented graphically by different symbols, or abstractly by equivalence relations. Various synchronous behaviors, from full synchrony to partial synchrony, can be observed for a given network. Patterns of synchrony, which do not depend on specific dynamics of the network, but only on the network structure, are associated with a special type of partition of cells, termed balanced equivalence relations. Algorithms in Aldis [J. W. Aldis, Internat. J. Bifur. Chaos Appl. Sci. Engrg., 18 (2008), pp. 407-427] and Belykh and Hasler [I. Belykh and M. Hasler, Chaos, 21 (2011), 016106] find the unique pattern of synchrony with the fewest clusters. In this paper, we compute the set of all possible patterns of synchrony and show their hierarchy structure as a complete lattice. We represent the network structure of a given coupled cell network by a symbolic adjacency matrix encoding the different coupling types. We show that balanced equivalence relations can be determined by a matrix computation on the adjacency matrix which forms a block structure for each balanced equivalence relation. This leads to a computer algorithm to search for all possible balanced equivalence relations. Our computer program outputs the balanced equivalence relations, quotient matrices, and a complete lattice for user specified coupled cell networks. Finding the balanced equivalence relations of any network of up to 15 nodes is tractable, but for larger networks this depends on the pattern of synchrony with the fewest clusters.

    Original languageEnglish
    Pages (from-to)352-382
    Number of pages31
    JournalSiam Journal on Applied Dynamical Systems
    Volume12
    Issue number1
    DOIs
    Publication statusPublished - 2013

    Keywords

    • SYSTEMS
    • SYNCHRONIZATION
    • lattice
    • coupled cell networks
    • OSCILLATORS
    • COMPLEX NETWORKS
    • synchrony
    • PATTERNS
    • BIFURCATIONS
    • DYNAMICS
    • balanced equivalence relations

    Cite this

    @article{3f59b99c30d54e31b5269918d16e9301,
    title = "Computation of balanced equivalence relations and their lattice for a coupled cell network",
    abstract = "A coupled cell network describes interacting (coupled) individual systems (cells). As in networks from real applications, coupled cell networks can represent inhomogeneous networks where different types of cells interact with each other in different ways, which can be represented graphically by different symbols, or abstractly by equivalence relations. Various synchronous behaviors, from full synchrony to partial synchrony, can be observed for a given network. Patterns of synchrony, which do not depend on specific dynamics of the network, but only on the network structure, are associated with a special type of partition of cells, termed balanced equivalence relations. Algorithms in Aldis [J. W. Aldis, Internat. J. Bifur. Chaos Appl. Sci. Engrg., 18 (2008), pp. 407-427] and Belykh and Hasler [I. Belykh and M. Hasler, Chaos, 21 (2011), 016106] find the unique pattern of synchrony with the fewest clusters. In this paper, we compute the set of all possible patterns of synchrony and show their hierarchy structure as a complete lattice. We represent the network structure of a given coupled cell network by a symbolic adjacency matrix encoding the different coupling types. We show that balanced equivalence relations can be determined by a matrix computation on the adjacency matrix which forms a block structure for each balanced equivalence relation. This leads to a computer algorithm to search for all possible balanced equivalence relations. Our computer program outputs the balanced equivalence relations, quotient matrices, and a complete lattice for user specified coupled cell networks. Finding the balanced equivalence relations of any network of up to 15 nodes is tractable, but for larger networks this depends on the pattern of synchrony with the fewest clusters.",
    keywords = "SYSTEMS, SYNCHRONIZATION, lattice, coupled cell networks, OSCILLATORS, COMPLEX NETWORKS, synchrony, PATTERNS, BIFURCATIONS, DYNAMICS, balanced equivalence relations",
    author = "Hiroko Kamei and Cock, {Peter J. A.}",
    year = "2013",
    doi = "10.1137/100819795",
    language = "English",
    volume = "12",
    pages = "352--382",
    journal = "Siam Journal on Applied Dynamical Systems",
    issn = "1536-0040",
    publisher = "Society for Industrial and Applied Mathematics",
    number = "1",

    }

    Computation of balanced equivalence relations and their lattice for a coupled cell network. / Kamei, Hiroko; Cock, Peter J. A.

    In: Siam Journal on Applied Dynamical Systems, Vol. 12, No. 1, 2013, p. 352-382.

    Research output: Contribution to journalArticle

    TY - JOUR

    T1 - Computation of balanced equivalence relations and their lattice for a coupled cell network

    AU - Kamei, Hiroko

    AU - Cock, Peter J. A.

    PY - 2013

    Y1 - 2013

    N2 - A coupled cell network describes interacting (coupled) individual systems (cells). As in networks from real applications, coupled cell networks can represent inhomogeneous networks where different types of cells interact with each other in different ways, which can be represented graphically by different symbols, or abstractly by equivalence relations. Various synchronous behaviors, from full synchrony to partial synchrony, can be observed for a given network. Patterns of synchrony, which do not depend on specific dynamics of the network, but only on the network structure, are associated with a special type of partition of cells, termed balanced equivalence relations. Algorithms in Aldis [J. W. Aldis, Internat. J. Bifur. Chaos Appl. Sci. Engrg., 18 (2008), pp. 407-427] and Belykh and Hasler [I. Belykh and M. Hasler, Chaos, 21 (2011), 016106] find the unique pattern of synchrony with the fewest clusters. In this paper, we compute the set of all possible patterns of synchrony and show their hierarchy structure as a complete lattice. We represent the network structure of a given coupled cell network by a symbolic adjacency matrix encoding the different coupling types. We show that balanced equivalence relations can be determined by a matrix computation on the adjacency matrix which forms a block structure for each balanced equivalence relation. This leads to a computer algorithm to search for all possible balanced equivalence relations. Our computer program outputs the balanced equivalence relations, quotient matrices, and a complete lattice for user specified coupled cell networks. Finding the balanced equivalence relations of any network of up to 15 nodes is tractable, but for larger networks this depends on the pattern of synchrony with the fewest clusters.

    AB - A coupled cell network describes interacting (coupled) individual systems (cells). As in networks from real applications, coupled cell networks can represent inhomogeneous networks where different types of cells interact with each other in different ways, which can be represented graphically by different symbols, or abstractly by equivalence relations. Various synchronous behaviors, from full synchrony to partial synchrony, can be observed for a given network. Patterns of synchrony, which do not depend on specific dynamics of the network, but only on the network structure, are associated with a special type of partition of cells, termed balanced equivalence relations. Algorithms in Aldis [J. W. Aldis, Internat. J. Bifur. Chaos Appl. Sci. Engrg., 18 (2008), pp. 407-427] and Belykh and Hasler [I. Belykh and M. Hasler, Chaos, 21 (2011), 016106] find the unique pattern of synchrony with the fewest clusters. In this paper, we compute the set of all possible patterns of synchrony and show their hierarchy structure as a complete lattice. We represent the network structure of a given coupled cell network by a symbolic adjacency matrix encoding the different coupling types. We show that balanced equivalence relations can be determined by a matrix computation on the adjacency matrix which forms a block structure for each balanced equivalence relation. This leads to a computer algorithm to search for all possible balanced equivalence relations. Our computer program outputs the balanced equivalence relations, quotient matrices, and a complete lattice for user specified coupled cell networks. Finding the balanced equivalence relations of any network of up to 15 nodes is tractable, but for larger networks this depends on the pattern of synchrony with the fewest clusters.

    KW - SYSTEMS

    KW - SYNCHRONIZATION

    KW - lattice

    KW - coupled cell networks

    KW - OSCILLATORS

    KW - COMPLEX NETWORKS

    KW - synchrony

    KW - PATTERNS

    KW - BIFURCATIONS

    KW - DYNAMICS

    KW - balanced equivalence relations

    U2 - 10.1137/100819795

    DO - 10.1137/100819795

    M3 - Article

    VL - 12

    SP - 352

    EP - 382

    JO - Siam Journal on Applied Dynamical Systems

    JF - Siam Journal on Applied Dynamical Systems

    SN - 1536-0040

    IS - 1

    ER -