Skip to content

Main Classes

dean geckt edited this page Oct 28, 2024 · 6 revisions

Enumerator

The enumerator is in charge of enumerating (counting) all subgraphs of a given network (it could be the input network or a random network).

The enumerator is implemented in an abstract class (sub_graphs_abc.py) via the class SubGraphsABC, this allows different algorithm implementations.

This class has only 1 mandatory method to implement: search_sub_graphs which returns an SubGraphSearchResult object. This object contains a “fsl” - a ‘frequent subgraph list’ implemented as a dictionary where each key is the subgraph canonical id and the value is its frequency. In addition it also contains a fully mapped fsl, where the value is a list of tuples, representing the actual subgraphs found.

SubGraphsABC as well as its implementations are located under /subgraphs. Each implementation is a different python class which is incharge of its own logic.

To create a new enumeration algorithm one should create a new python class, inherit from SubGraphsABC and implement its methods. Then to use it in the main.py program you need to add a new enum (in types.py) to SubGraphAlgoName and use it (in main.py) to point at your new class.

Lastly, you need to add a new option to --sub_graph_algorithm argument, also in main.py.

The algorithms we have already implemented are described fully in Data-structures, with links to relevant sources, papers, etc.

Randomizer

The Randomizer is in charge of generating random networks based on a given input. It is also implemented as an abstract class: NetworkRandomizer. Its constructor has a single input - the input Network, and has only a single abstract method: generate, which receives the number of networks it has to generate, and returns a list of DiGraph, which is a raw networkx type.

The NetworkRandomizer and its implementations are located under /random_networks and described fully in Data-structures.

Similarly to the Enumerator class, in order to create new randomizer logics one need to create a new python class and inherit NetworkRandomizer and implement generate.

Next you have to extend types.py with a new RandomGeneratorAlgoName and add a new option to argument (in main.py) --randomizer.

Note that this class does not enumerate the subgraphs of each generated graph, main.py handles this logic and sends the generated networks to the enumerator chosen via the arguments.

Statistical significance

To determine whether a detected subgraph is a motif or not we check its significance against the generated random networks. This logic is implemented as a single python class: MotifCriteria, located in motif_criteria.py.

It has a single public method - is_motif which receives a candidate Motif - an object containing how many times this subgraph occurred in the real network (n_real) and its random samples, i.e., how many times it appeared in the random networks, among other properties described in Data-structures#motif.

It then determines whether or not it is a motif, an anti-motif or none and stores this information in the output object MotifCriteriaResults. This object also holds all the statistical information regarding this candidate, e.g., its Z Score, which is calculated as follows:

image

Clone this wiki locally