Pajek
Program for Large Network Analysis

Started: November 15 1996
Last update:

1. Networks - main objects (vertices and connections). Default extension: .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.
2. Partitions - they tell for each vertex to which class vertex belong. Default extension: .clu.
3. Permutations - reordering of vertices. Default extension: .per.
4. Clusters - subset of vertices (e.g. one class from partition). Default extension: .cls.
5. Hierarchies - hierarchically ordered vertices. Example:

             Root
          g1      g2
        g11 g12   5,6,7
       1,2  3,4
       

   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 extension: .hie.
6. Vectors - they tell for each vertex some numerical property (real number). Default extension: .vec.

Short description of menu

• File Input/Output manipulation.
  • Network - N
    • Read network from Ascii file.
    • Edit graph. Choose vertex, show its neighbours and then:
      • 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 right mouse clicking);
      • subdivide line to two orthogonal lines using new invisible vertex (by single middle mouse clicking).
    • Save selected network to Ascii file.
    • Export Matrix to EPS - write matrix in EPS form:
      • Original - using default numbering
      • Using Permutation - using current permutation. Additionally lines can be drawn to divide different classes defined by selected partition.
      • Using Partition - using current partition. In the text window number and density of lines among classes (and vertices in selected two classes) are displayed. Additionally matrix is exported to EPS where density is expressed using shadowing:
        • Structural - Densities are normalized according to maximum possible number of lines among classes (suitable for dense networks).
        • Delta - Densities are normalized according to vertices having the highest number of input and output neighbors in classes (suitable for sparse networks).
      • Only Black Borders - If checked all squares in matrix will have black borders, otherwise dark squares will have white and light squares will have black borders.
    • Dispose selected network from memory.
  • Time Events Network - N
    • Read Time Events - Read time network described using time events. Following events can be used to describe development of network over time:

      Command	Explanation
      TI t	initial events - following events happen when time point t starts
      TE t	end events - following events happen when time point t is finished
      AV v n s	add vertex v with label n and properties s
      HV v	hide vertex v
      SV v	show vertex v
      DV v	delete vertex v
      AA u v s	add arc (u,v) with properties s
      HA u v	hide arc (u,v)
      SA u v	show arc (u,v)
      DA u v	delete arc (u,v)
      AE u v s	add edge (u:v) with properties s
      HE u v	hide edge (u:v)
      SE u v	show edge (u:v)
      DE u v	delete edge (u:v)
      CV v s	change vertex property - change property of vertex v to s
      CA u v s	change arc property - change property of arc (u,v) to s
      CE u v s	change edge property - change property of edge (u:v) to s
      CT u v	change type - change (un)directedness of line (u,v)
      CD u v	change direction of arc (u,v)
      PE u v s	replace pair of arcs (u,v) and (v,u) by single edge (u:v) with properties s
      AP u v s	add pair of arcs (u,v) and (v,u) with properties s
      DP u v	delete pair of arcs (u,v) and (v,u)
      EP u v s	replace edge (u:v) by pair of arcs (u,v) and (v,u) with properties s

      List of properties s can be empty as well.
      If several edges (arcs) can connect two vertices, additional tag like :k (k-th line) must be given to determine to which line the command belongs. E.g. command HE:3 14 37 results in hiding the third edge connecting vertices 14 and 37.
      Example of time network described using time events:

      *Vertices 3 *Events TI 1 AV 2 "b" TE 3 HV 2 TI 4 AV 3 "e" TI 5 AV 1 "a" TI 6 AE 1 3 1 TI 7 SV 2 AE 1 2 1 TE 7 DE 1 2 DV 2 TE 8 DE 1 3 TE 10 HV 1 TI 12 SV 1 TE 14 DV 1 See also other possibility: description of time network using time intervals
    • Save - Save time network in time events format.
  • Partition - C
    • Read partition from Ascii file.
    • Edit partition (put vertices to classes).
    • Save selected partition to Ascii file.
    • Dispose selected partition from memory.
  • Permutation - P
    • Read permutation from Ascii file.
    • Edit permutation (interchange positions of two vertices).
    • Save selected permutation to Ascii file.
    • Dispose selected permutation from memory.
  • Cluster - S (list of selected vertices)
    • Read cluster from Ascii file.
    • Edit cluster (add and delete vertices).
    • Save selected cluster to Ascii file.
    • Dispose selected cluster from memory.
  • Hierarchy - H
    • Read hierarchy from Ascii file.
    • Edit hierarchy (change types and names of nodes).
    • Save selected hierarchy to Ascii file.
    • Dispose selected hierarchy from memory.
  • Vector - V
    • Read vector from Ascii file.
    • Edit vector (change components of vector).
    • Save selected vector(s) to Ascii file. If cluster representing vector id's is present, all vectors with corresponding id numbers will be saved to the same output file. Vector's id can be added to cluster by pressing V on the selected vector (empty cluster should be created first). All vectors must have the same dimensions.
    • Dispose selected vector from memory.
  • Pajek Compound File - *.paj
    • Read Pajek compound file (file containing all possible Pajek objects - networks, partitions, permutations, clusters, hierarchies and vectors).
    • Save currently loaded objects as a Pajek compound file.
  • 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). If startup logfile (Pajek.log) exixts (in the same directory as Pajek.exe), it is automatically executed every time when Pajek is run.
  • Show Report Window - Bring the report window in the front in the case that it was closed or is not visible.
  • 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.
        • Sum Values - Values of all deleted lines are added to not deleted line between corresponding two vertices.
        • Do not Sum - Values of all deleted lines are not added to not deleted line between corresponding two vertices.
        • Min Value - Minimum value of all lines between two vertices is selected.
        • Max Value - Maximum value of all lines between two vertices is selected.
      • loops - Remove all loops from selected network.
      • lines with value
        • lower than - Remove all lines with value lower than specified value.
        • higher than - Remove all lines with value higher than specified value.
    • Add
      • Sibling edges - Add sibling edges to vertices with a common
        • Input - arc-ancestor
        • Output - arc-descendant
    • 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:
        • Sum Values - Value of the new edge is a sum of both values of arcs.
        • Min Value - Value of the new edge is smaller value of values of arcs.
        • Max Value - Value of the new edge is larger value of values of arcs.
    • 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).
    • Generate in Time - Generate network in specified time(s). Input first time, last time and step (integers).
      Additional parameters when vertices and lines are active should be given in network to perform this operation. They must be given between signs [ and ]:
      - is used to divide lower and upper limit of interval,
      , is used to separate intervals,
      * means infinity. Example: *Vertices 3 1 "a" [5-10,12-14] 2 "b" [1-3,7] 3 "e" [4-*] *Edges 1 2 1 [7] 1 3 1 [6-8] Vertex 'a' is active from times 5 to 10, and 12 to 14, vertex 'b' in times 1 to 3 and in time 7, vertex 'e' from time 4 on. Line from 1 to 2 is active only in time 7, line from 1 to 3 in times 6 to 8.
      Additional constraint: when generating netork in time, line will not be generated even it is active in that time, if appropriate vertices which are connected by the line are not active too. Note that time records should always be written as last in the row where vertices / lines are defined.
      See also other possibility of describing time network: description of time network using time events
      • All - Generate all networks in specified times.
      • Only Different - Generate network in specified time only if the new network will differ in at at least one vertex or line from the last network which was generated.
    • 2-Mode to 1-Mode - Generate ordinary (1-mode) network from input 2-mode (affiliation) network. Result is a valued network. To store 2-mode network in input file use Pajek or Ucinet format (look at Davis.dat from Ucinet dataset).
      • Rows - Result is network with relations among row elements (actors). The value of line tells number of common events of the two actors.
      • Columns - Result is network with relations among column elements (events). The value of line tells number of actors that took part in both events.
      The obtained network is usually not sparse. To make it sparser use Net/Transform/Remove/lines with value/lower than...
      It is also possible to generate unvalued 1-mode network, where multiple lines among vertices can exist. The label of the generated line corresponds to the label of the event/actor that served to induce the line.
    • Sort Lines - For each vertex sort lines connected to it in increasing order according to vertex on the other side of line.
