1

Spatial Motifs for Device-to-Device Network
Analysis (DNA) in Cellular Networks
Tengchan Zeng∗ , Omid Semiari† , Walid Saad∗ , and My T. Thai‡
∗ Wireless@VT, Electrical and Computer Engineering Department, Virginia Tech, VA, USA,
† Department of Electrical Engineering, Georgia Southern University, Statesboro, GA, USA,
‡ Department of Computer and Information Science and Engineering, University of Florida, Gainesville, FL, USA,

arXiv:1712.08818v1 [] 23 Dec 2017

Emails: ∗ {tengchan, walids}@vt.edu, † osemiari@georgiasouthern.edu, ‡ mythai@cise.ufl.edu.
Abstract
Device-to-device (D2D) communication is a promising approach to efficiently disseminate critical
or viral information. Reaping the benefits of D2D-enabled networks is contingent upon choosing the
optimal content dissemination policy subject to resource and user distribution constraints. In this paper, a
novel D2D network analysis (DNA) framework is proposed to study the impacts of frequently occurring
subgraphs, known as motifs, on D2D network performance and to determine an effective content
dissemination strategy. In the proposed framework, the distribution of devices in the D2D network
is modeled as a Thomas cluster process (TCP), and two graph structures, the star and chain motifs,
are studied in the communication graph. Based on the stochastic properties of the TCP, closed-form
analytical expressions for the statistical significance, the outage probability, as well as the average
throughput per device, are derived. Simulation results corroborate the analytical derivations and show
the influence of different system topologies on the occurrence of motifs and the D2D system throughput.
More importantly, the results highlight that, as the statistical significance of motifs increases, the
system throughput will initially increase, and, then, decrease. Hence, network operators can obtain
statistical significance regions for chain and star motifs that map to the optimal content dissemination
performance. Furthermore, using the obtained regions and the analytical expressions for statistical
significance, network operators can effectively identify which clusters of devices can be leveraged for
D2D communications while determining the number of serving devices in each identified cluster.

I. I NTRODUCTION
The number of mobile devices, such as smartphones and tablets, has significantly increased,
and almost half a billion mobile devices were added in 2016 [2]. This growth in mobile
devices has been accompanied by a rise in the need for pervasive wireless connectivity in
A preliminary version of this work was presented in part at the IEEE Asilomar Conference on Signals, Systems, and Computers,
Pacific Grove, CA, USA, Oct. 2017 [1]. This research was supported by the U.S. National Science Foundation under Grant
CNS-1513697.

2

which users require to access their content of interest anywhere, anytime, and on any device.
One effective approach for such large-scale content dissemination is to use device-to-device
(D2D) communication links, which enable mobile devices to communicate directly without
infrastructure [3]–[5]. By leveraging the physical proximity of device, D2D communications
can provide an effective means for disseminating contents (such as disaster alerts, commercial
advertisement, and event notifications) to users across a geographical region. However, when
deploying D2D communications for content dissemination, one must address two key challenges
[3]–[16]: a) designing content dissemination strategies for choosing the number of serving
devices that can serve as seeds for disseminating content, and b) developing metrics to assess
the content dissemination performance under different network topology parameters.
First, in order to choose the optimal set of serving devices, one can leverage a communication
graph composed of of D2D links and make use of graph-theoretic properties to identify the
most influential devices that can store popular content and the number of serving devices is
chosen to maximize the overall system throughput [6]–[11]. For example, in [6] and [7], the
authors use degree centrality, defined as the number of connected D2D links for every node, and
identify the set of nodes with high degree centrality as serving devices. Meanwhile, the works
in [8] and [9] focus on the betweenness centrality, which measures the fraction of shortest paths
passing through a focal node, to identify the set of serving devices for D2D content dissemination
purposes. Moreover, the authors in [10] use the closeness centrality, computed by the sum of
distance between a node and all other nodes in the graph, to establish the strategy for choosing
the best set of serving devices. Furthermore, in [11], the authors first build the adjacency matrix
for D2D communication network, and then choose the set of serving devices by using the
eigenvector corresponding to the largest eigenvalue in the adjacency matrix.
Although the works in [6]–[11] exploit the graph-based properties, these works solely focus on
the low-order network connectivity, which can only capture the features at the level of individual
nodes and edges. In other words, these properties just measure the accumulation of influence from
one device on other devices or D2D links. However, for content dissemination, understanding
how information propagates among multiple nodes is critical, as such propagation can directly
capture the influence of one device on a group of devices. On the other hand, the works in
[6]–[11] do not conduct performance analysis for content dissemination under different network
topologies.
For analyzing the performance of content dissemination using D2D and deriving tractable

3

performance metrics for coverage and data rate, it has become customary to use stochastic
geometry techniques as done in [12]–[16]. For example, in [12], the authors derive the closedform expression for the data rate of a cellular network in which D2D receivers are assumed to
be located at a fixed distance from their transmitters whose locations are modeled as a Poisson
point process (PPP). Also, the authors in [13] derive the outage probability for an arbitrary D2D
link in a model where D2D receivers are uniformly distributed in a circular region around the
transmitters. Moreover, in [14], to capture the notion of device clustering, the authors model
the locations of the devices as a Poisson cluster process (PCP), and develop expressions for
coverage probability and area spectral efficiency. Furthermore, performance metrics, such as
outage probability and average data rate, are also analyzed for systems where the distributions
of base stations and devices follow PPP as done in [15] and [16].
Nevertheless, these works in [12]–[16] do not consider multicast and multi-hop communications, which can extend the range of content dissemination and achieve a better performance
compared with single-hop D2D links [3]. In addition, these works are restricted to the modeling
and analysis of D2D communication, and do not consider any content dissemination policy or the
choice of the optimal set of serving devices. Although multicast and multihop communications
have been considered, respectively, in [17] and [18], these works do not study more practical
scenarios in which both types of communications exist. Moreover, the authors in [17] and [18]
are restricted to D2D systems with uniformly and independently distributed BSs and devices.
However, due to the similarity of users’ content interests, devices can group together within
a given area, e.g., a library, and form clusters rather than being independently and uniformly
distributed.
The main contribution of this paper is to propose a graph-based D2D network analysis (DNA)
framework to determine the content dissemination strategy in clustered D2D networks where both
multicast and multi-hop communications exist. In particular, we first develop a framework, based
on stochastic geometry, that models the distribution of device groups within the D2D network as
a cluster process. Then, we build a D2D communication graph based on the distance distribution
among devices and explore frequently occurring network subgraphs, also known as graph motifs,
to capture content propagation patterns in a group of devices. Next, we theoretically analyze the
occurrences for two types of graph motifs, i.e., chain (multi-hop) and star (multicast) motifs,
and conduct rigorous performance analysis for D2D and cellular devices. Finally, based on
the theoretical analysis, we determine guidelines for designing effective content dissemination

4

strategies in D2D-enabled cellular networks. To our best knowledge, this is the first work that
exploits network motifs to analyze the performance of content dissemination in D2D-enabled
cellular networks. The novelty of this work lies in the following key contributions:
•

We explore occurring network structures, known as graph motifs, to capture content propagation patterns among a group of devices and theoretically analyze the occurrences of different
motifs in D2D networks. In particular, we model the distribution of devices as a Thomas
cluster process (TCP), where the devices are normally scattered around the central points.
Then, based on the distance distribution between two arbitrary devices in the network, we
formulate a distance-based graph. Also, we derive tractable expressions for the statistical
significance to capture the occurrences of two types of motifs, chain and star motifs that
respectively capture multi-hop and multicast communications.

•

We conduct a comprehensive performance analysis for both D2D chain and star motifs.
In particular, we derive closed-form and tractable expressions for the average throughput
for D2D and cellular devices, in presence of motifs. Moreover, we also derive the outage
probabilities for both chain and star motifs and provide analytical bounds for the derived
expressions.

•

Extensive simulation results are used to corroborate the analytical results. In particular, we
can observe the influence of different system topologies on the occurrence and the outage
probability of motifs and the system throughput. Moreover, the results highlight that as the
statistical significance of motifs increases, the system throughput will initially increase, and,
then, decrease.

•

The proposed framework provides important guidelines for designing effective content
dissemination strategies in D2D-enabled cellular networks. In particular, using the derived
expressions and the simulation results, network operators can determine the statistical significance regions for different motifs that map to the optimal system throughput. Moreover,
by comparing the motifs’ statistical significance in each cluster with the optimal regions, the
operators can identify which clusters can be optimally leveraged for D2D communications.
In addition, based on the analytical derivations on the statistical motif occurrence, one can
also determine the number of serving devices in each identified cluster.

The rest of the paper is organized as follows. Section II presents the system model and key
assumptions. In Section III and Section IV, we conduct graph motifs based analysis for D2D

5

w

1

w

2

Star motif

Parent point
Seeding node
Non-seeding node
Feasible D2D link
Infeasible D2D link

Building
Chain motif

