Quad census: Difference between revisions
(Created page with "=Quad Census= ===Method=== === Complexity === === Parameter ===") |
No edit summary |
||
(2 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
=Quad Census= | =Quad Census= | ||
===Method=== | ===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) | |||
=== | === Result === | ||
The result of this analysis are written to node/edge and network attributes: | |||
* ind_orbit_..: The induced orbit-aware frequencies. The orbit number corresponds to the numbering shown in the opposing figure | |||
* non-ind_orbit_...: Same as ind_orbit_.. but for non-induced frequencies | |||
* <quad_name>: If the orbit-aware frequencies box is not checked the names of the corresponding quads is used, e.g. claw or diamond |
Latest revision as of 11:30, 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)
Result
The result of this analysis are written to node/edge and network attributes:
- ind_orbit_..: The induced orbit-aware frequencies. The orbit number corresponds to the numbering shown in the opposing figure
- non-ind_orbit_...: Same as ind_orbit_.. but for non-induced frequencies
- <quad_name>: If the orbit-aware frequencies box is not checked the names of the corresponding quads is used, e.g. claw or diamond