A random graph generation algorithm for the analysis of social networks

Social network analysis (SNA) is a rapidly growing field with numerous applications in industry and government. However, the field still lacks means to generate random social networks with certain desired properties, thus inhibiting their ability to test new SNA algorithms and metrics. Available random graph generation algorithms suffer from tendencies to generate disconnected graphs and sometimes induce undesirable network properties. In this paper, we present an algorithm, the prescribed node degree, connected graph (PNDCG) algorithm, designed to generate weakly connected social networks. Extensions to the PNDCG algorithm allow one to create random graphs that control the clustering coefficient and degree correlation within the generated networks. Empirical test results demonstrate the capability of the PNDCG algorithm to produce networks with the desired properties.