1

On the Capacity of Wireless Networks with Fractal
and Hierarchical Social Communications

arXiv:1708.04585v1 [cs.IT] 11 Aug 2017

Ying Chen, Rongpeng Li, Zhifeng Zhao, and Honggang Zhang

Abstract—The capacity of a wireless network with fractal
and hierarchical social communications is studied in this paper.
Specifically, we mathematically formulate the self-similarity of a
fractal wireless network by a power-law degree distribution P (k),
and we capture the direct social connection feature between two
nodes with degree k1 and k2 by a joint probability distribution
P (k1 , k2 ). Firstly, for a fractal wireless network with direct
social communications,
it is proved that the maximum capacity

is Θ √n 1log n with n denotes the total number of nodes in the
network, if the source node communicates with
 one of its direct
contacts randomly, and it can reach up to Θ log1 n if the two
nodes with distance d communicate according to the probability
in proportion to d−β . Secondly, since humans might get in touch
with others without direct connection but through the interconneced users, the fractal wireless networks with hierarchical
social communications is studied as well, and the related capacity
is derived based on the results in the case with direct social
communications. Our results show that this capacity is mainly
affected by the correlation exponent  of the fractal networks.
The capacity is reduced in proportional to log1 n if 2 <  < 3,
while the reduction coefficient is n1 if  = 3.
Index Terms—Capacity, Fractal Networks, Hierarchical Social
Communications, Self-Similarity, Complex Networks

I. I NTRODUCTION
The research on the capacity of a wireless network has continuously aroused intense interests in recent years. However,
except the recent works in [1], [2], little attention has ever
been paid to fractal wireless networks. As a vital property of
networks, fractal phenomenon has been discovered in many
wireless networking scenarios [3]. For example, the coverage
boundary of the wireless cellular networks shows a fractal
shape, and the fractal features can inspire the design of the
handoff scheme in mobile terminals [4], [5]. Moreover, a large
number of significant networks in the real world exhibit the
fractal characteristics naturally, such as the world-wide web,
yeast interaction, protein homology, and social networks[6],
[7].
Basically, different from some well-known fractal structures
with specific geometric shapes as studied in [8], [9], the fractal
wireless networks in this paper are the ones with general
fractal characteristics. The general fractal features have been
well studied [10], [11], [12] and are determined by the degree
Y. Chen, R. Li, Z. Zhao, and H. Zhang are with College of Information Science and Electronic Engineering, Zhejiang University. Email:
{21631088chen ying, lirongpeng, zhaozf, honggangzhang}@zju.edu.cn
This paper is financially supported by the Program for Zhejiang Leading
Team of Science and Technology Innovation (No. 2013TD20), the Zhejiang
Provincial Technology Plan of China (No. 2015C01075), and the National
Postdoctoral Program for Innovative Talents of China (No. BX201600133).

correlations in the connectivity of the networks, which could
be characterized by some particular models or distributions
like[13], [14], [15].
The most vital essence of the general fractal network studied
in this paper is discribed by the joint probability distribution P (k1 , k2 ), which gauges the possibility to establish a
connection between two nodes with degree k1 and k2 . As
the fundamental requirement for forming the general fractal
wireless networks [13], P (k1 , k2 ) can be expressed as:
−(γ−1)

P (k1 , k2 ) ∝ k1

· k2− , (k1 > k2 )

where γ is the degree distribution exponent,  is the correlation
exponent, and the operator ∝ denotes the proportional relationship between the two sides. This form of expression indicates
that k1 and k2 are independent of each other. Moreover, a
reasonable explanation for the condition k1 > k2 is that nodes
with larger degrees have a higher priority in contacts selection,
so they tend to choose nodes with smaller degrees and set up
connections with them.
Another important characteristic of a general fractal wireless
network is known as self-similarity. It has been found that
a variety of real complex networks consist of self-repeating
patterns on all length scales [7]. Self-similarity of fractal
wireless networks requires the node degree distribution P (k)
to remain invariant when the network grows, namely the socalled scale-free law. In order to meet this requirement, powerlaw degree distribution P (k) ∝ k −γ must be followed in a
general fractal wireless network [16], [17], [18], [19]. Actually,
the two power-law distributions above lay the foundation for
the capacity analysis of fractal wireless networks.
A. Related Work
Owing to its great significance, there have existed a great
deal of revalent researches on the capacities of various kind
of wireless networks. Gupta and Kumar proved that
 the
1
√
when
throughput in wireless networks can reach Θ
n log n
the network size (i.e., the total number of nodes) is n [20],
where the symbol Θ refers to the order of magnitude, while
T (n) = Θ(h(n)) means that the two functions T (n) and h(n)
have the same rate of growth. Matthias Grossglauser et al.
claimed that the capacity in ad hoc wireless networks can
increase dramatically when nodes are mobile rather than fixed
[21]. The capacity of wireless networks under the relay case
was studied in [22] and the research on the capacity of hybrid
wireless networks was conducted in [23]. Kulkarni et al. provided a very elementary deterministic approach on the capacity
of wireless networks, which can give throughput achievability

2

results in terms of the node locations [24]. Mingyue Ji et al.
derived the capacity of wireless ad hoc networks when the traffic is heterogeneous but the node distribution is homogeneous
[25]. For social-oriented wireless networks, Sadjadpour et al.
studied the capacity of a scale-free wireless network in which
nodes communicate with each other in the context of social
groups [26]. Particularly, it was discovered that the maximum
capacity can be improved in the classical scale-free networks
compared with the conclusion drawn by Gupta and Kumar
[27], [28]. In addition, they studied the capacity of composite
networks, that is, the combination of social and wireless ad hoc
networks [29]. Bita Azimdoost et al. investigated the capacity
and latency in an information-centric network when the data
cached in each node has a limited lifetime [30].
However, to our best knowledge, there have been no
theoretical researches on the capacity of wireless networks
with fractal and hierarchical social communications, which is
exactly what we study in this paper.
B. Contribution
Distinct from the previous works, we intend to address the
capacity of wireless networks with fractal and hierarchical
social interconnections. In this regard, we provide some key
novel contributions as following:
• First of all, we elaborate on the capacity of fractal wireless networks with ditect social communications. On one
hand, it is proved that if the source node communicates
with one of its
randomly, the maximum

 direct contacts
1
√
. On the other hand, if the two
capacity is Θ
n log n
nodes with distance d communicate according to the
−β
probability in proportion

to d , the maximum capacity
1
can reach up to Θ log n .
• Secondly, we reveal the relashionship between the extendibility of a fractal wireless network and the correlation exponent , which is the key parameter of a
fractal network and influences the topology structure
of it greatly. We mathematically prove that =3 is the
boundary to distinguish whether the fractal network is
extendable or not. When the correlation exponent is
within the range  ∈ (2, 3), the fractal network can
expand branches continuously while the fractal network
will stop branching rapidly if  > 3.
• Thirdly, we derive the capacity of wireless networks with
fractal and hierarchical social communications. Compared to the results with direct social communications, it
turns out that: 1) If 2 <  < 3, the order of the capacity
decreases in proportion to log1 n ; 2) If  = 3, then the
capacity reduces in proportion to n1 .
The remainder of the paper is organized as follows. We
introduce the foundations of a fractal wireless network as
well as the basic knowledges of hierarchical social communications, and discuss the network model in Section II. Then
the maximum throughput with direct social communications
is derived in Section III. Afterwards, the results are expanded
to the case with hierarchical social communications in Section
IV. Simulation results are discussed in Section V. Finally, we
draw a conclusion in Section VI.

