Link analysis with pajek
Pajek is a program (for Windows) for large network analysis and visualization. It is freely available for noncommercial use at http:vlado.fmf.uni-lj.si/pub/networks/pajek/ Besides ordinary networks Pajek supports also multi-relational and temporal networks. In large network analysis we are often interested in important parts of given network. There are several ways how to determine them. The islands approach is based on an importance measure of vertices or lines. Let (V,L,p) be a network with vertex property p : V ? R and let t be a real number. If we delete all vertices (and corresponding links) with the property value less than t, we get subnetwork called vertex-cut at level t. The number and sizes of its components depend on t. Often we consider only components of size at least k and not exceeding K. The components of size smaller than k are discarded as noninteresting, while the components of size larger than K are cut again at some higher level. Vertex-island is a connected subnetwork which vertices have greater property value than the vertices in its neighborhood. It is easy to see that the components of vertex-cuts are all vertex-islands. We developed an efficient algorithm that identifies all maximal vertex-islands of sizes in the interval k..K in a given network. For networks with weighted lines we can similarly define line-islands. The line-islands algorithm is based on line-cuts. Both algorithms are very general - they can be applied for any vertex/line importance measure. Their complexity is for sparse networks subquadratic - they can be applied to very large networks. We will illustrate them applying different importance measures on selected (large) networks. We will also present the use of pattern searching in analysis of genealogies and some approaches to analysis of (multi-relational) temporal networks.
Author:Nnataša Kejžar, FDV, Univerza v Ljubljani