A Note on Distance-based Graph Entropies

Abstract

A variety of problems in, e.g., discrete mathematics, computer science, information theory, statistics, chemistry, biology, etc., deal with inferring and characterizing relational structures by using graph measures. In this sense, it has been proven that information-theoretic quantities representing graph entropies possess useful properties such as a meaningful structural interpretation and uniqueness. As classical work, many distance-based graph entropies, e.g., the ones due to Bonchev et al. and related quantities have been proposed and studied. Our contribution is to explore graph entropies that are based on a novel information functional, which is the number of vertices with distance k to a given vertex. In particular, we investigate some properties thereof leading to a better understanding of this new information-theoretic quantity.

1. Introduction

Studies of the information content of complex networks and graphs have been initiated in the late 1950s based on the seminal work due to Shannon [1]. Numerous measures for analyzing complex networks quantitatively have been contributed [2]. A variety of problems in, e.g., discrete mathematics, computer science, information theory, statistics, chemistry, biology, etc., deal with investigating entropies for relational structures. For example, graph entropy measures have been used extensively to characterize the structure of graph-based systems in mathematical chemistry, biology [3] and in computer science-related areas, see [4]. The concept of graph entropy [5,6] introduced by Rashevsky [7] and Trucco [8] has been used to measure the structural complexity of graphs [3,9,10]. The entropy of a graph is an information-theoretic quantity that has been introduced by Mowshowitz [11]. Here the complexity of a graph [12] is based on the well-known Shannon’s entropy [1,5,11,13]. Importantly, Mowshowitz interpreted his graph entropy measure as the structural information content of a graph and demonstrated that this quantity satisfies important properties when using product graphs etc., see, e.g., [11,14–16]. Note the Körner’s graph entropy [17] has been introduced from an information theory point of view and has not been used to characterize graphs quantitatively. An extensive overview on graph entropy measures can be found in [6]. A statistical analysis of topological graph measures has been performed by Emmert-Streib and Dehmer [18].

Dehmer [5] presents some novel information functionals of V that capture, in some sense, the structural information of the underlying graph G. Several graph invariants, such as the number of vertices, edges, distances, the vertex degree sequences, extended degree sequences (i.e., the second neighbor, third neighbor, etc.), degree powers and connections, have been used for developing entropy-based measures [5,6,19,20]. In this paper, we study graph entropies related to a new information functional, which is the number of vertices with distance k to a given vertex. Distance is one of the most important graph invariants. For a given vertex v in a graph, the number of vertices with distance one to v is exactly the degree of v; the number of pairs of vertices with distance three, which is also related to the clustering coefficient of networks [21], is also called the Wiener polarity index introduced by Wiener in 1947 [22].

In view of the vast of amount of existing graph entropy measures [3,5], there has been very little work to find their extremal values [23]. A reason for this might be the fact that Shannon’s entropy represents a multivariate function and all probability values are not equal to zero when considering graph entropies. Inspired by Dehmer and Kraus [23], it turned out that determining minimal values of graph entropies is intricate because there is a lack of analytical methods to tackle this particular problem. Other related work is due to Shi [24], who proved a lower bound of quantum decision tree complexity by using Shannon’s entropy. Dragomir and Goh [25] obtained several general upper bounds for Shannon’s entropy by using Jensen’s inequality. Finally, Dehmer and Kraus [23] proved some extremal results for graph entropies, which are based on information functionals.

The main contribution of the paper is to study novel properties of graph entropies, which are based on an information functional by using the number of vertices with distance k to a given vertex. The paper is organized as follows. In Section 2, some concepts and notations in graph theory are introduced. In Section 3, we introduce the concept of graph entropies and some types of distance-based graph entropies. In Section 4, we state some properties of graph entropy. The paper finishes with a summary and conclusion in Section 5.

2. Preliminaries

A graph G is an ordered pair of sets V (G) and E(G) such that the elements uv ∈ E(G) are a sub-collection of the unordered pairs of elements of V (G). For convenience, we denote a graph by G = (V, E) sometimes. The elements of V (G) are called vertices and the elements of E(G) are called edges. If e = uv is an edge, then we say vertices u and v are adjacent, and u, v are two endpoints (or ends) of e. A loop is an edge whose two endpoints are the same. Two edges are called parallel, if both edges have the same endpoints. A simple graph is a graph containing no loops and parallel edges. If G is a graph with n vertices and m edges, then we say the order of G is n and the size of G is m. A graph of order n is addressed as an n-vertex graph, and a graph of order n and size m is addressed as an (n, m)-graph. A graph F is called a subgraph of a graph G, if V (F) ⊆ V (G) and E(F) ⊆ E(G), denoted by F ⊆ G. In this paper, we only consider simple graphs.

