visone manual - User contributions [en]

Quad census

2017-08-07T11:30:39Z

Ortmann:

=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 ===
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

Quad census

2017-08-07T11:24:13Z

Ortmann:

File:Quad census.png

2017-08-07T10:57:38Z

Ortmann: 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

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

Quad census

2017-08-07T10:54:59Z

Ortmann:

=Quad Census=
[[File:Quad_census.pdf]]

===Method===

=== Complexity ===

=== Parameter ===

Quad census

2017-08-03T14:06:03Z

Ortmann: Created page with "=Quad Census= ===Method=== === Complexity === === Parameter ==="

=Quad Census=
===Method===

=== Complexity ===

=== Parameter ===

Sparse stress minimization

2017-02-23T17:28:49Z

Ortmann:

=Sparse Stress Layout=
===Method===
The sparse stress layout is a heuristic to approximate the (full) stress layout. The goal of the stress minimization is to find a layout, <math>x</math>, such that <math>\sum_{i<j}w_{ij}(||x_i - x_j|| - d_{ij})^2 \text{ is as small as possible.}</math> In other words stress minimization tries to find a layout in which the euclidean distance of each pair of nodes matches their graph-theoretical distance, i.e. shortest-path distance.

In comparison to the (full) stress minimization, sparse stress on the one hand requires less space and running time, but on the other hand the resulting layouts have a slightly lower quality. The space and running time reduction is achieved by restricting the stress function from <math>n^2</math> to <math>m+np</math> with <math>p</math> denoting the number of pivots.

