Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Modeling Discrete Combinatorial Systems as Alphabetic Bipartite Networks: Theory and Applications

Monojit Choudhury, Niloy Ganguly, Abyayanda Maiti, Animesh Mukherjee, Lutz Brusch, Andreas Deutsch, and Fernando Peruani


Life and language are discrete combinatorial systems (DCSs) in which the basic building blocks are finite sets of elementary units: nucleotides or codons in a DNA sequence and letters or words in a language. Different combinations of these finite units give rise to potentially infinite numbers of genes or sentences. This type of DCS can be represented as an Alphabetic Bipartite Network (alpha-BiN) where there are two kinds of nodes, one type represents the elementary units while the other type represents their combinations. There is an edge between a node corresponding to an elementary unit u and a node corresponding to a particular combination v if u is present in v. Naturally, the partition consisting of the nodes representing elementary units is fixed, while the other partition is allowed to grow unboundedly. Here, we extend recent analytical findings for alpha-BiNs derived in [Europhys. Lett. 79, 28001 (2007)] and empirically investigate two real world systems: the codon-gene network and the phoneme-language network. The evolution equations for alpha-BiNs under different growth rules are derived, and the corresponding degree distributions computed. It is shown that asymptotically the degree distribution of alpha-BiNs can be described as a family of beta distributions. The one-mode projections of the theoretical as well as the real world alpha-BiNs are also studied. We propose a comparison of the real world degree distributions and our theoretical predictions as a means for inferring the mechanisms underlying the growth of real world systems.


Publication typeArticle
Published inPhysical Review E

Newer versions

Animesh Mukherjee, Monojit Choudhury, and Niloy Ganguly. Understanding how both the partitions of a bipartite network affect its one-mode projection, Physica A: Statistical Mechanics and its Applications, Elsevier, June 2011.

Previous versions

Fernando Peruani, Monojit Choudhury, Animesh Mukherjee, and Niloy Ganguly. Emergence of non-scaling degree distribution in bipartite networks: a numerical and analytical study, Europhysics Letters, 2007.

Monojit Choudhury, Animesh Mukherjee, Anupam Basu, Niloy Ganguly, Ashish Garg, and Vaibhav Jalan. Language Diversity across the Consonant Inventories: A Study in the Framework of Complex Networks, Association for Computational Linguistics, 2009.

Animesh Mukherjee, Monojit Choudhury, Anupam Basu, and Niloy Ganguly. Self-organization of the sound inventories: Analysis and synthesis of the occurrence and co-occurrence networks of consonants, Journal of Quantitative Linguistics, 2008.

Animesh Mukherjee, Monojit Choudhury, Anupam Basu, and Niloy Ganguly. Modeling the co-occurrence principles of consonant inventories: A complex network approach, International Journal of Modern Physics C, 2006.

> Publications > Modeling Discrete Combinatorial Systems as Alphabetic Bipartite Networks: Theory and Applications