Analytical and numerical studies of creation probabilities of hierarchical trees

We consider the creation conditions of diverse hierarchical trees both analytically and numerically. A connection between the probabilities to create hierarchical levels and the probability to associate these levels into a united structure is studied. We argue that a consistent probabilistic picture...

Full description

Saved in:
Bibliographic Details
Published in:Condensed Matter Physics
Date:2011
Main Authors: Olemskoi, A.I., Borysov, S.S., Shuda, I.A.
Format: Article
Language:English
Published: Інститут фізики конденсованих систем НАН України 2011
Online Access:https://nasplib.isofts.kiev.ua/handle/123456789/119973
Tags: Add Tag
No Tags, Be the first to tag this record!
Journal Title:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:Analytical and numerical studies of creation probabilities of hierarchical trees / A.I. Olemskoi, S.S. Borysov, I.A. Shuda // Condensed Matter Physics. — 2011. — Т. 14, № 1. — С. 14001: 1-6. — Бібліогр.: 14 назв. — англ.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-119973
record_format dspace
spelling Olemskoi, A.I.
Borysov, S.S.
Shuda, I.A.
2017-06-10T14:08:23Z
2017-06-10T14:08:23Z
2011
Analytical and numerical studies of creation probabilities of hierarchical trees / A.I. Olemskoi, S.S. Borysov, I.A. Shuda // Condensed Matter Physics. — 2011. — Т. 14, № 1. — С. 14001: 1-6. — Бібліогр.: 14 назв. — англ.
1607-324X
PACS: 02.50.-r, 89.75.-k, 89.75.Fb
DOI:10.5488/CMP.14.14001
arXiv:1106.3578
https://nasplib.isofts.kiev.ua/handle/123456789/119973
We consider the creation conditions of diverse hierarchical trees both analytically and numerically. A connection between the probabilities to create hierarchical levels and the probability to associate these levels into a united structure is studied. We argue that a consistent probabilistic picture requires the use of deformed algebra. Our consideration is based on the study of the main types of hierarchical trees, among which both regular and degenerate ones are studied analytically, while the creation probabilities of Fibonacci, scale-free and arbitrary trees are determined numerically.
Розглянуто аналiтично i чисельно умови утворення рiзних iєрархiчних дерев. Дослiджено зв’язок мiж ймовiрностями утворення iєрархiчних рiвнiв та ймовiрностi об’єднання цих рiвнiв у єдину структуру. Показано,що побудова послiдовної ймовiрнiсної картини вимагає використання деформованої алгебри. Даний розгляд заснований на дослiдженнi основних типiв iєрархiчних дерев,серед яких регулярне i вироджене дослiдженi аналiтично, тодi як ймовiрностi утворення дерева Фiбоначчi, безмасштабного та довiльного дерева визначенi чисельно. .
en
Інститут фізики конденсованих систем НАН України
Condensed Matter Physics
Analytical and numerical studies of creation probabilities of hierarchical trees
Аналiтичне i чисельне дослiдження ймовiрностi утворення iєрархiчних дерев
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Analytical and numerical studies of creation probabilities of hierarchical trees
spellingShingle Analytical and numerical studies of creation probabilities of hierarchical trees
Olemskoi, A.I.
Borysov, S.S.
Shuda, I.A.
title_short Analytical and numerical studies of creation probabilities of hierarchical trees
title_full Analytical and numerical studies of creation probabilities of hierarchical trees
title_fullStr Analytical and numerical studies of creation probabilities of hierarchical trees
title_full_unstemmed Analytical and numerical studies of creation probabilities of hierarchical trees
title_sort analytical and numerical studies of creation probabilities of hierarchical trees
author Olemskoi, A.I.
Borysov, S.S.
Shuda, I.A.
author_facet Olemskoi, A.I.
Borysov, S.S.
Shuda, I.A.
publishDate 2011
language English
container_title Condensed Matter Physics
publisher Інститут фізики конденсованих систем НАН України
format Article
title_alt Аналiтичне i чисельне дослiдження ймовiрностi утворення iєрархiчних дерев
description We consider the creation conditions of diverse hierarchical trees both analytically and numerically. A connection between the probabilities to create hierarchical levels and the probability to associate these levels into a united structure is studied. We argue that a consistent probabilistic picture requires the use of deformed algebra. Our consideration is based on the study of the main types of hierarchical trees, among which both regular and degenerate ones are studied analytically, while the creation probabilities of Fibonacci, scale-free and arbitrary trees are determined numerically. Розглянуто аналiтично i чисельно умови утворення рiзних iєрархiчних дерев. Дослiджено зв’язок мiж ймовiрностями утворення iєрархiчних рiвнiв та ймовiрностi об’єднання цих рiвнiв у єдину структуру. Показано,що побудова послiдовної ймовiрнiсної картини вимагає використання деформованої алгебри. Даний розгляд заснований на дослiдженнi основних типiв iєрархiчних дерев,серед яких регулярне i вироджене дослiдженi аналiтично, тодi як ймовiрностi утворення дерева Фiбоначчi, безмасштабного та довiльного дерева визначенi чисельно. .
issn 1607-324X
url https://nasplib.isofts.kiev.ua/handle/123456789/119973
citation_txt Analytical and numerical studies of creation probabilities of hierarchical trees / A.I. Olemskoi, S.S. Borysov, I.A. Shuda // Condensed Matter Physics. — 2011. — Т. 14, № 1. — С. 14001: 1-6. — Бібліогр.: 14 назв. — англ.
work_keys_str_mv AT olemskoiai analyticalandnumericalstudiesofcreationprobabilitiesofhierarchicaltrees
AT borysovss analyticalandnumericalstudiesofcreationprobabilitiesofhierarchicaltrees
AT shudaia analyticalandnumericalstudiesofcreationprobabilitiesofhierarchicaltrees
AT olemskoiai analitičneičiselʹnedoslidžennâimovirnostiutvorennâiêrarhičnihderev
AT borysovss analitičneičiselʹnedoslidžennâimovirnostiutvorennâiêrarhičnihderev
AT shudaia analitičneičiselʹnedoslidžennâimovirnostiutvorennâiêrarhičnihderev
first_indexed 2025-11-24T02:24:29Z
last_indexed 2025-11-24T02:24:29Z
_version_ 1850836803347546112
fulltext Condensed Matter Physics 2011, Vol. 14, No 1, 14001: 1–6 DOI:10.5488/CMP.14.14001 http://www.icmp.lviv.ua/journal Rapid Communication Analytical and numerical studies of creation probabilities of hierarchical trees A.I. Olemskoi1,2, S.S. Borysov2, I.A. Shuda2 1 Institute of Applied Physics, Nat. Acad. Sci. of Ukraine, 58 Petropavlivs’ka Str., 40030 Sumy, Ukraine 2 Sumy State University, 2 Rimskii-Korsakov Str., 40007 Sumy, Ukraine Received February 18, 2011 We consider the creation conditions of diverse hierarchical trees both analytically and numerically. A connec- tion between the probabilities to create hierarchical levels and the probability to associate these levels into a united structure is studied. We argue that a consistent probabilistic picture requires the use of deformed algebra. Our consideration is based on the study of the main types of hierarchical trees, among which both regular and degenerate ones are studied analytically, while the creation probabilities of Fibonacci, scale-free and arbitrary trees are determined numerically. Key words: probability, hierarchical tree, deformation PACS: 02.50.-r, 89.75.-k, 89.75.Fb 1. Introduction As it is shown for diverse systems, ranging from the World Wide Web [1] to biological [2] and social [3] networks, real networks are governed by strict organizing principles displaying the following properties: i) most networks have a high degree of clustering; ii) many networks have been found to be scale-free [4] which means that the probability distribution over node degrees, being the set of the numbers of links with neighbors, follows the power law. A formal basis of the theory of hierarchical structures is represented by the fact that hierar- chically constrained objects are related to an ultrametric space whose geometrical image is the Cayley tree with nodes and branches corresponding to elementary cells and their links [5]. One of the first theoretical pictures [6] has been devoted to the diffusion process on either uniformly or randomly multifurcating trees. The consequent study of hierarchical structures has shown [7] that their evolution is reduced to an anomalous diffusion process in ultrametric space that arrives at a steady-state distribution over hierarchical levels, which represents the Tsallis power law inherent to non-extensive systems [8]. The principal peculiarity of the Tsallis statistics is known to be governed by a deformed algebra [9]. This paper briefly represents the results of our study of creation conditions of a vast variety of hierarchical trees on the basis of methods initially developed within the quantum calculus [10]. An extended version of our analysis is published elsewhere [11]. The outline of the paper is as follows. In section 2, we discuss the statistical peculiarities of the picture of hierarchical structure creation to demonstrate that effective energies of hierarchical levels remain to be additive values, while the set of corresponding probabilities becomes both non-additive and non-multiplicative due to the coupling between different levels. Further consideration is based on an analytical and numerical study of the main types of hierarchical trees in section 3. Section 4 is devoted to the discussion of obtained results. c© A.I. Olemskoi, S.S. Borysov, I.A. Shuda 14001-1 http://dx.doi.org/10.5488/CMP.14.14001 http://www.icmp.lviv.ua/journal 2. Statistical peculiarities of hierarchical ensembles As pointed out above, the stationary creation probability of the l-th hierarchical level takes the Tsallis form pl = p0 expq ( − εl ∆ ) , expq(x) := [1 + (1 − q)x] 1 1−q + , [y]+ ≡ max(0, y). (2.1) Here, p0 is the top-level probability fixed by the normalization condition, q > 0 is a deformation parameter, εl is an effective energy of the l number, ∆ is an effective temperature. Although the energy is a key concept of the network optimization theory, it is not always possible to match its value to a given graph. However, basing on heuristic ideas, it is always possible to attach an effective value of energy to some phenomenological parameter. Also, for our purpose it is convenient to consider the nodes of the hierarchical tree as particles of a statistical ensemble, while its edges represent couplings between these particles. In contrast to the statistical theory of complex networks [12], the hierarchical systems under our consideration cannot simultaneously display the properties of additivity of effective energies and multiplicativity of related probabilities. The cornerstone of our approach is that the creation of a hierarchical structure does not break the law of the energy conservation, so that the energies εl remain to be additive values: ǫn := n ∑ l=0 εl. (2.2) Within the statistical theory of random networks [12], effective energies εl are reduced to a constant for microcanonical ensemble and are fixed by the set of particular probabilities pl according to the relation εl = −∆ ln(pl)+ const for both canonical and grand canonical ensembles with an effective temperature ∆. On the other hand, due to the coupling between different levels, the hierarchy essentially deforms the corresponding probabilities pl, which become non-multiplicative. Indeed, the probability Pn to create an n-level hierarchical structure is connected with total energy ǫn by means of the relation ǫn = −∆ lnq(Pn) with the deformed logarithm lnq(x) := ( x1−q − 1 ) /(1− q). Then, the condition (2.2) leads to the additivity of these logarithms: lnq(Pn) = ∑n l=0 lnq(pl), and one obtains the probability relation Pn := p0 ⊗q p1 ⊗q p2 ⊗q · · · ⊗q pn, (2.3) where the deformed product is defined as x ⊗q y := [ x1−q + y1−q − 1 ] 1 1−q + . Thus, in contrast to ordinary statistical systems, the creation probability Pn of a hierarchical structure is equal to the deformed production of specific probabilities pl related to the levels l = 0, 1, . . . , n. The above law of the deformed multiplicativity determines the probabilities pl to create a set of hierarchical levels simultaneously. Another problem emerges when we consider the connection between the creation probability of a given hierarchical level l and the same for each node at this level. For simplicity let us consider a regular tree, whose nodes multifurcate to generate a set of the Nl nodes determined with inherent probabilities π = p0/Nl where p0 is their top magnitude being a normalization constant. If one permits additivity of the node probabilities, we arrive at the total probability of the l level realization to be independent of their numbers: pl := Nlπ = p0. Since the probability pl to create a hierarchical level decays with the level number l, we are forced again to replace the trivial additive connection of the level probability pl with the node value π by a deformed sum. Finally, since the creation probabilities of the hierarchical levels go beyond probabilities related to non-hierarchical structures, the standard normalization condition based on the use of the usual sum is broken as well. With the growth of the difference |q − 1|, the probability (2.1) increases at arbitrary values of the energy εl with respect to the non-deformed value related to the parameter q = 1. On the other hand, the deformed sum x⊕q y := x+ y+(1− q)xy decreases with the growth of the parameter q > 1. As a result, one can anticipate that a self-consistent probabilistic picture of hierarchical ensembles is reached if one proposes the normalization condition p0 ⊕q p1 ⊕q · · · ⊕q pn = 1, q > 1 (2.4) 14001-2 Creation probabilities of hierarchical trees that is deformed to fix the top level probability p0. Taking into account the above statements, one obtains an explicit form of the creation proba- bility of a hierarchical structure [11] Pn = expq [ ∑n l=0 p1−q l − (n+ 1) 1− q ] = ( n ∑ l=0 p1−q l − n ) 1 1−q + . (2.5) The relations (2.5) mean the decrease of the creation probability with the growth of the hierarchical tree in accordance with the difference equation P 1−q n−1 − P 1−q n = 1− p1−q n . (2.6) In the non-deformed limit q → 1, relations (2.3) and (2.5) are reduced to the ordinary rule Pn = ∏n l=0 pl (respectively, equation (2.6) reads Pn/Pn−1 = pn), while at q = 2 the creation probability (2.5) takes a maximal value. According to equation (2.5) the subsequent step in the definition of the creation probability Pn of a hierarchical structure is the determination of a set of probabilities {pl} n 0 related to different hierarchical levels. 3. Level probabilities for different hierarchical trees First, we consider a regular tree whose nodes multifurcate at the level l with constant branching index b > 1 to generate a set of the Nl = bl nodes determined with inherent probabilities π = p0/Nl = p0b −l. Within naive proposition, one could permit additivity of the node probabilities to arrive at the total probability of the l level realization to be pl := Nlπ = p0. Thus, within the condition of additivity of the node probabilities, the related values pl = p0 = (n+1)−1 for all levels appear to be independent of their numbers l = 0, 1, . . . , n. To avoid this trivial situation, we propose to replace the common additive connection of the level probability with the node value π by the deformed one. Such deformation leads to the required level distribution in the binomial form [11] pl = [1 + (1 − q)b−l]b l + − 1 1− q p0 . (3.1) This probability increases with the growing number l of hierarchical level at q < 1 and decays at q > 1. From the physical point of view, the creation probability of a lower hierarchical level should be less than for higher levels, so that one ought to conclude that only the case q > 1 is meaningful. Characteristically, the form of this distribution very weakly depends on both deformation parame- ter q and branching index b excluding the domain 2− q ≪ 1, where the probability does not decay that fast at small values of the branching index b. With large growth of the parameter b ≫ 1 or level number l, the dependence pl decreases faster to exponentially reach the minimum value p∞ = e1−q − 1 1− q p0 = p0 lnq e. (3.2) There is a distinctive feature in the behavior of the regular hierarchical tree near the limit value q = 2 where the dependence (3.1) has no singularity. This feature is corroborated with the dependence of the top level probability p0 on the deformation parameter. This probability increases monotonously with the q-growth to reach sharply the limit value p0 = 1 in the point q = 2. Obviously, this means an anomalous increase of probabilities pl for the whole set of hierarchical levels. Though, within the domain 2 − q ≪ 1, the ordinary normalization condition ∑n l=0 pl = 1 is violated appreciably, the definition of the deformed sum shows that the deformed normalization condition (2.4) can be recovered with the q parameter growing. However, beyond the border q = 2, this condition is not satisfied at all. As a result, we arrive at the conclusion that physically meaningful values of the deformation parameter are concentrated within the domain q ∈ [1, 2]. 14001-3 The difference between regular and degenerate trees is that all nodes multifurcate at each level in the former case, while the only one node branches in the latter. In this sense, the degenerate tree can be considered as an antipode of the regular one to be studied analytically. Taking into account this peculiarity, the creation probability of the lth hierarchical level takes the form [11] pl = [ 1 + (1− q)b−l ] ∏l m=1 [ 1 + (1 − q)b−m ]b−1 −1 1− q p0 . (3.3) Similarly to the case of the regular tree, this distribution decays exponentially fast to the limit probability p∞ determined by equation (3.2). Above, we have considered two conceptual examples of hierarchical trees with self-similar struc- ture, i.e., regular and degenerate trees. By contrast, a scale-free tree has rather random structure, but the probability distribution over hierarchical levels tends to the power-law form inherent in self- similar statistical systems. In this case, the probability distribution over tree levels is determined by the discrete difference equation [7] pl+1 − pl = −pql /∆, l = 0, 1, . . . , n (3.4) accompanied with the deformed normalization condition (2.4) (∆ being a distribution dispersion). In figure 1 we compare the probability distributions over hierarchical levels of scale-free, regular, (a) (b) Figure 1. Probability distributions over hierarchical levels for scale-free, regular, Fibonacci and degenerate trees (curves 1-4, respectively) at ∆ = 2, b = 2, n = 10 and q = 1.9 (a) and q = 1.9999 (b). degenerate and Fibonacci trees at different values of the deformation parameter. As it is seen, at all q-values, that the forms of these distributions are actually similar for all the above trees excluding the scale-free one. In the latter case, the level probability decays to zero as a power law, whereas there is a limit non-zero value (3.2) for the regular trees. In accordance with such a behavior, the creation probabilities depicted in figure 2 decay faster for the scale-free tree than in the case of the regular and degenerate ones. Characteristically, this difference appears only within the domain 2− q ≪ 1 of the deformation parameter variation. Finally, let us consider two examples of arbitrary trees, among which the former concerns the Fibonacci tree (number of nodes at its each level is equal to Fibonacci number), while the latter relates to the schematic evolution tree shown in figure 3a (in the latter case, the nodes identify substantial stages in the evolution of life, e.g., human is situated on the 24th level). Using the approach developed for the node and level probabilities, obeying the normalization condition, we show that the probability distributions of the Fibonacci tree depicted in figures 1, 2 do not actually differ from the related dependencies for both regular and degenerate trees. As concerns the evolution tree, its probability distributions (figure 3b) show that the presence of the stopped 14001-4 Creation probabilities of hierarchical trees (a) (b) Figure 2. Creation probabilities of scale-free, regular, Fibonacci and degenerate hierarchical trees (curves 1-4, respectively) as function of the whole level number at ∆ = 2, b = 2 and q = 1.9 (a) and q = 1.9999 (b). (a) (b) Figure 3. (a) Schematic representation of evolution tree (from Ref. [13]). (b) Creation probability of the evolution tree vs. the level number at: q = 1.0001, 1.1, 1.2, 1.3, 1.4, 1.5, 1.7, 1.9, 1.9999 (curves 1-9, respectively). branches (type of two rightmost ones in figure 3a) considerably decreases the creation probability of new hierarchical levels. Particularly, the probability of human appearance takes the values greater than 10−4 only at the deformation parameter q = 1.9999. 4. Concluding remarks To avoid ambiguities it is worthwhile to stress that our consideration concerns rather the prob- abilistic picture of creation of the hierarchical trees themselves than hierarchical phenomena and processes evolving on these trees (for example, hierarchically constrained statistical ensembles [14], diffusion processes on multifurcating trees [6], et cetera). The principal peculiarity of the probabilistic picture elaborated is a distinction between the de- formed and non-deformed quantities. Thus, effective energies of hierarchical levels in equation (2.2) are non-deformed quantities because the creation of hierarchical structures does not break the conservation law of the energy being an additive value. Moreover, the node probabilities are de- termined using the non-deformed relations because these probabilities relate to the configuration of the hierarchical tree itself (in other words, they are determined for geometrical, rather than for probabilistic reasons). At the same time, the hierarchy appearance essentially deforms the probabil- 14001-5 ity relations (2.3)–(2.5) due to the coupling level probabilities pl . Similarly, the definition of these probabilities through corresponding node values is based on the use of a deformed summation. Making use of the deformed algebra leads to an increase of probabilities pl for the whole set of hierarchical levels assuming an anomalous character near the point q = 2. The deformed normalization condition (2.4) is fulfilled only at q 6 2, while it is broken beyond the limit q = 2. As a result, taking into account the fact that the creation probability of a lower hierarchical level should be less than the one for higher levels, the physically meaningful values of the deformation parameter belong to the domain q ∈ [1, 2]. References 1. Albert R., Jeong H., Barabási A.-L., Nature, 1999, 401, 130; doi:10.1038/43601. 2. Jeong H. et al., Nature, 2000, 407, 651; doi:10.1038/35036627. 3. Newman M.E.J., Proc. Nat. Acad. Sci. U.S.A., 2001, 98, 404; doi:10.1073/pnas.021544898. 4. Barabási A.-L., Albert R., Science, 1999, 286, 509; doi:10.1126/science.286.5439.509. 5. Rammal R., Toulouse G., Virasoro M.A., Rev. Mod. Phys., 1986, 58, 765; doi:10.1103/RevModPhys.58.765. 6. Bachas C.P., Huberman B.A., Phys. Rev. Lett., 1986, 57, 1965; doi:10.1103/PhysRevLett.57.1965. 7. Olemskoi A.I., JETP Letters, 2000, 71, 285; doi:10.1134/1.568335. 8. Tsallis C., Introduction to Nonextensive Statistical Mechanics – Approaching a Complex World. Springer, New York, 2009; doi:10.1007/978-0-387-85359-8. 9. Borges E.P., Physica A, 2004, 340, 95; doi:10.1016/j.physa.2004.03.082. 10. Kac V., Cheung P., Quantum calculus. Springer, New York, 2002. 11. Olemskoi A., Borysov S., Shuda I., J. Phys. Stud., 2011, in press. 12. Newman M.E.J., SIAM Review, 2003, 45, 167; doi:10.1137/S003614450342480. 13. Sugden A.M., Jasny B.R., Culotta E., Pennisi E., Science, 2003, 300, 1691; doi:10.1126/science.300.5626.1691. 14. Olemskoi A.I., Ostrik V.I., Kokhan S.V., Physica A, 2009, 388, 609; doi:10.1016/j.physa.2008.11.019. Аналiтичне i чисельне дослiдження ймовiрностi утворення iєрархiчних дерев О.I. Олємской1,2, С.С. Борисов2, I.О. Шуда2 1 Iнститут прикладної фiзики НАН України, вул. Петропавлiвська, 58, 40030 Суми, Україна 2 Сумський державний унiверситет, вул. Римського-Корсакова, 2, 40030 Суми, Україна Розглянуто аналiтично i чисельно умови утворення рiзних iєрархiчних дерев. Дослiджено зв’язок мiж ймовiрностями утворення iєрархiчних рiвнiв та ймовiрностi об’єднання цих рiвнiв у єдину структуру. Показано, що побудова послiдовної ймовiрнiсної картини вимагає використання деформованої алгебри. Даний розгляд заснований на дослiдженнi основних типiв iєрархiчних дерев, серед яких регулярне i вироджене дослiдженi аналiтично, тодi як ймовiрностi утворення дерева Фiбоначчi, безмасштабного та довiльного дерева визначенi чисельно. Ключовi слова: ймовiрнiсть, iєрархiчне дерево, деформацiя 14001-6 http://dx.doi.org/10.1038/43601 http://dx.doi.org/10.1038/35036627 http://dx.doi.org/10.1073/pnas.021544898 http://dx.doi.org/10.1126/science.286.5439.509 http://dx.doi.org/10.1103/RevModPhys.58.765 http://dx.doi.org/10.1103/PhysRevLett.57.1965 http://dx.doi.org/10.1134/1.568335 http://dx.doi.org/10.1007/978-0-387-85359-8 http://dx.doi.org/10.1016/j.physa.2004.03.082 http://dx.doi.org/10.1137/S003614450342480 http://dx.doi.org/10.1126/science.300.5626.1691 http://dx.doi.org/10.1016/j.physa.2008.11.019 Introduction Statistical peculiarities of hierarchical ensembles Level probabilities for different hierarchical trees Concluding remarks