Add stochastic block model generator #1200
Conversation
Pull Request Test Coverage Report for Build 9238376817Details
💛 - Coveralls |
There was a problem hiding this comment.
I haven't had time to give a complete review but:
- Complexity seems fine, if you think there are improvements you can open an issue after we merge this one
- We should probably accept numpy arrays as an input, I have a feeling that is the datatype people would use for a matrix
src/random_graph.rs
Outdated
| /// Arguments: | ||
| /// | ||
| /// :param list[int] blocks: Block membership (between 0 and B-1) of each node. | ||
| /// :param list[list[float]] probabilities: B x B matrix that contains the |
There was a problem hiding this comment.
This can probably be a 2d numpy.array
| Adds new function ``sbm_random_graph`` to the rustworkx-core module | ||
| ``rustworkx_core::generators`` that samples a graph from the stochastic | ||
| block model. |
There was a problem hiding this comment.
You can add drawings of some example graphs if you want, check
for an example
By the way, for links you want:
|
|
I wasn't sure how dependencies versions should be handled so I added ndarray directly with cargo. Docs hyperlinks are fixed. I also changed the first argument for the community sizes instead of membership. It makes more sense and is what networkx uses. |
I will tweak ndarray to use Cargo workspaces |
This naive O(n^2) algorithm might not be the fastest possible algorithm since there exists a O(m) algorithm for G(n, p), but I didn't see how to generalize it for non square "sub-matrices". I'm not convinced that networkx's implementation with iterators is actually more efficient.
I was unable to add hyperlinks to the G(n, p) generator in rustworkx and rustworkx-core. Is there a way to do so?