Open AccessArticle

Some New Properties for Degree-Based Graph Entropies

Guoxiang Lu

^1,2,3,*,

Bingqing Li

² and

Lijia Wang

School of Economics, Nankai University, No. 94 Weijin Road, Tianjin 300071, China

School of Finance, Nankai University, No. 94 Weijin Road, Tianjin 300071, China

School of Statistics and Mathematics, Zhongnan University of Economics and Law, No. 182 Nanhu Avenue, Wuhan 430073, China

Author to whom correspondence should be addressed.

Entropy 2015, 17(12), 8217-8227; https://doi.org/10.3390/e17127871

Submission received: 21 October 2015 / Revised: 4 December 2015 / Accepted: 10 December 2015 / Published: 16 December 2015

(This article belongs to the Section Complexity)

Download

Browse Figure

Versions Notes

Abstract

The graph entropies inspired by Shannon’s entropy concept become the information-theoretic quantities for measuring the structural information of graphs and complex networks. In this paper, we continue studying some new properties of the graph entropies based on information functionals involving vertex degrees. We prove the monotonicity of the graph entropies with respect to the power exponent. Considering only the maximum and minimum degrees of the

(n, m)

-graph, we obtain some upper and lower bounds for the degree-based graph entropy. These bounds have different performances to restrict the degree-based graph entropy in different kinds of graphs. Moreover the degree-based graph entropy can be estimated by these bounds.

Keywords:

Shannon’s entropy; graph entropy; degree powers; monotonicity; entropy bounds

1. Introduction

The entropy of a probability distribution is known as a measure of the unpredictability of information content or a measure of the uncertainty of a system. This concept was introduced first from Shannon’s famous paper [1]. Later, entropy was initiated to be applied to graphs. It was developed for measuring the structural information of graphs and networks [2]. In that paper, Rashevsky proposed the concept of graph entropy based on the classifications of vertex orbits. Recently, graph entropies have been widely applied in many different fields, such as chemistry, biology, ecology and sociology [3,4,5,6,7].

There are several different types of such graph entropy measures [8]. For example, the graph entropy measures that associate probability distributions with elements (vertices, edges, etc.) of a graph can be classified as intrinsic and extrinsic measures. For intrinsic graph entropy measures, the probability distribution is induced by some structural feature of the graph. For extrinsic graph entropy measures, the probability distribution is assigned arbitrarily to elements of the graph. Most of the classical graph entropies are intrinsic. Dehmer introduced graph entropies based on information functionals, which capture structural information, and studied their properties [9,10,11]. The degree powers are extremely significant invariants and studied extensively in graph theory and network science, and they are used as the information functionals to explore the networks [12,13]. For more expansive research, Estrada and co-authors proposed a physically-sound entropy measure for networks/graphs [14] and studied the walk-based graph entropies [15,16,17]. There is am especially close relationship between the graph entropies based on length-two cycles and the graph entropies based on the degree powers for exponent

k = 1

. We focus on the degree powers and the graph entropies based on the degrees. Therefore, we continue studying them under certain conditions.

The structure of this paper is as follows: In Section 2, some definitions and notations of graph theory and the graph entropies we are going to study are reviewed. In Section 3, the monotonicity of the graph entropies with respect to the power exponent is discussed. In Section 4, we give four upper bounds and three lower bounds of the graph entropies based on the degrees under certain conditions. In Section 5, numerical results are presented to demonstrate graph entropies. Finally, a short summary and conclusion are drawn in the last section.

2. Preliminaries to Degree-Based Graph Entropies

A graph

G = (V, E)

is an ordered pair of sets V and E, where the set V of elements named vertices or nodes is a nonempty finite set, and the set E is composed of two-element subsets

u v

of V named edges. If

e = u v

is an edge, then u and v are called adjacent to each other, and v is a neighbor of u. The order of G is defined as the number of vertices in the graph G. Additionally, the size of G is defined as the number of edges in the graph G. An

(n, m)

-graph is defined as a graph of order n and size m. If any two vertices are connected by at most one edge in a graph, then the graph is called a simple graph. A path is a finite sequence of edges that connect a sequence of vertices, such that all edges and vertices are distinct from one another. A cycle is a finite sequence of edges that connect a sequence of vertices starting and ending at the same vertex. A graph is connected if there exists at least one path between every pair of vertices. Correspondingly, a graph is disconnected if it is not connected. A tree is a connected graph without any cycle. It is easy to see that a tree is an

(n, n - 1)

-graph. A bipartite graph is a graph G whose vertices can be divided into two disjoint sets, such that every edge connects a vertex in one set to a vertex in another set. The two disjoint sets are called partite sets. Additionally, a bipartite graph can be denoted by

n_{1} \times n_{2}

if the orders of the partite sets are

n_{1}

and

n_{2}

, respectively.

The set of neighbors of a vertex u is called its neighborhood

N (u)

. The number of edges adjacent to the vertex u is the degree of u, which is denoted by

d (u)

or in short

d_{u}

. If each vertex has the same degree in G, then G is a regular graph or is d-regular with vertices of degree d. The maximum and minimum degrees are often denoted by

Δ (G)

and

δ (G)

. If

V = {v_{1}, v_{2}, \dots, v_{n}}

, then

D (G) = {d_{1}, d_{2}, \dots, d_{n}}

is a degree sequence of G. Without loss of generality, we order the vertices, such that the degree sequence is monotone decreasing, for example

Δ (G) = d_{1} \geq d_{2} \geq \dots \geq d_{n} = δ (G)

. To a given graph G, the vertex degree is an important graph invariant, which is related to the structural properties of the graph. In the following, we discuss a

(n, m)

-graph with given n and m. The sum of degree powers is defined by:

D (k) : = \sum_{i = 1}^{n} {d_{i}}^{k}