II. BACKGROUND AND M ODELS
A. Foundations of A Fractal Network
In order to characterize the general fractal wireless networks, it is essential to introduce the concept of renormalization through the box-covering algorithm [7], [14], [15]. Renormalization is a technique to examine the internal relationship
within a complex network by using a box to cover several
nodes and virtually replacing the whole box by a new node.
Besides, if there exists a link between two nodes in two boxes
respectively, then the two corresponding nodes evolved from
the boxes will be connected.
Mathematically, the network could be minimally covered by
NB (lB ) boxes of the same length scale lB under renormalization, where lB is the size of the box measured by the maximum
path length between any pair of nodes inside the box, and
NB (lB ) is the minimum value among all possible situations. In
essential, if the network is a general fractal wireless network,
we have the following relations, namely [14], [31]:

−dB

 NB (lB )/n ∼ lB
kB (lB )/khub ∼ lB −dg


nh (lB )/kB (lB ) ∼ lB −de ,
where n is the number of nodes in the network. A hub
indicates the node with the largest degree inside each box,
while kB (lB ) and khub denote the degree of the box and the
hub respectively. nh (lB ) refers to the number of links between
the hub of a box and nodes in other connected boxes. The three
indexes dg , dB and de denote the degree exponent, the fractal
exponent, and the anti-correlation exponent, respectively.
Viewing the process of renormalization from the perspective
of time steps, the number of boxes NB (lB ) in this time step
is also the number of nodes in the next time step, and the
first equation indicates that the ratio of the numbers of nodes
between successive time steps is proportional to lB −dB , and
the power-law relationship remains unchanged under renormalization, obeying the scale-free law. In the similar way, the
degree of the box kB (lB ) at present is the degree of the hub
khub in the next time step as well, and the second equation
shows that the ratio of the hub degrees between successive
time steps is a scale-invariantly exponential function of the
box size lB . Therefore, what the first and second equations
reveal is actually the topological self-similarity of fractal
wireless networks [14]. In addition, the degree exponent dg
and the fractal exponent dB are both finite for fractal wireless
networks.
Besides, the ratio nh (lB )/kB (lB ) in the third equation
reveals the contribution of hub nodes in box-box connections,
and it decreases sharply with the increasement of the length
scale lB . Actually, this equation illustrates the hub repulsion
phenomenon, i.e. a node with a large degree prefers not to be
linked to another node with a large degree, which is another
essential property of fractal wireless networks. Therefore,
the anti-correlation exponent de reveals the repulsion effect
between the hubs while large de tends to result in a fractal
wireless network.
In [13], it has been proved that there exist certain relations
among the aforementioned key parameters: γ = 1 + ddBg and

3

 = 2 + ddge , which suggest that γ and  in a fractal wireless
network are larger than 1 and 2, respectively. And the degree
distribution exponent is uaually in the range 2 < γ < 3 in real
complex networks [7]. Please note that for concision, all the
following relevant deductions will be characterized by the key
parameters γ and , instead of dB , dg and de .

v(j12) v ( 2 )
j3

v (j12)

vi v

(1)
j1

v (j32)
v (j31)
v(j22)

vi : Source Node
v (j1) : Level  1 Contact Node
v (j2 ) : Level  2 Contact Node
v (j3) : Level  3 Contact Node

B. Knowledges of Hierarchical Social Communications
Fig.1 illustrates the representative topology of a general
fractal wireless network with mutually social communications,
in which we assume that a node vi is going to transmit a data
packet to another node. In other words, the node vi is the
source node. In the situation of direct social communications,
the nodes vj1 and vj2 are directly connected with the node vi
and are regarded as the direct, or level-1 contacts of vi . Then
vk is chosen among the direct contacts (say vk = vj2 ) to
communicate with vi and it is known as the destination node.
Usually, a node has many direct contacts, and the degree k of
one node refers to the number of its level-1 contacts. In the
case of level-1 social communications, the degree distribution
and the joint probability distribution are aforementioned P (k)
and P (k1 , k2 ), respectively.

is known as P (k (3) ), where the degree k (3) of a node is the
level-3 degree, and so forth.

...
(a) level -1

(b) level - 2

(c) level - 3

Fig. 3. The level-L graphs formed by connecting all level-L contact pairs
directly.

vi
v j1

Fig. 2. The illustration of hierarchical social communications in a general
fractal wireless network.

( vk ) v j 2

vi : Source Node
vk : Destination Node
v j : Level - 1 Contact Node

Fig. 1. The illustration of level-1 social communications in a general fractal
wireless network.

As depicted in Fig. 2, in addition to the direct or so-called
level-1 social communications, the social communications
through fractal wireless networks can actually be hierarchical,
where the source node communicates with one of its levelL (L = 1, 2, · · ·, Lmax ) contacts, and Lmax refers to the
maximum social relationship level. Without loss of generality,
we use the superscript m to denote a level-m contact of the
source node. In the case of level-2 social communications,
(2)
(2)
the green nodes such as vj1 and vj2 are connected with the
source node vi through one internode, and they are defined as
the level-2 contacts of the source node. Then the destination
node vk is selected among the level-2 contacts to communicate
(3)
(3)
with vi . Similarly, the yellow nodes such as vj1 and vj2 are
referred to as the level-3 contacts of the source node, and so
on.
If all level-2 contact pairs in Fig.3(a) are connected with one
link directly, then we get a new graph as shown in Fig.3(b). In
this level-2 graph, the degree distribution is known as P (k (2) ),
where the degree k (2) of a node stands for the level-2 degree,
and refers to the number of its level-2 contacts or its links
in the level-2 graph. In the same way, we can also obtain
the level-3 graph as dipicted in Fig. 3(c) by connecting all
level-3 contact pairs directly, and the degree distribution here

C. Network Model
In order to clarify the capacity of the above wireless network
with fractal and hierarchical social communications clearly
and orderly, we assume that the fractal network is deployed in
a unit area square and the n nodes are uniformly distributed. It
is noteworthy that the topological fractal network is formed by
the social connections of nodes following the aforementioned
degree distributions P (k) and P (k1 , k2 ), which is not contradictory with the assumption of uniformly distributed nodes.
The case of level-1 social communications is described in
Fig. 4(a), and the symbols in the model are listed in Fig. 4(b).
Without losing generality, we assume that the source node
locates in the central square of this standard unit area square
model. The destination node vk is chosen among the four
level-1 contacts (nodes vj ). In level-L (L = 2, 3, ..., Lmax )
situations, the model is almost the same except that the destination node is re-selected according to the level-L contacts.
All the squares marked in red have the same hops x from the
source node as the destination node vk , and the total number of
them is 4x. The radius R1 and R2 of the two dotted-line circles
are used as the distances between the source and destination
node instead of their real distance.
Corresponding to the unit area square scenario, the widely
employed protocol model in [32] is adopted as the measurement of a successful transmission. A transmission is successful
if and only if the Euclidean distance between two nodes
|Xi − Xj | 6 r(n) and |Xk − Xi | ≥ (1 + ∆)|Xi − Xj |.
Xi and Xj refer to the transmitter node and the receiver
node respectively. Xk denotes any other transmitter sharing

4

T squares
★

★

★

★

vj4
★

★

r (n )
★

★

★

S

vi

★

R1

★

★

vj2(vk )
★

★

C1r (n)

vj3

R2
★

vj1★

(a )
Meanings

Symbols

vi: Source node.

vj : Contact node.
vk : Destination

node.

Routing path.
Nodes in these squares have the same hops
from the source node to the destination node.

★

