Repository files navigation

GraphBLAS algorithms written in Python withPython-graphblas. We are trying to target the NetworkX API algorithms where possible.

conda install -c conda-forge graphblas-algorithms

pip install graphblas-algorithms

First, create a GraphBLAS Matrix.

importgraphblasasgbM=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 asga.Graph.

importgraphblas_algorithmsasgaG=ga.Graph(M)

Finally call an algorithm.

hubs,authorities=ga.hits(G)

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

Algorithms whose result is a subgraph will returnga.Graph.

Dispatching to plugins is a new feature in Networkx 3.0.When bothnetworkx andgraphblas-algorithms are installed in anenvironment, calls to NetworkX algorithms can be dispatched to theequivalent version ingraphblas-algorithms.

importnetworkxasnximportgraphblas_algorithmsasga# Generate a random graph (5000 nodes, 1_000_000 edges)G=nx.erdos_renyi_graph(5000,0.08)# Explicitly convert to ga.GraphG2=ga.Graph.from_networkx(G)# Pass G2 to NetworkX's k_trussT5=nx.k_truss(G2,5)

G2 is not anx.Graph, but it does have an attribute__networkx_plugin__ = "graphblas". This tells NetworkX todispatch the k_truss call to graphblas-algorithms. This linkconnection exists because graphblas-algorithms registersitself as a "networkx.plugin" entry point.

The resultT5 is aga.Graph representing the 5-truss structure of theoriginal graph. To convert to a NetworkX Graph, use:

T5.to_networkx()

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

The following NetworkX algorithms have been implementedby graphblas-algorithms and can be used following thedispatch pattern shown above.

• Boundary
  • edge_boundary
  • node_boundary
• Centrality
  • degree_centrality
  • eigenvector_centrality
  • in_degree_centrality
  • katz_centrality
  • out_degree_centrality
• Cluster
  • average_clustering
  • clustering
  • generalized_degree
  • square_clustering
  • transitivity
  • triangles
• Community
  • inter_community_edges
  • intra_community_edges
• 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
• Isolate
  • is_isolate
  • isolates
  • number_of_isolates
• Link Analysis
  • hits
  • pagerank
• Reciprocity
  • overall_reciprocity
  • reciprocity
• Regular
  • is_k_regular
  • is_regular
• Shortest Paths
  • floyd_warshall
  • floyd_warshall_predecessor_and_distance
  • single_source_bellman_ford_path_length
  • all_pairs_bellman_ford_path_length
  • has_path
• Simple Paths
  • is_simple_path
• S Metric
  • s_metric
• Structural Holes
  • mutual_weight
• Tournament
  • is_tournament
  • score_sequence
  • tournament_matrix
• Triads
  • is_triad