article

Weighted spectral distribution for internet topology analysis: theory and applications

Authors:

Andrew Thomason,

Andrew W. Moore,

Richard Mortier,

Almerima Jamakovic,

Miguel RioAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 18, Issue 1

Pages 164 - 176

https://doi.org/10.1109/TNET.2009.2022369

Published: 01 February 2010 Publication History

Abstract

Comparing graphs to determine the level of underlying structural similarity between them is a widely encountered problem in computer science. It is particularly relevant to the study of Internet topologies, such as the generation of synthetic topologies to represent the Internet's AS topology. We derive a new metric that enables exactly such a structural comparison: the weighted spectral distribution. We then apply this metric to three aspects of the study of the Internet's AS topology. i) We use it to quantify the effect of changing the mixing properties of a simple synthetic network generator. ii) We use this quantitative understanding to examine the evolution of the Internet's AS topology over approximately seven years, finding that the distinction between the Internet core and periphery has blurred over time. iii) We use the metric to derive optimal parameterizations of several widely used AS topology generators with respect to a large-scale measurement of the real AS topology.

References

[1]

H. Bunke, "Graph matching: Theoretical foundations, algorithms, and applications," in Proc. Int. Conf. Vision Interface, May 2000, pp. 82-88.

[2]

V. Kann, "On the approximability of the maximum common subgraph problem," in Proc. 9th Annu. Symp. Theor. Aspects Comput. Sci., 1992, pp. 377-388.

[3]

S. Hanna, "Representation and generation of plans using graph spectra," presented at the 6th Int. Space Syntax Symp., Istanbul, Turkey, 2007.

[4]

B. Luo and E. Hancock, "Structural graph matching using the em algorithm and singular value decomposition," IEEE Trans. Pattern Anal. Machine Intell., vol. 23, no. 10, pp. 1120-1136, Oct. 2001.

[5]

A. Ng, M. Jordan, and Y. Weiss, "On spectral clustering: analysis and an algorithm," in Advances in Neural Information Processing Systems 14, T. Dietterich, S. Becker, and Z. Ghahramani, Eds. Cambridge, MA: MIT Press, 2002.

[6]

H. Haddadi, D. Fay, S. Uhlig, A. Moore, R. Mortier, A. Jamakovic, and M. Rio, "Tuning topology generators using spectral distributions," in SPEC Int. Perform. Eval. Workshop, Darmstadt, Germany, 2008, vol. 5119, Lecture Notes in Computer Science, pp. 154-173.

[7]

C. Gkantsidis, M. Mihail, and E. Zegura, "Spectral analysis of Internet topologies," in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 2003, pp. 364-374.

[8]

S. Butler, Lecture Notes for Spectral Graph Theory. Tianjin, China,: Nankai Univ., 2006.

[9]

A. Jamakovic and S. Uhlig, "On the relationship between the algebraic connectivity and graph's robustness to node and link failures," in Proc. 3rd Conf. Next Gen. Internet Networks (EuroNGI), Trondheim, Norway, 2007, pp. 96-102.

[10]

D. Vukadinovic, P. Huang, and T. Erlebach, "On the spectrum and structure of Internet topology graphs," in Proc. 2nd Int. Workshop IICS, 2002, pp. 83-95.

[11]

J. Winick and S. Jamin, "Inet-3.0: Internet topology generator," Univ. of Michigan, Tech. Rep. CSE-TR-456-02, 2002.

[12]

S. V. N. Vishwanathan, K. Borgwardt, and N. Schraudolph, "Fast computation of graph kernels," in Advances in Neural Information Processing Systems 19 (NIPS 2006). Cambridge, MA: MIT Press, 2006.

[13]

L. Shyu, S.-Y. Lau, and P. Huang, "On the search of Internet as-level topology invariants," in Proc. IEEE GLOBECOM, San Francisco, CA, 2006, pp. 1-5.

[14]

M. Latapy and C. Magnien, "Complex network measurements: Estimating the relevance of observed properties," in Proc. IEEE INFOCOM, Apr. 2008, pp. 1660-1668.

[15]

X. Wang and D. Loguinov, "Wealth-based evolution model for the Internet as-level topology," in Proc. IEEE INFOCOM, Apr. 2006, pp. 1-11.

[16]

A. Wool and G. Sagie, "A clustering approach for exploring the Internet structure," in Proc. 23rd IEEE Conv. Electr. Electron. Eng. Israel, Sep. 2004, pp. 149-152.

[17]

Y. Li, J.-H. Cui, D. Maggiorini, and M. Faloutsos, "Characterizing and modelling clustering features in as-level Internet topology," in Proc. IEEE INFOCOM, Apr. 2008, pp. 271-275.

[18]

A. Seary and W. Richards, "Spectral methods for analyzing and visualizing networks: An introduction," in Dynamic Social Network Modeling and Analysis. Washington, DC: National Academies Press, 2003, pp. 209-228.

