<commit_before>#CONCUSS: Combatting Network Complexity Using Structural Sparsity

CONCUSS is a software tool for large scale graph analytics.  The efficiency and scalability of CONCUSS come from exploiting the underlying [structure and sparsity](/docs/background.md) of the data.  It allows users to count the number of occurences of a specific pattern within a graph (i.e. subgraph isomorphism counting).  These counts are a building block for more complicated scientific analysis, such as motif counting and graphlet degree signature creation.  

## Command line usage

    ./concuss.py [OPTIONS] graph pattern [config]

Count the number of subgraphs of "graph" which are isomorphic to "pattern".

Positional arguments:

* `graph` - filename of the host graph
* `pattern` - filename or basic pattern. Basic pattern specified as: `pattern_nameint` or `pattern_nameint,int`. The `int`s specify number of vertices. See example below.
* `config` - filename of the configuration settings (defaults to `config/default.cfg`)

Optional arguments:

* `-h, --help` - show help message and exit
* `-o [OUTPUT], --output [OUTPUT]` - filename of the result
* `-v, --verbose` - verbose output
* `-p, --profile` - profile function calls
* `-c [COLORING], --coloring [COLORING]` - filename of existing *p*-centered
  coloring.  When this option is not selected, CONCUSS will find a coloring itself
* `-C, --coloring-no-verify` - same as -c but do not verify correctness of existing coloring


Example command:

Using pattern file:
	
	./concuss.py testing/graphs/karate.txt testing/graphs/motifs/K3.txt

Using basic pattern:
	
	./concuss.py testing/graphs/karate.txt clique3
	
Example output:

	Number of occurrences of H in G: 270

This means that there are 270 isomorphisms of K3 (a triangle) in the karate network.  Since the triangle has 3 automorphisms, the karate network has 90 distinct triangles.

Using bipartite basic pattern:
	
	./concuss.py testing/graphs/karate.txt biclique2,2
	
Example output:
	
	Number of occurrences of H in G: 288
	
## Install and Software Requirements

CONCUSS requires a 64-bit operating system and Python 2.7.x interpreter (e.g. CPython or PyPy).  
Running the pipeline with PyPy typically decreases runtimes due to native function inlining. 

### Extra Dependencies

The main computations in CONCUSS do not require any additional libraries.

To import graph data in GraphML or GEXF format, the Beautiful Soup package is required.

	pip install beautifulsoup

For developers wishing to contribute to CONCUSS, the testing suite (see below) uses the NetworkX python package to verify the correctness of the counts.

	pip install networkx

## File Format Compatibilities 

CONCUSS supports reading data files for the host and pattern graphs in the following formats:

* Edgelist (.txt)
* GML (.gml)
* LEDA (.leda)
* GraphML (.graphml) (requires Beautiful Soup package)
* GEXF (.gexf) (requires Beautiful Soup package)
<commit_msg>Added section on basic patterns in README<commit_after>#CONCUSS: Combatting Network Complexity Using Structural Sparsity

CONCUSS is a software tool for large scale graph analytics.  The efficiency and scalability of CONCUSS come from exploiting the underlying [structure and sparsity](/docs/background.md) of the data.  It allows users to count the number of occurences of a specific pattern within a graph (i.e. subgraph isomorphism counting).  These counts are a building block for more complicated scientific analysis, such as motif counting and graphlet degree signature creation.  

## Command line usage

    ./concuss.py [OPTIONS] graph pattern [config]

Count the number of subgraphs of "graph" which are isomorphic to "pattern".

Positional arguments:

* `graph` - filename of the host graph
* `pattern` - filename or basic pattern. See basic patterns section below.
* `config` - filename of the configuration settings (defaults to `config/default.cfg`)

Optional arguments:

* `-h, --help` - show help message and exit
* `-o [OUTPUT], --output [OUTPUT]` - filename of the result
* `-v, --verbose` - verbose output
* `-p, --profile` - profile function calls
* `-c [COLORING], --coloring [COLORING]` - filename of existing *p*-centered
  coloring.  When this option is not selected, CONCUSS will find a coloring itself
* `-C, --coloring-no-verify` - same as -c but do not verify correctness of existing coloring


Example command:

Using pattern file:
	
	./concuss.py testing/graphs/karate.txt testing/graphs/motifs/K3.txt
	
Example output:

	Number of occurrences of H in G: 270

This means that there are 270 isomorphisms of K3 (a triangle) in the karate network.  Since the triangle has 3 automorphisms, the karate network has 90 distinct triangles.


### Basic patterns:

CONCUSS can be run by providing a basic pattern instead of a pattern file for the `pattern` argument in the execution command. All other positional and optional arguments remain unchanged.

Basic patterns provide a faster and simpler way of specifying patterns to search for in the graph.

We provide the following commonly used basic patterns:

**1-partite basic patterns:**

<code>clique <br> wheel <br> cycle <br> path <br> star</code>

Usage:

	.concuss.py {path_to_graph}/graph basicpattern|int
	
`|` represents concatenation. The `int` specifies the number of vertices in pattern.

Example command:

	./concuss.py testing/graphs/karate.txt star4
	
Example output:

	Number of occurrences of H in G: 6588

**Bi-partite basic patterns:**

<code> biclique</code>

Usage:

	.concuss.py {path_to_graph}/graph basicpattern|int,int
	
`|` represents concatenation. The `ints` specify the number of vertices in the first and second sets of the bi-partite pattern.

Example command:

	./concuss.py testing/graphs/karate.txt biclique2,2
	
Example output:

	Number of occurrences of H in G: 288

## Install and Software Requirements

CONCUSS requires a 64-bit operating system and Python 2.7.x interpreter (e.g. CPython or PyPy).  
Running the pipeline with PyPy typically decreases runtimes due to native function inlining. 

### Extra Dependencies

The main computations in CONCUSS do not require any additional libraries.

To import graph data in GraphML or GEXF format, the Beautiful Soup package is required.

	pip install beautifulsoup

For developers wishing to contribute to CONCUSS, the testing suite (see below) uses the NetworkX python package to verify the correctness of the counts.

	pip install networkx

## File Format Compatibilities 

CONCUSS supports reading data files for the host and pattern graphs in the following formats:

* Edgelist (.txt)
* GML (.gml)
* LEDA (.leda)
* GraphML (.graphml) (requires Beautiful Soup package)
* GEXF (.gexf) (requires Beautiful Soup package)

{'fraction_non_alphanumeric': 0.07313810019325108, 'fraction_numerical': 0.006986769733908132, 'mean_word_length': 4.23579766536965, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5227548', 'n_tokens_mistral': 1957, 'n_tokens_neox': 1767, 'n_words': 886}