# Difference between revisions of "Quad census"

Jump to navigation
Jump to search

Line 1: | Line 1: | ||

=Quad Census= | =Quad Census= | ||

− | [[File:Quad_census. | + | ===Method=== |

+ | [[File:Quad_census.png|400px|thumb|All non-isomorphic subgraphs with four nodes (quads). Node and edge labels refer to the orbits and were enumerated such that each orbit is identified with a single quad.]] | ||

+ | |||

+ | The frequency distribution over all non-isomorphic 4-node subgraphs is called the quad census. | ||

− | + | The quad census analysis calculates for each node and edge respectively how often it is contained in a specific quad. Depending on the chosen parameters this analysis further distinguishes between different orbits. For example a claw has two node orbits, i.e., 11 and 12. Considering the orbits leads to a finer grained description of the nodes/edges and allows for a more precise comparison. | |

=== Complexity === | === Complexity === | ||

+ | The computation of the orbit-aware Quad Census can be done in <math>O(a(G)^2m)</math> where <math>m</math> denotes the number of edges of the graph and <math>a(G)</math> is the arboricity of the graph. | ||

+ | |||

+ | More detailed information on the computation of the orbit-aware Quad Census is available in | ||

+ | * Mark Ortmann, and Ulrik Brandes: [https://link.springer.com/content/pdf/10.1007%2Fs41109-017-0027-2.pdf Efficient orbit-aware triad and quad census in directed and undirected graphs], Applied Network Science, 2(13), 2017. | ||

− | === | + | === Settings === |

+ | * orbit-aware frequencies: If checked the node and edge orbit frequencies are computed, otherwise orbits will not be distinguished. | ||

+ | * write non-induced frequencies: If checked besides the induced also the node and edge (orbit-aware) non-induced frequencies are written. | ||

+ | * write network frequencies: Additionally computes the quad census on a graph level (if checked) |

## Revision as of 11:24, 7 August 2017

# Quad Census

### Method

The frequency distribution over all non-isomorphic 4-node subgraphs is called the quad census.

The quad census analysis calculates for each node and edge respectively how often it is contained in a specific quad. Depending on the chosen parameters this analysis further distinguishes between different orbits. For example a claw has two node orbits, i.e., 11 and 12. Considering the orbits leads to a finer grained description of the nodes/edges and allows for a more precise comparison.

### Complexity

The computation of the orbit-aware Quad Census can be done in where denotes the number of edges of the graph and is the arboricity of the graph.

More detailed information on the computation of the orbit-aware Quad Census is available in

- Mark Ortmann, and Ulrik Brandes: Efficient orbit-aware triad and quad census in directed and undirected graphs, Applied Network Science, 2(13), 2017.

### Settings

- orbit-aware frequencies: If checked the node and edge orbit frequencies are computed, otherwise orbits will not be distinguished.
- write non-induced frequencies: If checked besides the induced also the node and edge (orbit-aware) non-induced frequencies are written.
- write network frequencies: Additionally computes the quad census on a graph level (if checked)