BS
(a) Spatial motifs in the representative cluster.

Parent point
Device
BS

(b) Different clusters existing within a geographical area.

Fig. 1. System model that follows a TCP.

networks and develop the performance-related metrics. Simulation results are provided in Section
V and conclusions are drawn in Section VI.
II. S YSTEM M ODEL
Consider a cellular network composed of a single BS and a number of devices that can
communicate with the BS over cellular links as well as directly exchange information with one
another via D2D communications, as shown in Fig. 1(a). Here, devices with injected contents
from the BS are referred to as seeding nodes, and those that obtain the content from nearby
devices are called non-seeding nodes. Moreover, due to the similarity of users’ interests, devices
can concentrate at the same area, such as a library or a stadium [7]–[11], and the grouped devices
will form clusters. As done in [19], to avoid the interference between cellular and D2D links, we
consider a D2D overlay system in which the available bandwidth w is partitioned into w1 = βw
for D2D links and w2 = (1 − β)w for cellular links, where β ∈ (0, 1).
To capture the non-uniform, cluster-based distribution of devices in the network, we consider
a TCP composed of a parent point process and a daughter point process [20]. In particular, as
shown in Fig. 1(b), we model the distribution of the parent points (center points of the clusters)
as a PPP Φp with density λp . Also, the daughter points (devices) in each cluster are normally
scattered with variance σ 2 around the corresponding parent point x ∈ Φp [20]. Note that the
locations of daughter points, with respect to the corresponding parent point, are independent and
identically distributed (i.i.d.) variables [20].

6

A. D2D Communication Graph
As shown in Fig. 1(a), we arbitrarily select a cluster with parent point xr ∈ Φp , considered
as a representative cluster Cr . In cluster Cr , seeding nodes can disseminate popular contents to
other devices via D2D links. Nonetheless, due to limited transmit power, devices that belong to
cluster Cr will not communicate with other clusters. Hence, in cluster Cr , we can model the D2D
network as a directed acyclic graph G = (Φxr , Exr ), whose vertices are devices in the set Φxr and
whose edges, within the set Exr , are D2D links among devices in the cluster. In particular, each
D2D link can be defined as a 2 − tuple edge, e =< i, j >, where device i and device j are the
transmitter and the receiver, respectively, i, j ∈ Φxr . Also, as done in [21] and [22], we assume
that no edge exists between a pair of vertices in graph G if their distance exceeds the maximum
value sth . Moreover, if there exists a graph G0 = (Φ0xr , Ex0 r ) with Φ0xr ⊆ Φxr and Ex0 r ⊆ Exr , the
graph G0 is a subgraph of G. For analytical tractability, we assume that the number of devices in
each cluster is N . As will be clear from the following discussion, although the total number of
devices in each cluster is the same, the number of D2D links varies from one cluster to another,
which maintains generality of the model.
By focusing on cluster Cr , we can observe that groups of D2D links can form various
subgraphs with different structures, which can show how the content propagates among a group
of devices. For example, as shown in Fig. 1(a), two D2D links can share the same transmitter,
and the receiver of one link can act as the transmitter of another D2D link. To characterize D2D
subgraphs appearing in the network, we exploit the notion of graph motifs, defined as frequently
occurring subgraphs. The frequency of occurrence of motifs is typically measured with respect
a baseline system such as a random graph built by randomly assigning D2D links to pairs of
arbitrary devices [23]. In addition, to capture the occurrence of different motifs, one can measure
the statistical significance for each motif using the notion of a Z-score [24]:
Z=

co − cr
,
εr

(1)

where co is the number of occurrences of a given motif in the network, and cr and εr denote,
respectively, the mean and the standard deviation of motif’s occurrence in the baseline system.
For the baseline system, we use a random graph model that shares the same total number of D2D
links existing in graph G, but randomly rewires each link between an arbitrary pair of devices
[25]. For example, if there are co motifs where one seeding node sends data to two non-seeding
nodes, the total number of edges in the baseline system will be 2co . As a result, the edge between

7


any pair of devices in the baseline system occurs with the same probability 2co / N2 . Using the

2

properties of the binomial distribution, we can derive cr = bN/3c 31 2co / N2
1 − 2co / N2

2
 

2

and εr = bN/3c 31 2co / N2
1 − 2co / N2
1− 31 2co / N2
1−2co / N2
, where bxc is

the floor function of x and xy denotes the number of y-combinations in a set with x elements.
Furthermore, we can observe that

dZ
dco

> 0, when co ≥ 1, indicating that the Z-score is an

increasing function of the motif occurrence parameter co .
In addition, we assume that each seeding device can disseminate content to multiple nonseeding devices, and non-seeding devices are capable of forwarding the content to others.
Therefore, as illustrated in Fig. 1(a), for any group of three devices, we can observe two types
of communication motifs – the star motif and the chain motif. The star motif can be viewed
as a multicast link in which the seeding device disseminates its content to two non-seeding
devices, and is captured by two edges sharing the same first element in the communication
graph. Meanwhile, the chain motif can be considered as a two-hop D2D link. In particular, the
seeding device will first send its content to a non-seeding device in one time slot, which functions
as a relay propagating the content to another non-seeding device in the next time slot. Similarly,
for the chain motif in the graph, there exists two edges connecting three devices, and the second
element of one edge is the first element of the next edge. Here, we focus on three-device motifs,
since larger motifs can always be constructed using smaller motifs, and, hence, our framework
can easily extend to any other graph structures.
B. Channel Model and Interference Analysis
For the D2D link (i, j), from device i ∈ Φxr to j ∈ Φxr , in cluster Cr centred at xr ∈ Φp , the
received power is given by Pij = Pt hij d−α
ij , where Pt is the transmit power of each device, hij
is the channel gain that follows a Rayleigh fading distribution, dij is the corresponding distance
between any two devices i and j, and α is the path loss exponent. Similar to the bandwidth
allocation in [26], in a star motif, we assume that the two D2D links will split the frequency
resources evenly and each link uses half of the bandwidth,

w1
.
2

Meanwhile, in a chain motif,

the first and second D2D links will reuse the same resource, w1 , at two consecutive time slots.
Therefore, due to the co-channel deployment of D2D links, the receiving nodes will encounter
interference from other D2D links, irrespective of their motif types. We designate the interference
xr
on device j generated from devices in cluster Cr as the intra-cluster interference Ij−intra
, and

8

xr
the interference from devices within other clusters as the inter-cluster interference Ij−inter
. The

two types of interference are given by:
X
X
xr
xr
=
=
1y Pt hyj d−α
,
I
Ij−intra
yj
j−inter

X

1y Pt hyj d−α
yj ,

(2)

x∈Φp \xr y∈Φx

y∈Φxr \{i,j}

where the indicator variable 1y = 1 if device y is transmitting data to other device via D2D
link; otherwise, 1y = 0. For a large D2D network, the thermal noise power at the receiver will
be substantially smaller than the received interference power [27]. Thus, the expression of the
signal-to-interference-plus-noise ratio (SINR) of the D2D link can be approximated as
Pt hij d−α
ij
.
δij ≈ xr
xr
Ij−intra + Ij−inter

(3)

Since we consider a single-cell scenario and the BS will transmit contents to seeding devices in
different time slots, the seeding devices will experience no interference and their signal-to-noise
ratio (SNR) will be:
Pb hbj d−α
bj
δbj =
,
Pn

(4)

where Pb is the transmission power of the BS, hbj is the channel gain that follows a Rayleigh
distribution, dbj represents the distance between the BS and device j, and Pn captures the power
of the background noise. Moreover, we can find the achievable data rate R for D2D links and
cellular links, according to R = w3 log2 (1 + δ), where w3 is the assigned bandwidth.
C. Relationship between the Occurrence of Motifs and the D2D System Throughput
For each cluster, the BS can collect the occurrence of different communication motifs and
calculate the data rate of each device. Due to the co-channel deployment of D2D links, interference will increase as the frequency of occurrence of any given motif increases. As a result, as
shown in Section II-A, the Z-score is an increasing function of the occurrence zo of motifs, and,
hence, the interference will increase as the Z-score increases. Thus, for clusters having higher
Z-scores, content dissemination via D2D communications will experience a high interference,
thereby degrading the dissemination throughput. On the other hand, for clusters with a smaller
Z-score, only a limited number of D2D links can be formed, resulting in a low spectral reuse.
Therefore, we need to find the Z-score region, which can yield an optimal system performance.
This Z-score region can allow identifying clusters that can be used for D2D communications
by comparing any given Z-score of the clusters with the optimal region. Moreover, the number

9

