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
An easier way to build neural search on the cloud

Jina is geared towards building search systems for any kind of data, including text, images, audio, video and many more. With the modular design & multi-layer abstraction, you can leverage the effici

Jina AI 17k Jan 01, 2023
A Python-based application demonstrating various search algorithms, namely Depth-First Search (DFS), Breadth-First Search (BFS), and A* Search (Manhattan Distance Heuristic)

A Python-based application demonstrating various search algorithms, namely Depth-First Search (DFS), Breadth-First Search (BFS), and the A* Search (using the Manhattan Distance Heuristic)

17 Aug 14, 2022
Kaggler is a Python package for lightweight online machine learning algorithms and utility functions for ETL and data analysis.

Kaggler is a Python package for lightweight online machine learning algorithms and utility functions for ETL and data analysis. It is distributed under the MIT License.

Jeong-Yoon Lee 720 Dec 25, 2022
A chain of stores, 10 different stores and 50 different requests a 3-month demand forecast for its product.

Demand-Forecasting Business Problem A chain of stores, 10 different stores and 50 different requests a 3-month demand forecast for its product.

Ayşe Nur Türkaslan 3 Mar 06, 2022
This repo implements a Topological SLAM: Deep Visual Odometry with Long Term Place Recognition (Loop Closure Detection)

This repo implements a topological SLAM system. Deep Visual Odometry (DF-VO) and Visual Place Recognition are combined to form the topological SLAM system.

Best of Australian Centre for Robotic Vision (ACRV) 32 Jun 23, 2022
PyCaret is an open-source, low-code machine learning library in Python that automates machine learning workflows.

An open-source, low-code machine learning library in Python 🚀 Version 2.3.5 out now! Check out the release notes here. Official • Docs • Install • Tu

PyCaret 6.7k Jan 08, 2023
using Machine Learning Algorithm to classification AppleStore application

AppleStore-classification-with-Machine-learning-Algo- using Machine Learning Algorithm to classification AppleStore application. the first step : 1: p

Mohammed Hussien 2 May 02, 2022
Datetimes for Humans™

Maya: Datetimes for Humans™ Datetimes are very frustrating to work with in Python, especially when dealing with different locales on different systems

Timo Furrer 3.4k Dec 28, 2022
Crunchdao - Python API for the Crunchdao machine learning tournament

Python API for the Crunchdao machine learning tournament Interact with the Crunc

3 Jan 19, 2022
A Python step-by-step primer for Machine Learning and Optimization

early-ML Presentation General Machine Learning tutorials A Python step-by-step primer for Machine Learning and Optimization This github repository gat

Dimitri Bettebghor 8 Dec 01, 2022
A fast, scalable, high performance Gradient Boosting on Decision Trees library, used for ranking, classification, regression and other machine learning tasks for Python, R, Java, C++. Supports computation on CPU and GPU.

Website | Documentation | Tutorials | Installation | Release Notes CatBoost is a machine learning method based on gradient boosting over decision tree

CatBoost 6.9k Jan 05, 2023
Bayesian Modeling and Computation in Python

Bayesian Modeling and Computation in Python Open access and Code This repository contains the open access version of the text and the code examples in

Bayesian Modeling and Computation in Python 339 Jan 02, 2023
Tool for producing high quality forecasts for time series data that has multiple seasonality with linear or non-linear growth.

Prophet: Automatic Forecasting Procedure Prophet is a procedure for forecasting time series data based on an additive model where non-linear trends ar

Facebook 15.4k Jan 07, 2023
A python library for easy manipulation and forecasting of time series.

Time Series Made Easy in Python darts is a python library for easy manipulation and forecasting of time series. It contains a variety of models, from

Unit8 5.2k Jan 04, 2023
The Simpsons and Machine Learning: What makes an Episode Great?

The Simpsons and Machine Learning: What makes an Episode Great? Check out my Medium article on this! PROBLEM: The Simpsons has had a decline in qualit

1 Nov 02, 2021
InfiniteBoost: building infinite ensembles with gradient descent

InfiniteBoost Code for a paper InfiniteBoost: building infinite ensembles with gradient descent (arXiv:1706.01109). A. Rogozhnikov, T. Likhomanenko De

Alex Rogozhnikov 183 Jan 03, 2023
ETNA is an easy-to-use time series forecasting framework.

ETNA is an easy-to-use time series forecasting framework. It includes built in toolkits for time series preprocessing, feature generation, a variety of predictive models with unified interface - from

Tinkoff.AI 674 Jan 07, 2023
Free MLOps course from DataTalks.Club

MLOps Zoomcamp Our MLOps Zoomcamp course Sign up here: https://airtable.com/shrCb8y6eTbPKwSTL (it's not automated, you will not receive an email immed

DataTalksClub 4.6k Dec 31, 2022
DeepSpeed is a deep learning optimization library that makes distributed training easy, efficient, and effective.

DeepSpeed is a deep learning optimization library that makes distributed training easy, efficient, and effective. 10x Larger Models 10x Faster Trainin

Microsoft 8.4k Dec 30, 2022
My capstone project for Udacity's Machine Learning Nanodegree

MLND-Capstone My capstone project for Udacity's Machine Learning Nanodegree Lane Detection with Deep Learning In this project, I use a deep learning-b

Michael Virgo 407 Dec 12, 2022