RRŠITVF. - OKODJA
Analiza velikih omrežij s
programom pajek
Vladimir Batagelj FMF Oddelek za matematiko, Univerza v Ljubljani
Andrej Mrvar Fakulteta m družbene vede. Univerza v Ljubljani
Povzetek
Pri svojem delu se večkrat srečamo z velikimi omrežji, kjer gre število točk in povezav v tisoče, npr.: rodovniki, diagrami poteka programskih sistemov, organske molekule, računalniška omrežja, transportna omrežja, vodovodna in električna omrežja, referenčna omrežja, družboslovna omrežja, itd. Obvladovanje velikih omrežij pomeni tako časovno, kot tudi prostorsko zahteven problem, Večina standardnih algoritmov za analizo omrežij ima visoke časovne zahtevnosti in so zato neprimerni za analizo velikih omrežij. V sestavku so predstavljeni pristopi k analizi in predstavitvam tovrstnih omrežij. Pristopi so podprti s programom Pajek. Prikazanih je tudi nekaj tipičnih primerov uporabe.
Abstract
Large networks, having thousands of vertices and lines, can be found in many different areas, e. g: genealogies, flow graphs of programs, molecules, computer networks, transportation networks, social networks, intra/inter organise tional networks... Many standard network algorithms are very time and space consuming and therefore unsuitable for analysis of such networks. In the article we present some approaches to analysis and visualisation of large networks implemented in the program Pajek. Some typical examples are also given.
1. Uvod
I'ajek je programski paket, za okolje Windows (32 bit), ki omogoča analizo in prikaz velikih omrežij (omrežij z več tisoč točkami). Program je prosto dostopen na naslovu:
http://vlado.fraf.uni-lj.si/pub/networts/pajelc/
Velika omrežja lahko najdemo na Številnih področjih.
Največkrat pridemo do njih avtomatično, z uporabo
računalnikov, iz različnih podatkovnih virov, ki so že
v elektronski obliki. Primeri:
■	veliki rodovniki (rodovniki z nekaj 10.000 [25] osebami), omrežje mentorstev pri izdelavi doktorskih disertacij s področja teoretičnega računalništva (1.882 oseb [36]);
■	omrežja, dobljena iz slovarjev in drugih besedil (povezave med 52.652 angleškimi besedami glede na zameno/vrivanje/brisanje posameznih Črk [24();
■	transportna omrežja (povezave med 332 ameriškimi letališči [37]);
m velike molekule (molekule z nekaj tisoč atomi, npr. DNA J 31 [);
m komunikacijska omrežja: povezave med stranmi ali strežniki na Internetu, uporaba debatnih skupin (Usenet) [34], telefonski klici [22];
■	diagrami poteka programskih sistemov [16];
■	bibliografije, referenčna omrežja [9,7], omrežje Ordosevih soavtorjev (5.822 soavtorjev [20]),...
Velikih omrežij ne moremo učinkovito analizirati z uporabo standardnih programov za analizo omrežij, ki povečini temeljijo na matrični predstavitvi omrežja in so zato omejeni na omrežja z nekaj desel ali slo točkami.
Glavni cilji pri zasnovi programa Pajek so bili:
■	podpreti abstrakcijo s postopno razčlenitvijo velikega omrežja na več manjših omrežij, ki jih lahko nadalje analiziramo z uporabo običajnih metod;
■	ponuditi uporabniku močna orodja za prikaz omrežij;
m Vgraditi večje število učinkovitih algoritmov za analizo velikih omrežij.
1998 Številka 3 - letnik VI
i ippniin jd NFORM ATIKA
REŠITVK - ORODJA
skrčitev
izrez	vpelje
Slika i: Cilji pri zasnovi programa Pajek.
Kot je prikazano na sliki 1, lahko abstrakcijo podpremo na naslednje načine: poiščemo skupine (komponente, soseščine 'osrednjih* točk, jedra, ...) v omrežju; izrežemo in ločeno prikažemo točke, ki pripadajo posameznim skupinam (podroben lokalni pogled); skrčimo skupine v točke in prikažemo povezave med njimi (globalni pogled).
2. Učinkoviti algoritmi za analizo velikih omrežij
časovna T(n) in prostorska S(n) zahtevnost algoritma nam povesta, koliko časa in prostora potrebujemo za njegovo izvedbo na nalogah velikosti ir (v našem primeru — število točk ali povezav v omrežju). V večini velikih omrežij je število povezav m istega velikostnega reda kot število točk — O(n) ali največ 0(ii n). Taka omrežja imenujemo redka omrežja. V nadaljevanju bomo zato predpostavili, da analiziramo velika a redka omrežja.
Glede na vse večje pomnilniške zmogljivosti današnjih računalnikov prostorska zahtevnost za redka omrežja ni več kritična. Problem rešimo z ustreznimi podatkovnimi strukturami za notranjo predstavitev omrežja, v programu Pajek je bila uporabljena predstavitev omrežja z dvojno povezanimi seznami.
Časovna zahtevnost pa ostaja še vedno velik problem, saj tudi veliko hitrejši računalniki ne pomagajo veliko. V teoriji algoritmov veljajo problemi z algoritmi s polinomsko časovno zahtevnostjo za pohlevne — lahko rešljive. Toda, v primeru zelo velikih n, so lahko dejansko prezahtevni že algoritmi s časovno zahtevnostjo 0{//-), kar je razvidno iz tabele L Zato ima večina algoritmov, ki so vključeni v program Pajek, podkvadratične časovne zahtevnosti: 0(»), Q(n log /;), \fu), ali pa je njihova uporaba omejena samo na manjše množice izbranih točk.
3. Podatkovne strukture
Izvedbe algoritmov v programu Pajek so trenutno oprte na šest podatkovnih struktur:
■	omrežje — glavna struktura (točke in povezave);
■	permu ta d ja — preureditev točk;
■	vektor — vrednosti (lastnosti) točk;
■	skupina - podmnožica točk (npr. en razred iz razbitja);
m razbitje — pove za vsako točko, v katero skupino spada;
■	hierarhija — hierarhična razvrstitev skupin in točk omrežja.
Prava moč celotnega sistema Fajek se skriva v Številnih prehodih med temi strukturami.
Poleg svojih vhodnih formatov podpira Pajek še več drugih formatov: UCINCT DL [32¡; Vega [33]; GED [21], rodoslovne podatke lahko predelamo v dve vrsti rodovnikov: navadne in parne rodovnike [25, 17, 18, 12]; in nekaj kemijskih formatov: BS (Bali and Stick), MAC (Mac Molecule) in MOL (MDL MOLfile).
Prav tako lahko omrežja shranjujemo v internih in različnih drugih izhodnih formatih (UC1NET DL, Vega, [iS in MOL). Eno od možnih uporab programa Pajek je torej tudi pretvorba med različnimi formati za opis omrežja.
4. Algoritmi
V tekoči različici so v program Pajek vključeni naslednji učinkoviti algoritmi [1, 24, 14, 15]; m razbitja: po stopnjah, po globinah, jedra, p-klike, centri;
Tabela 1: Časovne zahtevnosti algoritmov (PentiuiïV64M/90MHz),
	Tin)	1.000	10.000	100,000	1,000.000
Shuffle	0(n)	0,00 s	0,015 s	0,17 s	2,22 s
Quick Sort	0(n logn)	0,00 s	0,00 s	0,40 s	5,14 s
Neap Sort	0(n log n)	0,00 s	0,06 s	0,98 s	14,35 s
Insertion Sort	0 (n2)	0,07 s	7,50 s	12,5 min	20,83 h
XY	0(n3)	0,10 s	1,67 min	1,16 dni	3,17 let
26
i if rimi« ini NFOfîMÂTIKA
199B * Številka 3 ■ letnik VI
Rešitve: - orodja
■	duojiŠke operacije: unija, presek, razlika,
■	komponente: krepke, šibke, dvopovezane, simetrične [11;
■	dekompozicije: simetrično-aciklična;
■	poti: najkrajše poti, vse poti med izbranima točkama [II];
■	pretoki: največji pretok med izbranima točkama [15];
■	glavne poti: metoda Paths Count in metoda SPLC [21;
■	soseščine: k-sosedi;
* CP/VI (metoda kritične poti);
■	izrez pod-omreŽja;
■	s krči t ve skupin v omrežju (posplošeni bločni modeli) [4];
■	preurejanja: topološko urejanje, Richardsovo oštevilčenje, oštevilčenje glede na iskanje v globino oz. širino;
■	kleSčcnjc: dreves, vmesnih točk, po stopnjah;
■	poenostavitve in transformacije: brisanje zank in večkratnih povezav, raz usmerjanje ...;
Pogosto uporabljena zaporedja osnovnih operacij
lahko definiramo kot makro, ki ga poženemo kot en
sam ukaz. Z uporabo makrojev lahko sistem prilagodimo posebnim skupinam uporabnikov (analiza rodovnikov, kemijske uporabe, ...).
V program Pajek so vključeni tudi nekateri algoritmi namenjeni reševanju posebnih problemov: npr. algoritmi za preverjanje ali je program napisan po pravilih strukturiranega programiranja [16]; simulacija Pet-rijevih mrež [13]; iskanje zanimivih vzorcev v molekulah ali rodovnikih.
Poseben poudarek je dan avtomatičnemu določanju prikazov omrežij [35]. V sistem so vključeni številni tovrstni algoritmi: energijska risanja (Kamada-Kawai ] 10] in Fruchterman-Reingold [fi]), risanja z uporabo lastnih vektorjev (Lanczosev algoritem [3,5]), nivojska risanja (rodovnikov in drugih acikličnih struktur).
Ti algoritmi so bili izpopolnjeni in prilagojeni, tako da omogočajo dodatne učinke, npr.: risanja z omejitvami (optimizacija le izbranega dela omrežja, določitev izbranih točk za nepremične, uporaba podobnosti in različnosti oziroma vrednosti na povezavah), prostorski prikazi. Pajek nudi tudi orodja za ročno risanje omrežij.
Slika 2: Rodovnik dveh ameriških predsednikov. 1998 - Številka 3 ■ letnik VI	iifjombito)NFORM ATIKA 27
Rešitve: - orodja
Dobljene prikaze lahko pretvorimo v številni? izhodne formate, ki si jih lahko nadalje ogledujemo s posebnimi pregledovalniki za ravninske in prostorske prikaze: (Encapsulated PostScript — GSView [28]; VRMI. — Cosmo Player [27); MDl.MOl, — Rasmol [31 J, Chime [261; Kinemages — Mage [291).
5. Primeri
Na sliki 2 je prikazana največja povezana komponenta (parni graf) v rodovniku ameriških predsednikov [19]. Najkrajša sorodstvena vez med Franklinom D. Koos-veltom in Oeorgeom H. W. Bushem, dobljena z uporabo makroja Path, je narisana na sliki 3.
Slika 4 prikazuje najkrajše poti med besedama graph in drawing ter drawing in contest.
Slika 5 prikazuje prvonagrajcni graf s tekmovanja v risanju grafov Graph Drawing Contest 1998 v Motrealu [33];
Na sliki 6 je prikazan posnetek pogleda na prostorski prikaz grafa v prikazovalniku CosmoPlayer [27|.
6. Nadaljnji razvoj
Program Pajek je Še v razvoju. Zadnja izdaja je vedno na voljo na njegovi predstavitveni strani. V bližnji prihodnosti nameravamo v sistem vključiti naslednje algoritme: različne metode združevanj in dekompozicij, nekatere statistike (štetja triad), animacije in predstavitve zaporedja omrežij, uvedba krmilnih stavkov v sistemu makrojev, ravninska risanja ...
Literatura
[1]	AHO AHO, A. V., HOPCROFT, J. E., ULLMAN, J. D. (1976): T/ie Design and Analysis of Computer Algorithms. Add i son -Wesley, Reading, MA.
[2]	BATAGEU, V. (1994):
An Efficient Algorithm for Citation Networks Analysis, Presented at EASST'94, Budapest, Hungary, August 28-31, 1994.
[3]	DATTA, B. N. (1995):
Numerical Linear Algebra and Applications. BrooksD&Cole Publishing Company, Pacific Grove.
George Herberl Walker Bush & Barbara Pierce Prescott Sheldon Bush & Dorothy Walker Samuel Prescott Bush & Flora Sheldon '".James Smith Bush & Harriet Eleanor Fay
Tsamuel Howard Fay & Susan Shellman

Samuel Prescott PhillipsFay & Harriet Howard James Roosevelt & Sara Delano
Samuel Howard & Anna Lillie
John üllie & Abigail Breck
iVheophilus Lillie & Hannah Ruck r
i
■John Ruck & Hannah Hutchinson i
*Ellsha Hutchinson & Hannah Hawkins
; Warren Delano & Catherine Robbins Lyman
■Joseph Lyman & Anne Jean Robbins V
^Edward Hutchinson Robbins & Elizabeth Murray "Nathaniel Robbins & Elizabeth Hutchinson
Edward Hutchinson & Lydia Foster
Elisha Hutchinson & Elizabeth Clarke
Slika 3: Najkrajša pot med Franklinom D. Roosveltom in Georgeom H. W. Bushem. 2 g upnrubimlNFORMATIKA	199B - Številka 3 - letnik VI
Rešitve: - orodja
[4| DOREIAN, P, RATAGEU, V., FERUGOJ, A. (1994):
Partitioning Networks Based on Generalized Concepts of Equivalence.
Journal of Mathematical Sociology. sObf 19, 1.1-27.
15] GOLUB, G. H„ van LOAN. C. F. (1996):
Matrix Computations. The John Hopkins University Press, Baltimore.
[6]	FRUCHTERMAN, T. M. J., REINGOLD, M, (1991): Graph Drawing by Force-Directed Placement. Software, Practice and Experience. sBbf 21,1129-1164.
[7]	HUMMON. N. R, DOREIAN, R (1989):
Connectivity in a Citation Network: The Development of UNA Theory.
Social Networks. Dtextbfsll. 39-63.
{8] HUMMON, N. P, DOREIAN. R (1990):
Computational Methods for Social Network Analysis. Social Networks, E)textbfsl2. 273-288.
[9] HUMMON, N. P, DOREIAN, P. FREEMAN, L. C. (1990): Analyzing the Structure of the CentraIity-Productivity literature Created Between 1948 and 1979. Knowledge: Creation, Diffusion, Utilization, Vol. Dtexthfill, June, No. 4, 459-480.
[10]	KAM ADA, T„ KAWAI, S. (1989):
An Algorithm for Drawing General Undirected Graphs. Information Processing Letters, SDhf 31, 7-15.
[11]	KNUTH, D. E. (1993): The Stanford GraphBase,
Stanford University, ACM Press, New York.
[12]	MRVAR, A., BATAGEU, V. (1997):
Pajek — program za analizo obsežnih omrežij. Uporaba v rodoslovju. Drevesa. Bilten slovenskega rodoslovnega društva. Letnik 4, Številke 12, december 1997, 4-6.
[13]	PETERSON. J. L. (1981):
Petri Net Theory and Modeling of Systems. Prentice-Hall, Inc., Englewood Cliffs, N.J.
[14]	ROGERS, E. M„ KIN C AID, D. L (1981): Communication Networks, Toward a New Paradigm for Research.
The Free Press. New York.
[15]	TARJAN, R. E, (1983):
Data Structures and Network Algorithms, Society for Industrial and Applied Mathematics Philadelphia, Pennsylvania.
Slika 4: Najkrajše puli med besedami. 1998 - Številka 3 - letnik VI	i ^wmfn r/H NFOR M ATIKA
Rešitve: - orodja
2Q rifAmihmlNFORMATIKA
Slika 5: Prvo na grajeni graf s tekmovanja v risanju grafov GD'98,
1998 -številka 3 - letnik V!
Rešitve: - orodja
* 9 *
Slika 6: Posnetek prostorskega grafa.
[16]	WATSON, A. H., MCCABE, T. J. (1996): Structured Testing; A Testing Methodology Using the Cyclomatic Complexity Metric. Computer Systems Laboratory, National Institute of Standards and Technology Special Publication 500-235, Gaithersburg. MO 20899-0001.
[17]	WHITE, D, R„ JORION, R (1992):
Representing and Computing Kinship; A New Approach. Current Athropology sObf 33, 454-462.
[18]	WHITE. D.R., JORION, P (1996):
Kinship Networks and Discrete Structure Theory: Applications and Impiications. Social Networks 18, 267-314.
[19]	American Presidents GEDCOM file: ftp://www.dcs.hull. ac.tik/public/genealogy/
[20]	Erdös Number project:
http://www. oaktand.edu/igrossmaiVerdoshp. html
[21]	GEDCOM Standard:
http ://www. gend ex. corn/ged co m55/55gci n l.ht m
[22]	Graph Drawing Competition 1996, Graph B:
h ttp ://p orta I. re sea rc h. be li - labs, co rtVo rgs/ss r/p eo p I e/n ort h/
contest.html
[23]	Graph Drawing Competition 1998: http://gd98.cs.mcgill.ca/contest/
[24} KNUTH, D. E.:
Dictionary. Stanford University, Computer Science Department:
f t p ://!a b rea. s tan f o rd, ed u/pu b/d ict/
[25] parnl rodovniki:
http://eclcctic.ss.uci.edu/ctfnvhite/pgraph/p-graphs.htmi
[26]	Plug-in Chime;
http://www. mdlt.com/downloa d/chimedown.html
[27]	Plug-in Cosmo Player: http ://c osm osoft ware. com/
[28]	Program GSView: ftp://ftp.cs.wiso.edu/pu b/gh ost/rj t/
[29]	Program Mage:
http ://www. prosci.org'Kinemage/Mage Softwa re. htm I
[30]	Program M0DEL2:
http://vlado.fmf.uni ij.si/pub/networks/stran/default.htm
[31]	Program RasMol (RASter MOLecules): http://klaatu.olt.umass.edu/microbio/rasmol/getras.htm
[32]	Program Ucinet: http://eclectic.5s.uci. edu/cl i rVordc r. h tm I
[33]	Program Vega: http://vega.ijp.si/HtmldoiWega03.htmi
[34]	SMITH, M. A. (1996): NetScan, Department of Sociology, UCLA:
http 'V/www. sscnet.ucla.edu/soc/csocinetscarVnetsc an.htm
[35]	Tekmovanja v risanju grafov: http://vlado.imf.uni-lj.si/pub/gd/gd95.htm
[36]	Theoretical Computer Science Genealog: http://sigact.ocm.org/genealogy/
[37]	Transportation Networks, National Transportation Atlas Database, Bureau of Transportation Statistics:
http ://www. bts. gov/ gis/nta t las^netwo rks. h tm I
Vladimir Batagelj je izredni profesor za diskretno in računalniško matematiko na Univerzi v Ljubljani, Fakulteta za matematiko in fiziko. Raziskovalno se ukvarja z diskretno matematiko (teorija grafov), optimizacijskimi metodami in analizo po datkov; predava pa predmete: diskretne strukture, kombinatorika, optimizacijske metode, operacijske raziskave, učenje z računalnikom ter razvoj matematike in računalništva. Je član več strokovnih združenj (DMFA RS, Informatika, INSNA, CSNA. ISI. IEEE, £ uro Logo) in programskega sveta Ro.
♦
Andrej Mrvar je diplomiral na Fakultetizo elektrotehniko in računalništvo, program računalništvo, leta 1992. Na isti fakulteti je leta 1995 zaključil magistrski študij. Na Fakulteti za računalništvo in informatiko trenutno pripravlja doktorsko disertacijo z naslovom Analiza in prikaz velikih omrežij. Zaposlen je kot asistent za računalništvo in statistiko na Fakulteti za družbene vede.
1993 - Številka 3 - letnik VI
niwtïZfi tiri NFO RM AT IKA ß j