of seeding devices in each identified cluster can be determined based on the number of cellular
devices.
However, due to the lack of closed-form expressions that link the Z-score and the wireless
throughput, directly finding the Z-score region that yields the optimal system performance is
challenging. Nevertheless, we can observe that the value of the Z-score depends on number of
devices N , their locations, and the maximum communication distance sth . In addition, the system
throughput is also a function of these three parameters. Therefore, instead of finding a direct
relationship between the Z-score and the system throughput, one can alternatively determine the
analytical expressions of the Z-score and the system throughput as function of their common
parameters. Using such analytical expressions, the BS can collect data on the Z-score and
the system throughput corresponding to the same parameter settings, and further observe how
the system throughput changes as the Z-score of motifs varies. The changes of the system
throughput as function of the Z-score can enable network operators to disclose the relationship
between the occurrence of motifs and the system performance, and further determine the Z-score
region which maps to the optimal system throughput. Next, we will first leverage the distance
distribution among devices and the stochastic properties inherent in the TCP to derive tractable
expressions for the Z-scores of chain and star motifs and the system throughput. Also, we will
further identify the hidden relationship between motifs and the system performance based on
simulation results and determine the content dissemination strategy for clustered networks.
III. S TATISTICAL S IGNIFICANCES OF S TAR AND C HAIN M OTIFS
In this section, for an arbitrarily chosen group of three devices in cluster Cr , we leverage
the distance distribution between any two randomly and uniformly selected points to derive the
probability of the content dissemination pattern among three devices being either a star or chain
motif. Based upon the probability of occurrence, we can derive closed-form expressions for the
Z-scores.
A. Distance Distribution
We arbitrarily select a group of three devices in cluster Cr , and due to the stationarity of the
TCP, we treat an arbitrary device out of these three devices as a typical point located at the
origin. In addition, we assume that the location of the parent point is at xr ∈ Φp , and the other
two devices are located at y1 and y2 relative to the parent point. Therefore, according to the

10

definition of the TCP in Section II, y1 and y2 are distributed according to a symmetric normal
distribution with the variance σ 2 around the parent point xr , and the parent point also follows
a zero mean symmetric normal distribution with the variance σ 2 relative to the origin point.
Additionally, xr , y1 , and y2 are i.i.d. variables, xr , y1 , y1 ∈ R2 .
Furthermore, we denote {Di }i=1,...,N −1 as the distance set from the typical point to another
uniformly selected point in the same cluster. In particular, the realization of {Di }i=1:N −1 is
di = ||xr +yi ||, i = 1, . . . , N − 1. Conditioned on the distance from the typical point to the parent
point sr = ||xr ||, the probability density function (PDF) of di follows a Rician distribution [27]:
 


di s r
d2i + s2r
di
2
I0
, di , sr ≥ 0,
(5)
fD (di , sr ; σ ) = 2 exp −
σ
2σ 2
σ2
where I0 (·) is the modified Bessel function of first kind with zero order. Conditioned on sr =
||xr ||, the elements in Di are also i.i.d. variables as shown in [27]. Moreover, the authors in
[27] also conclude that when the distances from the typical point to the parent points of other
clusters are a fixed value, the distances between the typical device at the origin and the devices
in other clusters are also i.i.d. variables and follow Rician distributions. As it will be clear from
the following discussion, we use this property to calculate inter-cluster interference. In addition,
according to the definition of the TCP, the distance sr follows a Rayleigh distribution with scale
parameter σ and with the following PDF:
sr
fS (sr ; σ ) = 2 exp
σ
2




s2r
− 2 , sr ≥ 0.
2σ

(6)

B. Probability of Occurrence of Motifs
Based on the distance distribution obtained in Section III-A, we can derive the probability
with which a group of three arbitrary devices will form either a chain or star motif. First, we can
observe that, for both chain and star motifs, there is a node capable of directly communicating
with the other two devices. Hence, if we consider a device with two direct D2D links as a
typical point located at the origin, we can express the distance from the typical point to the
other two uniformly and randomly selected devices as the norm of m = xr + y1 ∈ R2 , and
(1)

(2)

n = xr +y2 ∈ R2 , where m = (m(1) , m(2) ), n = (n(1) , n(2) ), and xr = (xr , xr ). In a TCP, y1 and
(1)

y2 are zero mean complex Gaussian random variables relative to xr . Hence, m(1) ∼ N (xr , σ 2 ),
(1)

(2)

(2)

(1)

n(1) ∼ N (xr , σ 2 ), m(2) ∼ N (xr , σ 2 ), and n(2) ∼ N (xr , σ 2 ). In addition, xr ∼ N (0, σ 2 ),
(2)

and xr ∼ N (0, σ 2 ). Thus, s1 = ||m|| and s2 = ||n|| follow the Rayleigh distribution. Due to
the common element, xr , in m and n, the distances s1 and s2 are also correlated. Based on the

11

distribution and correlation between s1 and s2 , next, we can obtain the joint probability of both
s1 and s2 being smaller than sth .
Theorem 1. Given that s1 = ||m|| and s2 = ||n|| follow Rayleigh distributions and are correlated,
the joint probability of both s1 = ||m|| and s2 = ||n|| being smaller than sth is:
 2


s2th


∞
k
γ
1
+
k,
3σ 2
3 X 1
 ,
PS,S (sth , sth ) =
4 k=0
2
(k!)
where γ(·, ·) refers to the lower incomplete gamma function, defined as γ(a, b) =

(7)
Rb
0

ca−1 e−c dc.

Proof: To calculate the probability of both s1 = ||m|| and s2 = ||n|| being smaller than the
distance threshold sth , we first calculate the correlation existing between m and n as
ρ=

1
cov(m, n)
cov(m, n)
p
= .
=p
m n
2
cov(m, m) cov(n, n)

(8)

where m and n are the standard deviations for m and n, respectively. Then, due to the fact
that both ||m|| and ||n|| follow Rayleigh distribution, we are able to have the joint cumulative
density function (CDF) as [28]
PS,S (s1 , s2 ) =

3
4

∞ 
X
k=0


 

k γ 1 + k, s21 γ 1 + k, s22
3σ 2
3σ 2
1
4

k!Γ (k + 1)

, s1 ≥ 0, s2 ≥ 0,

(9)

where Γ (·) represents to the complete gamma function, defined as Γ (a) = (a − 1)!. After
replacing s1 and s2 with sth and simplifications, we can obtain the joint CDF shown in (7).



In (7), PS,S (sth , sth ) represents the probability that a typical device can build D2D links
with two other devices uniformly and randomly chosen from the cluster, irrespective of the
link direction. Since a receiving device cannot access the content from multiple transmitters
at the same time, and a transmitter can spread content to at most two devices simultaneously,
PS,S (sth , sth ) is the probability with which any three devices can form either the star motif or the
chain motif. For ease of exposition, we use the term “three-node motifs” to refer to the union of
the star and chain motifs, and replace PS,S (sth , sth ) with PS,S hereinafter. Moreover, we assume
that the probability of one three-node motif being a star motif is θ, 0 < θ < 1, and the probability
of forming a chain motif will be 1−θ.

12

C. Z-scores for chain and star motifs
To calculate the Z-scores for the chain and star motifs, we must derive the occurrence of
these two motifs in cluster Cr and compare it with the baseline system. In particular, the
maximum number of groups of three devices is Nm = b N3 c, where any arbitrary two groups
do not share common devices and devices in each group are randomly and uniformly selected.
Therefore, we can express the probability of n groups of three-node motifs existing in a cluster

as Nnm (PS,S )n (1 − PS,S )Nm −n , n ≤ Nm . Using the properties of the binomial distribution, the
expected number co of three-node motifs in the network with distance will be co = Nm × PS,S .
Accordingly, the expected numbers of occurrence for the star and chain motifs are give by
chain
= (1 − θ)Nm × PS,S .
cstar
o = θNm × PS,S , co

(10)

For the baseline system, the total number of D2D links is equal to the one in the considered
system. In particular, since the number of D2D links in each three-node motif is two, the expected
number of D2D links in the baseline system is 2co . Therefore, we can derive the probability of
one pair of arbitrary devices being connected by a D2D link in the baseline system as follows:
Pr =

4PS,S
2co
=
.
Nm
N
−
1
m
2

In this case, the probability with which three devices form a three-node motif is

(11)
3
1


(Pr )2 (1 −

Pr ). Furthermore, the probabilities of being a star motif or a chain motif in the baseline system
are 3θ(Pr )2 (1 − Pr ), and 3(1 − θ)(Pr )2 (1 − Pr ), respectively. Similarly, by using the binomial
for the star motif and
and the standard deviation εstar
distribution, we can express the mean cstar
r
r
for the chain motif in the baseline system as
and εchain
the counterparts cchain
r
r
48θNm (PS,S )2 (Nm − 1 − 4PS,S )
,
(Nm − 1)3
48(1 − θ)Nm (PS,S )2 (Nm − 1 − 4PS,S )
cchain
=
,
r
(Nm − 1)3
s


48θNm (PS,S )2 (Nm − 1 − 4PS,S )
48θNm (PS,S )2 (Nm − 1 − 4PS,S )
star
εr =
1−
,
(Nm − 1)3
(Nm − 1)3
s


