7 releases
0.1.7  Sep 20, 2022 

0.1.6  Jul 6, 2022 
0.1.5  Mar 23, 2022 
0.1.4  Sep 30, 2021 
0.1.1 

#124 in Data structures
649 downloads per month
250KB
5.5K
SLoC
Dachshund is a graph mining library written in Rust. It provides high performance data structures for multiple kinds of graphs, from simple undirected graphs to typed hypergraphs. Dachshund also provides algorithms for common tasks for graph mining and analysis, ranging from shortest paths to graph spectral analysis.
Examples
Graph featurizer
This application takes a list of graphs and featurizes it. For instance:
cat example.txt  cut s f13  target/debug/simple_graph_featurizer
The output will look like this:
0 {"bet_cent":1.2,"clust_coef":0.0,"evcent":0.868,"num_16_cores":0,"num_17_trusses":0,"num_2_cores":1,"num_3_trusses":0,"num_4_cores":0,"num_5_trusses":0,"num_8_cores":0,"num_9_trusses":0,"num_connected_components":1,"num_edges":5,"size_of_largest_cc":5}
What the various JSONencoded features mean:
bet_cent
: average betweenness centrality.clust_coef
: average clustering coefficient.evcent
: average eigenvector centrality.num_{k}_cores
: {k}core count.num_{k}_trusses
: {k}truss count.num_connected_components
: number of connected components.num_edges
: number of edges.size_of_largest_cc
: number of nodes in largest connected component.
Clique miner
This application finds the largest (quasi) cliques in a graph. For instance:
cargo build
cat example.txt  target/debug/clique_miner \
typespec '[["author", "published", "article"]]' \
beam_size 20 alpha 0.1 global_thresh 1.0 \
local_thresh 1.0 num_to_search 10 epochs 200 \
max_repeated_prior_scores 3 debug_mode false \
min_degree 1 core_type author long_format false
The output should look like this:
0 2 2 [1,2] [3,4] ["article","article"] 1 [1.0,1.0] [1.0]
What this means:
 there is a clique in the graph with ID 0 (only graph provided)
 the clique has core nodes (authors) 1 and 2
 the clique has noncore nodes 3 and 4
 both noncore nodes are articles
 the global density is 1 (all edges that could exist do exist)
 the local density for each of the two core nodes is 1.0
 the density for the one noncore type ("article") is 1.0
For a better explanation of what the various arguments mean:
target/debug/clique_miner help
To run various tests:
cargo test
Requirements
All requirements are handled by cargo.
Building Dachshund
Simply run cargo build
. The executable should show up in target/debug/clique_miner
.
How Dachshund works
The clique miner is the first dachshund application. It uses a beam search algorithm (plus some other optimizations) to find the largest (quasi)cliques it can find. It supports initialization with known clique solutions.
See ./target/debug/clique_miner help
for meaning of each option.
See the CONTRIBUTING file for how to help out.
License
Dachshund is MIT licensed, as found in the LICENSE file.
Dependencies
~9.5MB
~186K SLoC