Cells that can transmit simultaneously.

r (n )

Transmission range.

R1 , R2

Substitute for the real distance between the
source and destination node.

C1r (n)

Side length of the squares.

T

Number of squares between cells that can
transmit simultaneously.

(b )

going until the data packet eventually reaches the destination
node after multiple hops. The red line with arrows denotes
one possible routing path in Fig. 4(a). The data packet can be
successfully transported for any pair of transmission under the
condition that there is at least one node in each square. Surely
this condition can be guaranteed in a probability approaching
1 according to [24].
Since the selection of the destination node affects the
capacity of the above fractal wireless network as well, the
destination node is chosen in two different ways in this paper.
In the first case, the destination node is selected according
to the uniform distribution 1q . That is to say, the source node
communicates with one of its contacts randomly, and all the
potential contacts have the same opportunities to communicate
with the source node. In the second case, the destination
node is selected according to the power-law distribution d−β
[34], where d refers to the distance between the source node
and the destination node, and β is the frequency parameter.
This selection rule is considered to be reasonable as Latane
et al. [34] discovered that the source node communicates
with different nodes with different preferences within a social
group, and the probability is proportional to the power-law of
the distance. In other words, the contacts closer to the source
node have more opportunities to communicate with it.
For simplicity of representation, we give some definitions
and highlight the relationship between them.
Definition 1. The elementary symmetric polynomial [35]
σp,N (Q0 ), 1 ≤ q ≤ N of variables Q0 = (q1 , q2 , ..., qN ) is
noted as
σp,N (Q0 ) = σp,N (q1 , q2 , ..., qN )
X
=
qi1 qi2 ...qip .
1≤i1 ≤i2 ≤...≤ip ≤N

Fig. 4. (a) The fractal network deployed in a standard unit area square model;
(b) The table of the symbols in the model.

the same channel with Xi and ∆ is the guard zone factor.
It is proved
 that the transmission range r(n) must reach
q
log n
Θ
to guarantee the connectivity of the network
n
[33]. In Fig. 4(a), the solid-line circle with the radius of r(n)
displays the transmission range.
For keeping consistence in analyzing the capacity, similarly
with [20], [24], a TDMA (Time Division Multiple Access)
scheme is designated as the MAI (multiple access interference)
avoidance method. As shown in Fig. 4(a), the network is
divided into a number of smaller squares with side length
C1 r(n). The interference units refer to those cells containing
at least two nodes closer than (2 + ∆)r(n) respectively [20],
and these cells which can simultaneously transmit data packets
should not be the interference units with each other. Therefore,
the squares signed with blue stars in Fig. 4(a), whose distances
are at least T squares away from each other, are permitted to
transmit data packets at the same time, where T ≥ (2+∆)/C1 .
A simple routing scheme in the space domain is adopted
here. When the source node is about to send a data packet,
it chooses one node closest to the destination node from its
neighbor squares to relay the packet. The relaying steps keep

Definition 2. The elementary symmetric polynomial [35]
0
0
k
σp,N
−1 (Q ), 1 ≤ p ≤ N −1 of variables Q = (q1 , q2 , . . . , qN )
except qk is noted as
k
0
σp,N
−1 (Q ) = σp,N −1 (q1 , q2 , ..., qk−1 , qk+1 , ..., qN ).

Lemma 1. Let the set Q0 = {q1 , q2 , ..., qN } contains N ≥
2 non-negative real numbers. If q is finite, then we have
σ1,N (Q0 ) · σq,N (Q0 )
N
= Θ(
).
0
(q + 1) · σq+1,N (Q )
N −q
Proof : The poof can be found in [28].
III. T HE U PPER B OUND OF THE C APACITY W ITH D IRECT
S OCIAL C OMMUNICATIONS
In this section, we will follow the aforementioned properties
of fractal wireless networks and try to clarify the specific
derivation procedure of the maximum capacity with direct
social communications. That is to say, we only take into
consideration the level-1 social communications in this section, and all the contacts, degrees, degree distribution or joint
probability distribution mentioned in this section are default
level-1. In addition, we also study the impact of a particular destination selection rule on the maximum achievable
throughput by taking account of two different cases, including
uniformly and power-law distributed destinations.

5

For the convenience for understanding, we make a list of all
the symbols and their explanations in this section, as shown
in Table I.
TABLE I
T HE LIST OF THE SYMBOLS AND THEIR MEANINGS IN S ECTION III.
Symbols
n
k
q
q0
N
γ

Mγ,
C
vi
vt
vk
qk
λ
λmax
X
E[X]
E1
E2
sl
d
β
E3
E4

Meanings
The total number of nodes.
The degree of a node.
The degree of the source node.
A relative large degree to divide the range
of degrees into two parts.
The number of potential contacts whose
degrees are less than q.
The degree distribution exponent of
a fractal network.
The correlation exponent of
a fractal network.
The normalization constant in the joint
probability distribution P (k1 , k2 ).
The set of all contacts.
The source node.
The destination node.
A particular node which is selected as
the destination node.
The degree of vk .
The data rate for every node.
The maximum achievable capacity.
The number of hops from the the source
node to the destination node.
The average number of hops.
The average number of hops when q ≤ q0
under the case of uniformly
distributed destinations.
The average number of hops when q > q0
under the case of uniformly
distributed destinations.
The red squares in Fig. 4(a), where
l = 1, 2, . . . 4x.
The distance between the source node to
the destination node.
The frequency parameter.
The average number of hops when q ≤ q0
under the case of power-law
distributed destinations.
The average number of hops when q > q0
under the case of power-law
distributed destinations.

λmax of the wireless network with fractal and direct social
communications is


1
λmax = Θ √
.
n · log n
In order to get the result in Theorem 1, we first present
the relationship between the capacity and the average number
of hops E[X], so we can solve the problem by finding out
E[X]. Secondly, we give the expression of E[X]. Thirdly,
We divide E[X] into two separate cases E1 and E2 with a
boundary q0 , which indicates a relatively large degree. E1 is
the average number of hops when q ≤ q0 , where the degree
q of the source node is a finite integer, meanwhile E2 is the
average number of hops when q > q0 , where q is considered
to be infinite. After E1 and E2 are obtained respectively, the
capacity derivation is achieved by backtracking. Next, we will
follow the proof sketch above. Watch out for the proof details
which may seem similar as [28], but actually totally different
since what we focus on is the capacity in fractal networks.
Lemma 2. Assume that λ is the data rate for every node
and λmax is the maximum achievable capacity, X is the
number of hops from the the source node to the destination
node. E[X] denotes the expectation of X for any transmission
between a pair of source and destination nodes. W is the
bandwidth assigned to the whole network. Then we have


1
.
(1)
λ 6 λmax = Θ
log n · E[X]
The proof is left in the appendix.
Lemma 3. Let the source node vi locate in the central
square whose degree is q, where q = 1, 2, ..., n. vk denotes the destination node whose degree is qk . The variables
−
q1 , q2 , ..., qN in Q = (q1− , q2− , ..., qN
) denote the degrees of
N potential level-1 contacts whose degrees are smaller than
q. Then the average number of hops can be given as
1

r(n)
4x X
k
X
X
qk− · σq−1,N
q −γ
−1 (Q)
Pn
x
.
E[X] =
·
−γ
q · σq,N (Q)
b=1 b
x=1 l=1 vk ∈sl
q=1
(2)
Proof : Let P (k = q) denote the probability when the degree
of the source node is q, while E[X|source vi , k = q] is the
average number of hops under the condition that the source
node vi has q level-1 contacts, then E[X] can be written as

