Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

remove np random generators for memory reasons #361

Closed
maximelucas opened this issue May 15, 2023 · 1 comment · Fixed by #597
Closed

remove np random generators for memory reasons #361

maximelucas opened this issue May 15, 2023 · 1 comment · Fixed by #597
Labels
good first issue Good for newcomers

Comments

@maximelucas
Copy link
Collaborator

maximelucas commented May 15, 2023

@maximelucas The combinatorial explosion of the mask array makes it impossible to use in some scenarios: e.g.

>>> import xgi
>>> xgi.random_hypergraph(1000, order=5, ps=[1e-12])  # => should create a network with ~1350 edges
numpy.core._exceptions._ArrayMemoryError: Unable to allocate 9.72 PiB for an array with shape (1368173298991500,) and data type float64

But that also has an easy solution of not pre-allocating mask:

import xgi
import numpy as np
import itertools

def random_hypergraph(N, ps, order=None, seed=None):
    rng = np.random.default_rng(seed)

    if order is not None:
        if len(ps) != 1:
            raise ValueError("ps must contain a single element if order is an int")

    if (np.any(np.array(ps) < 0)) or (np.any(np.array(ps) > 1)):
        raise ValueError("All elements of ps must be between 0 and 1 included.")

    nodes = range(N)
    hyperedges = []

    for i, p in enumerate(ps):

        if order is not None:
            d = order
        else:
            d = i + 1  # order, ps[0] is prob of edges (d=1)

        potential_edges = itertools.combinations(nodes, d + 1)
        edges_to_add = [e for e in potential_edges if rng.random() <= p]

        hyperedges += edges_to_add

    H = xgi.empty_hypergraph()
    H.add_nodes_from(nodes)
    H.add_edges_from(hyperedges)

    return H

This doesn't fail but this still takes $O({{N}\choose{m}})$ time to run.

Originally posted by @arashbm in #339 (comment)

Summary: go back to list comprehension rather than np.random()

@maximelucas maximelucas added the good first issue Good for newcomers label May 15, 2023
@arashbm
Copy link

arashbm commented May 15, 2023

You can also chain a generator of np.randoms of a few millions or so to potentially get the best of both worlds.

nwlandry added a commit that referenced this issue Sep 16, 2024
nwlandry added a commit that referenced this issue Sep 16, 2024
This reverts commit 28cbbf3.
nwlandry added a commit that referenced this issue Sep 16, 2024
nwlandry added a commit that referenced this issue Oct 16, 2024
* Add ability to generate ER hypergraphs without multiedges

* update

* Remove bad characters

* Fix #361

* Revert "Fix #361"

This reverts commit 28cbbf3.

* Fix #361

* Update test.yml

* fix non-multi-edge probability

* formatting

* Update random.py

* Update xgi/generators/uniform.py

Co-authored-by: Maxime Lucas <[email protected]>

* Update using-xgi.rst

* Response to review

* Update uniform.py

* Update xgi/generators/random.py

Co-authored-by: Maxime Lucas <[email protected]>

* Update xgi/generators/random.py

Co-authored-by: Maxime Lucas <[email protected]>

* Update xgi/generators/uniform.py

Co-authored-by: Maxime Lucas <[email protected]>

* Update xgi/generators/uniform.py

Co-authored-by: Maxime Lucas <[email protected]>

* Update xgi/generators/uniform.py

Co-authored-by: Maxime Lucas <[email protected]>

* Update xgi/generators/uniform.py

Co-authored-by: Maxime Lucas <[email protected]>

* Update xgi/generators/uniform.py

Co-authored-by: Maxime Lucas <[email protected]>

* Update xgi/generators/uniform.py

Co-authored-by: Maxime Lucas <[email protected]>

* updates

* Conditional API note (#595)

* Conditional API note

* Update api_reference.rst

* Remove bad characters

* Update random.py

* Update xgi/generators/random.py

Co-authored-by: Maxime Lucas <[email protected]>

* Update xgi/generators/random.py

Co-authored-by: Maxime Lucas <[email protected]>

* response to review

* updates

* Update random.py

* format

* Update random.py

* update docs

* add unit tests

* Fix test

* test different version

* fix test

* updates

* last additions

* update

* fix error

* unnecessary import

* add unit tests

* Update xgi/generators/random.py

Co-authored-by: Maxime Lucas <[email protected]>

* Update xgi/generators/random.py

Co-authored-by: Maxime Lucas <[email protected]>

* Update xgi/generators/random.py

Co-authored-by: Maxime Lucas <[email protected]>

* Update xgi/generators/random.py

Co-authored-by: Maxime Lucas <[email protected]>

---------

Co-authored-by: Maxime Lucas <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
good first issue Good for newcomers
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants