### 10 releases

0.1.10 | Nov 16, 2023 |
---|---|

0.1.9 | Jan 30, 2023 |

0.1.8 | Oct 31, 2022 |

0.1.6 | Jul 6, 2022 |

0.1.2 | Sep 17, 2020 |

#**338** in Data structures

**471** downloads per month

**MIT**license

260KB

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 `-`f1`-``3` `|` 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 JSON-encoded features mean:

: average betweenness centrality.`bet_cent`

: average clustering coefficient.`clust_coef`

: average eigenvector centrality.`evcent`

: {k}-core count.`num_``{`k_cores`}`

: {k}-truss count.`num_``{`k_trusses`}`

: number of connected components.`num_connected_components`

: number of edges.`num_edges`

: number of nodes in largest connected component.`size_of_largest_cc`

### 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 non-core nodes 3 and 4
- both non-core 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 non-core 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

. The executable should show up in `cargo`` build`

.`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

for meaning of each option.`./target/debug/clique_miner`` --`help

See the CONTRIBUTING file for how to help out.

## License

Dachshund is MIT licensed, as found in the LICENSE file.

#### Dependencies

~10MB

~183K SLoC