(1)

where k is an arbitrary real number. Obviously, when

k = 1

D (1) = \sum_{i = 1}^{n} d_{i} = 2 m

presents the sum of degrees. Observing

D (1) = T r (L)

where

L = D - A

is the graph Laplacian associated with G and

T r (L)

is equal to the sum of the eigenvalues of L, as well, we can see that there exists a connection between the degree-based graph entropies and spectral-based graph entropies. The sum of degree powers as an invariant is called the zeroth order general Randić index [18,19,20]. Chen et al. [21] have reviewed it for different values of k and the relationships with some indices, such as the Zagreb index, graph energies, the HOMO-LUMO index and the Estrada index [22,23,24,25,26,27,28,29,30,31,32].

Next, we introduce the definition of Shannon’s entropy in information theory [33]. The logarithms in this paper are base two logarithms.

Definition 1. Let

P = (p_{1}, p_{2}, \dots, p_{n})

be a probability distribution of discrete random variable X, such that

0 \leq p_{i} \leq 1

and

\sum_{i = 1}^{n} p_{i} = 1

. Shannon’s entropy of the probability distribution P (of discrete random variable X) is defined by:

H (P) = - \sum_{i = 1}^{n} p_{i} log p_{i}

(2)

Definition 2. Let

G = (V, E)

be a connected graph. For any

v_{i} \in V

, we define:

p (v_{i}) = \frac{f (v_{i})}{\sum_{j = 1}^{n} f (v_{j})}

(3)

where f is a meaningful information functional. According to the information functional f, the vertices are mapped to the non-negative real numbers.

Owing to

\sum_{i = 1}^{n} p (v_{i}) = 1

, the quantities

p (v_{i})

can be seen as probability values. Then, the graph entropy of G has been defined as follows [9].

Definition 3. Let

G = (V, E)

be a connected graph and f be a meaningful information functional. The (Shannon’s) graph entropy of G is defined by:

I_{f} (G) = - \sum_{i = 1}^{n} \frac{f (v_{i})}{\sum_{j = 1}^{n} f (v_{j})} log \frac{f (v_{i})}{\sum_{j = 1}^{n} f (v_{j})}

(4)

In [10], Dehmer and co-authors presented the parametric information functionals by using the diameter of graph G and the j-sphere of the vertices. In [11], they set other information functionals by using the spectrum of graph G. Because the degrees of the graph G can be seen as one species of the most noticeable invariants and they can be calculated very easily in large-scale networks, we focus on the information functionals by using the degree powers and the graph entropies based on the degrees. In [12,13], the graph entropy of G based on the degree powers’ information functional is defined by:

I_{f} (G, k) = - \sum_{i = 1}^{n} \frac{{d_{i}}^{k}}{\sum_{j = 1}^{n} {d_{j}}^{k}} log \frac{{d_{i}}^{k}}{\sum_{j = 1}^{n} {d_{j}}^{k}}

(5)

For simplicity, we write the entropy of graph

I_{f} (G, 1)

I_{f}^{1} (G)

3. Monotonicity of $I_{f} (G, k)$ with Respect to the Parameter k

In [13], the authors have proven the theorem:

Theorem 1. If G is a connected graph with vertices of degree d (d-regular graph), then

I_{f} (G, k) = log n

for any k.

In this section, we obtain the monotonicity of

I_{f} (G, k)

with respect to the parameter k when G is an ordinary graph.

Theorem 2. If G is a connected graph where each vertex does not have the same degree (not a d-regular graph), then for

k > 0

I_{f} (G, k)

is monotonically decreasing with respect to k; for

k < 0

I_{f} (G, k)

is monotonically increasing with respect to k.

Proof. We have ordered the vertices such that the degree sequence obtained is monotone decreasing

Δ (G) = d_{1} \geq d_{2} \geq \dots \geq d_{n} = δ (G)

and

d_{u} > d_{v}

for some

u, v

. The derivative of the function

I_{f} (G, k)

with respect to k is:

\begin{matrix} \frac{d}{d k} (I_{f} (G, k)) = & - \frac{d}{d k} (\sum_{i = 1}^{n} \frac{{d_{i}}^{k}}{\sum_{j = 1}^{n} {d_{j}}^{k}} log \frac{{d_{i}}^{k}}{\sum_{j = 1}^{n} {d_{j}}^{k}}) \\ = & - \frac{1}{ln 2} \cdot \frac{d}{d k} (\sum_{i = 1}^{n} \frac{{d_{i}}^{k}}{\sum_{j = 1}^{n} {d_{j}}^{k}} ln \frac{{d_{i}}^{k}}{\sum_{j = 1}^{n} {d_{j}}^{k}}) \\ = & - \frac{1}{ln 2} \cdot \sum_{i = 1}^{n} [\frac{{d_{i}}^{k} ln d_{i} ln (\frac{{d_{i}}^{k}}{D (k)})}{\sum_{j = 1}^{n} {d_{j}}^{k}} - \frac{{d_{i}}^{k} ln (\frac{{d_{i}}^{k}}{D (k)}) (\sum_{j = 1}^{n} {d_{j}}^{k} ln d_{j})}{{(\sum_{j = 1}^{n} {d_{j}}^{k})}^{2}}] \\ = & - \frac{1}{ln 2 {(D (k))}^{2}} \cdot [(\sum_{i = 1}^{n} {d_{i}}^{k} ln d_{i} ln (\frac{{d_{i}}^{k}}{D (k)})) (\sum_{j = 1}^{n} {d_{j}}^{k}) \\ - (\sum_{i = 1}^{n} {d_{i}}^{k} ln (\frac{{d_{i}}^{k}}{D (k)})) (\sum_{j = 1}^{n} {d_{j}}^{k} ln d_{j})] \\ = & - \frac{1}{ln 2 {(D (k))}^{2}} \cdot \sum_{i = 1}^{n} \sum_{j = 1}^{n} [{d_{i}}^{k} {d_{j}}^{k} ln d_{i} ln (\frac{{d_{i}}^{k}}{D (k)}) - {d_{i}}^{k} {d_{j}}^{k} ln d_{j} ln (\frac{{d_{i}}^{k}}{D (k)})] \\ = & - \frac{1}{ln 2 {(D (k))}^{2}} \cdot \sum_{1 \leq i < j \leq n} {d_{i}}^{k} {d_{j}}^{k} (ln d_{i} - ln d_{j}) [ln (\frac{{d_{i}}^{k}}{D (k)}) - ln (\frac{{d_{j}}^{k}}{D (k)})] \end{matrix}

