Next Article in Journal
The Natural Philosophy of Work
Previous Article in Journal
Distillation of a Complex Mixture. Part I: High Pressure Distillation Column Analysis: Modeling and Simulation
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

Entropy Characteristic on Harmonious Unifying Hybrid Preferential Networks

1
China Institute of Atomic Energy, P.O. Box 275-81, Beijing 102413, P. R. ChinaChina Institute of Atomic Energy, P.O. Box 275-81, Beijing 102413, P. R. China
2
Wuhan University of Technology, Wuhan 430070, P. R. China
*
Author to whom correspondence should be addressed.
Submission received: 27 September 2006 / Accepted: 18 April 2007 / Published: 21 May 2007

Abstract

:
Based on the harmonious unifying hybrid preferential model (HUHPM) network proposed by our group, the entropy characteristic of an un-weighted HUHPM-BA network and a weighted HUHPM-BBV network are investigated as the total hybrid ratio d/r is changed. We derive and compute the general relation of the power exponent of the degree distribution with the entropy by using the Boltzmann-Gibbs entropy (BGS) and the Tsallis non-extensive entropy (Sq). It is found that the BGS decreases as d/r increases and the current of the BGS along with hybrid ratio d/r or exponent γ of power-law is in agreement between numerical simulation and theoretical analysis. The relationship between the Sq and characteristic parameter q under different d/r is also given. And the Sq approaches to the BGS when q→1. These results can provide a better understanding for evolution characteristic in growing complex networks and further applications in network engineering are of prospective potential.

1. Introduction

The discovery of the ubiquity of small world (SW) [1] and scale-free (SF) networks [2,3] has led to many exciting insights into fundamental underlying principles that govern complex systems. It has been realized that, despite functional diversity, most real world networks like WWW and Internet systems share important structural features, e.g: small average path length, high clustering, and scale-free degree distribution. A number of network models have been proposed to embody the fundamental characteristics [4,5,6,7,8,9,10,11,12,13,14,15]. Among them our group led by Fang has proposed the harmonious unifying hybrid preferential model (HUHPM) to a certain class of complex networks, which is controlled by a total hybrid ratio d/r of deterministic preferential attachment (DPA) to random preferential attachment (RPA) [4,10,11,12]. The unified hybrid ratio can be defined as
d / r = Time intervals  d  of  D P A Time intervals  r  of  R P A
where d is the number of time intervals (steps) for DPA, and r is the number of RPA. Within this model we study both numerically and theoretically. It was found that the HUHPM has a key universal topological property and dynamical synchronizability, and one of most important features is that the exponents of power γ (node degree, node strength, and edged weight) are sensitive to the d/r or depends on the d/r strongly [11,12].
As is well known, statistical mechanics have made a great contribution towards the main advances of topology and dynamics in complex networks, as emphasized by Albert and Barabási [3]. People raise a question here: Entropy as another very important characteristic quantity for statistical mechanics, what role does the entropy play in complex networks? Entropy emerges as a classical thermodynamical concept in the 19th century with Clausius but it is due to the work of Boltzmann and Gibbs that the idea of entropy becomes a cornerstone of statistical mechanics. As a result we have that the entropy of a complex system is given by the so-called Boltzmann-Gibbs entropy (BGS)
Entropy 09 00073 i001
with the normalization condition
Entropy 09 00073 i002
where P(i) is the probability for the system to be in the i-th microstate, and k is a Boltzmann constant. Without loss of generality one can also support normalization k = 1. In 1988 Constantino Tsallis introduced the non-extensive entropy Sq [16,17]
Entropy 09 00073 i003
as a generalization of the BGS, where q is a characteristic parameter. It can be regarded as a minimal extension of Shannon entropy, to which it reduces when q→1. Parameter q describes therefore summarily all effects [16,17].
In this paper we use the BGS to measure the relationship of entropy with d/r, as well as power exponent γ. Through the numerical simulation and theoretical analysis we validate the correctness of our results in reference [4]. It is found that as d/r increases the BGS and Sq decrease, which implies that the self-organization of HUHPM is enhanced as hybrid ratio d/r increases. The relationship between the Sq under different d/r is also derived. And the Sq approaches to the BGS when q→1. These results can provide a better understanding for evolution characteristic in growing complex networks.
The whole paper is organized as follows. In the Section 2, some hybrid preferential models are firstly described. Then in the Section 3 and Section 4, we respectively investigate two kinds of entropy in different HUHPM networks. Theoretical results are verified by several simulation results. We conclude the paper and remark in Section 5.

