A random graph generation algorithm for the analysis of social networks. (July 2014)

• Record Type: Journal Article
• Authors: Morris, James F.; O'Neal, Jerome W.; Deckro, Richard F.
• Other Names: Snyder Scott D. guest-editor.; Taylor James M. guest-editor.
• Is Part Of: Journal of defense modeling and simulation. Volume 11:Number 3(2014:Jul.)
• Page Start: 265
• Page End: 276
• Publication Date: 2014-07
• Subjects: social network analysis -- random graph generation -- connected graphs -- assortative mixing -- clustering; Military art and science -- Computer simulation -- Periodicals; 355.0011305
• DOI: 10.1177/1548512912450370
• Languages: English
• ISSNs: 1548-5129

Abstract

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.