A Measure for Quantifying the Topological Structure of Some Networks

Abstract

Determining and quantifying the topological structure of networks is an exciting research topic in theoretical network science. For this purpose, a large amount of topological indices have been studied. They function as effective measures for improving the performance of existing networks and designing new robust networks. In this paper, we focus on a distance-based graph invariant named the Terminal Wiener index. We use this measure to analyze the structure of two well-known hierarchical networks: the Dendrimer tree $\mathcal{T}_{d,h}$ and the Dendrimer graph $\mathcal{D}_{d,h}$. We also investigate two methods of calculation in order to show that the proposed method reduces the computational complexity of the Terminal Wiener index.

1 Introduction

Many complex systems can be modeled as networks and studied using techniques derived from graph theory. Examples include the power grids, communication networks, biological networks, molecular networks, social networks, etc. One of the most fundamental questions arising from the study of networks is to quantify the topological properties of a structure. For this reason, the study of quantitative measures also called topological indices has become a subject of great interest [1]. The concept of topological indices began in 1947, when the physical chemist H. Wiener used the Wiener index for predicting the boiling points of paraffin [2]. Many years after its introduction, the same quantity has been extended to the field of complex systems [3, 4]. Due to the success of this graph invariant, a large number of topological indices have been put forward in the literature [1, 5].

In this paper, we focus on some distance-based graph invariants: the Wiener index [2] and the Terminal Wiener index [6]. These two indices can be used as effective measures to evaluate the efficiency of a network and to quantify the communication between people in a social network [7, 8]. For a general network G, one way for computing the Wiener index or the Terminal Wiener index is to use the definition and compute all the distances between pairs of vertices or pendent vertices, respectively. The complexity of this method is dominated by computing all pairs of shortest paths [9]. Hence, the fundamental task would be to design a fast and an efficient method for calculating any distance-based topological index avoiding computation of all shortest paths. In [10], a powerful method was introduced for computing the Wiener index of networks and showed a linear time complexity especially for hexagonal systems. The main idea of this method is to reduce the original network G into smaller weighted graphs called quotient graphs and then the Wiener index of the original network G is obtained from the quotient graphs. In this work, our aim is to extend this method in the case of the Terminal Wiener index. Then, in order to demonstrate the significance of this technique, we compute the Terminal Wiener index of two hierarchical networks: the Dendrimer tree also called Cayley tree and the Dendrimer graph [11]. For the first network, we apply a re-formula of the Terminal Wiener index, and for the second network, we apply the proposed method.

We proceed as follows: In Sect. 2, we introduce the basic concepts and we prove that the computation of the Terminal Wiener index can be reduced to the computation of the Wiener index of the appropriately weighted quotient graphs. In Sects. 3 and 4, we quantify the topological structure of the Dendrimer tree and the Dendrimer graph by using the two proposed methods. We summarize our findings in the section of concluding remarks.

2 Basic Concepts and Methods

Throughout this paper, we use the terms graph and network interchangeably.

Let $G = (V_G,E_G)$ be a graph with $V_G$ is the set of vertices and $E_G$ the set of edges. Let $d_p(k)$ denote the number of all pairs of pendent vertices (vertices of degree 1) of the graph G whose distances d(u, v) is equal to k. A weighted graph $(G,\omega )$ is a graph G with a weight function $\omega : V(G)\rightarrow \mathbf {R}$ that assigns positive real numbers to the vertices of G. The graph G is called a partial cube if its vertices u can be labeled with binary strings l(u) of a fixed length, such that $d(u,v) = H(l(u),l(v))$. The edges $e = xy$ and $f = uv$ are in the relation Djoković-Winkler $\theta$ if $d(x,u)+d(y,v) \ne d(x,v)+d(y,u)$. The relation $\theta$ is always reflexive and symmetric, and is transitive on partial cubes. Therefore, $\theta$ partitions the edge set of a partial cube into equivalent classes $F_1, F_2, ..., F_k$, called cuts. The techniques used in this work are presented as follows:

2.1 Method Based on a Re-formula of the Terminal Wiener Index

At first, we present the definition of the two topological indices: the Wiener index and the Terminal Wiener index.

Definition 1

Let G be a graph. Then the Wiener index of G is equal to the sum of distances between all pairs of vertices of G.

$$\begin{aligned} W(G)= \sum _{\{u,v\}\subseteq V(G)} d(u,v) \end{aligned}$$

(1)

The Terminal Wiener index is one of the most recent extensions of the Wiener index, that was introduced by Gutman et al. [6].