Obviously

D (k) > 0

. When

i < j

, we have

ln d_{i} \geq ln d_{j}

. Additionally, if

k > 0

, then

{d_{i}}^{k} \geq {d_{j}}^{k}

; if

k < 0

, then

{d_{i}}^{k} \leq {d_{j}}^{k}

. Moreover, for some

u, v

{d_{u}}^{k} {d_{v}}^{k} (ln d_{u} - ln d_{v}) [ln (\frac{{d_{u}}^{k}}{D (k)}) - ln (\frac{{d_{v}}^{k}}{D (k)})] \neq 0

These results show that if

k > 0

\frac{d}{d k} (I_{f} (G, k)) < 0

; if

k < 0

\frac{d}{d k} (I_{f} (G, k)) > 0

. Thus, we complete the proof. ☐

4. Some New Bounds for $I_{f}^{1} (G)$

In this section, we prove some new bounds for the degree-based graph entropy

I_{f}^{1} (G)

(n, m)

-graph

G (n, m)

Lemma 1. Let

G (n, m)

be an

(n, m)

-graph. The symbols Δ and δ denote the maximum degree and the minimum degree of

G (n, m)

, respectively. Then, the inequalities hold:

log (D (k)) - k log Δ \leq I_{f} (G, k) \leq log (D (k)) - k log δ

The above Lemma 1 is Theorem 1 in [13]. Especially,

D (1) = 2 m

(n, m)

-graph

G (n, m)

. Therefore, we have the following.

Theorem 3. Let

G (n, m)

be an

(n, m)

-graph. The symbols Δ and δ denote the maximum degree and the minimum degree of

G (n, m)

, respectively. Then, the inequalities hold:

log (2 m) - log Δ \leq I_{f}^{1} (G) \leq log (2 m) - log δ

(6)

Theorem 4. Let

G (n, m)

be an

(n, m)

-graph. The symbols Δ and δ denote the maximum degree and the minimum degree of

G (n, m)

, respectively. If

n > 2

, then the inequality holds:

I_{f}^{1} (G) \leq \frac{2 m - δ - Δ}{2 m} log \frac{2 m (n - 2)}{2 m - δ - Δ} - \frac{δ}{2 m} log \frac{δ}{2 m} - \frac{Δ}{2 m} log \frac{Δ}{2 m}

(7)

Proof. For

Δ = d_{1} \geq d_{2} \geq \dots \geq d_{n} = δ

and

\sum_{i = 1}^{n} d_{i} = 2 m

, we have:

\begin{matrix} I_{f}^{1} (G) & = - \sum_{i = 1}^{n} \frac{d_{i}}{\sum_{j = 1}^{n} d_{j}} log \frac{d_{i}}{\sum_{j = 1}^{n} d_{j}} = - \sum_{i = 1}^{n} \frac{d_{i}}{2 m} log \frac{d_{i}}{2 m} \\ = - (\sum_{i = 2}^{n - 1} \frac{d_{i}}{2 m} log \frac{d_{i}}{2 m}) - \frac{δ}{2 m} log \frac{δ}{2 m} - \frac{Δ}{2 m} log \frac{Δ}{2 m} \end{matrix}

Observe that

\sum_{i = 2}^{n - 1} d_{i} = 2 m - δ - Δ

. Hence, we construct vector

q = (q_{1}, q_{2}, \dots, q_{n - 2})

where

q_{j} = d_{j + 1} /(2 m - δ - Δ), j = 1, 2, \dots, n - 2

. Then,

0 \leq q_{j} \leq 1

and

\sum_{j = 1}^{n - 2} q_{j} = \sum_{i = 2}^{n - 1} d_{i} /(2 m - δ - Δ) = 1

. The vector q is a probability vector, and Shannon’s entropy of q is:

\begin{matrix} H (q) = & - \sum_{j = 1}^{n - 2} q_{j} log q_{j} = - \sum_{i = 2}^{n - 1} \frac{d_{i}}{2 m - δ - Δ} log \frac{d_{i}}{2 m - δ - Δ} \\ = & - \sum_{i = 2}^{n - 1} \frac{d_{i}}{2 m - δ - Δ} (log \frac{d_{i}}{2 m} + log \frac{2 m}{2 m - δ - Δ}) \\ = & - \sum_{i = 2}^{n - 1} \frac{2 m}{2 m - δ - Δ} \cdot \frac{d_{i}}{2 m} log \frac{d_{i}}{2 m} \\ - \sum_{i = 2}^{n - 1} \frac{d_{i}}{2 m - δ - Δ} log \frac{2 m}{2 m - δ - Δ} \\ = & - \frac{2 m}{2 m - δ - Δ} (\sum_{i = 2}^{n - 1} \frac{d_{i}}{2 m} log \frac{d_{i}}{2 m}) - log \frac{2 m}{2 m - δ - Δ} \end{matrix}

In information theory, it is easy to obtain that

