Affiliations: Computer Science Department, Athens University of
Economics and Business, Patision 76, 10434 Athens, Greece. spathari@aueb.gr,
fountalis@aueb.gr, sideri@aueb.gr | Computer Science Department, University of California,
Berkeley, USA. christos@cs.berkeley.edu
Note: [] Address for correspondence: Departmrnt of Computer Science,
Athens University of Economics and Business, Patision 76, 10434 Athens, Atiki,
Greece
Abstract: We introduce and evaluate several new models of network growth. Our
models are extensions of the FKP model, modifying and improving it in various
dimensions. In all these models nodes arrive one by one, and each node is
connected to previous nodes by optimizing a trade-off between a geometric
objective ("last mile cost") and a topological
objective ("position in the network"). Our new models
differ from the original FKP model in directions inspired by the real Internet:
two or more edges are attached to each arriving node (while the FKP model
produces a tree); these edges are chosen according to various criteria such as
robustness; edges may be added to the network between old nodes; or only
certain "fertile" nodes (an attribute that changes
dynamically) are capable of attracting new edges. We evaluate these models, and
compare them with the graph of the Internet's autonomous systems,
with respect to a suite of many test parameters (such as average degree, power
law exponent, and local clustering rank) proposed in the literature; to this
end we have developed the network generation and measurement system Pandora.
Keywords: Internet topology, power law, scale-free graphs, network generators, networkmodeling and simulation, complex networks