n
X

A. The Case of Uniformly Distributed Destinations
In the first case, we take the uniform distribution of the
destination nodes into consideration. In other words, we assume that the source node selects one of its level-1 contacts
as the destination node randomly. In this situation, we give
the result of the maximum capacity in Theorem 1 and proof
it subsequently.
Theorem 1. For a fractal wireless network with n nodes
satisfying the conditions below: 1) the level-1 contacts
are selected according to the joint probability distribution
−(γ−1) −
k
k
P (k1 , k2 ) = 1 Mγ, 2 ; 2) the level-1 degree of each node

E[X] =

n
X

P (k = q) · E[X|source vi , k = q].

Let P (X = x) denote the probability of x hops ranging
from 1 to 1/r(n). The event X = x is true if and only if vk
locates in the red squares sl (l = 1, 2, . . . 4x) and it is selected
as the destination node vt . Therefore, E[X|source vi , k = q]
can be expanded as
1

E[X|source vi , k = q] =

r(n)
X

x·P (X = x)

x=1

−γ

follows the power-law degree distribution P (k) = Pnk k−γ ;
k=1
3) the destination node vt is chosen by the uniform distribution
P (vt = vk |vk ∈ C) = 1q . Then the maximum capacity

(3)

q=1

1

=

r(n)
X

x=1

x·

(4)
4x X
X
l=1 vk ∈sl

P (vt = vk ).

6

vt = vk implies that vk is chosen as the destination node
vt after it is selected as a level-1 contact. In other words,
P (vt = vk ) = P (vk ∈ C) · P (vt = vk |vk ∈ C).

(5)

Moreover, the probability that vk is selected as a level-1
contact can be written as below and the proof in detail is in
the appendix:
P
qk− ·
qi−
qi−
· · · qi−
1
2
q−1
1≤i1 ≤···≤iq−1 ≤N
P
qi−
qi−
1
2
1≤i1 ≤···≤iq ≤N

P (vk ∈ C) =

where the symbol ≡ indicates the same order of magnitude
on the two sides of an equation.
All the n nodes are distributed uniformly in the unit area,
and the side length of each square is C1 r(n), so the summation
term in Eq. (12) can be solved as
1

1

r(n)
r(n)
4x X
X
X
X
x
x · 4x · C12 r2 (n) · n · 1
1≡

x=1

l=1 vk ∈sl

1

· · · qi−
q

2

≡ n · r(n)

(6)

k
q − · σq−1,N
−1 (Q)
= k
.
σq,N (Q)

Proof : According to the meaning of E1 , it should be given
1

r(n)
4x X
k
X
X
qk− · σq−1,N
q −γ
−1 (Q)
Pn
E1 =
x
.
·
−γ
q · σq,N (Q)
b=1 b
q=1
x=1 l=1 vk ∈sl
(8)
All situations of selecting q −1 nodes from C can be parted
into two categories according to the condition whether vk is
chosen. If it is chosen, we have to select the other q − 2 nodes
from C except vk . Otherwise we select q − 1 nodes in C
except vk , that is to say,

qk−

k
σq−2,N
−1 (Q)

= σq−1,N (Q) −
·


−
k
= σq−1,N (Q) − qk σq−2,N (Q) − qk− · σq−3,N
(Q)
.
−1
Since every term in the equation above is positive, then we
have
σq−1,N (Q) − qk− · σq−2,N (Q)

<

k
σq−1,N
−1 (Q)

< σq−1,N (Q).
(9)
A transformation of the Lemma 1 suggests that
σ1,N (Q) · σq−1,N (Q)
N
= Θ(
) = Θ(1).
q · σq,N (Q)
N −q+1

(10)

Moreover, the probability that the degree of the source node
is not greater than q0 is
P (q ≤ q0 ) =

q0
X
q=1

q −γ
Pn
= Θ(1).
−γ
b=1 b

(11)

Therefore, we get the upper bound of E1 according to Eq.
(8) - Eq. (11).
1

r(n)
4x X
X
X
qk− · σq−1,N (Q)
E1 <
x
q · σq,N (Q)
v ∈s
1

l=1

≡

k

qk−
q · σ1,N (Q)

l

1
r(n)

4x X
X X
x
1,
1

(13)
x2

≡ Θ n · r(n)

as

k
σq−1,N
−1 (Q)

r(n)
X

x=1

−1



Then we have the complete expression of Eq. (2) after
expanding Eq. (3) with Eq. (4) - Eq. (6).

Lemma 4. When the degree of the source node is not
greater than q0 , i.e. q ≤ q0 , the average number of hops E1 is


−1
E1 = Θ r(n)
.
(7)

q0
X

x=1

l=1 vk ∈sl

(12)

.

The qk− term in Eq. (12) can be replaced with its mean in
the upper bound for convenience,
Pq−1 −(γ+)
q−1
X
b=1 b
≡ Θ(1).
E[qk− ] =
P (k = b) · b− = P
n
−γ
b=1 b
b=1
(14)
On the other hand,
Z q−1
N
X
u−γ
qj− ≡ N ·
σ1,N (Q) =
u− Pn
du ≡ Θ(n).
−γ
1
b=1 b
j=1
(15)
By combining Eq. (13) - Eq. (15) together, we have the
upper bound of E1 , that is


−1
E1 = O r(n)
.
(16)
Similarly, the lower bound of E1 is
1

r(n)
4x X
X
X
qk− · σq−1,N (Q) − qk−2 · σq−2,N (Q)
x
E1 >
q · σq,N (Q)
v ∈s
1

l=1

k

l

1

r(n)
4x X
X
X
qk−2 · σq−2,N (Q)
= upper bound−
x
.
q · σq,N (Q)
v ∈s
1

l=1

k

l

It turns out that the second term in the lower bound is
1

r(n)
4x X


X
X
qk−2 · σq−2,N (Q)
−1
x
≡ Θ n−1 · r(n)
.
q · σq,N (Q)
x=1 l=1 vk ∈sl
(17)
The order in Eq. (17) is negligible compared with Eq. (16),
so the order of E1 is solved.

Lemma 5. When the degree of the source node is greater
than q0 , i.e. q > q0 , the average number of hops E2 is


−1
E2 = Θ r(n)
.
(18)

The proof on Lemma 5 can be found in the appendix.
Now we can prove Theorem 1.
Proof : Based on the results in Lemma 4 and Lemma 5,


−1
E[X] = E1 + E2 = Θ r(n)
.
(19)
Together with Lemma 2, we can obtain the results in
Theorem 1.


7

B. The Case of Power-law Distributed Destinations
In the second case, we assume that the probability that the
source node communicates with one of its level-1 contacts is
proportional to d−β , where d refers to the distance between
two nodes and β indicates that the closer contacts have more
opportunities to communicate with the source node. Fractal
wireless networks achieve another maximum throughput in
this situation, which is clarified in Theorem 2 and proofed
in the remainder of the subsection.
Theorem 2. For a fractal wireless network with n nodes
satisfying the conditions below: 1) the level-1 contacts
are selected according to the joint probability distribution
−(γ−1) −
k
k
P (k1 , k2 ) = 1 Mγ, 2 ; 2) the level-1 degree of each node
−γ

follows the power-law degree distribution P (k) = Pnk k−γ ;
k=1
3) the destination node vt is chosen by the power-law distri−β
bution P (vt = vk |vk ∈ C) = Pqd d−β . Then the maximum
j=1

j

capacity λmax of the wireless network with fractal and direct
social communications is



1


Θ √
,
0 ≤ β ≤ 2;



n · log n


!


