Still as a student Vladimir Batagelj (VB) collaborated on analysis of switching circuits and the theory and compiling of programming languages with Department of electronics at Institute Jožef Stefan in Ljubljana, Slovenia. This attracted his interest to graph and network theory \citep{r10,r9,r8}. With Tomaž Pisanski \citep{r24} they started to introduce graph theory in Slovenian mathematics. Graph theory became a part of the Discrete structures curriculum, taught by VB at Computer science, Faculty of electrotechnics.
In eighties they were joined by younger colleagues: Dragan Marušič, Bojan Mohar, Sandi Klavžar, Janez Žerovnik, and Aleksander Malnič. VB had a series of research projects on graph theory algorithms \citep{r6}. A library Graph for data structure graph was implemented in pascal by George Mejak \citep{rE}. In eighties they had each year also a Yugoslav seminar on graph theory \citep{r5,r7} and another seminar with University of Leoben, Austria (prof. Wilfrid Imrich). They were also regular participants of the MATH/CHEM/COMP conference at Inter-University center in Dubrovnik, Croatia organized by Ante Graovac. The group around Dragoš Cvetković \citep{r29,r30} in Belgrade was at that time developing a system Graph for analysis of graphs and doing graph theory on computer.
VB with Anuška Ferligoj developed a theory and algorithms for clustering with relational constraints \citep{r38,r39}. In 1990/91 they were visiting Patrick Doreian at the University of Pittsburgh. They started to develop an optimization approach to blockmodeling \citep{r13,r14,r34,r32} that was later generalized to types of links between clusters \citep{r3}, to two-mode networks \citep{r33} and by Patrick Doreian and Andrej Mrvar also to signed networks \citep{r35,r36,r43}. VB developed in pascal a package STRAN for blockmodeling. In Pittsburgh he also developed a very fast algorithm for computing Hummon-Doreian weights in acyclic networks \citep{r40,r2} and a semiring based algorithm for computing betweeness centralities \citep{rb}.
In 1991 VB and Tomaž Pisanski designed for a company Hermes Softlab a programming library Graph-X \citep{rF}. It was implemented in C by Marko Grobelnik and Darko Zupanič.
Andrej Mrvar (AM) was a Computer science student at University of Ljubljana. VB noticed him while he was presenting his home project on Saaty's AH procedure. He became AM's supervisor for master and Phd theses. For his master thesis AM implemented in pascal different graph visualization algorithms. Afterwards he started to work on analysis of large networks, that was an emergent topic at that time, for his Phd \citep{r44}.
To support the AM's work on his Phd AM and VB in November 1996 decided to collect all already developed graph analysis programs and to combine them into a single program –- Pajek. They also decided to make it free for noncommercial use. The first version of Pajek was presented on January 29, 1997 on Wednesday seminar at FMF, University of Ljubljana and on XVII Sunbelt Conference in San Diego, USA, February 13-16, 1997. Among the first users of Pajek were Wouter de Nooy and Doug White. Since Pajek had no user friendly documentation they decided with Wouter to write a book “Exploratory social network analysis with Pajek”. It was published in 2005 and the revised and expanded edition in 2012 by CUP \citep{r31}. The book was also published in Japanese in 2008 and in Chinese in 2012. In collaboration with Doug White and later with Klaus Hamberger different tools for analysis of genealogical data were added to Pajek \citep{r27,r50}. For example, Pajek can read genealogies from GED files.
% http://vlado.fmf.uni-lj.si/pub/gd/gd97.htm \begin{figure} \centerline{\includegraphics[width=\textwidth]{a97minb.png}} \caption{Snapshot of VRML scene made with Pajek for Graph Drawing Contest 1997}\label{gd} \end{figure}
In nineties VB and AM contributed several solutions to yearly Graph drawing contests. They won many prizes but also included in Pajek some new tools to address the contests' problems. In \citet{r23} they argued that for dense networks the matrix representation is more redable than the standard graphical representation. They also noticed that the Seidman's \citep{r48} notion of cores is the only known formalization of dense parts of the network that can be efficiently determined. The chemists from MATH/CHEM/COMP conference were interested in identification of select substructures in large organic molecula. For this purpose the fragments (later reinvented and called motifs by physicists) searching procedure was added to Pajek in 1998.
VB was a Phd supervisor also to Matjaž Zaveršnik who studied methods for network decomposition \citep{rG}. They developed algorithms for generalized cores \citep{r25}, islands \citep{r17} and short cycle connectivity \citep{r26}. They were also included in Pajek.
Multiplication of networks is very useful operation in network analysis, but it is dangerous when applied on large networks. The product of two large sparse networks needs not to be sparse itself –- it can “explode”. In many interesting cases (for example, genealogical and scientometric networks \citep{r15,r12}) the sparseness of the product can be garanted. A fast multiplication procedure was added to Pajek in 2005.
In summer 2005, while VB was visiting NICTA in Sydney, Australia, he was trying to analyze the two-mode IMDB network that was one of the task for that year Graph drawing contest. The two-mode hubs and authorities didn't give interesting results. There were no other tools in Pajek. So, VB asked AM to include in Pajek the counting of 4-rings and two-mode cores. The submitted solution \citep{r1} that was prepared in cooperation with NICTA's group won the first prize.
Around 2005 the 64-bit PC computers start to appear. Since they can have memories over 4G they are very important for further development of Pajek. The problem was that Pajek had to wait for 64-bit Delphi pascal compiler, and for several years the answer was “manana”. Finally, in 2010 the compiler became available.
* VOS + community * fast PathFinder
*** normalization in derived networks
In 2013 Pajek got the Richard's award: http://www.insna.org/awards_richard.html
Details on Pajek's evolution can be found in the history file at Pajek's site http://mrvar.fdv.uni-lj.si/pajek/history.htm .