H (q) \leq log (n - 2)

with equality if and only if

q_{1} = q_{2} = \dots = q_{n - 2}

(see [33] Theorem 2.6.4). Then, we have:

\begin{matrix} - \sum_{i = 2}^{n - 1} \frac{d_{i}}{2 m} log \frac{d_{i}}{2 m} & = \frac{2 m - δ - Δ}{2 m} [H (q) + log \frac{2 m}{2 m - δ - Δ}] \\ \leq \frac{2 m - δ - Δ}{2 m} [log (n - 2) + log \frac{2 m}{2 m - δ - Δ}] \\ = \frac{2 m - δ - Δ}{2 m} log \frac{2 m (n - 2)}{2 m - δ - Δ} \end{matrix}

(8)

Take (8) into

I_{f}^{1} (G)

\begin{matrix} I_{f}^{1} (G) & = - (\sum_{i = 2}^{n - 1} \frac{d_{i}}{2 m} log \frac{d_{i}}{2 m}) - \frac{δ}{2 m} log \frac{δ}{2 m} - \frac{Δ}{2 m} log \frac{Δ}{2 m} \\ \leq \frac{2 m - δ - Δ}{2 m} log \frac{2 m (n - 2)}{2 m - δ - Δ} - \frac{δ}{2 m} log \frac{δ}{2 m} - \frac{Δ}{2 m} log \frac{Δ}{2 m} \end{matrix}

Additionally, the equality holds if and only if

d_{2} = d_{3} = \dots = d_{n - 1}

. Thus, we complete the proof. ☐

Lemma 2. Define

μ : = min_{1 \leq i \leq n} {p_{i}}

;

ν : = max_{1 \leq i \leq n} {p_{i}}

. Then:

\frac{1}{2 ln 2 \cdot n ν} \sum_{1 \leq i < j \leq n} {(p_{i} - p_{j})}^{2} \leq log n - H (p) \leq \frac{1}{2 ln 2 \cdot n μ} \sum_{1 \leq i < j \leq n} {(p_{i} - p_{j})}^{2}

(9)

The above Lemma 2 can be seen in [34], Theorem 5. Merely the change of base should be applied to the formula because the logarithms in [34] are base

e

logarithms.

Theorem 5. Let

G (n, m)

be an

(n, m)

-graph. The symbols Δ and δ denote the maximum degree and the minimum degree of

G (n, m)

, respectively. Then, the inequalities hold:

\begin{matrix} max \{log n - \frac{(2 m - n δ) (n Δ - 2 m)}{4 ln 2 \cdot δ m n}, 0\} \leq I_{f}^{1} (G) \\ \leq & log n - \frac{n (n - 2) (δ^{2} + Δ^{2}) + n {(2 m - δ - Δ)}^{2} - 4 m^{2} (n - 2)}{4 ln 2 \cdot Δ m n (n - 2)} \end{matrix}

(10)

Proof. Let

p_{i} = \frac{d_{i}}{2 m}

, then

μ = \frac{δ}{2 m}

ν = \frac{Δ}{2 m}

and

\sum_{i = 1}^{n} d_{i} = 2 m

. Firstly,

\begin{matrix} \sum_{1 \leq i < j \leq n} {(p_{i} - p_{j})}^{2} & = \sum_{1 \leq i < j \leq n} {(\frac{d_{i}}{2 m} - \frac{d_{j}}{2 m})}^{2} = \frac{1}{4 m^{2}} [n \sum_{i = 1}^{n} d_{i}^{2} - {(\sum_{i = 1}^{n} d_{i})}^{2}] \\ = \frac{1}{4 m^{2}} (n \sum_{i = 1}^{n} d_{i}^{2} - 4 m^{2}) \end{matrix}

(11)

holds. We observe that:

\begin{matrix} 0 & \leq \sum_{i = 1}^{n} (d_{i} - δ) (Δ - d_{i}) = (δ + Δ) \sum_{i = 1}^{n} d_{i} - n δ Δ - \sum_{i = 1}^{n} d_{i}^{2} \\ = 2 m (δ + Δ) - n δ Δ - \sum_{i = 1}^{n} d_{i}^{2} \end{matrix}

This leads to:

\begin{matrix} n \sum_{i = 1}^{n} d_{i}^{2} - 4 m^{2} & \leq n [2 m (δ + Δ) - n δ Δ] - 4 m^{2} \\ = (2 m - n δ) (n Δ - 2 m) . \end{matrix}

(12)

Taking (11) and (12) into Lemma 2, we deduce the inequality:

\begin{matrix} log n - I_{f}^{1} (G) \leq \frac{(2 m - n δ) (n Δ - 2 m)}{4 ln 2 \cdot δ m n} \end{matrix}

(13)

On the other hand,

\begin{matrix} \sum_{i = 1}^{n} d_{i}^{2} & = δ^{2} + Δ^{2} + \sum_{i = 2}^{n - 1} d_{i}^{2} \\ \geq δ^{2} + Δ^{2} + \frac{1}{n - 2} {(\sum_{i = 2}^{n - 1} d_{i})}^{2} \\ = δ^{2} + Δ^{2} + \frac{{(2 m - δ - Δ)}^{2}}{n - 2} \end{matrix}

(14)

The inequality is obtained by using Chebyshev’s sum inequality. This leads to:

\begin{matrix} n \sum_{i = 1}^{n} d_{i}^{2} - 4 m^{2} & \geq n [δ^{2} + Δ^{2} + \frac{{(2 m - δ - Δ)}^{2}}{n - 2}] - 4 m^{2} \\ = \frac{n (n - 2) (δ^{2} + Δ^{2}) + n {(2 m - δ - Δ)}^{2} - 4 m^{2} (n - 2)}{n - 2} \end{matrix}

