Accurately and quickly calculating the weighted spectral distribution

详细信息    查看全文

• 作者：Bo Jiao ; Yuan-ping Nie ; Jian-mai Shi ; Gang Lu ; Ying Zhou…
• 关键词：Weighted spectral distribution ; Graph structure ; Complex network ; Normalized Laplacian spectrum
• 刊名：Telecommunication Systems
• 出版年：2016
• 出版时间：May 2016
• 年：2016
• 卷：62
• 期：1
• 页码：231-243
• 全文大小：1,580 KB
• 参考文献：1.Stanford large network dataset collection (2014). http://​snap.​stanford.​edu/​data/​ . Accessed Dec 2014.
  2.Latapy, M. (2011). Complex networks. Computer Communications, 34(5), 607–608.CrossRef
  3.Brouwer, A. E., & Haemers, W. H. (2012). Spectra of graphs. New York: Springer.CrossRef
  4.Cvetkovic, D., & Simic, S. K. (2012). Spectral graph theory in computer science. The IPSI BgD Transactions on Advanced Research, 8(2), 35–42.
  5.Cvetkovic, D. (2012). Spectral recognition of graphs. Yugoslav Journal of Operations Research, 22(2), 145–161.CrossRef
  6.Fay, D., Haddadi, H., Thomason, A., et al. (2010). Weighted spectral distribution for Internet topology analysis: Theory and applications. IEEE/ACM Transactions on networking, 18(1), 164–176.CrossRef
  7.Jamakovic, A., & Van Mieghem, P. (2008). On the robustness of complex networks by using the algebraic connectivity., NETWORKING 2008 ad hoc and sensor networks, wireless networks, next generation internet Berlin, Heidelberg: Springer.CrossRef
  8.Sydney, A., Scoglio, C., & Gruenbacher, D. (2013). Optimizing algebraic connectivity by edge rewiring. Applied Mathematics and Computation, 219, 5465–5479.CrossRef
  9.Wu, J., Barahona, M., Tan, Y. J., et al. (2010). Natural connectivity of complex networks. Chinese Physics Letters, 27(7), 078902.CrossRef
  10.Wu, J., Deng, H. Z., & Tan, Y. J. (2010). Spectral measure of robustness for internet topology. In: Proceedings of the 3rd IEEE International Conference on Computer Science and Information Technology (ICCSIT), 6, 50–54.
  11.Wu, J., Barahona, M., Tan, Y. J., et al. (2011). Robustness of regular ring lattices based on natural connectivity. International Journal of Systems Science, 42(7), 1085–1092.CrossRef
  12.Wu, J., Barahona, M., Tan, Y. J., et al. (2011). Spectral measure of structural robustness in complex networks. IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans, 41(6), 1244–1252.CrossRef
  13.Wu, J., Barahona, M., Tan, Y. J., et al. (2012). Robustness of random graphs based on graph spectra. Chaos: An Interdisciplinary. Journal of Nonlinear Science, 22(4), 043101.
  14.Arsic, B., Cvetkovic, D., Simic, S. K., et al. (2012). Graph spectral techniques in computer sciences. Applicable Analysis and Discrete Mathematics, 6(1), 1–30.CrossRef
  15.Cetinkaya, E. K., Alenazi, M. J. F., & Rohrer, J. P. ( 2012). Topology connectivity analysis of Internet infrastructure using graph spectra. In: Proceedings of the 4th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), pp. 752–758.
  16.Cetinkaya, E. K., Alenazi, M. J. F., Peck, A. M., et al. (2015). Multilevel resilience analysis of transportation and communication networks. Telecommunication Systems. doi:10.​1007/​s11235-015-9991-y .
  17.Edwards, B., Hofmeyr, S., & Stelle, G., et al. (2012). Internet topology over time. arXiv preprint arXiv:​1202.​3993 .
  18.Clegg, R. G., Di Cairano-Gilfedder, C., & Zhou, S. (2010). A critical look at power law modelling of the Internet. Computer Communications, 33(3), 259–268.CrossRef
  19.Zhou, S. (2006). Understanding the evolution dynamics of Internet topology. Physical Review E, 74(1), 016124.CrossRef
  20.Fay, D., Haddadi, H., Uhlig, S., et al. (2011). Discriminating graphs through spectral projections. Computer Networks, 55(15), 3458–3468.CrossRef
  21.Haddadi, H., Fay, D., & Uhlig, S., et al. (2008). Tuning topology generators using spectral distributions. In SPEC International Performance Evaluation Workshop Darmstadt, Germany. Lecture Notes in Computer Science, 5119, 154–173.
  22.Haddadi, H., Fay, D., & Jamakovic, A., et al. (2009). On the importance of local connectivity for Internet topology models. In 21st International Teletraffic Congress, ITC 21, Paris, France, September, 1–8.
  23.Barabasi, A. L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286(5439), 509–512.CrossRef
  24.Zhou, S., & Mondragn, R. J. (2004). Accurately modeling the Internet topology. Physical Review E, 70(6), 066108.CrossRef
  25.Jiao, B., Zhou, Y., & Du, J., et al. (2014). Study on the stability of the topology interactive growth mechanism using graph spectra. IET Communications. doi:10.​1049/​iet-com.​2014.​0183 .
  26.Shafi, S. Y., Arcak, M., & Ghaoui, L. E. (2012). Graph weight allocation to meet Laplacian spectral constraints. IEEE Transactions on Automatic Control, 57(7), 1872–1877.CrossRef
  27.LDL factorization (2014). http://​www.​mathworks.​com/​help/​dsp/​ref/​ldlfactorization​.​html . Accessed Dec 2014.
  28.Thomason, A. G. (1987). Pseudo-random graphs. North-Holland Mathematical study, 144, 307–331.CrossRef
  29.Chung, F. R. K., Graham, R. L., & Wilson, R. M. (1989). Quasi-random graphs. Combinatorica, 9(4), 345–362.CrossRef
  30.Chung, F. R. K. (1997). Spectral graph theory. Providence: American Mathematical Society.
  31.Eigenvalues and eigenvectors (2014). http://​www.​mathworks.​cn/​help/​matlab/​ref/​eig.​html . Accessed Dec 2014.
  32.Leskovec, J., Kleinberg, J., & Faloutsos, C. (2005). Graphs over time: Densification laws, shrinking diameters and possible explanations. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD).
  33.Leskovec, J., Lang, K. J., & Dasgupta, A., et al. (2009). Supplementary material: Large-scale community structure in social and information networks. http://​www.​cs.​cmu.​edu/​~jure/​pub/​ncp/​ncp-supp.​pdf . Accessed July 2015.
  34.Siganos, G., Faloutsos, M., Faloutsos, P., et al. (2003). Power laws and the AS-level Internet topology. IEEE/ACM Transactions on Networking, 11(4), 514–524.CrossRef
  35.Winick, J., & Jamin, S. (2002). Inet-3.0: Internet topology generator, Tech. rep. cse-tr-456-02, University of Michigan.
  36.Johnson, D. B. (1975). Finding all the elementary circuits of a directed graph. SIAM Journal on Computing, 4(1), 77–84.CrossRef
  37.Mateti, P., & Deo, N. (1976). On algorithms for enumerating all circuits of a graph. SIAM Journal on Computing, 5(1), 90–99.CrossRef
  38.Schott, R., & Staples, S. (2010). On the complexity of cycle enumeration using Zeons. HAL Id: hal-00567889.
  39.Marino, A. (2014). Algorithms for biological graphs: Analysis and enumeration. Bulletin of EATCS, 3(114).
  40.Pagh, R., & Silvestri, F. (2013). The input/output complexity of triangle enumeration. arXiv preprint arXiv:​1312.​0723 .
  41.Foucault Welles, B., Van Devender, A., & Contractor, N. (2010). Is a friend a friend?: Investigating the structure of friendship networks in virtual worlds. CHI’10 Extended Abstracts on Human Factors in Computing Systems. ACM, 4027–4032.
  42.Berry, J. W., Hendrickson, B., LaViolette, R. A., et al. (2011). Tolerating the community detection resolution limit with edge weighting. Physical Review E, 83(5), 056119.CrossRef
  
• 作者单位：Bo Jiao (1)
  Yuan-ping Nie (2)
  Jian-mai Shi (3)
  Gang Lu (1)
  Ying Zhou (1)
  Jing Du (1)
  
  1. Luoyang Electronic Equipment Test Center, Luoyang, 471003, China
  2. College of Computer, National University of Defense Technology, Changsha, 410073, China
  3. College of Information Systems and Management, National University of Defense Technology, Changsha, 410073, China
  
• 刊物类别：Business and Economics
• 刊物主题：Economics
  Business Information Systems
  Computer Communication Networks
  Artificial Intelligence and Robotics
  Probability Theory and Stochastic Processes
  
• 出版者：Springer Netherlands
• ISSN：1572-9451

文摘

The weighted spectral distribution (WSD) is a measure defined on the normalized Laplacian spectrum. It can be used for comparing complex networks with different sizes (number of nodes) and provides a sensitive discrimination of the structural robustness of complex networks. In this paper, we design an algorithm for the accurate calculation of the WSD in large-scale complex networks by utilizing characteristics of the graph structure. As an extension to Sylvester’s Law of Inertia for the calculation of the WSD based on spectral characteristics, our algorithm exhibits a higher time efficiency when applied to large-scale complex networks.