• Random Network - Generate random network of selected dimension
  • Total No. of Arcs - Generate random directed network of selected dimension and given number of arcs.
  • Vertices Output Degree - Generate random directed network of selected dimension and output degree of each vertex in given range.
  • Extended Model - Generate random network according to extended model defined by: R. Albert and A.-L. Barabasi: Topology of evolving networks: local events and universality.
• 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.
  • Valued Core - Generalized k-core: Instead of counting lines (neighbours) use values of lines. Sum of lines or maximum value can be used when computing valued core (change using Options/ReadWrite):
    Sum valued core of threshold val is a subnetwork of given network where the sum of values of lines to (from) the members of the same core is at least val.
    Max valued core of threshold val is a subnetwork of given network where the maximum value of all lines to (from) the members of the same core is at least val.
    Threshold values must be given in advance. Two different ways to determine thresholds:
    • First Threshold and Step - Select first threshold value and step in which to increase threshold.
    • Selected Thresholds - Thresholds (increasing numbers) are given using vector.
    Additionally, Input, Output or All valued cores can be used.
  • 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.
  • 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 several classes, so the result cannot be stored in partition - biconnected components are stored in hierarchy! Minimal number of vertices in components can be selected. Additionaly, partition containing articulation points is produced: number of biconnected components to which each vertex belongs is given. Partition containing vertices belonging to exactly one bicomponent, vertices outside bicomponents and articulation points is also produced: vertices outside bicomponents get class zero, each bicomponent is numbered consecutively (from 1 to number of bicomponents) and articulation points get class number 9999998.