(15)

Taking (11) and (15) into Lemma 2, we deduce the inequality:

\begin{matrix} log n - I_{f}^{1} (G) \geq log n - \frac{n (n - 2) (δ^{2} + Δ^{2}) + n {(2 m - δ - Δ)}^{2} - 4 m^{2} (n - 2)}{4 ln 2 \cdot Δ m n (n - 2)} \end{matrix}

(16)

Using (13) and (16), the validity of the inequalities (10) can be obtained. ☐

Lemma 3. Define

μ : = min_{1 \leq i \leq n} {p_{i}}

;

ν : = max_{1 \leq i \leq n} {p_{i}}

. Then:

ψ (μ, ν) \leq log n - H (p) \leq min {Ψ (μ, ν), n \cdot ψ (μ, ν)}

(17)

where

ψ (μ, ν) : = μ log (\frac{2 μ}{μ + ν}) + ν log (\frac{2 ν}{μ + ν})

Ψ (μ, ν) : = log (\frac{{(μ + ν)}^{2}}{4 μ ν})

The above Lemma 3 is proven in [35], Proposition 3.

Theorem 6. Let

G (n, m)

be an

(n, m)

-graph. The symbols Δ and δ denote the maximum degree and the minimum degree of

G (n, m)

, respectively. Then, the inequalities hold:

log n - min {Ψ (δ, Δ), n \cdot ψ (δ, Δ)} \leq I_{f}^{1} (G) \leq log n - ψ (δ, Δ)

(18)

where

ψ (δ, Δ) : = \frac{1}{2 m} [δ log (\frac{2 δ}{δ + Δ}) + Δ log (\frac{2 Δ}{δ + Δ})]

Ψ (δ, Δ) : = log (\frac{{(δ + Δ)}^{2}}{4 δ Δ})

Proof. Let

μ = δ /(2 m)

and

ν = Δ /(2 m)

in (17). Then, inequality (18) is obtained. ☐

Overall, we obtain four upper bounds:

\begin{matrix} U_{0} & : = log (2 m) - log δ \\ U_{1} & : = \frac{2 m - δ - Δ}{2 m} log \frac{2 m (n - 2)}{2 m - δ - Δ} - \frac{δ}{2 m} log \frac{δ}{2 m} - \frac{Δ}{2 m} log \frac{Δ}{2 m} \\ U_{2} & : = log n - \frac{n (n - 2) (δ^{2} + Δ^{2}) + n {(2 m - δ - Δ)}^{2} - 4 m^{2} (n - 2)}{4 ln 2 \cdot Δ m n (n - 2)} \\ U_{3} & : = log n - ψ (δ, Δ) \end{matrix}

and three new lower bounds:

\begin{matrix} L_{0} & : = log (2 m) - log Δ \\ L_{1} & : = max \{log n - \frac{(2 m - n δ) (n Δ - 2 m)}{4 ln 2 \cdot δ m n}, 0\} \\ L_{2} & : = log n - min {Ψ (δ, Δ), n \cdot ψ (δ, Δ)} \end{matrix}

5. Numerical Results

In this section, we compute the values of the degree-based graph entropy

I_{f}^{1} (G)

and the bounds obtained above for some special

(n, m)

-graphs.

5.1. Path Graph

Let

P_{n}

be a path graph with exactly two pendant vertices and

n - 2

internal vertices. Therefore, in

P_{n}

two pendant vertices have degree one, while all others (if any) have degree two. Additionally,

m = n - 1

Δ = 2

δ = 1

By calculating the graph entropy of a series of path graphs, we show some values of the degree-based graph entropy and bounds in the following Table 1.

Table 1. The values of the degree-based graph entropy and bounds for

P_{n}

**Table 1.** The values of the degree-based graph entropy and bounds for $P_{n}$ .
n	4	5	6	7	10	20	30	40	50	100
$I_{f}^{1} (P_{n})$	1.918	2.250	2.522	2.752	3.281	4.301	4.892	5.311	5.635	6.639
$U_{0}$	2.585	3.000	3.322	3.585	4.170	5.248	5.858	6.285	6.615	7.629
$L_{0}$	1.585	2.000	2.322	2.585	4.170	4.248	4.858	5.285	5.615	6.629
$U_{1}$	1.959	2.289	2.557	2.782	3.303	4.312	4.900	5.317	5.640	6.642
$L_{1}$	1.880	2.214	2.489	2.721	3.258	4.288	4.884	5.304	5.630	6.637
$U_{2}$	1.970	2.298	2.564	2.788	3.307	4.314	4.901	5.318	5.640	6.642
$L_{2}$	1.837	2.169	2.438	2.664	3.186	4.193	4.780	5.196	5.519	6.520
$U_{3}$	1.959	2.291	2.560	2.787	3.308	4.315	4.903	5.319	5.641	6.643

5.2. Star Graph

Let

S_{n}

be a star graph with one internal vertex and

n - 1

pendant vertices. It also can be seen as a complete bipartite graph

K_{1, n - 1}

. Therefore, in

S_{n}

, one internal vertex has degree

n - 1

, while all others (if any) have degree 1. Additionally,

m = n - 1

Δ = n - 1

δ = 1

By calculating the graph entropy of a series of star graphs, we show some values of the degree-based graph entropy and bounds in the following Table 2.

Table 2. The values of the degree-based graph entropy and bounds for

S_{n}