2. Basic network models: the HUHPM

Based on the Barabási and Albert (BA) scale-free (SF) network [2, 3], Fang and Liang [4] proposed a hybrid preferential model (HPM). Furthermore, our group develops the idea to HUHPM model. The basic concept and method for the HUHPM can be expressed as the following [4]:
H U H P M = Deterministic Preferential Attachment  ( D P A ) + Random Preferential Attachment  ( R P A )
This means that the HUHPM can rest on any type of network’s original growth way and RPA pattern by adding the DPA pattern according to certain arrangement of the degree distribution to arrive an expected topological properties. This implementation combines the random connection with the deterministic connection by using the hybrid ratio d/r to request growth scale size of the networks. In the process of the network evolution, the hybrid ratio must maintain the same value by combining RPA and DPA. Actually, the kind of preferential attachments carried on at first is flexible. This means that one can use different order to make the two hybrids grow the network in turn, until the required scale size is achieved. Figure 1 illustrates diagrams for evolution of HUHPM growing networks with N=14 and m=m0=3 under different hybrid ratio d/r=1/6, 1/1 and 6/1.
Figure 1. The network’s evolution process according to different d/r in HUHPM model. And the number of nodes is N=14, m=m0=3. Fig(a) for d/r=1/6, Fig(b) for d/r=1/1and Fig(c) for d/r=6/1.
Figure 1. The network’s evolution process according to different d/r in HUHPM model. And the number of nodes is N=14, m=m0=3. Fig(a) for d/r=1/6, Fig(b) for d/r=1/1and Fig(c) for d/r=6/1.
Entropy 09 00073 g001
Barabási and Albert (BA) [5] proposed an un-weighted network model using a famous preferential attachment mechanism. Because the weighted networks can more carefully portray the nodes connection and mutual interaction, not only reflect the topology of real network, but also reveal physical and dynamical characteristics for the real-world networks. Barrat, Barthelemy and Vespignani (BBV) [6,7] proposed a weighted network model with a tunable perturbation parameter δ to rearrange the edges’ weights locally using a random preferential attachment mechanism. BBV turns to BA when δ=0. BBV model can yield scale-free (SF) properties of the degree, strength and weight distributions controlled by weight associated parameter δ. However, both models, BA and BBV, only consider random preferential attachment (RPA) and do not consider deterministic preferential attachment (DPA) or connection effect. This is in contradiction to a fundamental observation, which has both deterministic and random factors extensively exist in the unifying real-world. Therefore, both of RPA and DPA in various complex network models should be paid attention to and be investigated carefully. Therefore, our group proposed the harmonious unifying hybrid preferential model (HUHPM), and applied it to the un-weighted BA and the weighted BBV models, so called HUHPM-BA and HUHPM-BBV models. Since BA and BBV can be described as different network statistical characterizations. In fact, the HUHPM can be applied to any un-weighted and weighted networks. The concrete growth process may refer to the related paper [4,5,6,7,10,11,18]. It is known that the HUHPM network has a series of topological property.

3. Entropy characteristic in the HUHPM-BA

