IBM Israel Research Seminars

By now it is well known that the distribution of node degrees in the graph induced by the peering arrangements between Autonomous Systems (ASs) exhibits power laws. The most appealing mathematical model that attempts to explain the power-law degree distribution was suggested by Barabasi and Albert (the BA model). We introduce two new models that are extensions to the BA model: the ``Incremental Edge Addition" (InEd) model, and the ``Super-Linear Preferential Attachment" (SLiP) model. We prove that both our models are more successful in matching the power-law exponent, in producing leaves, and in producing a large dense core.

Beyond mathematical analysis, we have also implemented our models as a synthetic network generator we call Tang (Tel Aviv Network Generator). Experimentation with Tang shows that the networks it produces are more realistic than those generated by other network generators.

Joint work with Sagy Bar and Avishai Wool.

About the Speaker
Mira is a Ph.D. candidate in Computer Science and Engineering at Tel Aviv University. Her primary field of research is Internet Topology and Complex Networks. Mira started her academic career with a B.Sc. in Mathematics from the Hebrew University and an MSc in Computer Science. Her thesis explored Coloring problems on Interval Graphs. Her current research in Internet Topology and Complex Networks includes the analysis of new models for the AS Graph, where she has developed tools and measurements to capture the underling organizing principles of the AS Graph in quantitative terms.
In addition for her interest in Internet Topology and Complex Networks Mira is also working on Private Computation, Property Testing, Hardness of Approximation, Graph Theory, and Combinatorics.