A graph is connected if, for every partition of its vertex set into two nonempty sets X and Y, there is an edge with one end in X and one end in Y. Otherwise, the graph is disconnected. In other words, a graph is disconnected if its vertex set can be partitioned into two nonempty subsets X and Y so that no edge has one end in X and one end in Y.

A path graph is a simple graph whose vertices can be arranged in a linear sequence in such a way that two vertices are adjacent if they are consecutive in the sequence, and are nonadjacent otherwise. Likewise, a cycle graph on three or more vertices is a simple graph whose vertices can be arranged in a cyclic sequence in such a way that two vertices are adjacent if they are consecutive in the sequence, and are nonadjacent otherwise. Denote by P_n and C_n the path graph and the cycle graph with n vertices, respectively.

A connected graph without any cycle is a tree. Actually, the path P_n is a tree of order n with exactly two pendent vertices. The star of order n, denoted by S_n, is the tree with n − 1 pendent vertices. A tree is called a double star S_p,q, if it is obtained from S_p+1 and S_q by identifying a leaf of S_p+1 with the center of S_q. So, for the double star S_p,q with n vertices, we have p + q = n. We call a double star S_p,q balanced, if $p=\lfloor \frac{n}{2}\rfloor$ and $q=\lceil \frac{n}{2}\rceil$. A comet is a tree composed of a star and a pendent path. For any numbers n and 2 ≤ t ≤ n−1, we denote by CS(n, t) the comet of order n with t pendent vertices, i.e., a tree formed by a path P_n−t of which one end vertex coincides with a pendent vertex of a star S_t+1 of order t + 1.

The length of a path is the number of its edges. For two vertices u and v, the distance between u and v in a graph G, denoted by d_G(u, v), is the length of the shortest path connecting u and v. A path P connecting u and v in G is called the geodesic path, if it is an induced path, i.e., the distance between u and v in G is exactly the length of the path P. The diameter of a graph G is the greatest distance between two vertices of G, denoted by D(G). The set S_j(v_i, G) := {v ∈ V |d(v_i, v) = j, j ≥ 1} is called the j-sphere of v_i regarding G.

All vertices adjacent to vertex u are called neighbors of u. The neighborhood of u is the set of the neighbors of u. The number of edges adjacent to vertex u is the degree of u, denoted by d(u). Vertices of degrees 0 and 1 are said to be isolated and pendent vertices, respectively. A pendent vertex is also referred to as a leaf of the underlying graph. A vertex of degree i is also addressed as an i-degree vertex. The minimum and maximum degree of G is denoted by δ(G) and Δ(G), respectively. If G has a_i vertices of degree d_i (i = 1, 2, . . . , t), where Δ(G) = d₁ > d₂ > ···> d_t = δ(G) and ${\displaystyle \sum _{i=1}^t}{a}_i=n$, we define the degree sequence of G as $D(G)=[d_1^{a_1},d_2^{a_2},\dots ,d_t^{a_t}]$. If a_i = 1, we use d_i instead of $d_i^{a_i}$ for convenience.

For terminology and notations not defined here, we refer the readers to [26].

3. Distance-Based Graph Entropies

Now we reproduce the definition of Shannon’s entropy [1].

Definition 1

Let p = (p₁, p₂, . . . , p_n) be a probability vector, namely, 0 ≤ p_i ≤ 1 and ${\sum }_{i=1}^n{p}_i=1$. The Shannon’s entropy of p is defined as

$$I(p)=-\sum _{i=1}^n{p}_i\hspace{0.17em}\text{log\hspace{0.17em}}{p}_i.$$

To define information-theoretic graph measures, we will often consider a tuple (λ₁, λ₂, . . . , λ_n) of non-negative integers λ_i ∈ ℕ [5]. This tuple forms a probability distribution p = (p₁, p₂, . . . , p_n), where

$$p_i=\frac{{\lambda }_i}{{\sum }_{j=1}^n{\lambda }_j}\mathrm{\hspace{0.17em} }\mathrm{\hspace{0.17em} }\mathrm{\hspace{0.17em} }i=1,2,\dots ,n.$$

Therefore, the entropy of tuple (λ₁, λ₂, . . . , λ_n) is given by