48(1−θ)Nm (PS,S )2 (Nm −1−4PS,S )
48(1−θ)(PS,S )2 (Nm −1−4PS,S )
chain
εr =
1−
.
(Nm − 1)3
(Nm − 1)3
cstar
r =

(12)
(13)
(14)

(15)

After obtaining the occurrence information for both motifs in cluster Cr and the baseline
system, we can derive the Z-scores for both motifs.

13

Remark 1. By using (1), (10) and (12)-(15), the closed-form expressions of Z-scores for both
motifs in the D2D system can be determined. In fact, (10) captures the expected number of
occurrences for chain and star motifs can be derived in cluster Cr . Also, (12)-(15) represent the
mean and standard variance of the occurrences for both motifs in the baseline system.
As observed from Theorem 1, the joint probability PS,S is a function of the total number of
devices N , the distribution variance σ 2 , and the maximum allowable distance sth . Therefore, we
can conclude that the value of the Z-score is also dependent on N , σ 2 , and sth .
IV. E XPECTED AVERAGE T HROUGHPUT AND O UTAGE P ROBABILITY
To analyze the performance of the content dissemination strategy under different clustered
network topology parameters, we use the distance distribution properties inherent in the TCP to
calculate the expected throughput for D2D and cellular devices. Moreover, the outage probabilities for the chain and star motifs are also derived.
A. Expected Throughput for Non-Seeding Devices in the Star Motif
As shown in Fig. 2, we choose an arbitrary star motif as a representative star motif Ms . In
motif Ms , the two receiving devices, j and k, will access data via D2D links from the seeding
device, i, located at the origin. Moreover, we assume that the set of seeding devices in star
motifs as Tx in the cluster x ∈ Φp , and the number of elements in Tx cannot be greater than
Nm .
Next, we take device j as an example and conduct Laplace transforms for the intra- and
inter-cluster interference encountered by device j. Based on the derived Laplace transforms,
we can study the performance-related metrics, such as the outage probability and the expected
throughput. According to the stationarity of the TCP and the symmetry between the two receiving
devices in the star motif, the Laplace transforms of the intra- and the inter-cluster interference
for device j can apply to another device k and receiving devices in other star motifs.
Lemma 1. For device j in the star motif, the Laplace transform of the intra-cluster interference
can be expressed as
Lstar
j-intra (s)

Z
=
0

∞

1
fV (v1 )dv1 PS,S + 1 − PS,S
1 + sPt v1−α 1

where fV1 (v1 ) = fS (v1 ; 2σ 2 ), v1 ≥ 0.

Nm −1
,

(16)

14

Cluster parent point
Device
D2D communication link
Intra-cluster interference vector
Inter-cluster interference vector
Auxiliary vector

Representative cluster

||yj-y||
||x+y -xr-yj ||

j
k

i

Fig. 2. Illustration of the inter- and intra-cluster interference to the representative star motif.



Proof: See Appendix A.

By using the Bernoulli’s inequality [29], we can obtain a lower bound on the intra-cluster
interference over device j, as given by the following corollary.
Corollary 1. The lower bound of the intra-cluster interference will be given by:
Z ∞
sPt
star
Lj-intra (s) ≥ 1 − (Nm − 1)
fS (v1 ; 2σ 2 )dv1 PS,S .
α
v
+
sP
t
0
1

(17)


Proof: See Appendix B.

The Laplace transform of the inter-cluster interference and its lower bound are derived next.
Lemma 2. For device j in the star motif, the Laplace transform of the inter-cluster interference
is given by
Lstar
j-inter (s)=exp −λp 2π

Z

∞

Z

∞

1−
0

0

1
fV (v2 |t)dv2 PS,S + 1 − PS,S
1 + sPt v2−α 2

Nm !

!
tdt ,
(18)

where fV2 (v2 |t) = fD (v2 , t; 3σ 2 ), v2 ≥ 0.
Proof: See Appendix C
Corollary 2. The lower bound for the inter-cluster interference can be expressed as
!

2
α π csc 2π
(sP
)
t
α
PS,S .
Lstar
j-inter (s) ≥ exp −λp 2πNm
α
Proof: See Appendix D.



(19)


15

Considering that content dissemination within a star motif will not occur an outage if and
only if the SINR for both D2D links in the star motif exceed the minimum requirement δth , then
the outage probability for the star motif can be derived as follows.
Theorem 2. The outage probability for the star motif is given by:
Z ∞



2

δth α
δth α
star
star
star
Poutage (δth ) = 1 −
r Lj-intra
r fR1 (r1 )dr1 ,
Lj-inter
Pt 1
Pt 1
0

(20)

where fR1 (r1 ) = fS (r1 ; 2σ 2 ), r1 ≥ 0,
Proof: We first calculate the SINR distribution for a D2D link to obtain the probability of a
D2D link meeting the minimum SINR requirement:
Pstar
j (δth ) = E(P{δj > δth })
 

δth xr
xr
α
= E P hij > (Ij-intra + Ij-inter )||xr + yj ||
Pt

 

δth xr
(a)
xr
α
(I
+ Ij-inter )||xr + yj ||
= E E − exp
Pt j-intra




Z ∞
δth α
δth α
(b)
star
star
=
Lj-inter
r Lj-intra
r fR1 (r1 )dr1 ,
Pt 1
Pt 1
0

(21)

where (a) follows the fact that the channel gain hij ∼ exp(1) for a Rayleigh fading channel. In
(b), we substitute r1 with ||xr + yj || and use polar coordinates. Note that the probability in (21)
can also apply to the link between device i to k, due to the symmetry between device j and k.
Since outage will not occur when the SINR of both links exceed the threshold δth , we can use
the probability in (21) for both D2D links in the star motif to derive the outage probability in


(20).
Since Rj =

w1
2

2R

log2 (1 + δj ), Rj < R will yield δj < 2 w1 − 1. Thus, after replacing δth with

2R

2 w1 − 1 in (21), we can have the CDF of the throughput for receiving devices in the star motif.
Corollary 3. Based on the distribution of the SINR, the CDF of the throughput for receivers in
the star motif can be derived as follows:
!
2R
Z ∞
w1
2
−
1
r1α Lstar
P(Rj < R) = 1 −
Lstar
j-inter
j-intra
P
t
0

2R

2 w1 − 1 α
r1
Pt

!
fR1 (r1 )dr1 .

(22)

By using the relationship between the CDF and the expected value, we are able to obtain the
expected throughput of receiving devices in the star motif in the following corollary.

16

Representative cluster

Cluster parent point
Device
D2D communication link
Intra-cluster interference vector
Inter-cluster interference vector
Auxiliary vector

||xr+y||

i
k
j

Fig. 3. Illustration of the inter- and intra-cluster interference to the representative chain motif.

Corollary 4. The expected throughput for receivers in the star motif is given by:
Z ∞
(1 − P (Rj < R))dR
Estar =
0
!
!
2R
2R
Z ∞Z ∞
w1
w1
2
−
1
−
1
2
=
Lstar
r1α Lstar
r1α fR1 (r1 )dr1 dR.
j-inter
j-intra
P
P
t
t
0
0

(23)

B. Expected Throughput for Non-Seeding Devices in the Chain Motif
As illustrated in Fig. 3, we also choose an arbitrary representative chain motif Mc in cluster
Cr . In motif Mc , the seeding device i first transmits its data to j, which is at the origin and will
subsequently propagate the data to device k. Similar to the receiving devices in the star motif,
device k in a chain motif also accesses its content from the transmitter at the origin. Therefore,
the Laplace transforms of the intra- and inter-cluster interference given by (16) and (18), and
the probability in (21) can be directly applied to the D2D link between device j and k. In
contrast, due to the different assigned bandwidth, the CDF and the expected throughput must be
re-calculated. Nevertheless, unlike device k, device j located at the origin has different distance
distribution to the serving device and the devices that generate interference from receiving nodes
in the star motifs. Hence, to obtain the expression of the throughput, we need to derive the Laplace
transforms of the intra- and inter-cluster interference for receiving device j in the chain motif.
Lemma 3. For the typical device j in the chain motif, the Laplace transform of the intra-cluster
interference, conditioned on the distance from the typical point to the parent point sr = ||xr ||,
is given by
Lchain
j-intra (s|sr )

Z
=
0

∞

1
fV (v3 |sr )dv3 PS,S + 1 − PS,S
1 + sPt v3−α 3

where fR (v3 |sr ) = fD (v3 , sr ; σ 2 ), v3 ≥ 0.

Nm −1
,

(24)

17



Proof: See Appendix E.

Corollary 5. After using the proof in Appendix B, the lower bound of the intra-cluster interference can be expressed as:
Lchain
j-intra (s|sr )

Z
≥ 1 − (Nm − 1)
0

∞

v3α

sPt
fD (v3 , sr ; σ 2 )dv3 PS,S .
+ sPt

(25)

Lemma 4. For the device j in the chain motif, the Laplace transform of the inter-cluster
interference is given by
Lchain
j-inter (s)=exp

Z