1
λmax =
Θ p
,
2 < β ≤ 3;
3−β

n
· log nβ−1







1


,
β > 3.
 Θ
log n
The proof of Theorem 2 is pretty similar to Theorem 1, so
we just give some key lemmas in the derivation procedure but
skip the lines to prove them.
Lemma 6. Let the source node vi locate in the central
square whose degree is q, where q = 1, 2, . . . , n. vk denotes
the destination node whose degree is qk and its distance
from the source node is dk . The variables q1 , q2 , · · ·, qN in
−
Q = (q1− , q2− , · · ·, qN
) denote the degrees of N potential
level − 1 contacts whose degrees are smaller than q. Let
−β
−β
D = (d−β
1 , d2 , ···dq ), and dj (1 ≤ j ≤ q) in D denotes the
distance between the jth contact and the source node. Then
the average number of hops can be given as

Combined with Lemma 2, we can obtain the result in
Theorem 2.
IV. T HE U PPER B OUND OF THE C APACITY W ITH
H IERARCHICAL S OCIAL C OMMUNICATIONS
In the last section, we only take into account the direct
social communications. However, as we mention before, the
social communications can actually be hierarchical among the
interconnected users. In other words, the source node can
communicate with one of its level-L (L = 1, 2, ..., Lmax )
contacts through the internodes with different levels of social interconnections. In this section, we firstly describe the
relationship between the extendibility of a fractal network
and the correlation exponent , which is stated in Theorem
3. Then we expand the results achieved in the last section
to the maximum throughput capacity with hierarchical social
communications. The conclusion is clarified in Theorem 4 and
proved afterwards.
Theorem 3. For a fractal wireless network with n nodes
satisfying the conditions below: 1) the level-1 contacts
are selected according to the joint probability distribution
−(γ−1) −
k
k
P (k1 , k2 ) = 1 Mγ, 2 ; 2) the level-1 degree of each node
−γ

follows the power-law degree distribution P (k) = Pnk k−γ .
k=1
Then the relationship between the extendibility of the fractal
network and the correlation exponent  is:
1) If 2 <  < 3, the fractal network can expand its branches
continuously, and the average level-L (L = 1, 2, ..., Lmax )
degree increases monotonously via expanding.
2)  = 3 is the boundary to distinguish whether the fractal
network is extendable or not. In this case, the mean of level-L
degree keeps invariant throughout.
3) If  > 3, the fractal network will stop branching rapidly
after expanding finite levels. In other words, the expectation
of level-L degree decreases monotonously.
Before giving the proof, we first take a brief look at the
definition of moment generating function and its properties.
Definition 3. For a discrete random variable X, its moment generating function is defined as:

E[X] =
n
X

1
r(n)

X
q −γ
Pn
·
x
−γ
b=1 b
x=1

4x
X

X

qk−

·

k
σq−1,N
−1 (Q)

·

d−β
k

φX (t) = E[etX ] =

∞
X

etx · P (X = x).

x=0
.
σ1,q (D)
In addition, it’s easy to obtain some useful properties of
(20)
moment generating function:
Lemma 7. When the degree of the source node is not
∞
P
Property 1 : φX (0) =
P (X = x) = 1.
greater than q0 , i.e. q ≤ q0 , the average number of hops E3 is
x=0



0
−1
Property 2 : φX (0) = E[X].

Θ r(n)
,
0 ≤ β ≤ 2;



Proof
:


β−3


E3 =
(21)
Θ r(n)
,
2 < β ≤ 3;


d
d tX 

0
tX

φ
(t)
=
E[e
]
=
E
e
= E[X · etX ].

X
dt
dt
Θ(1),
β > 3.
q=1

l=1 vk ∈sl

σq,N (Q)

Lemma 8. When the degree of the source node is greater
than q0 , i.e. q > q0 , the average number of hops E4 is



−1

Θ
r(n)
,
0 ≤ β ≤ 2;





β−3
E4 =
(22)
Θ r(n)
,
2 < β ≤ 3;




Θ(1),
β > 3.


Property 3 : For the discrete random variables X, Y and
Z, if Z = X + Y , and X and Y are independent of each
other, then φZ (t) = φX (t) · φY (t).
Proof :
φZ (t) = E[etZ ] = E[et(X+Y ) ] = E[etX ] · E[etY ].

8


Now, we could prove Theorem 3.
Proof : In the first place, we define some symbols here:
n
n
P
P
Mγ =
k −γ and M =
k − are two normalization
k=1
(L)

M =

n
X

k −γ =

k=1
n
X

k − =

k=1

K

(1)

1
k 1−γ 1
|n ≈
,
γ−1
γ−1
1−

1
k
|1 ≈
,
−1 n
−1

= E[K (1) ] =

n
X

k·P (K (1) = k)

k=1

=

E[K 0(2) ] = φ0K 0(2) (t)|t=0
n
X
k−1
=
k · P (K (1) = k) · [φD (t)]
· φ0D (t)|t=0

k=1

factors; K
denotes the average degree of level-L (L =
1, 2, ...Lmax ); each link has two end nodes, and D stands for
the degree of one end node when that of another end node
of the link is known. When the degree of vi is known, for
(1)
example, the degree distribution of vj1 follows the power−
law P (D = k) = kM , k = 1, 2, ...n according to P (k1 , k2 );
D is the expectation of D.
Hereinafter what we focus on is the order of throughput
capacity, then n approaches to positive infinite, and since γ and
 are greater than 2, so some of their values can be calculated
as:
Mγ =

Now calculate the expectation of K 0(2) by the Property 1
and 2 of moment generating function:

n
X

k·

k=1

k −γ
1
k 2−γ 1
=
·
|
Mγ
Mγ γ − 2 n

γ−1
,
γ−2
n
n
X
X
k −  − 1
k·
k · P (D = k) =
.
D = E[D] =
≈
M  − 2

=

k=1

As depicted in Fig. 2, assume that we have known the level1 degree of vi is K (1) , and we intend to solve the average
level-2 degree of vi . Its level-2 degree K (2) can be expressed
as:
K (2) = (D1 − 1) + (D2 − 1) + ... + (DK (1) − 1),
where D1 , D2 , ..., DK (1) are independently and identically
−
power-law distributed as P (D = k) = kM , k = 1, 2, ...n.
And K (1) follows the aforementioned power-law distribution
−γ
P (k), i.e. P (K (1) = k) = kMγ , k = 1, 2, ...n.
Define K 0(2) =

(1)
K
P

k=1

Dk , then K (2) = K 0(2) − K (1) .

k · P (K (1) = k) · 1k−1 · D

k=1

=D·K

(1)

.

Therefore, we can obtain the average level-2 degree K
K

(2)

= E[K 0(2) − K (1) ] = (D − 1) · K

(1)

(2)

:

1
γ−1
=
·
.
−2 γ−2

When L ≥ 3, we can derive the average level-L degree in
the same way. The level-L degree K (L) will be expended as:
K (L) = (D1 − 1) + (D2 − 1) + ... + (DK (L−1) − 1)
= K 0(L) − K (L−1) ,
where the distribution of D1 , D2 , ..., DK (L−1) is the same, and
K (L−1)
P
K 0(L) =
Dk .
k=1

The moment generating function of K 0(L) is:
0(L)

φK 0(L) (t) = E[etK ]
n
X
0(L)
P (K (L−1) = k) · E[etK |K (L−1) = k],
=

≈

k=1

k=1
n
X

k=1

