eliotwrobson / cynetdiff

A performance-focused library implementing algorithms for simulating network diffusion processes, written in Cython.

• 👋 Hi, I’m @eliotwrobson
• 👀 I’m interested in theoretical computer science!
• 🌱 I’m currently learning about geometry in high dimensions.
• 💞️ I’m looking to collaborate on papers.
• 📫 How to reach me: [email protected].

cynetdiff's Issues

Make methods more consistent

See title, make method names and return types more consistent. Also, add a built-in counter for the number of model iterations that have been executed.

Add `get_all_activated_nodes` function

See title, make it possible to read from the list of all activated nodes.

Update GitHub link

See title.

feat: Support for randomized activation

See title, add support for randomized activation of seeding in successive experiments (i.e. the overall seed set is fixed, but only sometimes activated in a run of the model). This model is a slight generalization of the independent cascade, described here: https://ieeexplore.ieee.org/abstract/document/10384250

Generalize activation probability function

See title. Instead of setting a single global default activation probability, pull from a set that's stored internally. This will improve performance in the trivalency case.

Add efficient parallelism

See title. The current parallel code doesn't perform well in benchmarks (for some unknown reason, probably something with the memory access being weird) and will be removed for the first alpha release. It should be possible to add back this functionality later on. Reference to a commit with this code on it:

https://github.com/eliotwrobson/ndleafy/blob/d21c628a591f186579a2776b5cbcd0bc6d661df3/src/ndleafy/models.pyx#L131

Update docs site

Update copyright and other typos on the docs site.

Bucket-filling Algorithm for Linear Threshold

The current way of simulating the linear threshold model is reasonably fast. However, it involves checking all in-neighbors of a node during each attempted activation. This can be simplified by using a "bucket-filling" algorithm, where each node is given a "bucket" and activated nodes fill the buckets of their neighbors upon activation. It should be possible then to remove the predecessors arrays and substantially save space.

Add introduction section to documentation

Add a section of the documentation that explains the models in-detail. This should accompany a running example of CyNetDiff code corresponding to the aspect of the model being described (i.e. the concept of activation, seeing which nodes get activated, etc).

Investigate Lazy Threshold Computation

For the linear threshold model, the thresholds are being computed in advance for every node in the entire graph. This is fine if most of the nodes in the graph will be visited, but for workloads where only very few nodes are visited, this is inefficient. See about changing to computing these thresholds lazily and what effect that has on performance.

Nicer error messages

See title. A lot of seg faults can be avoided.