[19]

B. Nadler, S. Lafon, R. Coifman, and I. Kevrekidis, "Diffusion maps, spectral clustering and eigenfunctions of Fokker-Planck operators," in Proc. NIPS, 2005, pp. 955-962.

[20]

A. G. Thomason, "Pseudo-random graphs," in Random Graphs '85, ser. North-Holland Mathematical Studies. Amsterdam, The Netherlands: Elsevier, 1987, vol. 144, pp. 307-331.

[21]

F. R. K. Chung, R. L. Graham, and R. M. Wilson, "Pseudo-random graphs," Combinatorica, vol. 9, no. 4, pp. 345-362, 1989.

[22]

F. R. K. Chung, Spectral Graph Theory, ser. CBMS Regional Conference Series in Mathematics. Providence, RI: AMS, 1997.

[23]

R. Albert and A.-L. Barabasi, "Topology of evolving networks: local events and universality," Phys. Rev. Lett., vol. 85, p. 5234, 2000.

[24]

S. Butler, "Interlacing for weighted graphs using the normalized laplacian," Electron. J. Linear Algebra, vol. 16, pp. 90-98, 2007.

[25]

B. Huffaker, D. Andersen, E. Aben, M. Luckie, K. Claffy, and C. Shannon, "The Skitter AS links dataset," 2001-2007 {Online}. Available: http://www.caida.org/data/active/skitter_aslinks_dataset.xml/

[26]

R. Oliveira, B. Zhang, and L. Zhang, "Observing the evolution of Internet as topology," in Proc. ACM SIGCOMM, Kyoto, Japan, Aug. 2007, pp. 313-324.

[27]

R. Bush, J. Hiebert, O. Maennel, M. Roughan, and S. Uhlig, "Testing the reachability of (new) address space," in Proc. SIGCOMM Workshop INM, 2007, pp. 236-241.

[28]

A. Lakhina, J. Byers, M. Crovella, and P. Xie, "Sampling biases in IP topology measurements," in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 2003, pp. 332-341.

[29]

M. Newman, "Assortative mixing in networks," Phys. Rev. Lett., vol. 89, no. 20, pp. 871-898, 2002.

[30]

H. Haddadi, D. Fay, A. Jamakovic, O. Maennel, A. W. Moore, R. Mortier, M. Rio, and S. Uhlig, "Beyond node degree: Evaluating AS topology models," Computer Lab., Univ. of Cambridge, U.K., Tech. Rep. UCAM-CL-TR-725, 2008.

[31]

P. Gill, M. Arlitt, Z. Li, and A. Mahanti, "The flattening Internet topology: Natural evolution, unsightly barnacles or contrived collapse?," in Proc. PAM, Apr. 2008, pp. 1-10.

[32]

J. I. Alvarez-Hamelin, L. Dall'Asta, A. Barrat, and A. Vespignani, "k-core decomposition of Internet graphs: hierarchies, self-similarity and measurement biases," Netw. Hetero. Media, vol. 3, pp. 371-371, 2008.

[33]

E. W. Zegura, K. L. Calvert, and M. J. Donahoo, "A quantitative comparison of graph-based models for Internet topology," IEEE/ACM Trans. Netw., vol. 5, no. 6, pp. 770-783, Dec. 1997.

[34]

T. Bu and D. Towsley, "On distinguishing between Internet power law topology generators," in Proc. IEEE INFOCOM, New York, Jun. 2002, pp. 638-647.

[35]

B. M. Waxman, "Routing of multipoint connections," IEEE J. Sel. Areas Commun., vol. 6, pp. 1617-1622, Dec. 1988.

[36]

S. Zhou, "Characterising and modelling the Internet topology, the rich-club phenomenon and the PFP model," BT Technol. J., vol. 24, pp. 108-115, 2006.

[37]

P. Mahadevan, D. Krioukov, M. Fomenkov, X. Dimitropoulos, K. c. claffy, and A. Vahdat, "The Internet as-level topology: Three data sources and one definitive metric," Comput. Commun. Rev., vol. 36, no. 1, pp. 17-26, 2006.

[38]

J. Nelder and R. Mead, "A simplex method for function minimization," Comput. J., vol. 7, pp. 308-313, 1965.

[39]

J. Dennis and D. Woods, "Optimization in microcomputers: The nelder-meade simplex algorithm," in New Computing Environments: Microcomputers in Large-Scale Computing, A. Wouk, Ed. Philadelphia, PA: SIAM, 1987, pp. 116-122.

[40]

P. Zhu and C. Wilson, "A study of graph spectra for comparing graphs," presented at the 16th BMVC, Sep. 2005.

[41]

A. N. Kolmogorov and S. V. Fomin, Introductory Real Analysis. New York: Dover, 1975.

Cited By

