Pajek—Program for Analysis and Visualization of Large Networks


'Vladimir Batagelj Vladimir Batagelj / 'Andrej Mrvar Andrej Mrvar

Pajek is a program for Windows for analysing and visualizing large networks with some thousands or even millions of vertices. In the Slovene language the word “pajek” means “spider.” The latest version of Pajek is freely available for non-commercial use at its home page http://vlado.fmf.uni-lj.si/pub/networks/pajek/

We started the development of Pajek in November 1996. Pajek is implemented in Delphi (Pascal). Some procedures were contributed by Matjaz Zaversnik. The main motivation for the development of Pajek was the observation that several sources of large networks exist that are already in machine-readable form. Pajek is intended to provide tools for analysing and visualizing such networks: collaboration networks, organic molecules in chemistry, protein-receptor interaction networks, genealogies, Internet networks, citation networks, diffusion (AIDS, news, innovations) networks, data-mining (2-mode networks), etc. See also the collection of large networks at: http://vlado.fmf.uni-lj.si/pub/networks/data/ The design of Pajek is based on our previous experiences gained in the development of graph data structure and the algorithm libraries Graph and X-graph, the collection of network analysis and the visualization programs STRAN, RelCalc, Draw, Energ, and the SGML-based graph description markup language NetML. The main goals in the design of Pajek are:

• to support abstraction by (recursive) decomposition of a large network into several smaller networks that can be treated further using more sophisticated methods;


• to provide the user with some powerful visualization tools;


• to implement a selection of efficient (subquadratic) algorithms for the analysis of large
  networks.

Data structures

• network (graph),


• partition (nominal or ordinal properties of vertices),


• vector (numerical properties of vertices),


• cluster (subset of vertices),


• permutation (reordering of vertices, ordinal properties),
  and


• hierarchy (general tree structure on vertices).

Algorithms

• simplifications and transformations: deleting loops, multiple edges, transforming arcs to edges etc.;


• components: strong, weak, biconnected, symmetric;


• decompositions: symmetric-acyclic, hierarchical clustering;


• paths: shortest path(s), all paths between two vertices;


• flows: maximum flow between two selected vertices;


• neighborhood: k-neighbours;


• CPM—critical paths;


• social networks algorithms: centrality measures (see Figure 1), hubs and authorities, measures of prestige, brokerage roles, structural holes, diffusion partitions;


• measures of dependencies among partitions/vectors: Cramer's V, Spearman rank correlation coefficient, Pearson correlation coefficient, Rajski co-efficient;


• extracting subnetwork;


• shrinking clusters in network (generalized blockmodeling);


• reordering: topological ordering, Richards’ numbering, Murtagh’s seriation and clumping algorithms, depth/breadth first search.

Special algorithms

• islands: If we represent a given or computed value of vertices/lines as a height of vertices/lines and we immerse the network in water up to a selected level, we get islands. Varying the level, we get different islands. Islands are a very general and efficient approach to determine the “important” sub-networks in a given network.


• citation weights: Citation network analysis started in 1964 with the paper by Garfield et al. In 1989 Hummon and Doreian proposed three indices.


• weights of arcs that provide us with an automatic way to identify the (most) important part of the citation network. We developed algorithms to compute two of these indices efficiently.


• cores and generalized cores: The notion of core was introduced by Seidman in 1983. Vertices belonging to a k-core have to be linked to at least k other vertices of the core. A very efficient algorithm exists for determining cores. The notion of core can be extended to other vertex functions and for several of them the corresponding cores can be efficiently determined.


• pattern searching: If a selected pattern determined by a given graph does not occur frequently in a sparse network, the straightforward backtracking algorithm applied for pattern searching quickly finds all appearances of the pattern even in the case of very large networks. Pattern searching was successfully applied to searching for patterns of atoms in molecula (carbon rings) and searching for re-linking marriages in genealogies.


• triads: A triad is a subgraph on three given vertices. There are 16 types of triads. Several network properties can be expressed in terms of their triadic spectrum—the distribution of all their triads.


• triangular networks: We can assign to a given graph a triangular network in which every line of the original graph receives as its weight the number of triangles that contain it. Triangular weights, combined with islands, provide us with a very efficient way of identifying dense parts of a graph.


• generating large random networks: Pajek contains very efficient algorithms for generating random networks of the Erdös-Renyi type (undirected, directed, acyclic, undirected bipartite, directed bipartite, acyclic bipartite, 2-mode, and others). It also provides some procedures for generating random scale free networks.


• normalizations: The normalization approach was developed for quick inspection of (1- mode) networks obtained from 2-mode networks—a kind of network-based data-mining. In networks obtained from large 2-mode networks there are often huge differences in weight. Thus it is not possible to compare the vertices according to the raw data. Beforehand, we have to normalize the network to make the weights comparable. There are several ways of doing this.

Algorithms for small networks

Layout Algorithms and Layout Features

Interfaces