Little Ball of Fur - A graph sampling extension library for NetworKit and NetworkX (CIKM 2020)

Overview

Version repo size Arxiv build badge coverage badge benedekrozemberczki


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

Edge Sampling

Exploration Based Sampling

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

Comments
  • change initial num of nodes formula

    change initial num of nodes formula

    to avoid having more initial nodes than the requested final number of nodes (when the final number of nodes requested is much smaller than the graph size).

    opened by bricaud 7
  • Error install dependency networkit==7.1

    Error install dependency networkit==7.1

    I didn't manage to install littleballoffur due to one of its dependency that seems outdated. It didn't work to install networkit==7.1 but I did manage to run its latest version. However, littleballoffur runs on networkit==7.1.

    I am using a Jupyter notebook as an environment and the following system specs: posix Darwin 21.4.0 3.8.12 (default, Mar 17 2022, 14:54:15) [Clang 13.0.0 (clang-1300.0.29.30)]

    The specific error output:

    Collecting networkit==7.1
      Using cached networkit-7.1.tar.gz (3.1 MB)
      Preparing metadata (setup.py) ... error
      error: subprocess-exited-with-error
      
      × python setup.py egg_info did not run successfully.
      │ exit code: 1
      ╰─> [2 lines of output]
          ERROR: No suitable compiler found. Install any of these:  ['g++', 'g++-8', 'g++-7', 'g++-6.1', 'g++-6', 'g++-5.3', 'g++-5.2', 'g++-5.1', 'g++-5', 'g++-4.9', 'g++-4.8', 'clang++', 'clang++-3.8', 'clang++-3.7']
          If using AppleClang, OpenMP might be needed. Install with: 'brew install libomp'
          [end of output]
      
      note: This error originates from a subprocess, and is likely not a problem with pip.
    error: metadata-generation-failed
    
    × Encountered error while generating package metadata.
    ╰─> See above for output.
    
    note: This is an issue with the package mentioned above, not pip.
    hint: See above for details.
    
    

    Please note that: libomp 14.0.0 is already installed and up-to-date.

    Is there some way I could install the library on networkit v10? Thanks a lot!

    opened by CristinBSE 6
  • Node attributes are not copied from original graph

    Node attributes are not copied from original graph

    Breadth and Depth First Search return me subgraphs without correct attributes on nodes/edges. Actually, I found that the dict containing those attributes has been completely deleted in the sampled graph. Is this a known issue? Is the sampler supposed to work in this way?

    opened by jungla88 6
  • Why can't I use the graph imported by nx.read_edgelist()

    Why can't I use the graph imported by nx.read_edgelist()

    graph = nx.read_edgelist("filename", nodetype=int, data=(("Weight", int),))

    error : AssertionError: Graph is not connected. why? 'graph' is a networkx graph

    opened by DeathSentence 5
  • Spikyball exploration sampling

    Spikyball exploration sampling

    You might find the change a bit invasive (understandable :) This adds a new family exploration sampling method (spikyball) described in the paper Spikyball sampling: Exploring large networks via an inhomogeneous filtered diffusion available here https://arxiv.org/abs/2010.11786 and submitted for publication in Combinatorial Optimization, Graph, and Network Algorithms journal. The version number has been increased in order not to collide with official releases of lbof, you might want to change this...

    opened by naspert 4
  • Assumptions on graph properties

    Assumptions on graph properties

    Hi there,

    I am wondering if it would be possible to relax some constrain the graph has to satisfy in order to start an exploration on it. In particular, the requirement of connectivity seems a bit strong to me. I think a graph sampling procedure could easily deal with such property, since in the case the graph is not connected the sampling could take place on the single connected components or the exploration could rely on the neighborhood of the current node explored. For node sampling strategies like BFS and DFS looks pretty natural to me, also for Random Walk Sampling (maybe the one with the restart probability could be a little tricky). Something strange could probably happen for edge sampling if the connectivity property is not satisfied. Do you see any possibility to extend little ball of fur to such type of graphs? What was the reason that bring you to assume the connectivity property for graphs?

    Thank you !

    opened by jungla88 3
  • Error importing DiffusionSampler

    Error importing DiffusionSampler

    Hello,

    First of all, thank you for your great work building this library. Great extension to NetworkX.

    I am facing an issue when trying to import the DiffusionSampler specifically. All the other samplers get imported just fine. However the DiffusionSampler raises import issue.

    I am using a Jupyter notebook as an environment.

    The specific error output:

    ---------------------------------------------------------------------------
    ImportError                               Traceback (most recent call last)
    <ipython-input-29-fbd222d9c756> in <module>
    ----> 1 from littleballoffur import DiffusionSampler
          2 
          3 
          4 model = DiffusionSampler()
          5 new_graph = model.sample(wd50k_connected_relabeled)
    
    ImportError: cannot import name 'DiffusionSampler' from 'littleballoffur'
    

    Is this replicable?

    Thank you in advance for looking into it.

    opened by DimitrisAlivas 3
  • ForestFireSampler throws exceptions for some seed values

    ForestFireSampler throws exceptions for some seed values

    Hi,

    I am trying to sample an undirected, connected graph of 5559 nodes and 10804 edges into a sample of 100 nodes. As I loop over the "creation of samples" part, I am altering the seed for the ForeFireSampler every time to obtain a different sample.

    E.g. seed_value = random.randint(1,2147483646) sampler = ForestFireSampler(100, seed=seed_value )

    However, for some runs I get an exception thrown, which is also reproducible. I assume it is related to specific seed values which the sampler doesn´t seem to be able to handle. An example is seed value 1176372277.

    Traceback (most recent call last): File "/project/topology_extraction.py", line 472, in abstraction_G = graph_sampling(S) File "/project/topology_extraction.py", line 234, in graph_sampling new_graph = sampler.sample(S) File "/usr/local/lib/python3.8/dist-packages/littleballoffur/exploration_sampling/forestfiresampler.py", line 74, in sample self._start_a_fire(graph) File "/usr/local/lib/python3.8/dist-packages/littleballoffur/exploration_sampling/forestfiresampler.py", line 47, in _start_a_fire top_node = node_queue.popleft() IndexError: pop from an empty deque

    Process finished with exit code 1

    I believe this is a bug in the library.

    Thanks! Nils

    opened by nrodday 3
  • Error in forest fire sampling

    Error in forest fire sampling

    Hi,

    While running the forest fire sampling code, I got an error that it is trying to pop an element from an empty deque.

    File "/opt/anaconda3/lib/python3.7/site-packages/littleballoffur/exploration_sampling/forestfiresampler.py", line 47, in _start_a_fire top_node = node_queue.popleft() IndexError: pop from an empty deque

    I am not sure if it was due to data or needs an empty/try-catch check or should it be handled by application code. Hence opened an issue.

    Thank you

    opened by apurvamulay 2
  • Broken link in Readme (readdthedocs)

    Broken link in Readme (readdthedocs)

    https://littleballoffur.readthedocs.io/en/latest/notes/introduction.html

    as of 2020-05-18 9:35 AM EDT, it says "sorry this page does not exist"

    opened by bbrewington 1
  • Error in line 254 _checking_indexing() of backend.py

    Error in line 254 _checking_indexing() of backend.py

    According to your code, once numeric_indices != node_indices, the error raises. Under my scenario, I constructed a networkx graph in which the indices of nodes start from '1', and then, the sampler did not work. This error will be triggered if the indices of nodes in a networkx graph do not start from '0'. I have to adjust my graph such that the indices of nodes start from '0' to utilize your samplers. I hope you can refine this part of the code to avoid someone else meets this problem.

    opened by Haoran-Young 0
