Structural Properties and Complexity of a New Network Class: Collatz Step Graphs

Emmert-Streib, Frank
February 2013
PLoS ONE;Feb2013, Vol. 8 Issue 2, p1
Academic Journal
In this paper, we introduce a biologically inspired model to generate complex networks. In contrast to many other construction procedures for growing networks introduced so far, our method generates networks from one-dimensional symbol sequences that are related to the so called Collatz problem from number theory. The major purpose of the present paper is, first, to derive a symbol sequence from the Collatz problem, we call the step sequence, and investigate its structural properties. Second, we introduce a construction procedure for growing networks that is based on these step sequences. Third, we investigate the structural properties of this new network class including their finite scaling and asymptotic behavior of their complexity, average shortest path lengths and clustering coefficients. Interestingly, in contrast to many other network models including the small-world network from Watts & Strogatz, we find that CS graphs become ‘smaller’ with an increasing size.


Related Articles

  • Distinguishing Noise from Chaos: Objective versus Subjective Criteria Using Horizontal Visibility Graph. Ravetti, Martín Gómez; Carpi, Laura C.; Gonçalves, Bruna Amin; Frery, Alejandro C.; Rosso, Osvaldo A. // PLoS ONE;Sep2014, Vol. 9 Issue 9, p1 

    A recently proposed methodology called the Horizontal Visibility Graph (HVG) [Luque et al., Phys. Rev. E., 80, 046103 (2009)] that constitutes a geometrical simplification of the well known Visibility Graph algorithm [Lacasa et al., Proc. Natl. Sci. U.S.A. 105, 4972 (2008)], has been used to...

  • Empirical Bayes conditional independence graphs for regulatory network recovery. Mahdi, Rami; Madduri, Abishek S.; Wang, Guoqing; Strulovici-Barel, Yael; Salit, Jacqueline; Hackett, Neil R.; Crystal, Ronald G.; Mezey, Jason G. // Bioinformatics;8/1/2012, Vol. 28 Issue 15, p2029 

    Motivation: Computational inference methods that make use of graphical models to extract regulatory networks from gene expression data can have difficulty reconstructing dense regions of a network, a consequence of both computational complexity and unreliable parameter estimation when sample...

  • Spectral Characterizations of the Corona of a Cycle and Two Isolated Vertices. Bu, Changjiang; Zhou, Jiang; Li, Hongbo; Wang, Wenzhe // Graphs & Combinatorics;Sep2014, Vol. 30 Issue 5, p1123 

    For a cycle C, let C ○ 2 K be the graph obtained from C by attaching two pendant edges to each vertex of C. In this paper, we prove that C ○ 2 K is determined by its signless Laplacian spectrum when n ≠ 32, 64. We also show that C ○ 2 K is determined by its Laplacian...

  • Designer's Optimal Decisions to Fit Cross-Section Squares of the Supports of a Construction Platform in Overestimations of Uncertainties in the Generalized Model. Romanuke, V. // Cybernetics & Systems Analysis;May2014, Vol. 50 Issue 3, p426 

    The author considers an antagonistic model of fitting cross-sectional areas of the supports of construction platform, where the total load on the platform is normalized to unity. The generalized model under study is generated by interval uncertainties as the evaluations of the normalized squares...

  • Reflexive Incidence Matrix (RIM) Representation of Petri Nets. Das, Sajal K.; Agrawal, V. K.; Sarkar, Dilip; Patnaik, L. M.; Goel, P. S. // IEEE Transactions on Software Engineering;Jun87, Vol. 13 Issue 6, p643 

    Although incidence matrix representation has been used to analyze the Petri net based models of a system, it has the limitation that it does not preserve reflexive properties (i.e., the presence of self- loops) of Petri nets. But in many practical applications self-loops play very important...

  • Kumjian-Pask Algebras of Desourcification. Rosjanuardi, Rizky; Yusnitha, Isnie // AIP Conference Proceedings;2016, Vol. 1708 Issue 1, p1 

    Kumjian-Pask algebra which was introduced by Pino, Clark, an Huef and Raeburn [1] in 2013, gives a purely algebraic version of a k-graph algebra. Rosjanuardi [2] gave necessary and sufficient condition of finitely dimensional complex Kumjian-Pask algebra of row-finite k-graph without sources. We...

  • A unified framework for the evaluation of complex networks. Bo Jiao; Xun-long Pang; Rong-hua Guo; Jing Du // Applied Mechanics & Materials;2014, Issue 670-671, p1473 

    Graph metrics are important tools for the comparisons between networks. However, different graph metrics may lead to different evaluation results for a certain network. In this paper, we generate a unified framework for the multi-metrics and study the collective evaluation method for complex...

  • History-dependent contact models for viscoplastic materials. Barboteu, Mikael; Ramadan, Ahmad; Sofonea, Mircea; Pătrulescu, Flavius // IMA Journal of Applied Mathematics;Dec2014, Vol. 79 Issue 6, p1180 

    We consider two mathematical models which describe the frictionless process of contact between a rate-type viscoplastic body and a foundation. The contact is modelled with normal compliance and memory term such that penetration is not restricted in the first problem, but is restricted with...

  • Fourth Order and Fourth Sum Connectivity Indices of Polyphenylene Dendrimers. Arif, Nabeel E.; Hasni, Roslan; Alikhani, Saeid // Journal of Applied Sciences;Nov2012, Vol. 12 Issue 21, p2279 

    The m-order connectivity index mχ (G) of a graph G is mχ (G) = Σ 1/vi v12 ... v1m+1√di1 di2 ... dim+1, where, di1 di1 ... dim+1 runs over all paths of length m in G and di denotes the degree of vertex vi. Also ms X(G) = Σ 1/vi v12 ... v1m+1√di1 di2 ... dim+1 is its m-sum...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics