{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreidqnwx3hmsa3eim3bmqhymqdmqhwefgllc62bdmmdig7qfacez5wa",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mk7swgosamo2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.21504v1",
  "publishedAt": "2026-04-24T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Gianlorenzo D'Angelo",
    "Riccardo Michielan"
  ],
  "textContent": "**Authors:** Gianlorenzo D'Angelo, Riccardo Michielan\n\nWe study the efficient generation of random graphs with a prescribed expected degree sequence, focusing on rank-1 inhomogeneous models in which vertices are assigned weights and edges are drawn independently with probabilities proportional to the product of endpoint weights. We adopt a temporal viewpoint, adding edges to the graph one at a time up to a fixed time horizon, and allowing for self-loops or duplicate edges in the first stage. Then, the simple projection of the resulting multigraph recovers exactly the simple Norros--Reittu random graph, whose expected degrees match the prescribed targets under mild conditions. Building on this representation, we develop an exact generator based on \\textit{edge-arrivals} for expected-degree random graphs with running time $O(n+m)$, where $m$ is the number of generated edges, and hence proportional to the output size. This removes the typical vertex sorting used by widely-used fast generator algorithms based on \\textit{edge-skipping} for rank-1 expected-degree models, which leads to a total running time of $O(n \\log n + m)$. In addition, our algorithm is simpler than those in the literature, easy to implement, and very flexible, thus opening up to extensions to directed and temporal random graphs, generalization to higher-order structures, and improvements through parallelization.",
  "title": "Efficient generation of expected-degree graphs via edge-arrivals"
}