Constructing directed networks with a desired minimum balanced coloring

Biological, social, and technological networks are made up of many interacting nodes coupled by directed connections. Moreover, the study of empirical networks has shown that often groups of their nodes are “symmetric” to one another, i.e., they are structurally identical to one another within such networks. Many of the popular network-generating algorithms do not control for the emergence of symmetries. Here, we present an algorithm focused on directed networks that enables the user to generate what are called “expanded” directed networks, which transform each node of a base network into a cluster with a desired number of nodes, after checking for the expansion to be feasible. Analytical conditions are provided for an expansion to be feasible and for the generation of the expansion or minimal expansion, i.e., a feasible expansion with the least number of nodes. The algorithm is used to construct synthetic networks with prescribed symmetries.