-
Notifications
You must be signed in to change notification settings - Fork 0
Main Classes
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.
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.
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: