Comparing the structure of power-law graphs and the Internet AS graph Export

@inproceedings{citeulike:1040533, abstract = {In this work we devise algorithmic techniques to compare the interconnection structure of the Internet AS graph with that of graphs produced by topology generators that match the power-law degree distribution of the AS graph. We are guided by the existing notion that nodes in the AS graph can be placed in tiers with the resulting graph having an hierarchical structure. Our techniques are based on identifying graph nodes at each tier, decomposing the graph by removing such nodes and their incident edges, and thus explicitly revealing the interconnection structure of the graph. We define quantitative metrics to analyze and compare the decomposition of synthetic power-law graphs with the Internet-AS graph. Through experiments, we observe qualitative similarities in the decomposition structure of the different families of power-law graphs and explain any quantitative differences based on their generative models. We believe our approach provides insight into the interconnection structure of the AS graph and finds continuing applications in evaluating the representativeness of synthetic topology generators.}, author = {Jaiswal, S. and Rosenberg, A. L. and Towsley, D.}, citeulike-article-id = {1040533}, citeulike-linkout-0 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1348119}, journal = {Network Protocols, 2004. ICNP 2004. Proceedings of the 12th IEEE International Conference on}, keywords = {as, graph, graphs, internet, law, power, topology}, pages = {294--303}, posted-at = {2007-01-14 05:32:05}, priority = {0}, title = {Comparing the structure of power-law graphs and the Internet AS graph}, url = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1348119}, year = {2004} }

TY - CONF ID - citeulike:1040533 L3 - citeulike-article-id:1040533 N2 - In this work we devise algorithmic techniques to compare the interconnection structure of the Internet AS graph with that of graphs produced by topology generators that match the power-law degree distribution of the AS graph. We are guided by the existing notion that nodes in the AS graph can be placed in tiers with the resulting graph having an hierarchical structure. Our techniques are based on identifying graph nodes at each tier, decomposing the graph by removing such nodes and their incident edges, and thus explicitly revealing the interconnection structure of the graph. We define quantitative metrics to analyze and compare the decomposition of synthetic power-law graphs with the Internet-AS graph. Through experiments, we observe qualitative similarities in the decomposition structure of the different families of power-law graphs and explain any quantitative differences based on their generative models. We believe our approach provides insight into the interconnection structure of the AS graph and finds continuing applications in evaluating the representativeness of synthetic topology generators. JF - Network Protocols, 2004. ICNP 2004. Proceedings of the 12th IEEE International Conference on EP - 303 TI - Comparing the structure of power-law graphs and the Internet AS graph SP - 294 KW - as KW - graph KW - graphs KW - internet KW - law KW - power KW - topology AU - Jaiswal, S AU - Rosenberg, AL AU - Towsley, D PY - 2004/// UR - http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1348119 ER -