More detailed background information can be found in
* Mark Ortmann, Mirza Klimenta, and Ulrik Brandes: [https://dx.doi.org/10.1007/978-3-319-50106-2_2 A sparse Stress Model], GD'16, 18-32, 2016.

=== Complexity ===
The computation of the sparse stress layout requires <math>O(m+np)</math> time and space and a <math>O(p(m+n \log n))</math> preprocessing time.

=== Parameters & Their Influence ===
* By its iterative nature the quality of the stress minimized layout depends on the initialization. Therefore, we recommend to check the "init with PivotMDS" box.
* The number of pivots influences the quality of the final layout. A higher number of pivots increases the quality, but also space and running time.
* The pivot strategy allows to choose between various (pivot) sampling strategies. We recommend K_MEANS_SSSP as it has advantages over the other routines respective the layout quality. However if time is the most important factor we recommend Random. The other two strategies are a compromise between quality and running time.
* The link lengths defines the distance between adjacent nodes in the euclidean space and is used for the shortest-path computation.
* The maximum number of iterations defines after how many executions of the iterative stress minimization algorithm the procedure should stop. A higher number of iterations results in a higher quality.
* Given the case that the layouts of two consecutive iterations of the sparse stress algorithm differ only by a very small amount we say that the algorithm has converged. Since, often the number of iterations is often higher than necessary, we recommend to check the "stop on convergence" box to decrease the running time of the algorithm.

Sparse stress minimization

2017-02-23T17:10:41Z

Ortmann:

Sparse stress minimization

2017-02-23T16:51:10Z

Ortmann:

=Sparse Stress Layout=
===Method===
The Sparse Stress Layout is a heuristic to approximate the (full) stress layout. The goal of the stress minimization is to find a layout, <math>x</math>, such that <math>\sum_{i<j}w_{ij}(||x_i - x_j|| - d_{ij})^2 \text{ is as small as possible.}</math> In other words stress tries to find a layout in which the euclidean distance of each pair of nodes matches their graph-theoretical distance, i.e. shortest-path distance.
=== Complexity ===

Triangle k Core

2015-06-08T15:20:21Z

Ortmann:

=Triangle k Core=
The triangle k core, or k truss have been intoduced by [http://www.csee.ogi.edu/~zak/cs506-pslc/trusses.pdf Cohen (NSA Tech. Report 2008)] and [http://web.cse.ohio-state.edu/~zhangya/ICDE12_conf_full_179.pdf Zhang and Parthasarathy (ICDE 2012)] independently and runs in <math>\mathcal{O}(\Delta(G)m)</math> time, where <math>\Delta(G)</math> is the maximum degree and <math>m</math> the number of edges.
=== Definition Triangle Core ===
The triangle k-core of a simple undirected graph <math>G = (V,E)</math> is the inclusion maximal subgraph <math>C_{k}(G) \subset G</math> where each edge <math>e \in E(C_k(G))</math> is part of at least <math>k</math> triangles in <math>C_k(G)</math>.

More detailed background information is provided in

=== Definition Triangle Core Number ===
The triangle core number of an edge <math>e \in E(G)</math> is the maximal k such that <math>e \in C_k(G)</math>

Triangle k Core

2015-06-08T14:48:59Z

Ortmann:

=Triangle k Core=
The triangle k core, or k truss have been intoduced by [http://www.csee.ogi.edu/~zak/cs506-pslc/trusses.pdf Cohen] and [http://web.cse.ohio-state.edu/~zhangya/ICDE12_conf_full_179.pdf Zhang and Parthasarathy] independently and runs in <math>\mathcal{O}(\Delta(G)m)</math> time, where <math>\Delta(G)</math> is the maximum degree and <math>m</math> the number of edges.
=== Definition Triangle Core ===
The triangle k-core of a simple undirected graph <math>G = (V,E)</math> is the inclusion maximal subgraph <math>C_{k}(G) \subset G</math> where each edge <math>e \in E(C_k(G))</math> is part of at least <math>k</math> triangles in <math>C_k(G)</math>.

More detailed background information is provided in

=== Definition Triangle Core Number ===
The triangle core number of an edge <math>e \in E(G)</math> is the maximal k such that <math>e \in C_k(G)</math>

Triangle k Core

2015-06-08T14:34:31Z

Ortmann:

=Triangle k Core=
=== Definition Triangle Core ===
The triangle k-core of a simple undirected graph <math>G = (V,E)</math> is the inclusion maximal subgraph <math>C_{k}(G) \subset G</math> where each edge <math>e \in E(C_k(G))</math> is part of at least <math>k</math> triangles in <math>C_k(G)</math>.

More detailed background information is provided in

=== Definition Triangle Core Number ===
The triangle core number of an edge <math>e \in E(G)</math> is the maximal k such that <math>e \in C_k(G)</math>

Haha

WNA

2010-11-30T17:46:59Z

Ortmann: Created page with ''''Word-Network Analysis''' ('''WNA''') extracts a network from a text by interpreting the text as a chain of words and connecting ''relevant'' words within a certain ''interval'…'

'''Word-Network Analysis''' ('''WNA''') extracts a network from a text by interpreting the text as a chain of words and connecting ''relevant'' words within a certain ''interval''.

Consider the following text example and take a closer look at the WNA procedure.
<blockquote> The two planes crashed into the towers of the World Trade Center in New York </blockquote>
First of all the WNA identifies the relevant words of the text. This preprocessing step includes:
<ul><dd>
<li> [http://en.wikipedia.org/wiki/Stemming Stemming]
<li> Filtering words with a length less than a preset word length
<li> Filtering [http://en.wikipedia.org/wiki/Stop_words stop words]
<li> Filtering part of speech
</ul>
The preprocessed text example could look like this:
<blockquote>plane crash tower world trade center new york</blockquote>
In the second and final step the network is constructed. Every word of the preprocessed text constitutes a node of the network, where equal words are represented by solely one node. The connections are created by using one of the following methods:
<ul><dd>
<li>Co-occurrence: Every word within in the same sentence is connected
<li>k-Windowing: Every word is connected to the k-1 subsequent words
</ul>
The following figures show the final network depending on the utilized method.
<table>
<td>[[File:CoOccurence.png|thumb|300px|<div align="center">Co-Occurence</div>]]</td>
<td>[[File:3Windowing.png|thumb|823px|<div align="center">3-Windowing</div>]]</td>
</table>

File:3Windowing.png

2010-11-30T13:47:40Z

Ortmann: WNA-Network with window size 3

WNA-Network with window size 3

File:CoOccurence.png

2010-11-30T13:46:43Z

Ortmann: Co-Occurence WNA-Network

Co-Occurence WNA-Network