[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Next Article in Journal
Tail Risk Constraints and Maximum Entropy
Previous Article in Journal
The Switching Generator: New Clock-Controlled Generator with Resistance against the Algebraic and Side Channel Attacks
You seem to have javascript disabled. Please note that many of the page functionalities won't work as expected without javascript enabled.
 
 
Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
Journals
Entropy
Volume 17
Issue 6
10.3390/e17063710
entropy-logo
Submit to this Journal Review for this Journal Propose a Special Issue
► Article Menu

Article Menu

share Share announcement Help format_quote Cite question_answer Discuss in SciProfiles thumb_up
...
Endorse textsms
...
Comment
first_page
settings
Order Article Reprints
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

Entropy of Weighted Graphs with Randi´c Weights

by
Zengqiang Chen
1,
Matthias Dehmer
2,3,*,
Frank Emmert-Streib
4,5 and
Yongtang Shi
6,*
1
College of Computer and Control Engineering, Nankai University, Tianjin 300071, China
2
Department of Computer Science, Universität der Bundeswehr München, Werner-Heisenberg-Weg 39, 85577 Neubiberg, Germany
3
Department of Mechatronics and Biomedical Computer Science, UMIT, A-6060 Hall in Tyrol, Austria
4
Computational Medicine and Statistical Learning Laboratory, Department of Signal Processing, Tampere University of Technology, FI-33720 Tampere, Finland
5
Institute of Biosciences and Medical Technology, 33520 Tampere, Finland
6
Center for Combinatorics and LPMC-TJKLC, Nankai University, Tianjin 300071, China
*
Authors to whom correspondence should be addressed.
Entropy 2015, 17(6), 3710-3723; https://doi.org/10.3390/e17063710
Submission received: 18 May 2015 / Revised: 29 May 2015 / Accepted: 1 June 2015 / Published: 5 June 2015
Browse Figure

<p>The dendrimers with one center (left) and two centers (right), such that <span class="html-italic">t</span> =3 and <span class="html-italic">r</span> = 3.</p> ">
Versions Notes

Abstract

:
Shannon entropies for networks have been widely introduced. However, entropies for weighted graphs have been little investigated. Inspired by the work due to Eagle et al., we introduce the concept of graph entropy for special weighted graphs. Furthermore, we prove extremal properties by using elementary methods of classes of weighted graphs, and in particular, the one due to Bollobás and Erdös, which is also called the Randić weight. As a result, we derived statements on dendrimers that have been proven useful for applications. Finally, some open problems are presented.

1. Introduction

The study of entropy measures for exploring network-based systems emerged in the late fifties based on the seminal work due to Shannon [1]. Rashevsky is the first who introduced the so-called structural information content based on partitions of vertex orbits [2]. Mowshowitz used the the same measure and proved some properties for graph operations (sum, join, etc.) [3–6]. Moreover, Rashevsky used the concept of graph entropy to measure the structural complexity of graphs. Here, the complexity of a graph is based on the well-known Shannon’s entropy. Mowshowitz [3] introduced the entropy of a graph as an information-theoretic quantity, and he interpreted it as the structural information content of a graph. Mowshowitz [3] later studied mathematical properties of graph entropies measures thoroughly and also discussed special applications thereof. Graph entropy measures have been used in various disciplines, for example for characterizing graph patterns in biology, chemistry and computer science; see [7–14]. Thus, it is not surprising at all to realize that the term “graph entropy” has been defined in various ways. Another classical example is Körner’s entropy [15], introduced from an information theory-specific point of view.
Several graph invariants have been used for developing graph entropy measures, such as the number of vertices, the vertex degree sequences, extended degree sequences (i.e., the second neighbor, third neighbor, etc.), eigenvalues and connectivity information; see, [16–21]. Distance-based graph entropies [17,21] are also studied, which are related to the average distance and various Wiener indices [22–32]. The properties of graph entropies that are based on information functionals by using degree powers of graphs have been explored, too; see [13,33,34]. The degree power is one of the most important graph invariants and well studied in graph theory; its also related to the Zagreb index [35–41] and the zeroth-order Randić index [42–44]. To study results on the properties of degree powers and Randić indices in depth, we refer to [45,46].
In order to investigate the influence of the structure of social relations between individuals of a community’s economic development, Eagle et al. [47] developed two new metrics, social diversity and spatial diversity, to capture the social and spatial diversity of communication ties within a social network of each individual, by using the entropy for vertices. Following this, we introduce the concept of graph entropy for weighted graphs. We mention that Dehmer et al. [48] already tackled the problem of defining the entropy of weighted chemical graphs by using special information functionals. Therefore, this paper extends the work done in [48] considerably. Another contribution of this paper relates to the study of extremal values of weighted graphs. We examined the extremal properties of this entropy when using special graph classes. Here, we use the class of weighted graphs due to Bollobás and Erdös. Finally, some open problems are presented.

2. Preliminaries

In this paper, “log” denotes the logarithm based on two entirely.
In [47], the authors used the following node entropy. For a given graph G and vertex vi, let di be the degree of vi. For an edge vivj, one defines:
p i j = w ( v i v j ) ∑ j = 1 d i w ( v i v j ) ,
where w(vivj) is the weight (or volume) of the edge vivj and w(vivj) > 0. The node entropy has been defined by:
H ( v i ) = − ∑ j = 1 d i p i j log ( p i j ) .
Motivated by this method, we introduce the definition of the entropy of edge-weighted graphs, which also can be interpreted as multiple graphs. For an edge-weighted graph, G = (V, E, w), where V, E and w denote the vertex set, the edge set and the edge weight (sometimes, also called the cost) of G, respectively. In this paper, we always assume that the edge weight is positive.
Definition 1. For an edge weighted graph G = (V, E, w), the entropy of G is defined by:
I ( G , w ) = − ∑ u v ∈ E p u v log ( p u v ) ,
where p u v = w ( u v ) ∑ u v ∈ E w ( u v ).
The above definition of the entropy for edge-weighted graphs is based on the probability function (1), which is used in [47]. In this sense, Definition 1 is a general case of that used by Eagle et al. For any edge weight w, Theorem 1 provides the extremal values of I(G, w) for graphs with n vertices. However, if we want to go further to investigate the extremal values of I(G, w), then we need to specify an edge weight function rather than the general case. After careful consideration, we would like to choose the Randić weight, which is well studied; for more details, see Section 3.
In the following, we assume all to be edge weighted connected graphs. Let Kn, Pn and Sn be the complete graph, the path graph and the star graph with n vertices, respectively. A tree is called a subdivided star if it is obtained from a star by subdividing each edge of the star exactly once, and at most one edge is subdivided twice. The double star with n vertices, denoted by Sp,q, is the tree obtained by connecting two centers of two stars Sp and Sq, where p + q = n. The balanced complete bipartite graph is a complete bipartite graph, such that the numbers of vertices in the two parts are equal or have a difference of one. The balanced complete multipartite graph is a complete multipartite graph, such that the number of vertices in any two parts are equal or have a difference of one, which is also called the Turán graph.

3. Extremal Properties of I(G, w)

The trivial case is that w(e) = c > 0 for each edge e, where c is a constant.
Theorem 1. Let G = (V, E, w) be a graph with n vertices. If w(e) = c for each edge e, where c > 0 is a constant, then we obtain:
log ( n − 1 ) ≤ I ( G , w ) ≤ log ( n ( n − 1 ) 2 ) .
The left equality holds if and only if G is a tree, and the right equality holds if and only if G is the complete graph.
Proof. Suppose m = |E|. Since w(e) = c for each edge e, then we get:
I ( G , w ) = − ∑ e ∈ E 1 m log 1 m = ∑ e ∈ E log m m = log m .
Since G is connected, we have n − 1 ≤ m ≤ ( n 2 ) The result is proven
In 1975, the chemist, Milan Randić [49], proposed a topological index by describing its interpretation as the “branching index”. It has been proven useful for measuring the extent of branching of the carbon-atom skeleton of saturated hydrocarbons. This index is nowadays called the Randić index. Randić noticed that there is a good correlation between this index and several physico-chemical properties of alkanes; for instance boiling points, chromatographic retention times, enthalpies of formation, parameters of the Antoine equation for vapor pressure, surface areas, etc. Later, in 1998, two famous mathematicians, Bollobás and Erdös [50], generalized this index by replacing −1/2 by any real number α, which is called the general Randić index. In fact, the Randić index became the most popular and most frequently-employed structure descriptor, used in numerous QSPRand QSARstudies. To study chemical applications and mathematical results of the Randić index in depth, we refer to [44,49,51].
For an edge e = uv and any real number α, one defines w(e) = (d(u)d(v))α, where d(u) denotes the degree of u. Then, the general Randić index [44,52,53] is defined as:
R α ( G ) = ∑ u v ∈ E ( d ( u ) d ( v ) ) α .
When α = − 1 2, Equation (4) is just the well-known Randić index [49]. When α = 1, Equation (4) is the second Zagreb index [54–57]. The case of α = −1 has been also investigated [58].
Now, we list some basic extremal results on Rα(G) for α < 0 that are used in this paper.
Lemma 1 ([44]). (i) Let G be a graph with n vertices and no isolated vertices. For α ∈ (−1/2, 0), the maximum value of Rα is n ( n − 1 ) 1 + 2 α 2 and the minimum value is min min { ( n − 1 ) 1 + α , n 2 ( e v e n n ) , n − 3 2 + 2 1 + α ( o d d n ) }; for α ∈ (−∞, −1), the maximum value of Rα is n 2 ( e v e n n ) o r n − 3 2 + 2 1 + α ( o d d n ), and the minimum value is n ( n − 1 ) 1 + 2 α 2.
(ii) Among all trees with n vertices, the star graph Sn attains the minimum value of Rα for α < 0 and Rα(Sn) = (n − 1)α+1; the path graph Pn attains the maximum value of Rα for α ∈ [−1/2, 0] and Rα (Pn) = 2α+1 + (n − 3)4α; the subdivided star attains the maximum value of Rα for α ∈ [−∞, −2] when n ≥ 7, and the Rα-value of the subdivided star is n − 1 2 ( ( n − 1 ) α + 2 α ) ( o d d n ) o r n − 2 2 ( ( n − 2 ) α + 2 α ) + 4 α ( e v e n n ).
Let G be a graph with n vertices. The Laplacian matrix of G is L(G) = D(G) − A(G), where A(G) and D(G) = diag(d1, d2,…, dn) denote the adjacency matrix of G and the diagonal matrix of vertex degrees, respectively. Let λ1(G) ≥ λ2(G) ≥ … ≥ λn(G) = 0 be the eigenvalues of L(G), which are also called Laplacian eigenvalues of G. In [59], the authors proved the following result.
Lemma 2 ([59]). Let G be a simple connected graph with n vertices. Then:
1 2 ∑ i = 1 n d i 2 α + 1 − k 2 λ 1 ( G ) ≤ R α ( G ) ≤ 1 2 ∑ i = 1 n d i 2 α + 1 − k 2 λ n − 1 ( G ) ,
where k = ∑ i = 1 n d i 2 α − 1 n ( ∑ i = 1 n d i α ) 2.
Let I(G, α) be the entropy I(G, w) based on the above stated weight, i.e.,
I ( G , α ) = − ∑ u v ∈ E ( d ( u ) d ( v ) ) α ∑ u v ∈ E ( d ( u ) d ( v ) ) α log ( ( d ( u ) d ( v ) ) α ∑ u v ∈ E ( d ( u ) d ( v ) ) α ) .
The above equality can also be expressed as:
I ( G , α ) = log ( R α ( G ) ) − α R α ( G ) ∑ u v ∈ E ( d ( u ) d ( v ) ) α log ( d ( u ) d ( v ) ) .
Now, we can establish inequalities between I(G, α) and Rα.
Theorem 2. Let G be a connected graphs with n vertices. For α < 0, we have:
log ( R ′ ) − α ≤ I ( G , α ) ≤ log ( R ) − 2 α log ( n − 1 ) ,
where R′ = min Rα(G) and R = max Rα(G).
Proof. Since α < 0, we have:
I ( G , α ) ≤ log ( R ) − α R ∑ u v ∈ E ( d ( u ) d ( v ) ) α log ( ( n − 1 ) 2 ) = log ( R ) − 2 α log ( n − 1 )
and
I ( G , α ) ≥ log ( R ′ ) − α R ′ ∑ u v ∈ E ( d ( u ) d ( v ) ) α log ( 2 ) = log ( R ′ ) − α .
The proof is completed.
From the above stated theorem representing an upper or a lower bound of Rα for α < 0, we can obtain an upper bound or a lower bound of I(G, α). As an example, we can get some bounds of Rα from Lemmas 1 and 2.
Corollary 1. (i) Let G be a graph with n vertices and no isolated vertices. For α ∈ (−1/2, 0), we have:
log ( min { ( n − 1 ) 1 + α , n 2 ( e v e n n ) , n − 3 2 + 2 1 + α ( o d d n ) } ) − α ≤ I ( G , α ) ≤ log ( n ( n − 1 ) ) − 1 ;
for α ∈ (−∞, −1), when n is even, we have:
log ( n ( n − 1 ) 1 + 2 α ) − α − 1 ≤ I ( G , α ) ≤ log ( n ) − 2 α log ( n − 1 ) − 1 ,
when n is odd, we have:
log ( n ( n − 1 ) 1 + 2 α ) − α − 1 ≤ I ( G , α ) ≤ log ( n − 3 + 2 2 + α ) − 2 α log ( n − 1 ) − 1.
(ii) Let T be a tree with n vertices. For α ∈ [−1/2, 0], we have:
( α + 1 ) log ( n − 1 ) − α ≤ I ( G , α ) ≤ log ( 1 + ( n − 3 ) 2 α − 1 ) − 2 α log ( n − 1 ) + α + 1 ;
for α ∈ [−∞, −2], when n is odd, we have:
( α + 1 ) log ( n − 1 ) − α ≤ I ( G , α ) ≤ log ( ( n − 1 ) α + 2 α ) + ( 1 − 2 α ) log ( n − 1 ) − 1 ,
when n is even, we have:
( α + 1 ) log ( n − 1 ) − α ≤ I ( G , α ) ≤ log ( n − 2 2 ( ( n − 2 ) α + 2 α ) + 4 α ) − 2 α log ( n − 1 ) .
Corollary 2. Let G be a simple connected graph with n vertices. Then:
log ( 1 2 ∑ i = 1 n d i 2 α + 1 − k 2 λ 1 ( G ) ) − α ≤ I ( G , α ) ≤ log ( 1 2 ∑ i = 1 n d i 2 α + 1 − k 2 λ n − 1 ( G ) ) − 2 α log ( n − 1 ) ,
where k = ∑ i = 1 n d i 2 α − 1 n ( ∑ i = 1 n d i α ) 2.
From the proof of Theorem 2, we get the following result.
Corollary 3. Let G be a graph with n vertices. Let δ and Δ be the minimum degree and the maximum degree of G, respectively. Then, for α < 0, we have:
log ( R ′ ) − 2 α log ( δ ) ≤ I ( G , α ) ≤ log ( R ) − 2 α log ( Δ ) ,
where R′ = min Rα(G) and R = max Rα(G).
In the following, we will study some extremal properties of I(G, α) for some classes of graphs.
Theorem 3. Let G = (V, E, w) be a regular graph with n vertices and n ≥ 3. Then, we have:
log n ≤ I ( G , α ) ≤ log ( n ( n − 1 ) 2 ) .
The left equality holds if and only if G is the cycle graph, and the right equality holds if and only if G is the complete graph.
Proof. Suppose G = (V, E, w) is k-regular. Then, k ≥ 2, since G is connected and n ≥ 3. Therefore, we have:
I ( G , α ) = − ∑ e ∈ E k 2 α ∑ e ∈ E k 2 α log k 2 α ∑ e ∈ E k 2 α = log n k 2 .
Since 2 ≤ k ≤ n − 1, we have:
log n ≤ I ( G , α ) ≤ log ( n ( n − 1 ) 2 ) .
The proof is complete.
In the following, we prove bounds for complete bipartite graphs. However, it seems not easy to determine bounds for the complete k-partite graphs.
Theorem 4. Let G = (V, E, w) be a complete bipartite graph with n vertices. Then, we infer:
log ( n − 1 ) ≤ I ( G , α ) ≤ log ( ⌊ n 2 ⌋ ⌈ n 2 ⌉ ) .
The left equality holds if and only if G is the star graph, and the right equality holds if and only if G is the balanced complete bipartite graph.
Proof. Suppose G = (V, E, w) is a complete bipartite graph with n vertices, and the two parts have p and q vertices, respectively. Therefore, p + q = n. We have:
I ( G , α ) = − ∑ e ∈ E ( p q ) α ∑ e ∈ E ( p q ) α log ( p q ) α ∑ e ∈ E ( p q ) α = log ( p q ) .
Thus,
log ( n − 1 ) ≤ I ( G , α ) ≤ log ( ⌊ n 2 ⌋ ⌈ n 2 ⌉ ) .
The left equality holds if and only if p = 1 and q = n − 1, i.e., G is a star. The right equality holds if p = ⌊ n 2 ⌋ and q = ⌈ n 2 ⌉, i.e., G is the balanced complete bipartite graph.
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 Pn−t of which one end vertex coincides with a pendent vertex of a star St+1 of order t+1. Observe that CS(n, t) is the path graph if t = 2 and is the star graph if t = n − 1. Then, for 2 ≤ t ≤ n − 2, we have:
I ( C S ( n , t ) , α ) = log ( 2 α + ( 2 t ) α + ( t − 1 ) t α + ( n − t − 2 ) 4 α ) − α ( 2 α + ( 2 t ) α log ( 2 t ) + ( t − 1 ) t α log t + 2 ( n − t − 2 ) 4 α ) 2 α + ( 2 t ) α + ( t − 1 ) t α + ( n − t − 2 ) 4 α .
By some elementary calculations, we get the following result.
Theorem 5. Among all comets with n vertices and parameter t,
  • for α = 1, we have:
    I ( C S ( n , t 0 ) , α ) ≤ I ( C S ( n , t ) , α ) ≤ log ( n − 1 ) ,
    the right equality holds if and only if t = n − 1, i.e., CS(n, t) is the star graph, and the left equality holds if and only if t = t0, where t ≥ 3 is the root the equation ∂ I ( C S ( n , t ) , 1 ) ∂ t = 0 , i.e.,
    ( ( t 2 + t ) log t − 6 t + 8 n − 14 ) ( 2 t − 3 ) = ( t 2 − 3 t + 4 n − 6 ) ( ( 2 t + 1 ) log t − t − 4 ln 2 − 6 ) .
  • For α = −1, we have:
    I ( C S ( n , t ) , α ) ≤ log ( n − 1 ) ,
    the right equality holds if and only if t = n − 1, i.e., CS(n, t) is the star graph, and the left equality holds if and only if t = t0, where t0 ≥ 4 is the root the equation ∂ I ( C S ( n , t ) , − 1 ) ∂ t = 0 , i.e.,
    ( 1 + ( 2 t − 1 ) log t + ( n − t ) t ) ( 2 − t 2 ) = ( 2 t − 1 + ( n − t ) t 2 ) ( − 2 − 2 t 2 + 2 log t + 4 t − t 2 ln 2 ) .
By performing a numerical study, we also list some values of t0 and t00 as follows in Table 1.
For most of the topological indices on trees with a given number of vertices, we obtain that the star graph and the path graph are the extremal graphs maximal or minimal values. However, from Theorem 5, the path graph is not the extremal graph among all trees, as the path graph is also a comet. It seems to be intricate to determine extremal values of this entropy and to characterize the corresponding extremal graphs among all trees with a given number of vertices for any real number α.
Similarly, by some elementary calculations, we get the extremal values of double stars.
Theorem 6. For Sp,q, we have that for α ∈ [0.5, +∞),
I ( S ⌊ n / 2 ⌋ , ⌈ n / 2 ⌉ , α ) ≤ I ( S p , q , α ) ≤ I ( S 1 , n − 1 , α ) ;
for α ∈ [−∞, −0.5),
I ( S 1 , n − 1 , α ) ≤ I ( S p , q , α ) ≤ I ( S ⌊ n / 2 ⌋ , ⌈ n / 2 ⌉ , α ) .
We try to determine the bounds for all values of α. However, the problem seems quite complicated when α ∈ (−0.5, 0.5).
In [20,60], the authors studied the extremal values of entropy based on different well-known information functionals for dendrimers, which possess interesting applications in structural chemistry and computational biology. We also consider the value of I(G, α) for dendrimers.
A dendrimer is a tree with two additional parameters; the progressive degree t and the radius r. Every internal node of the tree has degree t+1. As in every tree, a dendrimer has one (monocentric dendrimer) or two (dicentric dendrimer) central nodes; the radius r denotes the (largest) distance from an external node to the (closer) center. If all external nodes are at a distance r from the center, then the dendrimer is called homogeneous. Internal nodes different from the central nodes are called branching nodes and are said to be on the i-th orbit if their distance to the (nearer) center is r. Every branching vertex has one incoming edge, as well as t outgoing edges.
Let D(t, r) denote the dendrimer graph with parameters t and r. If D(t, r) has only one center, then we have n = 1 + ( t + 1 ) ( t r − 1 ) t − 1. If D (t, r) has only two centers, then we have n = 2 ( t r + 1 − 1 ) t − 1. Observe that 1 ≤ t ≤ n − 2 and 1 ≤ r ≤ ⌊ n − 1 2 ⌋. As an example, we show dendrimers with one center (left) and two centers (right), such that t =3 and r = 3 in Figure 1. In addition, the graph is the star if r = 1 and t = n − 2, while the graph is the path if r = ⌊ n − 1 2 ⌋ and t = 1. In the following, we suppose D (t, r) has only one center, since the other case is similar. We will show that for α ∈ (−∞, 0), the star graph and the path graph attain the minimum and maximum value of I (G, α), respectively. However, it seems very complicated getting such results for α ∈ (0, ∞).
Theorem 7. Let D(t, r) be a dendrimer with n vertices with only one center. Then, for α ∈ (−∞, 0), we have:
log ( 2 + ( n − 3 ) 2 α ) − α ( n − 3 ) 2 α − 1 1 + ( n − 3 ) 2 α − 1 ≤ I ( G , α ) ≤ log ( n − 1 ) ,
the left equality holds if and only if D (t, r) is the path graph, and the right equality holds if and only if D(t, r) is the star graph.
Proof. If r = 1, i.e., D is a star, then we have I (D, α) = log (t + 1). Since D (t, r) has only one center, we have n = 1 + ( t + 1 ) ( t r − 1 ) t − 1 = t + 2, i.e., t= n − 2. Therefore, in this case, we have I (D, α) = log (n−1). If t = 1, i.e., D is a path, then by some elementary calculations, we have:
I ( D , α ) = log ( 2 + ( n − 3 ) 2 α ) − α ( n − 3 ) 2 α − 1 1 + ( n − 3 ) 2 α − 1 .
In the following, we suppose t ≥ 2, i.e., r ≤ ⌊ n − 1 2 ⌋ − 1. Since D (t, r) has only one center, then there are (t + 1)tr−1 leaves, and both end vertices of any other edge have degree t + 1. Set A 1 = ∑ u v ∈ E ( d ( u ) d ( v ) ) α ∑ u v ∈ E ( d ( u ) d ( v ) ) α. Then, we infer:
A 1 = ( t + 1 ) t r − 1 ( t + 1 ) α + ( n − 1 − ( t + 1 ) t r − 1 ) ( t + 1 ) 2 α = ( t + 1 ) t r − 1 ( t + 1 ) α + t + 1 t − 1 ( t r − 1 − 1 ) ( t + 1 ) 2 α .
Therefore,
I ( D , α ) = − ( t + 1 ) t r − 1 ⋅ ( t + 1 ) α A 1 ⋅ log ( ( t + 1 ) α A 1 ) − ( n − 1 − ( t + 1 ) t r − 1 ) ⋅ ( t + 1 ) 2 α A 1 ⋅ log ( ( t + 1 ) 2 α A 1 ) = − ( t + 1 ) t r − 1 ⋅ ( t + 1 ) α A 1 ⋅ log ( ( t + 1 ) α A 1 ) − t + 1 t − 1 ( t r − 1 − 1 ) ⋅ ( t + 1 ) 2 α A 1 ⋅ log ( ( t + 1 ) 2 α A 1 ) = log ( t r − 1 ( t + 1 ) + t + 1 t − 1 ( t r − 1 − 1 ) ( t + 1 ) α ) − α ( t r − 1 − 1 ) ( t + 1 ) α log ( t + 1 ) t r − 1 ( t − 1 ) + ( t r − 1 − 1 ) ( t + 1 ) α .
By substituting n = 1 + ( t + 1 ) ( t r − 1 ) t − 1 into the above equality, we have:
I ( D , α ) = log [ n t − n − 2 t + ( − t 2 + ( n − 1 ) t − n − 2 ) ( t + 1 ) α t ( t − 1 ) ] − α ( − t 2 + ( n − 1 ) t − n − 2 ) ( t + 1 ) α log ( t + 1 ) ( n t − n − 2 ) ( t + 1 ) + ( − t 2 + ( n − 1 ) t − n − 2 ) ( t + 1 ) α .
By some elementary calculations, we infer that for α < 0 and a given n, I(D, α) is an increasing function on t. Thus, I(D, α) attains the minimum when t = 1 and attains the maximum value when t = n − 2. Thus, we have completed the proof.

4. Summary and Conclusions

Based on the contribution of Eagle et al. [47] investigating vertex entropies, we introduced in our paper the concept of a graph entropy for weighted graphs. To the best of our knowledge, this problem has received very little attention so far with only a few exceptions, e.g., [61]. We examined extremal properties of our entropy definition for special graph classes. Specifically, in this paper, we placed our emphasis on weighted graphs due to Bollobás and Erdös, which is also called the Randić weight.
As an open problem, it would be interesting to consider the extremal values of I(D, α) among all dendrimers for α ∈ (0, ∞). Furthermore, it is challenging to determine extremal values of I(T, α) among all trees with n vertices for any real number α. One possible attempt to do this could be based on establishing some graph transformations, which can increase or decrease the values of the entropy. This leads to the formulation of the following open problem.
Problem 1. Determine extremal values of I(T, α) among all trees with n vertices for any real number α.
This paper mainly considered edge weights defined by Bollobás and Erdös. For future work, it would be interesting to consider other edge weights of graphs, such as the sum-connectivity weight [62,63] and the atom-bond connectivity (ABC) index [64–66], which are well studied with applications in chemistry. Furthermore, it would be interesting to generalize our definition to (weighted) hypergraphs.
On the other hand, the entropy for vertex-weighted graphs can be defined similarly, which has already been studied extensively; see [17,19].

Acknowledgments

Matthias Dehmer thanks the Austrian Science Funds for supporting this work (Project P26142). Matthias Dehmer gratefully acknowledges financial support from the German Federal Ministry of Education and Research (BMBF) (Project RiKoV, Grant No. 13N12304). Zengqiang Chen was supported by the National Science Foundation of China (No. 61174094) and the Natural Science Foundation of Tianjin (No. 14JCYBJC18700). Yongtang Shi was supported by The National Science Foundation of China (NSFC), Program for Changjiang Scholars and Innovative Research Team in University (PCSIRT) and the China Postdoctoral Science Foundation.

Author Contributions

Wrote the paper: Zengqiang Chen, Matthias Dehmer, Frank Emmert-Streib and Yongtang Shi. Did the analysis: Zengqiang Chen, Matthias Dehmer, Frank Emmert-Streib and Yongtang Shi. All authors have read and approved the final manuscript.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Shannon, C.; Weaver, W. The Mathematical Theory of Communication; University of Illinois Press: Urbana, IL, USA, 1949. [Google Scholar]
  2. Rashevsky, N. Life, information theory, and topology. Bull. Math. Biophys. 1955, 17, 229–235. [Google Scholar]
  3. Mowshowitz, A. Entropy and the complexity of the graphs I: An index of the relative complexity of a graph. Bull. Math. Biophys. 1968, 30, 175–204. [Google Scholar]
  4. Mowshowitz, A. Entropy and the complexity of graphs II: The information content of digraphs and infinite graphs. Bull. Math. Biophys. 1968, 30, 225–240. [Google Scholar]
  5. Mowshowitz, A. Entropy and the complexity of graphs III: Graphs with prescribed information content. Bull. Math. Biophys. 1968, 30, 387–414. [Google Scholar]
  6. Mowshowitz, A. Entropy and the complexity of graphs IV: Entropy measures and graphical structure. Bull. Math. Biophys. 1968, 30, 533–546. [Google Scholar]
  7. Dehmer, M.; Graber, A. The discrimination power of molecular identification numbers revisited. MATCH Commun. Math. Comput. Chem. 2013, 69, 785–794. [Google Scholar]
  8. Kraus, V.; Dehmer, M.; Schutte, M. On sphere-regular graphs and the extremality of information-theoretic network measures. MATCH Commun. Math. Comput. Chem. 2013, 70, 885–900. [Google Scholar]
  9. Allen, E.B. Measuring Graph Abstractions of Software: An Information-Theory Approach. Proceedings of the 8th International Symposium on Software Metrics, Ottawa, ON, Canada, 4–7 June 2002; p. 182.
  10. Kraus, V.; Dehmer, M.; Emmert-Streib, F. Probabilistic inequalities for evaluating structural network measures. Inf. Sci. 2014, 288, 220–245. [Google Scholar]
  11. Dehmer, M.; Emmert-Streib, F.; Grabner, M. A computational approach to construct a multivariate complete graph invariant. Inf. Sci. 2014, 260, 200–208. [Google Scholar]
  12. Chen, Y.; Wu, K.; Chen, X.; Tang, C.; Zhu, Q. An entropy-based uncertainty measurement approach in neighborhood systems. Inf. Sci. 2014, 279, 239–250. [Google Scholar]
  13. Lawyer, G. Understanding the influence of all nodes in a network. Sci. Rep. 2015, 5. [Google Scholar] [CrossRef]
  14. Wang, C.; Qu, A. Entropy, similarity measure and distance measure of vague soft sets and their relations. Inf. Sci. 2013, 244, 92–106. [Google Scholar]
  15. Körner, J. Coding of an information source having ambiguous alphabet and the entropy of graphs. Proceedings of the 6th Prague Conference on Information Theory, Statistical Decision, Functions, Random Processes, Prague, Czech Republic, 19–25 September 1971; pp. 411–425.
  16. Dehmer, M.; Li, X.; Shi, Y. Connections between generalized graph entropies and graph energy. Complexity 2014. [Google Scholar] [CrossRef]
  17. Dehmer, M. Information processing in complex networks: Graph entropy and information functionals. Appl. Math. Comput. 2008, 201, 82–94. [Google Scholar]
  18. Dragomir, S.; Goh, C. Some bounds on entropy measures in information theory. Appl. Math. Lett. 1997, 10, 23–28. [Google Scholar]
  19. Dehmer, M.; Mowshowitz, A. A History of Graph Entropy Measures. Inf. Sci. 2011, 1, 57–78. [Google Scholar]
  20. Chen, Z.; Dehmer, M.; Emmert-Streib, F.; Shi, Y. Entropy bounds for dendrimers. Appl. Math. Comput. 2014, 242, 462–472. [Google Scholar]
  21. Chen, Z.; Dehmer, M.; Shi, Y. A note on distance-based graph entropies. Entropy 2014, 16, 5416–5427. [Google Scholar]
  22. Soltani, A.; Iranmanesh, A.; Majid, Z.A. The multiplicative version of the edge Wiener index. MATCH Commun. Math. Comput. Chem. 2014, 71, 407–416. [Google Scholar]
  23. Lin, H. Extremal Wiener index of trees with given number of vertices of even degree. MATCH Commun. Math. Comput. Chem. 2014, 72, 311–320. [Google Scholar]
  24. Skrekovski, R.; Gutman, I. Vertex version of the Wiener theorem. MATCH Commun. Math. Comput. Chem. 2014, 72, 295–300. [Google Scholar]
  25. Lin, H. On the Wiener index of trees with given number of branching vertices. MATCH Commun. Math. Comput. Chem. 2014, 72, 301–310. [Google Scholar]
  26. Al-Fozan, T.; Manuel, P.; Rajasingh, I.; Rajan, R. Computing Szeged index of certain nanosheets using partition technique. MATCH Commun. Math. Comput. Chem. 2014, 72, 339–353. [Google Scholar]
  27. Da Fonseca, C.; Ghebleh, M.; Kanso, A.; Stevanovic, D. Counterexamples to a conjecture on Wiener index of common neighborhood graphs. MATCH Commun. Math. Comput. Chem. 2014, 72, 333–338. [Google Scholar]
  28. Knor, M.; Lužar, B.; Škrekovski, R.; Gutman, I. On Wiener index of common neighborhood graphs. MATCH Commun. Math. Comput. Chem. 2014, 72, 321–332. [Google Scholar]
  29. Feng, L.; Liu, W.; Yu, G.; Li, S. The hyper-Wiener index of graphs with given bipartition. Util. Math. 2014, 95, 23–32. [Google Scholar]
  30. Feng, L.; Yu, G. The hyper-Wiener index of cacti. Util. Math. 2014, 93, 57–64. [Google Scholar]
  31. Ma, J.; Shi, Y.; Yue, J. The Wiener polarity index of graph products. Ars Comb. 2014, 116, 235–244. [Google Scholar]
  32. Wiener, H. Structural determination of paraffin boiling points. J. Am. Chem. Soc. 1947, 69, 17–20. [Google Scholar]
  33. Cao, S.; Dehmer, M.; Shi, Y. Extremality of degree-based graph entropies. Inf. Sci. 2014, 278, 22–33. [Google Scholar]
  34. Cao, S.; Dehmer, M. Degree-based entropies of networks revisited. Appl. Math. Comput. 2015, 261, 141–147. [Google Scholar]
  35. Gutman, I. An exceptional property of first Zagreb index. MATCH Commun. Math. Comput. Chem. 2014, 72, 733–740. [Google Scholar]
  36. Azari, M.; Iranmanesh, A.; Gutman, I. Zagreb indices of bridge and chain graphs. MATCH Commun. Math. Comput. Chem. 2013, 70, 921–938. [Google Scholar]
  37. Das, K.; Xu, K.; Gutman, I. On Zagreb and Harary indices. MATCH Commun. Math. Comput. Chem. 2013, 70, 301–314. [Google Scholar]
  38. Lin, H. Vertices of degree two and the first Zagreb index of trees. MATCH Commun. Math. Comput. Chem. 2014, 72, 825–834. [Google Scholar]
  39. Vasilyev, A.; Darda, R.; Stevanovic, D. Trees of given order and independence number with minimal first Zagreb index. MATCH Commun. Math. Comput. Chem. 2014, 72, 775–782. [Google Scholar]
  40. Ji, S.; Li, X.; Huo, B. On reformulated Zagreb indices with respect to acyclic, unicyclic and bicyclic Graphs. MATCH Commun. Math. Comput. Chem. 2014, 72, 723–732. [Google Scholar]
  41. Xu, K.; Das, K.C.; Balachandran, S. Maximizing the Zagreb Indices of (n, m)-Graphs. MATCH Commun. Math. Comput. Chem. 2014, 72, 641–654. [Google Scholar]
  42. Hu, Y.; Li, X.; Shi, Y.; Xu, T. Connected (n, m)-graphs with minimum and maximum zeroth-order general Randić index. Discret. Appl. Math. 2007, 155, 1044–1054. [Google Scholar]
  43. Hu, Y.; Li, X.; Shi, Y.; Xu, T.; Gutman, I. On molecular graphs with smallest and greatest zeroth-order general Randić index. MATCH Commun. Math. Comput. Chem. 2005, 54, 425–434. [Google Scholar]
  44. Li, X.; Shi, Y. A survey on the Randić index. MATCH Commun. Math. Comput. Chem. 2008, 59, 127–156. [Google Scholar]
  45. Bollobás, B.; Nikiforov, V. Degree powers in graphs: the Erdös-Stone Theorem. Comb. Probab. Comput. 2012, 21, 89–105. [Google Scholar]
  46. Gu, R.; Li, X.; Shi, Y. Degree powers in C5-free graphs. Bull. Malays. Math. Sci. Soc. 2014. [Google Scholar] [CrossRef]
  47. Eagle, N.; Macy, M.; Claxton, R. Network diversity and economic development. Science 2010, 328, 1029–1031. [Google Scholar]
  48. Dehmer, M.; Barbarini, N.; Varmuza, K.; Graber, A. Novel Topological Descriptors for Analyzing Biological Networks. BMC Struct. Biol. 2010, 10. [Google Scholar] [CrossRef]
  49. Randić, M. On characterization of molecular branching. J. Am. Chem. Soc. 1975, 97, 6609–6615. [Google Scholar]
  50. Bollobás, B.; Erdös, P. Graphs of extremal weights. Ars Comb. 1998, 50, 225–233. [Google Scholar]
  51. Li, X.; Gutman, I. Mathematical Aspects of Randić-Type Molecular Structure Descriptors; University of Kragujevac and Faculty of Science Kragujevac: Kragujevac, Serbia, 2006. [Google Scholar]
  52. Li, X.; Shi, Y.; Zhong, L. Minimum general Randić index on chemical trees with given order and number of pendent vertices. MATCH Commun. Math. Comput. Chem. 2008, 60, 539–554. [Google Scholar]
  53. Li, X.; Shi, Y.; Xu, T. Unicyclic graphs with maximum general Randić index for α > 0. MATCH Commun. Math. Comput. Chem. 2006, 56, 557–570. [Google Scholar]
  54. Arezoomand, M.; Taeri, B. Zagreb Indices of the Generalized Hierarchical Product of Graphs. MATCH Commun. Math. Comput. Chem. 2013, 69, 131–140. [Google Scholar]
  55. Kazemi, R. The second Zagreb index of molecular graphs with tree structure. MATCH Commun. Math. Comput. Chem. 2014, 72, 753–760. [Google Scholar]
  56. Abdo, H.; Dimitrov, D.; Reti, T.; Stevanovic, D. Estimating the spectral radius of a graph by the second Zagreb index. MATCH Commun. Math. Comput. Chem. 2014, 72, 741–751. [Google Scholar]
  57. da Fonseca, C.; Stevanovic, D. Further properties of the second Zagreb index. MATCH Commun. Math. Comput. Chem. 2014, 72, 655–668. [Google Scholar]
  58. Li, X.; Yang, Y. Best lower and upper bounds for the Randić index R−1 of chemical trees. MATCH Commun. Math. Comput. Chem. 2004, 52, 147–156. [Google Scholar]
  59. Lu, M.; Liu, H.; Tian, F. The Connectivity Index. MATCH Commun. Math. Comput. Chem. 2004, 51, 149–154. [Google Scholar]
  60. Dehmer, M.; Kraus, V. On extremal properties of graph entropies. MATCH Commun. Math. Comput. Chem. 2012, 68, 889–912. [Google Scholar]
  61. Dehmer, M.; Barbarini, N.; Varmuza, K.; Graber, A. A Large Scale Analysis of Information-Theoretic Network Complexity Measures Using Chemical Structures. PLoS ONE 2009, 4, e8057. [Google Scholar]
  62. Tomescu, I.; Jamil, M. Maximum General Sum-Connectivity Index for Trees with Given Independence Number. MATCH Commun. Math. Comput. Chem. 2014, 72, 715–722. [Google Scholar]
  63. Du, Z.; Zhou, B.; Trinajstić, N. On the general sum-connectivity index of trees. Appl. Math. Lett. 2011, 24, 402–405. [Google Scholar]
  64. Ahmadi, M.; Dimitrov, D.; Gutman, I.; Hosseini, S. Disproving a Conjecture on Trees with Minimal Atom-Bond Connectivity Index. MATCH Commun. Math. Comput. Chem. 2014, 72, 685–698. [Google Scholar]
  65. Hosseini, S.; Ahmadi, M.; Gutman, I. Kragujevac trees with minimal atom-bond connectivity index. MATCH Commun. Math. Comput. Chem. 2014, 71, 5–20. [Google Scholar]
  66. Rostami, M.; Sohrabi-Haghighat, M. Further Results on New Version of Atom-Bond Connectivity Index. MATCH Commun. Math. Comput. Chem. 2014, 71, 21–32. [Google Scholar]
Entropy 17 03710f1 1024
Figure 1. The dendrimers with one center (left) and two centers (right), such that t =3 and r = 3.
Figure 1. The dendrimers with one center (left) and two centers (right), such that t =3 and r = 3.
Entropy 17 03710f1
Table
Table 1. Some values of t0 and t 0 ′.
Table 1. Some values of t0 and t 0 ′.
n304050601002003004005001000
t0111519222536577488102155
t 0 ′182736455492190288387486983

Share and Cite

MDPI and ACS Style

Chen, Z.; Dehmer, M.; Emmert-Streib, F.; Shi, Y. Entropy of Weighted Graphs with Randi´c Weights. Entropy 2015, 17, 3710-3723. https://doi.org/10.3390/e17063710

AMA Style

Chen Z, Dehmer M, Emmert-Streib F, Shi Y. Entropy of Weighted Graphs with Randi´c Weights. Entropy. 2015; 17(6):3710-3723. https://doi.org/10.3390/e17063710

Chicago/Turabian Style

Chen, Zengqiang, Matthias Dehmer, Frank Emmert-Streib, and Yongtang Shi. 2015. "Entropy of Weighted Graphs with Randi´c Weights" Entropy 17, no. 6: 3710-3723. https://doi.org/10.3390/e17063710

APA Style

Chen, Z., Dehmer, M., Emmert-Streib, F., & Shi, Y. (2015). Entropy of Weighted Graphs with Randi´c Weights. Entropy, 17(6), 3710-3723. https://doi.org/10.3390/e17063710

Article Metrics

Back to TopTop