In this section, we use the BGS to measure the relationship of entropy and d/r, as well as power exponent γ. In reference [10] we theoretically get the approximate degree distribution as follows, respectively. For un-weighted network HUHPM-BA, we have
P ( k ) 2 m 1 β k ( 1 β + 1 ) γ = 1 β + 1 = A 1 exp [ ( d / r A 2 ) A 3 ] + A 4
where k is the degree of network node and P(k) denotes the probability distribution of nodes whose degree is k. The d/r is hybrid ratio and the γ is exponents of power-law. All the coefficients Ai above are taken from reference [10], i=1, 2, 3, 4. To compute the entropy, we consider approximately that β is a constant for different m and
P ( k ) = 2 m 1 β k ( 1 β + 1 ) i 2 m 1 β i ( 1 β + 1 ) = 1 i ( k i ) 1 β + 1
where P(k) satisfying normalization condition
P ( k ) = 1
Using formula (1), (3) and (4), we draw the theoretical curves BGS VS d/r and BGS VS γ, as shown in figure 2(a) and (c). The corresponding results of numerical simulation are shown in figure 2(b) and (d).
Figure 2. BGS versus d/r and γ with network size N=2000, m=1, 3, 5, where (a), (c) are theoretical results for BGS and (b), (d) are numerical simulation results respectively.
Figure 2. BGS versus d/r and γ with network size N=2000, m=1, 3, 5, where (a), (c) are theoretical results for BGS and (b), (d) are numerical simulation results respectively.
Entropy 09 00073 g002
Figure 3. The relationship between Sq and q under different d/r, N=2000. The d/r of these plots spans from 1/1999 to 1999/1, where (a) is theoretical result and (b) is numerical simulation result.
Figure 3. The relationship between Sq and q under different d/r, N=2000. The d/r of these plots spans from 1/1999 to 1999/1, where (a) is theoretical result and (b) is numerical simulation result.
Entropy 09 00073 g003
According to the formula (2), figure 3 gives the relationship between Sq and q under different d/r. It is seen from figure 3 that for the fixed q value Sq reduces along with the d/r increase. When q = 1 it turns to BGS. Clearly, the tendency of change for two kinds of entropy above with the hybrid ratio d/r are similar each other. This means that two kinds of entropy are in consistent with each other basically when q is getting bigger. As mentioned above, however, because parameter q only describes summarily all effects [16,17]. A few differences of two results for two kinds of entropy may not avoid.

4. Entropy characteristic in the weighted HUHPM-BBV

HUHPM-BBV model generates weighted graphs exhibiting the statistical properties observed in several real world systems. Considering a network grown by HUHPM-BBV model, its degree distribution is shown below.
P ( k ) 1 m 1 1 β β k 1 + 1 β γ = 1 + 1 β = 4 δ + A 1 exp [ ( d / r A 2 ) A 3 ] + A 4 2 δ + 1
where k is the degree of network node and P(k) denotes the probability distribution of nodes whose degree is k. The d/r is total hybrid ratio and the γ is exponents of power-law. All the coefficients Ai above are taken from reference [10], i=1, 2, 3, 4. δ is the weighted parameter associated with perturbation of model.
To compute the entropy, we consider approximately that β is a constant for different m and
P ( k ) = 1 m 1 1 β β k 1 + 1 β i 1 m 1 1 β β i 1 + 1 β = 1 i ( k i ) 1 + 1 β
where P(k) satisfying normalization condition
P ( k ) = 1
.
Using formula (1), (5) and (6), we obtain the curves between BGS and d/r, BGS versus γ, as shown in figure 4(a) and (c). The corresponding results of numerical simulation are shown in figure 4(b) and (d). And the results of m=5 in figure 3 are the states of δ=0 corresponding to figure 4.
Figure 4. BGS versus d/r and γ with N=2000, m=5, where (a), (c) are theoretical results for BGS with δ=2 and (b), (d) are numerical simulation results respectively. δ is parameter in BBV model.
Figure 4. BGS versus d/r and γ with N=2000, m=5, where (a), (c) are theoretical results for BGS with δ=2 and (b), (d) are numerical simulation results respectively. δ is parameter in BBV model.
Entropy 09 00073 g004
According to the formula (2), figure 5 gives the relationship between Sq and q under different d/r. If we consider the fixed q value, Sq reduces along with the d/r increasing, and does not associate with m. When q = 1 it turn to BGS.
Figure 5. The relationship between Sq and q under different d/r for N=2000, m=5, δ=2. The d/r of these plots spans from 1/1999 to 1999/1, where (a) theoretical results and (b) numerical simulation results.
Figure 5. The relationship between Sq and q under different d/r for N=2000, m=5, δ=2. The d/r of these plots spans from 1/1999 to 1999/1, where (a) theoretical results and (b) numerical simulation results.
Entropy 09 00073 g005