Releases(v_20200)
Owner
Benedek Rozemberczki
Machine Learning Engineer at AstraZeneca and PhD candidate at The University of Edinburgh.
Benedek Rozemberczki
Apache Liminal is an end-to-end platform for data engineers & scientists, allowing them to build, train and deploy machine learning models in a robust and agile way

Apache Liminals goal is to operationalise the machine learning process, allowing data scientists to quickly transition from a successful experiment to an automated pipeline of model training, validat

The Apache Software Foundation 121 Dec 28, 2022
Predicting diabetes over a five year period using logistic regression and the Pima First-Nation dataset

Diabetes This script uses the Pima First Nations dataset to create a model to predict whether or not an individual will develop Diabetes Mellitus Type

1 Mar 28, 2022
Houseprices - Predict sales prices and practice feature engineering, RFs, and gradient boosting

House Prices - Advanced Regression Techniques Predicting House Prices with Machine Learning This project is build to enhance my knowledge about machin

1 Jan 01, 2022
A machine learning project that predicts the price of used cars in the UK

Car Price Prediction Image Credit: AA Cars Project Overview Scraped 3000 used cars data from AA Cars website using Python and BeautifulSoup. Cleaned t

Victor Umunna 7 Oct 13, 2022
Machine Learning from Scratch