and the expectation of K 0(L) can be solved as:
E[K 0(L) ] = φ0K 0(L) (t)|t=0
n
X
k−1
k · P (K (L−1) = k) · [φD (t)]
· φ0D (t)|t=0
=
=

k=1
n
X

k · P (K (L−1) = k) · 1k−1 · D

k=1

=D·K

(L−1)

.

That is to say, the average level-L degree can be written
as:
(L)
K
= E[K 0(L) − K (L−1) ]
(L−1)

= (D − 1) · K
1
(L−1)
·K
.
=
−2

Under the condition of K (1) , the moment generating funcTherefore, we obtain the final expression of K (L) :
tion of K 0(2) is written as:

L−1
n
P
0(2)
0(2)
1
γ−1
φK 0(2) (t) = E[etK ] =
P (K (1) = k) · E[etK |K (1) = k]. K (L) =
·
, L = 1, 2, ..., Lmax . (23)
k=1
−2
γ−2
According to the Property 3 of moment generating function:
Now from Eq. (23), we surely see the conclusion in Theorem
3 holds.

0(2)
E[etK |K (1) = k] = φD1 (t) · φD2 (t) · ... · φDk (t) = [φD (t)]k .
Additionally, for the convinience of understanding, we also
dipict the conclusions on the extendibility features of Theorem
Then φK 0(2) (t) is:
3 in Fig. 5.
n
X
As we can see in Fig. 5, the fractal network keeps branching
(1)
k
P (K = k) · [φD (t)] .
φK 0(2) (t) =
when
2 <  < 3, while the degrees of nodes reduce to 1
k=1

9

As
 weknow, the total number of contact pairs of all levels
n
is
, then the ratio of level-L contact pairs is:
2


(L)
K
n
.
R(L) = m(L) /
=
2
n−1
(c )   3

(b)   3

(a) 2    3

Fig. 5. The extendibility of a fractal network under different values of
correlation exponent .

quickly when  > 3. This result could contribute to explaining
the reasons to the fact that the correlation exponent in real
world falls in the range (2, 3).
Theorem 4. For a fractal wireless network with n nodes
satisfying the conditions below: 1) the level-1 contacts
are selected according to the joint probability distribution
−(γ−1) −
k
k
P (k1 , k2 ) = 1 Mγ, 2 ; 2) the level-1 degree of each node
follows the power-law degree distribution P (k) =
(H)
λmax

−γ
Pnk
−γ .
k=1 k

of the wireless network
Then the maximum capacity
with fractal and hierarchical social communications is



1
 Θ λ
,
2 << 3;
max ·
log n
λ(H)
(24)
max =

Θ(λmax · n−1 ),
 = 3.
where λmax refers to the maximum capacity of wireless
networks with fractal and direct social communications as
defined in Theorem 1 and 2 in Section III.
Proof : Taking all the level-L (L = 1, 2, ..., Lmax ) social
communications in a fractal wierless network into consideration, the average number of hops E (H) [X] to the destination
node of arbitrary hierarchical level can be written as:
E

(H)

(1)

(1)

(2)

[X] = E [X] · R + E [X] · R
+E (Lmax ) [X] · R(Lmax ) ,

(2)

+ ...

(25)

where E (L) [X] (L = 1, 2, ..., Lmax ) refers to the average
number of hops in the case of level-L social communications. Specifically, E (1) [X] is the same as the aforementioned
E[X]. Here we consider the approximate relationship between
E (L) [X] and E (1) [X] that generally holds: E (L) [X] ≈ L ·
E (1) [X]. In addition, R(L) (L = 1, 2, ..., Lmax ) stands for the
ratio between the numbers of contact pairs of level-L and that
of all levels.
Define m(L) (L = 1, 2, ..., Lmax ) to be the number of edges
in the graph of level-L, which is formed by connecting all
level-L contact pairs directly as illustrated in Fig. 3. From
now on we show how to get the R(L) .
The average degree k (L) and the number of edges m(L)
meet the equation below [36]:
k

(L)

(L)

= 2m

(1)

LX
max


γ−1
1 + α + ... + αLmax −1
(γ − 2)(n − 1)

R(l) =

l=1

γ−1
1 − αLmax
·
(γ − 2)(n − 1)
1−α

(γ − 1)
· αLmax − 1
=
(γ − 2)(α − 1)(n − 1)
= 1.
=

Then we have:
(γ − 2)(n − 1)
1 − αLmax
=
,
1−α
γ−1
(γ − 2)(α − 1)(n − 1)
αLmax − 1 =
.
γ−1
So the maximum level can be calculated as:
h
i
log (γ−2)(α−1)(n−1)
+
1
(γ−1)
= Θ (log n) .
Lmax =
log(α)

(26)

(27)

According to Eq. (25), the average number of hops E (H)
in this case is:
E (H) [X] =

=

LX
max

E (l) [X] · R(l)

l=1
LX
max

E (1) [X] · l ·

l=1

= E (1) [X] ·

γ−1
· αl−1
(γ − 2)(n − 1)

LX
max
γ−1
l·αl−1
(γ − 2)(n − 1)
l=1

=E
where S =

LP
max

(1)

γ−1
[X] ·
· S,
(γ − 2)(n − 1)

l · αl−1 , and it can be solved as following:

l=1

S = 1 + 2 · α + 3 · α2 + ... + Lmax · αLmax −1 ,
/n.

So we can obtain the number of edges easily:
m(L) = k

Due to the possible existence of loops in fractal wireless
networks, some contact pairs may be counted repeatedly. For
instance, the vi and vj1 in Fig. 1 can be seen as both level-1
contact pair and level-5 contact pair. As a result, we define
the maximum level Lmax to imply that the contact pairs of
larger levels have been counted before.
Now we discuss the maximum capacity under the condition
of 2<  <3 and  = 3, respectively. For the simplicity of the
1
expressions, we define α = ε−2
.
Case 1: 2 <  < 3, i.e. α > 1
As we know, the summation of R(L) should equal to one:

· n/2.

α · S = 1 · α + 2 · α2 + ... + Lmax · αLmax ,
(α − 1) · S = Lmax · αLmax − 1 + α + ... + αLmax −1
= Lmax · αLmax −

1 − αLmax
.
1−α



10

Together with Eq. (26), S can be given analytically:


1
(γ − 2)(α − 1)(n − 1)
S=
· Lmax ·
+1
α−1
γ−1
1
(γ − 2)(n − 1)
−
·
.
α−1
γ−1
According to the order of Lmax in Eq. (27),
γ−1
·S
(γ − 2)(n − 1)


1
γ−1
=
· Lmax · (α − 1) + Lmax ·
−1
α−1
(γ − 2)(n − 1)
= Θ(log n).
(28)
Then we can have:


E (H) [X] = Θ E (1) [X] · log n .
Finally together with Lemma 2, we obtain the maximum
capacity with hierarchical social communications in the case
2 <  < 3:


1
λ(H)
=
Θ
λ
·
.
(29)
max
max
log n
Case 2:  = 3, i.e. α =
R(L) =

1
−2

= 1. In this case,

γ−1
= R(1) .
(γ − 2)(n − 1)

So the maximum level is calculated as:
Lmax =

1
(γ − 2)(n − 1)
=
= Θ(n).
(1)
γ−1
R

According to Eq. (25), the average number of hops E (H)
when  = 3 is:
E (H) [X] =

LX
max

E (l) [X] · R(l)

l=1

= E (1) [X] · R(1) ·

LX
max

l

l=1

Lmax (1 + Lmax )
2
(γ − 2)n + 1
(1)
= E [X] ·
.
2(γ − 1)
= E (1) [X] · R(1) ·