5. Conclusion and potential of application

Based on the networks grown by HUHPM-BA model and HUHPM-BBV model, we derive and compute the general relation of the power exponent of the degree distribution with the entropy using the BG entropy (BGS) and the Tsallis entropy (Sq). It is found that the BGS decreases as d/r increases and the current of the BGS along with hybrid ratio d/r or exponent γ of power-law is in consistent. The relationship between the Sq and q under different d/r is also given. And the Sq approaches to the BGS when q→1. These results can provide a better understanding for evolution characteristic in growing complex networks and further applications in network engineering are of prospective potential.
It is found that the BGS decreases as d/r increases and the current of the BGS along with hybrid ratio d/r or exponent γ of power-law is in consistent according to numerical simulation and theoretical analysis in both models. The entropy of a network provides an average measure of network’s heterogeneity, since it measure the diversity of the degree distribution. In theoretical analysis, P(k) is power exponent functions and it cut off the long tails(diversity) observed in simulations. So BGS in the simulations takes higher values than in the theory for both models. Also as exponent γ increases, the network becomes less heterogeneous and as a result lower entropy is observed. These results are good consistent with reference [19]. On the other hand, there still have some factors unconsidered while the values of BGS and Sq existing errors drawing from figure 2, figure 3, figure 4 and figure 5. One of reasons produced error is that because parameter q only describes total all effects in global and ignored detail factor, thus a few theoretical error for two kinds of entropy may be understood. Therefore, the form of P(k) and exact entropy theory are still needed to improve deeply. So this subject is still open and challenge in network science for us.
Self-organization is an evolution process from disorder to order. In HUHPM networks, BGS and Sq decrease as d/r increases, which mean that states of disorder tend to order. This situation is easily understood that, since the total hybrid ratio d/r ≥ 1 implies that determinism takes up the dominance and much more order is taken place within HUHPM networks. So the decrease of entropy for a complex system implies the self-organization of HUHPM networks is enhanced with total hybrid ratio d/r increases.
However, we believe that the HUHPM networks reveal one of essential mechanisms to the actual network to produce the SF and SW effects as well as entropy characteristic, therefore further applications in more widespread types of network are possible. For example, because the exponents of the three power law for the HUHPM networks have high sensitivity to the hybrid ratio d/r change, this may make a corresponding encryption method that applies to the cryptology and privacy communication domain. That means that based on track to initiate sensitive disposition, further experiments can be explored combining corresponding network theory. On the other hand, due to the fact that the power exponent, entropy, average path length and average clustering coefficient can adjust by the hybrid ratio d/r, one may design the required network architecture to satisfy different special requirements in network engineering.

Acknowledgements

This work was supported by the Key Projects of the National Natural Science Foundation of China under Grant No.70431002, National Natural Science Foundation of China under Grant No.70371068, and Foundation of President of China Institute of Atomic Energy under Grant No.YZ0618.