**Table 2.** The values of the degree-based graph entropy and bounds for $S_{n}$ .
n	4	5	6	7	10	20	30	40	50	100
$I_{f}^{1} (S_{n})$	1.792	2.000	2.161	2.292	2.585	3.124	3.429	3.643	3.807	4.315
$U_{0}$	2.585	3.000	3.322	3.585	4.170	5.248	5.858	6.285	6.615	7.629
$L_{0}$	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000
$U_{1}$	1.792	2.000	2.161	2.292	2.585	3.124	3.429	3.643	3.807	4.315
$L_{1}$	1.639	1.673	1.623	1.519	1.104	0.000	0.000	0.000	0.000	0.000
$U_{2}$	1.880	2.160	2.393	2.593	3.065	4.014	4.582	4.988	5.305	6.294
$L_{2}$	1.585	1.678	1.737	1.778	1.848	1.926	1.951	1.963	1.971	1.986
$U_{3}$	1.880	2.160	2.393	2.593	3.065	4.014	4.582	4.988	5.305	6.294

5.3. Monocentric Homogeneous Dendrimer Graph

Let the monocentric dendrimer be a special tree, which is controlled by two parameters t and r. The parameter t denotes the progressive level, and the parameter r denotes the radius of the tree. The degrees of all internal vertices are equal to

t + 1

. As there exists one central vertex in a monocentric dendrimer, the maximum distance from one pendant vertex to the central vertex is referred to as the radius. If the distances from the central vertex to all pendant vertices are equal to r, then we call the tree a monocentric homogeneous dendrimer. For more details, please see [36,37]. Figure 1 is an example of a monocentric homogeneous dendrimer with three as the value of t and s, respectively.

Figure 1. A monocentric homogeneous dendrimer with

t = 3

and

r = 3

Figure 1. A monocentric homogeneous dendrimer with

t = 3

and

r = 3

For parameters t and r, we have the order

n = 1 + \frac{(t + 1) (t^{r} - 1)}{t - 1}

, and

m = n - 1

Δ = t + 1

δ = 1

. Let

t = 3

; we change the value of parameter r to compute the degree-based graph entropy and bounds. The results are listed in Table 3.

Table 3. The values of the degree-based graph entropy and bounds for monocentric homogeneous dendrimer

D (3, r)

**Table 3.** The values of the degree-based graph entropy and bounds for monocentric homogeneous dendrimer $D (3, r)$ .
r	1	2	3	4	5	6	7	8	9	10
$I_{f}^{1} (D (3, r))$	2.000	3.750	5.393	6.997	8.588	10.175	11.761	13.346	14.931	16.516
$U_{0}$	3.000	5.000	6.700	8.322	9.919	11.508	13.094	14.680	16.265	17.850
$L_{0}$	1.000	3.000	4.700	6.322	7.919	9.508	11.094	12.680	14.265	15.850
$U_{1}$	2.000	4.035	5.713	7.326	8.920	10.508	12.094	13.680	15.265	16.850
$L_{1}$	1.673	3.371	5.007	6.610	8.201	9.787	11.373	12.958	14.543	16.128
$U_{2}$	2.160	4.057	5.719	7.328	8.921	10.509	12.094	13.680	15.265	16.850
$L_{2}$	1.678	3.444	5.084	6.687	8.278	9.865	11.451	13.036	14.621	16.206
$U_{3}$	2.148	4.044	5.715	7.327	8.920	10.508	12.094	13.680	15.265	16.850

5.4. Complete Bipartite Graph $K_{s, 2 s}$

Let

K_{n_{1}, n_{2}}

be a complete bipartite graph. In other words,

K_{n_{1}, n_{2}}

is an

n_{1} \times n_{2}

bipartite graph, where every vertex of one partite set is connected to every vertex of the other partite set. For a special class of complete bipartite graphs

K_{s, 2 s}

, we have the order

n = 3 s

, and

m = 2 s^{2}

Δ = 2 s

δ = s

By calculating the graph entropy of the special class of complete bipartite graphs

K_{s, 2 s}

, we show some values of the degree-based graph entropy and bounds in the following Table 4.

Table 4. The values of the degree-based graph entropy and bounds for

K_{s, 2 s}

**Table 4.** The values of the degree-based graph entropy and bounds for $K_{s, 2 s}$ .
n	4	5	6	7	10	20	30	40	50	100
$I_{f}^{1} (K_{s, 2 s})$	3.500	3.822	4.085	4.307	4.822	5.822	6.407	6.822	7.144	8.144
$U_{0}$	4.000	4.322	4.585	4.807	5.322	6.322	6.907	7.322	7.644	8.644
$L_{0}$	3.000	3.322	3.585	3.807	4.322	5.322	5.907	6.322	6.644	7.644
$U_{1}$	3.567	3.893	4.158	4.382	4.900	5.903	6.490	6.905	7.227	8.228
$L_{1}$	3.465	3.787	4.050	4.272	4.787	5.787	6.372	6.787	7.109	8.109
$U_{2}$	3.572	3.897	4.161	4.385	4.902	5.904	6.490	6.906	7.228	8.228
$L_{2}$	3.415	3.737	4.000	4.222	4.737	5.737	6.322	6.737	7.059	8.059
$U_{3}$	3.570	3.895	4.160	4.384	4.901	5.904	6.490	6.905	7.228	8.228

Observe the four tables above, and we summarize the findings as follows:

The value of degree-based entropy $I_{f}^{1} (G)$ corresponds to the scale of the graph. The larger the order and size are, the bigger the degree-based entropy is. This means that the corresponding graph is more complex in the structure information.
To the graph $P_{n}$ and $S_{n}$ of the same order and size, $I_{f}^{1} (P_{n}) \geq I_{f}^{1} (S_{n})$ . This means that if $P_{n}$ and $S_{n}$ have the same scale, $P_{n}$ is more complex in the structure information.
The upper bound $U_{1}$ is the closest to $I_{f}^{1} (G)$ or better than $U_{0}, U_{2}, U_{3}$ , and the lower bound $L_{2}$ is the closest to $I_{f}^{1} (G)$ or better than $L_{0}, L_{2}$ . The upper bound $U_{0}$ is the farthest from $I_{f}^{1} (G)$ or worse than $U_{1}, U_{2}, U_{3}$ . The closeness of $I_{f}^{1} (G)$ and other upper bounds $U_{1}, U_{2}$ or lower bound $L_{0}, L_{1}$ is uncertain.
In Table 2, when the size n is big enough and continues to increase, the value of $L_{0}$ is always one, and the value of $L_{1}$ approaches zero. This means that these lower bounds are not ideal. However, in other tables, all bounds correspond to the scale of the graph. Therefore, we infer that the bounds are closely related to the structure information of the graph. The more complex a graph of the same order and size is in the structure information, the better the bounds are.