$$I({\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n)=-\sum _{i=1}^n{p}_i\hspace{0.17em}\text{log\hspace{0.17em}}{p}_i=\text{log\hspace{0.17em}}\left(\sum _{i=1}^n{\lambda }_i\right)-\sum _{i=1}^n\frac{{\lambda }_i}{{\sum }_{j=1}^n{\lambda }_j}\text{log\hspace{0.17em}}{\lambda }_i.$$

(1)

In the literature, there are various ways to obtain the tuple (λ₁, λ₂, . . . , λ_n), like the so-called magnitude-based information measures introduced by Bonchev and Trinajstić [27], or partition-independent graph entropies, introduced by Dehmer [5,28], which are based on information functionals.

We are now ready to define the entropy of a graph due to Dehmer [5] by using information functionals.

Definition 2

Let G = (V, E) be a connected graph. For a vertex v_i ∈ V, we define

$$p(v_i):=\frac{f(v_i)}{{\sum }_{j=1}^{\mid V\mid }f(v_j)},$$

where f represents an arbitrary information functional.

Observe that ${\sum }_{i=1}^{\mid V\mid }p(v_i)=1$. Hence, we can interpret the quantities p(v_i) as vertex probabilities. Now we immediately obtain one definition of graph entropy of graph G.

Definition 3

Let G = (V, E) be a connected graph and f be an arbitrary information functional. The entropy of G is defined as

$$\begin{array}{l}{I}_f(G)=-\sum _{i=1}^{\mid V\mid }\frac{f(v_i)}{{\sum }_{j=1}^{\mid V\mid }f(v_j)}\text{log}\hspace{0.17em}\left(\frac{f(v_i)}{{\sum }_{j=1}^{\mid V\mid }f(v_j)}\right)\\ =\text{log}\hspace{0.17em}\left(\sum _{i=1}^{\mid V\mid }f(v_i)\right)-\sum _{i=1}^{\mid V\mid }\frac{f(v_i)}{{\sum }_{j=1}^{\mid V\mid }f(v_j)}\text{log}\hspace{0.17em}f(v_i).\end{array}$$

(2)

Distance is one of the most important graph invariants. We first restate some definitions of the information functionals based on distances. In [5], the following information functional was introduced:

$$f(v_i)={\alpha }^{{\sum }_{j=1}^{D(G)}{c}_j\mid S_j(v_i,G)\mid },$$

where c_j with j = 1, 2, . . . , D(G) and α are arbitrary real positive parameters. The information functional proposed in [20] is calculated for a vertex v_i as the entropy of its shortest distances from all other vertices in the graph:

$$H(v_i)=-\sum _{u\in V}\frac{d(v_i,u)}{D(v_i)}\text{log}\frac{d(v_i,u)}{D(v_i)},$$

where D(v_i) = ∑_u∈V d(v_i, u). The aggregation function over all distances of vertices in the graph is proposed as follows:

$$H=\sum _{v\in V}H(v_i).$$

The information functional based on the shortest distances is introduced in [29]:

$$f(v_i)=\sum _{u\in V}d(v_i,u).$$

There are also some functionals based on the betweenness centralities [29,30].

In this paper, we consider a new information functional, which is the number of vertices with distance k to a given vertex. For a given vertex v in a graph, the number of vertices with distance one to v is exactly the degree of v. On the other hand, the number of pairs of vertices with distance three, which is also related to the clustering coefficient of networks, is also called the Wiener polarity index introduced for molecular networks by Wiener in 1947 [22]. For more recent results on Wiener index and Wiener polarity index, we refer to [31–41].

Let G = (V, E) be a connected graph with n vertices and v_i ∈ V (G). Denote by n_k(v_i) the number of vertices with distance k to v_i, i.e.,

$$n_k(v_i)=\hspace{0.17em}\mid S_k(v_i,G)\mid \hspace{0.17em}=\hspace{0.17em}\mid \{u:d(u,v_i)=k,\hspace{0.17em}u\in V(G)\}\mid ,$$

where k is an integer such that 1 ≤ k ≤ D(G).

Definition 4

Let G = (V, E) be a connected graph. For a vertex v_i ∈ V and 1 ≤ k ≤ D(G), we define the information functional as:

$$f(v_i):=n_k(v_i).$$

Therefore, by applying Definition 4 and Equality (2), we obtain the special graph entropy

$$\begin{array}{l}{I}_k(G):=I_f(G)=-\sum _{i=1}^n\frac{n_k(v_i)}{{\sum }_{j=1}^n{n}_k(v_j)}\text{log}\hspace{0.17em}\left(\frac{n_k(v_i)}{{\sum }_{j=1}^n{n}_k(v_j)}\right)\\ =\text{log\hspace{0.17em}}\left(\sum _{i=1}^n{n}_k(v_i)\right)-\frac{1}{{\sum }_{j=1}^n{n}_k(v_j)}·\sum _{i=1}^n{n}_k(v_i)\hspace{0.17em}\text{log\hspace{0.17em}}{n}_k(v_i).\end{array}$$

(3)

In this paper, we will discuss the extremal properties of the above graph entropy.

4. Results and Discussion

Observe that for k = 1, n₁(v_i) = d(v_i) is the degree of v_i and

$$I_1(G)=\text{log\hspace{0.17em}}\left(\sum _{i=1}^n{d}_i\right)-\frac{1}{{\sum }_{j=1}^n{d}_j}·\sum _{i=1}^n{d}_i\hspace{0.17em}\text{log}\hspace{0.17em}{d}_i,$$

which has been studied in [19] for some classes of graphs. If we denote the number of edges by m, then we have

$$I_1(G)=\text{log\hspace{0.17em}}(2m)-\frac{1}{2m}·\sum _{i=1}^n{d}_i\hspace{0.17em}\text{log\hspace{0.17em}}{d}_i,$$

(4)

since ${\sum }_{i=1}^n{d}_i=2m$. Denote by p_k(G) the number of geodesic paths with length k in graph G. Then we have ${\sum }_{i=1}^n{n}_k(v_i)=2p_k$, since each path of length k is counted twice in ${\sum }_{i=1}^n{n}_k(v_i)$

Therefore, Equation (3) can be represented as

$$I_k(G)=\text{log\hspace{0.17em}}(2p_k)-\frac{1}{2p_k}·\sum _{i=1}^n{n}_k(v_i)\hspace{0.17em}\text{log\hspace{0.17em}}{n}_k(v_i).$$

(5)

The number of paths with length k in a given graph is widely studied by Erdös and Bollobás; we refer the readers to [42–47]. Since there are some good algorithms for finding shortest paths in a graph, such as Dijkstra’s algorithm [26], we can obtain the following result.

Proposition 5

Let G be a graph with n vertices. For a given integer k, the value of I_k(G) can be computed in polynomial time.

Let T be a tree with n vertices and V (T) = {v₁, v₂, . . . , v_n}. In the following, we consider the properties of I_k(T) for k = 2.

First, we study the values of p₂(T) and n_k(v_i). Observe that

$$p_2(T)=\sum _{i=1}^n\left(\begin{array}{c}{d}_i\\ 2\end{array}\right)=\frac{1}{2}\sum _{i=1}^n{d}_i(d_i-1)=\frac{1}{2}\sum _{i=1}^n{d}_i^2-m=\frac{1}{2}\sum _{i=1}^n{d}_i^2-(n-1)$$

and

$$n_2(v_i)=\sum _{u\in N(v_i)}d(u).$$

Then from Equation (5), we have

$$I_2(T)=\text{log}\hspace{0.17em}\left(\sum _{i=1}^n{d}_i^2-2(n-1)\right)-\frac{{\displaystyle \sum _{i=1}^n}{n}_2(v_i)\hspace{0.17em}\text{log}\hspace{0.17em}{n}_2(v_i)}{{\displaystyle \sum _{i=1}^n}{d}_i^2-2(n-1)}.$$

(6)

If T ≅ S_n is a star graph, then we have

$$I_2(S_n)=\text{log}((n-2)(n-1))-\frac{(n-1)(n-2)\hspace{0.17em}\text{log}(n-2)}{(n-1)(n-2)}=\text{log}(n-1).$$

If T ≅ P_n is a path graph, then we have

$$I_2(P_n)=\text{log}(2(n-2))-\frac{(n-4)·2\hspace{0.17em}\text{log\hspace{0.17em}}2}{2(n-2)}=\text{log}(n-2)+\frac{2}{n-2}.$$

Let T be a tree with n vertices. By calculating the values I₂(T) for n = 7, 8, 9, 10, we can obtain the trees with extremal values of entropy. The trees with maximum and minimum values of I₂(T) are shown in Figures 1 and 2, respectively.

As we have seen from Figure 1, for n = 7, 8, 9, 10, the maximum value of I₂(T) is attained when T is the balanced double star $S_{\lfloor \frac{n}{2}\rfloor ,\lceil \frac{n}{2}\rceil }$. By some elementary calculations, we have

$$I_2\hspace{0.17em}\left(S_{\lfloor \frac{n}{2}\rfloor ,\lceil \frac{n}{2}\rceil }\right)=\{\begin{array}{ll}\text{log}(n)\hfill & \text{if\hspace{0.17em}}n=2k\hfill \\ \frac{3k-1}{2k}\text{log}(k)-\frac{k-1}{2k}\text{log}(k-1)+1\hfill & \text{if\hspace{0.17em}}n=2k+1.\hfill \end{array}$$

It is easy to obtain the following result.

Theorem 6

Let S_n, P_n, $S_{\lfloor \frac{n}{2}\rfloor ,\lceil \frac{n}{2}\rceil }$ be the star graph, the path graph and the balanced double star graph with n vertices, respectively. Then we have

$$I_2(S_n)<I_2(P_n)<I_2\hspace{0.17em}\left(S_{\lfloor \frac{n}{2}\rfloor ,\lceil \frac{n}{2}\rceil }\right).$$

Proof

First, we have

$$I_2(P_n)-I_2(S_n)=\text{log\hspace{0.17em}}\left(\frac{n-2}{n-1}\right)+\frac{2}{n-2}>0$$

for all n ≥ 3. For n = 2k,

$$I_2\hspace{0.17em}\left(S_{\lfloor \frac{n}{2}\rfloor ,\lceil \frac{n}{2}\rceil }\right)-I_2(P_n)=\text{log}(2k)-\text{log}(2k-2)-\frac{2}{2k-2}>0$$

for all k ≥ 1. The case of n = 2k + 1 is similar.

From Figure 2, for n = 7, 8, 9, 10, the minimum value of I₂(T) is attained when T is a comet. For a comet CS(n, t) with n − t ≥ 3, by some elementary calculations, we have

$$I_2(CS(n,t))=\text{log}(t^2-3t+2n-2)-\frac{2(n-t-3)+n_1\hspace{0.17em}\text{log}\hspace{0.17em}t+{(t-1)}^2\text{log}(t-1)}{t^2-3t+2n-2}.$$

Let

$$f(t)=\text{log}(t^2-3t+2n-2)-\frac{2(n-t-3)+n_1\hspace{0.17em}\text{log}\hspace{0.17em}t+{(t-1)}^2\text{log}(t-1)}{t^2-3t+2n-2}$$

and

$$g(t)=\frac{\partial f(t)}{\partial t}.$$

Denote by t₀ the root of g(t) = 0. Then CS(n, t₀) is the tree with the minimum value of entropy among all comets.

In fact, for a tree T with n vertices, we can guess the following result. However, this was neither successfully proved nor disproved despite many attempts.

Conjecture 7

For a tree T with n vertices, the balanced double star and the comet CS(n, t₀) can attain the maximum and the minimum values of I₂(T), respectively.

Observe that the extremal graphs for n = 10 is not unique. From this observation, we can obtain the following result.

Theorem 8

Let CS(n, t) be a comet with n − t ≥ 4. Denote by T a tree obtained from CS(n, t) by deleting the leaf that is not adjacent to the vertex of maximum degree and attaching a new vertex to one leaf that is adjacent to the vertex of maximum degree. Then we have I₂(T) = I₂(CS(n, t)).

Proof

Let CS(n, t) be a comet with n − t ≥ 4. Let w be the vertex with maximum degree t. Denote by u the leaf of CS(n, t) that is not adjacent to w, and v is one leaf that is adjacent to w. Let T = CS(n, t) − u + uv. Note that the degree sequence of T is the same as CS(n, t). Then we only need to check the part ${\displaystyle \sum _{i=1}^n}{n}_2(v_i)\hspace{0.17em}\text{log\hspace{0.17em}}{n}_2(v_i)$.

For a given graph G, we define a sequence

$$s(n_2,G)=(n_2(v_1),n_2(v_2),\dots ,n_2(v_n)).$$

By some elementary calculations, we can find that s(n₂, T) = s(n₂, CS(n, t)). Then from Equation (6), we obtain that I₂(T) = I₂(CS(n, t)).

Actually, the above proof provides a method to verify whether two graphs have the same value of entropy. If G and H are two graphs with the same vertex set and the same degree sequence, then we can use the defined sequence s(n₂, G) to check whether G and H have the same value of entropy.

5. Conclusions

Many distance-based entropies have been proposed and studied. In this paper, based on Shannon’s entropy, we study graph entropies related to a new information functional, which is the number of vertices with distance k to a given vertex. One of the future works is to explore the discrimination power of this entropy.

Some properties of this entropy of graphs are characterized. Similar to other entropies [48], to determine the extremal values of I_k(G) and characterize the extremal graphs is a challenging problem. It seems also much complicated for trees. One possible attempt is to establish some graph transformations, which can increase or decrease the values of the entropy.