• 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.
    • Weak ... forget directions (or undirected network).
  • Breadth First - Breadth first numbering of selected network...
    • Strong ... taking directions of arcs into account.
    • Weak ... forget directions (or undirected network).
  • Core + Degree - Numbering in decreasing order according to all core partition. Within the same core number vertices are ordered in decreasing order according to number of neighbours which have the same or higher core number.
• 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. Vector with importances of vertices (articles) is also generated. 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 - 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 999998 (65534 in older versions). After you have a partition you can extract subnetwork.
  • From Clusters - Compute selected distances according to each vertex in Cluster. Results consist of so many partitions as is the number of vertices in cluster. Instead of storing results in partitions they can be stored in vectors as well.
• 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.
  • Walks with Limited Length - Find all walks between two vertices with limited maximum length.
  • 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. Additional networks containing total and free delay times of activities are generated. Two vectors (partitions) are generated, too: First containing the earliest possible times of coming into given states and the second containing the latest feasible times of coming into given states.
• Maximum Flow among vertices.
  • Selected Pair - Find maximum flow between selected 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). Result is a new network, containing the two vertices and lines contributing to maximum flow between them.
  • Pairs in Cluster - Find maximum flow among vertices determined by cluster. Result is a new network, where a value on line means maximum flow between corresponding two vertices. Algorithm is slow: Use it on smaller networks or clusters with limited number of vertices only!
• Vector - Get vector from network
  • Centrality - Result is a vector containing selected centrality measure of each vertex and centralisation index of the whole network.
    • Closeness centrality (Sabidussi).
      • Input - centrality of each vertex according to distances of other vertices to selected vertex. This measure can be applied to strongly connected networks only.
      • Output - centrality of each vertex according to distances of selected vertex to all other vertices. This measure can be applied to strongly connected networks only.
      • All - forget direction of lines - consider network as undirected. This measure can be applied to weakly connected networks only.
    • Betweenness centrality (Freeman).
  • 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 it according to their strengths, or they steal the same amount
  • Get coordinate - x, y, or z coordinate of network. You can also get all coordinates at once - possibility to have more than 3 coordinates, coordinates must contain character . (dot).
  • Important Vertices - Find important vertices in directed network (e.g. web pages, scientific citations) or 2-mode network. Result are vectors with weights and partition with selected number of important vertices.
    • 1-Mode: Hubs/Authorities - In directed networks we can usually identify two types of important vertices: hubs and authorities. A vertex is a good hub, if it points to many good authorities, and it is a good authority, if it is pointed to by many good hubs.
    • 2-Mode: Important Vertices - Generalization of algorithm for 2-mode networks - find important vertices from first and second subset.