6. Summary and Conclusions

In this paper, we studied the properties for degree-based graph entropies. We discussed the degree powers’ information functional and obtained the monotonicity of the graph entropy

I_{f} (G, k)

with respect to the parameter k. Specifically, for the degree-based graph entropy

I_{f}^{1} (G)

, we introduced some new bounds, which can estimate

I_{f}^{1} (G)

by only using the order n, the size m and the maximum and minimum degrees of a given graph G. The numerical results for special graphs show that the new bounds have different effects to restrict

I_{f}^{1} (G)

. The monotonicity and bounds might prove useful in further structure information investigation of graphs and real networks, such as estimating the complexity and analyzing the aggregation or homogeneity.

Acknowledgments

The authors would like to thank the editor and referees for their helpful suggestions and comments on the manuscript. This manuscript is supported by the China Postdoctoral Science Foundation (2015M571255), the National Science Foundation of China (the NSF of China) Grant No. 71171119, the Fundamental Research Funds for the Central Universities (FRF-CU) Grant No. 2722013JC082 and the Fundamental Research Funds for the Central Universities under Grant Number NKZXTD1403.

Author Contributions

Guoxiang Lu, Bingqing Li, and Lijia Wang did the analysis; Guoxiang Lu, Bingqing Li, and Lijia Wang wrote the paper. All authors have read and approved the final manuscript.

Conflicts of Interest

The authors declare no conflict of interest.

References

Shannon, C.E. A mathematical theory of communication. Bell Syst. Tech. J. 1948, 27, 379–423, 623–656. [Google Scholar] [CrossRef]
Rashevsky, N. Life, information theory, and topology. Bull. Math. Biol. 1955, 17, 229–235. [Google Scholar] [CrossRef]
Mehler, A.; Lücking, A.; Weiß, P. A network model of interpersonal alignment. Entropy 2010, 12, 1440–1483. [Google Scholar] [CrossRef]
Solé, R.V.; Montoya, J.M. Complexity and fragility in ecological networks. Proc. R. Soc. Lond. B Biol. Sci. 2001, 268, 2039–2045. [Google Scholar] [CrossRef] [PubMed]
Ulanowicz, R.E. Quantitative methods for ecological network analysis. Comput. Biol. Chem. 2004, 28, 321–339. [Google Scholar] [CrossRef] [PubMed]
Dehmer, M.; Barbarini, N.; Varmuza, K.; Graber, A. Novel topological descriptors for analyzing biological networks. BMC Struct. Biol. 2010, 10. [Google Scholar] [CrossRef] [PubMed]
Dehmer, M.; Graber, M. The discrimination power of molecular identification numbers revisited. MATCH Commun. Math. Comput. Chem. 2013, 69, 785–794. [Google Scholar]
Mowshowitz, A.; Dehmer, M. Entropy and the complexity of graphs revisited. Entropy 2012, 14, 559–570. [Google Scholar] [CrossRef]
Dehmer, M. Information processing in complex networks: Graph entropy and information functionals. Appl. Math. Comput. 2008, 201, 82–94. [Google Scholar] [CrossRef]
Dehmer, M.; Varmuza, K.; Borgert, S.; Emmert-Streib, F. On entropy-based molecular descriptors: Statistical analysis of real and synthetic chemical structures. J. Chem. Inf. Model. 2009, 49, 1655–1663. [Google Scholar] [CrossRef] [PubMed]
Dehmer, M.; Sivakumar, L.; Varmuza, K. Uniquely discriminating molecular structures using novel eigenvalue-based descriptors. MATCH Commun. Math. Comput. Chem. 2012, 67, 147–172. [Google Scholar]
Cao, S.; Dehmer, M.; Shi, Y. Extremality of degree-based graph entropies. Inf. Sci. 2014, 278, 22–33. [Google Scholar] [CrossRef]
Cao, S.; Dehmer, M. Degree-based entropies of networks revisited. Appl. Math. Comput. 2015, 261, 141–147. [Google Scholar] [CrossRef]
Estrada, E.; Hatano, N. Statistical-mechanical approach to subgraph centrality in complex networks. Chem. Phys. Lett. 2007, 439, 247–251. [Google Scholar] [CrossRef]
Estrada, E. Generalized walks-based centrality measures for complex biological networks. J. Theor. Biol. 2010, 263, 556–565. [Google Scholar] [CrossRef] [PubMed]
Estrada, E.; de la Peña, J.A.; Hatano, N. Walk Entropies in Graphs. Linear Algebra Appl. 2014, 443, 235–244. [Google Scholar] [CrossRef] [Green Version]
Estrada, E.; de la Peña, J.A. Maximum walk entropy implies walk regularity. Linear Algebra Appl. 2014, 458, 542–547. [Google Scholar] [CrossRef]
Randić, M. Characterization of molecular branching. J. Am. Chem. Soc. 1975, 97, 6609–6615. [Google Scholar] [CrossRef]
Li, X.; Zheng, J. A unified approach to the extremal trees for different indices. MATCH Commun. Math. Comput. Chem. 2005, 54, 195–208. [Google Scholar]
Li, X.; Shi, Y. A survey on the Randić index. MATCH Commun. Math. Comput. Chem. 2008, 59, 127–156. [Google Scholar]
Chen, Z.; Dehmer, M.; Shi, Y. Bounds for degree-based network entropies. Appl. Math. Comput. 2015, 265, 983–993. [Google Scholar] [CrossRef]
Arezoomand, M.; Taeri, B. Zagreb indices of the generalized hierarchical product of graphs. MATCH Commun. Math. Comput. Chem. 2013, 69, 131–140. [Google Scholar]
Gutman, I. An exceptional property of first Zagreb index. MATCH Commun. Math. Comput. Chem. 2014, 72, 733–740. [Google Scholar]
Das, K.C.; Xu, K.; Gutman, I. On Zagreb and Harary indices. MATCH Commun. Math. Comput. Chem. 2013, 70, 301–314. [Google Scholar]
Abdo, H.; Dimitrov, D.; Réti, T.; Stevanović, D. Estimating the spectral radius of a graph by the second Zagreb index. MATCH Commun. Math. Comput. Chem. 2014, 72, 741–751. [Google Scholar]
Bozkurt, Ş.B.; Bozkurt, D. On incidence energy. MATCH Commun. Math. Comput. Chem. 2014, 72, 215–225. [Google Scholar]
Das, K.C.; Gutman, I.; Çevik, A.S.; Zhou, B. On Laplacian energy. MATCH Commun. Math. Comput. Chem. 2013, 70, 689–696. [Google Scholar]
Li, X.; Li, Y.; Shi, Y.; Gutman, I. Note on the HOMO-LUMO index of graphs. MATCH Commun. Math. Comput. Chem. 2013, 70, 85–96. [Google Scholar]
Estrada, E. Characterization of 3D molecular structure. Chem. Phys. Lett. 2000, 319, 713–718. [Google Scholar] [CrossRef]
Estrada, E.; Rodríguez-Velázquez, J.A. Subgraph centrality in complex networks. Phys. Rev. E 2005, 71, 056103. [Google Scholar] [CrossRef] [PubMed]
De la Peña, J.A.; Gutman, I.; Rada, J. Estimating the Estrada index. Linear Algebra Appl. 2007, 427, 70–76. [Google Scholar] [CrossRef]
Khosravanirad, A. A lower bound for Laplacian Estrada index of a graph. MATCH Commun. Math. Comput. Chem. 2013, 70, 175–180. [Google Scholar]
Cover, T.M.; Thomas, J.A. Elements of Information Theory, 2nd ed.; Wiley: Hoboken, NJ, USA, 2006. [Google Scholar]
Dragomir, S.S. An inequality for logarithmic mapping and applications for the shannon entropy. Comput. Math. Appl. 2003, 46, 1273–1279. [Google Scholar] [CrossRef]
Simic, S. Jensen’s inequality and new entropy bounds. Appl. Math. Lett. 2009, 22, 1262–1265. [Google Scholar] [CrossRef]
Chen, Z.; Dehmer, M.; Emmert-Streib, F.; Shi, Y. Entropy bounds for dendrimers. Appl. Math. Comput. 2014, 242, 462–472. [Google Scholar] [CrossRef]
Chen, Z.; Dehmer, M.; Emmert-Streib, F.; Shi, Y. Entropy of Weighted Graphs with Randić Weights. Entropy 2015, 17, 3710–3723. [Google Scholar] [CrossRef]

