Skip to main content

Graph algorithms written in GraphBLAS and backend for NetworkX

Project description

GraphBLAS Algorithms
conda-forge pypi PyPI - Python Version License
Tests Coverage DOI Discord

graphblas-algorithms is a collection of GraphBLAS algorithms written using python-graphblas. It may be used directly or as an experimental backend to NetworkX.

Why use GraphBLAS Algorithms? Because it is fast, flexible, and familiar by using the NetworkX API.

Are we missing any algorithms that you want? Please let us know!
GraphBLAS vs NetworkX
GraphBLAS vs igraph

Installation

conda install -c conda-forge graphblas-algorithms
pip install graphblas-algorithms

Basic Usage

First, create a GraphBLAS Matrix.

import graphblas as gb

M = gb.Matrix.from_coo(
  [0, 0, 1, 2, 2, 3],
  [1, 3, 0, 0, 1, 2],
  [1., 2., 3., 4., 5., 6.],
  nrows=4, ncols=4, dtype='float32'
)

Next wrap the Matrix as ga.Graph.

import graphblas_algorithms as ga

G = ga.Graph(M)

Finally call an algorithm.

hubs, authorities = ga.hits(G)

When the result is a value per node, a gb.Vector will be returned. In the case of HITS, two Vectors are returned representing the hubs and authorities values.

Algorithms whose result is a subgraph will return ga.Graph.

Plugin for NetworkX

Dispatching to plugins is a new feature in Networkx 3.0. When both networkx and graphblas-algorithms are installed in an environment, calls to NetworkX algorithms can be dispatched to the equivalent version in graphblas-algorithms.

Dispatch Example

import networkx as nx
import graphblas_algorithms as ga

# Generate a random graph (5000 nodes, 1_000_000 edges)
G = nx.erdos_renyi_graph(5000, 0.08)

# Explicitly convert to ga.Graph
G2 = ga.Graph.from_networkx(G)

# Pass G2 to NetworkX's k_truss
T5 = nx.k_truss(G2, 5)

G2 is not a nx.Graph, but it does have an attribute __networkx_plugin__ = "graphblas". This tells NetworkX to dispatch the k_truss call to graphblas-algorithms. This link connection exists because graphblas-algorithms registers itself as a "networkx.plugin" entry point.

The result T5 is a ga.Graph representing the 5-truss structure of the original graph. To convert to a NetworkX Graph, use:

T5.to_networkx()

Note that even with the conversions to and from ga.Graph, this example still runs 10x faster than using the native NetworkX k-truss implementation. Speed improvements scale with graph size, so larger graphs will see an even larger speed-up relative to NetworkX.

Plugin Algorithms

The following NetworkX algorithms have been implemented by graphblas-algorithms and can be used following the dispatch pattern shown above.

graphblas_algorithms.nxapi
├── boundary
│   ├── edge_boundary
│   └── node_boundary
├── centrality
│   ├── degree_alg
│   │   ├── degree_centrality
│   │   ├── in_degree_centrality
│   │   └── out_degree_centrality
│   ├── eigenvector
│   │   └── eigenvector_centrality
│   └── katz
│       └── katz_centrality
├── cluster
│   ├── average_clustering
│   ├── clustering
│   ├── generalized_degree
│   ├── square_clustering
│   ├── transitivity
│   └── triangles
├── community
│   └── quality
│       ├── inter_community_edges
│       └── intra_community_edges
├── components
│   ├── connected
│   │   ├── is_connected
│   │   └── node_connected_component
│   └── weakly_connected
│       └── is_weakly_connected
├── core
│   └── k_truss
├── cuts
│   ├── boundary_expansion
│   ├── conductance
│   ├── cut_size
│   ├── edge_expansion
│   ├── mixing_expansion
│   ├── node_expansion
│   ├── normalized_cut_size
│   └── volume
├── dag
│   ├── ancestors
│   └── descendants
├── dominating
│   └── is_dominating_set
├── efficiency_measures
│   └── efficiency
├── generators
│   └── ego
│       └── ego_graph
├── isolate
│   ├── is_isolate
│   ├── isolates
│   └── number_of_isolates
├── isomorphism
│   └── isomorph
│       ├── fast_could_be_isomorphic
│       └── faster_could_be_isomorphic
├── linalg
│   ├── bethehessianmatrix
│   │   └── bethe_hessian_matrix
│   ├── graphmatrix
│   │   └── adjacency_matrix
│   ├── laplacianmatrix
│   │   ├── laplacian_matrix
│   │   └── normalized_laplacian_matrix
│   └── modularitymatrix
│       ├── directed_modularity_matrix
│       └── modularity_matrix
├── link_analysis
│   ├── hits_alg
│   │   └── hits
│   └── pagerank_alg
│       ├── google_matrix
│       └── pagerank
├── lowest_common_ancestors
│   └── lowest_common_ancestor
├── operators
│   ├── binary
│   │   ├── compose
│   │   ├── difference
│   │   ├── disjoint_union
│   │   ├── full_join
│   │   ├── intersection
│   │   ├── symmetric_difference
│   │   └── union
│   └── unary
│       ├── complement
│       └── reverse
├── reciprocity
│   ├── overall_reciprocity
│   └── reciprocity
├── regular
│   ├── is_k_regular
│   └── is_regular
├── shortest_paths
│   ├── dense
│   │   ├── floyd_warshall
│   │   ├── floyd_warshall_numpy
│   │   └── floyd_warshall_predecessor_and_distance
│   ├── generic
│   │   └── has_path
│   ├── unweighted
│   │   ├── all_pairs_shortest_path_length
│   │   ├── single_source_shortest_path_length
│   │   └── single_target_shortest_path_length
│   └── weighted
│       ├── all_pairs_bellman_ford_path_length
│       ├── bellman_ford_path
│       ├── bellman_ford_path_length
│       ├── negative_edge_cycle
│       └── single_source_bellman_ford_path_length
├── simple_paths
│   └── is_simple_path
├── smetric
│   └── s_metric
├── structuralholes
│   └── mutual_weight
├── tournament
│   ├── is_tournament
│   ├── score_sequence
│   └── tournament_matrix
├── traversal
│   └── breadth_first_search
│       ├── bfs_layers
│       └── descendants_at_distance
└── triads
    └── is_triad

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

graphblas-algorithms-2023.10.0.tar.gz (68.0 kB view details)

Uploaded Source

Built Distribution

graphblas_algorithms-2023.10.0-py3-none-any.whl (97.9 kB view details)

Uploaded Python 3

File details

Details for the file graphblas-algorithms-2023.10.0.tar.gz.

File metadata

File hashes

Hashes for graphblas-algorithms-2023.10.0.tar.gz
Algorithm Hash digest
SHA256 059be9faaef2697a1d29e4fd50ae11a6ee6d91bb6c1c341f6138121aca4b40f4
MD5 4efcc0c4e09419a2bf9934d14e4d2e4f
BLAKE2b-256 0b4899579d5bfc2f6a9f8b30dac947c00a41eb9a410d04605c66f0e2bc9bae73

See more details on using hashes here.

File details

Details for the file graphblas_algorithms-2023.10.0-py3-none-any.whl.

File metadata

File hashes

Hashes for graphblas_algorithms-2023.10.0-py3-none-any.whl
Algorithm Hash digest
SHA256 75f135a756c4a3a52796a5967d0c9131af03596937c2f918cba6d9b714666fa3
MD5 7fd71eac02dd65545e85fdc21ab008cc
BLAKE2b-256 fcd7c98979217e0bc3fb066601eba26c75ec865b9560a4700a99c1cb87fe4dc4

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page