Fast Generation of Scale Free Networks with Directed Arcs
 Lookup NU author(s)
 Huqui Zhang
 Professor Aad van Moorsel




Author(s)   Zhang H, van Moorsel A 
Publication type   Report 
Series Title   School of Computing Science Technical Report Series 
Year   2009 
Legacy Date   February 2009 
Report Number   1138 
Pages   14 



Full text is available for this publication: 




To evaluate peertopeer systems through discreteevent simulation, one needs to be able to generate sufficiently large networks of nodes that exhibit the desired properties, such as the scalefree 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. 



Institution   School of Computing Science, University of Newcastle upon Tyne 
Place Published   Newcastle upon Tyne 
URL   http://www.cs.ncl.ac.uk/publications/trs/papers/1138.pdf 
Actions   
Share   