SetMo

SetMo is a tool for enumerating and counting subgraphs (motifs) in networks. It uses two types of g-tries concurrently to both count and prevent-from-counting subgraphs.

Features

• Directed and undirected networks: Supports both directed and undirected graph analysis
• Forbidden subgraphs support: Filter out induced subgraphs, allowing to find exculively some subgraph families (e.g. trees, planar graphs, bipartite graphs, etc.)
• Property checking: Filter subgraphs by properties like average degree, vertex degree, articulation points
• Example networks: Some networks are provided for testing.

Requirements

• C++ compiler (g++ with C++17 support)
• make
• Standard build tools

Compilation

cd SetMo
make

Usage

Basic Usage

./SetMo -s <size> -i <input_network>

Required Arguments

• -s <size>: Subgraph size (motif size), must be at least 3
• -i <input_network>: Path to input network file

Optional Arguments

• -o <output_file>: Path to output file (default: results.html)
• -d: Network is directed (default: undirected)
• -q: Skip output file generation
• -fa <familiy>: Use forbidden subgraphs to search only specific subgraph families (details below)
• -fs <filename>: Use your own list of forbidden subgraphs (details below)
• -fsu <filename>: Use your own list of forbidden underlying subgraphs (details below)
• -<propertyChecker> <propertyValue>: Define values for subgraph properties (details below)

Subgraph Families

Find subgraphs of specific graph families using the -fa option:

./SetMo -s 4 -i Networks/power.txt -fa triangleFree

Available graph-family options:

• triangleFree
• tree
• planar
• bipartite
• clawFree
• cluster
• chordal

Custom Forbidden Subgraphs

You can use -fs to define forbidden subgraphs with custom files:

./SetMo -s 4 -i Networks/power.txt -fs Subgraphs/custom_forbidden_file.txt

For custom underlying forbidden subgraphs (i.e. forbidding an undirected subgraph on a directed network), you should use the -fsu argument.

./SetMo -s 4 -d -i Networks/kemail.txt -fsu Subgraphs/custom_underlying_forbidden_file.txt

The files should contain one adjacency matrix per line, for example:

0100101001010010
0100101101010110

Property Checkers

Filter subgraphs by graph properties:

• -maxAvgDegree <value>: Maximum average degree
• -minAvgDegree <value>: Minimum average degree
• -maxVertDegree <value>: Maximum vertex degree
• -minVertDegree <value>: Minimum vertex degree
• -maxArtPoints <value>: Maximum number of articulation points
• -minArtPoints <value>: Minimum number of articulation points

Example:

./SetMo -s 5 -i Networks/power.txt -maxVertDegree 3

Custom Subgraph Files

Explicitly enumerate the subgraphs you want to search by using the -gt <filepath> argument. The file should contain one adjacency matrix per line:

./SetMo -s 6 -i Networks/power.txt -gt Subgraphs/Sample/Power/order6.txt

If not specified, SetMo will assume all subgraphs are searchable, and filter from the set of all subgraphs.

Examples

Count all 4-node subgraphs in an undirected network:

./SetMo -s 4 -i Networks/power.txt

Count all 5-node subgraphs in a directed network:

./SetMo -s 5 -d -i Networks/neural.txt

Count all 6-node trees:

./SetMo -s 6 -i Networks/power.txt -fa tree

Count 7-node subgraphs, disallowing vertices to have a degree larger than 4:

./SetMo -s 7 -i Networks/power.txt -maxVertDegree 4

Count the 8-node subgraphs defined in a file, but only those that are claw-free:

./SetMo -s 8 -i Networks/power.txt -gt Subgraphs/Sample/Power/order8.txt -fa clawFree

Network Input Format

Networks should be in adjacency list format, 1 edge per line. Example networks are provided.

Example:

1 2
2 3
4 5
4 6
4 7
6 7

Output

SetMo generates a html file containing:

• Network statistics
• Subgraph enumeration results
• Frequency counts for each subgraph type
• Timing information