1. Home
  2. Issues
  3. Volume 21, Issue 3 (2023): Special Issue: Advances in Network Data Science
  4. Generating General Preferential Attachme ...

Journal of Data Science


Generating General Preferential Attachment Networks with R Package wdnet
Volume 21, Issue 3 (2023): Special Issue: Advances in Network Data Science, pp. 538–556
Pub. online: 25 July 2023      Type: Computing In Data Science      Open accessOpen Access
Received
19 May 2023
Accepted
5 July 2023
Published
25 July 2023

Abstract

Preferential attachment (PA) network models have a wide range of applications in various scientific disciplines. Efficient generation of large-scale PA networks helps uncover their structural properties and facilitate the development of associated analytical methodologies. Existing software packages only provide limited functions for this purpose with restricted configurations and efficiency. We present a generic, user-friendly implementation of weighted, directed PA network generation with R package wdnet. The core algorithm is based on an efficient binary tree approach. The package further allows adding multiple edges at a time, heterogeneous reciprocal edges, and user-specified preference functions. The engine under the hood is implemented in C++. Usages of the package are illustrated with detailed explanation. A benchmark study shows that wdnet is efficient for generating general PA networks not available in other packages. In restricted settings that can be handled by existing packages, wdnet provides comparable efficiency.

Supplementary material

 Supplementary Materials
(1) The code used for benchmarks and the R Markdown source for the paper can be found at https://github.com/Yelie-Yuan/code-sharing/tree/main/generating-pa. (2) The development version of the package is available at https://gitlab.com/wdnetwork/wdnet.

References

 
Abbasi A, Hossain L, Leydesdorff L (2012). Betweenness centrality as a driver of preferential attachment in the evolution of research collaboration networks. Journal of Informatics, 6(3): 403–412.
 
Atwood J, Ribeiro B, Towsley D (2015). Efficient network generation under general preferential attachment. Computational Social Networks, 2(1): 7. https://doi.org/10.1186/s40649-015-0012-9
 
Barabási AL, Albert R (1999). Emergence of scaling in random networks. Science, 286(5439): 509–512. https://doi.org/10.1126/science.286.5439.509
 
Barrat A, Barthélemy M, Vespignani A (2004). Weighted evolving networks: Coupling topology and weight dynamics. Physical Review Letters, 92(22): 228701. https://doi.org/10.1103/PhysRevLett.92.228701
 
Bollobás B, Borgs C, Chayes J, Riordan O (2003). Directed scale-free graphs. In: SODA’03: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 132–139. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA.
 
Britton T (2020). Directed preferential attachment models: Limiting degree distributions and their tails. Journal of Applied Probability, 57(1): 122–136. https://doi.org/10.1017/jpr.2019.80
 
Capocci A, Servedio VDP, Colaiori F, Buriol LS, Donato D, Leonardi S, et al. (2006). Preferential attachment in the growth of social networks: The internet encyclopedia Wikipedia. Physical Review E, 74(3): 036116. https://doi.org/10.1103/PhysRevE.74.036116
 
Csardi G, Nepusz T (2006). The igraph software package for complex network research. InterJournal, Complex Systems, 1695.
 
Dong X, Castro L, Shaikh N (2020). fastnet: An R package for fast simulation and analysis of large-scale social networks. Journal of Statistical Software, 96(7): 1–23. https://doi.org/10.18637/jss.v096.i07
 
Eddelbuettel D, François R (2011). Rcpp: Seamless R and C++ integration. Journal of Statistical Software, 40(8): 1–18. https://doi.org/10.18637/jss.v040.i08
 
Erdös P, Rényi A (1959). On random graphs I. Publicationes Mathematicae Debrecen, 6: 290–297. https://doi.org/10.5486/PMD.1959.6.3-4.12
 
Gilbert EN (1959). Random graphs. Annals of Mathematical Statistics, 30(4): 1141–1144. https://doi.org/10.1214/aoms/1177706098
 
Hadian A, Nobari S, Minaei-Bidgoli B, Qu Q (2016). ROLL: Fast in-memory generation of gigantic scale-free networks. In: SIGMOD’16: Proceedings of the 2016 International Conference on Management of Data, 1829–1842. Association for Computing Machinery, New York, NY, USA.
 
Hagberg AA, Schult DA, Swart PJ (2008). Exploring network structure, dynamics, and function using NetworkX. In: Proceedings of the 7th Python in Science Conferencee (SciPy 2008), 11–15. Pasadena, CA, USA.
 
Kong JS, Sarshar N, Roychowdhury VP (2008). Experience versus talent shapes the structure of the web. Proceedings of the National Academy of Sciences, 105(37): 13724–13729. https://doi.org/10.1073/pnas.0805921105
 
Mahmoud HM (1992). Evolution of Random Search Trees. John Wiley & Sons, Hoboken, NJ, USA.
 
Mahmoud HM (2008). Pólya Urn Models. CRC Press, Boca Raton, FL, USA.
 
Momeni N, Rabbat MG (2015). Measuring the generalized friendship paradox in networks with quality-dependent connectivity. In: Complex Networks VI: Proceedings of the 6th Workshop on Complex Networks CompleNet 2015 (G Mangioni, F Simini, SM Uzzo, D Wang, eds.), 45–55. Springer-Verlag.
 
Pham T, Sheridan P, Shimodaira H (2020). PAFit: An R package for the non-parametric estimation of preferential attachment and node fitness in temporal complex networks. Journal of Statistical Software, 92(3): 1–30. https://doi.org/10.18637/jss.v092.i03
 
Ucar I (2022). RcppXPtrUtils: XPtr Add-Ons for ‘Rcpp’. R package version 0.1.2.
 
Wan P, Wang T, Davis RA, Resnick SI (2017). Fitting the linear preferential attachment model. Electronic Journal of Statistics, 11(2): 3738–3780.
 
Wang T, Resnick SI (2022a). Asymptotic dependence of in-and out-degrees in a preferential attachment model with reciprocity. Extremes, 25(3): 417–450. https://doi.org/10.1007/s10687-022-00439-5
 
Wang T, Resnick SI (2022b). Random networks with heterogeneous reciprocity. ArXiv e-prints.
 
Wang T, Resnick SI (2023). Poisson edge growth and preferential attachment networks. Methodology and Computing in Applied Probability, 25(1): 8. https://doi.org/10.1007/s11009-023-09997-y
 
Wang T, Yan J, Yuan Y, Zhang P (2022). Generating directed networks with predetermined assortativity measures. Statistics and Computing, 32(5): 91. https://doi.org/10.1007/s11222-022-10161-8
 
Yuan Y, Wang T, Yan J, Zhang P (2023). wdnet: Weighted and Directed Networks. University of Connecticut. R package version 1.1.1.
 
Yuan Y, Yan J, Zhang P (2021). Assortativity measures for weighted and directed networks. Journal of Complex Networks, 9(2): cnab017. https://doi.org/10.1093/comnet/cnab017
 
Physica A: Statistical Mechanics and its Applications

PDF XML
PDF XML

Copyright
2023 The Author(s). Published by the School of Statistics and the Center for Applied Statistics, Renmin University of China.
Open access article under the CC BY license.

Keywords
complete binary tree heterogeneous reciprocity multiple addition user-specified preference function weighted and directed network

Funding
Dr. Wang and Dr. Yan’s works were partially supported by the NSF grant DMS2210735.

Metrics
since February 2021
550

Article info
views

306

PDF
downloads


Share


RSS