Research ArticlesNo Access

THE APPLICATION OF SEMIDEFINITE INTEGER PROGRAMMING MODEL FOR THE SIMULATION OF COMPLEX NETWORKS

JIAO BO

Luoyang Electronic Equipment Test Center, Luoyang 471003, P. R. China

Corresponding author.

Search for more papers by this author

LU ZHI-YONG

Luoyang Electronic Equipment Test Center, Luoyang 471003, P. R. China

Search for more papers by this author

, and

SHI JIAN-MAI

School of Information System and Management, National University of Defense Technology, Changsha 410073, P. R. China

Search for more papers by this author

https://doi.org/10.1142/S0219525915500150Cited by:0 (Source: Crossref)

Abstract

Semidefinite integer programming model is an accurate tool for the structural design of networks. In this paper, we propose a semidefinite integer programming model with the constraints of spectral distributions and node degree distributions for the simulation of complex networks. Also, the feasible solutions and branch-and-bound solving algorithms of the model are designed. Based on eight metrics (e.g., spectral distribution, node degree distribution, clustering coefficients, etc.), the validity and practicability of the proposed method are illustrated.

Keywords:

References

S. Mukherjee, Adv. Complex Syst. 16(08), 1350031-1 (2013). Link, Web of Science, Google Scholar
J. Wang and G. Provan, Adv. Complex Syst. 12(01), 45 (2009). Link, Web of Science, Google Scholar
R. D. Smith, Adv. Complex Syst. 14(06), 905 (2011). Link, Web of Science, Google Scholar
Biological network, Available at http://en.wikipedia.org/wiki/Biological_network . Google Scholar
Y. Zhang, H. L. Zhang and B. X. Fang, J. Softw. 15(08), 1220 (2004). Google Scholar
China Internet Network Information Center, Statistical Report on Internet development in China (2011) . Google Scholar
Y. Tianet al., IEEE Trans. Parallel Distrib. Syst. 24(09), 1908 (2013). Crossref, Web of Science, Google Scholar
Y. Zhang, B. Fang and H. Zhang, ICIC Express Lett. 02(01), 29 (2008). Google Scholar
G. Zhang, G. Zhang and J. Fan, J.-China Inst. Commun. 28(10), 92 (2007). Web of Science, Google Scholar
Y. Zhang, B. X. Fang and H. L. Zhang, Chinese J. Comput. 31(04), 611 (2008). Crossref, Web of Science, Google Scholar
S. Zhou, G. Q. Zhang and G. Q. Zhang, IET Commun. 01(02), 209 (2007). Crossref, Web of Science, Google Scholar
B. M. Waxman, IEEE J. Sel. Areas Commun. 06(09), 1617 (1988). Crossref, Web of Science, Google Scholar
A. L. Barabasi and R. Albert, Sci. 286(5439), 509 (1999). Crossref, Web of Science, Google Scholar
T. Bu and D. Towsley , On distinguishing between Internet power law topology generators , Proc. IEEE Infocom ( New York, NY , 2002 ) . Google Scholar
S. Zhou and R. J. Mondragn, Phys. Rev. E 70(06), 066108 (2004). Crossref, Web of Science, Google Scholar
Winick, J. and Jamin, S., Inet-3.0: Internet topology generator, University of Michigan, Technical Report CSE- TR-456-02 (2002) . Google Scholar
E. W. Zegura, K. L. Calvert and M. J. Donahoo, IEEE/ACM Trans. Netw. 5(6), 770 (1997). Crossref, Web of Science, Google Scholar
M. Faloutsos, P. Faloutsos and C. Faloutsos, On power-law relationships of the Internet topology, Proc. ACM SIGCOMM 1999 (Cambridge, Massachusetts, United States, 1999) pp. 251–262. Google Scholar
H. Tangmunarunkitet al., Network topology generators: Degree-based vs. structural, Proc. ACM SIGCOMM (Pittsburgh, PA, 2002) pp. 147–159. Google Scholar
H. Tangmunarunkitet al., ACM SIGCOMM Comput. Commun. Rev. 32(1), 76 (2002). Crossref, Web of Science, Google Scholar
Haddadi, H., Fay, D., Jamakovic, A., Maennel, O., Moore, A. W., Mortier, R., Rio, M. and Uhlig, S., Beyond node degree: Evaluating AS topology models , arXiv:0807.2023 . Google Scholar
Butler, S. K., Eigenvalues and structures of graphs, Ph.D. thesis. University of California: San Diego (2008) . Google Scholar
S. Maletic , D. Horak and M. Rajkovic , Adv. Complex Syst. 15 ( ) , 1250055-1 ( 2012 ) . Link, Web of Science, Google Scholar
Y. Xu and Z. Wang, Approaches in evaluations of Internet topology modeling, The Second Int. Workshop on Education Technology and Computer Science (Wuhan, China, 2010) pp. 31–34. Google Scholar
W. Liuet al., Utility of algebraic connectivity metric in topology design of survivable networks, The 7th Int. Workshop on Design of Reliable Communication Networks (Washington DC, USA, 2009) pp. 131–138. Google Scholar
J. Wuet al., Chin. Phys. Lett. 27(07), 078902 (2010). Crossref, Web of Science, Google Scholar
J. Wuet al., J. Nonlinear Sci. 22(4), 043101 (2012). Crossref, Web of Science, Google Scholar
D. Fayet al., IEEE/ACM Trans. Netw. 18(01), 164 (2010). Crossref, Web of Science, Google Scholar
D. Vukadinovic , P. Huang and T. Erlebach , On the spectrum and structure of Internet topology graphs , Proc. Innovative Internet Community Systems ( 2002 ) . Google Scholar
E. K. Cetinkayaet al., Topology connectivity analysis of Internet infrastructure using graph spectra, The 4th Int. Workshop on Reliable Networks Design and Modeling (St. Petersburg, USA, 2012) pp. 752–758. Google Scholar
Laurent, M. and Rendl, F., Semidefinite programming and integer programing, Report PNA-R0210 (CWI, Amsterdam, April, 2002) . Google Scholar
S. Y. Shafi, M. Arcak and L. E. Ghaoui, IEEE Trans. Automatic Control 57(07), 1872 (2012). Crossref, Web of Science, Google Scholar
Datatang, Internet communication network topology of China, Available at http:// www.datatang.com/data/599# . Google Scholar
Huffaker, B., Fomenkov, M. and Claffy, K., Internet topology data comparison, Technical Report CAIDA, Available at http://www.caida.org/research/topology/ topo_comparison . Google Scholar
R. Oliveiraet al., ACM SIGMETRICS Perform. Eval. Rev. ACM 36(1), 217 (2008). Crossref, Google Scholar
Chang, H., Govindan, R., Jamin, S., Shenker, S. J. and Willinger, W., On inferring AS-level connectivity from BGP routing tables, Technical Report UM-CSE-TR-454-02, Available at http://topology.eecs.umich.edu (2002) . Google Scholar
H. Changet al., Comput. Netw. 44(6), 737 (2004). Crossref, Web of Science, Google Scholar
R. J. Horn , Matrix Analysis ( Cambridge University Press , New York , 1990 ) . Google Scholar
E. L. Lawler and D. E. Wood, Oper. Res. 14(4), 699 (1966). Crossref, Web of Science, Google Scholar
G. Siganoset al., IEEE/ACM Trans. Netw. 11(04), 514 (2003). Crossref, Web of Science, Google Scholar
A. Lakhinaet al., IEEE J. Sel. Areas Commun. 21(6), 934 (2003). Crossref, Web of Science, Google Scholar
P. Mahadevanet al., SIGCOMM Comput. Commun. Rev. 36(01), 17 (2006). Crossref, Web of Science, Google Scholar
F. J. Massey Jr., J. Am. Stat. Assoc. 46(253), 68 (1951). Crossref, Web of Science, Google Scholar