The research goal is to develop a large-scale agent-based simulation environment to support implementations of Internet simulation applications. The Small Worlds (SW) graphs are used to model Web sites and social networks of Internet users. Each vertex represents the identity of a simple agent. In order to cope with scalability issues, we have to consider distributed parallel processing. The focus of this paper is to present two parallel-distributed algorithms for the construction of a particular type of SW graph called β-model. The first algorithm serializes the graph construction, while the second constructs the graph in parallel.