Analytical Solution of a Stochastic Content Based Network Model

Abstract

We define and completely solve a content-based directed network whose nodes consist of random words and an adjacency rule involving perfect or approximate matches, for an alphabet with an arbitrary number of letters. The analytic expression for the out-degree distribution shows a crossover from a leading power law behavior to a log-periodic regime bounded by a different power law decay. The leading exponents in the two regions have a weak dependence on the mean word length, and an even weaker dependence on the alphabet size. The in-degree distribution, on the other hand, is much narrower and does not show scaling behavior. The results might be of interest for understanding the emergence of genomic interaction networks, which rely, to a large extent, on mechanisms based on sequence matching, and exhibit similar global features to those found here.

13 pages, 5 figures. Rewrote conclusions regarding the relevance to gene regulation networks, fixed minor errors and replaced fig. 4. Main body of paper (model and calculations) remains unchanged. Submitted for publication

References in corpus (6)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Random model for RNA interference yields scale free network
• Content based network model with duplication and divergence
• The Shift-Match Number and String Matching Probabilities for Binary Sequences
• Hamiltonian model for multidimensional epistasis

Cited by in corpus (8)

• Wikipedia information flow analysis reveals the scale-free architecture of the Semantic Space
• Inversion method for content-based networks
• Robustness and Closeness Centrality for Self-Organized and Planned Cities
• Spontaneous Self-Assembly of Transcription Factor Based Gene Regulation Networks
• Content based network model with duplication and divergence
• String Matching and 1d Lattice Gases
• Information content based model for the topological properties of the gene regulatory network of Escherichia coli
• The Structure and Dynamics of Gene Regulation Networks