∞

Z

∞

1−

−λp 2π
0

0

1
fV (v4 |t)dv4 PS,S + 1 − PS,S
1 + sPt v4−α 4

Nm !

!
tdt ,
(26)

where fV4 (v4 |t) = fD (v4 , t; σ 2 ), v4 ≥ 0.


Proof: See Appendix F.

Corollary 6. After using the proof in Appendix D, the lower bound of the inter-cluster interference experienced by the link from i to j is given by
2

(sPt ) α π csc
Lchain
j-inter (s) ≥ exp −λp 2πNm
α

2π
α

!


PS,S

.

(27)

Therefore, for a device j, we can obtain the SINR distribution, which allows deriving the
outage probability of a chain motif in the following theorem.
Theorem 3. The outage probability of the chain motif can be calculated as
star
chain
Pchain
(δth )
outage (δth ) = 1 − Pk (δth )Pj
Z ∞





δth α
δth α
star
star
Lj-inter
=1−
r Lj-intra
r fR1 (r1 )dr1 ×
Pt 1
Pt 1
0
Z ∞ Z ∞





δth α
δth α
chain
chain
Lj-inter
r Lj-intra
r |sr fR2 (r2 |sr )fSr (sr )dr2 dsr ,
Pt 2
Pt 2
0
0

(28)

where fR2 (r2 |sr ) = fD (r2 , sr ; σ 2 ), r2 ≥ 0, and fSr (sr ) = fS (sr ; σ 2 ), sr ≥ 0.
Proof: For the D2D link from device i to j, the probability of the D2D link from device i to j
meeting the minimum SINR threshold is
Pchain
(δth ) = E(P{δj > δth })
j

 
δth xr
xr
α
= ER P hij > (Ij-intra + Ij-inter )||xr + yj ||
Pt

18


 

δth xr
xr
α
= ER E exp
(I
+ Ij-inter )||xr + yj ||
Pt j-intra




Z ∞Z ∞
δth α
δth α
(a)
chain
chain
Lj-inter
=
r Lj-intra
r |sr fR2 (r2 |sr )fSr (sr )dr2 dsr .
(29)
Pt 2
Pt 2
0
0
In (a), we first make a change of variables by setting r2 = ||xr + yj ||, and, then, we perform
one de-conditioning in terms of r2 and another de-conditioning for sr , and finally convert the
coordinates from Cartesian to polar. Based on the distance distribution, we have fR2 (r2 |sr ) =
fD (r2 , sr ; σ 2 ) and fSr (sr ) = fS (sr ; σ 2 ). Then, since the outage will not occur if and only if the


SINR of both links exceed the threshold level, we can obtain (28).
R

Similar to Corollary 3, we can replace δth with 2 w1 −1 in (21) and (29) to obtain the throughput
CDF for the two D2D links in the chain motif. To calculate the throughput, we can observe
that the chain motif is equivalent to a two-hop network. According to the work in [30], if a
non-seeding node is connected to the seeding node through a multi-hop link with length l, the
achievable throughput of the non-seeding device is limited by 1/l times the minimum of all D2D
link rates over the multi-hop communication network. Therefore, we can derive the expected
throughput of non-seeding devices j and k in the following corollaries.
Corollary 7. Since device j is directly connected to seeding node i, the expected throughput is

