Modelling complex networks by random hierarchical graphs
Numerous complex networks contain special patterns, called network motifs. These are specific subgraphs, which occur oftener than in randomized networks of Erd˝os-R´enyi type. We choose one of them, the triangle, and build a family of random hierarchical graphs, being Sierpi ´nski gasket-based gra...
Збережено в:
| Опубліковано в: : | Condensed Matter Physics |
|---|---|
| Дата: | 2008 |
| Автор: | |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут фізики конденсованих систем НАН України
2008
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/119146 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Modelling complex networks by random hierarchical graphs / M. Wróbel // Condensed Matter Physics. — 2008. — Т. 11, № 2(54). — С. 341-346. — Бібліогр.: 9 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-119146 |
|---|---|
| record_format |
dspace |
| spelling |
Wróbel, M. 2017-06-04T17:24:02Z 2017-06-04T17:24:02Z 2008 Modelling complex networks by random hierarchical graphs / M. Wróbel // Condensed Matter Physics. — 2008. — Т. 11, № 2(54). — С. 341-346. — Бібліогр.: 9 назв. — англ. 1607-324X PACS: 05.50.+q, 05.70.Fh, 75.10.Nr, 89.75.-k DOI:10.5488/CMP.11.2.341 https://nasplib.isofts.kiev.ua/handle/123456789/119146 Numerous complex networks contain special patterns, called network motifs. These are specific subgraphs, which occur oftener than in randomized networks of Erd˝os-R´enyi type. We choose one of them, the triangle, and build a family of random hierarchical graphs, being Sierpi ´nski gasket-based graphs with random “decorations”. We calculate the important characteristics of these graphs – average degree, average shortest path length, small-world graph family characteristics. They depend on probability of decorations. We analyze the Ising model on our graphs and describe its critical properties using a renormalization-group technique. Багато комплексних мереж м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 з використанням методу ренорм-групи. en Інститут фізики конденсованих систем НАН України Condensed Matter Physics Modelling complex networks by random hierarchical graphs Моделювання складних мереж з використанням випадкових iєрархiчних графiв Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Modelling complex networks by random hierarchical graphs |
| spellingShingle |
Modelling complex networks by random hierarchical graphs Wróbel, M. |
| title_short |
Modelling complex networks by random hierarchical graphs |
| title_full |
Modelling complex networks by random hierarchical graphs |
| title_fullStr |
Modelling complex networks by random hierarchical graphs |
| title_full_unstemmed |
Modelling complex networks by random hierarchical graphs |
| title_sort |
modelling complex networks by random hierarchical graphs |
| author |
Wróbel, M. |
| author_facet |
Wróbel, M. |
| publishDate |
2008 |
| language |
English |
| container_title |
Condensed Matter Physics |
| publisher |
Інститут фізики конденсованих систем НАН України |
| format |
Article |
| title_alt |
Моделювання складних мереж з використанням випадкових iєрархiчних графiв |
| description |
Numerous complex networks contain special patterns, called network motifs. These are specific subgraphs,
which occur oftener than in randomized networks of Erd˝os-R´enyi type. We choose one of them, the triangle,
and build a family of random hierarchical graphs, being Sierpi ´nski gasket-based graphs with random “decorations”.
We calculate the important characteristics of these graphs – average degree, average shortest path
length, small-world graph family characteristics. They depend on probability of decorations. We analyze the
Ising model on our graphs and describe its critical properties using a renormalization-group technique.
Багато комплексних мереж м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 з використанням методу ренорм-групи.
|
| issn |
1607-324X |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/119146 |
| citation_txt |
Modelling complex networks by random hierarchical graphs / M. Wróbel // Condensed Matter Physics. — 2008. — Т. 11, № 2(54). — С. 341-346. — Бібліогр.: 9 назв. — англ. |
| work_keys_str_mv |
AT wrobelm modellingcomplexnetworksbyrandomhierarchicalgraphs AT wrobelm modelûvannâskladnihmerežzvikoristannâmvipadkovihiêrarhičnihgrafiv |
| first_indexed |
2025-11-26T01:39:30Z |
| last_indexed |
2025-11-26T01:39:30Z |
| _version_ |
1850603168197509120 |
| fulltext |
Condensed Matter Physics 2008, Vol. 11, No 2(54), pp. 341–346
Modelling complex networks by random hierarchical
graphs
M.Wróbel∗
Institute of Mathematics, Maria Curie-Skłodowska University, Lublin, Poland
Received January 31, 2008
Numerous complex networks contain special patterns, called network motifs. These are specific subgraphs,
which occur oftener than in randomized networks of Erdős-Rényi type. We choose one of them, the triangle,
and build a family of random hierarchical graphs, being Sierpiński gasket-based graphs with random “deco-
rations”. We calculate the important characteristics of these graphs – average degree, average shortest path
length, small-world graph family characteristics. They depend on probability of decorations. We analyze the
Ising model on our graphs and describe its critical properties using a renormalization-group technique.
Key words: random graphs, Ising model, complex networks, network motifs
PACS: 05.50.+q, 05.70.Fh, 75.10.Nr, 89.75.-k
1. Introduction
A great number of complex networks that occur in nature have recently been found to contain
characteristic sets of recurring subgraphs called network motifs [1–3]. These are small subgraphs
(typically three- or four-node) that occur far oftener than in the randomized networks of Erdős-
Rényi type. To find these motifs, one compares the subgraph content of the model representing a
real network and the randomized network of Erdős-Rényi type with the same degree distribution.
In [3], the model is built up as a portion of N elements of Z
d with periodic boundary conditions.
A bond between the nodes x and y is placed at random according to a connectivity function F (x, y),
such that max F (x, y) = 1 and of range 1 � Rd � N . The bond between the nodes x and y exists
with probability F (x, y). The authors find the number of appearances of all three- and four-node
non-directed subgraphs in the model and compare them with the number of occurrences of the
corresponding subgraphs in the random network of Erdős-Rényi type having N nodes and the
same degree distribution. It turns out that certain subgraphs (triangles, squares and aggregates of
triangles) occur much oftener than in the Erdős-Rényi network. Those subgraphs are referred to
as network motifs. Of course, different networks may display different network motifs, but a given
motif can be used to characterize a family of networks. Many complex networks have a fractal-type
structure, in which nodes form groups and then join the groups of groups, and so forth, starting
from the lowest levels of organization (individual nodes) up to the level of the entire network [4].
This structure permits to consider useful network properties in a small part and then to expand
them to the whole network.
In this paper, we choose one of the motifs found in [3] – the three-node complete non-directed
graph. We build the family of random hierarchical graphs based on this motif, and analyze the
important network characteristics, such as average degree, average shortest-path length, small
world graph family [5], and the critical behavior of an Ising model.
Our family of graphs {Λk}k∈N is generated in an iterative way. Here k = 1, 2, 3, . . . denotes the
level of the graph understood as a step of the construction. The initial graph (network motif), Λ1,
is the complete graph of order 3. Each step of the construction k > 1 consists of two parts. First,
we join 3 graphs of level k − 1 (called units) in a way shown in figure 1. We obtain a Sierpiński
∗E-mail: mwrobel@hektor.umcs.lublin.pl
c© M.Wróbel 341
M.Wróbel
gasket-based graph, and this is a deterministic core of our model. In the second part of each step,
we decorate the graph at random by adding independent bonds connecting every pair of distinct
external nodes a, b, c with probability p. This procedure yields two types of bonds: the nearest-
neighbor bonds (depicted by solid lines) and the long-range ones (dotted lines). Each graph has 3
a
a
b
c
b
c
a b
c
Figure 1. Construction of the graph Λ3.
external nodes of a special purpose. Units of the same level are attached to them to form the unit
of a higher level. In the figures we denote them by a, b, c. The rest of the nodes are called internal.
2. Network characteristics
Let Vk and Ek denote the sets of nodes and bonds, respectively. The latter set consists of two
separate subsets Ek(nn) and Ek(lr), being the set of the nearest-neighbor and the long-range. It is
easy to see, that
|Vk| =
3
2
(
3k−1 + 1
)
is independent of p. For Ek, we obtain the expected value
〈|Ek|〉 = 3k +
3
2
(
3k−1 − 1
)
p,
where the first term corresponds to the nearest-neighbor bonds Ek(nn), and the second one is due
to the long-range bonds Ek(lr).
Notice, that if p = 0 (nearest-neighbor bonds only), the number of bonds in Λk is 3k. For p = 1,
one gets |Ek| = 3
23k − 3
2 , so decorating does not affect the asymptotics of |Ek|.
2.1. Average degree
Let nk(i) stand for the number of bonds ending at node i ∈ Vk. For each external node i ∈ Vk,
one has 〈nk(i)〉 = 2 + 2(k− 1)p. Maximal degree in Λk is achieved for the internal nodes which are
the external ones in the unit of level k − 1. One finds
max
i∈Λk
〈nk(i)〉 = 4[1 + (k − 2)p] k > 1,
so for p = 1 degree does not exceed 4(k − 1).
In Λk, there exist 3 external nodes of degree 2 + 2(k − 1)p, and 3k−i internal nodes of degree
4 + 4(i − 1)p for i = 1, 2, . . . , k − 1. So the average expected value of degree in Vk is the average
of 〈nk(i)〉 over all i ∈ Vk. This is
〈nk〉 =
3(2 + 2(k − 1)p) +
∑k−1
i=1 [3k−i(4 + 4(i − 1)p)]
3
2 (3k−1 + 1)
= 4 + 2p − 4
1 + p
3k−1 + 1
,
342
Modelling complex networks
which tends to 4 + 2p in the limit k → ∞.
2.2. Average shortest-path length
As the figure 2 suggests, it is convenient to introduce the following notations. The graph
of level k, k > 1, consists of 3 subgraphs of level k − 1
Λk = Λa
k−1 ∪ Λb
k−1 ∪ Λc
k−1.
Every node v ∈ Vk has a label pointing to a place in the graph
v = {α1α2 . . . αk}, αi ∈ {a, b, c}.
a b
c
V
a
4
Figure 2. The graph of level 5.
Each symbol corresponds to the choice
of the triangle of previous level. Notice
that every node, besides the external ones,
has two labels. In the example, the node
v from figure 2 can be labelled by {bacca}
or {bacac}.
The distance ρk(i, γ)between i and
γ ∈ {ak, bk, ck}, measured in terms of the
number of bonds along the path in Λk, is
ρk(i, γ) = (1−δαkγ)+
k−1
∑
j=1
2j−1(1−δαk−jγ).
Let i ∈ Λa
k−1 and j ∈ Λb
k−1. Then the
distance between i and j is
ρk(i, j) 6 ρk−1(i, b) + ρk−1(j, a).
Thus, for p = 0, the average shortest-path
length ρk is
ρk =
∑
i,j∈Vk
ρk(i, j)
1
2 |Vk|(|Vk| − 1)
� 2k.
Notice that we do not include the distance from each node to itself in this average, but some
authors (Newman [5]) do. This difference is negligible from practical point of view.
2.3. Small world graph family
For the last years, small-world networks have been studied intensively, see [5,6]. The family of
graphs {Λk} is a small world graph family if the diameter of Λk (the maximal distance between
the two nodes in Λk) scales logarithmically or slower with the graph size, that is,
∃C > 0 diamΛk 6 C log〈nk〉
|Vk|.
In our model, for p = 0, one has diamΛk = 2k−1. So it is not the case. But for the decorated
graph with p = 1, we obtain diamΛk < k and corresponding constant is
C = (log6 3)−1.
343
M.Wróbel
3. The critical point of the Ising model
The critical behavior of the Ising and Pots models certainly characterizes the network [7–9].
The Ising model for the diamond hierarchical lattice was considered in [7,8]. In [9], authors decorate
this lattice and obtain exact results for the Ising model on it. We follow their example in describing
our model.
The Ising model on our graph Λk is defined by associating spin variables σi = ±1 to the nodes
i ∈ Vk and by the Hamiltonian
−βH = J
∑
〈i,j〉∈Ek(nn)
σiσj + K
∑
〈i,j〉∈Ek(lr)
σiσj + HB
∑
〈i,j〉∈Ek(nn)
(σi + σj) + HN
∑
i∈Vk
σi, (1)
Figure 3. The cluster of level 2.
where J > 0 is the interaction for the nearest-
neighbor bonds and K > 0 is the interaction con-
stant for the long-range bonds. This Hamiltionian
includes two types of magnetic field terms: HB at-
tached to bonds and HN counted with nodes.
We use the renormalization-group transforma-
tion consisting of decimating the three internal
nodes α, β, γ in the cluster shown in the fig-
ure 3. This transformation maps the Hamiltonian
−βH(J,HB,HN,K,G) into a renormalized Hamil-
tonian −βH′(J ′,H ′
B,H ′
N,K ′, G′)
−βH′ =
∑
〈i,j〉∈Ek(nn)
(J ′σiσj + H ′
B(σi + σj) + G′) + H ′
N
∑
i∈Vk
σi + K ′
∑
〈i,j〉∈Ek(lr)
σiσj . (2)
The renormalized parameters are
J ′ =
1
8
ln((R0R3)/(R2R1)) + K,
K ′ = K,
H ′
B =
1
12
ln(R3/R0),
H ′
N = HN ,
G′ =
1
24
ln(R3R0(R2R1)
3) + 4G, (3)
where
R0 = (x−3y3 + 3x−3y−1z−2 + xy−5z−4 + x9y−9z−6)k3g,
R1 = (xy5z2 + xy + 2x−3y + x−3y−3z−2 + 2xy−3z−2 + x5y−7z−2)k−1g, (4)
R2 = (x5y7z4 + 2xy3z2 + x−3y3z2 + 2x−3y + xy−1 + xy−5z−2)k−1g,
R3 = (x9y9z6 + 3xy5z4 + 3x−3yz2 + x−3y−6)k3g
and the useful variables x, y, z, g, k have a form
x = exp(2J), y = exp(2HB), z = exp(HN), g = exp(12G), k = exp(K). (5)
Here G is an additive constant per bond, absent in the Hamiltonian (1), but always generated
by the transformation, and Rj corresponds to the partition function of the external nodes with
j spins equal to 1 and the rest (3 − j) equal to −1.
The subspace HB = HN = 0 is up-down symmetric and closed under the transformation (3),
(4). Within this subspace we calculate the fixed point. Here y = z = 1 and from (4) we obtain the
following system of equations:
{ x3 = (x9 + 3x + 4x−3)k3g,
x−1 = (x5 + 4x + 3x−3)k−1g.
344
Modelling complex networks
Hence the final equation takes the form
s = t
s3 + 3s + 4
s2 + 4s + 3
, (6)
where s = x4 and t = k4.
If t = 1 (the model without long-range bonds), we find only a fixed point s = 1, which is stable
and there are no critical points.
Solving the equation (6) for t > 1 we obtain two solutions
s1 =
3 + t −
√
9 + 22t − 15t2
2(t − 1)
, s2 =
3 + t +
√
9 + 22t − 15t2
2(t − 1)
.
So there are three types of behavior for the renormalization-group flows. For all K lower than
a threshold value Kc and for all p ∈ (0, 1] we can find J such that the critical point exists. So the
flows go to a continuous line of fixed points J(K), K < Kc, with a distinct fixed point for each
starting interaction K. When K = Kc there is one stable fixed point Jc(Kc) = 1
8 ln 3, and there
are no phase transitions. For K > Kc we can find sufficient small p, for which there exists J(K)
such that the critical point exists..
It is easy to see, that
Kc =
1
4
ln
9
5
. (7)
References
1. Milo R., Shen-Orr S., Itzkovitz S., Kashtan N., Chklovskii D., Alon U., Science, 2002, 298, 824–827.
2. Kashtan N., Itzkovitz S., Milo R., Alon U., Phys. Rev. E, 2004, 70, 031909.
3. Itzkovitz S., Alon U., Phys. Rev. E, 2005, 71, 026117.
4. Clauset A., Moore C., Newman M. Structural Inference of Hierarchies in Networks, In: Proceedings of
the 23rd International Conference on Machine Learning, Workshop on “Statistical Network Analysis”,
Springer Lecture Notes in Computer Science (Pittsburgh, June 2006), also arXiv:physics/0610051v1
[physics.soc-ph] 9 Oct 2006.
5. Newman M.E.J., SIAM Review, 2003, 45, 167 – 256.
6. Barrat A., Weigh M., Eur. Phys. J. B, 2000, 13, 547–560.
7. Griffiths R.B., Kaufman M., Phys. Rev. B, 1982, 26, 5022–5032.
8. Bleher P.M., Žalys E., Commun. Math. Phys., 1989, 120, 409–436.
9. Hinczewski M., A. Nihat Berker, Phys. Rev. E, 2006, 73, 066126.
345
M.Wróbel
Моделювання складних мереж з використанням випадкових
iєрархiчних графiв
М.Врубель
Iнститут математики, Унiверситет Марiї Кюрi-Склодовської Люблiн, Польща
Отримано 31 сiчня 2008 р.
Багато комплексних мереж м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 мережi, мережевi мотиви
PACS: 05.50.+q, 05.70.Fh, 75.10.Nr, 89.75.-k
346
|