Machine Learning from Scratch Author: Shengxuan Wang From: Oregon State University Content: Building Machine Learning model from Scratch, without usin

ShawnWang 0 Jul 05, 2022
Simple, light-weight config handling through python data classes with to/from JSON serialization/deserialization.

Simple but maybe too simple config management through python data classes. We use it for machine learning.

Eren Gölge 67 Nov 29, 2022
Scikit-Learn useful pre-defined Pipelines Hub

Scikit-Pipes Scikit-Learn useful pre-defined Pipelines Hub Usage: Install scikit-pipes It's advised to install sklearn-genetic using a virtual env, in

Rodrigo Arenas 1 Apr 26, 2022
A comprehensive set of fairness metrics for datasets and machine learning models, explanations for these metrics, and algorithms to mitigate bias in datasets and models.

AI Fairness 360 (AIF360) The AI Fairness 360 toolkit is an extensible open-source library containg techniques developed by the research community to h

1.9k Jan 06, 2023
Decentralized deep learning in PyTorch. Built to train models on thousands of volunteers across the world.

Hivemind: decentralized deep learning in PyTorch Hivemind is a PyTorch library to train large neural networks across the Internet. Its intended usage

1.3k Jan 08, 2023
A repository to work on Machine Learning course. Select an algorithm to classify writer's gender, of Hebrew texts.

MachineLearning A repository to work on Machine Learning course. Select an algorithm to classify writer's gender, of Hebrew texts. Tested algorithms:

Haim Adrian 1 Feb 01, 2022
Home repository for the Regularized Greedy Forest (RGF) library. It includes original implementation from the paper and multithreaded one written in C++, along with various language-specific wrappers.

Regularized Greedy Forest Regularized Greedy Forest (RGF) is a tree ensemble machine learning method described in this paper. RGF can deliver better r

RGF-team 363 Dec 14, 2022
AtsPy: Automated Time Series Models in Python (by @firmai)

Automated Time Series Models in Python (AtsPy) SSRN Report Easily develop state of the art time series models to forecast univariate data series. Simp

Derek Snow 465 Jan 02, 2023
XGBoost-Ray is a distributed backend for XGBoost, built on top of distributed computing framework Ray.

XGBoost-Ray is a distributed backend for XGBoost, built on top of distributed computing framework Ray.

92 Dec 14, 2022
A fast, distributed, high performance gradient boosting (GBT, GBDT, GBRT, GBM or MART) framework based on decision tree algorithms, used for ranking, classification and many other machine learning tasks.

Light Gradient Boosting Machine LightGBM is a gradient boosting framework that uses tree based learning algorithms. It is designed to be distributed a

Microsoft 14.5k Jan 07, 2023
Hierarchical Time Series Forecasting using Prophet

htsprophet Hierarchical Time Series Forecasting using Prophet Credit to Rob J. Hyndman and research partners as much of the code was developed with th

Collin Rooney 131 Dec 02, 2022
Winning solution for the Galaxy Challenge on Kaggle

Winning solution for the Galaxy Challenge on Kaggle

Sander Dieleman 483 Jan 02, 2023
Kubeflow is a machine learning (ML) toolkit that is dedicated to making deployments of ML workflows on Kubernetes simple, portable, and scalable.

SDK: Overview of the Kubeflow pipelines service Kubeflow is a machine learning (ML) toolkit that is dedicated to making deployments of ML workflows on

Kubeflow 3.1k Jan 06, 2023
This repository has datasets containing information of Uber pickups in NYC from April 2014 to September 2014 and January to June 2015. data Analysis , virtualization and some insights are gathered here

uber-pickups-analysis Data Source: https://www.kaggle.com/fivethirtyeight/uber-pickups-in-new-york-city Information about data set The dataset contain

B DEVA DEEKSHITH 1 Nov 03, 2021
SynapseML - an open source library to simplify the creation of scalable machine learning pipelines

Synapse Machine Learning SynapseML (previously MMLSpark) is an open source library to simplify the creation of scalable machine learning pipelines. Sy

Microsoft 3.9k Dec 30, 2022
AP1 Transcription Factor Binding Site Prediction

A machine learning project that predicted binding sites of AP1 transcription factor, using ChIP-Seq data and local DNA shape information.

1 Jan 21, 2022