Parallelism in simulation and modeling of scale-free complex networks

摘要

Evolution and structure of very large networks has attracted considerable attention in recent years. In this paper we study a possibility to simulate stochastic processes which move edges in a network leading to a scale-free structure. Scale-free networks are characterized by a "fat-tail" degree distribution with considerably higher presence of so called hubs - nodes with very high degree. To understand and predict very large networks it is important to study the possibility of parallel simulation. We consider a class of stochastic processes which keeps the number of edges in the network constant called equilibrium networks. This class is characterized by a preferential selection where the edge destinations are chosen according to a preferential function f(k) which depends on the node degree k. For this class of stochastic processes we prove that it is difficult if not impossible to design an exact parallel algorithm if the function f(k) is monotonous with an injective derivative. However, in the important case where f(k) is linear we present a fully scalable algorithm with almost linear speedup. The experimental results confirm the linear scalability on a large processor cluster.