Link analysis with pajek

author: Nataša Kejžar, Faculty of Social Sciences, University of Ljubljana
published: Feb. 25, 2007,   recorded: July 2005,   views: 21119

See Also:

Download slides icon Download slides: linkana.pdf (1.7 MB)

Download article icon Download article: kejzar_natasa_00.doc (33.0 KB)

Help icon Streaming Video Help

Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.

 Watch videos:   (click on thumbnail to launch)

Watch Part 1
Part 1 57:10
Watch Part 2
Part 2 31:40


Pajek is a program (for Windows) for large network analysis and visualization. It is freely available for noncommercial use at 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.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

Comment1 Viewer, July 15, 2007 at 11:47 a.m.:

Nice interesting talk and topic, but next time please get somebody else to shoot the video. It was hard to follow the gist of the talk when not seeing the slides :)

Write your own review or comment:

make sure you have javascript enabled or clear this field: