Motif based hierarchical random graphs: structural properties and critical points of an Ising model

A class of random graphs is introduced and studied. The graphs are constructed in an algorithmic way from five motifs which were found in [Milo R., Shen Orr S., Itzkovitz S., Kashtan N., Chklovskii D., Alon U., Science, 2002, 298, 824 – 827]. The construction scheme resembles that used in [Hinczewsk...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2011
Автори:	Kotorowicz, Monika, Kozitsky, Yuri
Формат:	Стаття
Мова:	English
Опубліковано:	Інститут фізики конденсованих систем НАН України 2011
Назва видання:	Condensed Matter Physics
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/119972
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Motif based hierarchical random graphs: structural properties and critical points of an Ising model / Monika Kotorowicz, Yuri Kozitsky // Condensed Matter Physics. — 2011. — Т. 14, № 1. — С. 13801: 1-18. — Бібліогр.: 30 назв. — англ.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-119972
record_format	dspace
spelling	irk-123456789-1199722017-06-11T03:04:03Z Motif based hierarchical random graphs: structural properties and critical points of an Ising model Kotorowicz, Monika Kozitsky, Yuri A class of random graphs is introduced and studied. The graphs are constructed in an algorithmic way from five motifs which were found in [Milo R., Shen Orr S., Itzkovitz S., Kashtan N., Chklovskii D., Alon U., Science, 2002, 298, 824 – 827]. The construction scheme resembles that used in [Hinczewski M., A. Nihat Berker, Phys. Rev. E, 2006, 73, 066126], according to which the short-range bonds are non-random, whereas the long-range bonds appear independently with the same probability. A number of structural properties of the graphs have been described, among which there are degree distributions, clustering, amenability, small-world property. For one of the motifs, the critical point of the Ising model defined on the corresponding graph has been studied. Вводиться i вивчається клас випадкових графiв, збудованих в алгоритмiчний спосiб з п’яти мотивiв, знайдених у [Milo R., Shen-Orr S., Itzkovitz S., Kashtan N., Chklovskii D., Alon U., Science, 2002, 298, 824]. Конструкцiйна схема нагадує схему, застосовану у [Hinczewski M., A. Nihat Berker, Phys. Rev. E, 2006, 73, 066126], згiдно з якою короткосяжнi ребра є невипадковi, тодi як довгосяжнi ребра виникають незалежно iз однаковою ймовiрнiстю. Описано ряд структурних властивостей графiв, серед яких є розподiл ступенiв, кластернiсть, аменабiльнiсть, властивiсть тiсного свiту. Для одного з мотивiв вивчається критична точка моделi Iзiнга, визначеної на вiдповiдному графi. 2011 Article Motif based hierarchical random graphs: structural properties and critical points of an Ising model / Monika Kotorowicz, Yuri Kozitsky // Condensed Matter Physics. — 2011. — Т. 14, № 1. — С. 13801: 1-18. — Бібліогр.: 30 назв. — англ. 1607-324X PACS: 89.75.Fb, 89.75.Kd, 05.10.Cc, 05.70.Jk DOI:10.5488/CMP.14.13801 arXiv:1106.4399 http://dspace.nbuv.gov.ua/handle/123456789/119972 en Condensed Matter Physics Інститут фізики конденсованих систем НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	English
description	A class of random graphs is introduced and studied. The graphs are constructed in an algorithmic way from five motifs which were found in [Milo R., Shen Orr S., Itzkovitz S., Kashtan N., Chklovskii D., Alon U., Science, 2002, 298, 824 – 827]. The construction scheme resembles that used in [Hinczewski M., A. Nihat Berker, Phys. Rev. E, 2006, 73, 066126], according to which the short-range bonds are non-random, whereas the long-range bonds appear independently with the same probability. A number of structural properties of the graphs have been described, among which there are degree distributions, clustering, amenability, small-world property. For one of the motifs, the critical point of the Ising model defined on the corresponding graph has been studied.
format	Article
author	Kotorowicz, Monika Kozitsky, Yuri
spellingShingle	Kotorowicz, Monika Kozitsky, Yuri Motif based hierarchical random graphs: structural properties and critical points of an Ising model Condensed Matter Physics
author_facet	Kotorowicz, Monika Kozitsky, Yuri
author_sort	Kotorowicz, Monika
title	Motif based hierarchical random graphs: structural properties and critical points of an Ising model
title_short	Motif based hierarchical random graphs: structural properties and critical points of an Ising model
title_full	Motif based hierarchical random graphs: structural properties and critical points of an Ising model
title_fullStr	Motif based hierarchical random graphs: structural properties and critical points of an Ising model
title_full_unstemmed	Motif based hierarchical random graphs: structural properties and critical points of an Ising model
title_sort	motif based hierarchical random graphs: structural properties and critical points of an ising model
publisher	Інститут фізики конденсованих систем НАН України
publishDate	2011
url	http://dspace.nbuv.gov.ua/handle/123456789/119972
citation_txt	Motif based hierarchical random graphs: structural properties and critical points of an Ising model / Monika Kotorowicz, Yuri Kozitsky // Condensed Matter Physics. — 2011. — Т. 14, № 1. — С. 13801: 1-18. — Бібліогр.: 30 назв. — англ.
series	Condensed Matter Physics
work_keys_str_mv	AT kotorowiczmonika motifbasedhierarchicalrandomgraphsstructuralpropertiesandcriticalpointsofanisingmodel AT kozitskyyuri motifbasedhierarchicalrandomgraphsstructuralpropertiesandcriticalpointsofanisingmodel
first_indexed	2025-07-08T17:00:13Z
last_indexed	2025-07-08T17:00:13Z
_version_	1837098879105892352
fulltext	Condensed Matter Physics 2011, Vol. 14, No 1, 13801: 1–18 DOI:10.5488/CMP.14.13801 http://www.icmp.lviv.ua/journal Motif based hierarchical random graphs: structural properties and critical points of an Ising model ∗ Monika Kotorowicz†, Yuri Kozitsky‡ Institute of Mathematics, Maria Curie-Skłodowska University, Lublin, Poland Received March 15, 2010, in final form June 7, 2010 A class of random graphs is introduced and studied. The graphs are constructed in an algorithmic way from five motifs which were found in [Milo R., Shen-Orr S., Itzkovitz S., Kashtan N., Chklovskii D., Alon U., Science, 2002, 298, 824–827]. The construction scheme resembles that used in [Hinczewski M., A. Nihat Berker, Phys. Rev. E, 2006, 73, 066126], according to which the short-range bonds are non-random, whereas the long-range bonds appear independently with the same probability. A number of structural properties of the graphs have been described, among which there are degree distributions, clustering, amenability, small-world property. For one of the motifs, the critical point of the Ising model defined on the corresponding graph has been studied. Key words: amenability, degree distribution, clustering, small-world graph, Ising model, critical point PACS: 89.75.Fb, 89.75.Kd, 05.10.Cc, 05.70.Jk 1. Introduction and setup A vast variety of large systems occurring in nature and society have a very complicated topolog- ical structure. These are the Internet, the World Wide Web, citation, neural, and social networks, etc. In view of the complex topology and unknown organizing principles, the networks are often modeled as random graphs. A random graph with a given node set V is a graph in which for a given pair i, j ∈ V , the bond 〈i, j〉 appears at random. The study of random graphs has been originated by P. Erdős and A. Rényi, who were the first to introduce such graphs in [1, 2]. In the Erdős-Rényi random graph model, denoted by Gn,p , the number of nodes is n, and the bonds between distinct nodes appear independently1 with the same probability p. An important characteristic of a graph is the node degree, which is the number of bonds attached thereat. In Gn,p , it is a random variable, and all such variables are independent and have the same probability distribution. Namely, the probability that the degree of a given node is k is given by the Bernoulli law Pn(k) = ( n− 1 k ) pk(1− p)n−1−k , k = 0, 1, . . . , n− 1. (1) For random graphs, the most interesting questions refer to their asymptotic properties in the limit n → +∞. To get nontrivial answers to such questions one allows the parameters to depend on n. For pn = c/n, the limit of (1) is the Poisson law P (k) = cke−c/k! , k ∈ N0. (2) However, for irregular complex networks, the random graph Gn,p is not a good model since in the most of such networks the degree distribution is essentially non-Poissonian. Many real world ∗This work was supported by the DFG through the project 436 POL 125/0–1 as well as through SFB 701: “Spektrale Strukturen und Topologische Methoden in der Mathematik”. Yuri Kozitsky was also supported by TODEQ MTKD–CT–2005–030042. †E-mail: monika@hektor.umcs.lublin.pl ‡E-mail: jkozi@hektor.umcs.lublin.pl 1C.f., however, the discussion in [3]. c© M. Kotorowicz, Yu. Kozitsky 13801-1 http://dx.doi.org/10.5488/CMP.14.13801 http://www.icmp.lviv.ua/journal M. Kotorowicz, Yu. Kozitsky networks, e.g. the WWW, are characterized by power-law node degree distributions, which have the form P (k) = Ck−γ , γ > 1, typical for the so-called scale-free graphs. Another important parameter characterizing a random graph is the clustering coefficient, which is the probability that two nodes are neighbors given they have a common neighbor. Clearly, in Gn,p this probability is p, and is the same independently of whether or not the nodes have a com- mon neighbor. Real world networks usually manifest strong clustering, which once more indicates that Erdős-Rényi type random graphs are not appropriate as their models. In [4], D.J. Watts and H. Strogatz proposed another type of random graphs, in which the mentioned disadvantage is overcome. It should be noted, however, that such graphs do not have power law node degree distri- butions. The next step beyond the Erdős-Rényi model was done by A.-L. Barabási and R. Albert in [5]. In their model, the preferential attachment principle has been employed, typical for many real networks (the Internet, citation and social networks). According to this principle, the more connected a node is, the more likely it receives a new bond. The construction of the Barabási- Albert model starts from an initial graph with m0 > 2 nodes (neither can be isolated). At each step, one adds a new node and connects it to the existing nodes. The probability pi that the new node is connected to node i is proportional to the degree ni of that node, that is, pi = ni/( ∑ j nj). Many of the complex networks occurring in nature contain characteristic patterns, recurring much more frequently than the other ones. They are called network motifs, see [6–11]. Different networks may have different motifs, and motifs in turn can characterize the networks. For instance, in biological regulation networks it has been experimentally demonstrated that each of the mo- tifs can perform a key information processing function, see [8]. In [10], the authors introduced a random graph model based on some geometric principles (constraints). Then, they compared the appearance of eight elementary three- and four-node patterns in their model with the same charac- teristics of the Erdős-Rényi random graph. It turned out that five of these patterns are motifs for their model, but not for the Erdős-Rényi random graph, see figure 1 below and table 1 in [10]. For J J J J J J J J � � � � � � � � @ @ @ @ Figure 1. Three and four node motifs M1,M2,M3,M4,M5 found in [10]. another random graph model, the appearance of the same eight patterns was also studied in [11]. Note that among these patterns, only M1 and M5 correspond to complete graphs (each node is a neighbor to every other node). One of the ways to get information about infinite graphs, also random ones, is to study the properties of certain models of statistical physics defined thereon. The most popular ones are the Ising and Potts models, as well as the models of bond and site percolation, see [12]. On the other hand, in statistical physics certain graphs are employed to mimic a crystal lattice, for which the critical-point behavior of the Ising model can be described in an explicit and rigorous way. These are the so-called hierarchical lattices introduced in [13]. Such lattices are defined in a rather algorithmic way by means of the basic pattern, e.g., by a “diamond”, which is the pattern M3 depicted in figure 1. A mathematical description of the Gibbs states of the Ising model on such graphs was done by P.M. Bleher and E. Žalys in [14, 15]. M. Hinczewski and A. Nihat Berker [16] studied the critical-point properties of the Ising model on the diamond hierarchical lattice ‘decorated’ by additional bonds, which appear at random. In the present paper, we follow the way suggested in [16] and introduce hierarchical graphs constructed by means of the motifs shown in figure 1, decorated by additional bonds which appear at random and repeat, in a way, the corresponding motif. We analyse some of their characteristics, such as the average degree, the node degree distribution, amenability, the small-world property, as well as the critical-point properties of the Ising model. This study of ours is a continuation of [17], where the graph based on M1 was introduced by one of us. Note that our hierarchical graphs also found applications in cryptography, see [18]. 13801-2 Motif based hierarchical random graph 2. The graphs: construction and structural properties 2.1. The construction: informal description As is typical for hierarchical graphs, e.g., for hierarchical lattices in [13, 16], the construction is carried out in an algorithmic way: at k-th level, k ∈ N, one produces a subgraph, say Λk , which is then used as a construction element for producing Λk+1 . The procedure is the same at each level, and the starting element is obtained from the corresponding motif. Let us illustrate this for the simplest case based on the motif M1 . First we label the nodes of M1 by a, b, and c, as it is shown in figure 2, and obtain Λ1 — the triangle. Then we take three such graphs and label them by the same labels. As a result, each of the triangles has nodes of two kinds: one node the label of which coincides with the triangle label (e.g., node a in triangle a), and two nodes with non-coinciding labels. Thereafter, the triangles are glued up according to the following rule: node c of triangle a is glued up with node a of triangle c, ect. The nodes with the coinciding labels remain untouched. These are the so-called external nodes of Λ2 . The remaining nodes are called internal. The bonds of the initial triangles turn into the bonds of Λ2 . We call them basic bonds; they are depicted by solid lines. At the next stage of the first step, we add the bonds connecting the external nodes in the same way as it is in the motif M1 . Such bonds are depicted by dotted lines and are called decorations. As a result, we obtain the graph Λ2 , which has six basic bonds and three decorations, three external and three internal nodes. Then we repeat the same procedure — take three copies of Λ2 , label them by a, b, and c, and divide their external nine nodes into two groups: three nodes with coinciding labels and six nodes with non-coinciding labels. Then the graphs Λ2 are glued up as described above. Thereafter, three decorating bonds are drawn to connect the external nodes. This procedure is repeated ad infinitum. Similar constructions for motifsM2 and M3 are presented in figure 3 and figure 4, respectively. Here we have omitted the decorating bonds not to overload the pictures. The picture forM4 is obtained from that forM3 by adding the diagonals. The picture for M5 is just the three-dimensional version of the picture for M1 , where the basic pattern is a tetrahedron. 2.2. Definitions In order to fix the terminology and to make the construction of our graphs mathematically immaculate, we begin by introducing a number of relevant mathematical notions. A (simple) graph G is a pair of sets (V,E), where V is the set of nodes, whereas E is a subset of the Cartesian product V × V. We suppose that E is symmetric and irreflexive, i.e., 〈j, i〉 ∈ E whenever 〈i, j〉 ∈ E, and 〈i, i〉 /∈ E for every i, j ∈ V. We say that i and j are connected by a bond if 〈i, j〉 ∈ E. In this case, we write i ∼ j and say that i and j are adjacent or that they are neighbors. Hence, the elements of E themselves can be called bonds. The graph is said to be complete if each two nodes are adjacent. For a given i, by n(i) we denote the degree of i — the number of its neighbors. If V is finite, then E is also finite, and the graph is said to be finite. Otherwise, the graph is infinite. An infinite graph is called locally finite, if n(i) is finite for every node. All the infinite graphs we study are countable, which means that both sets V and E are infinite and countable. Given G = (V,E) and G ′ = (V′,E′), let φ : V → V ′ be such that φ(i) ∼ φ(j) whenever i ∼ j. Such a map φ is called a morphism. A bijective morphism is called an isomorphism. If φ is an isomorphism, then its inverse φ−1 is also an isomorphism, and then the graphs G and G ′ are said to be mutually isomorphic. Such graphs have identical structures and thus can be identified. In this case, we also say that G′ is a copy of G. One observes that this refers to both finite and infinite graphs. An isomorphism φ : V → V, i.e. which maps the graph onto itself, is called an automorphism. The graph G ′ = (V′,E′) such that V ′ ⊂ V and E ′ ⊂ E is said to be a subgraph of G = (V,E). In this case, we write G ′ ⊂ G. Suppose that a subgraph G ′ ⊂ G has a copy, say G̃, that is, there exists an isomorphism φ : G̃ → G ′. Then φ, considered as a map φ : G̃ → G, is called an embedding of G̃ into G, whereas G ′ is called the image of G̃ under this embedding. Figure 1 presents the so-called unlabeled graphs, which we call patterns. After labeling, i.e., attaching a label to each of the nodes, such a pattern turns into a graph. Another labeling may or may not yield the same graph. This depends on whether or not 13801-3 M. Kotorowicz, Yu. Kozitsky there exists the corresponding automorphism. For instance, any labeling of the triangle M1 yields the same graph since in any case each of the nodes has the same neighbors. For the pattern M2 , the left-hand graph in figure 3 with the interchanged labels a and b is the same. However, the graph with the interchanges c and d is not the same anymore. Of course, this new graph is isomorphic to the initial one. This is because there is only one nontrivial automorphism of M2 : the one which interchanges a and b, and preserves c and d. The triangle has six automorphisms. Let us now turn to random graphs. To introduce such a graph we need an underlying graph G = (V,E) and a family E of subsets of E. If G is finite, as E one can take the set of all subsets of E. In the sequel, we deal with such graphs only. Thus, for E ′ ∈ E , we say that E ′ has been picked at random with probability P (E′). In the Erdős-Rényi model Gn,p , the underlying graph is complete with the node set V = {1, . . . , n}. In this model, P (E′) = p\|E ′\|, where p ∈ [0, 1] and \|E′\| stands for the number of elements in E ′. In other words, the elements of E are being picked independently, each with the same probability p. In a bit complicated model, the bonds are picked independently but with probability which depends on the bond. In this case, as well as in the case of the Erdős-Rényi model, we deal with a random graph with independent bonds. For such graphs, P (E′) = ∏ e∈E′ p(e), (3) where p(e) is the probability of picking bond e. The set of graphs G′ = (V,E′) with E ′ ∈ E is called the graph ensemble — each G ′ is picked at random from this ensemble. A random graph model is the pair consisting of the graph ensemble and of the function P : E → [0, 1]. If the function P is as in (3), the graph is said to be a random graph with independent bonds. Suppose that we have two random graph models with independent bonds. Let also G = (V,E) and G̃ = (Ṽ, Ẽ) be their underlying graphs and φ : V → Ṽ be a morphism. Then this map is said to be the morphism of the random graphs if for every 〈i, j〉 ∈ E, the probability (in the first model) that this bond is picked is the same as the corresponding probability (in the second model) for the bond 〈φ(i), φ(j)〉. 2.3. The construction As was mentioned above, each of our graphs is constructed in an algorithmic way from the cor- responding motif presented in figure 1. Since they are going to be random graphs with independent bonds, we have to construct the corresponding underlying graphs and, to define, for a given bond, the probability of being picked, c.f. (3). In all our models, the bonds will be of two kinds, which we call basic bonds and decorations. Basic bonds are going to be non-random, i.e. they are picked with probability one. Decorating bonds appear with probability p ∈ [0, 1], which is a parameter of the model. Turn now to the construction of the underlying graphs. Let q be the number of nodes in the corresponding motif, that is, q = 3 for M1 and q = 4 for the remaining motifs. At step k = 1, we just label the vertices of the corresponding motif by i = 1, . . . , q and obtain the initial graph Λ1 = (V1 , E1). All its bonds are set to be basic. Suppose now that we have q + 1 copies of Λ1 obtained by the isomorphisms φj2 , j = 0, 1, . . . , q. Thus, in j-th copy the nodes are φj2(i), i = 1, . . . , q. The graph Λ2 is obtained from these copies under the following conditions φ02(i) = φi2(i), i = 1, . . . , q; φi2(j) = φj2(i), i = 1, . . . , q, i 6= j. (4) Thus, the images of V1 under φi2 and φj2 with i 6= j intersect only at one node where (4) holds. The maps φj2 , j = 0, 1, . . . , q embed Λ1 into Λ2 . The nodes φi2(i), i = 1, . . . , q, are called the external nodes of Λ2 . All other nodes are called internal. Thus, Λ2 has q external and q(q − 1)/2 internal nodes. At this stage, we label them by i = 1, . . . , q(q + 1)/2 in such a way that the external nodes have the same labels as in Λ1 , that is, φ i 2(i) = i, i = 1, . . . q. By construction, the bonds obtained as images under the map φ02 are decorations: they are of the form 〈φ02(i), φ02(j)〉 where i and j are adjacent in Λ1 . From the first condition in (4) we see that the decorating bonds connect the external nodes of Λ2 . The remaining bonds of Λ2 are set to be basic. Now we construct Λ3 from one copy of Λ1 and q copies of Λ2 . Let φ 0 3 be the map which produces the copy of Λ1 and φj3 , 13801-4 Motif based hierarchical random graph j = 1, . . . , q be the maps which produce the copies of Λ2 . We then impose the conditions φ03(i) = φi3(i), i = 1, . . . , q; φi3(j) = φj3(i), i = 1, . . . , q, i 6= j (5) and obtain Λ3. Thus, φ 0 3 embeds Λ1 → Λ3 , and φ i 3 : Λ2 → Λ3 , i = 1, 2, . . . , q. As above, the nodes φi3(i) are set to be external, and the remaining nodes are internal. The images of V2 under φi3 and φj3 with i 6= j intersect only at one node where (5) holds. Again we label the nodes of Λ3 in such a way that φi3(i) = i, i = 1, . . . , q. Now let us establish which bonds of Λ2 are decorating and which are basic. As above, the bonds connecting the external nodes are decorating. The images of decorating bonds of Λ2 are decorating bonds in Λ3 ; the same is also true for the basic bonds — the basic bonds of Λ3 are exactly the images of the basic bonds of Λ2 . For k > 4, the construction of Λk from Λk−1 and Λ1 is identical to the construction of Λ3 just described. As above, by Vk and Ek we denote the sets of nodes and bonds of Λk , respectively. Thus, for k > 2 we have Ek = E′ k ∪E′′ k , where E′ k (respectively, E′′ k ) consists of basic (respectively, decorating) bonds. All Λk , k ∈ N, are considered as subgraphs of an infinite graph Λ∞ , the structure and properties of which are not important for the study presented in this article. Note that the construction principle used above essentially differs from that used in the con- struction of the hierarchical lattices in [13–16]. Namely, in our case to obtain Λk one replaces each node of the basic pattern by a copy of the graph Λk−1 . In the hierarchical lattices, one replaces a bond. As we shall see in the sequel, this leads to essentially different properties of the resulting graphs. Below in figure 2, we illustrate the construction described above for the case where the basic pattern is the motif M1 . In this case, the bare graph (i.e. the one which occurs for p = 0) is the approximating graph for the fractal known as the Sierpiński gasket2. The elements of E′ 2 (middle graph) and of E′ 3 (right-hand graph) are depicted by solid lines. The elements of E′′ 2 and of E′′ 3 are depicted by dotted lines. We omit some dotted lines to indicate that they appear at random and hence may be absent in a given realization of the graph. Note that Λ3 can be viewed as the triangle composed of three copies of Λ2 . In figure 3, we present the construction of the bare graph Λ3 corresponding to M2 . In contrast to the former case, this is not a planar graph. In figure 4, we construct the bare graph Λ2 for the motif M3 . One observes that in that picture the node c of the lower left-hand quadrat (i.e. quadrat a) is glued up with node a of the upper right-hand quadrat. It is interesting that the corresponding fractal can be obtained by the following procedure, resembling the one which yields the Sierpiński gasket. One takes the full quadrat and cuts it out into four equal quadrats, but without cutting the external lines. Then, one glues up the vertices of the smaller quadrats as depicted and proceeds with cutting out the smaller quadrats. The fractal which one obtains fromM5 is a three dimensional version of the Sierpiński gasket. One takes the full tetrahedron and cuts out its inner one fourth in such a way that the remaining four tetrahedra are glued up according to the rule: vertex b of tetrahedron a is glued up with vertex a of tetrahedron b, etc. J JJ a b c - J JJ J JJ J JJ a b γ c β α - J JJ J JJ J JJ J JJ J JJ J JJ J JJ J JJ J JJ a b c Figure 2. Construction of the graph Λ3 based on M1 . 2The fractal itself is obtained as the closure of the set ∪k∈NVk in the appropriate topology, see e.g. [19]. 13801-5 M. Kotorowicz, Yu. Kozitsky �� a b c d - �� a b c d - a �� α b �� β γ c � � � � � �� δ ǫ ζ d �� Figure 3. Construction of the bare graph Λ3 based on M2 . d c a b - d c a b Figure 4. Construction of the bare graph Λ2 based on M3 . 2.4. Degree distribution Now we turn to the description of the structural properties of the graphs constructed above. Let mk , k ∈ N, be the number of times the basic pattern appears in non-decorated Λk as a subgraph. For the graphs based on M1 and M5 we have the same situation. Here m1 = 1 and mk = qmk−1 , for k > 2 with the exception in Λ2 , where the additional pattern appears. So, for M1 and M5 we obtain m1 = 1 and mk = (q + 1)qk−2, k > 2. (6) Here q = 3 and q = 4 for M1 and M5 , respectively. For motif M3 we have m1 = 1, m2 = 2q and mk = qmk−1, k > 3. (7) Hence mk = 2 · 4k−1 for k > 2. The simplest case if for M4 , where mk = qmk−1 for k > 2. It gives m4 = 4k−1. The last motif is M2 – triangle with additional bond. On each level this bond “produces” new 17 patterns. So m1 = 1 and for k > 2 mk = 1 3 (26 · 4k−1 − 17). Now we analyze the number of times the basic pattern appears in fully decorated Λk , denoted by m̃k . For the graphs based on M1 and M5 we have m̃k = 2q + 1 q − 1 qk−1 + q + 2 q − 1 . (8) For M3 it is 2 34 k − 5 3 and for M4 we obtain 1 3 (4 k − 1). In all cases, we have mk increasing as C(p)qk−1, which means that adding decorations does not change the asymptotics of mk . 13801-6 Motif based hierarchical random graph In a similar way, we obtain \|Vk\| = qk + q 2 , \|Ek\| = rqk−1 + rp qk−1 − 1 q − 1 , k ∈ N, (9) where \|Vk\| stands for the number of nodes in Λk , whereas \|Ek\| is the expected number of bonds in this graph. As was mentioned above, the degree distribution is a very important characteristic of the graph. In contrast to Erdős-Rényi type graphs, for our graphs the distribution of the random variable n(i) depends on the type of i. Thus, the simplest way to describe this distribution is to average n(i) over the nodes of a given Λk , that is, to consider nk = 1 \|Vk\| ∑ i∈Vk n(i). (10) Let 〈nk〉 be the expected value of nk . Then 〈nk〉 = 2\|Ek\|/\|Vk\| = 4r q(q − 1) (q − 1 + p)− 4r q(q − 1) · q − 1 + 2p qk−1 + 1 . (11) However, this result provides only partial information on the node degree distribution. To get more, let us analyze the structure of the node sets Vk , k = 1, 2, . . ., more in detail. For a given Λk and l = 1, . . . , k, let V (l) k be the set of nodes i ∈ Vk which are external for some Λl and, at the same time, are internal for any Λl+1 . Of course, here we mean those Λl’s which are subgraphs for Λk . As an example, let us consider the graph Λ2 based on M1 , see the middle graph in figure 2. The nodes a, b, and c constitute V (2) 2 , whereas the remaining nodes constitute V (1) 2 . The elements of V (k−1) k are exactly the nodes at which the subgraphs Λj k−1 , j = 1, . . . , q are glued up to form Λk , whereas the elements of V (k) k are exactly the external nodes of Λk . Then \|V (k) k \| = q and \|V (k−1) k \| = q(q − 1)/2. For l < k − 1, we have \|V (l) k \| = q\|V (l) k−1\|, which can be solved to yield \|V (l) k \| = 1 2 qk−l(q − 1), l = 1, . . . , k − 1, \|V (k) k \| = q. (12) The reason to consider the sets V (l) k is that all the elements of each such V (l) k have the same degree distribution, independent of k for l 6 k− 1. In fact, the degrees of i ∈ V (1) k are non-random since these nodes receive no decorating bonds. For such i, n(i) = ∑ j n (0)(j), where n(0)(j) is the degree of the corresponding node in the basic pattern, and the sum is taken over all such patterns which are glued up. By the symmetry of M1 , M3 , and M5 , we have n(i) = 4 for M1 and M3 , and n(i) = 6 for M5 . For M2 , n(i) takes values 3, 4, 5, see figure 3. For i ∈ V (l) k , l = 2, 3, . . . , k− 1, we have n(i) = ñ(i) + ν(i), where ñ(i) is non-random and has to be calculated as just described. The summand ν(i) is the number of decorating bonds attached to i. To simplify our consideration, let us stick to the case of the graph generated by M1 . Then for l = 1, . . . , k− 1 and i ∈ V (l) k , we have ñ(i) = 4 and ν(i) takes values ν = 0, 1, 2, . . . , 4(l − 1), with probability Prob (ν(i) = ν) = ( 4(l− 1) ν ) pν(1 − p)4(l−1)−ν . (13) For i ∈ V (k) k , ν(i) takes values 0, 1, . . . , 2(k − 1). Therefore, the maximum node degree which can occur in Vk , k > 2, is max i∈Vk n(i) = 4k − 4. (14) As is usual in the theory of real world networks, which are in fact non-random, the randomness manifests itself as the random choice of a node. If we apply this principle here, then (13) can be considered as the conditional probability distribution, conditioned by the event that the node i 13801-7 M. Kotorowicz, Yu. Kozitsky has been picked from the set V (l) k . The probability of the latter event is taken to be proportional to the number of its elements, that is, Prob ( i ∈ V (l) k ) = \|V (l) k \| \|Vk\| = q − 1 1 + q1−k q−l = 2 1 + 31−k 3−l, l 6 k − 1, (15) Prob ( i ∈ V (k) k ) = 2q qk + q = 2 3k−1 + 1 . If we now take the expectation of n(i) with respect to this distribution, that is, 〈nk〉 = k−1∑ l=1 4(l−1)∑ ν=0 (4 + ν) 2 · 3−l 1 + 31−k · ( 4(l − 1) ν ) pν(1− p)4(l−1)−ν (16) + 2(k−1)∑ ν=0 (2 + ν) 2 3k−1 + 1 · ( 2(k − 1) ν ) pν(1 − p)2(k−1)−ν , we readily obtain 〈nk〉 = 4+2p−4(1+ p)/(3k−1 + 1), which is in full agreement with the one given in (11) or in table 1. In order to figure out the limit k → +∞ of the distribution given by (13) and (15) we calculate its characteristic function, c.f. (16), ϕk(t) = k−1∑ l=1 4(l−1)∑ ν=0 exp [it(4 + ν)] 2 · 3−l 1 + 31−k · ( 4(l − 1) ν ) pν(1− p)4(l−1)−ν (17) + 2(k−1)∑ ν=0 exp [it(2 + ν)] 2 3k−1 + 1 · ( 2(k − 1) ν ) pν(1− p)2(l−1)−ν = 2e4it 1 + 31−k · 1− 31−k ( eitp+ 1− p )4 3− (eitp+ 1− p) 4 + 2e2it 3k−1 + 1 ( eitp+ 1− p )2 , i = √ −1 . Then the limiting characteristic function is ϕ(t) = 2e4it 3− (eitp+ 1− p) 4 , (18) which can be continued to a meromorphic function analytic in some complex neighborhood of the point t = 0. This means that the limiting node degree distribution has all moments and hence cannot be of scale-free type3. This also agrees with the heuristic rule, see equation (3.13) on page 188 in [20], that for scale-free networks max i∈Vk n(i) ∼ \|Vk\|1/(α−1), α > 1, (19) whereas in our case we have (14) and \|Vk\| = (3k + 3)/2. In a similar way, one can show that all our graphs are not scale-free. Another observation on this item can be made by comparing the function (18) with the characteristic function of the Poisson distribution (2) which has the form ϕPoisson(t) = exp [ c ( eit − 1 )] , and hence can be continued to a function analytic on the whole complex plane. Therefore, the distribution corresponding to (18) with p > 0 is intermediate as compared to the Poisson and scale-free distributions. For p = 0, the function (18) is also entire. 3For scale-free graphs, the node degree distribution is P (k) = Ck−γ , k > 1, γ > 1; hence, ∑∞ k=1 kmP (k) diverges for all m > γ − 1. 13801-8 Motif based hierarchical random graph 2.5. Amenability, clustering, and small world properties The next property of our graphs which we are going to address is amenability. To introduce it we need one more notion. Let G = (V,E) be a countable graph with node set V and bond set E. For a finite ∆ ⊂ V , by ∂∆ we denote the set of nodes which are not in ∆ but have neighbors in ∆. This set is the outer boundary of ∆, whereas the elements of ∆ which are neighbors to the elements of ∂∆ constitute the inner boundary of ∆. As usual, by \|∆\| and \|∂∆\| we denote the number of nodes in these sets. The graph G is said to be amenable if there exists a sequence of finite node sets {∆k}k∈N , such that lim k→+∞ \|∂∆k\| \|∆k\| = 0. (20) If such a limit is positive for any sequence {∆k}k∈N , the graph is called nonamenabile. The lattices Z d, d > 1, are amenable graphs and for such sets one can take the cubes ∆k = {i = (i1, . . . id) ∈ Z d : \|ij \| 6 Nk , j = 1, . . . , d}, such that Nk+1 > Nk and Nk → +∞. In this case, \|∆k\| ∼ Nd k and \|∂∆k\| ∼ Nd−1 k and hence (20) holds. Sometimes, sequences for which (20) holds are called Van Howe sequences, see e.g. [21]. Cayley trees, except for Z, are nonamenable. Let us turn now to our graphs. Due to their hier- archical structure, it is convenient to check (20) for the sequence of node sets of Λk , that is for {Vk}k∈N . By the construction of Λk , the inner boundary of each Vk is exactly the set of all its external nodes, the number of which is equal to the number of nodes in the corresponding motif, i.e. it is q. By construction, one of them becomes an external node of Λk+1 , and the remaining q− 1 ones become inner nodes of Λk+1 . For all the motifs Mj , j = 1, . . . , 5, we have the degree of any node therein being at most 3, see figure 1. Then for all our graphs, max i∈Vk n(i) 6 6k, c.f. (14). At the same time, \|Vk\| ∼ qk, q = 3, 4, see (9), which immediately yields that all our graphs are amenable. Now we study the clustering in our graphs. For non-random graphs, the clustering coefficient is defined as follows. For a given node i ∈ V of degree n(i), let N(i) be the number of bonds linking its neighbors, which is the number of triangles with vertex i. Clearly, N(i) 6 n(i)[n(i)− 1]/2 and the maximum value of this parameter is attained for complete graphs where each node is a neighbor to any other one. Thus, the quantity Q(i) := 2N(i) n(i)[n(i)− 1] , (21) characterizes clustering at node i. Then we define the clustering of our graphs as Q = lim k→+∞ 1 \|Vk\| ∑ i∈Vk Q(i). (22) Note that for many graphs, e.g., for trees or bipartite graphs, one has Q(i) = 0 for any node i, see also [22, 23]. For random graphs, the degree n(i), as well as the parameter N(i), are random. Since in this case the calculation of Q is much more involved, we postpone it to the future. Here we only compare the values of Q obtained for the bare graphs with those for fully decorated ones. For the graph based onM1 and a node i ∈ V (l) k , l = 1, . . . , k−1, we have: (a) n(i) = 4, N(i) = 3 for l = 1, and N(i) = 2 for l > 2; (b) n(i) = 4l, N(i) = 4l. Here (a) and (b) correspond to a bare graph and to a fully decorated graph, respectively. These numbers follow directly from the construction of the graphs. The number of elements in each V (l) k is given in (12), which allows one to compute (a) Q = lim k→+∞ ( 1 3 + \|V (1) k \| 6\|Vk\| + 2 \|Vk\| ) = 4 9 = 0.4444 . . . , (23) 13801-9 M. Kotorowicz, Yu. Kozitsky (b) Q = 2 · 3−1/4 arctan 3−1/4 − 1 31/4 ln 31/4 + 1 31/4 − 1 ≈ 0.525897. (24) For the bare graph based on M3 , we have N(i) = 0 for all nodes; hence, Q = 0 in this case. For the fully decorated graph based on M3 , we observe that two nodes of V (1) 2 have neighbors only in V (1) 2 , and the remaining four nodes have two neighbors in V (1) 2 and two — in V (2) 2 . Since for the nodes i ∈ V (1) 2 , we have N(i) = 0, like in the case of the bare graph, we should consider these two groups separately. Thus, we split each V (l) k , l = 1, . . . , k− 1, into V (l) k,0 and V (l) k,1 , where the first set consists of the nodes which have neighbors only in V (l) k,0 . The elements of V (l) k,1 have also neighbors in V (l′) k with l′ > l. The number of nodes in these sets are: \|V (l) k,0 \| = 1 2 4k−l, \|V (l) k,1 \| = 4k−l. For all i ∈ V (l) k , l = 1, . . . , k− 1, we have n(i) = 4l. At the same time, N(i) = 4(l− 1) for i ∈ V (l) k,0 , and N(i) = 1 + 4(l− 1) for i ∈ V (l) k,1 . Putting all these numbers together we obtain Q = 3 2 ∞∑ l=2 (l − 1)4−(l−1) l(4l− 1) + ∞∑ l=1 4−l l(4l− 1) ≈ 0.1223. (25) For the bare graph based on M5 one can obtain for i ∈ V (l) k , l = 1, 2, . . . , k − 1: n(i) = 6, N(i) = 8 for l = 1, and n(i) = 6, N(i) = 6 for l > 2. For the fully decorated graph based on M5 we have for all internal nodes n(i) = 6l, and N(i) = 9 for l = 1, and N(i) = 12l+7 for l > 2. Hence, we obtain (a) Q = lim k→+∞ ( 2 5 + 2\|V (1) k \| 15\|Vk\| + 12 5\|Vk\| ) = 0.5, (26) (b) Q ≈ 0.554145. There exists one more property of real world networks, which Erdős-Rényi type graph does not share, see e.g. [20, 24]. It is the so-called small-world property, illustrated by Pal Erdős himself in the following way. All authors of mathematical papers are given the Erdős index which for his coauthors is equal to one. For their coauthors who are not Erdős’ coauthors, this index is equal to 2, and so on. Everyone whose papers are indexed by the Mathematical Reviews can check his own index at the web-site http://www.ams.org/mathscinet/. It turns out that for many authors it ranges from 2 to 6 (for the second named author of this paper it is 4). To formulate the small-world property one needs the following notion. A path in the graph is a sequence of nodes such that every two consecutive elements of this sequence are neighbors to each other. The length of the path is the number of such consecutive pairs, which is equal to the number of bonds one passes on the way from the origin to the terminus. If every two nodes can be connected by a path, the graph is said to be connected. For the given two nodes, i and j, the length of the shortest path which connects them is said to be the distance ρ(i, j) between these nodes. Informally speaking, a graph G = (V,E) has the small-world property (or is a small-world graph) if every two nodes i, j ∈ V are “not too far” from each other. More precisely this property is formulated as follows. An infinite graph G has a small-world property if there exists a sequence of its connected finite subgraphs {Gk}k∈N with the following property. Let diam(Gk) = maxi,j∈Vk ρ(i, j) be the diameter of Gk , k ∈ N, and 〈nk〉 be the average value of the node degree in Gk , that is, 〈nk〉 = 2\|Ek\|/\|Vk\|. Then the sequence {Gk}k∈N , and hence the graph G, are said to have the small-world property if there exists a positive constant C such that for all k ∈ N, diam(Gk) 6 C log〈nk〉 \|Vk\|. (27) This means that in such graphs, the distances between the nodes scale at most logarithmically with the size of the graph. For our graphs, the results on this item are given in the last three rows 13801-10 http://www.ams.org/mathscinet/ Motif based hierarchical random graph of table 1. The diameters of Λk presented therein were calculated in a routine way for the cases where the graphs are bare (p = 0) or are fully decorated (p = 1). In the former case, neither of our graphs has the small-world property. However, this property holds for all fully decorated graphs. Table 1. The structural characteristics of the families of hierarchical graphs. motif M1 M2 M3 M4 M5 \|Vk\| 3 2 (3 k−1 + 1) 2(4k−1 + 1) 2(4k−1 + 1) 2(4k−1 + 1) 2(4k−1 + 1) \|Ek\| 3k 4k 4k 5 · 4k−1 6 · 4k−1 3 2 (3 k−1 − 1)p 4 3 (4 k−1 − 1)p 4 3 (4 k−1 − 1)p 5 3 (4 k−1 − 1)p 2(4k−1 − 1)p 〈nk〉 4 + 2p 4 + 4 3p 4 + 4 3p 5 + 5 3p 6 + 2p −4 1+p 3k−1+1 − 4 3 3+2p 4k−1+1 − 4 3 3+2p 4k−1+1 − 5 3 3+2p 4k−1+1 −2 3+2p 4k−1+1 diam(Λk), p = 0 2k−1 2k 2k 2k 2k−1 diam(Λk), p = 1 k k + 1 2(k − 1) k k C, p = 1 (log6 3) −1 (log6 4) −1 2(log6 4) −1 (log7 4) −1 (log8 4) −1 In table 1, we collected the structural characteristics of our graphs based on the motifsM1 , . . . , M5 given in figure 1. Its first three rows are obtained from the formulas (9) and (11). 3. Graph structure and the Ising model properties As was mentioned above, there exists a profound connection between the properties of Gibbs random fields of models based on graphs and the structural properties of these graphs4. For the hierarchical lattices, the notion of the Gibbs random field of the Ising model was introduced in [14, 15]. In the physical terminology, each (pure) Gibbs random field corresponds to a state of thermal equilibrium of the model, see [25] for more details. Accordingly, the existence of multiple Gibbs random fields corresponds to the existence of multiple equilibrium states and hence of phase transitions. If there is no interaction between the spins, the Gibbs random field is unique. However, if the interaction is strong enough and if it is effectively propagated by the underlying graph (high enough “connectivity”), the Gibbs fields can be multiple. The condition of high connectivity is essential, which can be seen from the fact that the Ising model on the one-dimensional lattice Z, considered as a graph with the natural adjacency relation, bears only one Gibbs field and hence no phase transitions can occur in this case – no matter how strong the interaction is. With regard to these arguments, we can divide all graphs into three groups according to the following property of the Ising model defined on these graphs: (a) There exists only one Gibbs random field for all interactions. (b) There exists only one Gibbs random field for weak interactions, and multiple Gibbs random fields for strong interactions. (c) There exist multiple Gibbs random fields for all nonzero interactions. 4Of course, we are speaking now about countably infinite graphs. 13801-11 M. Kotorowicz, Yu. Kozitsky As was mentioned above, the lattice Z belongs to the first group. The lattices Z d with d > 2, as well as all Cayley trees5 belong to the second group. An example of the graph belonging to the third group can be found in section 4 of [26]. Clearly, the above classification should be made more precise for random graphs, since in this case the existence of a Gibbs random field is a random event. We return to this issue below. The Ising model defined on the graphs from the second group may have a critical point, which separates the regime of uniqueness (weak interactions) from the regime of non-uniqueness (strong interactions). At their critical point, the Gibbs random fields have “unusual” properties, which can be detected without explicit construction of these fields. One of such properties is the so- called self-similarity, which manifests itself in the appearance of unstable fixed points of some (renormalization) transformations. It turns out that the hierarchical graphs are quite suitable for such a study — that it why they appear in this context. Thus, one can have the following criterion: if the Ising model has a critical point, the graph belongs to the second group. If not, then the graph belongs either to the first or to the third group. The latter cases can be distinguished by an additional study. In contrast to the hierarchical lattices introduced and studied in [16], our bare graphs belong to the first group. This can be seen from the analysis which we present below — a direct proof of such a statement will be done in our forthcoming publication. Thus, the interaction along the decorating bonds plays the main role in the possible appearance of phase transitions in the Ising model defined on our graphs. In view of this fact, we will assume that the solid bonds bear the interaction K, whereas the dotted bonds bear the interaction L. As the bonds of the latter kind appear at random, we can think of the corresponding model as of the one defined on the fully decorated graph with random interactions along the decorating bonds. Thus, in this model, the interaction along each bond 〈i, j〉 is a random variable, denoted by Lω ij , which takes values 0 and some nonzero L ∈ R with probabilities 1−p and p, respectively. For different bonds, these random variables are independent. For a given k ∈ N, the Ising model on the fully decorated graph Λk is defined in the usual way by assigning spin variables σi = ±1 to the nodes i ∈ Vk and by setting the Hamiltonian − βHk = h ∑ i∈Vk σi +K ∑ 〈i,j〉∈E′ k σiσj + ∑ 〈i,j〉∈E′′ k Lω ijσiσj , h,K ∈ R, k ∈ N, (28) where h is an external field. In accordance with the above arguments, the third summand cor- responds to the interaction along decorating bonds. We have included the first term in view of the following arguments. As is known, the Ising model on the lattices Z d, d > 2, exhibits phase transitions only if h = 0. This is also the case if the graph is amenable and quasi-transitive. For nonamenable graphs, this model may have a phase transition for nonzero h, see [27]. By the construction of our graphs, each Λk has q external nodes, i1, . . . , iq , and the correspond- ing number of internal nodes, see table 1. Such external nodes can be considered as a boundary of Λk . Correspondingly, we call the spin variables external or boundary (respectively, internal) spins if they are assigned to external (respectively, internal) nodes. For a fixed configuration of the external spins σi1 , . . . , σiq , we consider Zω k (σi1 , . . . , σiq ) = ∑ internal spins of Λk exp (−βHk) . (29) This is the conditional partition function of the spin system in Λk , conditioned by the fixed configuration of spins on the boundary of Λk . Of course, it depends on the graph, i.e. on the motif used in its construction. According to the main principle of the theory of Gibbs random fields applied in our context, see [25], the fact that such a field is unique is ensured by the conditional partition function asymptotic independence, as k → +∞, of the boundary spins. For our graphs, Zω k are random and hence also depend on ω. In this situation, one can apply the following two approaches: the above mentioned independence holds (i) for almost all ω; (ii) in average. The latter 5Except for Z, see page 247 in [25]. 13801-12 Motif based hierarchical random graph corresponds to the fact that the expected values of Zω k , which we denote by 〈Zω k 〉, are independent of the boundary spins. These two approaches are called quenched and annealed disorders, respectively, see [28], page 99. We will work in the annealed approach. It can be shown that the summands in (29) are positive and separated from zero. Since the number of these summands increases to +∞ as k → +∞, we have 〈Zω k 〉 → +∞. Therefore, a weaker form of the uniqueness condition can be lim k→+∞ 〈Zω k (σi1 , . . . , σiq )〉/〈Zω k (σ ′ i1 , . . . , σ ′ iq )〉 = c, (30) which holds for any two configurations of the boundary spins and for some c > 0, which depends on these configurations. The convergence in (30) should be stable with respect to small changes of h and K, i.e. of the starting element Z1 . In this case, the annealed limiting free energy per spin is independent of the boundary configuration. Correspondingly, a necessary condition for the latter quantity to be dependent on the boundary spins is that lim k→+∞ 〈Zω k (σi1 , . . . , σiq )〉/〈Zω k (σ ′ i1 , . . . , σ ′ iq )〉 = +∞, (31) for some σi1 , . . . , σiq and σ′ i1 , . . . , σ ′ iq . We say that the Ising model defined on our graph has a critical point, if there exists c′ > 0, distinct from c in (30), such that for K = K∗ and h = h∗ , lim k→+∞ 〈Zω k (σi1 , . . . , σiq )〉/〈Zω k (σ ′ i1 , . . . , σ ′ iq )〉 = c′. (32) Here K∗ and h∗ are certain values of the interaction intensity and the external field. The conver- gence in (32) should be such that for arbitrarily small deviations from the point (K∗ , h∗) one has either (30) or (31) instead of (32). Note that we do not exclude that h∗ 6= 0 since our graphs are not quasi-transitive and hence the result of [27] may not be applicable in this case. 4. Critical points of the Ising model on M1 based graph For k = 1, we have only basic bonds and no inner nodes. Thus, Z1(a, b, c) = exp [−βH1(a, b, c)] = exp[K(ab+ ac+ bc) + h(a+ b+ c)], (33) where we use the same notations for the nodes a, b, c, see the left-hand graph in figure 2, as well as for the corresponding spin variable, that is, for short we write a = σa , b = σb , ect. For k = 2, we have, see the middle graph in figure 2, −βH2(a, b, c, α, β, γ) = −βH1(a, γ, β)− βH1(γ, b, α)− βH1(β, α, c) + Lω abab+ Lω bcbc+ Lω acac. Thus, to obtain Z2(a, b, c) we have to sum out the internal spins, see (29). That is, Zω 2 (a, b, c) = exp [Lω abab+ Lω acac+ Lω bcbc] ∑ α,β,γ Z1(a, γ, β)Z1(γ, b, α)Z1(β, α, c), where the sum is taken over α, β, γ = ±1. According to the hierarchical structure of the underlying graph, for all k > 2 the graph Λk is obtained from the subgraphs Λk−1 exactly in the same way. This yields the following recurrence for the partition functions (29) Zω k (a, b, c) = Rω k (a, b, c) ∑ α,β,γ Zk−1(a, γ, β)Zk−1(γ, b, α)Zk−1(β, α, c), (34) where Rω k (a, b, c) = exp [Lω abab+ Lω acac+ Lω bcbc] , (35) and Z1(a, b, c) is given in (33). From the independence of Lω ij for different bonds, it follows that the random variables Zω k−1 on the right-hand side of (34) are independent, which allows us to compute the expectations and obtain 〈Zω k (a, b, c)〉 = 〈Rω k (a, b, c)〉 ∑ α,β,γ 〈Zω k−1(a, β, γ)〉〈Zω k−1(α, b, γ)〉〈Zω k−1(α, β, c)〉. (36) 13801-13 M. Kotorowicz, Yu. Kozitsky We recall that the random variables Lω ij take the values L 6= 0 and 0 with probabilities p and 1− p, respectively. In view of the model symmetry, c.f. (33), the system (36) involves the following variables Ak = 〈Zω k (1, 1, 1)〉, Bk = 〈Zω k (1, 1,−1)〉, (37) Ck = 〈Zω k (−1,−1, 1)〉, Dk = 〈Zω k (−1,−1,−1)〉, which have the initial values A1 = e3(K+h), B1 = e−K+h, C1 = e−K−h, D1 = e3(K−h). (38) By direct calculations, 〈Rω k (1, 1, 1)〉 = (p exp(L) + 1− p)3, (39) 〈Rω k (−1, 1, 1)〉 = (p exp(L) + 1− p)(p exp(−L) + 1− p)2. Thereafter, the recursion (36) can be written in the form xk+1 = t Px(xk, yk) Q(xk, yk, zk) , (40) yk+1 = Py(xk, yk, zk) Q(xk, yk, zk) , zk+1 = t Pz(yk, zk) Q(xk, yk, zk) , with the initial conditions x1 = e4(K+h), y1 = e2h, z1 = e4K−2h, (41) where we have used the notations xk = Ak/Ck , yk = Bk/Ck , zk = Dk/Ck , k ∈ N, (42) and t = ( p eL + 1− p p e−L + 1− p )2 . (43) The polynomials in (40) have the following form Px(x, y) = x3 + 3xy2 + 3y2 + 1, (44) Py(x, y, z) = x2y + y3 + 2xy + y2z + 2y + z, Pz(y, z) = y3 + 3y + 3z + z3, Q(x, y, z) = xy2 + x+ 2y2 + 2yz + z2 + 1. For every t > 0, the mapping (xk , yk , zk) 7→ (xk+1 , yk+1 , zk+1) = Tt(xk , yk , zk) , defined in (40) and (44), maps the first octant of R3 into itself. The starting point (x1 , y1 , z1) lies on the surface S defined by the equation, c.f. (41), x = y3z, (45) which, however, is not preserved by this mapping, which can be checked directly. Let Tt be the invariant set of the map Tt , that is, the set of points (x, y, z) such that Tt(x, y, z) = (x, y, z). Suppose that the intersection of Tt with S is non-void. If (x∗ , y∗ , z∗) belongs to this intersection 13801-14 Motif based hierarchical random graph - 6 � � � � � � � � � � � 4 3 t x (1) ∗ x (2) ∗ φt(x) Figure 5. Graphical solution of (48). and (x1 , y1 , z1) = (x∗ , y∗ , z∗) , then (xk , yk , zk) = (x∗ , y∗ , z∗) for all k ∈ N. Let us find such points. From the second equation in (40) for x = y3z we get yQ(y3z, y, z) = Py(y 3z, y, z), which can be transformed into the following y3(1 + y3z)(1− yz) = (y + z)(1− yz). (46) A solution of the latter equation is z = 1/y, thus x = y2, which being used in the first equation in (40) yields (1 + y2)2 = t(1 + y2)2 and hence t = 1. For p > 0, the latter implies L = 0, and also K = 0, see (41). This fixed point corresponds to a noninteracting system of spins in an external field and thereby has nothing to do with critical points. For z 6= 1/y, from (46) we get z(1− y2)(y4 + y2 + 1) = −y(1− y2), (47) which for positive y and z has a unique solution y = 1, and hence x = z. We insert this into the first equation in (40) and obtain x = t x3 + 3x+ 4 x2 + 4x+ 3 = t x2 − x+ 4 x+ 3 := φt(x). (48) For t = 1, the only solution is x = 1, which corresponds to L = K = 0. The choice t = 1 also corresponds to a bare graph (p = 0); hence, the bare graph based on M1 has no critical points and no phase transitions. As we have already mentioned above, in a separate work we prove that the Gibbs states of the Ising model based on this graph are always unique. For t < 1, that is, for L < 0, (48) has only one positive solution x∗ = −3− t+ √ 9 + 22t− 15t2 2(1− t) < 1, (49) which corresponds to K∗ < 0. It is stable and (xk , yk , zk) → (x∗, 1, x∗) as k → +∞, for any (x1 , y1 , z1) ∈ S. Thus, for L < 0, the Ising model has no critical points and no phase transitions, even for the fully decorated graph. This can be caused by a frustration, which takes place in an antiferromagnetic Ising model on triangles. For t > 1, figure 5 presents the graphical solutions of (48). They have the following form x (1) ∗ = 3 + t− √ 9 + 22t− 15t2 2(t− 1) , x (2) ∗ = 3 + t+ √ 9 + 22t− 15t2 2(t− 1) . (50) By direct calculations, we get φ′t(x (1) ∗ ) < 1 and φ′t(x (2) ∗ ) > 1, see figure 5. Hence, x (1) ∗ is stable, whereas x (2) ∗ is unstable. Note also that x (1) ∗ → 1 and x (2) ∗ → ∞ as t→ 1. The solutions (50) exist and are considered to be distinct, provided t ∈ (1, 9/5). This yields the condition p < ψ(L) := 3− √ 5√ 5 exp(L)− 3 exp(−L) + 3− √ 5 . (51) 13801-15 M. Kotorowicz, Yu. Kozitsky Since ψ(L) is a decreasing function, the equation ψ(L) = 1 has only one solution L∗ = 1 4 ln 9 5 . (52) Then, for L 6 L∗ , the critical point exists for all p ∈ (0, 1]. For such L and p, let K∗(L, p) be the solution of the equation exp(4K) = x (2) ∗ . (53) Then lim k→+∞ xk =    x (1) ∗ if x1 < exp[4K∗(L, p)], x (2) ∗ if x1 = exp[4K∗(L, p)], +∞ if x1 > exp[4K∗(L, p)]. (54) The conditions in (54) can be formulated directly for K, e.g. xk → x (1) ∗ if K < K∗(L, p). Thus, x (1) ∗ is the so-called high-temperature fixed point. For L > L∗ , we have ψ(L) < 1. Hence, the condition (51) is not satisfied for p ∈ (ψ(L), 1], which also includes the fully decorated graph with p = 1. For such L and p, the whole graph of φt lies above the line φt(x) = x, which means that xk → +∞ for all initial x1 > 0. Thus, for L > L∗ and p ∈ (ψ(L∗), 1], the model has no critical points and the Gibbs random fields are multiple for all K ∈ R. For p = ψ(L∗), we have t = 9/5 and x (1) ∗ = x (2) ∗ = 3, which corresponds to K∗ = (ln 3)/4. In this case, xk → 3 if K 6 K∗ , and xk → +∞ if K > K∗ . 5. Concluding remarks 5.1. Construction and structural properties The graphs introduced in this paper are constructed from motifs M1 , . . . ,M5 in an algorithmic way, like the hierarchical lattices introduced in [13], and employed in [16] where they were supplied with long-range (decorating) bonds. However, our main construction principle — to replace nodes with the graphs of the previous level — differs from the one used in those papers, where the graphs of the previous level replaced the bonds. Hierarchical graphs of this kind model the real world networks with the so-called modular structure, which are organized in tightly knit communities with relatively sparse connections between them. For more details herein, we refer the reader to [29, 30] and to the publications cited therein. In contrast to the graphs introduced in [16], see also [29], our decorated graphs are not scale-free. For them, the node degree distribution is of intermediate type such that all the moments exist. The corresponding characteristic function can be extended to a meromorphic function, analytic in the complex neighborhood of zero, see (18), whereas for scale-free graphs such functions are nonanalytic at zero. All our graphs are amenable, which correlates with the property just discussed, see (14), (9), and (19). An interesting property is that, like for the graphs studied in [16], adding decorations forms the graphs possessing the small-world property. 5.2. Critical points The appearance of critical points, and hence of phase transitions, for the Ising model confirms good communicating properties of the underlying graphs. For our graphs, in contrast to the hierar- chical lattices for which phase transitions take place even without decorations, critical points can exist only if the decorations are applied, with any p > 0. The most interesting related fact is that for the graph based on M1 , the antiferromagnetic Ising model has no phase transitions for any L and p. This is due to the generic frustration of such models — the elementary factor Rk(a, b, c) which appears in (35) with negative L cannot be maximized. We expect that the same is true for the graphs based on M5. To check if this conjecture of ours is true we plan to study a Potts model on the same graph and q > 3, for which such a frustration is no longer actual. We also plan to 13801-16 Motif based hierarchical random graph look for critical points with nonzero h, as well as for critical points of the Ising model with the underlying graphs based on the remaining motifs. However, the corresponding problems are much tougher, so that the appropriate numerical means should be applied. 6. Acknowledgement The authors benefited from fruitful discussions on the matter of this work held with our col- leagues Yuri Kondratiev and Vasyl Ustimenko for which they are cordially grateful. The authors are also grateful to the unnamed referee whose remarks and suggestions were helpful in improving the presentation of the article. References 1. Erdős P., Rényi A., Publicationes Mathematicae, 1959, 6, 290. 2. Erdős P., Rényi A., Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 1960,5, 17. 3. Bia las, P., Burda, Z., Wac law, B. Causal and homogeneous networks. In: Science of complex networks, 14,AIP Conf. Proc., 776, Amer. Inst. Phys., Melville, NY, 2005. 4. Watts D.J., Strogatz H., Nature, 1998, 393, 440; doi:10.1038/30918. 5. Barabási A.-L., Albert R., Science, 1999, 286, 509; doi:10.1126/science.286.5439.509. 6. Milo R. et al., Science, 2002, 298, 824; doi:10.1126/science.298.5594.824. 7. Itzkovitz S. et al., Phys. Rev. E, 2003, 68, 026127; doi:10.1103/PhysRevE.68.026127. 8. Alon U., Science, 2003, 301, 1866; doi:10.1126/science.1089072; Nature Reviews Genetics, 2007, 8, 450; doi:10.1038/nrg2102. 9. Kashtan N., Itzkovitz S., Milo R., Alon U., Phys. Rev. E, 2004, 70, 031909; doi:10.1103/PhysRevE.70.031909. 10. Itzkovitz S., Alon U., Phys. Rev. E, 2005, 71, 026117; doi:10.1103/PhysRevE.71.026117. 11. Matias C. et al, REVSTAT, 2006, 4, 31. 12. Häggström O., Adv. Appl. Probab., 2000, 32, 39. 13. Griffiths R.B., Kaufman M., Phys. Rev. B, 1982, 26, 5022; doi:10.1103/PhysRevB.26.5022. 14. Bleher P.M., Žalys E., Litovsk. Mat. Sb., 1988, 28, 252 [English translation in Lithuanian Math. J., 1989, 28, 127; doi:10.1007/BF01027189]. 15. Bleher P.M., Žalys E., Commun. Math. Phys., 1989, 120, 409; doi:10.1007/BF01225505. 16. Hinczewski M., A. Nihat Berker, Phys. Rev. E, 2006, 73, 066126; doi:10.1103/PhysRevE.73.066126. 17. Wróbel M., Condens. Matter Phys., 2008, 11, 341. 18. Kotorowicz M., Albanian Journal of Mathemathics, 2008, 3, 235. 19. Barlow M.T. Heat kernels and sets with fractal structure. In: Heat kernels and analysis on manifolds, graphs, and metric spaces (Paris, 2002). Contemp. Math., 338, Amer. Math. Soc., Providence, RI, 2003. 20. Newman M.E.J., SIAM Review, 2003, 45, 167; doi:10.1137/S003614450342480. 21. Ruelle D., Statistical mechanics: Rigorous results. W.A. Benjamin, Inc., New York–Amsterdam, 1969. 22. Erdős P., Kleitman D.J., Rothschild B.L., Asymptotic enumeration of Kn-free graphs. In: Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo II, pp. 19. Atti dei Convegni Lincei, No. 17, Accad. Naz. Lincei, Rome, 1976. 23. Futorny V., Ustimenko V., Acta Appl. Math., 2007, 98, 47; doi:10.1007/s10440-007-9144-8. 24. Barrat A., Weigh M., Eur. Phys. J. B, 2000, 13, 547; doi:10.1007/s100510050067. 25. Georgii H.-O., Gibbs measures and phase transitions. de Gruyter Studies in Mathematics, 9. Walter de Gruyter & Co., Berlin, 1988. 26. Kȩpa D., Kozitsky Y., Condens. Matter Phys., 2008, 11, 313. 27. Jonasson J, Steif J.E., J. Theoret. Probab., 1999, 12, 549; doi:10.1023/A:1021690414168. 28. Bovier, A., Statistical mechanics of disordered systems. A mathematical perspective. Cambridge Se- ries in Statistical and Probabilistic Mathematics, Cambridge University Press, Cambridge, 2006; doi:10.1017/CBO9780511616808.004. 29. Hinczewski M., Phys. Rev. E, 2007, 75, 06611104; doi:10.1103/PhysRevE.75.061104. 30. Kashtan N., Mayo A.E., Kalisky T., Alon U., PLoS Comput. Biol., 2009, 5, e1000355; doi:10.1371/journal.pcbi.1000355. 13801-17 http://dx.doi.org/10.1038/30918 http://dx.doi.org/10.1126/science.286.5439.509 http://dx.doi.org/10.1126/science.298.5594.824 http://dx.doi.org/10.1103/PhysRevE.68.026127 http://dx.doi.org/10.1126/science.1089072 http://dx.doi.org/10.1038/nrg2102 http://dx.doi.org/10.1103/PhysRevE.70.031909 http://dx.doi.org/10.1103/PhysRevE.71.026117 http://dx.doi.org/10.1103/PhysRevB.26.5022 http://dx.doi.org/10.1007/BF01027189 http://dx.doi.org/10.1007/BF01225505 http://dx.doi.org/10.1103/PhysRevE.73.066126 http://dx.doi.org/10.1137/S003614450342480 http://dx.doi.org/10.1007/s10440-007-9144-8 http://dx.doi.org/10.1007/s100510050067 http://dx.doi.org/10.1023/A:1021690414168 http://dx.doi.org/10.1017/CBO9780511616808.004 http://dx.doi.org/10.1103/PhysRevE.75.061104 http://dx.doi.org/10.1371/journal.pcbi.1000355 M. Kotorowicz, Yu. Kozitsky Iєрархiчнi випадковi графи з мотивiв: структурнi властивостi та критичнi точки моделi Iзiнга Монiка Которович, Юрiй Козицький Iнститут математики, Унiверситет Марiї Кюрi-Склодовської, Люблiн Вводиться i вивчається клас випадкових графiв, збудованих в алгоритмiчний спосiб з п’яти мотивiв, знайдених у [Milo R., Shen-Orr S., Itzkovitz S., Kashtan N., Chklovskii D., Alon U., Science, 2002, 298, 824]. Конструкцiйна схема нагадує схему, застосовану у [Hinczewski M., A. Nihat Berker, Phys. Rev. E, 2006,73, 066126], зг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нга, критична точка 13801-18 Introduction and setup The graphs: construction and structural properties The construction: informal description Definitions The construction Degree distribution Amenability, clustering, and small world properties Graph structure and the Ising model properties Critical points of the Ising model on M1 based graph Concluding remarks Construction and structural properties Critical points Acknowledgement

Motif based hierarchical random graphs: structural properties and critical points of an Ising model

Репозитарії

Схожі ресурси