benedekrozemberczki / Littleballoffur

Little Ball of Fur is a graph sampling extension library for Python.

Please look at the Documentation, relevant Paper, Promo video and External Resources.

Little Ball of Fur consists of methods that can sample from graph structured data. To put it simply it is a Swiss Army knife for graph sampling tasks. First, it includes a large variety of vertex, edge, and exploration sampling techniques. Second, it provides a unified application public interface which makes the application of sampling algorithms trivial for end-users. Implemented methods cover a wide range of networking (Networking, INFOCOM, SIGCOMM) and data mining (KDD, TKDD, ICDE) conferences, workshops, and pieces from prominent journals.

Citing

If you find Little Ball of Fur useful in your research, please consider citing the following paper:

@inproceedings{littleballoffur,
               title={{Little Ball of Fur: A Python Library for Graph Sampling}},
               author={Benedek Rozemberczki and Oliver Kiss and Rik Sarkar},
               year={2020},
               pages = {3133–3140},
               booktitle={Proceedings of the 29th ACM International Conference on Information and Knowledge Management (CIKM '20)},
               organization={ACM},
}

A simple example

Little Ball of Fur makes using modern graph subsampling techniques quite easy (see here for the accompanying tutorial). For example, this is all it takes to use Diffusion Sampling on a Watts-Strogatz graph:

import networkx as nx
from littleballoffur import DiffusionSampler

graph = nx.newman_watts_strogatz_graph(1000, 20, 0.05)

sampler = DiffusionSampler()

new_graph = sampler.sample(graph)

Methods included

In detail, the following sampling methods were implemented.

Node Sampling

• Degree Based Node Sampler from Adamic et al.: Search In Power-Law Networks (Physical Review E 2001)

• Random Node Sampler from Stumpf et al.: SubNets of Scale-Free Networks Are Not Scale-Free: Sampling Properties of Networks (PNAS 2005)

• PageRank Based Node Sampler from Leskovec et al.: Sampling From Large Graphs (KDD 2006)

Edge Sampling

• Random Edge Sampler from Krishnamurthy et al.: Reducing Large Internet Topologies for Faster Simulations (Networking 2005)

• Random Node-Edge Sampler from Krishnamurthy et al.: Reducing Large Internet Topologies for Faster Simulations (Networking 2005)

• Hybrid Node-Edge Sampler from Krishnamurthy et al.: Reducing Large Internet Topologies for Faster Simulations (Networking 2005)

• Random Edge Sampler with Induction from Ahmed et al.: Network Sampling: From Static to Streaming Graphs (TKDD 2013)

• Random Edge Sampler with Partial Induction from Ahmed et al.: Network Sampling: From Static to Streaming Graphs (TKDD 2013)

Exploration Based Sampling

• Snowball Sampler from Goodman: Snowball Sampling (The Annals of Mathematical Statistics 1961)

• Loop-Erased Random Walk Sampler from Wilson: Generating Random Spanning Trees More Quickly Than the Cover Time (STOC 1996)

• Forest Fire Sampler from Leskovec et al.: Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations (KDD 2005)

• Random Node-Neighbor Sampler from Leskovec et al.: Sampling From Large Graphs (KDD 2006)

• Random Walk With Restart Sampler from Leskovec et al.: Sampling From Large Graphs (KDD 2006)

• Metropolis Hastings Random Walk Sampler from Hubler et al.: Metropolis Algorithms for Representative Subgraph Sampling (ICDM 2008)

• Random Walk Sampler from Gjoka et al.: Walking in Facebook: A Case Study of Unbiased Sampling of OSNs (INFOCOM 2010)

• Random Walk With Jump Sampler from Ribeiro et al.: Estimating and Sampling Graphs with Multidimensional Random Walks (SIGCOMM 2010)

• Frontier Sampler from Ribeiro et al.: Estimating and Sampling Graphs with Multidimensional Random Walks (SIGCOMM 2010)

• Community Structure Expansion Sampler from Maiya et al.: Sampling Community Structure (WWW 2010)

• Non-Backtracking Random Walk Sampler from Lee et al.: Beyond Random Walk and Metropolis-Hastings Samplers: Why You Should Not Backtrack for Unbiased Graph Sampling (SIGMETRICS 2012)

• Randomized Depth First Search Sampler from Doerr et al.: Metric Convergence in Social Network Sampling (HotPlanet 2013)

• Randomized Breadth First Search Sampler from Doerr et al.: Metric Convergence in Social Network Sampling (HotPlanet 2013)

• Rejection Constrained Metropolis Hastings Random Walk Sampler from Li et al.: On Random Walk Based Graph Sampling (ICDE 2015)

• Circulated Neighbors Random Walk Sampler from Zhou et al.: Leveraging History for Faster Sampling of Online Social Networks (VLDB 2015)

• Shortest Path Sampler from Rezvanian et al.: Sampling Social Networks Using Shortest Paths (Physica A 2015)

• Diffusion Sampler from Rozemberczki et al.: Fast Sequence-Based Embedding with Diffusion Graphs (Complex Networks 2018)

• Diffusion Tree Sampler from Rozemberczki et al.: Fast Sequence-Based Embedding with Diffusion Graphs (Complex Networks 2018)

• Common Neighbor Aware Random Walk Sampler from Li et al.: Walking with Perception: Efficient Random Walk Sampling via Common Neighbor Awareness (ICDE 2019)

• Spiky Ball Sampler from Ricaud et al.: Spikyball Sampling: Exploring Large Networks via an Inhomogeneous Filtered Diffusion (Algorithms 2020)

Head over to our documentation to find out more about installation and data handling, a full list of implemented methods, and datasets. For a quick start, check out our examples.

If you notice anything unexpected, please open an issue and let us know. If you are missing a specific method, feel free to open a feature request. We are motivated to constantly make Little Ball of Fur even better.

Installation

Little Ball of Fur can be installed with the following pip command.

$ pip install littleballoffur

As we create new releases frequently, upgrading the package casually might be beneficial.

$ pip install littleballoffur --upgrade

Running examples

As part of the documentation we provide a number of use cases to show how to use various sampling techniques. These can accessed here with detailed explanations.

Besides the case studies we provide synthetic examples for each model. These can be tried out by running the scripts in the examples folder. You can try out the random walk sampling example by running:

$ cd examples
$ python ./exploration_sampling/randomwalk_sampler.py

Running tests

$ python setup.py test

License

• GNU General Public License v3.0