[[pajek:histback]]

Table of Contents

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 .

- [Ahmed et~al.(2007)]{r1} Ahmed, A., Batagelj, V., Fu, X., Hong, S.-H., Merrick, D., Mrvar, A.: Visualisation and analysis of the Internet movie database. Asia-Pacific Symposium on Visualisation 2007 (IEEE Cat. No. 07EX1615), 2007, p 17-24
- [Batagelj(2009)]{rA} Batagelj, V.: Social Network Analysis, Large-Scale. R.A. Meyers, ed., Encyclopedia of Complexity and Systems Science, Springer 2009: 8245-8265.
- [Batagelj(2003)]{r2} Batagelj, V.: Efficient Algorithms for Citation Network Analysis. http://arxiv.org/abs/cs.DL/0309023
- [Batagelj(1997)]{r3} Batagelj, V.: Notes on blockmodeling. Social Networks 19(1997), 143-155
- [Batagelj(1993)]{r4} Batagelj, V.: Centrality in social networks. Metodološki zvezki, 9. Ljubljana: Faculty of Social Sciences, 1993, p. 129-138.
- [Batagelj(1987)]{r5} Batagelj, V.: Data structure graph. V: Eight Yugoslav seminar on graph Theory : Novi Sad, April 17-18, 1987. Novi Sad: Institute of Mathematics, 1987, p. 4.
- [Batagelj(1981-4)]{r6} Batagelj, V., etal. Teorija grafov. Algoritmi teorije grafov. Research reports 90, 103, 117, 133. Ljubljana: Inštitut za matematiko, fiziko in mehaniko, (part 1, 1981, part2, 1982, part 3, 1983, part 4, 1984) .
- [Batagelj(1983)]{r7} Batagelj, V.: General scheme for graph traversing algorithms. In: Cvetković D., etal. (eds.), Graph theory: proceedings of the fourth Yugoslav seminar on graph theory, Novi Sad, april 15.-16. 1983. Novi Sad: Univ. of Novi Sad, Institute of mathematics, 1984, p. 27-37.
- [Batagelj(1971a)]{r8} Batagelj, V.: Odločljive operacije in minimalne poti. V: Zbornik radova ADP seminara. Zagreb, 1971, str. B1-1/1-9.
- [Batagelj(1971b)]{r9} Batagelj, V.: Vrednostna funkcija grafov II. V: Zbornik radova ADP seminara. Zagreb, 1971, str. B2-4/1-4.
- [Batagelj(1970)]{r10} Batagelj, V.: Vrednostna funkcija grafov. V: Zbornik radova ADP seminara. Zagreb, 1970, str. B16/1-4.
- [Batagelj and Brandes(2005)]{r11} Batagelj, V., Brandes, U.: Efficient generation of large random networks. PHYS REV E 71 (3): - Part 2 MAR 2005
- [Batagelj and Cerinšek(2013)]{r12} Batagelj, V., Cerinšek, M.: On bibliographic networks. Scientometrics (2013).
- [Batagelj et~al.(1992a)]{r13} Batagelj, V., Doreian, P., Ferligoj, A.: An optimizational approach to regular equivalence. SOC NETWORKS 14 (1-2): 121-135 MAR-JUN 1992
- [Batagelj et~al.(1992b)]{r14} Batagelj, V., Ferligoj, A., Doreian, P.: Direct and indirect methods for structural equivalence. SOC NETWORKS 14 (1-2) 63-90, 1992
- [Batagelj and Mrvar(2008)]{r15} Batagelj, V., Mrvar, A.: Analysis of Kinship Relations With Pajek. Social Science Computer Review 26(2), 224-246, 2008.
- [Batagelj and Mrvar(2003)]{r16} Batagelj, V., Mrvar, A.: Density based approaches to network analysis : analysis of Reuters terror news network. V: Workshop on Link Analysis for Detecting Complex Behavior (LinkKDD2003), August 27, 2003. 2003. http://www-2.cs.cmu.edu/~dunja/LinkKDD2003/papers/Batagelj.pdf.
- [Zaveršnik and Batagelj(2004)]{r17} Zaveršnik Batagelj Islands
- [Batagelj and Mrvar(2003)]{r18} Batagelj, V., Mrvar, A.: Pajek – Analysis and Visualization of Large Networks. In Juenger, M., Mutzel, P. (Eds.): Graph Drawing Software. Springer (series Mathematics and Visualization), Springer, Berlin 2003. 77-103. ISBN 3-540-00881-0.
- [Batagelj and Mrvar(2001)]{r19} Batagelj, V., Mrvar, A.: A subquadratic triad census algorithm for large sparse networks with small maximum degree. SOC NETWORKS 23 (3): 237-243 JUL 2001
- [Batagelj and Mrvar(2000)]{r20} Batagelj, V., Mrvar, A.: Some analyses of Erdos collaboration graph. Social Networks 22(2000), 173-186
- [Batagelj and Mrvar(1998)]{r21} Batagelj, V., Mrvar, A.: Pajek: A Program for Large Network Analysis. Connections 21(1998)2, 47-57
- [Batagelj et~al.(2002)]{r22} Batagelj, V., Mrvar, A., Zaveršnik M. (2002) Network analysis of texts. Language Technologies, Ljubljana, p. 143-148. http://nl.ijs.si/isjt02/zbornik/sdjt02-24bbatagelj.pdf
- [Batagelj et~al.(1999)]{r23} Batagelj, V., Mrvar, A., Zaveršnik, M.: Partitioning Approach to Visualization of Large Graphs. Graph Drawing, Lecture Notes in Computer Science, 1999, Volume 1731/1999, 90-97.
- [Batagelj and Pisanski(1979)]{r24} Batagelj, V., Pisanski, T.: On partially directed Eulerian multigraphs. Publ. Inst. Math. (Belgr.), 1979, 25(39), 16-24
- [Batagelj and Zaveršnik(2011)]{r25} Batagelj, V., Zaveršnik, M.: Fast algorithms for determining (generalized) core groups in social networks. Advances in Data Analysis and Classification, 2011. Volume 5, Number 2, 129-145.
- [Batagelj and Zaveršnik(2007)]{r26} Batagelj, V., Zaveršnik, M.: Short cycle connectivity. DISCRETE MATH 307 (3-5): 310-318 FEB 6 2007
- [Burt(1992)]{r27} Burt R.S. (1992): Structural Holes. The Social Structure of Competition. Cambridge MA: Harvard University Press.
- [Cormen et~al.(1990)]{r28} Cormen, T. , Leiserson, C., Rivest, R.: Introduction to Algorithms. McGraw-Hill, 1990.
- [Cvetković and Pevac(1988)]{r29} Cvetković, D., Pevac, I.: Man-Machine Theorem Proving in Graph Theory. Artificial Intelligence, 35(1): 1-23 (1988).
- [Cvetković et~al.(1989)]{r30} Cvetković, D., et al. : Deset godina razvoja i upotrebe ekspertnog sistema GRAPH, In Bratko, I., et al. (eds.) Simpozijum Östvarenja i primene vestacke inteligencije”, Dubrovnik, 25.-27. October 1989, Tehnički fakultet “M. Pupin”, Institut za politehniku, Zrenjanin, 1990, 25-46
- [De Nooy et~al.(2011)]{r31} De Nooy, W., Mrvar, A., Batagelj, V.: Exploratory Social Network Analysis with Pajek; Revised and Expanded Second Edition. Structural Analysis in the Social Sciences, Cambridge University Press, September 2011. Translation in japanesse 2008, Denkyo Press, Tokyo. Translation in chinesse 2012.
- [Doreian et~al.(2004)]{r32} Doreian, P., Batagelj, V., Ferligoj, A.: Generalized Blockmodeling. Structural Analysis in the Social Sciences. Cambridge University Press, November 2004.
- [Doreian et~al.(2004)]{r33} Doreian, P, Batagelj, V, Ferligoj, A: Generalized blockmodeling of two-mode network data. SOC NETWORKS 26 (1): 29-53 JAN 2004
- [Doreian et~al.(2000)]{r34} Doreian, P., Batagelj, V., Ferligoj, A.: Symmetric-acyclic decompositions of networks. J CLASSIF 17 (1): 3-28 2000
- [Doreian and Mrvar(2009)]{r35} Doreian, P., Mrvar, A. Partitioning signed social networks. Soc. networks. Jan. 2009, vol. 31, no. 1, 1-11.
- [Doreian and Mrvar(1996)]{r36} Doreian, P., Mrvar, A. (1996) A Partitioning Approach to Structural Balance. Social Networks, 18. 149-168.
- [Dremelj et~al.(2002)]{r37} Dremelj, P., Mrvar, A., Batagelj, V. Analiza rodoslova dubrovačkog vlasteoskog kruga pomoću programa Pajek. An. Zavoda povij. znan. Hrvat. akad. znan. umjet. Dubr., 2002, sv. 40, str. 105-126.
- [Dunbar(2012)]{r51} Dunbar
- [Ferligoj and Batagelj(1983)]{r38} Ferligoj, A., Batagelj, V.: Some types of clustering with relational constraints. Psychometrika, 1983, let. 48, št. 4, str. 541-552.
- [Ferligoj and Batagelj(1982)]{r39} Ferligoj, A., Batagelj, V.: Clustering with relational constraint. Psychometrika 47 (4): 413-426 1982
- [Hummon and Doreian(1989)]{r40} Hummon, N.P., Doreian, P. (1989) Connectivity in a citation network: The development of DNA theory. Social Networks, 11, 39–63.
- [Kleinberg(1998)]{r41} Kleinberg J. (1998) Authoritative sources in a hyperlinked environment. In Proc 9th ACMSIAM Symposium on Discrete Algorithms, p. 668-677. http://www.cs.cornell.edu/home/kleinber/auth.ps
- [McCabe(2003)]{r42} McCabe, T. Computer Science Approaches: Visualization Tools and Software Metrics. in Survey Automation. NAP, 2003, p. 116-136. http://books.nap.edu/books/0309089301/html/116.html
- [Mrvar and Doreian(2009)]{r43} Mrvar, A., Doreian, P. Partitioning signed two-mode networks. J. math. sociol., 2009, vol. 33, no. 3, str. 196-221.
- [Mrvar(1999)]{r44} Mrvar, A. Analiza in prikaz velikih omrežij : doktorska disertacija. Ljubljana, 1999.
- [Murtagh(1985)]{r45} Murtagh, F. (1985) Multidimensional Clustering Algorithms, Compstat lectures, 4, Vienna: Physica-Verlag.
- [Pennock(2002)]{r46} Pennock, D.M. etal. (2002) Winners dont’t take all, PNAS, 99/8, 5207-5211.
- [Peterson(2012)]{r47} Peterson, J. L.: Petri Net Theory and the Modeling of Systems.
- [Seidman(1983)]{r48} Seidman, S. B. (1983) Network structure and minimum degree, Social Networks, 5, 269–287.
- [Tarjan(1983)]{r49} Tarjan, R. E. (1983) Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics Philadelphia, Pennsylvania.
- [White et~al.(1999)]{r50} White, D.R., Batagelj, V., Mrvar, A.: Analyzing Large Kinship and Marriage Networks with Pgraph and Pajek. Social Science Computer Review, Vol. 17 No. 3, Fall 1999 245-274
- [Batagelj(2011)]{rB} Batagelj, V: Large-Scale Network Analysis. J Scott, P Carrington (eds): The SAGE Handbook of Social Network Analysis, SAGE, 2011.
- [Batagelj(2009)]{rC} Batagelj, V.: Complex Networks, Visualization of. R.A. Meyers, ed., Encyclopedia of Complexity and Systems Science, Springer 2009: 1253-1268.
- [Wasserman and Faust(1994)]{rD} Wasserman S., Faust K. (1994). Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge.
- [Batagelj(1989)]{rE} Batagelj / Mejak
- [Batagelj and Pisanski(1991)]{rF} Graph-X
- [Zaveršnik(2004)]{rG} Zaveršnik doktorat
- MRVAR, Andrej. Analiza in prikaz velikih omrežij : doktorska disertacija. Ljubljana: [A. Mrvar], 1999. 183 f., graf. prikazi, tabele. [COBISS.SI-ID 19300701]
- MRVAR, Andrej. Izbrani algoritmi analize družboslovnih omrežij : magistrska naloga. Ljubljana: [A. Mrvar], 1995. 91 str. [COBISS.SI-ID 16566365]

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported