fastRG (Q1354428): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Swh import (talk | contribs) SWHID from Software Heritage |
||||||||||||||
Property / Software Heritage ID | |||||||||||||||
Property / Software Heritage ID: swh:1:snp:116b37c6359f5af4eefe7f755c58841daa1fe849 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / Software Heritage ID: swh:1:snp:116b37c6359f5af4eefe7f755c58841daa1fe849 / qualifier | |||||||||||||||
Property / Software Heritage ID: swh:1:snp:116b37c6359f5af4eefe7f755c58841daa1fe849 / qualifier | |||||||||||||||
point in time: 15 October 2023
|
Latest revision as of 00:45, 14 March 2024
Sample Generalized Random Dot Product Graphs in Linear Time
Language | Label | Description | Also known as |
---|---|---|---|
English | fastRG |
Sample Generalized Random Dot Product Graphs in Linear Time |
Statements
21 August 2023
0 references
Samples generalized random product graphs, a generalization of a broad class of network models. Given matrices X, S, and Y with with non-negative entries, samples a matrix with expectation X S Y^T and independent Poisson or Bernoulli entries using the fastRG algorithm of Rohe et al. (2017) <https://www.jmlr.org/papers/v19/17-128.html>. The algorithm first samples the number of edges and then puts them down one-by-one. As a result it is O(m) where m is the number of edges, a dramatic improvement over element-wise algorithms that which require O(n^2) operations to sample a random graph, where n is the number of nodes.
0 references