© 2015 by the authors; licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons by Attribution (CC-BY) license (http://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Lu, G.; Li, B.; Wang, L. Some New Properties for Degree-Based Graph Entropies. Entropy 2015, 17, 8217-8227. https://doi.org/10.3390/e17127871

AMA Style

Lu G, Li B, Wang L. Some New Properties for Degree-Based Graph Entropies. Entropy. 2015; 17(12):8217-8227. https://doi.org/10.3390/e17127871

Chicago/Turabian Style

Lu, Guoxiang, Bingqing Li, and Lijia Wang. 2015. "Some New Properties for Degree-Based Graph Entropies" Entropy 17, no. 12: 8217-8227. https://doi.org/10.3390/e17127871

APA Style

Lu, G., Li, B., & Wang, L. (2015). Some New Properties for Degree-Based Graph Entropies. Entropy, 17(12), 8217-8227. https://doi.org/10.3390/e17127871

Article Menu

Some New Properties for Degree-Based Graph Entropies

Abstract

1. Introduction

2. Preliminaries to Degree-Based Graph Entropies

3. Monotonicity of $I_{f} (G, k)$ with Respect to the Parameter k

4. Some New Bounds for $I_{f}^{1} (G)$

5. Numerical Results

5.1. Path Graph

5.2. Star Graph

5.3. Monocentric Homogeneous Dendrimer Graph

5.4. Complete Bipartite Graph $K_{s, 2 s}$

6. Summary and Conclusions

Acknowledgments

Author Contributions

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI

Article Menu

Some New Properties for Degree-Based Graph Entropies

Abstract

1. Introduction

2. Preliminaries to Degree-Based Graph Entropies

3. Monotonicity of I f ( G , k ) with Respect to the Parameter k

4. Some New Bounds for I f 1 ( G )

5. Numerical Results

5.1. Path Graph

5.2. Star Graph

5.3. Monocentric Homogeneous Dendrimer Graph

5.4. Complete Bipartite Graph K s , 2 s

6. Summary and Conclusions

Acknowledgments

Author Contributions

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI

3. Monotonicity of $I_{f} (G, k)$ with Respect to the Parameter k

4. Some New Bounds for $I_{f}^{1} (G)$

5.4. Complete Bipartite Graph $K_{s, 2 s}$