littleballoffur: A Python repository from krackers

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

Please look at the Documentation 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 and the new datasets useful in your research, please consider citing the following paper:

>@misc{littleballoffur2020,
       title={Little Ball of Fur: A Python Library for Graph Subsampling},
       author={Benedek Rozemberczki and Oliver Kiss},
       year={2020},
}

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 Random Walk Sampling on a Watts-Strogatz graph:

import networkx as nx
from littleballoffur import RandomWalkSampler

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

sampler = RandomWalkSampler()

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

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)
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)
Common Neighbor Aware Random Walk Sampler from Li et al.: Walking with Perception: Efficient Random Walk Sampling via Common Neighbor Awareness (ICDE 2019)

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 examples script.

$ python examples.py

krackers/littleballoffur