Last update:
Program for analysing large networks (networks having thousands of
vertices).
Five objects are used for that purpose:
Networks - main objects (vertices and connections).
Default extansion: .net.
Network can be presented on input file in different ways:
using arcs/edges (e.g. 1 2 - line from 1 to 2)
using arcslists/edgeslists
(e.g. 1 2 3 - line from 1 to 2 and from 1 to 3)
Vega format (look at Pisanski project Vega)
I hope formats are self-explanatory. Using one of presentations
structure of network is defined. You can also add information
for network drawing. This is explained in
Drawnet.htm.
Partitions - they tell for each vertex to which class vertex belong.
Default extansion: .clu.
Permutations - reordering of vertices.
Default extansion: .per.
Clusters - subset of vertices (e.g. one class from partition).
Default extansion: .cls.
Root has two subgroups - g1 and g2. g2 is leaf - cluster with
elements 5,6 and 7. g1 has two subgroups - g11 and g12....
Default extansion: .hie.
By double clicking on selected network, partition,...
you can show the object on screen. In the case of hierarchy
you can also edit it (change name and type of node).
Short description of menu
File Input/Output manipulation.
Network - N
Read network from Ascii file.
Edit graph. Choose vertex, show its neighbours,
add new lines to/from selected vertex
(by left mouse double clicking on Newline),
delete lines (by left mouse double clicking),
change value of line by single righ
mouse clicking.
Save selected network to Ascii file.
Dispose selected network from memory.
Partition - C
Read partition from Ascii file.
Edit partition.
Save selected partition to Ascii file.
Dispose selected partition from memory.
Permutation - P
Read permutation from Ascii file.
Save selected permutation to Ascii file.
Dispose selected permutation from memory.
Cluster - S (list of selected vertices)
Read cluster from Ascii file.
Save selected cluster to Ascii file.
Dispose selected cluster from memory.
Hierarchy - H
Read hierarchy from Ascii file.
Save selected hierarchy to Ascii file.
Dispose selected hierarchy from memory.
Repeat session - During program execution all commands are
written to file *.log. In this way you can repeat any execution by running
selected log file.
If you change name of file on disk to ?, program will ask for name when
running logfile next time (so you can repeat the same sequence of steps
- logfile with different input data).
Exit program.
Net - operations, for which only network is needed as input.
Transform
Transpose - Inverse (transpose) network of selected network
(change direction of arrows in directed network).
Remove
all edges - Remove all edges from selected network.
all arcs - Remove all arcs from selected network.
multiple lines - Remove all multiple lines from
selected network.
Values of all deleted lines are sumed
to not deleted line between corresponding two vertices.
loops - Remove all loops from selected network.
Edges->Arcs - Convert all edges to arcs (in both directions)
(make directed network).
Arcs->Edges
All - Convert all arcs to edges (make undirected network).
Bidirected only - Convert only arcs in both directions to edges.
Add source and sink - If network is acyclic, add unique first and
last vertex (new network has two artificial
vertices).
Reduction
Hierarchical - Recursively delete from network all vertices
that have only 0 or 1 neighbour. Results: simpler network and
hierarchy with deleted vertices. Original network can be later
restored (if we forget directions of lines).
Betweenness - Recursively delete from network all vertices
that have exactly 2 neighbours (together with corresponding two
lines) and (instead of that) add direct line between these
two neighbours. Result is simpler network (for drawing).
Original network cannot be restored!
Degree - (Recursively) delete from network all vertices
with degree lower than selected value (according to Input, Output or
All degree).
Original network cannot be restored!
Design (flow graph) Reductuion of all structural
parts of network according to McCabe (for programs - flow graphs).
Copy (Enlarge) - Copy network to new network.
Dimension can be enlarged for selected number of vertices
(additional vertices without lines are added).
Random Network - Generate network of selected dimension
and number of lines per vertex in given range.
Partitions - Partitioning Network. Result is a Partition.
Degree
Input - Number of lines into vertices.
Output - Number of lines out of vertices.
All - Number of neighbours of vertices.
Core - k-core is a subnetwork of given network
where each vertex has at least k neighbours in the same
core according to:
Input ... lines coming into vertex.
Output ... lines going out of vertex.
All ... all neighbours.
Depth
Acyclic Partition acyclic network according to depths of vertices.
Genealogy Partition genealogy network according to layers of vertices.
p-Cliques Partition network according to p-Cliques
(partition to clusters where vertices have at least proportion p
(number betwween 0 and 1) neighbours inside the cluster.
Strong ... for directed network.
Weak ... for undirected network.
Centers Find centers in a graph using robbery algorithm:
vertices that have higher degrees (are stronger) than their neighbours
steal from them:
at the beginning give to vertices initial strength according to
their degrees or start with value 1
when 'weak' vertex is found neighbours steal from him
according to their strengths or they steal the same amount
Vertex Labels Partition vertices with same labels to the same
class numbers (for moleculae).
Vertex Shapes Partition vertices with same shapes (ellipse,
box, diamond) to the same class numbers (used in genealogy to show gender).
Components
Strong - Strong Components of selected network.
Weak - Weak Components of selected network.
Bi-Components - Biconnected Components of selected network.
Articulation points belong to more classes, so the result cannot be
stored in partition - it is stored in hierarchy! Minimal number of
vertices in components can be selected.
Hierarchical Decomposition
Symmetric-Acyclic - Symmetric-Acyclic decomposition of
network. Result is hierarchy with nested clusters.
Numbering
Depth First - Depth first numbering of selected network...
Strong ... taking directions of arcs into account.
Citation Weights - If a network represents citation network,
weights of lines (citations) and vertices (articles) can be computed.
A new network with values on lines representing importances of
citations is generated.
Partition with importances of vertices (articles) is also generated.
(Numbers are multiplied by 10000). Two versions of algorithm:
Source - Sink - Paths Count Method.
Compute from Source to Sink.
Vertex -Sink - SPLC Method.
Each vertex is considered as Source.
k-Neighbours - From selected network select all vertices
Input ...from which we can reach selected vertex
in at most k-steps.
Output ...that can be reached from selected vertex
in at most k-steps.
All ...Input + Output (forget direction of lines)
Result is partition where vertices are in class numbers
equal to the distance from given vertex,
vertices that cannot be reached from selected vertex
are in class number 65534. After you have a partition you can extract
subnetwork.
Paths between 2 vertices
One Shortest - Find the shortest path between two vertices.
Result is new network. Values on lines can
be taken into account (if they present distances
between vertices) or not (graph theoretical distance).
The latter possibility is faster.
All Shortest - Find all shortest paths between two vertices.
Result is new network. Values on lines can
be taken into account (if they present distances
between vertices) or not (graph theoretical distance).
The latter possibility is faster.
All Paths - Find all paths between two vertices.
Result is partition where vertices that are on
the path are in class 1, others are in class 0.
Network still has to be extracted.
Diameter - Find diameter - the length of the longest
shortest path in network and corresponding
two vertices. Full search is performed,
so the operation may be slow for very large
networks (number of vertices larger than 2000).
Critical Path Method (CPM) - Find the critical path in acyclic
network - result is new network containing the critical path.
Algorithm can be used in the area of project planning
but also for analysing acyclic graphs. Another network
with source-sink added is generated. Values on lines in that
network represent free times of activities.
Additionally, two partitions are generated:
First containing the earliest possible times (integers)
of coming into given states and the
second containing the latest feasible times (integers)
of coming into given states.
Maximum Flow - Find and extract maximum flow between
given two vertices (algorithm looks for paths to be saturated
and among them it always selects the shortest path).
Algorithm can be used in the technical area (actual flow,
values on lines mean capacities) or for analysing graphs
(if all values are 1).
Nets - binary operations on networks. Two networks
must be selected before performing binary operations.
First Network - Network that is currently active,
will be used as first network in operations.
Second Network - Network that is currently active,
will be used as second network in operations.
Union of lines - Fuse selected networks. If you want to get
union of networks, multiple lines must still be deleted.
Intersection - Intersection of selected networks.
Difference - Difference of selected networks.
Union of vertices - Add the second network at the
end of first network.
Fragment (1 in 2) - Find all instances of
fragment (determined by network 1) in network 2.
Find Execute command.
Options Select appropriate model of fragment.
Induced - there should be no additional lines between
vertices in instance of fragment to match (stronger
condition) otherwise additional lines can be
present (weaker).
Labeled - labels must match (e.g. atoms in moleculae).
Check values of lines - values of lines must match
(e.g. in genealogy values represent sex: 1 - man, 2 - woman).
Check only cluster - only fragments are searched
where first vertex is one of the vertices in cluster.
Shrink coordinates (1 to 2) -
Useful if you shrink network, draw shrunk network separately,
and then apply all coordinates to vertices in original network
(vertices in same class get the same coordinates).
Replace coordinates in network 2 using coordinates of shrunk
network 1. Shrinking can be determined using
Partition or
Hierarchy
Operations - One network and something else is needed as input.
Shrink Network -
Before starting shrinking, select appropriate blockmodel in
Options menu. Default is just number of lines between shrunk vertices
that must be present in original network, to cause a line in a new
network.
Partition - Shrink network according to selected partition.
Vertices in class 0 are left unchanged, others are shrunk.
Hierarchy - Shrink network according to selected hierarchy.
Nodes in hierarchy that are Closed are shrunk to new vertex.
Cut nodes are shrunk to virtual vertex. Border
nodes are not shrunk, but they are not visible.
Vertices belonging to other nodes are left unchanged.
Type of shrinking (blockmodel) can be selected in Options menu.
Extract from Network
Partition - Extract sub-network according to selected
partition (extract range of classes from partition).
Cluster - Extract sub-network according to selected cluster.
to GEDCOM - Extract sub-genealogy according to selected
partition (for example one weakly connected
component) to new GEDCOM file (genealogy must be
read as Ore graph).
Transform - Transformations of network according to partition.
Remove Lines Inside Clusters - Remove all lines that have both
vertices in thex same (selected) cluster(s).
Reorder
Network - Reorder vertices in network according to
selected permutation.
Partition - Reorder vertices in partition according to
selected permutation.
Expand Reduction - Restore original network from reduced
network (hierarchical reduction!) and appropriate hierarchy (result is always undirected network).
R-Enumeration - Starting with network and
(random) permutation find such permutation
that numbers of vertices that belong to same
(strongly connected) groups are close to each other.
Greedy Partition - Put vertices in the same class as
are selected vertices in partition if
Input ...we can reach selected vertices in at most k-steps.
Output ...we can come to vertices from selected vertices
in at most k-steps.
All ...Input + Output (forget direction of lines)
Classes are joined if one vertex should belong to more classes.
Identify - Identify (reorder and/or join some units).
Petri - Execute Petri net according to starting marking
of places determined by partition. Number of places
in network is equal to dimension of partition.
Places must be defined furst (1..m) then
transitions (m+1..n).
What to do if more than one transition can fire?
Two possibilities:
Random - Transition is chosen randomly.
Complete - Complete tree of all possible transitions is built -
result is hierarchy. You can choose the maximum
depth of the tree, or execute Petri net
as long as possible.
Try for example -petri2.net petri2.clu-
from book of J. L. Peterson:
Petri Net Theory and the Modeling of Systems, p.21
or -petri51.net petri51.clu- p 65-67..
Refine Partition Refine partition according to selected network
(reachability).
Strong ... for directed network.
Weak ... for undirected network.
Partition - Only Partition is needed as input.
Create Null Partition - Create null partition of selected dimension.
Default dimension is the size of selected network
(if there is one in memory).
Binarize - Make binary (0-1) partition from selected
partition.
Canon Partition - Transform partition to its canonical (unique) form
(vertex 1 is always in class 1, the next vertex with smallest
number that is not in the same class as vertex 1 is in class 2...).
Make Random Network - Generate random network where
input or output degree of each vertex is fixed using partition.
Input - partition tells input degrees of vertices.
Output - partition tells output degrees of vertices.
Make Permutation - Make permutation from selected partition.
(first all vertices with the lowest class number, ...)
Make Cluster - Transform partition to cluster.
Make Hierarchy - Transform partition to hierarchy
(nested or not).
Partitions - operations on two partitions. Two partitions
must be selected before performing operations.
First Partition - Partition that is currently active,
will be used as first (original) partition in operations.
Second Partition - Partition that is currently active,
will be used as second (criterion) partition in operations.
Extract second from first - Extract from first partition vertices
that satisfy criterion (are on specified interval) determined by
second partition.
This operation is useful when we have partition that actually saves
some information about vertices (for example gender). When you get
(extract) some smaller part of the network (for example vertices
that are on distances less than 3 from selected vertex),
information about gender would be lost without performing the
same operation (extraction) on partition.
Add Partitions - Add two partitions (useful for example
when combining Input and Output neighbours in acyclic networks)
Expand First According to Second - Expand first partition
according to shrinking determined by second partition.
Permut. - Only permutation is needed as input.
Identity - Create identity permutation of selected dimension.
Default dimension is the size of selected network
(if there is one in memory).
Random - Create random permutation of selected dimension.
Default dimension is the size of selected network
(if there is one in memory).
Inverse - Create inverse permutation of selected permutation.
Cluster - Only cluster is needed as input.
Make Partition - Transform cluster to partition.
Hierarchy - Only hierarchy is needed as input.
Extract Cluster - Extract cluster from hierarchy -
the cluster is whole subtree of selected node in hierarchy.
Make Network - Converts hierarchy to network
(use it for example to draw hierarchy - drawing by layers).
Closed nodes are also taken into account.
Make Partition - Converts hierarchy to partition
(according to closed nodes).
Options
Read / Write
Threshold - Value of line must be higher (absolutely) than
given to generate line between two vertices.
Max. vertices to draw - Maximum number of vertices in
network to allow drawing (to prevent long waiting).
Descriptions? - Read also coordinates, labels and
other graphical descriptions of vertices and
lines or not. I recommend to select that option,
especially if you are planning to draw pictures
of networks too.
Auto Report? Automatically report all textual results to
file rep1.rep.
GEDCOM - Pgraph Use Pgraph format
(nodes are couples or individuals)
when reading genealogies (D. R. White),
otherwise nodes are only individuals.
Pgraph+labels Attach also labels of lines to pgraph, when
reading GEDCOM file.
Blockmodel - Select type of blockmodel for shrinking.
Possibilities are:
0..Min Number of Links
1..Null
2..Complete
3..Row-Dominant
4..Col-Dominant
5..Row-Regular
6..Col-Regular
7..Regular
8..Row-Functional
9..Col-Functional
10..Degree Density
Look at Doreian, Batagelj, Ferligoj: Blockmodeling.
FontSize - Size of Font for displays.
Draw
Draw -
Draw Network. A new window is opened, where a new menu appears.
You can edit network by hand (move vertices using left mouse button),
select a part of the picture (using right mouse button and select
the area), edit lines that belong to selected vertex by
clicking on vertex using right mouse button, spin picture
using keys X, Y, Z, S, x, y, z, s.
Description of Draw window menu:
Energy - Automatic layout generation.
Kamada-Kawai - algorithm for automatic layout generation
in the plane.
Free - Every position in the plane is possible.
Fix first and last - First and last vertex are
fixed in opposite corners.
Fix one vertex in the middle -
Select vertex which will be fixed in the middle of the picture.
Selected group only - Only selected part of the picture
is taking into account during optimisation.
Fix selected vertices -
Selected vertices (from partition) are fixed on given positions).
This item is visible only if Draw partition is active.
2D - Fruchterman Reingold algorithm for automatic layout generation
(faster than Kamanda-Kawai)
3D - Fruchterman Reingold algorithm for automatic layout generation
in space.
Starting positions - for energy drawing
(random, circular, given positions on plane xy,
given z coordinates).
EigenValues - Drawing using eigenvalues/eigenvectors
(Lanczos algorithm). Values of lines can be taken into account or not.
1 1 1 - Select 2 or 3 eigenvalues and algorithm will
compute corresponding eigenvectors. Eigenvalues may be multiple
so there are many possibilities. Some examples
1 1 1 - compute 3 eigenvectors that correspond to the first eigenvalue
1 1 2 - compute 2 eigenvectors that correspond to the first eigenvalue
and 1 that correspond to the second
1 2 2 - compute 1 eigenvector that correspond to the first eigenvalue
and 2 that correspond to the second
1 2 3 - compute 1 eigenvector that correspond to the first,
1 that correspond to the second and 1 that correspond to the
third eigenvalue
1 1 - compute 2 eigenvectors that correspond to the first eigenvalue
(2D picture)
Layers - Visible only if Draw partition is active.
Draw in layers according to partition.
Type of Layout Select type of picture
(2D - layers in y direction, or 3D - layers in z direction).
According to that, appropriate menu appears.
In y direction Draw vertices in layers (y coordinate)
inside layers draw vertices centered-equidistantly (x coordinate),
z coordinate is 0.5 for all vertices.
In y direction+random in x Same as first option,
only vertices are put on layers in random order
not according to vertex numbers.
In z direction Draw layers in z direction,
live x and y coordinates as they are.
In z direction + random in xy Draw layers in z direction,
x and y coordinates get random values
Averaging x coordinate - Use it after vertices are put
on layers in 2D. Iteratively compute average x-cooordinate of all
neighbours and normalize. Good approximation of global picture,
but vertices are put to close to each other. Use it on all vertices
or only on selected one.
Averaging x and y coordinates - Use it after vertices
are put on layers in 3D. Iteratively compute average x and y
cooordinates of all neighbours and normalize. Good approximation
of global picture, but vertices are put to close to each other.
Use it on all vertices or only on selected one.
Tile in x direction After averaging x coordinate
vertices are put to close to each other, so using this option
vertices are repositioned to minimal distance described in resoultion.
Tile in xy plane Same as previous, only this
option is used when drawing 3D pictures.
Optimize layers in x direction Optimize layout in layers
using minimization of the total length of lines.
Forward - go from first to last layer. In the current layer
optimize only layers having numbers equal or one smaller as
the current layer number.
Backward - go from last to first layer. In the current layer
optimize only layers having numbers equal or one larger as
the current layer number.
Complete - go from first to last layer. In the current layer
optimize only layers having numbers equal or one smaller
or one larger as the current layer number.
Optimize layers in xy plane - Same as previous, only this
option is used when drawing 3D pictures.
Resolution How many additional positions are available on
layers. Works only if Pgraph is selected. The higher the resolution,
the better is the result of optimization, but also slower.
GraphOnly - Show complete picture without labels of vertices and arrows.
Redraw - Redraw network.
Options - Additional options for picture layout.
Transform - Transformations of picture.
Fit area
max(x), max(y), max(z) - Draw picture as big as
possible to fit area (resize each coordinate to fit in
picture independently).
max(x,y,z) - Resize to fit in area but keap
real proportions (resize according to largest
distance in all three coordinates, e.g. moleculae).
Resize - Resize picture (or selected part of it) in all three directions
for selected factor.
Translate - Translate picture (or selected part of it) in space.
Reflect y axis - Reflect picture (or selected part of it) around y axis.
Rotate 2D - Rotate picture (or selected part of it) in xy plane.
Fisheye - Fisheye transformation (cartesian or polar)
of picture. If no vertex is selected the middle point of picture
(or selected part of it) is used as focus, otherwise first selected
vertex will be used as focus.
Values of lines - Meaning of values of lines during
energy drawing or eigenvectors computing (no meaning, similarities,
dissimilarities (distances)).
Mark vertices using - Labels can be marked using
labels
numbers
without labels
without labels and arrows
without labels and arrows but using real sizes
(x_fact and y_fact in input files).
selected group - when Draw/Partition is selected also part of
labels can be displayed.
Lines - Select the way the lines are drawn:
Draw Lines
Edges - draw edges or not
Arcs - draw arcs or not
Mark Lines - mark lines with labels or not
Size - Determine size of vertices, lines, arrows and font
or turn them to default values.
Colors - Determine color of background, vertices, lines and font
(of labels of vertices and lines)
or turn them to default values.
Layout - Layout options
Redraw during moving - Redraw whole network during
moving selected vertex (slower) or not (faster).
Real xy positions - The draw window has always
square shape or not.
ScrollBar On/Off - Show/Hide the scrollbars in the top
left corner of Draw window. When part of picture is selected,
scrollbar is used for moving. When whole picture is selected,
scrollbar is used for spinning (like pressing keys
X, Y, Z, x, y, z - spinning around axis defined by the key,
and S - spin around selected normal)
Interrupt - Interrupt period during optimisations
(stop every ? second, or not)
Select all - Select all vertices in window
(then possible to put vertices in given class).
Export - picture to one of the following formats
EPS/PS - Export to EPS format (with or without Clip, or WYSIWYG
[What You See Is What You Get - exported EPS picture is similar to
picture in Draw window - except that colors are Black/White
or color determined by partition]).
PS - Export to PS format (similar to EPS but without header).
MDL MOL file - Export to MDL Molfile format.
You need Chime plugin for Netscape to watch it.
(Chemscape Chime)
Kinemages - Export to Kinemages format.
You need Mage viewer to watch it.
A free copy of the Mage software can be downloaded from
Download Mage)
Spin
Spin around - Spin network around selected normal.
Perspective - Distant vertices are drawn smaller (or not).
Normal - Normal vector to spin around.
Step in degrees - Step in degrees when showing rotation.
Move - Give additional constraints on hand vertex moving:
Fix - Fix (do not allow) moving in x (or y) direction.
Grid - Define x*y positions on grid, these become
feasible positions for vertices during moving
by hand .
Circle - Define x*y positions on concentric circles,
these become feasible positions for vertices
during moving by hand.
Info - Select aestetic properties of the current layout
to compute:
Closest Vertices
Smallest Angle
Shortest/Longest Line
Number of crossings if lines
Vertex Closest to Line
All Properties
Remember that coordinates of vertices must be between 0 and 1!
Draw-Partition - Similar to Draw. Colors
of vertices mean the classes in selected partition.
Additionally you can put selected vertex or selected vertices into
given class in partition (classes are shown using different colors)
by clicking on middle mouse button (or Shift+left button)
(increment class), or together with Alt (or Alt+left button) -
decrement class number. Some additional menu items
that were already described appeared (you can draw network
according to layers from partition and optimise energy using fixed
vertices determined using partition).
It is also possible to move the selected class
(by clicking close to vertex from that partition).
Info
Network - General information about network
number of vertices
number of lines
sort lines according to their values (ascending or
descending) to find the most/least important lines.
Partition - General information about partition.
Sort vertices according to their class numbers (ascending or
descending) to see the most important vertices.
Frequency distribution of class numbers, and average of
class numbers are also given.
Hierarchy - General information about hierarchy.
Operation is possible only if node numbers are integers.
It returns number of vertices in nodes of hierarchy (on first level).