Fast Generation of Scale Free Networks with Directed Arcs

  1. Lookup NU author(s)
  2. Huqui Zhang
  3. Professor Aad van Moorsel
Author(s)Zhang H, van Moorsel A
Editor(s)Bradley, J.T.
Publication type Conference Proceedings (inc. Abstract)
Conference NameComputer Performance Engineering: 6th European Performance Engineering Workshop (EPEW)
Conference LocationLondon, UK
Year of Conference2009
Legacy Date9-10 July 2009
Volume5652
Pages131-148
Series TitleLecture Notes in Computer Science
ISBN9783642029233
Full text for this publication is not currently held within this repository. Alternative links are provided below where available.
To evaluate peer-to-peer systems through discrete-event simulation, one needs to be able to generate sufficiently large networks of nodes that exhibit the desired properties, such as the scale-free nature of the connectivity graph. In applications such as the web of trust or analysis of hyperlink structures, the direction of the arcs between two nodes is relevant and one therefore generates directed graphs. In this paper we introduce model to generate directed scale free graphs without multiple arcs between the same pair of nodes and loops. This model is based on existing models that allows multiple arcs and loops, but considerably more challenging to implement in an efficient manner. We therefore design and implement a set of algorithms and compare them with respect to CPU and memory use, in terms of both theoretical complexity analysis and experimental results. We will show through experiments that with the fastest algorithms networks with a million or more nodes can generated in mere seconds.
PublisherSpringer-Verlag
URLhttp://dx.doi.org/10.1007/978-3-642-02924-0_11
DOI10.1007/978-3-642-02924-0_11
ActionsLink to this publication
Library holdingsSearch Newcastle University Library for this item