Z ∞
R
1
w1
−
1)))dR
(1 − (1 − Pchain
(2
Echain = min
j
1
0
!
!
R
R
Z ∞Z ∞Z ∞
w1
w1
2
−
1
2
−
1
Lchain
=
r2α Lchain
r2α |sr fR2 (r2 |sr )fSr (sr )dr2 dsr dR.
j-inter
j-intra
Pt
Pt
0
0
0
(30)
Corollary 8. Since device k connects to the seeding device i via a two-hop link, the expected
throughput is given by
!
!
R
R
Z ∞Z ∞
w1
w1
2
2
−
1
−
1
1
0
Lstar
r1α Lstar
r1α |sr fR1 (r1 )dr1 dR,
Echain
= min
j-inter
j-intra
2
P
P
t
t
0
0
!
!
!
R
R
Z ∞Z ∞Z ∞
w1
w1
2
−
1
2
−
1
Lchain
r2α Lchain
r2α |sr fR2 (r2 |sr )fSr (sr )dr2 dsr dR .
j-intra
j-inter
P
P
t
t
0
0
0
(31)
C. Expected Throughput for Seeding Devices
From the work in [27], conditioned on the distance between the parent point xr ∈ Φp and a
typical device at the origin, the distance between the device in cluster Cr and the typical device

19

follows a Rician distribution. Equivalently, if we set the condition as the distance z = ||xr − b||
between the parent point xr and the BS b, the distance r3 between the devices in the cluster
and the BS will also follow a Rician distribution fR3 (r3 |z) = fD (r3 , z; σ 2 ), z, r3 > 0. Similar
to (22), we change the coordinates and replace the variables, and, then, the CDF of throughput
will be:
R

2 w2 − 1
Pn ||xr + y − b||α fY (y)fX (xr )dxr dy
P (Rk < R) =1 −
P
2
2
b
R
R
Z ∞ Z ∞ wR
2 2 −1
=1−
Pn r3α fR3 (r3 |z)fZ (z)dr3 dz,
P
b
0
0
Z

Z

(32)

where r3 = xr + y − b.
According to the distribution of parent points, z can be interpreted as the distance between
the BS and a point which is uniformly distributed in the area. Without loss of generality, we
assume that the BS is at the center of a square area of side 2L that contains all devices. Hence,
the CDF expression for the distance z will be:



πz 2 ,
0 ≤ z ≤ L,


√
√


1
L
2
2
2 − L2 , L ≤ z ≤
FZ (z) =
πz
−
4
z
arccos
−
L
z
2L,
z

4L2 
√


1,
2L ≤ z.
We can then find the corresponding PDF as



πz,

1 
fZ (z) =
πz − 4z arccos
2L2 



0,


L
z

0 ≤ z ≤ L,
√
, L ≤ z ≤ 2L,

(33)

(34)

otherwise.

Based on the relationship between the SINR and the expected throughput, we can obtain the
expression of the throughput in the next Lemma.
Lemma 5. For seeding devices within the D2D network, the expected throughput is given by
Z ∞ Z ∞ Z ∞ wR
2 2 −1
Eseeding =
Pn r3α fR3 (r3 |z)fZ (z)dr3 dzdR.
(35)
Pb
0
0
0
D. Average Throughput per Device in the D2D Network
After obtaining the throughput for each device and the possibility of a three-node motif being
either a star or a chain motif, the expected average throughput per device in the D2D network
can be derived next.

20

Table. I. Simulation parameters.
Parameter

Definition

Value

Pb

Transmission power of BS

46 dBm

Pt

Transmission power of devices

23 dBm

N

Number of devices in each cluster

25, 50, 100

Distribution variance

50, 100, 150

λp

Cluster density

5, 10, 20 clusters/km2

w

Total system bandwidth

20 MHz

β

Bandwidth parameter

0.6

α

Path loss exponent

4

δth

Minimum SINR requirement

0 dB

θ

Probability of being a star motif

1/3

/

Noise spectral density

−174 dBm/Hz

/

Simulation area

1 km × 1 km

σ

2

Corollary 9. Based on (23), (30), (31), as well as (35), and the possibilities of a three-node
motif being either a star or a chain motif, the average throughput per device will be:
0
chain
star
Eseeding + Eseeding
Echain
+ cchain
Echain + cchain
2cstar
o
o
o Estar + co Eseeding + co
N
star
chain
chain 0
2c Estar + co Echain + co Echain + (co + 1)Eseeding
.
= o
N

ER =

(36)

We can observe that the average throughput per device in the content dissemination network
is dependent on the same factors on which the Z-scores of both the star and chain motifs
depend, namely, the distribution variance, the number of devices, and the maximum allowable
distance. Thus, both the system throughput and Z-score for motifs are functions of the same
network parameters and, hence, the BS can collect data on Z-scores of chain and star motifs and
the system throughput corresponding to the same settings. This data can help understand how
the dissemination performance changes as the occurrence of different motifs varies and further
identify Z-score regions, which map to the optimal content dissemination performance, for both
chain and star motifs, as will also be evident from the subsequent simulation results.
V. S IMULATION R ESULTS
Next, we present rigorous simulation results to validate the analytical derivations and show
the relationship between the occurrence of motifs and the content dissemination performance in
D2D-enabled cellular networks. In particular, we consider that wireless devices are distributed
within a square area of 1 km × 1 km. Also, for each D2D link, the transmitter is chosen

21

1

0.9

0.9

0.8

0.8

Joint CDF

0.6
Simulation, <2=50

0.5

2

Analysis, < =50

0.4

Simulation, <2=100

0.3

Outage probability

0.7

0.7

Analysis, <2=100

0.6
0.5
0.4
0.3

Simulation, chain motif
Simulation, star motif
Analysis, chain motif
Analysis, star motif
Upper bound, chain motif
Upper bound, star motif

0.2

0.2
Simulation, <2=150

0.1

0.1

Analysis, <2=150

0
0

10

20

30

40

50

60

70

0
11

80

Fig. 4. Joint CDF versus distance threshold sth .

12

13

14

15

16

17

18

19

20

Maximum D2D communication distance (m)

Maximum D2D communication distance (m)

Fig. 5. Outage probability versus distance threshold sth .

randomly. To observe the impacts of different network topology parameters on the occurrence
of motifs and the system throughput, we change the distribution variance and the cluster density.
Simulation parameters are summarized in Table I.
Fig. 4 shows the joint CDF PS,S of a group of three devices being a three-node motif versus
the communication distance sth for systems with λp = 20 cluster/km2 and σ 2 = 50, 100, 150.
As shown in Fig. 4, we can observe that the simulation results corroborate the analytical results
in Theorem 1. Moreover, as sth increases, PS,S increases. But, the increase varies differently for
different D2D systems. In particular, to achieve PS,S = 1, the sth for the D2D system with σ 2 = 50
should be around 40 m, while the ones of systems with σ 2 = 100, 150 are, respectively, close to
50 m and 60 m. This is due to the fact that, in the system with a smaller distribution variance,
devices are more likely to form three-node motifs. Furthermore, for a fixed distance threshold
sth , we can observe that the system with a lower variance will lead to a higher probability PS,S .
For example, when sth = 20 m, the values of PS,S are approximately 0.75, 0.45, and 0.28 for
the systems with σ 2 = 50, 100, 150.
Fig. 5 shows the outage probability, for chain and star motifs, versus the D2D communication
distance sth with δth = 0 dB, σ 2 = 100, and N = 25 in each cluster. As illustrated in Fig.
5, the simulation results validate the analytical results in Theorems 2 and 3. Moreover, the
lower bounds for the intra- and inter-cluster interference in Corollaries 1, 2, 5 and 6 can lead
to upper bounds of outage probabilities for both motifs. Moreover, we can observe that, as sth
increases, the outage probabilities for both motifs will increases. This is due to the fact that as
the maximum distance increases, the D2D system is more likely to have more motifs, leading
to more interference and thereby a lower SINR.

22

6

Simulation, 6p=5
Analysis, 6p=5
Simulation, 6p=10

5

Throughput (Mbps)

Analysis, 6p=10
Simulation, 6p=20

4

Analysis, 6p=20

3

2

1

0
0

5

10

15

20

25

30

35

40

Maximum D2D communication distance (m)

Fig. 6. Average data per device versus the distance threshold sth .

Fig. 6 shows the average throughput per device when σ 2 = 100, λp = 5, 10, 20, and N = 50.
In Fig. 6, we can observe that the simulation results of average throughout corroborate the
analytical derivations in Corollary 9. Moreover, Fig. 6 shows that the cluster density λp plays
an important role in determining the content dissemination performance. In particular, when sth
is small, the system with a smaller cluster density λp will have a higher throughput. However,
when sth is above 30 m, the throughput of D2D systems with lower cluster densities is slightly
better than the counterpart for systems with higher cluster densities. In fact, when sth is very
small, both motifs barely exist in the networks and, thus, D2D links will experience less intracluster interference. In this case, the system performance mainly depends on the inter-cluster
interference. Therefore, a system with a lower cluster density tends to have a better performance
than the one with a higher density. However, when sth is larger, more and more three-node
motifs will appear in the network, increasing both inter- and intra-cluster interference. From
the analytical results in Section IV, we can observe that when the sth , N , and σ 2 are fixed,
intra-cluste interference will be the same for systems with different λp . But, due to the different
cluster densities, the inter-cluster interference will be different. We can observe that, when sth
increases to 25 m, the average throughput is equal for all λp . This is due to the fact that, in such
a case, the intra-cluster interference has a dominant effect on the system performance.
Fig. 7 presents the Z-scores for the chain and star motifs versus the distribution variance
σ 2 . We can observe that, as the distribution variance σ 2 increases, the Z-scores for both chain
and star motifs will decrease. The reason is that, for a fixed sth , as the variance σ 2 increases,
both motifs are less likely to occur in the network. Moreover, we can observe that Z-scores
of chain motifs are higher than the counterparts for star motifs, indicating that chain motifs

23

15.85

22.6

Star motif
22.5

15.75

22.4

15.7

22.3

15.65

22.2

15.6

22.1

15.55
20

40

60

80

100

120

Distribution variance <

140

Z-score, chain motif

Z-score, star motif

Chain motif
15.8

22
160

2

Fig. 7. Z-scores for the chain and star motifs versus the distribution variance σ 2 .
4

4
Chain motif

3.5

3.5

3

3

Throughput (Mbps)

Throughput (Mbps)

Star motif

2.5
2
1.5

2.5
2
1.5

1

1

0.5

0.5

0
15.3

15.35

15.4

15.45

15.5

15.55

15.6

15.65

Z-score

15.7

15.75

15.8

0
21.6

21.7

21.8

21.9

22

22.1

22.2

22.3

22.4

22.5

Z-score

Fig. 8. Average throughput per device versus Z-score for the star and chain motifs.

are more likely to occur in network. It can be explained that star motifs need more restrictive
requirements, i.e., two different D2D links sharing the same seeding device. By combining the
results of Fig. 6 and Fig. 7 with the analytical derivations in Section III and Section IV, we can
see that both the average throughput per device and the Z-scores for the motifs are dependent
on the same factors, i.e., σ 2 and sth .
Fig. 8 shows the average throughput per device versus the Z-scores for the chain and star
motifs. Here, we consider a network with λp = 10 clusters/km2 , σ 2 = 100 and N = 50.
Moreover, we change the value of sth so that we can change the Z-scores for both motifs
as well as the system throughput. From Fig. 8, we can see that, for both motifs, the average
throughput is a concave function with respect to the Z-scores for both motifs. Moreover, there
exists Z-score regions for both chain and star motifs that lead to a higher throughput than points
in other Z-score regions. This stems from the tradeoff between received signal power over the
D2D communication links and the interference introduced from the increased number of D2D
links. In addition, the optimal Z-score regions will be different for star and chain motifs. For

24

108

Cellualr device
D2D device
All device

Throughput (bps)

107

106

105

104

0

0.2

0.4

0.6

0.8

1

Bandwidth parameter -

Fig. 9. Average throughput of D2D, cellular, and all devices versus bandwidth parameter β.

example, for chain motifs, the Z-score region where the network can achieve at least 2 Mbps
throughput is from 21.71 to 21.92, and the counterpart for the star motif is from 15.35 to 15.47.
Fig. 9 shows the average throughput for D2D and cellular devices under different bandwidth
parameter β, when σ 2 = 100, sth = 15 m, and λp = 10 clusters/km2 . We can observe that
as the bandwidth parameter increases, the average average D2D throughput will increase while
the throughput for cellular devices decreases. We can conclude that the system performance is
mainly determined by the average throughput of D2D devices. Therefore, when designing a D2D
system, the bandwidth parameter β should be properly chosen so that the D2D-enabled cellular
system can achieve the target performance.
From the simulation results shown in Figs. 6-9, we can observe that, as long as the operator
knows the Z-scores of the chain and star motifs appearing in the D2D communication networks,
the achievable content dissemination performance, captured by the average throughput, can
be predictable. The predictable throughput can enable the operator to find the optimal Zscore regions which can achieve a high dissemination performance. Hence, when using D2D
communications for content dissemination, the operators can identify the proper clusters to
achieve a targeted performance by verifying whether the Z-score is in the optimal region.
Furthermore, because of the relationship between the Z-score and the expected number of
occurrences of chain and star motifs, we can also determine the number of seeding devices
in each identified cluster. As such, based on the relationship between motif occurrence and
content dissemination performance, the operators can decide on how to identify proper clusters
to leverage D2D communications and further determine the number of seeding devices in each
identified cluster for the optimal content dissemination policy.

25

VI. C ONCLUSION
In this paper, we have proposed a novel DNA framework to explore frequent communication patterns across D2D users, known as spatial motifs, to optimize content dissemination in
emerging cellular networks. In particular, we have utilized the stochastic geometry to derive the
analytical results of the frequency of occurrence for two common types of motifs composed
of three devices, and the performance metrics for each motif in the D2D-enabled clustered
network. Simulation results have corroborated the analytical derivations and shown the impact
of system topologies on the occurrence of motif and the average throughput. More importantly,
the simulation results have shed light on the relationship between the average throughput and
the motifs appearing in the D2D network. The derived relationship can be used by network
operators to obtain the statistical significance regions for different motifs observed in the network, and to determine the content dissemination strategy – e.g., allocating bandwidth to D2D
links, determining number of seeding nodes, etc – in future cellular networks. Therefore, by
implementing the proposed framework, the operator can obtain guidelines for designing effective
content dissemination strategies in D2D-enabled cellular networks.
A PPENDIX
A. Proof of Lemma 1
We conduct the Laplace transform of the intra-cluster interference of device j as



X
(a)

−s
Pt hyj ||yj − y||−α 
Lstar
j-intra (s) = E exp
y∈Txr \yi




Y

= ET x r 

Ehyj [exp(−sPt hyi ||y − yj ||−α )]

y∈Txr \yi




(b)

= ETxr 

Y

y∈Txr \yi
(c)

=

NX
m −1 
k=0



1

1 + sPt ||y − yj ||−α

1
E
1 + sPt ||y − yj ||−α

k




Nm − 1
×
(PS,S )k (1 − PS,S )Nm −1−k
k
|
{z
}
P(n=k)

Nm −1 Z
(d) X
=
k=0

0

∞

1
fV (v1 )dv1
1 + sPt v1−α 1

k



Nm − 1
×
(PS,S )k (1 − PS,S )Nm −1−k
k

26

=

NX
m −1 
k=0

(e)

Z

∞

=

0

 Z ∞
k
Nm − 1
1
× (1 − PS,S )Nm −1−k
−α fV1 (v1 )dv1 PS,S
k
1 + sPt z1
0
Nm −1
1
fV (v1 )dv1 PS,S + 1 − PS,S
,
(37)
1 + sPt v1−α 1

where (a) is the definition of Laplace transformation, (b) follows from assumption of Rayleigh
fading channel and the channel gain hyj ∼ exp(1), and the transformation in (c) is due to the
fact the locations of devices within the cluster are i.i.d. variables. We substitute v1 with ||y − y1 ||
and change the Cartesian to the polar coordinates in (d). Since both y and y1 are i.i.d., and
follow zero mean complex Gaussian distribution with variance σ 2 , we have the PDF of v1 :
fV1 (v1 ) = fS (v1 ; 2σ 2 ), v1 ≥ 0. The change in (e) is based upon the binomial expansion of a
power of a sum [31].
B. Proof of Corollary 1
The lower bound could be given by:
Z ∞
Nm −1
1
2
star
fS (v1 ; 2σ )dv1 PS,S + 1 − PS,S
Lj-intra (s) =
1 + sPt v1−α
0



Nm −1
Z ∞
1
2
fS (v1 ; 2σ )dv1 PS,S
= 1− 1−
1 + sPt v1−α
0

Nm −1

Z ∞
sPt
(a)
2
fS (v1 ; 2σ )dv1 PS,S
= 1−
v1α + sPt
0
Z ∞
(b)
sPt
≥1 − (Nm − 1)
fS (v1 ; 2σ 2 )dv1 PS,S ,
(38)
α
v
+
sP
t
0
1
R∞
where the changes in (a) is replacing 1 with 0 fS (v1 ; 2σ 2 )dv1 . In (a), due to the fact 0 ≤
R ∞ sPt
sPt
≤
1
and
the
monotony
of
integral,
we
can
have
0
≤
f (z ; 2σ 2 )dz1 ≤
α
v1 +sPt
0 v1α +sPt S 1
R∞
R∞
t
f (z ; 2σ 2 )dz1
fS (v1 ; 2σ 2 )dv1 = 1. Also, since PS,S ∈ (0, 1), the product of PS,S and 0 vαsP
+sPt S 1
0
1

is in (0, 1). In (b), based on the Bernoulli inequality [29], we are able to derive the lower bound
for the intra-cluster interference as (38).
C. Proof of Lemma 2
We can conduct Laplace transform for the inter-cluster interference as



X
X
(a)

−s
Lstar
Pt hyj ||x + y 0 − xr − yj ||−α 
j-inter (s) = E exp
x∈Φp \xr y 0 ∈Tx

27



#

"
Y

= EΦp 

Y

ETx

y 0 ∈Tx

x∈Φp \xr



"

(b)

Y

= EΦp 

ET x

Y
y 0 ∈Tx

x∈Φp \xr

"

Ehyj [exp(−sPt hyj ||x + y 0 − xr − yj ||−α )] 
1
1 + sPt ||x + y 0 − xr − yj ||−α


Nm 
Y X
ET x

(c)

= EΦp

x∈Φp \xr k=0

#


1
1 + sPt ||x + y 0 − xr − yj ||−α
#

k
×

 
Nm
(PS,S )k (1 − PS,S )Nm −k
k
|
{z
}
P(n=k)


(d)

= EΦp 

Nm Z
Y X

x∈Φp \xr k=0

R2


k  
1
Nm
fZ2 (z2 )dz2 ×
(PS,S )k (1−PS,S )Nm −k 
−α
1 + sPt ||x + z2 ||
k

! !
k  
Nm
×
(PS,S )k (1−PS,S )Nm −k dx
= exp −λp
k
2
2
R
R
k=0
Z
Nm ! !
Z
1
(f )
f (z )dz2 PS,S + 1 − PS,S
= exp −λp
1−
dx
−α Z2 2
R2 1 + sPt ||x + z2 ||
R2
Z ∞
Nm ! !
Z ∞
1
(g)
tdt ,
= exp −λp 2π
1−
fV (v2 |t)dv2 PS,S + 1 − PS,S
1 + sPt v2−α 2
0
0
(e)

Z

Nm Z
X
1−

1
fZ (z2 )dz2
1+sPt ||x+z2 ||−α 2

(39)
where fV2 (v2 |t) = fD (v2 , t; 3σ 2 ), v2 ≥ 0. The changes in (a), (b), (c), and (f) follow the same
reasons with (a), (b), (c) and (e) in (37). In (d), we assume z2 = y 0 − xr − yi , where y 0 , xr , and
y1 are i.i.d. and follow zero mean complex Gaussian distribution with variance σ 2 . Hence, z2
follows zero mean complex Gaussian distribution with variance 3σ 2 . (e) can be explained by the
probability generation function (PGFL) of PPP [32]. In (g), we substitute the variable v2 with
||x + z2 || and convert the coordinates from Cartesian to polar.
D. Proof of Corollary 2
We first analyse one part of the equation in (39), and then obtain the final inequation. Similar
to Appendix B, we can have
Nm
Z ∞
Z ∞
sPt
1
≥ 1 − Nm
fR (v2 |t)dv2 PS,S .
−α fR (v2 |t)dv2 PS,S + 1 − PS,S
α
v2 + sPt
1 + sPt v2
0
0
(40)

28

Based on that, we can derive
Z ∞
star
Lj-inter (s) = exp −λp 2π

Nm ! !
1
1−
fR (v2 |t)dv2 PS,S + 1 − PS,S
tdt
1 + sPt v2−α
0
0
 

Z ∞ Z ∞
sP t
fR (v2 |t)dv2 PS,S tdt
≥ exp −λp 2πNm
v2α + sPt
0
0


Z ∞
sPt
(a)
= exp −λp 2πNm
v2 dv2 PS,S
v2α + sPt
0
!
2
2π
α
(sP
)
π
csc(
)
(b)
t
α
= exp −λp 2πNm
PS,S ,
(41)
α
R∞
where the change in (a) depends on the fact of Rice distribution where 0 fR (v2 |t)tdt = v2 .
Z

∞

The changes in (b) are with the aid of Mathematica.
E. Proof of Lemma 3
We conduct the Laplace transform of the intra-cluster interference as



X
(a)

−s
Pt hyj ||xr + y||−α 
Lchain
j-inter (s|sr ) = E exp
y∈Tx \yi




Y

= ETx 

Ehyj [exp(−sPt hyj ||xr + y||−α )]

y∈Tx \yi


(b)

= ET x 



Y

Ehyj

y∈Tx \yj
(c)

=

NX
m −1 Z
k=0

R2





1

1 + sPt ||xr + y||−α

1
fY (y)dy
1 + sPt ||xr + y||−α

k



Nm − 1
×
(PS,S )k (1 − PS,S )Nm −1−k
k
|
{z
}
P(n=k)

NX
m −1 

 Z
k
Nm − 1
1
=
fY (y)dyPS,S × (1 − PS,S )Nm −1−k
−α
k
1
+
sP
||x
+
y||
t
r
R2
k=0
Z
Nm −1
1
(d)
=
f (y)dyPS,S + 1 − PS,S
−α Y
R2 1 + sPt ||xr + y||
Z ∞
Nm −1
1
(e)
=
fV (v3 |sr )dv3 PS,S + 1 − PS,S
,
(42)
1 + sPt v3−α 3
0
where fR (v3 |sr ) = fD (v3 , sr ; σ 2 ). The changes in (a), (b), (c), and (d) follow the same reasons
with (a), (b), (c) and (e) in (37). In (e), we change the variables by using v3 = ||xr + y|| and
convert from Cartesian to polar coordinates.

29

F. Proof of Lemma 4
We conduct Laplace transform for the inter-cluster interference as



X X
(a)

−s
Lchain
Pt hyj ||x + y 0 ||−α 
j-inter (s) = E exp
x∈Φp \xr y 0 ∈Tx



#

"
Y

= EΦp 

ETx

= EΦp 

#

"
Y

ET x

Y
y 0 ∈Nx

x∈Φp \xr

"

Nm Z
Y X

(c)

= EΦp

Ehyj [exp(−sPt hyi ||x + y 0 ||−α )] 

y 0 ∈Nx

x∈Φp \xr


(b)

Y

x∈Φp \xr k=0

R2

1

1 + sPt ||x + y 0 ||−α

1
fY (y 0 )dy 0
1 + sPt ||x + y 0 ||−α

k

#

Nm
×
(PS,S )k (1 − PS,S )Nm −k
k
|
{z
}


P(n=k)

Z

(d)

− λp

= exp

1−
R2





Nm Z
X
k=0

1
f (y 0 )dy 0
0 ||−α Y
1
+
sP
||x
+
y
2
t
R
! !

k

Nm
(PS,S )k (1 − PS,S )Nm −k dx
k
Z
Nm ! !
Z
1
(e)
dx
= exp −λp
1−
f (y 0 )dy 0 PS,S + 1 − PS,S
0 −α Y
R2 1 + sPt ||x + y ||
R2
Z ∞
Nm ! !
Z ∞
1
(f )
1−
= exp −λp 2π
fV (v4 |t)dv4 PS,S + 1 − PS,S
tdt ,
1 + sPt v4−α 4
0
0

×

(43)
where fV4 (v4 |t) = fD (v4 , t; σ 2 ). The changes in (a), (b), (c) (d), and (e) follow the same reasons
with (a), (b), (c), (d), and (e) in (39). In (f), we change the variables by using v4 = ||x + y 0 ||
and convert from Cartesian to polar coordinates.
R EFERENCES
[1] T. Zeng, O. Semiari, and W. Saad, “Exploring spatial motifs for device-to-device network analysis (DNA) in 5G networks,”
in Proc. of IEEE Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, Oct. 2017.
[2] Cisco. Cisco visual networking index: Global mobile data traffic forecast update, 2016 to 2021 white paper, 2017.
[3] A. Asadi, Q. Wang, and V. Mancuso, “A survey on device-to-device communication in cellular networks,” IEEE
Communications Surveys & Tutorials, vol. 16, no. 4, pp. 1801–1819, Fourthquarter 2014.
[4] J. Liu, N. Kato, J. Ma, and N. Kadowaki, “Device-to-device communication in LTE-advanced networks: A survey,” IEEE
Communications Surveys & Tutorials, vol. 17, no. 4, pp. 1923–1940, Fourthquarter 2015.
[5] M. Mozaffari, W. Saad, M. Bennis, and M. Debbah, “Unmanned aerial vehicle with underlaid device-to-device
communications: Performance and tradeoffs,” IEEE Transactions on Wireless Communications, vol. 15, no. 6, pp. 3949–
3963, Jun. 2016.

30

[6] B. Bai, L. Wang, Z. Han, W. Chen, and T. Svensson, “Caching based socially-aware D2D communications in wireless
content delivery networks: A hypergraph framework,” IEEE Wireless Communications, vol. 23, no. 4, pp. 74–81, Aug.
2016.
[7] O. Semiari, W. Saad, S. Valentin, M. Bennis, and H. V. Poor, “Context-aware small cell networks: How social metrics
improve wireless resource allocation,” IEEE Transactions on Wireless Communications, vol. 14, no. 11, pp. 5927–5940,
Nov. 2015.
[8] Y. Zhao, W. Song, and Z. Han, “Social-aware data dissemination via device-to-device communications: Fusing social and
mobile networks with incentive constraints,” IEEE Transactions on Services Computing, accepted and to appear, 2017.
[9] R. Agarwal, V. Gauthier, M. Becker, T. Toukabrigunes, and H. Afifi, “Large scale model for information dissemination
with device to device communication using call details records,” Computer Communications, vol. 59, pp. 1–11, Mar.
2015.
[10] Z. Wu, L. Wang, G. Araniti, and Z. Han, “Exploiting social-interest interactions on user clustering and content
dissemination in device-to-device communications,” in IEEE/CIC International Conference on Communications in China
(ICCC), Shenzhen, China, Nov. 2015.
[11] Y. Meng, C. Jiang, H.-H. Chen, and Y. Ren, “Cooperative device-to-device communications: Social networking
perspectives,” IEEE Network, vol. 31, no. 3, May/June 2017.
[12] X. Lin, J. G. Andrews, and A. Ghosh, “Spectrum sharing for device-to-device communication in cellular networks,” IEEE
Transactions on Wireless Communications, vol. 13, no. 12, pp. 6727–6740, Dec. 2014.
[13] S. Andreev, O. Galinina, A. Pyattaev, K. Johnsson, and Y. Koucheryavy, “Analyzing assisted offloading of cellular user
sessions onto D2D links in unlicensed bands,” IEEE Journal on Selected Areas in Communications, vol. 33, no. 1, pp.
67–80, Jan. 2015.
[14] M. Afshang, H. S. Dhillon, and P. H. J. Chong, “Fundamentals of cluster-centric content placement in cache-enabled
device-to-device networks,” IEEE Transactions on Communications, vol. 64, no. 6, pp. 2511–2526, Jun. 2016.
[15] A. H. Sakr and E. Hossain, “Cognitive and energy harvesting-based d2d communication in cellular networks: Stochastic
geometry modeling and analysis,” IEEE Transactions on Communications, vol. 63, no. 5, pp. 1867–1880, May 2015.
[16] E. Baştug, M. Bennis, M. Kountouris, and M. Debbah, “Cache-enabled small cell networks: Modeling and tradeoffs,”
EURASIP Journal on Wireless Communications and Networking, vol. 2015, no. 1, p. 41, Feb. 2015.
[17] X. Lin, R. Ratasuk, A. Ghosh, and J. G. Andrews, “Modeling, analysis, and optimization of multicast device-to-device
transmissions,” IEEE Transactions on Wireless Communications, vol. 13, no. 8, pp. 4346–4359, Aug. 2014.
[18] J. Dai, J. Liu, Y. Shi, S. Zhang, and J. Ma, “Analytical modeling of resource allocation in D2D overlaying multi-hop
multi-channel uplink cellular networks,” IEEE Transactions on Vehicular Technology, vol. 66, no. 8, pp. 6633–6644, Aug.
2017.
[19] B. Zhou, H. Hu, S.-Q. Huang, and H.-H. Chen, “Intracluster device-to-device relay algorithm with optimal resource
utilization,” IEEE Transactions on Vehicular Technology, vol. 62, no. 5, pp. 2315–2326, Jun. 2013.
[20] M. Haenggi, Stochastic geometry for wireless networks. Cambridge University Press, 2012.
[21] E. Frlan, “Direct communication wireless radio system,” Apr. 4 2000, US Patent 6,047,178.
[22] H. Ding, S. Ma, and C. Xing, “Feasible D2D communication distance in D2D-enabled cellular networks,” in Proc. of
IEEE International Conference on Communication Systems (ICCS), Macau, China, Nov. 2014.
[23] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, “Network motifs: simple building blocks of
complex networks,” Science, vol. 298, no. 5594, pp. 824–827, Oct. 2002.
[24] U. Alon, “Network motifs: theory and experimental approaches,” Nature Reviews Genetics, vol. 8, no. 6, pp. 450–461,
Jun. 2007.
[25] E. D. Kolascyk, Statistical Analysis of Network Data Methods and Models. Springer, 2009.
[26] Q. Zhang, W. Saad, W. Bennis, and M. Debbah, “Network formation game for multi-hop wearable communications over
millimeter wave frequencies,” in Proc. of IEEE Global Communications Conference (GLOBECOM), Singapore, Dec.
2017.
[27] M. Afshang, H. S. Dhillon, and P. H. J. Chong, “Modeling and performance analysis of clustered device-to-device
networks,” IEEE Transactions on Wireless Communications, vol. 15, no. 7, pp. 4957–4972, Jul. 2016.
[28] M. K. Simon, Probability distributions involving Gaussian random variables: A handbook for engineers and scientists.
Springer Science & Business Media, 2007.
[29] Y. C. Li and C. C. Yeh, “Some equivalent forms of bernoullis inequality: A survey,” Applied Mathematics, vol. 4, no. 07,
pp. 1070–1093, Jun. 2013.
[30] M. Sikora, J. N. Laneman, M. Haenggi, D. J. Costello, and T. E. Fuja, “Bandwidth-and power-efficient routing in linear
wireless networks,” IEEE Transactions on Information Theory, vol. 52, no. 6, pp. 2624–2633, Jun. 2006.
[31] J. Harris and H. Stöcker, Handbook of mathematics and computational science. Springer Science & Business Media,
1998.
[32] S. Chiu, D. Stoyan, W. S. Kendall, and J. Mecke, Stochastic geometry and its applications. John Wiley & Sons, 2013.