So the average number of hops is obtained:


E (H) [X] = Θ E (1) [X] · n .
In other words, the maximum capacity in this case is:
−1
λ(H)
).
max = Θ(λmax · n

(30)

To sum up Eq. (29) - Eq. (30), the maximum capacity of
fractal wireless networks with hierarchical social communica(H)
tions λmax in Theorem 4 is achieved.


Fig. 6. The maximum capacity of fractal wireless networks with direct social
communications under different values of β.

V. S IMULATIONS A ND D ISCUSSIONS
In this section, we try to illustrate our results in a more
intuitive manner. We first foucs on the direct social communication scenario and discuss the maximum capacities of
wireless networks in two different destination selection means,
which are illustrated in Fig. 6.
From Fig. 6, when β varies between 0 and 2, the average
number of hops does not decrease distinctly compared with the
case where the destination nodes are chosen uniformly. When
β exceeds 2, the source node prefers to communicate with the
closer direct social contacts, which leads to the exponentially
growth of the maximum throughput. When β is greater than 3,
only Θ(1) average hops are taken for each transmission, which
raisesthe maximum
capacity with direct communications up

to Θ log1 n finally. The results are also consistent with our
findings in Theorem 2.
Next, we discuss the effect of the correlation exponent 
on the achievable capacity. According to Theorem 4, corresponding to different values of the correlation exponent ,
the hierarchical social communications will further reduce the
achievable capacity of fractal wireless networks. The reduction
proportion is log1 n if 2 <  < 3 and n1 if  = 3, compared to
that with direct social communications. The effect of reduction
under two different destination selection means(i.e., uniform
and power-law) are provided in Fig. 7 and Fig. 8, respectively.
Specifically, we can find that the order of the maximum
1
when the correlation exponent 
capacity is reduced by log(n)
is within the range (2, 3), while the decreasement ratio is n1
when the correlation exponent  = 3.
The reduction effect on the maximum capacity can be intuitively explained by the topological extension feature of fractal
wireless networks. As we mention in Section II, the logarithm
of the number of boxes NB (lB ) is linearly dependent on
the length scale lB , which indicates the possible existence
of box extension with a very large size. In other words,
the fractal topology stretches out the shortest path between
some transmission pairs, which leads to the increase of the
average number of hops in the scenario with hierarchical social
communications, and results in the reduction on the maximum
achievable capacity naturally.

11

varies by different values of the corelation exponent  of the
fractal network:



1
 Θ λ
,
2 << 3;
·
max
log n
λ(H)
max =

Θ(λmax · n−1 ),
 = 3.
Surely, there are still some issues to figure out in the future
studies. For instance, why the condition  = 3 is the boundary
to determine whether or not the fractal network is extendable.
Moreover, why is there a leap in the reduction coefficient of
hierarchical social communications when  = 3. We leave all
these open issues in the future works.
Fig. 7. The camparasion between the maximum capacities of fractal wireless
networks with hierarchical and direct social communications under the case
of uniformly distributed destinations.

A PPENDIX
Proof of Lemma 2: The total traffic which the network has to
deal with is nλE[X] while the network can handle T 2 CW
2
2
1 r(n)
simultaneously. So the inequality nλE[X] ≤ T 2 CW
must
2 r 2 (n)
1

q
log n
be satisfied. Recalling that the order of r(n) is Θ
n
in Section II, then we can get Eq. (1).

Proof of Lemma 3: The set {vi1 , vi2 , . . . , viq } contains
q level-1 contacts of the source node. Taking all possible
combinations of nodes into consideration, the probability that
the source node has q level-1 contacts is
X
P (|C| = q) =
P (C = {vi1 , vi2 , . . . , viq })
1≤i1 ≤i2 ≤...iq ≤N

=
Fig. 8. The camparasion between the maximum capacities of fractal wireless
networks with hierarchical and direct social communications under the case
of power-law distributed destinations.

VI. C ONCLUSION AND F UTURE W ORKS
In this paper, we study the capacity of wireless networks
with fractal and hierarchical social communications.
Under the condition of direct social communications, it
has been proved that if the source node communicates with
one of its direct contacts randomly, the maximum capacity
in


Theorem 1 corresponds to the classical result Θ √n 1log n
achieved by Kumar [20]. On the other hand, if the two nodes
with distance d communicate with each other according to the
probability in proportion to d−β , the maximum capacity is



1


√
,
0 ≤ β ≤ 2;
Θ



n · log n


!


1
Θ p
,
2 < β ≤ 3;
λmax =
3−β

n
· log nβ−1







1


,
β > 3.
 Θ
log n
While taking social communications of all levels into account, we discover that the hierarchical social communications
decrease the maximum capacity in a proportion related to the
number of nodes n, and the corresponding reduction factor

· · · qi−
qi−
(q −(γ−1) )q · qi−
q
2
1

X

(Mγ, )q

1≤i1 ≤i2 ≤...iq ≤N

where N is the number of nodes whose degrees are less than
q and the source node selects level-1 contacts only among
those nodes. N grows as fast as n because
Pq−1 −γ
b
N = n · Pb=1
= Θ(n).
n
−γ
b=1 b
The probability that the set C consists of q particular nodes
is
P (C = {vi1 , vi2 , ···viq }) = P

qi−
qi−
· · · qi−
1
2
q

1≤i1 ≤···≤iq ≤N

qi−
qi−
· · · qi−
1
2
q

.

Consequently, we obtain the probability that vk is chosen as
a level-1 contact in Eq. (6) and simplify it with the elementary
symmetric polynomials in Definition 1 and 2.

Proof of Lemma 5: Similar to the case of E1 , E2 is given
as
1

r(n)
4x X
k
X
X
qk− · σq−1,N
q −γ
−1 (Q)
P
·
x
.
E2 =
n
−γ
q
·
σ
(Q)
b
q,N
b=1
x=1 l=1 vk ∈sl
q=q0 +1
(31)
Since N is large enough and the degrees of q level-1
contacts are independently and identically distributed, the law

n
X

,

12

of large numbers can work here. Let Xij = qi−
, Yij = log Xij
j
and Y denote the mean of Yij , then we have
P
Qq
k
qk− σq−1,N
1≤i1 ≤···≤iq ≤N,∃m,im =k
j=1 Xij
−1 (Q)
P
Qq
≡
q · σq,N (Q)
q · 1≤i1 ≤···≤iq ≤N j=1 Xij
P
Pq
1≤i1 ≤···≤iq ≤N,∃m,im =k exp(
j=1 Yij )
P
Pq
≡
q · 1≤i1 ≤···≤iq ≤N exp( j=1 Yij )
P
1≤i1 ≤···≤iq ≤N,∃m,im =k exp(qY)
≡
P
q · 1≤i1 ≤···≤iq ≤N exp(qY)


N −1
q−1
1

 =
≡
= Θ(n−1 ).
N
N
q·
q
(32)
Besides, the probability that the degree of the source node
is greater than q0 is
P (q > q0 ) =

n
X
q=q0

q −γ
Pn
= Θ(1).
−γ
b=1 b
+1

(33)

Then Eq. (31) can be simplified by Eq. (32) - Eq. (33),
namely:
1

r(n)
4x X


X
X
1
−1
x
≡ Θ r(n)
.
E2 ≡
n
v ∈s
x=1

l=1

k

(34)

l

Therefore, the order of E2 is obtained.



R EFERENCES
[1] Y. Chen, R. Li, Z. Zhao, and H. Zhang, “On the capacity of fractal
wireless networks with direct social interactions,” arXiv:1705.09751,
May 27, 2017.
[2] ——, “On the capacity of fractal wireless networks with direct social
interactions,” IEEE Access, under review.
[3] C. Yuan, Z. Zhao, R. Li, M. Li, and H. Zhang, “The emergence of
scaling law, fractal patterns and small-world in wireless networks,” IEEE
Access, vol. 5, no. 1, pp. 3132–3130, Mar. 2017.
[4] X. Ge, Y. Qiu, J. Chen, M. Huang, H. Xu, J. Xu, W. Zhang, Y. Yang,
C. X. Wang, and J. Thompson, “Wireless fractal cellular networks,”
IEEE Wireless Commun., vol. 23, no. 5, pp. 110–119, Oct. 2016.
[5] Y. Hao, M. Chen, L. Hu, J. Song, M. Volk, and I. Humar, “Wireless
fractal ultra-dense cellular networks,” Sensors, vol. 17, no. 4, Apr. 2017.
[6] S. H. Strogatz, “Complex systems: Romanesque networks,” Nature, vol.
433, no. 7024, p. 365, Jan. 2005.
[7] C. Song, S. Havlin, and H. A. Makse, “Self-similarity of complex
networks,” Nature, vol. 433, no. 7024, p. 392, Jan. 2005.
[8] T. Maksymyuk, M. Brych, I. Strykhalyuk, and M. Jo, “Fractal modeling for multi-tier heterogeneous networks with ultra-high capacity
demands,” Smart Comput. Rev., vol. 5, no. 4, pp. 346–355, Aug. 2015.
[9] P. Jacquet, “Capacity of simple multiple-input-single-output wireless
networks over uniform or fractal maps,” IEEE 21st International
Symposium on Modeling, Analysis and Simulation of Computer and
Telecommunication Systems (MASCOTS), pp. 444–453, Aug. 2013.
[10] C. C. Chen, J. S. Daponte, and M. D. Fox, “Fractal feature analysis
and classification in medical imaging,” IEEE Trans. Med. Imag., vol. 8,
no. 2, p. 133, Jan. 1989.
[11] B. B. Mandelbrot and J. A. Wheeler, “The fractal geometry of nature,”
J. R. Stat. Soc., vol. 147, no. 4, p. 468, Jun. 1983.
[12] K. J. Falconer, “Fractal geometry - mathematical foundations and
applications,” Biometrics, vol. 46, no. 3, p. 499, Nov. 2003.
[13] L. K. Gallos, C. Song, and H. A. Makse, “Scaling of degree correlations
and its influence on diffusion in scale-free networks,” Phys. Rev. Lett.,
vol. 100, no. 24, p. 248701, Jun. 2008.
[14] C. Song, S. Havlin, and H. A. Makse, “Origins of fractality in the growth
of complex networks,” Nature Phys., vol. 2, no. 4, pp. 275–281, Mar.
2006.

[15] C. Song, L. K. Gallos, S. Havlin, and H. A. Makse, “How to calculate the
fractal dimension of a complex network: the box covering algorithm,”
J. Stat. Mech-Theory E., vol. 2007, no. 3, pp. 297–316, Jan. 2007.
[16] R. Albert and A. Barabasi, “Barab’asi: Statistical mechanics of complex
networks,” Rev. Mod. Phys., vol. 74, no. 1, Jan. 2002.
[17] M. E. J. Newman, “The structure and function of complex networks,”
SIAM Rev., vol. 45, no. 2, pp. 167–256, Jun. 2003.
[18] R. Albert and H. Jeong, “Internet: Diameter of the world-wide web,”
Nature, vol. 401, no. 6, pp. 130–131, Sep. 1999.
[19] M. Faloutsos, P. Faloutsos, and C. Faloutsos, “On power-law relationships of the internet topology,” SIGCOMM’99, vol. 29, no. 4, pp. 251–
262, Sep. 1999.
[20] P. Gupta and P. R. Kumar, “The capacity of wireless networks,” IEEE
Trans. Inf. Theory, vol. 46, no. 2, pp. 388–404, Mar. 2000.
[21] M. Grossglauser and D. N. C. Tse, “Mobility increases the capacity of
ad hoc wireless networks,” IEEE/ACM Trans. Netw., vol. 10, no. 4, pp.
477–486, Aug. 2002.
[22] M. Gastpar and M. Vetterli, “On the capacity of wireless networks: The
relay case,” in Proc. IEEE INFOCOM 2002, New York, NY, USA.
[23] B. Azimdoost, H. R. Sadjadpour, and J. J. Garcialunaaceves, “On the
capacity of hybrid wireless networks,” Eurasip J. Wireless Commun. and
Netw., vol. 2010, no. 1, pp. 1–9, Sep. 2009.
[24] S. R. Kulkarni and P. Viswanath, “A deterministic approach to throughput scaling in wireless networks,” IEEE Trans. Inf. Theory, vol. 50,
no. 50, p. 351, Jul. 2002.
[25] M. Ji, Z. Wang, H. R. Sadjadpour, and J. J. Garcia-Luna-Aceves,
“Capacity of wireless networks with heterogeneous traffic under physical
model,” in IEEE Conf. Sarnoff, Honolulu, HI, USA, Mar. 2010.
[26] B. Azimdoost, H. R. Sadjadpour, and J. J. Garcia-Luna-Aceves, “The
impact of social groups on the capacity of wireless networks,” in Netw.
Sci. Workshop, West Point, NY, USA, Jun. 2011.
[27] M. K. Kiskani, H. Sadjadpour, and M. Guizani, “Social interaction
increases capacity of wireless networks,” in Wireless Commun. Mobile
Comput. Conf., Sardinia, Italy, Jul. 2013.
[28] M. Karimzadeh Kiskani, B. Azimdoost, and H. R. Sadjadpour, “Effect
of social groups on the capacity of wireless networks,” IEEE Trans.
Wireless Commun., vol. 15, no. 1, pp. 3–13, Jan. 2016.
[29] B. Azimdoost and H. R. Sadjadpour, “Capacity of scale free wireless
networks,” in 2012 IEEE Global Communications Conference (GLOBECOM), Anaheim, CA, USA, Apr. 2013.
[30] B. Azimdoost, C. Westphal, and H. R. Sadjadpour, “Fundamental limits
on throughput capacity in information-centric networks,” IEEE Trans.
Commun., vol. PP, no. 99, pp. 5037–5049, Oct. 2016.
[31] R. Cohen and S. Havlin, “Scale-free networks are ultrasmall,” Phys. Rev.
Lett., vol. 90, no. 5, p. 058701, Feb. 2003.
[32] X. Feng and P. R. Kumar, “Scaling laws for ad hoc wireless networks: an
information theoretic approach,” Foundations and Trends in Networking,
vol. 1, no. 2, pp. 16–47, Jan. 2006.
[33] M. D. Penrose, “The longest edge of the random minimal spanning tree,”
Ann. Appl. Probab., vol. 7, no. 2, pp. 222–230, 1996.
[34] B. Latane and A. Others, “Distance matters: Physical space and social
impact,” PSPB, vol. 21, no. 8, pp. 795–805, Aug. 1995.
[35] T. P. Mitev, “New inequalities between elementary symmetric polynomials,” Journal of Inequalities in Pure and Applied Mathematics(JIPAM),
vol. 4, no. 2, p. 48, 2003.
[36] P. Mahadevan, D. Krioukov, K. Fall, and A. Vahdat, “Systematic
topology analysis and generation using degree correlations,” in ACM
SIGCOMM Comput. Commun. Rev., Pisa, Italy, Jun. 2006.

