https://visone.ethz.ch/wiki/api.php?action=feedcontributions&user=Nocaj&feedformat=atomvisone manual - User contributions [en]2024-03-28T09:13:43ZUser contributionsMediaWiki 1.39.6https://visone.ethz.ch/wiki/index.php?title=Sparse_stress_minimization&diff=1660Sparse stress minimization2017-02-22T11:34:59Z<p>Nocaj: Created page with "content will follow."</p>
<hr />
<div>content will follow.</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Tutorials&diff=1647Tutorials2016-02-26T14:20:43Z<p>Nocaj: </p>
<hr />
<div>This page provides an index to tutorials that illustrate common and advanced usage scenarios of the visone software.<br />
<br />
== Installation ==<br />
<br />
* [[Installation_(tutorial)|'''Installing visone''']] tells you where you can download visone and how you install and run the program.<br />
<br />
== Basic tutorials ==<br />
<br />
These basic tutorials lead you step by step through a sequence of tasks illustrating common usage of visone.<br />
<br />
* [[Introducing_the_visual_network_editor_(tutorial)|'''Introducing visone's graphical user interface''']] tells you how networks are created and modified by use of the mouse. You will also learn about the different types of information that are encoded in a visone network and how networks can be exported to data and image files.<br />
<br />
* [[Visualization_and_analysis_(tutorial)|'''Visualizing and analyzing networks''']] shows you how analysis and visualization goes hand in hand in visone. It introduces you to the most common usage scenario: importing data from one or several files, analyzing the network, visualizing the network together with the computed indicators, exporting data and images for further processing or publication.<br />
<br />
* [[Data_input_(tutorial)|'''How do I get my data into visone?''']] Normally, visone reads network data from [[GraphML]] files, which should never cause any problems. However, in some cases it is necessary to import data stemming from other sources that can, for instance, export adjacency matrices to comma-separated-value (CSV) tables. This tutorial guides you through the various possibilities to input data into visone.<br />
<br />
== Advanced tutorials ==<br />
<br />
These tutorials illustrate advanced usage of visone.<br />
<br />
* [[Managing_attributes_(tutorial)|'''Advanced attribute management''']] introduces you to the full power of visone's [[Attribute_manager|attribute manager]] and shows you how to select elements dependent on attribute values. The attribute manager allows you, for instance, to convert tie strength to distance or rankings and vice versa, dichotomize networks, rescale tie weights and much more.<br />
<br />
* [[Collections_(tutorial)|'''Network collections and dynamic networks''']]. A [[network collection]] is a set or sequence of several networks that belong together, e.g., by building a longitudinal network. This tutorial guides you through several application examples for network collections, including dynamic visualization as well as statistical modeling of network dynamics with the [[RSiena interface|RSiena software]].<br />
<br />
* [[Event_networks_(tutorial)|'''Event networks.''']] The links in an ''event network'' are formed by time-stamped interaction events, such as users sending emails to other users, users editing documents in a Web 2.0 environment, etc. This tutorial illustrates the analysis and visualization of event networks with visone.<br />
<br />
* [[Graph_difference_(tutorial)|'''Using the R console to compare graphs''']] shows an advanced usage of the R console, where two graphs are compared by creating and visualizing their difference graph.<br />
<br />
== visone extensions ==<br />
<br />
* [[R_console_(tutorial)|'''R''']] is a widely used software tool for statistical computation and graphics. An R console can be opened from within visone, with full access to the [http://www.r-project.org/ R programming environment] and the ability to exchange network data back and forth. This extends visone's capabilities tremendously, providing access to a huge set of methods for statistical analysis and modeling.<br />
<br />
* [[RSiena_(tutorial)|'''Siena''']] is a software tool for [http://www.stats.ox.ac.uk/~snijders/siena/SnijdersSteglichVdBunt2009.pdf stochastic actor-oriented modeling (SAOM)] of network panel data. The recent R-based version RSiena can be accessed transparently using visone menus, and there are dedicated graphical methods to explore parameters interactively.<br />
<br />
* [[KNIME_(tutorial)|'''KNIME''']] is a comprehensive data mining workflow tool. KNIME and visone can exchange network data back and forth at runtime.<br />
<br />
== Application-specific tutorials ==<br />
<br />
* [[Personal_networks_(tutorial)|'''Analyzing ensembles of personal networks collected with EgoNet.''']] [http://sourceforge.net/projects/egonet/ EgoNet] is a software to conduct interviews in which the [[Personal_network|personal networks]] of respondents are collected. This tutorial explains (1) how to load data collected with EgoNet into visone and (2) how to cluster, aggregate, and visualize collections of personal networks using the methodology proposed in: Ulrik Brandes, Juergen Lerner, Miranda J. Lubbers, Chris McCarty, and Jose Luis Molina [http://www.inf.uni-konstanz.de/algo/publications/bllmm-vsccg-08.pdf '''Visual Statistics for Collections of Clustered Graphs''']. ''Proc. IEEE Pacific Visualization Symp. (PacificVis'08)'', 2008.<br />
<br />
* [[Wikipedia_edit_networks_(tutorial)|'''Wikipedia edit networks.''']] This tutorial introduces you to the collection, analysis, and visualization of '''edit networks''' associated with the history of [http://www.wikipedia.org Wikipedia] pages.<br />
<br />
== External Tutorials ==<br />
There are also user-produced tutorials in various languages.<br />
* [[Media:Visone-tutorial-french.pdf|French visone tutorial by Jacques Cellier]] and the used [[Media:data-french-visone-tutorial.zip|example data]].</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Tutorials&diff=1646Tutorials2016-02-26T14:20:13Z<p>Nocaj: </p>
<hr />
<div>This page provides an index to tutorials that illustrate common and advanced usage scenarios of the visone software.<br />
<br />
== Installation ==<br />
<br />
* [[Installation_(tutorial)|'''Installing visone''']] tells you where you can download visone and how you install and run the program.<br />
<br />
== Basic tutorials ==<br />
<br />
These basic tutorials lead you step by step through a sequence of tasks illustrating common usage of visone.<br />
<br />
* [[Introducing_the_visual_network_editor_(tutorial)|'''Introducing visone's graphical user interface''']] tells you how networks are created and modified by use of the mouse. You will also learn about the different types of information that are encoded in a visone network and how networks can be exported to data and image files.<br />
<br />
* [[Visualization_and_analysis_(tutorial)|'''Visualizing and analyzing networks''']] shows you how analysis and visualization goes hand in hand in visone. It introduces you to the most common usage scenario: importing data from one or several files, analyzing the network, visualizing the network together with the computed indicators, exporting data and images for further processing or publication.<br />
<br />
* [[Data_input_(tutorial)|'''How do I get my data into visone?''']] Normally, visone reads network data from [[GraphML]] files, which should never cause any problems. However, in some cases it is necessary to import data stemming from other sources that can, for instance, export adjacency matrices to comma-separated-value (CSV) tables. This tutorial guides you through the various possibilities to input data into visone.<br />
<br />
== Advanced tutorials ==<br />
<br />
These tutorials illustrate advanced usage of visone.<br />
<br />
* [[Managing_attributes_(tutorial)|'''Advanced attribute management''']] introduces you to the full power of visone's [[Attribute_manager|attribute manager]] and shows you how to select elements dependent on attribute values. The attribute manager allows you, for instance, to convert tie strength to distance or rankings and vice versa, dichotomize networks, rescale tie weights and much more.<br />
<br />
* [[Collections_(tutorial)|'''Network collections and dynamic networks''']]. A [[network collection]] is a set or sequence of several networks that belong together, e.g., by building a longitudinal network. This tutorial guides you through several application examples for network collections, including dynamic visualization as well as statistical modeling of network dynamics with the [[RSiena interface|RSiena software]].<br />
<br />
* [[Event_networks_(tutorial)|'''Event networks.''']] The links in an ''event network'' are formed by time-stamped interaction events, such as users sending emails to other users, users editing documents in a Web 2.0 environment, etc. This tutorial illustrates the analysis and visualization of event networks with visone.<br />
<br />
* [[Graph_difference_(tutorial)|'''Using the R console to compare graphs''']] shows an advanced usage of the R console, where two graphs are compared by creating and visualizing their difference graph.<br />
<br />
== visone extensions ==<br />
<br />
* [[R_console_(tutorial)|'''R''']] is a widely used software tool for statistical computation and graphics. An R console can be opened from within visone, with full access to the [http://www.r-project.org/ R programming environment] and the ability to exchange network data back and forth. This extends visone's capabilities tremendously, providing access to a huge set of methods for statistical analysis and modeling.<br />
<br />
* [[RSiena_(tutorial)|'''Siena''']] is a software tool for [http://www.stats.ox.ac.uk/~snijders/siena/SnijdersSteglichVdBunt2009.pdf stochastic actor-oriented modeling (SAOM)] of network panel data. The recent R-based version RSiena can be accessed transparently using visone menus, and there are dedicated graphical methods to explore parameters interactively.<br />
<br />
* [[KNIME_(tutorial)|'''KNIME''']] is a comprehensive data mining workflow tool. KNIME and visone can exchange network data back and forth at runtime.<br />
<br />
== Application-specific tutorials ==<br />
<br />
* [[Personal_networks_(tutorial)|'''Analyzing ensembles of personal networks collected with EgoNet.''']] [http://sourceforge.net/projects/egonet/ EgoNet] is a software to conduct interviews in which the [[Personal_network|personal networks]] of respondents are collected. This tutorial explains (1) how to load data collected with EgoNet into visone and (2) how to cluster, aggregate, and visualize collections of personal networks using the methodology proposed in: Ulrik Brandes, Juergen Lerner, Miranda J. Lubbers, Chris McCarty, and Jose Luis Molina [http://www.inf.uni-konstanz.de/algo/publications/bllmm-vsccg-08.pdf '''Visual Statistics for Collections of Clustered Graphs''']. ''Proc. IEEE Pacific Visualization Symp. (PacificVis'08)'', 2008.<br />
<br />
* [[Wikipedia_edit_networks_(tutorial)|'''Wikipedia edit networks.''']] This tutorial introduces you to the collection, analysis, and visualization of '''edit networks''' associated with the history of [http://www.wikipedia.org Wikipedia] pages.<br />
<br />
== External Tutorials ==<br />
There are also user-produced tutorials in various languages.<br />
* [[Media:Visone-tutorial-french.pdf|French visone tutorial by Jacques Cellier]] and the used [[Media:data-french-visone-tutorial.zip||example data]].</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=File:Data-french-visone-tutorial.zip&diff=1645File:Data-french-visone-tutorial.zip2016-02-26T14:19:30Z<p>Nocaj: Used example data by the french visone tutorial</p>
<hr />
<div>Used example data by the french visone tutorial</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Tutorials&diff=1644Tutorials2016-02-26T14:18:28Z<p>Nocaj: /* External Tutorials */</p>
<hr />
<div>This page provides an index to tutorials that illustrate common and advanced usage scenarios of the visone software.<br />
<br />
== Installation ==<br />
<br />
* [[Installation_(tutorial)|'''Installing visone''']] tells you where you can download visone and how you install and run the program.<br />
<br />
== Basic tutorials ==<br />
<br />
These basic tutorials lead you step by step through a sequence of tasks illustrating common usage of visone.<br />
<br />
* [[Introducing_the_visual_network_editor_(tutorial)|'''Introducing visone's graphical user interface''']] tells you how networks are created and modified by use of the mouse. You will also learn about the different types of information that are encoded in a visone network and how networks can be exported to data and image files.<br />
<br />
* [[Visualization_and_analysis_(tutorial)|'''Visualizing and analyzing networks''']] shows you how analysis and visualization goes hand in hand in visone. It introduces you to the most common usage scenario: importing data from one or several files, analyzing the network, visualizing the network together with the computed indicators, exporting data and images for further processing or publication.<br />
<br />
* [[Data_input_(tutorial)|'''How do I get my data into visone?''']] Normally, visone reads network data from [[GraphML]] files, which should never cause any problems. However, in some cases it is necessary to import data stemming from other sources that can, for instance, export adjacency matrices to comma-separated-value (CSV) tables. This tutorial guides you through the various possibilities to input data into visone.<br />
<br />
== Advanced tutorials ==<br />
<br />
These tutorials illustrate advanced usage of visone.<br />
<br />
* [[Managing_attributes_(tutorial)|'''Advanced attribute management''']] introduces you to the full power of visone's [[Attribute_manager|attribute manager]] and shows you how to select elements dependent on attribute values. The attribute manager allows you, for instance, to convert tie strength to distance or rankings and vice versa, dichotomize networks, rescale tie weights and much more.<br />
<br />
* [[Collections_(tutorial)|'''Network collections and dynamic networks''']]. A [[network collection]] is a set or sequence of several networks that belong together, e.g., by building a longitudinal network. This tutorial guides you through several application examples for network collections, including dynamic visualization as well as statistical modeling of network dynamics with the [[RSiena interface|RSiena software]].<br />
<br />
* [[Event_networks_(tutorial)|'''Event networks.''']] The links in an ''event network'' are formed by time-stamped interaction events, such as users sending emails to other users, users editing documents in a Web 2.0 environment, etc. This tutorial illustrates the analysis and visualization of event networks with visone.<br />
<br />
* [[Graph_difference_(tutorial)|'''Using the R console to compare graphs''']] shows an advanced usage of the R console, where two graphs are compared by creating and visualizing their difference graph.<br />
<br />
== visone extensions ==<br />
<br />
* [[R_console_(tutorial)|'''R''']] is a widely used software tool for statistical computation and graphics. An R console can be opened from within visone, with full access to the [http://www.r-project.org/ R programming environment] and the ability to exchange network data back and forth. This extends visone's capabilities tremendously, providing access to a huge set of methods for statistical analysis and modeling.<br />
<br />
* [[RSiena_(tutorial)|'''Siena''']] is a software tool for [http://www.stats.ox.ac.uk/~snijders/siena/SnijdersSteglichVdBunt2009.pdf stochastic actor-oriented modeling (SAOM)] of network panel data. The recent R-based version RSiena can be accessed transparently using visone menus, and there are dedicated graphical methods to explore parameters interactively.<br />
<br />
* [[KNIME_(tutorial)|'''KNIME''']] is a comprehensive data mining workflow tool. KNIME and visone can exchange network data back and forth at runtime.<br />
<br />
== Application-specific tutorials ==<br />
<br />
* [[Personal_networks_(tutorial)|'''Analyzing ensembles of personal networks collected with EgoNet.''']] [http://sourceforge.net/projects/egonet/ EgoNet] is a software to conduct interviews in which the [[Personal_network|personal networks]] of respondents are collected. This tutorial explains (1) how to load data collected with EgoNet into visone and (2) how to cluster, aggregate, and visualize collections of personal networks using the methodology proposed in: Ulrik Brandes, Juergen Lerner, Miranda J. Lubbers, Chris McCarty, and Jose Luis Molina [http://www.inf.uni-konstanz.de/algo/publications/bllmm-vsccg-08.pdf '''Visual Statistics for Collections of Clustered Graphs''']. ''Proc. IEEE Pacific Visualization Symp. (PacificVis'08)'', 2008.<br />
<br />
* [[Wikipedia_edit_networks_(tutorial)|'''Wikipedia edit networks.''']] This tutorial introduces you to the collection, analysis, and visualization of '''edit networks''' associated with the history of [http://www.wikipedia.org Wikipedia] pages.<br />
<br />
== External Tutorials ==<br />
There are also user-produced tutorials in various languages.<br />
* [[Media:Visone-tutorial-french.pdf|French visone tutorial by Jacques Cellier]] and the used example data</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=File:Visone-tutorial-french.pdf&diff=1643File:Visone-tutorial-french.pdf2016-02-26T14:07:36Z<p>Nocaj: French visone tutorial by Jacques Cellier.</p>
<hr />
<div>French visone tutorial by Jacques Cellier.</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Tutorials&diff=1642Tutorials2016-02-26T14:04:13Z<p>Nocaj: </p>
<hr />
<div>This page provides an index to tutorials that illustrate common and advanced usage scenarios of the visone software.<br />
<br />
== Installation ==<br />
<br />
* [[Installation_(tutorial)|'''Installing visone''']] tells you where you can download visone and how you install and run the program.<br />
<br />
== Basic tutorials ==<br />
<br />
These basic tutorials lead you step by step through a sequence of tasks illustrating common usage of visone.<br />
<br />
* [[Introducing_the_visual_network_editor_(tutorial)|'''Introducing visone's graphical user interface''']] tells you how networks are created and modified by use of the mouse. You will also learn about the different types of information that are encoded in a visone network and how networks can be exported to data and image files.<br />
<br />
* [[Visualization_and_analysis_(tutorial)|'''Visualizing and analyzing networks''']] shows you how analysis and visualization goes hand in hand in visone. It introduces you to the most common usage scenario: importing data from one or several files, analyzing the network, visualizing the network together with the computed indicators, exporting data and images for further processing or publication.<br />
<br />
* [[Data_input_(tutorial)|'''How do I get my data into visone?''']] Normally, visone reads network data from [[GraphML]] files, which should never cause any problems. However, in some cases it is necessary to import data stemming from other sources that can, for instance, export adjacency matrices to comma-separated-value (CSV) tables. This tutorial guides you through the various possibilities to input data into visone.<br />
<br />
== Advanced tutorials ==<br />
<br />
These tutorials illustrate advanced usage of visone.<br />
<br />
* [[Managing_attributes_(tutorial)|'''Advanced attribute management''']] introduces you to the full power of visone's [[Attribute_manager|attribute manager]] and shows you how to select elements dependent on attribute values. The attribute manager allows you, for instance, to convert tie strength to distance or rankings and vice versa, dichotomize networks, rescale tie weights and much more.<br />
<br />
* [[Collections_(tutorial)|'''Network collections and dynamic networks''']]. A [[network collection]] is a set or sequence of several networks that belong together, e.g., by building a longitudinal network. This tutorial guides you through several application examples for network collections, including dynamic visualization as well as statistical modeling of network dynamics with the [[RSiena interface|RSiena software]].<br />
<br />
* [[Event_networks_(tutorial)|'''Event networks.''']] The links in an ''event network'' are formed by time-stamped interaction events, such as users sending emails to other users, users editing documents in a Web 2.0 environment, etc. This tutorial illustrates the analysis and visualization of event networks with visone.<br />
<br />
* [[Graph_difference_(tutorial)|'''Using the R console to compare graphs''']] shows an advanced usage of the R console, where two graphs are compared by creating and visualizing their difference graph.<br />
<br />
== visone extensions ==<br />
<br />
* [[R_console_(tutorial)|'''R''']] is a widely used software tool for statistical computation and graphics. An R console can be opened from within visone, with full access to the [http://www.r-project.org/ R programming environment] and the ability to exchange network data back and forth. This extends visone's capabilities tremendously, providing access to a huge set of methods for statistical analysis and modeling.<br />
<br />
* [[RSiena_(tutorial)|'''Siena''']] is a software tool for [http://www.stats.ox.ac.uk/~snijders/siena/SnijdersSteglichVdBunt2009.pdf stochastic actor-oriented modeling (SAOM)] of network panel data. The recent R-based version RSiena can be accessed transparently using visone menus, and there are dedicated graphical methods to explore parameters interactively.<br />
<br />
* [[KNIME_(tutorial)|'''KNIME''']] is a comprehensive data mining workflow tool. KNIME and visone can exchange network data back and forth at runtime.<br />
<br />
== Application-specific tutorials ==<br />
<br />
* [[Personal_networks_(tutorial)|'''Analyzing ensembles of personal networks collected with EgoNet.''']] [http://sourceforge.net/projects/egonet/ EgoNet] is a software to conduct interviews in which the [[Personal_network|personal networks]] of respondents are collected. This tutorial explains (1) how to load data collected with EgoNet into visone and (2) how to cluster, aggregate, and visualize collections of personal networks using the methodology proposed in: Ulrik Brandes, Juergen Lerner, Miranda J. Lubbers, Chris McCarty, and Jose Luis Molina [http://www.inf.uni-konstanz.de/algo/publications/bllmm-vsccg-08.pdf '''Visual Statistics for Collections of Clustered Graphs''']. ''Proc. IEEE Pacific Visualization Symp. (PacificVis'08)'', 2008.<br />
<br />
* [[Wikipedia_edit_networks_(tutorial)|'''Wikipedia edit networks.''']] This tutorial introduces you to the collection, analysis, and visualization of '''edit networks''' associated with the history of [http://www.wikipedia.org Wikipedia] pages.<br />
<br />
== External Tutorials ==<br />
There are also user-produced tutorials in various languages.<br />
* French visone tutorial by Jacques Cellier,</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Backbone_Layout&diff=1641Backbone Layout2016-02-01T15:51:02Z<p>Nocaj: /* Method */</p>
<hr />
<div>=Backbone Layout=<br />
===Method===<br />
Small-world graphs have characteristically low average distance and thus cause force-directed methods to generate drawings that look like hairballs.<br />
<br />
The backbone layout tries to untangle hairball graphs. The method is based on a spanning subgraph that is sparse but connected and consists of strong ties holding together communities. <br />
Strong ties are identified using a structural measures of embeddedness.<br />
<br />
More detailed background information is provided in<br />
<br />
* Arlind Nocaj, Mark Ortmann, and Ulrik Brandes: [http://jgaa.info/accepted/2015/NocajOrtmannBrandes2015.19.2.pdf Untangling the Hairballs of Multi-Centered, Small-World Online Social Media Networks], Journal of Graph Algorithms and Applications, 19(2):595-618, 2015.<br />
<br />
<br />
{|<br />
|+ valign="top"| Facebook friendships at California Institute of Technology (Caltech36). Vertex color corresponds to dormitory (gray for missing values), but has not been utilized in the layout algorithm. The layout in '''(a)''' is based on the entire hairball graph, whereas '''(b)''' uses edge embeddedness which spreads the graph while keeping cohesive groups together. Embeddedness mapped to edge color; backbone edges dark gray.<br />
|- halign="center"<br />
| style="text-align: center;" |[[File:Caltech36-hairball.png|300px]]<br />
|- <br />
| style="text-align: center;" |'''(a)''' drawing based on complete network<br />
|-<br />
| style="text-align: center;" |[[File:Caltech36-Quadrilateral-Backbone.png|500px]]<br />
|-<br />
| style="text-align: center;" |'''(b)''' drawing based on quadrilateral Simmelian backbone<br />
|<br />
|}<br />
<br />
=== Complexity ===<br />
The computation of the embeddedness together with the backbone extraction scales well for large networks with, e.g., millions of edges and nodes.<br />
<br />
The asymptotic runtime is <math> O(|E| \triangle(G))</math> for a graph <math>G=(V,E)</math> where <math>\triangle(G)</math> is the maximum degree of a vertex <math> v\in V</math>. <br />
<br />
<br />
The final layout based on the extracted backbone needs <math>O(|V|^2)</math> time and memory, which does not scale for very large graphs.<br />
<br />
=== Example Data ===<br />
A set of 50 synthetic hairball networks with a hidden group structure:<br />
* [[Media:Hairball-Graphs-PPM500.zip|'''Dataset''']] (11 MB) and its [[Hairball_Graphs_(data)| '''Description''']]</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Node_Connectivity&diff=1640Node Connectivity2015-08-07T13:55:13Z<p>Nocaj: </p>
<hr />
<div>The node connectivity between two nodes u and v is the number of nodes which have to be removed such that u and v are not connected by a path anymore. <br />
Link direction is not considered.<br />
<br />
If u and v are connected by a direct link (u,v) then their node connectivity is the number of nodes in their connected component minus one.</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Edge_Connectivity&diff=1639Edge Connectivity2015-08-07T13:54:49Z<p>Nocaj: Created page with "The edge (or link) connectivity between two nodes u and v is the number of edges which have to be removed such that u and v are not connected by a path anymore."</p>
<hr />
<div>The edge (or link) connectivity between two nodes u and v is the number of edges which have to be removed such that u and v are not connected by a path anymore.</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Node_Connectivity&diff=1638Node Connectivity2015-08-07T13:47:23Z<p>Nocaj: </p>
<hr />
<div>The node connectivity between two nodes u and v is the number of nodes which have to be removed such that u and v are not connected by path anymore. <br />
Link direction is not considered.<br />
<br />
If u and v are connected by a direct link (u,v) then their node connectivity is the number of nodes in their connected component minus one.</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Node_Connectivity&diff=1637Node Connectivity2015-08-07T13:40:28Z<p>Nocaj: Created page with "The node connectivity between two nodes u and v is the number of nodes which have to be removed such that u and v are not connected anymore. If u and v are connected by a direct..."</p>
<hr />
<div>The node connectivity between two nodes u and v is the number of nodes which have to be removed such that u and v are not connected anymore.<br />
<br />
If u and v are connected by a direct link (u,v) then their node connectivity is the number of nodes in their connected component minus one.</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=DAG_Longest_Path&diff=1636DAG Longest Path2015-08-07T08:16:31Z<p>Nocaj: </p>
<hr />
<div>Each node gets the length of the longest directed path from any source in the directed acyclic graph (DAG).<br />
A source in DAG is a node which has only outgoing links.<br />
<br />
If the graph has cycles, each strongly connected component is aggregated to one node which results in a DAG.<br />
In this case, each vertex gets the longest directed path from any strongly connected component whose nodes do not have any incoming edge to a node of another strongly connected component.</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=DAG_Longest_Path&diff=1635DAG Longest Path2015-08-07T08:14:12Z<p>Nocaj: </p>
<hr />
<div>Each node gets the length of the longest directed path from any source in the directed acyclic graph (DAG).<br />
A source in DAG is a node which has only outgoing links.<br />
<br />
If the graph has cycles, each strongly connected component is aggregated to one vertex which results in a DAG.<br />
Each vertex gets the longest directed path from any strongly connected component which has not incoming edges from any other strongly connected component.</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=DAG_Longest_Path&diff=1634DAG Longest Path2015-08-07T08:14:04Z<p>Nocaj: </p>
<hr />
<div><br />
<br />
Each node gets the length of the longest directed path from any source in the directed acyclic graph (DAG).<br />
A source in DAG is a node which has only outgoing links.<br />
<br />
If the graph has cycles, each strongly connected component is aggregated to one vertex which results in a DAG.<br />
Each vertex gets the longest directed path from any strongly connected component which has not incoming edges from any other strongly connected component.</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Transitive_Reduction&diff=1633Transitive Reduction2015-07-30T05:39:51Z<p>Nocaj: </p>
<hr />
<div>In a directed acyclic graph, every transitive link is removed. This transformation maintains the reachability among the nodes.<br />
<br />
If the graph has cycles every transitive link between two different strongly connected components is removed.<br />
<br />
See https://en.wikipedia.org/wiki/Transitive_reduction for a more detailed discussion.</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Transitive_Reduction&diff=1632Transitive Reduction2015-07-29T13:32:47Z<p>Nocaj: Created page with "In a directed acyclic graph, every transitive link is removed. This transformation maintains the reachability amont the nodes. If the graph has cycles every transitive link betw..."</p>
<hr />
<div>In a directed acyclic graph, every transitive link is removed. This transformation maintains the reachability amont the nodes.<br />
<br />
If the graph has cycles every transitive link between two different strongly connected components is removed.<br />
<br />
See https://en.wikipedia.org/wiki/Transitive_reduction for a more detailed discussion.</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Effective_Resistance&diff=1631Effective Resistance2015-07-09T06:26:55Z<p>Nocaj: Created page with "Computes the pairwise effective resistance (also called resistance distance) for all pairs of nodes. See the following article as a detailed reference: * Klein, D. J., & Randić,..."</p>
<hr />
<div>Computes the pairwise effective resistance (also called resistance distance) for all pairs of nodes.<br />
See the following article as a detailed reference:<br />
* Klein, D. J., & Randić, M. (1993). Resistance distance. Journal of Mathematical Chemistry, 12(1), 81-95.</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Triangle_k_Core&diff=1625Triangle k Core2015-06-10T13:34:29Z<p>Nocaj: </p>
<hr />
<div>The triangle k core, or k truss has 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.<br />
<br />
=== Definition Triangle Core ===<br />
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>.<br />
<br />
More detailed background information is provided in<br />
* Cohen, Jonathan. "Trusses: Cohesive subgraphs for social network analysis." National Security Agency Technical Report (2008).<br />
* Zhang, Yang, and Srinivasan Parthasarathy. "Extracting analyzing and visualizing triangle k-core motifs within networks." In Data Engineering (ICDE), 2012 IEEE 28th International Conference on, pp. 1049-1060. IEEE, 2012.<br />
<br />
=== Definition Triangle Core Number ===<br />
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></div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Triangle_k_Core&diff=1624Triangle k Core2015-06-10T13:34:13Z<p>Nocaj: </p>
<hr />
<div>The triangle k core, or k truss has 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.<br />
<br />
<br />
=== Definition Triangle Core ===<br />
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>.<br />
<br />
More detailed background information is provided in<br />
* Cohen, Jonathan. "Trusses: Cohesive subgraphs for social network analysis." National Security Agency Technical Report (2008).<br />
* Zhang, Yang, and Srinivasan Parthasarathy. "Extracting analyzing and visualizing triangle k-core motifs within networks." In Data Engineering (ICDE), 2012 IEEE 28th International Conference on, pp. 1049-1060. IEEE, 2012.<br />
<br />
=== Definition Triangle Core Number ===<br />
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></div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Triangle_k_Core&diff=1623Triangle k Core2015-06-10T13:33:15Z<p>Nocaj: added references</p>
<hr />
<div>The triangle k core, or k truss has 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.<br />
<br />
* Cohen, Jonathan. "Trusses: Cohesive subgraphs for social network analysis." National Security Agency Technical Report (2008).<br />
* Zhang, Yang, and Srinivasan Parthasarathy. "Extracting analyzing and visualizing triangle k-core motifs within networks." In Data Engineering (ICDE), 2012 IEEE 28th International Conference on, pp. 1049-1060. IEEE, 2012.<br />
=== Definition Triangle Core ===<br />
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>.<br />
<br />
More detailed background information is provided in<br />
<br />
=== Definition Triangle Core Number ===<br />
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></div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Triangle_k_Core&diff=1622Triangle k Core2015-06-10T13:30:37Z<p>Nocaj: </p>
<hr />
<div>The triangle k core, or k truss has 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.<br />
=== Definition Triangle Core ===<br />
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>.<br />
<br />
More detailed background information is provided in<br />
<br />
=== Definition Triangle Core Number ===<br />
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></div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Triangle_k_Core&diff=1621Triangle k Core2015-06-10T13:18:18Z<p>Nocaj: </p>
<hr />
<div>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.<br />
=== Definition Triangle Core ===<br />
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>.<br />
<br />
More detailed background information is provided in<br />
<br />
=== Definition Triangle Core Number ===<br />
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></div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=DAG_Longest_Path&diff=1620DAG Longest Path2015-06-10T12:57:52Z<p>Nocaj: Created page with "The input must be a directed acyclic graph (DAG). A source in DAG is a node which has only outgoing links. Each node gets the length of the longest directed path from any source ..."</p>
<hr />
<div>The input must be a directed acyclic graph (DAG).<br />
A source in DAG is a node which has only outgoing links.<br />
Each node gets the length of the longest directed path from any source in the DAG.</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Loop_Attribute_To_Node_Attribute&diff=1619Loop Attribute To Node Attribute2015-06-10T12:35:12Z<p>Nocaj: moved Loop Attribute To Node Attribute to Loop To Node Attribute over redirect</p>
<hr />
<div>#REDIRECT [[Loop To Node Attribute]]</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Loop_To_Node_Attribute&diff=1618Loop To Node Attribute2015-06-10T12:35:11Z<p>Nocaj: moved Loop Attribute To Node Attribute to Loop To Node Attribute over redirect</p>
<hr />
<div>For each selected edge attribute a node attribute is created containing the value of the self loop.<br />
For multiple self loops aggregation is performed based on the selected action.</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Loop_To_Node_Attribute&diff=1616Loop To Node Attribute2015-06-10T11:59:32Z<p>Nocaj: moved Loop To Node Attribute to Loop Attribute To Node Attribute</p>
<hr />
<div>For each selected edge attribute a node attribute is created containing the value of the self loop.<br />
For multiple self loops aggregation is performed based on the selected action.</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Loop_To_Node_Attribute&diff=1615Loop To Node Attribute2015-06-10T11:56:59Z<p>Nocaj: Created page with "For each selected edge attribute a node attribute is created containing the value of the self loop. For multiple self loops aggregation is performed based on the selected action."</p>
<hr />
<div>For each selected edge attribute a node attribute is created containing the value of the self loop.<br />
For multiple self loops aggregation is performed based on the selected action.</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Triangle_k_Core&diff=1610Triangle k Core2015-06-08T14:20:41Z<p>Nocaj: Created page with "will be filled soon..."</p>
<hr />
<div>will be filled soon...</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Triangle_k_core&diff=1609Triangle k core2015-06-08T14:20:10Z<p>Nocaj: Created page with "will be filled soon..."</p>
<hr />
<div>will be filled soon...</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Positional_Dominance&diff=1608Positional Dominance2015-06-08T13:38:32Z<p>Nocaj: Created page with "to be filled soon..."</p>
<hr />
<div>to be filled soon...</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Louvain_Clustering&diff=1531Louvain Clustering2015-04-09T13:27:42Z<p>Nocaj: </p>
<hr />
<div>=Louvain Clustering=<br />
=== Method ===<br />
<br />
The Louvain clustering tries to optimize modularity in a greedy fashion by randomly moving nodes from one cluster to another in multiple levels.<br />
<br />
The algorithm is:<br />
# (level) start with each node being a singleton cluster:<br />
# consider nodes in random order<br />
# iterate as long as cluster membership changes<br />
#* for each node : remove it from its current cluster and add it to the cluster with the highest modularity gain<br />
# aggregate the resulting clustering to a new graph and continue on next level (step 1), as long as modularity improves.<br />
<br />
<br />
=== Complexity ===<br />
Practically, the algorithm seems to scale well for large graphs.<br />
<br />
=== References ===<br />
*Fast unfolding of communities in large networks, Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre, Journal of Statistical Mechanics: Theory and Experiment 2008 (10), P10008 (12pp) doi: 10.1088/1742-5468/2008/10/P10008. ArXiv: http://arxiv.org/abs/0803.0476<br />
*"The Louvain method for community detection in large networks" Vincent Blondel http://perso.uclouvain.be/vincent.blondel/research/louvain.html</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Louvain_Clustering&diff=1530Louvain Clustering2015-04-02T14:42:36Z<p>Nocaj: </p>
<hr />
<div>=Louvain Clustering=<br />
=== Method ===<br />
<br />
The Louvain clustering tries to optimize modularity in a greedy fashion by randomly moving nodes from one cluster to another in multiple levels.<br />
<br />
The algorithm is:<br />
# start with each node being a singleton cluster:<br />
# consider nodes in random order<br />
# repeat as long as cluster membership changes<br />
#* for each node : remove it from its current cluster and add it to the cluster with the highest modularity gain<br />
# aggregate the resulting clustering to a new graph and continue with step 1 (as long as modularity improves).<br />
<br />
<br />
=== Complexity ===<br />
Practically, the algorithm seems to scale well for large graphs.<br />
<br />
=== References ===<br />
*Fast unfolding of communities in large networks, Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre, Journal of Statistical Mechanics: Theory and Experiment 2008 (10), P10008 (12pp) doi: 10.1088/1742-5468/2008/10/P10008. ArXiv: http://arxiv.org/abs/0803.0476<br />
*"The Louvain method for community detection in large networks" Vincent Blondel http://perso.uclouvain.be/vincent.blondel/research/louvain.html</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Louvain_Clustering&diff=1529Louvain Clustering2015-04-02T14:40:35Z<p>Nocaj: </p>
<hr />
<div>=Louvain Clustering=<br />
=== Method ===<br />
<br />
The Louvain clustering tries to optimize modularity in a greedy fashion by randomly moving nodes from one cluster to another in multiple levels.<br />
<br />
The algorithm is:<br />
# start with each node being a singleton cluster:<br />
# consider nodes in random order<br />
# repeat as long as cluster membership changes, consider nodes in a random order<br />
#* for each node : remove it from its current cluster and add it to the cluster with the highest modularity gain<br />
# aggregate the resulting clustering to a new graph and continue with step 1 (as long as modularity improves).<br />
<br />
<br />
=== Complexity ===<br />
Practically, the algorithm seems to scale well for large graphs.<br />
<br />
=== References ===<br />
*Fast unfolding of communities in large networks, Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre, Journal of Statistical Mechanics: Theory and Experiment 2008 (10), P10008 (12pp) doi: 10.1088/1742-5468/2008/10/P10008. ArXiv: http://arxiv.org/abs/0803.0476<br />
*"The Louvain method for community detection in large networks" Vincent Blondel http://perso.uclouvain.be/vincent.blondel/research/louvain.html</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Louvain_Clustering&diff=1528Louvain Clustering2015-04-02T14:38:42Z<p>Nocaj: </p>
<hr />
<div>=Louvain Clustering=<br />
=== Method ===<br />
<br />
The Louvain clustering tries to optimize modularity in a greedy fashion.<br />
<br />
The algorithm is:<br />
# start with each node being a singleton cluster:<br />
# consider nodes in random order<br />
# repeat as long as cluster membership changes, consider nodes in a random order<br />
#* for each node : remove it from its current cluster and add it to the cluster with the highest modularity gain<br />
# aggregate the resulting clustering to a new graph and continue with step 1 (as long as modularity improves).<br />
<br />
<br />
=== Complexity ===<br />
The algorithms scales well for large graphs <br />
<br />
=== References ===<br />
*Fast unfolding of communities in large networks, Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre, Journal of Statistical Mechanics: Theory and Experiment 2008 (10), P10008 (12pp) doi: 10.1088/1742-5468/2008/10/P10008. ArXiv: http://arxiv.org/abs/0803.0476<br />
*"The Louvain method for community detection in large networks" Vincent Blondel http://perso.uclouvain.be/vincent.blondel/research/louvain.html</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Visualization_tab&diff=1502Visualization tab2015-03-18T08:19:48Z<p>Nocaj: /* coordinates */</p>
<hr />
<div>Visualization algorithms change the graphical appearance of the network; they are accesible via the visualization tab. Basic illustrations of how to layout networks or display attribute values are provided in the two tutorials on [[Visualization_and_analysis_(tutorial)|''visualization and analysis'']] and [[Managing_attributes_(tutorial)|''advanced attribute management'']].<br />
<br />
visone distinguishes between three major '''visualization categories'''<br />
* ''layout'' to recompute the positions (coordinates) or nodes, links-bends, or labels to optimize readability or other specified layout criteria;<br />
* ''mapping'' to specify how attribute values (such as node centrality, tie strength, or class membership) are encoded in grapical variables (such as size, width, or color);<br />
* ''geometry'' to apply geometric transformations such as rotation, reflection, or scaling to the network or parts of the network; <br />
<br />
== layout ==<br />
<br />
''Layout'' refers to the task of obtaining positions for the elements of a network visualization, where [[#node layout|computing node positions]] is of primary interest. <br />
Other tasks are [[#link routing|(re-)routing the links]] of a visualization, e.g. to avoid overlap between link and node representations, or to automatically [[#label placement|arrange label positions]] for better readability.<br />
<br />
<br />
=== node layout ===<br />
<br />
The methods in this section deal with the computation of node positions for one or more networks. Generally, nodes are considered to be geometric points (or objects that are described by a single point), and links are represented as straight lines between their incident nodes. <br />
Thus, most methods produce so called ''straight-line drawings'' (also referred to as ''node-link diagrams'' or ''sociograms''). <br />
<br />
There are several general objectives that most methods try to optimize, such as:<br />
* links should have more or less the same length.<br />
* nodes should be distributed well over the drawing area.<br />
* the number of meaningless link crossings should be kept small.<br />
* structural symmetries in the network should be represented well.<br />
<br />
Additionally, some methods are constrained by additional or different objectives:<br />
* node placement is restricted with respect to a given scalar node attribute, e.g., such that nodes lie on [[#centrality layout|concentric circles]] or [[#status layout| verical layers]] corresponding to the attributes values.<br />
* given a [[#dynamic layout|sequence of networks]], the layout should ease comparison with respect to the layout of the previous network in the sequence.<br />
* the layout should reveal [[#spectral layout|specific structural properties]].<br />
<br />
<br />
<br />
==== stress minimization ====<br />
<br />
Stress minimization, an instance of a family of dimension-reduction techniques referred to as ''multidimensional scaling'' (MDS), is our preferred method to obtain a general-purpose layout for networks.<br />
The main idea is to compute a layout such that graph-theoretic distances (i.e., shortest-path lengths) between nodes are represented as good as possible, where more weight is placed on representation error with respect to shorter distances than larger ones. <br />
The method usually meets the general criteria mentioned above, and yields better results than [[#spring embedder|spring embedders]] in most cases.<br />
<br />
Note that the outcome of stress minimization is dependent on the current layout of the network.<br />
We suggest to compute a [[#metric MDS|metric MDS]] layout first to obtain good results.<br />
Also note that computing a layout via the [[Quick_layout|quick layout]] button corresponds to this procedure, i.e., applying stress minimization to a metric MDS layout.<br />
<br />
<!-- For more details on the options available in visone, see the [[stress minimization|concept page]] for stress minimization. --><br />
<br />
==== backbone layout ====<br />
The backbone layout tries to untangle hairball graphs. The method is based on a spanning subgraph that is sparse but connected and consists of strong ties holding together communities. For more details see the [[Backbone_Layout|concept page]].<br />
<br />
<br />
==== metric MDS ====<br />
<br />
Metric MDS, also referred to as ''classical scaling'' is the original, spectral-decomposition variant of multidimensional scaling. <br />
As with [[#stress minimization|stress minimization]], the goal is to represent shortest-path distances as well as possible. <br />
In contrast to stress minimization all distances are treated equally. <br />
Thus, this approach generally yields good representation of large distance, but poor representation of shorter distances, affecting layout quality. <br />
However, since metric MDS produces a unique solution, it is suited well to serve as initialization for stress minimization.<br />
<br />
<!-- See the metric MDS [[metric MDS|concept page]] for more technical details. --><br />
<br />
==== centrality layout ====<br />
<br />
Centrality layout, like [[#status layout|status layout]] is used to obtain a layout that represents values of a given numerical nodal attribute, e.g. a centrality index of nodes. <br />
Nodes with the same attribute value are arranged on concentric circles, where nodes with higher value are closer to the center, and nodes with lower value are in the periphery.<br />
At the same time, the algorithm tries to reduce link crossings as much as possible. <br />
Circumferences corresponding to regular intervals with respect to the attribute values are shown in the background of the visualization, to increase legibility of each node's corresponding value.<br />
<br />
<!-- See the centrality layout [[centrality layout|concept page]] for details on available options. --><br />
<br />
==== status layout ====<br />
<br />
Status layout, like [[#centrality layout|centrality layout]] is used to obtain a layout that represents values of a given numerical nodal attribute, e.g. a centrality index of nodes. <br />
Nodes with the same attribute value are arranged on horizontal lines, where nodes with higher value are closer to the top, and nodes with lower value are closer to the bottom of the drawing. <br />
The algorithm tries to avoid link crossings. <br />
Note also, that bend-points for the links are introduced to increase readability. <br />
Optionally, the status niveaus (i.e., horizontal lines) corresponding to attribute values can be shown in the background of the visualization.<br />
<br />
<!-- See the status layout [[status layout|concept page]] for more details. --><br />
<br />
==== dynamic layout ====<br />
<br />
Dynamic layout refers to techniques for obtaining coherent positions of nodes for several networks, usually embodying a time-series of a network. <br />
The goal is to convey the evolution of the network, by easing comparison between a current layout and the preceeding one. <br />
In visone, three methods are currently offered to obtain a dynamic layout, all based on [[#stress minimization|stress minimization]].<br />
One approach calculates one single layout for an aggregate of all individual networks, and applies these positions, i.e., all nodes strictly maintain their position throughout the sequence. <br />
The other two approaches trade off this perfect stability for better readability of individual networks. <br />
<br />
Note that dynamic layout can only be applied to [[network collection|network collections]]. <br />
Also, visone provides [[animation]] of the sequence via the [[File:Animation.png|link=animation]] icon in the [[GUI#toolbar|toolbar]]. <br />
<br />
<!-- See the dynamic layout [[dynamic layout|concept page]] for more information on technical details and available options. --><br />
<br />
==== stress minimization (dyad attributes) ====<br />
<br />
This method differs from standard [[#stress minimization|stress minization]] in the choice of input distances. <br />
Usually, shortest-path distances are considered. <br />
Here, any numerical dyad attribute may be choosen as input.<br />
The method then tries to arrange nodes, such that those distances are matched as well as possible in the layout. <br />
<br />
==== spring embedder ====<br />
<br />
The spring embedder is the most commonly known general-purpose layout technique (however, we generally advise to use [[#stress minimization|stress minimization]] due to better scaling and quality). <br />
The available method is an instance of force-directed methods in which a network is likened to a physical system of repelling objects (the nodes) and springs of a given length (the links) binding adjacent nodes together. <br />
Nodes are iteratively repositioned based on the forces exerted on them, so that the system moves toward a force equilibrium.<br />
<br />
<!-- See the spring embedder [[spring embedder|concept page]] for further details. --><br />
<br />
==== spectral layout ====<br />
<br />
Spectral layout computes positions based on Eigenvectors of a networks adjacency matrix or the corresponding Laplacian.<br />
<br />
<!-- See the spectral layout [[spectral layout|concept page]] for more details. --><br />
<br />
==== circular layout ====<br />
<br />
Circular layout arranges nodes on one or more circles, based on the connectedness in the network.<br />
<br />
<!-- See the circular layout [[circular layout|concept page]] for details. --><br />
<br />
==== random layout ====<br />
<br />
Random layout assigns a random position for each node.<br />
<br />
=== link routing ===<br />
<br />
Links are re-routed to avoid overlap between nodes and links, by introducing or moving bend-points of links. <br />
<br />
<!-- See the link routing [[link routing|concept page]] for details on available options. --><br />
<br />
=== label placement ===<br />
<br />
rearranges label positions to avoid overlap with nodes and links.<br />
<br />
== mapping ==<br />
<br />
Methods in the mapping category are all used to map attribute values to visual attributes of the network diagram. <br />
Graphical attributes are [[#color|color]], [[#size|size]], and [[#label|labels]]. These are available for both nodes and links.<br />
Mappings only available for nodes are the mappings to the geometrical attributes [[#coordinates|coordinates]], and the [[#z-layer|order]] in wich nodes are rendered.<br />
<br />
==== color ====<br />
<br />
A mapping for node and link attributes to the color of nodes, node borders and links, suitable for both numerical and categorial attributes. <br />
For numerical attributes, values can be mapped by means of <br />
* interpolation in the RGB color space between a given color for the minimum value and a given color for the maximum value.<br />
* saturation of a given color.<br />
* brightness of a given color.<br />
Categorial attributes can be mapped by specifying a color table.<br />
<br />
==== size ====<br />
<br />
A mapping for node and link attributes to node area, width or height, or link width. <br />
This mapping is only allowed for numerical attributes.<br />
<br />
==== label ====<br />
<br />
A mapping for node and link attributes to properties of the corresponding labels. <br />
Available options are:<br />
* plain mapping of the attribute value to label texts.<br />
* mapping of values given by the attribute to label colors (in the same way as color-mapping for nodes and links).<br />
* mapping of numerical attribute values to font-sizes of labels.<br />
<br />
==== coordinates ====<br />
<br />
A mapping for numerical node attributes to coordinates in either x- or y-direction. <br />
Attribute values can be applied directly, or interploated to fit into the dimensions of the network's current diagram. <br />
Horizontal or vertical lines drawn in the background indicate corresponding attribute values.<br />
<br />
[[Geographic Mapping]] of longitude/latitude coordinates together with a map on the background is also possible.<br />
<br />
==== z-layer ====<br />
<br />
A mapping for numerical node attributes to the order in which nodes are drawn in the diagram. <br />
In case of overlap, nodes with a lower value will be beneath nodes with a higher value.<br />
<br />
== geometry ==<br />
<br />
The geometry category provides mechanisms to alter the layout of a network by means of purely geometric operations, so called affine transformations.<br />
<br />
=== affine transformations ===<br />
<br />
Affine transformations provided in visone are translation, rotation, scaling and reflection. <br />
<br />
=== procrustes analysis ===<br />
<br />
Networks in a network collection are automatically translated, rotated, and scaled to match the cofiguration of a reference network or the previous network in the collection as good as possible.</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Geographic_Mapping&diff=1501Geographic Mapping2015-03-13T07:45:54Z<p>Nocaj: </p>
<hr />
<div>In geographical networks the layout of nodes can be determined by some geographic coordinates.<br />
<br />
The geographic mapping allows the representation of geographical networks, whose node positions are characterized by longitude and latitude, over the corresponding map. <br />
<br />
The main features are:<br />
* map nodes: positions based on two node attributes (longitude latitude) using mercator projection<br />
* update map: download a map from the selected open street map provider and map it on the background (internet connection required)<br />
<br />
If just the nodes should be mapped, e.g., without redownloading a new map, then "update map" can be deactivated.<br />
<br />
Several map styles and different levels of detail can be selected by the user.<br />
<br />
<br />
{|<br />
|+ valign="top"| Communication network: <br />
| 9 students at the University of Konstanz living in the Bodensee region and communicating during the semester break<br />
|- halign="center"<br />
| style="text-align: center;" |[[File:geomap.png|400px]]<br />
|<br />
|}<br />
<br />
=== Example Data ===<br />
The communication network of 9 students at the University of Konstanz during the semester break:<br />
* graphml file with network containing geographic node attributes [[File:geonet-withoutMap.graphmlz]]<br />
* graphml file with geographically mapped nodes and map [[File:geonet-withMap.graphmlz]]</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Geographic_Mapping&diff=1500Geographic Mapping2015-03-13T07:39:14Z<p>Nocaj: </p>
<hr />
<div>In geographical networks the layout of nodes is fixed and determined by some coordinates.<br />
<br />
The geographic mapping allows the representation of geographical networks, whose node positions are characterized by latitude and longitude, over the corresponding map. <br />
<br />
The map is downloaded from OpenStreetMaps, and therefore an internet connection is required when plotting a geographic network for the first time. When the position of the nodes is modified to avoid node overlapping, then the original position of the node can be recovered unchecking the option map nodes and visualizing the network. In this case the background map is not re-downloaded from the internet. Thus, an internet connection is not necessary.<br />
<br />
Several map styles with a specific area and level of detail can be selected by the user.<br />
<br />
<br />
{|<br />
|+ valign="top"| Communication network: <br />
| 9 students at the University of Konstanz living in the Bodensee region and communicating during the semester break<br />
|- halign="center"<br />
| style="text-align: center;" |[[File:geomap.png|400px]]<br />
|<br />
|}<br />
<br />
=== Example Data ===<br />
The communication network of 9 students at the University of Konstanz during the semester break:<br />
* graphml file with network containing geographic node attributes [[File:geonet-withoutMap.graphmlz]]<br />
* graphml file with geographically mapped nodes and map [[File:geonet-withMap.graphmlz]]</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=File:Geonet-withMap.graphmlz&diff=1499File:Geonet-withMap.graphmlz2015-03-13T07:35:25Z<p>Nocaj: small network with geographic node attributes (longitude and latitude) mapped with a map on the background</p>
<hr />
<div>small network with geographic node attributes (longitude and latitude) mapped with a map on the background</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=File:Geonet-withoutMap.graphmlz&diff=1498File:Geonet-withoutMap.graphmlz2015-03-13T07:33:20Z<p>Nocaj: small network with geographic node attributes (longitude and latitude)</p>
<hr />
<div>small network with geographic node attributes (longitude and latitude)</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Louvain_Clustering&diff=1495Louvain Clustering2015-03-12T13:42:50Z<p>Nocaj: Created page with "=Louvain Clustering= === Method === Starting with a state where each node is a singleton cluster, it greedily merges two clusters if the modularity score gets higher. === Comple..."</p>
<hr />
<div>=Louvain Clustering=<br />
=== Method ===<br />
Starting with a state where each node is a singleton cluster, it greedily merges two clusters if the modularity score gets higher.<br />
<br />
=== Complexity ===<br />
The algorithms scales well for large graphs <br />
<br />
=== References ===<br />
*Fast unfolding of communities in large networks, Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre, Journal of Statistical Mechanics: Theory and Experiment 2008 (10), P10008 (12pp) doi: 10.1088/1742-5468/2008/10/P10008. ArXiv: http://arxiv.org/abs/0803.0476<br />
*"The Louvain method for community detection in large networks" Vincent Blondel http://perso.uclouvain.be/vincent.blondel/research/louvain.html</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Geographic_Mapping&diff=1494Geographic Mapping2015-03-12T12:43:14Z<p>Nocaj: Created page with "this will be the page describing the geographic mapping, together with an example dataset"</p>
<hr />
<div>this will be the page describing the geographic mapping, together with an example dataset</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Backbone_Layout&diff=1492Backbone Layout2014-11-05T11:07:26Z<p>Nocaj: </p>
<hr />
<div>=Backbone Layout=<br />
===Method===<br />
Small-world graphs have characteristically low average distance and thus cause force-directed methods to generate drawings that look like hairballs.<br />
<br />
The backbone layout tries to untangle hairball graphs. The method is based on a spanning subgraph that is sparse but connected and consists of strong ties holding together communities. <br />
Strong ties are identified using a structural measures of embeddedness.<br />
<br />
More detailed background information is provided in<br />
<br />
* Arlind Nocaj, Mark Ortmann, and Ulrik Brandes: [http://inf.uni-konstanz.de/~nocaj/publications/nob-uh-14.pdf Untangling Hairballs: From 3 to 14 Degrees of Separation], Proc. 22nd Intl. Symp. Graph Drawing (GD 2014), 2014.<br />
<br />
<br />
{|<br />
|+ valign="top"| Facebook friendships at California Institute of Technology (Caltech36). Vertex color corresponds to dormitory (gray for missing values), but has not been utilized in the layout algorithm. The layout in '''(a)''' is based on the entire hairball graph, whereas '''(b)''' uses edge embeddedness which spreads the graph while keeping cohesive groups together. Embeddedness mapped to edge color; backbone edges dark gray.<br />
|- halign="center"<br />
| style="text-align: center;" |[[File:Caltech36-hairball.png|300px]]<br />
|- <br />
| style="text-align: center;" |'''(a)''' drawing based on complete network<br />
|-<br />
| style="text-align: center;" |[[File:Caltech36-Quadrilateral-Backbone.png|500px]]<br />
|-<br />
| style="text-align: center;" |'''(b)''' drawing based on quadrilateral Simmelian backbone<br />
|<br />
|}<br />
<br />
=== Complexity ===<br />
The computation of the embeddedness together with the backbone extraction scales well for large networks with, e.g., millions of edges and nodes.<br />
<br />
The asymptotic runtime is <math> O(|E| \triangle(G))</math> for a graph <math>G=(V,E)</math> where <math>\triangle(G)</math> is the maximum degree of a vertex <math> v\in V</math>. <br />
<br />
<br />
The final layout based on the extracted backbone needs <math>O(|V|^2)</math> time and memory, which does not scale for very large graphs.<br />
<br />
=== Example Data ===<br />
A set of 50 synthetic hairball networks with a hidden group structure:<br />
* [[Media:Hairball-Graphs-PPM500.zip|'''Dataset''']] (11 MB) and its [[Hairball_Graphs_(data)| '''Description''']]</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Backbone_Layout&diff=1491Backbone Layout2014-11-05T11:05:44Z<p>Nocaj: </p>
<hr />
<div>=Backbone Layout=<br />
===Method===<br />
Small-world graphs have characteristically low average distance and thus cause force-directed methods to generate drawings that look like hairballs.<br />
<br />
The backbone layout tries to untangle hairball graphs. The method is based on a spanning subgraph that is sparse but connected and consists of strong ties holding together communities. <br />
Strong ties are identified using a structural measures of embeddedness.<br />
<br />
More detailed background information is provided in<br />
<br />
* [http://inf.uni-konstanz.de/~nocaj/publications/nob-uh-14.pdf Arlind Nocaj, Mark Ortmann, and Ulrik Brandes: Untangling Hairballs: From 3 to 14 Degrees of Separation, Proc. 22nd Intl. Symp. Graph Drawing (GD 2014), 2014].<br />
<br />
<br />
{|<br />
|+ valign="top"| Facebook friendships at California Institute of Technology (Caltech36). Vertex color corresponds to dormitory (gray for missing values), but has not been utilized in the layout algorithm. The layout in '''(a)''' is based on the entire hairball graph, whereas '''(b)''' uses edge embeddedness which spreads the graph while keeping cohesive groups together. Embeddedness mapped to edge color; backbone edges dark gray.<br />
|- halign="center"<br />
| style="text-align: center;" |[[File:Caltech36-hairball.png|300px]]<br />
|- <br />
| style="text-align: center;" |'''(a)''' drawing based on complete network<br />
|-<br />
| style="text-align: center;" |[[File:Caltech36-Quadrilateral-Backbone.png|500px]]<br />
|-<br />
| style="text-align: center;" |'''(b)''' drawing based on quadrilateral Simmelian backbone<br />
|<br />
|}<br />
<br />
=== Complexity ===<br />
The computation of the embeddedness together with the backbone extraction scales well for large networks with, e.g., millions of edges and nodes.<br />
<br />
The asymptotic runtime is <math> O(|E| \triangle(G))</math> for a graph <math>G=(V,E)</math> where <math>\triangle(G)</math> is the maximum degree of a vertex <math> v\in V</math>. <br />
<br />
<br />
The final layout based on the extracted backbone needs <math>O(|V|^2)</math> time and memory, which does not scale for very large graphs.<br />
<br />
=== Example Data ===<br />
A set of 50 synthetic hairball networks with a hidden group structure:<br />
* [[Media:Hairball-Graphs-PPM500.zip|'''Dataset''']] (11 MB) and its [[Hairball_Graphs_(data)| '''Description''']]</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Backbone_Layout&diff=1490Backbone Layout2014-08-28T13:13:09Z<p>Nocaj: </p>
<hr />
<div>=Backbone Layout=<br />
===Method===<br />
Small-world graphs have characteristically low average distance and thus cause force-directed methods to generate drawings that look like hairballs.<br />
<br />
The backbone layout tries to untangle hairball graphs. The method is based on a spanning subgraph that is sparse but connected and consists of strong ties holding together communities. <br />
Strong ties are identified using a structural measures of embeddedness.<br />
<br />
More detailed background information is provided in<br />
<br />
* Arlind Nocaj, Mark Ortmann, and Ulrik Brandes: Untangling Hairballs: From 3 to 14 Degrees of Separation, Proc. 22nd Intl. Symp. Graph Drawing (GD 2014), to appear.<br />
<br />
<br />
{|<br />
|+ valign="top"| Facebook friendships at California Institute of Technology (Caltech36). Vertex color corresponds to dormitory (gray for missing values), but has not been utilized in the layout algorithm. The layout in '''(a)''' is based on the entire hairball graph, whereas '''(b)''' uses edge embeddedness which spreads the graph while keeping cohesive groups together. Embeddedness mapped to edge color; backbone edges dark gray.<br />
|- halign="center"<br />
| style="text-align: center;" |[[File:Caltech36-hairball.png|300px]]<br />
|- <br />
| style="text-align: center;" |'''(a)''' drawing based on complete network<br />
|-<br />
| style="text-align: center;" |[[File:Caltech36-Quadrilateral-Backbone.png|500px]]<br />
|-<br />
| style="text-align: center;" |'''(b)''' drawing based on Simmelian backbone with quadrilateral index<br />
|<br />
|}<br />
<br />
=== Complexity ===<br />
The computation of the embeddedness together with the backbone extraction scales well for large networks with, e.g., millions of edges and nodes.<br />
<br />
The asymptotic runtime is <math> O(|E| \triangle(G))</math> for a graph <math>G=(V,E)</math> where <math>\triangle(G)</math> is the maximum degree of a vertex <math> v\in V</math>. <br />
<br />
<br />
The final layout based on the extracted backbone needs <math>O(|V|^2)</math> time and memory, which does not scale for very large graphs.<br />
<br />
=== Example Data ===<br />
A set of 50 synthetic hairball networks with a hidden group structure:<br />
* [[Media:Hairball-Graphs-PPM500.zip|'''Dataset''']] (11 MB) and its [[Hairball_Graphs_(data)| '''Description''']]</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Backbone_Layout&diff=1489Backbone Layout2014-08-28T13:12:42Z<p>Nocaj: </p>
<hr />
<div>=Backbone Layout=<br />
===Method===<br />
Small-world graphs have characteristically low average distance and thus cause force-directed methods to generate drawings that look like hairballs.<br />
<br />
The backbone layout tries to untangle hairball graphs. The method is based on a spanning subgraph that is sparse but connected and consists of strong ties holding together communities. <br />
Strong ties are identified using a structural measures of embeddedness.<br />
<br />
More detailed background information is provided in<br />
<br />
* Arlind Nocaj, Mark Ortmann, and Ulrik Brandes: Untangling Hairballs: From 3 to 14 Degrees of Separation, Proc. 22nd Intl. Symp. Graph Drawing (GD 2014), to appear.<br />
<br />
<br />
{|<br />
|+ valign="top"| Facebook friendships at California Institute of Technology (Caltech36). Vertex color corresponds to dormitory (gray for missing values), but has not been utilized in the layout algorithm. The layout in '''(a)''' is based on the entire hairball graph, whereas '''(b)''' uses edge embeddedness which spreads the graph while keeping cohesive groups together. Embeddedness mapped to edge color; backbone edges dark gray.<br />
|- halign="center"<br />
| style="text-align: center;" |[[File:Caltech36-hairball.png|300px]]<br />
|- <br />
| style="text-align: center;" |'''(a)''' drawing based on complete network<br />
|-<br />
| style="text-align: center;" |[[File:Caltech36-Quadrilateral-Backbone.png|500px]]<br />
|-<br />
| style="text-align: center;" |'''(b)''' drawing based on Simmelian backbone with quadrilateral index<br />
|<br />
|}<br />
<br />
=== Complexity ===<br />
The computation of the embeddedness together with the backbone extraction scales well for large networks with, e.g., millions of edges and nodes.<br />
<br />
The asymptotic runtime is <math> O(|E| \triangle(G))</math> for a graph <math>G=(V,E)</math> where <math>\triangle(G)</math> is the maximum degree of a vertex <math> v\in V</math>. <br />
<br />
<br />
The final layout based on the extracted backbone needs <math>O(|V|^2)</math> time and memory, which does not scale for very large graphs.<br />
<br />
=== Example Data ===<br />
A set of 50 synthetic hairball networks with a hidden group structure:<br />
* [[Media:Hairball-Graphs-PPM500.zip|'''Hairball-Graphs-PPM500.zip''']] (11 MB) and its [[Hairball_Graphs_(data)| '''Description''']]</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Backbone_Layout&diff=1488Backbone Layout2014-08-28T13:11:02Z<p>Nocaj: /* Method */</p>
<hr />
<div>=Backbone Layout=<br />
===Method===<br />
Small-world graphs have characteristically low average distance and thus cause force-directed methods to generate drawings that look like hairballs.<br />
<br />
The backbone layout tries to untangle hairball graphs. The method is based on a spanning subgraph that is sparse but connected and consists of strong ties holding together communities. <br />
Strong ties are identified using a structural measures of embeddedness.<br />
<br />
More detailed background information is provided in<br />
<br />
* Arlind Nocaj, Mark Ortmann, and Ulrik Brandes: Untangling Hairballs: From 3 to 14 Degrees of Separation, Proc. 22nd Intl. Symp. Graph Drawing (GD 2014), to appear.<br />
<br />
<br />
{|<br />
|+ valign="top"| Facebook friendships at California Institute of Technology (Caltech36). Vertex color corresponds to dormitory (gray for missing values), but has not been utilized in the layout algorithm. The layout in '''(a)''' is based on the entire hairball graph, whereas '''(b)''' uses edge embeddedness which spreads the graph while keeping cohesive groups together. Embeddedness mapped to edge color; backbone edges dark gray.<br />
|- halign="center"<br />
| style="text-align: center;" |[[File:Caltech36-hairball.png|300px]]<br />
|- <br />
| style="text-align: center;" |'''(a)''' drawing based on complete network<br />
|-<br />
| style="text-align: center;" |[[File:Caltech36-Quadrilateral-Backbone.png|500px]]<br />
|-<br />
| style="text-align: center;" |'''(b)''' drawing based on Simmelian backbone with quadrilateral index<br />
|<br />
|}<br />
<br />
=== Complexity ===<br />
The computation of the embeddedness together with the backbone extraction scales well for large networks with, e.g., millions of edges and nodes.<br />
<br />
The asymptotic runtime is <math> O(|E| \triangle(G))</math> for a graph <math>G=(V,E)</math> where <math>\triangle(G)</math> is the maximum degree of a vertex <math> v\in V</math>. <br />
<br />
<br />
The final layout based on the extracted backbone needs <math>O(|V|^2)</math> time and memory, which does not scale for very large graphs.<br />
<br />
=== Example Data ===<br />
A set of 50 synthetic hairball networks with a hidden group structure:<br />
* [[Hairball_Graphs_(data)| '''Dataset Description''']]<br />
* Download: [[Media:Hairball-Graphs-PPM500.zip|'''Hairball-Graphs-PPM500.zip''']] (11 MB)</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Visualization_tab&diff=1487Visualization tab2014-08-28T13:08:42Z<p>Nocaj: </p>
<hr />
<div>Visualization algorithms change the graphical appearance of the network; they are accesible via the visualization tab. Basic illustrations of how to layout networks or display attribute values are provided in the two tutorials on [[Visualization_and_analysis_(tutorial)|''visualization and analysis'']] and [[Managing_attributes_(tutorial)|''advanced attribute management'']].<br />
<br />
visone distinguishes between three major '''visualization categories'''<br />
* ''layout'' to recompute the positions (coordinates) or nodes, links-bends, or labels to optimize readability or other specified layout criteria;<br />
* ''mapping'' to specify how attribute values (such as node centrality, tie strength, or class membership) are encoded in grapical variables (such as size, width, or color);<br />
* ''geometry'' to apply geometric transformations such as rotation, reflection, or scaling to the network or parts of the network; <br />
<br />
== layout ==<br />
<br />
''Layout'' refers to the task of obtaining positions for the elements of a network visualization, where [[#node layout|computing node positions]] is of primary interest. <br />
Other tasks are [[#link routing|(re-)routing the links]] of a visualization, e.g. to avoid overlap between link and node representations, or to automatically [[#label placement|arrange label positions]] for better readability.<br />
<br />
<br />
=== node layout ===<br />
<br />
The methods in this section deal with the computation of node positions for one or more networks. Generally, nodes are considered to be geometric points (or objects that are described by a single point), and links are represented as straight lines between their incident nodes. <br />
Thus, most methods produce so called ''straight-line drawings'' (also referred to as ''node-link diagrams'' or ''sociograms''). <br />
<br />
There are several general objectives that most methods try to optimize, such as:<br />
* links should have more or less the same length.<br />
* nodes should be distributed well over the drawing area.<br />
* the number of meaningless link crossings should be kept small.<br />
* structural symmetries in the network should be represented well.<br />
<br />
Additionally, some methods are constrained by additional or different objectives:<br />
* node placement is restricted with respect to a given scalar node attribute, e.g., such that nodes lie on [[#centrality layout|concentric circles]] or [[#status layout| verical layers]] corresponding to the attributes values.<br />
* given a [[#dynamic layout|sequence of networks]], the layout should ease comparison with respect to the layout of the previous network in the sequence.<br />
* the layout should reveal [[#spectral layout|specific structural properties]].<br />
<br />
<br />
<br />
==== stress minimization ====<br />
<br />
Stress minimization, an instance of a family of dimension-reduction techniques referred to as ''multidimensional scaling'' (MDS), is our preferred method to obtain a general-purpose layout for networks.<br />
The main idea is to compute a layout such that graph-theoretic distances (i.e., shortest-path lengths) between nodes are represented as good as possible, where more weight is placed on representation error with respect to shorter distances than larger ones. <br />
The method usually meets the general criteria mentioned above, and yields better results than [[#spring embedder|spring embedders]] in most cases.<br />
<br />
Note that the outcome of stress minimization is dependent on the current layout of the network.<br />
We suggest to compute a [[#metric MDS|metric MDS]] layout first to obtain good results.<br />
Also note that computing a layout via the [[Quick_layout|quick layout]] button corresponds to this procedure, i.e., applying stress minimization to a metric MDS layout.<br />
<br />
<!-- For more details on the options available in visone, see the [[stress minimization|concept page]] for stress minimization. --><br />
<br />
==== backbone layout ====<br />
The backbone layout tries to untangle hairball graphs. The method is based on a spanning subgraph that is sparse but connected and consists of strong ties holding together communities. For more details see the [[Backbone_Layout|concept page]].<br />
<br />
<br />
==== metric MDS ====<br />
<br />
Metric MDS, also referred to as ''classical scaling'' is the original, spectral-decomposition variant of multidimensional scaling. <br />
As with [[#stress minimization|stress minimization]], the goal is to represent shortest-path distances as well as possible. <br />
In contrast to stress minimization all distances are treated equally. <br />
Thus, this approach generally yields good representation of large distance, but poor representation of shorter distances, affecting layout quality. <br />
However, since metric MDS produces a unique solution, it is suited well to serve as initialization for stress minimization.<br />
<br />
<!-- See the metric MDS [[metric MDS|concept page]] for more technical details. --><br />
<br />
==== centrality layout ====<br />
<br />
Centrality layout, like [[#status layout|status layout]] is used to obtain a layout that represents values of a given numerical nodal attribute, e.g. a centrality index of nodes. <br />
Nodes with the same attribute value are arranged on concentric circles, where nodes with higher value are closer to the center, and nodes with lower value are in the periphery.<br />
At the same time, the algorithm tries to reduce link crossings as much as possible. <br />
Circumferences corresponding to regular intervals with respect to the attribute values are shown in the background of the visualization, to increase legibility of each node's corresponding value.<br />
<br />
<!-- See the centrality layout [[centrality layout|concept page]] for details on available options. --><br />
<br />
==== status layout ====<br />
<br />
Status layout, like [[#centrality layout|centrality layout]] is used to obtain a layout that represents values of a given numerical nodal attribute, e.g. a centrality index of nodes. <br />
Nodes with the same attribute value are arranged on horizontal lines, where nodes with higher value are closer to the top, and nodes with lower value are closer to the bottom of the drawing. <br />
The algorithm tries to avoid link crossings. <br />
Note also, that bend-points for the links are introduced to increase readability. <br />
Optionally, the status niveaus (i.e., horizontal lines) corresponding to attribute values can be shown in the background of the visualization.<br />
<br />
<!-- See the status layout [[status layout|concept page]] for more details. --><br />
<br />
==== dynamic layout ====<br />
<br />
Dynamic layout refers to techniques for obtaining coherent positions of nodes for several networks, usually embodying a time-series of a network. <br />
The goal is to convey the evolution of the network, by easing comparison between a current layout and the preceeding one. <br />
In visone, three methods are currently offered to obtain a dynamic layout, all based on [[#stress minimization|stress minimization]].<br />
One approach calculates one single layout for an aggregate of all individual networks, and applies these positions, i.e., all nodes strictly maintain their position throughout the sequence. <br />
The other two approaches trade off this perfect stability for better readability of individual networks. <br />
<br />
Note that dynamic layout can only be applied to [[network collection|network collections]]. <br />
Also, visone provides [[animation]] of the sequence via the [[File:Animation.png|link=animation]] icon in the [[GUI#toolbar|toolbar]]. <br />
<br />
<!-- See the dynamic layout [[dynamic layout|concept page]] for more information on technical details and available options. --><br />
<br />
==== stress minimization (dyad attributes) ====<br />
<br />
This method differs from standard [[#stress minimization|stress minization]] in the choice of input distances. <br />
Usually, shortest-path distances are considered. <br />
Here, any numerical dyad attribute may be choosen as input.<br />
The method then tries to arrange nodes, such that those distances are matched as well as possible in the layout. <br />
<br />
==== spring embedder ====<br />
<br />
The spring embedder is the most commonly known general-purpose layout technique (however, we generally advise to use [[#stress minimization|stress minimization]] due to better scaling and quality). <br />
The available method is an instance of force-directed methods in which a network is likened to a physical system of repelling objects (the nodes) and springs of a given length (the links) binding adjacent nodes together. <br />
Nodes are iteratively repositioned based on the forces exerted on them, so that the system moves toward a force equilibrium.<br />
<br />
<!-- See the spring embedder [[spring embedder|concept page]] for further details. --><br />
<br />
==== spectral layout ====<br />
<br />
Spectral layout computes positions based on Eigenvectors of a networks adjacency matrix or the corresponding Laplacian.<br />
<br />
<!-- See the spectral layout [[spectral layout|concept page]] for more details. --><br />
<br />
==== circular layout ====<br />
<br />
Circular layout arranges nodes on one or more circles, based on the connectedness in the network.<br />
<br />
<!-- See the circular layout [[circular layout|concept page]] for details. --><br />
<br />
==== random layout ====<br />
<br />
Random layout assigns a random position for each node.<br />
<br />
=== link routing ===<br />
<br />
Links are re-routed to avoid overlap between nodes and links, by introducing or moving bend-points of links. <br />
<br />
<!-- See the link routing [[link routing|concept page]] for details on available options. --><br />
<br />
=== label placement ===<br />
<br />
rearranges label positions to avoid overlap with nodes and links.<br />
<br />
== mapping ==<br />
<br />
Methods in the mapping category are all used to map attribute values to visual attributes of the network diagram. <br />
Graphical attributes are [[#color|color]], [[#size|size]], and [[#label|labels]]. These are available for both nodes and links.<br />
Mappings only available for nodes are the mappings to the geometrical attributes [[#coordinates|coordinates]], and the [[#z-layer|order]] in wich nodes are rendered.<br />
<br />
==== color ====<br />
<br />
A mapping for node and link attributes to the color of nodes, node borders and links, suitable for both numerical and categorial attributes. <br />
For numerical attributes, values can be mapped by means of <br />
* interpolation in the RGB color space between a given color for the minimum value and a given color for the maximum value.<br />
* saturation of a given color.<br />
* brightness of a given color.<br />
Categorial attributes can be mapped by specifying a color table.<br />
<br />
==== size ====<br />
<br />
A mapping for node and link attributes to node area, width or height, or link width. <br />
This mapping is only allowed for numerical attributes.<br />
<br />
==== label ====<br />
<br />
A mapping for node and link attributes to properties of the corresponding labels. <br />
Available options are:<br />
* plain mapping of the attribute value to label texts.<br />
* mapping of values given by the attribute to label colors (in the same way as color-mapping for nodes and links).<br />
* mapping of numerical attribute values to font-sizes of labels.<br />
<br />
==== coordinates ====<br />
<br />
A mapping for numerical node attributes to coordinates in either x- or y-direction. <br />
Attribute values can be applied directly, or interploated to fit into the dimensions of the network's current diagram. <br />
Horizontal or vertical lines drawn in the background indicate corresponding attribute values.<br />
<br />
==== z-layer ====<br />
<br />
A mapping for numerical node attributes to the order in which nodes are drawn in the diagram. <br />
In case of overlap, nodes with a lower value will be beneath nodes with a higher value.<br />
<br />
== geometry ==<br />
<br />
The geometry category provides mechanisms to alter the layout of a network by means of purely geometric operations, so called affine transformations.<br />
<br />
=== affine transformations ===<br />
<br />
Affine transformations provided in visone are translation, rotation, scaling and reflection. <br />
<br />
=== procrustes analysis ===<br />
<br />
Networks in a network collection are automatically translated, rotated, and scaled to match the cofiguration of a reference network or the previous network in the collection as good as possible.</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Backbone_Layout&diff=1486Backbone Layout2014-08-28T12:57:58Z<p>Nocaj: </p>
<hr />
<div>=Backbone Layout=<br />
===Method===<br />
Small-world graphs have characteristically low average distance and thus cause force-directed methods to generate drawings that look like hairballs.<br />
<br />
The backbone layout tries to untangle hairball graphs. The method is based on a spanning subgraph that is sparse but connected and consists of strong ties holding together communities.<br />
<br />
Strong ties are identified using a measure of embeddedness which is based on a weighted accumulation of triangles in quadrangles.<br />
<br />
More detailed background information is provided in<br />
<br />
* Arlind Nocaj, Mark Ortmann, and Ulrik Brandes: Untangling Hairballs: From 3 to 14 Degrees of Separation, Proc. 22nd Intl. Symp. Graph Drawing (GD 2014), to appear.<br />
<br />
<br />
{|<br />
|+ valign="top"| Facebook friendships at California Institute of Technology (Caltech36). Vertex color corresponds to dormitory (gray for missing values), but has not been utilized in the layout algorithm. The layout in '''(a)''' is based on the entire hairball graph, whereas '''(b)''' uses edge embeddedness which spreads the graph while keeping cohesive groups together. Embeddedness mapped to edge color; backbone edges dark gray.<br />
|- halign="center"<br />
| style="text-align: center;" |[[File:Caltech36-hairball.png|300px]]<br />
|- <br />
| style="text-align: center;" |'''(a)''' drawing based on complete network<br />
|-<br />
| style="text-align: center;" |[[File:Caltech36-Quadrilateral-Backbone.png|500px]]<br />
|-<br />
| style="text-align: center;" |'''(b)''' drawing based on Simmelian backbone with quadrilateral index<br />
|<br />
|}<br />
<br />
=== Complexity ===<br />
The computation of the embeddedness together with the backbone extraction scales well for large networks with, e.g., millions of edges and nodes.<br />
<br />
The asymptotic runtime is <math> O(|E| \triangle(G))</math> for a graph <math>G=(V,E)</math> where <math>\triangle(G)</math> is the maximum degree of a vertex <math> v\in V</math>. <br />
<br />
<br />
The final layout based on the extracted backbone needs <math>O(|V|^2)</math> time and memory, which does not scale for very large graphs.<br />
<br />
=== Example Data ===<br />
A set of 50 synthetic hairball networks with a hidden group structure:<br />
* [[Hairball_Graphs_(data)| '''Dataset Description''']]<br />
* Download: [[Media:Hairball-Graphs-PPM500.zip|'''Hairball-Graphs-PPM500.zip''']] (11 MB)</div>Nocajhttps://visone.ethz.ch/wiki/index.php?title=Applications&diff=1485Applications2014-08-28T12:52:42Z<p>Nocaj: </p>
<hr />
<div>On this page we list datasets on which the usage of visone can be illustrated.<br />
<br />
== Empirical datasets ==<br />
<br />
* [[Egoredes_(data)|'''Egoredes''' acculturation networks]]: personal networks of immigrants<br />
* [[Signos_(data)|'''Signos''']] newer and more comprehensive data about personal networks of immigrants than the Egoredes data above<br />
* [[Newcomb_Fraternity_(data)|'''Newcomb Fraternity Data''']]<br />
* [[Knecht_Classroom_(data)|'''Knecht Classroom Data''']]: four observations of a classroom friendship network<br />
* [[Penn State Event Data|'''Penn State Event Data''']]: event data about political conflict and cooperation (formerly ''Kansas Event Data System (KEDS)'')<br />
<br />
== Workshop data ==<br />
<br />
* [[Sunbelt_workshop_(data)|'''Data for Sunbelt XXXIII (2013) visone workshop''']]<br />
<br />
* [[Introductory_workshop_(data)|'''Data for ASNA 2011 workshop''']]<br />
<br />
== Synthetic datasets ==<br />
<br />
* [[Hairball_Graphs_(data)| '''Hairball Graphs''']]: 50 synthetic hairball graphs with a hidden group structure<br />
<br />
== Auxiliary software ==<br />
<br />
* [[EgoNet2GraphML_(software)|EgoNet2GraphML]] can (1) convert EgoNet interviews into GraphML files (that can be opened with visone) and (2) cluster, aggregate, and visualize collections of personal networks using the methodology proposed in: Ulrik Brandes, Juergen Lerner, Miranda J. Lubbers, Chris McCarty, and Jose Luis Molina '''"Visual Statistics for Collections of Clustered Graphs"'''. ''Proc. IEEE Pacific Visualization Symp. (PacificVis'08)'', 2008 ([http://www.inf.uni-konstanz.de/algo/publications/bllmm-vsccg-08.pdf ''link to pdf'']).<br />
* [[WikiEvent_(software)|'''WikiEvent''']] is a small graphical java software with which the '''''edit network''''' associated with the history of [http://www.wikipedia.org Wikipedia] pages can be computed. See the [[Wikipedia_edit_networks_(tutorial)| tutorial on Wikipedia edit networks]].</div>Nocaj