No Access

ENHANCING NETWORK PERFORMANCE BY EDGE ADDITION

ZHONGYUAN JIANG

Institute of Information Science, Beijing Jiaotong University, Beijing 100044, China

Beijing Key Laboratory of Advanced Information Science and Network Technology, Beijing 100044, China

Search for more papers by this author

MANGUI LIANG

Institute of Information Science, Beijing Jiaotong University, Beijing 100044, China

Beijing Key Laboratory of Advanced Information Science and Network Technology, Beijing 100044, China

Corresponding author.

Search for more papers by this author

, and

DONGCHAO GUO

Institute of Information Science, Beijing Jiaotong University, Beijing 100044, China

Beijing Key Laboratory of Advanced Information Science and Network Technology, Beijing 100044, China

Search for more papers by this author

https://doi.org/10.1142/S0129183111016841Cited by:83 (Source: Crossref)

Abstract

Transmission efficiency and robustness are two important properties of various networks and a number of optimization strategies have been proposed recently. We propose a scheme to enhance the network performance by adding a small fraction of links (or edges) to the currently existing network topology, and we present four edge addition strategies for adding edges efficiently. We aim at minimizing the maximum node betweenness of any node in the network to improve its transmission efficiency, and a number of experiments on both Barabási–Albert (BA) and Erdös–Rényi (ER) networks have confirmed the effectiveness of our four edge addition strategies. Also, we evaluate the effect of some other measure metrics such as average path length, average betweenness, robustness, and degree distribution. Our work is very valuable and helpful for service providers to optimize their network performance by adding a small fraction of edges or to make good network planning on the existing network topology incrementally.

Keywords:

PACS: 89.75.Hc, 64.60.Ak

You currently do not have access to the full text article.
Recommend the journal to your library today!

References

P. Erdös and A. Rényi, Pulb. Math. Inst. Hung. Acad/Sci. 5, 17 (1960). Google Scholar
A. L. Barabási and R. Albert, Science 286, 509 (1999). Web of Science, ADS, Google Scholar
R. Albert, H. Jeong and A. L. Barabási, Nature 406, 387 (2000), DOI: 10.1038/35019019. Crossref, Web of Science, Google Scholar
M. Ericsson, M. G. C. Resende and P. M. Pardalos, J. Comb. Optim. 6, 299 (2002), DOI: 10.1023/A:1014852026591. Web of Science, Google Scholar
B. Fortz and M. Thorup, IEEE J. Sel. Areas Commun. 20, (2002), DOI: 10.1109/JSAC.2002.1003042. Google Scholar
T. N. Bui and C. Jones, Inf. Process. Lett. 42, 153 (1992), DOI: 10.1016/0020-0190(92)90140-Q. Web of Science, Google Scholar
B. Danilaet al., Phys. Rev. E 74, 046106 (2006), DOI: 10.1103/PhysRevE.74.046106. Web of Science, Google Scholar
Z. H. Guan, L. Chen and T. H. Qian, Physica A 390, 1131 (2011), DOI: 10.1016/j.physa.2010.10.002. Web of Science, ADS, Google Scholar
B. Danila, Y. D. Sun and K. E. Bassler, Phys. Rev. E 80, 066116 (2009), DOI: 10.1103/PhysRevE.80.066116. Web of Science, Google Scholar
G. Yanet al., Phys. Rev. E 73, 046108 (2006), DOI: 10.1103/PhysRevE.73.046108. Web of Science, Google Scholar
P. Echenique, J. Gomez-Gardenes and Y. Moreno, Phys. Rev. E 70, 056105 (2004), DOI: 10.1103/PhysRevE.70.056105. Web of Science, Google Scholar
M. Tanget al., Phys. Rev. E 80, 026114 (2009), DOI: 10.1103/PhysRevE.80.026114. Web of Science, Google Scholar
W. X. Wanget al., Phys. Rev. E 73, 026111 (2006), DOI: 10.1103/PhysRevE.73.026111. Web of Science, Google Scholar
B. Tadić, S. Thurner and G. J. Rodgers, Phys. Rev. E 69, 036102 (2004), DOI: 10.1103/PhysRevE.69.036102. Web of Science, Google Scholar
R. Guimeràet al., Phys. Rev. Lett. 89, 248701 (2002), DOI: 10.1103/PhysRevLett.89.248701. Web of Science, ADS, Google Scholar
V. Cholviet al., Phys. Rev. E 71, 035103(R) (2005), DOI: 10.1103/PhysRevE.71.035103. Web of Science, Google Scholar
G. Q. Zhang, D. Wang and G. J. Li, Phys. Rev. E 76, 017101 (2007), DOI: 10.1103/PhysRevE.76.017101. Web of Science, Google Scholar
P. Holme et al. , Phys. Rev. E 65 , 056109 . Web of Science, Google Scholar
B. Shargelet al., Phys. Rev. Lett. 90, 068701 (2003), DOI: 10.1103/PhysRevLett.90.068701. Web of Science, Google Scholar
G. Paulet al., Eur. Phys. J. B 38, 187 (2004), DOI: 10.1140/epjb/e2004-00112-3. Web of Science, ADS, Google Scholar
A. Valente , A. Sarkar and H. Stone , Proc. of the 5th International Conference on Complex Systems (ICCS) ( 2004 ) . Google Scholar
A. Beygelzimeret al., Physica A 357, 593 (2005). Web of Science, ADS, Google Scholar
H. J. Herrmannet al., J. Stat. Mech. P01027 (2011), DOI: 10.1088/1742-5468/2011/01/P01027. Google Scholar
C. M. Schneideret al., PNAS 108, 3838 (2011), DOI: 10.1073/pnas.1009440108. Web of Science, ADS, Google Scholar
P. Mahadevan, D. Krioukov, M. Fomenkov, B. Huffaker, X. Dimitropoulos, K. Claffy and A. Vahdat, The Internet AS-level topology: three data sources and one definitive metric, in: ACM SIGCOMM CCR (2005) . Google Scholar
M. E. J. Newman, Phys. Rev. E 64, 016132 (2001), DOI: 10.1103/PhysRevE.64.016132. Web of Science, Google Scholar
U. Brandes, J. Math. Soc. 25, 163 (2001), DOI: 10.1080/0022250X.2001.9990249. Web of Science, Google Scholar