References and Notes

  1. Watts, D.J.; Strogatz, S.H. Collective dynamics of 'small-world' networks. Nature 1998, 393, 440–442. [Google Scholar] [CrossRef] [PubMed]
  2. Barabási, A.L.; Albert, R. Emergence of scaling in random networks. Science 1999, 286, 509–512. [Google Scholar] [PubMed]
  3. Albert, R.; Barabási, A.L. Statistical mechanics of complex networks. Reviews of Modern Physics 2002, 74, 47–97. [Google Scholar] [CrossRef]
  4. Fang, J.Q.; Liang, Y. Topological properties and transition features generated by a new hybrid preferential model. Chin. Phys. Lett. 2005, 22(10), 2719–2722. [Google Scholar]
  5. Barabási, A.L.; Albert, R.; Jeong, H. Mean-field theory for scale-free random networks. Physica A 1999, 272, 130–131. [Google Scholar] [CrossRef]
  6. Barrat, A.; Barthélemy, M.; Vespignani, A. Weighted evolving networks: coupling topology and weight dynamics. Phys. Rev. Lett. 2004, 92, 228701. [Google Scholar] [CrossRef] [PubMed]
  7. Barrat, A.; Barthelemy, M.; Vespignani, A. Modeling the evolution of weighted networks. Phys. Rev. E 2004, 70, 066149. [Google Scholar] [CrossRef]
  8. Wang, W.X.; Wang, B.H.; Hu, B.; Yan, G.; Ou, Q. General dynamics of topology and traffic on weighted technological networks. Phys. Rev. Lett. 2005, 94, 188702. [Google Scholar] [CrossRef] [PubMed]
  9. Li, Y.; Fang, J.Q.; Liu, Q.; Liang, Y. Small world properties generated by a new algorithm under same degree of all nodes. Commun. Theor.Phys (Beijing, China) 2006, 45, 950–954. [Google Scholar]
  10. Fang, J.Q.; Bi, Q.; Li, Y.; Lu, X.B.; Liu, Q. A harmonious unifying hybrid preferential model and its universal properties for complex dynamical networks (in Chinese). Chinese Science 2007, 37(2), 1–20. [Google Scholar]
  11. Fang, J. Q.; Bi, Q.; Li, Y.; Lu, X. B.; Liu, Q. Sensitivity of exponents of three-power-laws to hybrid ratio in weighted HUHPM. Chi. Phys. Lett. 2007, 24(1), 279–282. [Google Scholar]
  12. Fang, J. Q. Exploring theoretical model of network science and research progresses (in Chinese). Sci. & Tech. Rev. 2006, 12, 67–72. [Google Scholar]
  13. Fang, J. Q. Theoretical research progress in dynamical complexity of nonlinear complex networks. Progress in Nature Science 2006. (in print). [Google Scholar]
  14. Fang, J. Q.; Bi, Q.; Li, Y. Advances in theoretical models of network. Frontiers of Physics in China 2007, 2(1), 109–124. [Google Scholar] [CrossRef]
  15. Fronczak, A.; Fronczak, P.; Hołyst, J.A. Fluctuation-dissipation relations in complex networks. Phys. Rev. E 2006, 73, 016108. [Google Scholar] [CrossRef]
  16. Tsallis, C.; Baldovin, F.; Cerbino, R.; Pierobon, P. Introduction to nonextensive statistical mechanics and thermodynamics. arXiv cond-mat/0309093 2003. [Google Scholar]
  17. Wilk, G.; Wlodarczyk, Z. Nonextensive information entropy for stochastic networks. arXiv cond-mat/0212056 2003. [Google Scholar]
  18. Lu, X. B.; Wang, X. F.; Fang, J. Q. Topological transition features and synchronizability of a weighted hybrid preferential network. Physica A 2006, 371(2), 841–850. [Google Scholar] [CrossRef]
  19. Solé, R. V.; Valverde, S. Information theory of complex networks: on evolution and architectural constraints. Lect. Notes Phys. 2004, 650, 189–207. [Google Scholar]

Share and Cite

MDPI and ACS Style

Li, Y.; Fang, J.-Q.; Bi, Q.; Liu, Q. Entropy Characteristic on Harmonious Unifying Hybrid Preferential Networks. Entropy 2007, 9, 73-82. https://0-doi-org.brum.beds.ac.uk/10.3390/e9020073

AMA Style

Li Y, Fang J-Q, Bi Q, Liu Q. Entropy Characteristic on Harmonious Unifying Hybrid Preferential Networks. Entropy. 2007; 9(2):73-82. https://0-doi-org.brum.beds.ac.uk/10.3390/e9020073

Chicago/Turabian Style

Li, Yong, Jin-Qing Fang, Qiao Bi, and Qiang Liu. 2007. "Entropy Characteristic on Harmonious Unifying Hybrid Preferential Networks" Entropy 9, no. 2: 73-82. https://0-doi-org.brum.beds.ac.uk/10.3390/e9020073

Article Metrics

Back to TopTop