9Druæboslovne razprave, XVII (2001), 36: 9-22 Andrej Mrvar UDK 316.472.4 Analiza velikih socialnih omreæij POVZETEK: V vsakdanjem æivljenju se vedno bolj pogosto sreËujemo z velikimi omreæji, kjer gre πtevilo toËk/povezav v (deset ali sto) tisoËe: socialna omreæja (omreæja prijatelj- stev, sodelovanja, komuniciranja med posamezniki, organizacijami, dræavami ...,), rodovniki, raËunalniπka omreæja (lokalna raËunalniπka omreæja, omreæja povezav med predstavitvenimi stranmi, Internet, ...,), referenËna omreæja (omreæja citiranj), diagrami poteka programskih sistemov, organske molekule, transportna omreæja (cestna, vodovodna, elektriËna omreæja ...,), itd. Obvladovanje velikih omreæij predstavlja 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 posebnim programom za analizo velikih omreæij. V sestavku je prikazanih nekaj primerov uporabe tega programa pri analizi in prikazu rodovnikov. KLJU»NE BESEDE: velika omreæja, socialna omreæja, Ëasovna zahtevnost, rodovniki, poroËna prepletenost, Pajek. 1. Uvod V vsakdanjem æivljenju se okoli nas nahajajo velika omreæja, pa Ëe jih opazimo ali ne. Pripadajo predvsem naπemu mikro okolju in makro okolju, Ëe za mero velikosti okolja vzamemo obiËajni Ëutni svet ljudi. Velika omreæja nimajo vselej vidne in Ëvrste oblike, kot jo imajo na primer predmeti, ljudje ali klasiËne organizacije (stavbe). Kljub temu pa lahko iz ozadja predstavljajo pomemben faktor vsakdanjega dogajanja. S svojo lastno strukturo in dinamiko in s sebi lastnim vplivom namreË stanovitno uËinkujejo na naπe æivljenje. Odkar se je obseg naπega zavedanja in tudi znanja o njih poveËal, kar je predvsem posledica razvoja znanosti in nenehne rasti velikih infrastrukturnih omreæij okoli nas, in odkar so na razpolago πe uËinkovita orodja za njihovo analizo, postajajo velika omreæja vse bolj zanimiva za sistematiËno prouËevanje. Med velika omreæja πtejemo omreæja, pri katerih gre πtevilo enot (toËk/povezav) v (deset ali sto) tisoËe. Ta dokaj ohlapna znaËilnost velikih omreæij je v bistvu raziskovalna prednost, ker nas vsebinsko ne omejuje in nam dopuπËa, da lahko med velika omreæja uvrstimo zelo razliËne pojave. Kot primer velikih omreæij naj navedemo nekatera bolj znana: - socialna omreæja: omreæja prijateljstev, mentorstev [14], soavtorstev (Batagelj in Mrvar, 2000), sodelovanja, komuniciranja med posamezniki [3], organizacijami, dræavami,...; 10 Druæboslovne razprave, XVII (2001), 36: 9-22 Andrej Mrvar - rodovniki - sorodstvena drevesa ljudi (White et al., 1999; Dremelj et al.,1999), plemenskih æivali; - raËunalniπka omreæja (lokalna raËunalniπka omreæja, debatne skupine, omreæja pove- zav med predstavitvenimi stranmi, Internet,...); - diagrami poteka programskih sistemov; - referenËna omreæja, omreæja citiranj (Hummon in Doreian, 1989; Hummon et al., 1990); - organske molekule [10]; - transportna omreæja (cestna, vodovodna, elektriËna omreæja, letalska omreæja [15]), itn. Eno od zanimivih podroËij analize socialnih omreæij, kjer je na voljo veËje πtevilo empiriËno zajetih obseænih omreæij, so rodovniki (genealogije), s katerimi se ukvarja (predvsem zbira podatke) vse veË ljudi. Tako tudi v Sloveniji obstaja Slovensko rodoslovno druπtvo [12]. V veËjih slovenskih rodovnikih najdemo podatke o veË 10.000 osebah. Na omreæju Internet pa lahko najdemo πe precej veËje rodovnike, ki so povezani v poizvedovalni sistem GENDEX [2]. Analitska vpraπanja, povezana s temi zbirkami podatkov, so tudi druæboslovno izredno vznemirljiva, saj rodovniki vsebujejo velika sorodstvena omreæja, ki se raztezajo skozi daljπi Ëas in lahko - ni pa to nujno - moËno vplivajo na socialno vedenje ljudi. Do nedavna je bilo na πtevilna analitska vpraπanja iz rodovnikov πe teæko odgovoriti, zlasti zato, ker so bili (roËni) naËini iskanja odgovorov precej okorni, povezani z velikimi stroπki in dolgotrajnimi prouËevanji. Danes je poloæaj æe precej drugaËen. V tem prispevku bomo na primeru rodovnikov pokazali, da je danes, z metodiËnim pristopom k velikim omreæjem in z uporabo ustreznih programov, moæno æe precej laæje odgovoriti na πtevilna vpraπanja, ki so πe vËeraj izgledala analitsko prezahtevna. 2. Zanimiva vpraπanja okrog rodovnikov Rodoslovni podatki se zbirajo za razliËne namene: - rodovniki, zanimivi iz zgodovinskih in drugih vzrokov (npr. poroke med florentin- skimi rodbinami (Padgett in Ansell, 1989), rodovnik dubrovniπkih plemiπkih druæin (Dremelj et al., 1999), rodovnik ameriπkih predsednikov [1]); - rodovniki posameznih druæin in/ali teritorialnih obmoËij za osebno ali religiozno uporabo, npr. rodovniki Mormonov [11]; - posebni rodovniki; - πtudenti in njihovi mentorji pri izdelavi doktorskih disertacij: Theoretical Computer Science Genealogy [14]; - boæanstva (antika). V velikih rodovnikih si lahko postavimo veliko zanimivih vpraπanj, na katera lahko odgovorimo samo na osnovi sorodstvenih povezav, ki jih predstavimo z ustreznim omreæjem. Na primer: - Ali sta poljubni dve osebi v krvnem sorodstvu ali vsaj svaπtvu (povezanost preko 11Druæboslovne razprave, XVII (2001), 36: 9-22 Analiza velikih socialnih omreæij æeninih oz. moæevih sorodnikov). Vpraπanje lahko razπirimo na iskanje najkrajπe sorodstvene zveze med dvema osebama. - Iskanje πtevila vseh prednikov oziroma vseh potomcev dane osebe, oziroma πirπe - doloËanje vseh prednikov ali vseh potomcev izbrane osebe. - DoloËanje oseb v doloËeni okolici izbrane osebe (nekaj generacij pred in nekaj za izbrano osebo). - Ugotavljanje prepletenosti med druæinami (veËkratnih porok med istimi druæinami / rodbinami, ki so imele tudi ekonomski namen - ohranjanje bogastva znotraj druæin). - Iskanje zanimivih vzorcev v rodovniku - porok med sorodniki, otrok z veË starπi, velikokrat poroËenih oseb. Na osnovi teh statistik lahko primerjamo razliËne rodovnike - oziroma πirπe - kulture med sabo. - Iskanje najdaljπih nepretrganih verig v rodovniku in πe posebej najdaljπih nepretrganih moπkih verig v rodovniku, ki so imele v preteklosti poseben pomen (dedovanje, ohranjanje rodovnega imena,...). - Statistike: povpreËno πtevilo otrok, najveËje πtevilo otrok,... 3. Metodologija Pogoj za sistematiËno analizo velikih omreæij, kamor spadajo tudi rodovniki, je konceptualnokategorialni aparat na dovolj sploπni ravni.»e torej zanemarimo vsebinsko razliËnost velikih omreæij, nam ravno abstraktne skupne lastnosti velikih omreæij omogoËijo, da se jih lahko metodiËno lotimo na soroden naËin. Za uspeπno analitsko reπevanje problemov velikih omreæij bomo omreæja najprej opredelili. Nato bomo nakazali, s katerimi algoritmi je velika omreæja mogoËe uËinkovito (dovolj hitro) analizirati, naπteli podatkovne strukture, ki nam to omogoËajo in predstavili program za analizo in prikaz velikih omreæij. Omenjene pristope bomo prikazali na primeru analize izbranega rodovnika. 3.1 Definicija omreæja Naj bo dana konËna mnoæica enot E = (X1, X2, ..., Xn). Odnosi med enotami naj bodo opisani z eno ali veË dvomestnimi relacijami Rt ⊆ E x E, t = 1, ..., r, ki doloËajo omreæje N = (E, R1, R2, ..., Rr). Zapis Xi R Xj preberemo: enota Xi je v relaciji R z enoto Xj . Relacija R lahko predstavlja prijateljstvo, sovraπtvo, sorodstvene odnose (Xi je otrok od Xj ali Xi je sestra od Xj ali Xi je poroËen z Xj), citiranje (avtor Xi citira avtorja Xj ali v Ëlanku Xi se sklicujemo na Ëlanek Xj)... V nadaljevanju se bomo v veËini primerov omejili na eno samo relacijo R in sicer v primeru rodovnikov na relacijo Xi je otrok od Xj . Omreæje, v katerem nastopa relacija R, lahko predstavimo na veË naËinov: - Predstavitev s pripadajoËo dvojiπko matriko R = [rij]nxn, kjer je  1 Xi R Xjrij =  0 sicer  12 Druæboslovne razprave, XVII (2001), 36: 9-22 Andrej Mrvar VËasih je lahko rij tudi realno πtevilo, ki izraæa moË relacije R med enotama Xi in Xj. - opis z grafom G=(V, L), kjer je V mnoæica toËk (Vertices) in L mnoæica (usmerjenih ali neusmerjenih) povezav (Lines). ToËke grafa predstavljajo enote v omreæju, povezave pa relacijo. Graf predstavimo s sliko, kjer toËke grafa predstavimo s kroæci, usmerjene povezave s puπËicami, neusmerjene povezave pa z daljicami, ki povezujejo ustrezne toËke. Zapis Xi R Xj v primeru predstavitve z grafom pomeni, da v grafu obstaja usmerjena povezava (R), ki vodi od toËke Xi do toËke Xj. ToËka Xi se imenuje zaËetna, toËka Xj pa konËna toËka povezave. 3.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 n (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Ë O(n log 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 za- htevnost za redka omreæja ni veË kritiËna. Problem reπimo z ustreznimi podatkovnimi strukturami za notranjo predstavitev omreæja. »asovna zahtevnost pa ostaja πe vedno velik problem, saj tudi veliko hitrejπi raËunal- niki 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 O(n2), kar je razvidno iz tabele 1. Tabela 1: »asovne zahtevnosti algoritmov (Pentium/64M/90MHz) Iz tabele je razvidno, da so za analizo velikih omreæij primerni le algoritmi, ki imajo podkvadratiËne Ëasovne zahtevnosti. Naj dodamo, da je vsebinska zahtevnost analize velikih omreæij na tej ravni sploπnosti neodvisna od predlagane metodologije raziskovalca in je zato kakovost vsebinske interpretacije povsem odvisna od disciplinarne ekspertnosti raziskovalca. 3.3 Podatkovne strukture Sistem za analizo velikih omreæij smo oprli na naslednje podatkovne strukture: - omreæje - osnovna struktura (npr. toËke predstavljajo osebe, povezave pa neko sorodstveno razmerje). Potrebujemo torej program, ki razpozna, oziroma predela podatke, zapisane na nek standarden naËin na vhodni datoteki, v ustrezno omreæje. T(n) 1.000 10.000 100.000 1.000.000 O(n) 0,00 s 0,015 s 0,17 s 2,22 s O(n log n) 0,00 s 0,00 s 0,40 s 5,14 s O(n2) 0,07 s 7,50 s 12,5 min 20,83 h O(n3) 0,10 s 1,67 min 1,16 dni 3,17 let 13Druæboslovne razprave, XVII (2001), 36: 9-22 Analiza velikih socialnih omreæij - permutacija - preureditev toËk, ki jo predstavimo s tabelo (npr. preureditev oseb v rodovniku po naraπËajoËi letnici rojstva); - razbitje - omreæju prirejena tabela, ki predstavlja posebno razvrstitev toËk po skupinah (razredih), npr. razvrstitev oseb po spolu v primeru rodovnikov; - vektor - lastnost toËk omreæja (realno πtevilo, ki predstavlja neko kvantitativno lastnost toËke, npr. letnico rojstva osebe); - skupina - seznam izbranih toËk (npr. osebe, ki pripadajo dani druæini); - hierarhija - hierarhiËna razvrstitev skupin (in poslediËno toËk) omreæja, ki je predstavljena s sploπno drevesno strukturo. Merilo hierarhiËne razvrstitve je podobnost / razliËnost toËk oziroma skupin. 3.4 Sistem za analizo velikih omreæij 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 deset ali sto toËkami. Za analizo velikih omreæij so potrebni posebni programi. Predstavili bomo program Pajek, ki je bil napisan ob upoπtevanju navedenih opredelitev, algoritmov in podatkovnih struktur. Glavni cilji pri zasnovi programa so: - 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; - vgraditi veËje πtevilo uËinkovitih algoritmov za analizo velikih omreæij. Slika 1: Cilji pri zasnovi programa Pajek Na sliki 1 je abstrakcija prikazana z razliËnimi pogledi na omreæje. Na omreæje lahko pogledamo kot na celoto (globalen pogled) ali pa se osredotoËimo na del omreæja (lokalen pogled). lokalno izrez vpetje skrËitev hierarhijagl ob al no 14 Druæboslovne razprave, XVII (2001), 36: 9-22 Andrej Mrvar Obstajata dva razliËna globalna pogleda: skrËitev in hierarhija. Pri skrËitvi obravna- vamo toËke v skupini kot neko novo toËko - toËke v skupinah stisnemo v skupno toËko. ©e sploπnejπi globalni pogled pa je hierarhija - toËke v omreæju hierarhiËno zdruæujemo v skupine in na ta naËin dobimo drevo. Kasneje se sprehajamo po drevesu in glede na poloæaj v drevesu ‘vidimo’ omreæje podrobneje (Ëe se nahajamo v bliæini listov drevesa) ali bolj na grobo (Ëe smo v bliæini korena drevesa) - toËke, ki so pod izbranim vozliπËem v drevesu, namreË stisnemo v novo toËko. Obstajata tudi dva lokalna pogleda na omreæje. Prvega imenujemo izrez - iz omreæja izreæemo manjπi del in ga v nadaljevanju obravnavamo loËeno. Drugi lokalni pogled se imenuje vpetje - iz omreæja izreæemo manjπi del, hkrati pa prikaæemo, kako je ta del povezan z ostankom omreæja. Poseben poudarek je v programu dan avtomatiËnemu doloËanju prikazov omreæij [13]. V sistem so vkljuËeni πtevilni tovrstni algoritmi: energijska risanja (Kamada in Kawai, 1989; Fruchterman in Reingold, 1991), risanja z uporabo lastnih vektorjev (Datta, 1995; Golub in val Loan, 1996), nivojska risanja (rodovnikov in drugih acikliËnih struktur). Sistem nudi tudi orodja za roËno risanje omreæij. Dobljene prikaze lahko pretvorimo v πtevilne izhodne formate, ki si jih lahko nadalje ogledujemo s posebnimi pregledovalniki za ravninske in prostorske prikaze: (Encapsulated PostScript - GSView [8]; Scalable Vector Graphics - SVG [7]; VRML - CosmoPlayer [6]; MDLMOL - Rasmol [10]; Chime [5]; Kinemages - Mage [9]). V nadaljevanju si bomo pogledali uporabo tega programa pri analizi rodovnikov. 4. Primer: analiza rodovnikov Kot smo omenili v uvodu, je eno od podroËij, kjer je na voljo veËje πtevilo velikih omreæij, rodoslovje. V rodoslovju obstaja kar nekaj programov za vnos podatkov (GIM, Brother’s Keeper, Family Tree Maker ...,), ne obstajajo pa programi, ki bi omogoËali njihovo analizo. To vrzel skuπa zapolniti program Pajek. Rodoslovne podatke lahko predelamo v dve vrsti grafov - rodovnikov, ki ju bomo imenovali navadni in parni rodovnik. V navadni obliki (Ore, 1963) je vsaka oseba predstavljena s toËko grafa, poroka je oznaËena z neusmerjeno povezavo med toËkama, usmerjene povezave pa vodijo od starπev do otrok (naprej v prihodnost). Tak je primer na levi strani slike 2. Na tej sliki so predstavljene πtiri generacije. Zaradi sploπnosti je pri izbrani osebi (oËetu) predpostavljeno, da se je dvakrat poroËila, zato sta z ustrezno toËko (oËetom) povezani dve neusmerjeni povezavi (povezavi z materjo in maËeho). Na tej sliki so tudi vse osebe (razen sestre) poroËene. V parni obliki (p-graph, p je prva Ërka francoske besede parenté - sorodstvo) so toËke grafa lahko posamezniki ali pari. VeË o tej obliki predstavitve najdemo na predstavitveni strani D. R. Whita z Univerze Irvine v Kaliforniji [4]. »e neka oseba πe ni poroËena, je v grafu predstavljena s svojo toËko; Ëe pa je poroËena, je v grafu predstav- ljena skupaj s svojim zakoncem s skupno toËko. V tej obliki imamo samo usmerjene povezave, ki vodijo od otrok do starπev (nazaj v preteklost). Ker so toËke lahko tudi 15Druæboslovne razprave, XVII (2001), 36: 9-22 Analiza velikih socialnih omreæij pari, moramo posebej oznaËiti, ali se povezava nanaπa na moπkega ali na æensko. Pove- zave, ki se nanaπajo na izvornega moπkega (kaæejo pa na njegove starπe), so oznaËene z neprekinjeno puπËico, povezave, ki se nanaπajo na izvorno æensko (kaæejo pa na njene starπe), pa s prekinjeno (pikËasto) puπËico. »e je neka oseba veËkrat poroËena, se pojavi v toliko toËkah, kolikor je porok. Tak primer grafa je podan na desni strani slike 2. Ta slika prikazuje povsem identiËno situacijo kot tista na levi strani, le da je namesto navad- nega rodovnika uporabljen parni rodovnik. Slika 2: Predstavitev rodovnika v navadni obliki (levo) in v parni obliki (desno) 4.1 Podatki V velikih rodovnikih lahko odkrijemo zanimive stvari. V primerih, ki sledijo, bo uporabljen eden od (trenutno) najveËjih slovenskih rodovnikov - rodovnik Leona Drameta, v katerem se nahajajo podatki o okrog 30.000 osebah. Motivacija za zaËetek zbiranja teh podatkov je bila, da se Ëimdlje v preteklost popiπe prednike vseh æiveËih oseb na doloËenem teritoriju. Najstareπi zapis v tem rodovniku se nanaπa na leto 1540. 4.2 Rezultati analize V nadaljnjih podpoglavjih je prikazanih nekaj zanimivih podomreæij (lokalnih pogledov, oziroma izrezov), dobljenih iz navedenega rodovnika. 4.2.1 Iskanje najkrajπe sorodstvene zveze med dvema osebama Prvo vpraπanje, ki si ga lahko zastavimo nad rodovnikom, je, ali sta dve nakljuËno izbrani osebi v sorodu. »e sta v sorodu, bi seveda radi naπli najkrajπo sorodstveno zvezo med njima. zet & hËi JAZ & æena oËe & mati ded-o & babica-o ded-m & babica-m sin & snaha brat & svakinja sestra oËe & maËeha ded-o babica-o oËe mati JAZ æena sinsnaha hËi zet maËeha ded-m babica-m sestrabratsvakinja 16 Druæboslovne razprave, XVII (2001), 36: 9-22 Andrej Mrvar Slika 3: Najkrajπa pot (parni rodovnik) Slika 3 prikazuje najkrajπo pot med Leonom Drametom (zbirateljem podatkov v rodovniku) in Bojanom Mihaelom KuËanom (neËakom slovenskega predsednika), Ëe uporabimo parni rodovnik. Slika je narisana po generacijskih nivojih, starejπe generacije so narisane bolj levo, mlajπe pa bolj desno. Tako lahko razberemo, da je Bojan Mihael KuËan za eno generacijo mlajπi od Leona Drameta. PuπËica, ki vodi iz toËke, ki predstavlja Leona Drameta, kaæe na njegove starπe (Rihard Drame in Ljudmila Pakiæ). Iz slike razberemo tudi, da naj bi Leon Drame ne bil poroËen (v ustrezni toËki je predstavljen brez svojega partnerja) ter da se v starejπih generacijah pogosto lahko pojavljajo manjkajoËi podatki (npr. imena oseb, glej na sliki oznako ‘??? KuËan’). 4.2.2 ©tevilo neposrednih potomcev izbrane osebe Zanimivo je tudi vpraπanje o osebi (ali paru) z najveËjim πtevilom potomcev. Slika 4 prikazuje osebo z najveË zakonskimi partnerji in otroki (skupno glede na vse njegove poroke). V tem primeru je uporabljen navadni rodovnik (puπËice torej kaæejo od vsakega od starπev na njune otroke). Bojan Mihael KuËan Mihael KuËan & Marija Viner ??? KuËan Leon Drame Rihard Drame & Ljudmila Pakiæ Janez Pakiæ Ana Roæanc SreËko Intihar & Zlata KuËan Franc Intihar & Terezija MihelËiË Joæef Intihar Ana Klemenc Jurij Klemenc & Marija KorenËiË Martin KorenËiË Marija Vidrih Viktor Pakiæ & Dragica Modic Ivan Modic & Joæefa Beber Jakob Beber & Jera Brezec Andrej Beber & Marija Puntar Anton Krajc & Neæa Puntar Peter Krajc Marija BombaË Jernej Puntar Terezija Kobal Mihael BombaË Marija Pajk Andrej Puntar Marija PetriË Franc KorenËiË Ivana BombaË Janez Puntar Joæefa Beber 17Druæboslovne razprave, XVII (2001), 36: 9-22 Analiza velikih socialnih omreæij Slika 4: Posameznik z najveË zakonskimi partnerji in otroci skupno (navadni rodovnik) Iz slike razberemo, da se je Anton MatiËiË poroËil trikrat in imel skupaj 19 otrok (πest z Urπulo Kraπevec, osem z Marijo StraæiπËar in pet z Marijo ©kerlj). Na sliki so osebe moπkega spola oznaËene s kvadratki, osebe æenskega spola pa z krogci. V oËi nam hitro pade πe ena zanimivost: obstajajo celo otroci istih starπev z enakimi imeni (npr. Marija MatiËiË). »e pogledamo v zapiske, lahko najdemo razlog: zaradi visoke umrljivosti otrok, so starπi naslednjemu rojenemu otroku radi dali spet enako ime (πe posebej, Ëe je πlo za ohranjanje oËetovega imena). 4.2.3 Iskanje ‘zanimivih’ porok V tem podpoglavju bomo zaradi nedvoumnosti uporabljali pojem druæina za partnersko zvezo med moæem in æeno, pojem rodbina pa za podmnoæico tistih oseb v rodovniku, ki imajo skupnega prednika. V rodovniku si lahko postavimo πe naslednji dve vpraπanji: - Ali so se pripadniki izbranih rodbin veËkrat poroËali med sabo? Tu gre za prepletenosti, kjer poroËna partnerja nimata skupnega prednika (poroËna prepletenost). An to n M at iËi Ë Marija ©kerlj Blaæ MatiËiË Jakob MatiËiË Marija MatiËiË Anton MatiËiË Marija MatiËiË Marija StraæiπËar FranËiπka MatiËiË Ivana MatiËiË Joæefa MatiËiË Carolina MatiËiË Marija MatiËiË Helena MatiËiË Kristina MatiËiË Urπula MatiËiË Urπula Kraπevec Ana MatiËiË Jera MatiËiË Terezija MatiËiË Antonija MatiËiË Alojzius MatiËiË Pavlina MatiËiË 18 Druæboslovne razprave, XVII (2001), 36: 9-22 Andrej Mrvar - Ali so se pripadniki iste rodbine poroËali med sabo - krvne poroke: poroke, kjer imata partnerja skupnega prednika. Na obe vpraπanji lahko odgovorimo le, Ëe rodovnik obravnavamo v parni obliki - to je tudi glavna analitska prednost parnega rodovnika pred navadnim rodovnikom (poleg manjπega πtevila toËk in povezav). Za podani vzorec, ki predstavlja neko zanimivo situacijo, nam mora program vrniti vse pojavitve takega vzorca v rodovniku. Oba tipa porok se na sliki izbranega dela parnega rodovnika kaæeta kot sklenjeni verigi: Ëe zaËnemo pot v neki toËki in sledimo povezavam, pri Ëemer smeri povezav zanemarimo, se lahko vrnemo v zaËetno toËko (glej sliki 5 in 6). Poglejmo si oba primera malo bolj podrobno. Ugotavljanje poroËne prepletenosti rodbin Vpraπanje o poroËni prepletenosti rodbin lahko razbijemo na dve podvpraπanji in sicer: - Ali so se pripadniki izbranih dveh rodbin sploh kdaj poroËili? Za neporoËanja so lahko (ni pa nujno) kriva nesoglasja, ki se prenaπajo preko generacij (tak primer je obdelan v znanem Shakespearjevem delu Romeo in Julija). - »e smo na prvo vpraπanje odgovorili pozitivno (obstaja vsaj ena poroka med rodbinama), si lahko postavimo nadaljnje vpraπanje: ali obstajajo med temi porokami tudi soËasne poroke v okviru ene generacije. Do tega pride, Ëe se brata poroËita s sestrama iz druge rodbine, kjer gre torej za dvakratno poroko v okviru ene generacije med (istima) dvema rodbinama. Slika 5: Primer poroke med sorodniki Slika 5 prikazuje primer poroke takega tipa. V tem primeru sta se brat in sestra (Andrej in Marjeta MartinËiË) poroËila s sestro in bratom iz druge rodbine (Heleno in Antonom Kebetom). S porokami takega tipa, so rodbine ohranjale svoje premoæenje (bogastvo) oziroma ga celo poveËevale. Veliko takih navzkriænih porok lahko zato zasledimo pri poroËanju viπjih druæbenih slojev. Zanimiv je primer dubrovniπkega plemstva, kjer se je zaradi teritorialne zaprtosti, pomanjkanja partnerjev iz ustreznih Andrej MartinËiË Helena Kebe Andrej MartinËiË Marjeta Grebenc Anton Kebe Helena Roæanc Anton Kebe Marjeta MartinËiË 19Druæboslovne razprave, XVII (2001), 36: 9-22 Analiza velikih socialnih omreæij plemiπkih rodbin in teænje po ohranjanju bogastva pojavljalo zelo veliko porok tega tipa (Dremelj et al., 1999). Ugotavljanje krvnega sorodstva v porokah Pri iskanju krvnih porok si lahko postavimo naslednji vezani vpraπanji: - Ali sta dve druæini v krvnem sorodstvu (eden od partnerjev ima skupnega prednika z enim od partnerjev iz druge druæine)? - Ali obstaja med dvema druæinama, ki sta v krvnem sorodstvu, kakπna poroka? »e da in Ëe jih je veË, katere izmed teh krvnih porok so (naj)bolj koËljive? Pri tem bomo za bolj koËljive πteli tiste poroke, kjer se poroËijo bliænji krvni sorodniki - skupni prednik je torej generacijsko bliæe (npr. obravnavamo njegove sinove in hËere), za manj pa tiste, kjer se poroËijo bolj oddaljeni krvni sorodniki - skupni prednik se pojavi pred veliko generacijami (npr. obravnavamo njegove prapravnuke in prapravnukinje). Slika 6: Dva primera krvne poroke med sorodniki Slika 6 prikazuje dva primera krvne poroke - levo je primer krvne poroke med sorodniki, kjer sta se poroËila pravnuk (Rajko Zupanc) in pravnukinja (Marija Drame), desno pa primer, ko sta se poroËila sin (Viljem Pollak) in vnukinja (Pavla Smolej). Morda bi na tem mestu opozorili πe na prisotnost napak v rodovnikih. Pri vnosu podatkov o daljnjih prednikih se lahko zelo hitro pojavijo napake, ko zaradi manjkajoËih podatkov (predvsem o letnicah rojstva) rodoslovec vnese napaËne sorodstvene povezave med osebami. To lahko povzroËi, da se v rodovniku pojavijo omenjeni napaËni vzorci - poroke med bliænjimi sorodniki. V tem primeru pa lahko spoznamo praktiËno uporabnost programa za analizo velikih omreæij - saj s pomoËjo programa laæje najdemo napake pri vnosu. Pri poroki med sinom in vnukinjo gre istoËasno πe za generacijski preskok. Do tega lahko pride zaradi razliËnih vzrokov. Najenostavnejπi razlog je lahko velika razlika Caspar Pollak FranËiπka Napret Viljem Pollak Pavla Smolej Jakob Smolej Marija Pollak Rajko Zupanc Marija Drame Rudof Drame Terezija SeniËar Rudolf Drame Ana Skornik Mihael Drame Jera Smole Martin Magdalenc Domina Zupanc Mihael Magdalenc Marija Drame 20 Druæboslovne razprave, XVII (2001), 36: 9-22 Andrej Mrvar med starostjo poroËnih partnerjev. Do generacijskega preskoka pa lahko pride tudi, Ëe so bile osebe iz razliËnih generacij v danem zgodovinskem Ëasu pribliæno enako stare. Vzrok za to so lahko velike Ëasovne razlike med rojstvi posameznih otrok in velike razlike med starostjo ob poroki posameznih otrok. Generacijskih preskokov lahko v preteklosti najdemo veliko. Pri veËini generacijskih preskokov smo æe dognali, da je obiËajno daljπa veja po æenini strani (torej gre npr. veËkrat za poroko sin-vnukinja kot za poroko vnuk-hËi). To zakonitost lahko pojasnimo z dejstvom, da so se v preteklosti æenske poroËale veliko prej kot moπki. V primeru dubrovniπkega plemstva so se æenske poroËale stare v povpreËju 18, moπki pa 30 let. Glede krvoskrunstva je zadnja situacija (situacija na desni strani slike 6) veliko bolj koËljiva. Podobnih situacij lahko najdemo v velikih rodovnikih zelo veliko. Za merjenje jakosti krvoskrunstva je bil vpeljan poseben indeks prepletenosti (relinking index). Definicijo tega indeksa najdemo v Ëlanku Analyzing Large Kinship and Marriage Networks with Pgraph and Pajek (White et al., 1999). Indeks lahko zavzame vrednosti med 0 in 1, kjer veËja vrednost pomeni bliæje sorodstvo oziroma moËnejπe krvoskrunstvo. Za primer povejmo, da ima bolj oddaljena krvna poroka na levi strani slike 6 indeks prepletenosti 0.2, desna (bliæja) pa 0.5. Indeks doseæe vrednost 1 v primeru poroke med bratom in sestro. Naj omenimo πe, da lahko z istim indeksom merimo tudi jakost prepletenosti, ko ne gre za krvne poroke (poroka med parom bratov in parom sester iz razliËnih rodbin). V omenjenem Ëlanku se nahajajo ta in πe πtevilni drugi primeri in podrobnosti, povezani z analizo rodovnikov, opisani pa so tudi koraki, kako pridemo do æeljenih rezultatov. 5. Sklepne misli V Ëlanku smo prikazali, kako se lahko danes, s sistematiËno metodologijo in ob pomoËi sodobnih informatiËnih sredstev, lotevamo tudi zahtevnejπih analitskih vpraπanj nad velikimi (socialnimi) omreæji. S primeri smo posegli na podroËje empiriËne genealogije in za ponazoritev izvedli nekaj osnovnih vpogledov v Drametov rodovnik. Z uporabljenimi primeri seveda πe zdaleË nismo izËrpali vseh vsebinsko zanimivih vpraπanj, ki so moæna glede na informacije v tej podatkovni bazi. V prihodnje bi zato kazalo (s pomoËjo razpoloæljivih Ëasovnih in poklicnih podatkov) opraviti tudi kakπno longitudinalno πtudijo, na primer o trendnih spremembah v vzorcih statusne homogamije, v starostnih vzorcih poroËanja, v πtevilu potomcev, v πtevilu priseljencev, itn. Posebna vrednost takπnih mikro-socialnih πtudij, zlasti nad rodovniki teritorialnih obmoËij, je - poleg nazornosti - v njihovi morebitni posploπljivosti, saj iz historiËne analize lokalnih pojavov lahko zaslutimo obrise πirπih sprememb v vsakdanjem æivljenju ljudi. Zahvala Zahvaljujem se Antonu Krambergerju, ki je s svojimi pripombami v veliki meri prispeval k boljπi razumljivosti in kakovosti Ëlanka. 21Druæboslovne razprave, XVII (2001), 36: 9-22 Analiza velikih socialnih omreæij Literatura Batagelj, V., Mrvar, A. (1998): Pajek - A Program for Large Network Analysis. Connections, 21, (2), 47-57. Batagelj, V., Mrvar, A. (2000): Some Analyses of Erdös Collaboration Graph. Social Networks, 22, 173-186. Datta, B. N. (1995): Numerical Linear Algebra and Applications. Brooks&Cole Publishing Com- pany, Pacific Grove. Dremelj, P., Mrvar, A., Batagelj, V. (1999): Rodovnik dubrovniπkih plemiπkih druæin med 12. in 16. stoletjem. Drevesa - Bilten Slovenskega rodoslovnega druπtva. Letnik 6, πtevilka 1-4, december 1999, 4-11. Golub, G. H., Van Loan, C. F. (1996): Matrix Computations. The John Hopkins University Press, Baltimore. Fruchterman, T. M. J., Reingold, E. M. (1991): Graph Drawing by Force-Directed Placement. Software, Practice and Experience, 21, 1129-1164. Hummon, N. P., Doreian, P. (1989): Connectivity in a Citation Network: The Development of DNA Theory. Social Networks, 11, 39-63. Hummon, N. P., Doreian, P., Freeman, L. C. (1990): Analyzing the Structure of the Centrality- Productivity Literature Created Between 1948 and 1979. Knowledge: Creation, Diffusion, Utilization, Vol. 11, June, No. 4, 459-480. Kamada, T., Kawai, S. (1989): An Algorithm for Drawing General Undirected Graphs. Informa- tion Processing Letters, 31, 7-15. Mrvar, A. (1999): Analiza in prikaz velikih omreæij. Fakulteta za raËunalniπtvo in informatiko: Doktorska disertacija. Mrvar, A., Batagelj, V. (1997): Pajek - program za analizo obseænih omreæij. Uporaba v rodoslovju. Drevesa - Bilten slovenskega rodoslovnega druπtva. Letnik 4, πtevilka 12, december 1997, 4- 6. Ore, O. (1963): Graphs and Their Uses. New York, Random House. Padgett, J. F., Ansell, C. K. (1989): Robust action and the rise of the Medici 1400-1434. Ameri- can Journal of Sociology, 98, 1259-1319. White, D. R., Jorion, P. (1996): Kinship Networks and Discrete Structure Theory: Applications and Implications. Social Networks, 18, 267-314. White, D. R., Batagelj, V., Mrvar, A. (1999): Analyzing Large Kinship and Marriage Networks with Pgraph and Pajek. Social Science Computer Review - SSCORE, 17 (3), 245-274. Spletni naslovi (izpis: marec 2001) [1] American Presidents GEDCOM file: ftp://www.dcs.hull.ac.uk/public/genealogy/ [2] GENDEX - WWW Genealogical Index: http://www.gendex.com/gendex/ [3] Graph Drawing Competition 1996, graf B: www.research.att.com/conf/gd96/graphs/B [4] Parni rodovniki: http://eclectic.ss.uci.edu/~drwhite/pgraph/p-graphs.html 22 Druæboslovne razprave, XVII (2001), 36: 9-22 Andrej Mrvar [5] Plug-in Chime: http://www.mdli.com/download/chimedown.html [6] Plug-in Cosmo Player: http://cosmosoftware.com/ [7] Plug-in SVG: http://www.adobe.com/svg/viewer/install/ [8] Program GSView: ftp://ftp.cs.wisc.edu/pub/ghost/rjl/ [9] Program Mage: ftp://kinemage.biochem.duhe.edu/PCPrograms/Win95-98/2000 [10] Program RasMol (RASter MOLecules): http://www.umass.edu/microbio/rasmol/getras.htm [11] Rodovniki Mormonov: http://www.familytreemaker.com/00000116.html http://www.genforum.com/mormon/ [12] Slovensko rodoslovno druπtvo: http://genealogy.ijp.si/slovrd/rd.htm [13] Tekmovanja v risanju grafov: http://vlado.fmf.uni-lj.si/pub/gd/gd00.htm [14] Theoretical Computer Science Genealogy: http://sigact.acm.org/genealogy/ [15] Transportation Networks, National Transportation Atlas Database, Bureau of Transporta- tion Statistics: http://www.bts.gov/gis/ntatlas/networks.html Avtorjev naslov Dr. Andrej Mrvar, Fakulteta za druæbene vede Univerze v Ljubljani, p.p. 2547, 1000 Ljubljana, e-mail: andrej.mrvar@uni-lj.si Program Pajek Pajek (Batagelj in Mrvar, 1998; Mrvar, 1999) je programski paket, za okolje Windows (95/ 98/NT/2000), ki omogoËa analizo in prikaz velikih omreæij (omreæij z veË tisoË toËkami). Program je prosto dostopen na naslovu: http://vlado.fmf.uni-lj.si/pub/networks/pajek/ Avtorja programa sta Vladimir Batagelj in Andrej Mrvar. Program Pajek je πe v razvoju. Zadnjo verzijo, razliËna omreæja, analize in druge zanimivosti, povezane z analizo omreæij je moË najti na njegovi predstavitveni strani. Rokopis sprejet februarja 2001. Po mnenju uredniπtva je Ëlanek uvrπËen v kategorijo: izvirni znanstveni Ëlanek (s kvantitativno argumentacijo).