Definition 2

Let $V_p(G)\subseteq V(G)$ be the set of pendent vertices of the graph G. Then the Terminal Wiener index is defined as the sum of distances between all pairs of pendent vertices of G.

$$\begin{aligned} TW(G)=\sum _{\{u,v\}\subseteq V_p(G)} d(u,v) \end{aligned}$$

(2)

From the above definition, we can rewrite the Terminal Wiener index as follows:

Lemma 1

Let G be a graph with n vertices and $p \ge 2$ pendent vertices. Let D(G) be the diameter of G. Then:

$$\begin{aligned} TW(G) = \left\{ \begin{array}{ll} p(p-1)+d_{p}(3)+2 d_{p}(4)+...+(D-2)d_{p}(D) &{} \; \; \; \; \text {if } D(G) > 2 ,\\ \\ p(p-1) &{} \; \; \; \; \text {if } D(G)=~2. \end{array} \right. \end{aligned}$$

(3)

Proof

The proof of this lemma is obvious, see [12] for illustration.    $\square$

We can observe that Lemma 1 focuses on the calculation of all shortest path between pendent vertices that made the computational complexity of this technique dominated by computing all distances.

2.2 Method Based on Edge-Partitions

In this method, we extend the algorithm proposed by Klavz̃ar [10] to the case of the Terminal Wiener index. For this purpose, we need some auxiliary results.

We start with the definition of the weighted Wiener index of a weighted graph $(G,\omega )$:

Definition 3

[13]. Let $(G,\omega )$ be a weighted graph. Then the weighted Wiener index $W(G,\omega )$ of $(G,\omega )$ is defined as:

$$\begin{aligned} W(G,\omega ) = \sum _{\{u,v\}\subseteq V(G)} \omega (u) \omega (v) d_G(u,v) \end{aligned}$$

(4)

Let $\theta ^*$ be the transitive closure of the relation Djoković-Winkler $\theta$. Then, $\theta ^*$ partitions the edge set of a graph G into $\theta ^*$- equivalent classes. As an example, consider the graph G from Fig. 1. It has two $\theta ^*$-classes $F_1$ and $F_2$.

For describing the proposed method, we need to use the concept of the canonical metric representation of a graph [14].

Fig. 1.

$\theta ^*$-equivalent classes of G

Let $\alpha$ be the canonical metric representation of a connected graph G:

• Let G be a connected graph and $F_1, ..., F_k$ its $\theta ^*$-classes.

• Let $G/F_i$ be the quotient graphs, $i=1, ..., k$. Its vertices are the connected components of $G-F_i$. Two vertices u and v being adjacent if there exist vertices $x \in u$ and $y \in v$ such that $xy \in F_i$.

• Define $\alpha : G \rightarrow \prod _{1 \le i \le k} G/F_i$ with $\alpha : u \rightarrow (\alpha _1(u), ..., \alpha _k(u))$, where $\alpha _i(u)$ is the connected component of $G-F_i$ that contains the pendent vertex u.

• Let $(G/F_i,\omega )$ be a weighted graph, such that, the weight of a vertex of $G/F_i$ is the number of pendent vertices in the corresponding connected components of $G-F_i$. We consider only the pendent vertices that already exist in the original graph G.

The computational complexity of the Terminal Wiener index of a graph G can be reduced as follows:

Theorem 1

For any connected graph with $p \ge 2$ pendent vertices, we have:

$$\begin{aligned} TW(G) = \sum _{1\le i \le k} W(G/F_i,\omega ) \end{aligned}$$

(5)

Proof

Let $C_1^{(i)}, ..., C_{r_i}^{(i)}$ be the connected components of $G-F_i$ with $1\le i \le k$. We denote by $|V_p(C_j^{(i)})|$ the number of pendent vertices in the component $C_j^{(i)}$, and we note that, we should considerate only the number of pendent vertices that already exist in the original graph G.

From the above notations of the canonical metric representation $\alpha$, we can see that:

$$\begin{aligned} TW(G)&= \sum _{\{u,v\}\in V_p(G)} d_G(u,v)\\&= \sum _{\{u,v\}\in V_p(G)} d_G(\alpha (u),\alpha (v))\\&= \sum _{\{u,v\}\in V_p(G)} \sum _{i=1}^k d_{G/F_i}(\alpha _i(u),\alpha _i(v))\\&= \sum _{i=1}^k \sum _{\{u,v\}\in V_p(G)} d_{G/F_i}(\alpha _i(u),\alpha _i(v))\\&= \sum _{i=1}^k \sum _{1\le j\le j^\prime \le r_i} d_{G/F_i}\bigg (C_j^{(i)},C_{j^\prime }^{(i)}\bigg )|V_p(C_j^{(i)})||V_p(C_{j^\prime }^{(i)})|\\&= \sum _{i=1}^k W(G/F_i,\omega ) \end{aligned}$$

   $\square$

From Theorem 1 we can see that the Terminal Wiener index can be reduced to the computation of the Wiener index of the appropriately weighted quotient graphs. In other words, this method focuses only on counting the number of pendent vertices in the corresponding connected components. From this fact, the main result of this subsection can be useful to design a faster algorithm for computing the Terminal Wiener index avoiding the computation of the distances [9], and it can be implemented to run in linear time if the corresponding quotient graphs of a network G are trees. For more information about linear algorithms for the computation of topological indices of a specific class of graphs we refer to see [15, 16]. We note that this technique is also an efficient tool for a hand manipulation, see Sect. 4.

3 Quantifying the Topological Structure of the Dendrimer Tree

In this section, we introduce the construction method and some structural properties of the Dendrimer tree $\mathcal{T}_{d,h}$. Then, we give the analytical expression of the Terminal Wiener index for this structure by using the first technique, which is based on a re-formula of this index.

3.1 Construction Method and Structural Properties

Let $\mathcal{T}_{d,h}$ $(d \ge 3, h \ge 0)$ be a Dendrimer tree with two additional parameters: fixed maximum degree d and the number of iterations or depth h. The Dendrimer tree can be built in the following iterative way. Initially, $\mathcal{T}_{d,0}$ consists of only a central vertex that is the core of the Dendrimer tree. $\mathcal{T}_{d,1}$ is obtained by attaching d vertices to the central vertex. For any $h>1$, we obtain $\mathcal{T}_{d,h}$ from $\mathcal{T}_{d,h-1}$ by attaching $d-~1$ new vertices to the pendent vertices of $\mathcal{T}_{d,h-1}$. Figure 2 illustrates an example for a Dendrimer tree with $d=3$ and $h=~\{0, 1, 2, 3\}$. Every internal vertex of the Dendrimer tree has degree d, and the iteration h denote the distance between all pendent vertices (blue vertices) and the core vertex.

From the construction method of the Dendrimer tree $\mathcal{T}_{d,h}$, we can extract the following structural properties:

• The number of pendent vertices of $\mathcal{T}_{d,h}$ is:

  $$\begin{aligned} p_h=d(d-1)^{h-1} \; \; \; \; \; \; \; \; \; \; \; with \; h\ge 1 \end{aligned}$$

  (6)

• The number of vertices of $\mathcal{T}_{d,h}$ is:

  $$\begin{aligned} N_h = 1+d\frac{(d-1)^h-1}{d-2} \end{aligned}$$

  (7)

• The diameter $D_{h}$ of $\mathcal{T}_{d,h}$ is equal to:

  $$\begin{aligned} D_{h}=2h \end{aligned}$$

  (8)

Fig. 2.

Dendrimer trees $T_{d,h}$ with $d=3$ and $h=\{0, 1, 2, 3\}$ (Color figure online)

3.2 Computation of the Terminal Wiener Index for the Network $\mathcal{T}_{d,h}$

In this part, we use the rewrite of the Terminal Wiener index in order to get analytical expression of this index for the structure $\mathcal{T}_{d,h}$.

We start with the following lemma, that is defined as follows:

Lemma 2

For any Dendrimer tree $\mathcal{T}_{d,h}$. The $d_p(k)$ for $k=\{4,6,8,...,D_{h}\}$ is given by:

$$\begin{aligned} d_{p}(k) = \left\{ \begin{array}{ll} \frac{d(d-2)}{2}(d-1)^{\frac{2h+k-4}{2}} &{} \text {if } k \le 2(h-1) ,\\ \\ \frac{d}{2}(d-1)^{k-1} &{} \text {if } k=2h. \end{array} \right. \end{aligned}$$

(9)

Proof

We have the distance between pendent vertices of the Dendrimer tree $\mathcal{T}_{d,h}$ is always even. In the first iteration, d vertices are attached to the central vertex, and in the next iterations, each pendent vertex $v_i$ is attached to $(d-1)$ vertices. Obviously, with some calculations and due to the symmetry of this structure, we can get the result.    $\square$

Theorem 2

Let $\mathcal{T}_{d,h}$ be a Dendrimer tree with $h \ge 1$ and $d \ge 3$. Then:

$$\begin{aligned} \begin{aligned} TW(\mathcal{T}_{d,h})=d(d-1)^{h-1}\bigg [(d-1)^{h-1} \bigg (hd-\frac{d-1}{d-2}\bigg ) -1+\frac{d-1}{d-2} \bigg ] \end{aligned} \end{aligned}$$

(10)

Proof

By using Lemmas 1, 2 and the structural properties of $\mathcal{T}_{d,h}$, we get:

$$\begin{aligned} \begin{aligned} TW(\mathcal{T}_{d,h})&=p_h(p_h-1)+2d_{p}(4)+4d_{p}(6)+...+(D_{h}-2)d_{p}(D_{h})\\&=d(d-1)^{h-1}[d(d-1)^{h-1}-1]+\frac{d(d-2)}{2}\sum _{i=1}^{h-2}2i(d-1)^{h-1+i}\\&+ d(h-1)(d-1)^{2h-1} \end{aligned} \end{aligned}$$

which yields the Eq.(10).    $\square$

Table 1. The numerical result of the Terminal Wiener index of the dendrimer tree $\mathcal{T}_{d,h}$

The Numerical Result: In Table 1, we present some values of the Terminal Wiener index of the Dendrimer tree $\mathcal{T}_{d,h}$. We can see that the behavior of this measure shows a dominant change with the increasing values of the number of iterations h and the maximum degree d.

4 Quantifying the Topological Structure of the Dendrimer Graph

In this section, we represent the construction method of the dendrimer graph $\mathcal{D}_{d,h}$, analyze its structural properties and we express the Terminal Wiener index of this structure using the second method.

4.1 Construction Method and Structural Properties

Let $\mathcal{D}_{d,h}$ be a Dendrimer graph, where h denote the levels and d the number of vertices added to every vertex in each iteration. The $\mathcal{D}_{d,h}$ can be built in the following iterative way. Initially, the dendrimer graph is composed of a core $\mathcal{D}_0$ that contain a cycle of order $n^\prime$ and $d-1$ vertices attached to each vertex of the cycle, which gives $p_0$ pendent vertices. $\mathcal{D}_{d,1}$ is obtained from $\mathcal{D}_0$ by adding d vertices to each pendent vertex of $\mathcal{D}_0$. Similarly, we obtain $\mathcal{D}_{d,h}$ from $\mathcal{D}_{d,h-1}$ by attaching d vertices to every pendent vertex of $\mathcal{D}_{d,h-1}$. Figure 3, illustrates some iterations of the Dendrimer graph $\mathcal{D}_{d,h}$. The internal vertices of the network $\mathcal{D}_{d,h}$ have degree equal to $d+1$, and the level h denote the distance between all pendent vertices and terminal vertices of the core.

Fig. 3.

(Left) The core $\mathcal{D}_0$ of the Dendrimer graph, with $n^\prime =6$ and $p_0=6$. (Middle and Right) Dendrimer graphs $\mathcal{D}_{d,h}$, with $d=2$ and $h=\{1, 2\}$.

From the construction method of the Dendrimer graph $\mathcal{D}_{d,h}$, we can derive some structural properties:

• The number of pendent vertices of the graph $\mathcal{D}_{d,h}$ is equal to:

  $$\begin{aligned} p_h=d^h (d-1)n^\prime \end{aligned}$$

  (11)

• The number of vertices of $\mathcal{D}_{d,h}$ is equal to:

  $$\begin{aligned} N_h = n^\prime +n^\prime (d^{h+1}-1) \end{aligned}$$

  (12)

• The diameter of this structure $\mathcal{D}_{d,h}$ is equal to:

  $$\begin{aligned} D_{h} = \lfloor {\frac{n^\prime }{2}}\rfloor +2(h+1) \end{aligned}$$

  (13)

4.2 Calculation of the Terminal Wiener Index for the Network $\mathcal{D}_{d,h}$

In this section, we apply the technique based on edge partitions in order to obtain the Terminal Wiener index of the structure $\mathcal{D}_{d,h}$.

The following lemma is crucial for the proof of the next theorem.

Lemma 3

Let $(\mathcal{C}_n,\omega )$ be a weighted cycle of order n, such that, all the vertices have the same weight $\omega$. Then:

$$\begin{aligned} W(\mathcal{C}_n,\omega ) = \left\{ \begin{array}{ll} \frac{1}{8}n^{3}\omega ^2 &{} \; \; \; \text {if } n \; is \; even ,\\ \\ \frac{1}{8}(n^{3}-n)\omega ^2 &{} \; \; \; \text {if } n \; is \; odd. \end{array} \right. \end{aligned}$$

(14)

Proof

Obviously, by using the Definition 3 with identical weights $\omega (u) = \omega (v)$.

   $\square$

Theorem 3

Let $\mathcal{D}_{d,h}$ be a Dendrimer graph, with $d \ge 2$ and $h \ge 0$. Then:

• If $n^\prime$ is even:

$$\begin{aligned} TW(\mathcal{D}_{d,h}) = n^\prime d^{2h} \bigg [(d-1)^2 \bigg (\frac{1}{8}n^{\prime 2}+n^\prime (h+1) \bigg )-d \bigg ]+n^\prime d^h \end{aligned}$$

(15)

• If $n^\prime$ is odd:

$$\begin{aligned} TW(\mathcal{D}_{d,h}) = n^\prime d^{2h} \bigg [(d-1)^2 \bigg ( \frac{1}{8}(n^{\prime 2}-1)+n^\prime (h+1) \bigg )-d \bigg ]+n^\prime d^h \end{aligned}$$

(16)

Proof

The core $\mathcal{D}_0$ of the Dendrimer graph contains a cycle of order $n^\prime$. In the case of an even $n^\prime$, it is easy to observe that an edge e of the cycle $\mathcal{C}$ of $\mathcal{D}_{d,h}$ is in relation $\theta$ with its antipodal edge on $\mathcal{C}$ and if the order of the cycle is odd, then all the edges will be in the same $\theta ^*$-class.

Now, we determine the corresponding weighted graphs of the dendrimer graph $\mathcal{D}_{d,h}$: In category A, we represent the weighted graphs obtained by removing an edge that doesn’t belong to the cycle of the core $\mathcal{D}_0$, and category B contains the weighted graphs obtained by removing an edge or all the edges of the cycle of the core $\mathcal{D}_0$.

Each weighted graph from the category A is repeated $d^i(d-1)n^\prime$ times with $0\le i \le h$, and if we are in the case of an even cycle, the weighted graph from the category B, that is in the top, is repeated $\frac{n^\prime }{2}$ times.

Then, we apply the Theorem 1 with the above representations, the Lemma 3 and the structural properties of $\mathcal{D}_{d,h}$:

• if $n^\prime$ is even

  $$\begin{aligned} TW(\mathcal{D}_{d,h})&= \frac{n^\prime }{2}\bigg [ \frac{p_h}{2}\frac{p_h}{2}\bigg ]+\sum _{i=0}^h d^i(d-1)n^\prime \bigg [ \frac{p_h}{n^\prime (d-1)d^i}*\bigg (p_h-\frac{p_h}{n^\prime (d-1)d^i} \bigg ) \bigg ] \end{aligned}$$

• if $n^\prime$ is odd

  $$\begin{aligned} TW(\mathcal{D}_{d,h})&= \bigg ( \frac{p_h}{n^\prime } \bigg )^2 \bigg (\frac{1}{8}n^{\prime 3}-\frac{1}{8}n^\prime \bigg )+\sum _{i=0}^h d^i(d-1)n^\prime \bigg [ \frac{p_h}{n^\prime (d-1)d^i}\bigg (p_h-\frac{p_h}{n^\prime (d-1)d^i} \bigg ) \bigg ] \end{aligned}$$

Which yield the Eqs. 15, 16, respectively.    $\square$

Table 2. The numerical result of the Terminal Wiener index of the dendrimer graph $\mathcal{D}_{d,h}$

The Numerical Result: In Table 2, we present some values of the Terminal Wiener index of the Dendrimer graph $\mathcal{D}_{d,h}$. Such that, we take into consideration the parity of $n^\prime$. In general, this measure shows an increasing change by modifying the values of parameters.

5 Concluding Remarks

The computation of topological indices is an important task in the study of structural properties of networks. In this paper, we have calculated the Terminal Wiener index of two hierarchical networks: the Dendrimer tree and the Dendrimer graph. In order to show the computational complexity of this index, we have investigated two methods of computation. The first method is based on a re-formula of the Terminal Wiener index and its complexity is dominated by computing all shortest paths at a given distance. The second method is based on the edge-partitions and its efficiency is in the fact that it reduces the original network into smaller components and avoids the computation of all shortest paths.