Vashishtha RSingh ACherifi H(2022)A Community Detection Algorithm Using Random WalkComputational Data and Social Networks 10.1007/978-3-031-26303-3_20(227-235)Online publication date: 5-Dec-2022
https://dl.acm.org/doi/10.1007/978-3-031-26303-3_20
Ermakova TFabian BAlexander Fradin DGross S(2021)A Framework for Internet Connectivity Risk Assessment Based on Graph ModelsIEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology10.1145/3486622.3493980(576-581)Online publication date: 14-Dec-2021
https://dl.acm.org/doi/10.1145/3486622.3493980
Wang TLin HWang P(2017)Weighted-spectral clustering algorithm for detecting community structures in complex networksArtificial Intelligence Review10.1007/s10462-016-9488-447:4(463-483)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1007/s10462-016-9488-4
Show More Cited By

Index Terms

Weighted spectral distribution for internet topology analysis: theory and applications

Recommendations

TopGen - internet router-level topology generation based on technology constraints
Simutools '08: Proceedings of the 1st international conference on Simulation tools and techniques for communications, networks and systems & workshops

In order to realistically simulate algorithms or evaluate P2P overlay topologies, a detailed model of the underlying router topology is required. Since actively measuring this topology is extremely laborious and furthermore a waste of network resources, ...
Study of internet autonomous system interconnectivity from BGP routing tables
Special issue: In memroy of Olga Casals

Recently, several authors have proposed models based on power-laws to characterize Internet topologies. Most of these works use the BGP (Border Gateway Protocol) tables published by Oregon Route Views. The adjacency matrix containing AS (autonomous ...
Modeling internet topology dynamics

Despite the large number of papers on network topology modeling and inference, there still exists ambiguity about the real nature of the Internet AS and router level topology. While recent findings have illustrated the inaccuracies in maps inferred from ...

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 18, Issue 1

February 2010

332 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 February 2010

Revised: 23 March 2009

Received: 31 July 2008

Published in TON Volume 18, Issue 1

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
231
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Vashishtha RSingh ACherifi H(2022)A Community Detection Algorithm Using Random WalkComputational Data and Social Networks 10.1007/978-3-031-26303-3_20(227-235)Online publication date: 5-Dec-2022
https://dl.acm.org/doi/10.1007/978-3-031-26303-3_20
Ermakova TFabian BAlexander Fradin DGross S(2021)A Framework for Internet Connectivity Risk Assessment Based on Graph ModelsIEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology10.1145/3486622.3493980(576-581)Online publication date: 14-Dec-2021
https://dl.acm.org/doi/10.1145/3486622.3493980
Wang TLin HWang P(2017)Weighted-spectral clustering algorithm for detecting community structures in complex networksArtificial Intelligence Review10.1007/s10462-016-9488-447:4(463-483)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1007/s10462-016-9488-4
Wang YLi ZTyson GUhlig SXie G(2016)Design and Evaluation of the Optimal Cache Allocation for Content-Centric NetworkingIEEE Transactions on Computers10.1109/TC.2015.240984865:1(95-107)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1109/TC.2015.2409848
Jiao BShi J(2016)Graph perturbations and corresponding spectral changes in Internet topologiesComputer Communications10.1016/j.comcom.2015.11.01176:C(77-86)Online publication date: 15-Feb-2016
https://dl.acm.org/doi/10.1016/j.comcom.2015.11.011
Jiao BNie YShi JLu GZhou YDu J(2016)Accurately and quickly calculating the weighted spectral distributionTelecommunications Systems10.1007/s11235-015-0077-762:1(231-243)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1007/s11235-015-0077-7
Gardner MMay RBeard CMedhi D(2016)Determining Geographic Vulnerabilities Using a Novel Impact Based Resilience MetricJournal of Network and Systems Management10.1007/s10922-016-9383-y24:3(711-745)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1007/s10922-016-9383-y
Fay DHaddadi HSeto MWang HKling C(2016)An Exploration of Fetish Social Networks and CommunitiesProceedings of the 12th International Conference and School on Advances in Network Science - Volume 956410.1007/978-3-319-28361-6_17(195-204)Online publication date: 11-Jan-2016
https://dl.acm.org/doi/10.1007/978-3-319-28361-6_17
Çetinkaya EAlenazi MPeck ARohrer JSterbenz J(2015)Multilevel resilience analysis of transportation and communication networksTelecommunications Systems10.1007/s11235-015-9991-y60:4(515-537)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1007/s11235-015-9991-y
Kunegis JSizov SSchwagereit FFay DMunson EStrohmaier M(2012)Diversity dynamics in online networksProceedings of the 23rd ACM conference on Hypertext and social media10.1145/2309996.2310039(255-264)Online publication date: 25-Jun-2012
https://dl.acm.org/doi/10.1145/2309996.2310039
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents