Abstract
Recently, there has been substantial interest in the study of various random networks as mathematical models of complex systems. As real-life complex systems grow larger, the ability to generate progressively large random networks becomes all the more important. This motivates the need for efficient parallel algorithms for generating such networks. Naïve parallelization of sequential algorithms for generating random networks is inefficient due to inherent dependencies among the edges and the possibility of creating duplicate (parallel) edges. In this article, we present message passing interface-based distributed memory parallel algorithms for generating random scale-free networks using the preferential-attachment model. Our algorithms are experimentally verified to scale very well to a large number of processing elements (PEs), providing near-linear speedups. The algorithms have been exercised with regard to scale and speed to generate scale-free networks with one trillion edges in 6 minutes using 1,000 PEs.
| Original language | English |
|---|---|
| Article number | 13 |
| Journal | ACM Transactions on Parallel Computing |
| Volume | 7 |
| Issue number | 2 |
| DOIs | |
| State | Published - May 16 2020 |
Funding
This article has been authored by UT-Battelle, LLC, under contract DE-AC05-00OR22725 with the U.S. Department of Energy. Accordingly, the United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a non-exclusive, paid-up, irrevocable, worldwide license to publish or reproduce the published form of this manuscript, or allow others to do so, for United States Government purposes. This work has been partially supported by NSF DIBBs Grant No. ACI-1443054, DTRA Grant No. HDTRA1-11-1-0016, DTRA CNIMS Contract No. HDTRA1-11-D-0016-0001, NSF NetSE Grant No. CNS-1011769, NSF BIGDATA Grant No. IIS-1633028, and ORNL Post Doctoral Education Investment No. 3410PDED. Authors’ addresses: M. Alam and K. S. Perumalla, Oak Ridge National Laboratory, 1 Bethel Valley Road, Oak Ridge, TN, 37831, USA; emails: {alamm,perumallaks}@ornl.gov; M. Khan, Texas A&M University-Kingsville, 700 University Blvd., Kingsville, TX, 78363, USA; email: [email protected]; M. Marathe, Network Systems Science and Advanced Computing Division, Biocomplexity Institute and Initiative & Department of Computer Science, University of Virginia, Research Park Blvd., Charlottesville, VA, 22904, USA; email: [email protected]. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. © 2020 Association for Computing Machinery. 2329-4949/2020/05-ART13 $15.00 https://doi.org/10.1145/3391446
| Funders | Funder number |
|---|---|
| National Science Foundation | ACI-1443054, HDTRA1-11-D-0016-0001, CNS-1011769, 1931628 |
| U.S. Department of Energy |
Keywords
- Network science
- distributed algorithms
- preferential attachment
- random networks