Az igraph csomag és a hálózatos adatstruktúra létrehozása

A hálózatok ábrázolásának és elemzésének automatizálása felé vezető út fontos állomása az, amikor az adatainkból a számítógép által hálózatként érzékelt struktúrát hozunk létre. Mai témánk ezt a nem túl látványos, de annál fontosabb részfeladatát mutatja be a hálózatok manipulálásának.

Hálózatokról már az eddigiekben is számos alkalommal szó esett a blogon. A genealógiai adatbázisok szerkezetéről szóló poszt, illetve annak gyakorlati megvalósítása az internetről lebányászott genealógiákkal egy speciális szempontból tárgyalta a témát: az adatokat gyűjtögető történész szemszögéből közelítette meg a hálózatokat. Az ezekben felvázolt relációs adatstruktúra, az egyének és a házasságok tábla adott felépítése egy olyan sémát követ, amely alkalmas a számos forrásból összeszedegetett adatok hatékony tárolására és kezelésére.

Mindez viszont önmagában még nem a hálózat! Noha az adatbázisunkban kétségkívül ott vannak azok az adatok, amelyből könnyen felépíthető egy genealógiai kapcsolathálózat, a számítógépnek azonban ez egyelőre csak néhány táblázat, tele mindenféle adattal. Pont ugyanolyan, mint bármely más táblázatok. A feladatunk most az, hogy a hálózatunk csomópontjait és a köztük lévő a kapcsolatokat definiáló adatokat átkonvertáljuk egy olyan adatstruktúrává, amelyet már az R nyelv is hálózatként érzékel.

Elöljáróban hangsúlyozni szeretném még, hogy ne tévesszük össze ezt a hálózatos adatstruktúrát a hálózatok vizuális reprezentációjával! Nem magától értetődő ugyanis, hogy a végeredmény szemmel látható lesz majd. Pontosabban szólva az adatok is láthatók persze, de nem abban a grafikus formában, ahogy a hálózatok ábrázolásával általában találkozunk. Az a hálózatos adatstruktúra, amelynek technikai megvalósítására ebben a posztban törekszem, pusztán az adatok egy speciális elrendezési módja. Ennek létrehozására azért van szükség, mert ez szolgál bemenetként az olyan alkalmazásokhoz és algoritmusokhoz, amelyek például különböző számításokat végeznek a hálózatokon, vagy éppen vizuálisan is képesek megjeleníteni azokat.

A fentiek értelmében tehát a történeti hálózatkutatás technikai háttere a következő három lépcsőfokból áll:

  1. Az adatok összegyűjtése az adott kutatás jellegéhez illeszkedő adatbázisban.

  2. Az előbbiek átalakítása egy hálózatos adatstruktúrává. Ez a mostani blogposzt témája.

  3. A hálózatos adatstruktúra elemzése és/vagy vizualizációja.

A gyakorlati megvalósításhoz a konkrét példát ezúttal is egy genealógiai kapcsolathálózat felépítése jelenti. Ehhez a korábban előállított tesztadatokat fogom felhasználni. Első lépésként hozzunk létre egy munkakönyvtárat és mentsük le ebbe a teszt-egyenek.csv és a teszt-hazassagok.csv fájlokat!

Az alábbiakban R nyelven (v4.0.3) írt kódot használok a feladat végrehajtásához. A magyarázó szövegek közé ékelt fekete kódblokkok tartalmát az RStudio-ban egymás alá illesztve elvileg bárki által reprodukálható az itt bemutatott műveletsor. A kódblokkok # kezdetű sorai pusztán magyarázó funkcióval bírnak, ezekre a program futtatásakor nincs szükség.

A hálózatos adatstruktúra megvalósítása

Egy hálózat kapcsolatait definiáló adatok rögzítésére többféle lehetőség is kínálkozik. Megtehetjük ezt például egy úgynevezett szomszédsági mátrix segítségével. Ebben az esetben egy olyan táblázatot kell elképzelni, amelyben miden sor és oszlop a hálózat egy-egy konkrét csomópontjának felel meg. Ha a hálózatunknak N darab csomópontja van, akkor a mátrix N sorból és N oszlopból áll. A kapcsolatok rögzítése a sorok és oszlopok metszéspontjában történik: ha az adott csomópontok között fennáll a kapcsolat, akkor a cellába 1 kerül, ha nem, akkor 0.

A szomszédsági mátrix kiválóan használható abban az esetben, ha a matematikából kölcsönzött eszközökkel akarjuk elemezni a hálózatunkat. A relációs adatbázisban való adatrögzítéshez azonban nem ez a legoptimálisabb választás. (A későbbiekben egyébként, ha szükségünk lenne rá, könnyen elő lehet állítani.)

A másik megoldás, amit én is követek, a kapcsolatok egyenkénti felsorolását jelenti. Itt a két oszlopból álló táblázat minden sora egy-egy konkrét kapcsolatot reprezentál. Vagyis ha L darab kapcsolat szerepel a hálózatban, akkor a táblázatnak L sora lesz. A két oszlopba a kérdéses kapcsolat két végén lévő csomópontok azonosítója kerül. Bemenetként ezt a formátumot kell most előállítanunk.

Ehhez adottak tehát a fentebb belinkelt tesztadatok. A munkakönyvtárba letöltött CSV fájlokat olvassuk be az R-be, majd vizsgáljuk meg a felépítésüket abból a szempontból, hogy mennyire felel meg az a mi céljainknak.

# Ide a saját munkakönyvtárunk elérését kell beírni!
setwd("C:/Munkakönyvtár")
# Töltsük le ide a teszt-egyenek.csv és a teszt-hazassagok.csv fájlokat!

# Az egyenek és hazassagok tábla beolvasása.
# Az első három sorból eltávolítjuk a figyelmeztetést, ami az adatok bizonytalan
# forrása miatt a tudományos célú igénybevételétől óvja a felhasználókat.
egyenek <- read.csv2("teszt-egyenek.csv", skip = 3)
hazassagok <- read.csv2("teszt-hazassagok.csv", skip = 3)

# A két táblázat felépítésének kinyomtatása a konzolra.
str(egyenek)
str(hazassagok)
## 'data.frame':    4237 obs. of  17 variables:
##  $ ID         : int  10001 10002 10003 10004 10005 10006 10007 10008 10009 10010 ...
##  $ nemzNev    : chr  "Széchényi" "Széchényi" "Széchényi" "Széchényi" ...
##  $ kerNev     : chr  "Benedek" "Tamás" "Mihaly" "István" ...
##  $ kerNevRovid: chr  "Benedek" "Tamás" "Mihaly" "István" ...
##  $ nem        : chr  "férfi" "férfi" "férfi" "férfi" ...
##  $ apaID      : int  9999 10001 10001 10002 10003 10004 10004 10004 10004 10005 ...
##  $ anyaID     : int  9999 10331 10331 10332 10333 10334 10334 10334 10334 10335 ...
##  $ szulEv     : int  9999 9999 1530 9999 1560 9999 9999 9999 9999 1592 ...
##  $ szulHo     : int  9999 9999 9999 9999 9999 9999 9999 9999 9999 9999 ...
##  $ szulNap    : int  9999 9999 9999 9999 9999 9999 9999 9999 9999 9999 ...
##  $ szulPont   : int  9999 9999 1 9999 1 9999 9999 9999 9999 1 ...
##  $ szulTelep  : chr  "Ismeretlen" "Ismeretlen" "Ismeretlen" "Ismeretlen" ...
##  $ halEv      : int  1542 1571 1580 1618 1629 1699 1671 1687 1657 1695 ...
##  $ halHo      : int  9999 9999 9999 9999 9999 9999 9999 9999 9999 2 ...
##  $ halNap     : int  9999 9999 9999 9999 9999 9999 9999 9999 9999 18 ...
##  $ halPont    : int  4 4 2 4 3 4 4 4 4 1 ...
##  $ halTelep   : chr  "Ismeretlen" "Ismeretlen" "Szécsényke" "Ismeretlen" ...
## 'data.frame':    1740 obs. of  13 variables:
##  $ hazID    : int  1 2 3 4 5 6 7 8 9 10 ...
##  $ ferjID   : int  10001 10002 10003 10004 10005 10011 10337 10338 10339 10017 ...
##  $ felesegID: int  10331 10332 10333 10334 10335 10336 10013 10015 10016 10340 ...
##  $ hazEv    : int  9999 9999 9999 9999 9999 1630 9999 1664 1667 1680 ...
##  $ hazHo    : int  9999 9999 9999 9999 9999 1 9999 9999 9999 9999 ...
##  $ hazNap   : int  9999 9999 9999 9999 9999 24 9999 9999 9999 9999 ...
##  $ hazPont  : int  9999 9999 9999 9999 9999 1 9999 1 1 1 ...
##  $ hazTelep : chr  "Ismeretlen" "Ismeretlen" "Ismeretlen" "Ismeretlen" ...
##  $ elvEv    : int  8888 8888 8888 8888 8888 8888 8888 8888 8888 8888 ...
##  $ elvHo    : int  8888 8888 8888 8888 8888 8888 8888 8888 8888 8888 ...
##  $ elvNap   : int  8888 8888 8888 8888 8888 8888 8888 8888 8888 8888 ...
##  $ elvPont  : int  8888 8888 8888 8888 8888 8888 8888 8888 8888 8888 ...
##  $ elvTelep : chr  "Nem vonatkozik rá" "Nem vonatkozik rá" "Nem vonatkozik rá" "Nem vonatkozik rá" ...

A kódblokk utáni első ábra az egyének tábla felépítését mutatja. Az ebben szereplő mezőkből nekünk háromra lesz szükségünk: ID, apaID és anyaID. Ezekben a kérdéses személyek, illetve a szüleik azonosítója szerepel. A második ábrán a házasságok tábla felépítése látható. Itt a ferjID és a felesegID mezőkben az adott házaspár két tagjának azonosítóit találjuk. Az említett az adatokból minden további nélkül előállítható a tervezett hálózatunk. Technikai szempontból először egy-egy részhálózatot hozok majd létre az apaID–ID, az anyaID–ID és a ferjID–felesegID kapcsolatpárokból, majd egyesítem ezeket.

Ugyanakkor nem hagyhatjuk figyelmen kívül, hogy a szülők egyike-másika esetleg ismeretlen, akiket egységesen a 9999-es ID-vel kódoltam be. Erre láthatunk is egy példát az első ábra 7. és 8. sorában, a legelső személynél. (A házasságoknál ilyen nem fordulhat elő, mert aki nem kötött házasságot, az eleve hiányzik onnan.) Azokat a szülő-gyermeki kapcsolatokat tehát, amelyeknél az apa vagy az anya ismeretlen, el kell távolítani a bemeneti adatokból. Ellenkező esetben – a tényleges családi hovatartozásuktól függetlenül – a 9999-es ID-hez hozzákötné a rendszer az összes ismeretlen szülővel rendelkező gyermeket.

A hálózatos adatstruktúra létrehozására többféle csomag is rendelkezésre áll az R nyelven. Én már évek óta az igraph csomagot használom erre a célra, amely funkciógazdag és nagyon jól dokumentált.

# A szükséges csomagok betöltése.
# A legelső használat előtt az install.packages("...") utasítással telepíteni   
# kell ezeket. A ... helyére az adott csomag neve írandó.
library(igraph)

# Az apa-gyermek hálózat létrehozása.
halozatApaGyermek <- egyenek[egyenek$apaID != 9999, c("apaID","ID")] %>%
  graph_from_data_frame(directed = T)

# Az anya-gyermek hálózat létrehozása.
halozatAnyaGyermek <- egyenek[egyenek$anyaID != 9999, c("anyaID","ID")] %>%
  graph_from_data_frame(directed = T)

# A házasságok hálózatának létrehozása.
halozatHazassagok <- hazassagok[,c("ferjID","felesegID")] %>%
  graph_from_data_frame(directed = T)

# A részhálózatok egyesítése.
halozat <- halozatApaGyermek %u% halozatAnyaGyermek %u% halozatHazassagok

# A hálózat felépítésének kinyomtatása a konzolra.
print(halozat)
## IGRAPH 0bee5a6 DN-- 4232 6948 -- 
## + attr: name (v/c)
## + edges from 0bee5a6 (vertex names):
##  [1] 17552->17324 17549->17310 17546->17298 17544->17296 17542->17294
##  [6] 17540->17292 17539->17292 17535->17288 17534->17287 17533->17286
## [11] 17531->17283 17530->17283 17528->17280 17526->17277 17518->17275
## [16] 17517->17274 17516->17273 17514->17271 17510->17268 17507->17265
## [21] 17494->17255 17493->17253 17489->17248 17487->17245 17485->17243
## [26] 17484->17242 17480->17231 17477->17227 17476->17225 17475->17222
## [31] 17474->17221 17473->17220 17471->17217 17469->17214 17465->17206
## [36] 17464->17204 17456->17192 17454->17188 17452->17182 17450->17176
## + ... omitted several edges

A halozat változóban tárolva most már ott van a hálózatos adatstruktúránk, de ez még nem az igazi. A figyelmes olvasó rögtön két anomáliát is felfedezhet a fenti kódblokkban, illetve a konzolra kinyomtatott részben. (A problémás sorokat szürkével megjelöltem.)

A konzolra nyomtatott információk első sorának végén két szám szerepel: 4232 és 6948. Ezek a hálózatban lévő csomópontokról és kapcsolatokról tájékoztatnak. Csakhogy az egyének táblánkban – ahogy fentebb, e tábla felépítésének ábrázolásánál látható – 4237 rekord van, azaz 5 személy hiányzik a hálózatból. Ennek az az oka, hogy az illetők valami miatt nem kapcsolódnak senkihez sem. Jelen esetben, mivel az adatkészletünk hangsúlyozottan nem tudományos célú igénybevételre készült, ez nem jelent gondot. Sőt, még előnyös is, mert demonstrálni lehet vele egy lehetséges problémát. Egy valós kutatási szituációban azonban el kellene gondolkodni azon, hogy a megfigyelt különbség normális dolog-e, s ha nem, akkor hol hibáztunk. Én most úgy tekintem, hogy szükségünk van ezekre a különálló pontokra és utólag hozzáadom őket a hálózathoz. (Ez persze nem változtat azon a tényen, hogy kapcsolat nélküli, különálló csomópontok maradnak!)

A másik anomália a kódblokk kiemelt sorában látható: a házassági kapcsolatokból – a felmenő-leszármazotti kapcsolatokhoz hasonlóan – egy irányított hálózat lett létrehozva. Ez ellentétben van azzal, amit erről a genealógiai kapcsolatok hálózatként való értelmezéséről szóló blogposztomban írtam. Ott ugyanis a házassági kapcsolatokat irányítatlannak definiáltam. A korábbi véleményemet természetesen most is fenntartom. A gyakorlati megvalósítás azonban technikai nehézségekbe ütközik: az igraph nem enged olyan hálózatot létrehozni, amelyben irányított és irányítatlan kapcsolatok egyaránt előfordulnak.

Itt a megoldás az lesz, hogy a hálózat ugyan csupa irányított kapcsolattal jön létre, de az egyes kapcsolatokat megjelölöm aszerint, hogy azok a valóságban is irányítottak-e. Ennek a markernek a feldolgozása, ahol az szükségesnek mutatkozik, a későbbiekben egy külön algoritmussal történik. Ez a plusz macera azonban mindenképpen megéri, mert nem pusztán elméleti kérdésről van szó. A hálózat irányítottságának nagy szerep jut például a konkrét genealógiai kapcsolatok detektálásának megvalósításában.

# A kapcsolat nélküli csomópontok hozzáadása a hálózathoz.
halozat <- halozat + vertices(setdiff(egyenek$ID, as.numeric(V(halozat)$name)))

# A házassági és a felmenő-leszármazotti kapcsolatok irányítottságának megjelölése.
# Ezt nem lehet előzetesen megtenni, mert a részhálózatok egyesítésekor elveszik
# ez a plusz paraméter.
kapcsolatMinden <- paste(get.edgelist(halozat)[,1], get.edgelist(halozat)[,2], sep = "|")
kapcsolatHazassagok <- paste(get.edgelist(halozatHazassagok)[,1], get.edgelist(halozatHazassagok)[,2], sep = "|")
E(halozat)$iranyitott <- !(kapcsolatMinden %in% kapcsolatHazassagok)

Ellenőrzésképpen futtassunk le két számszaki ellenőrzést!

# A hálózat csomópontjainak száma megegyezik-e az egyének tábla sorainak számával?
length(V(halozat)) == nrow(egyenek)
## [1] TRUE
# Az irányítatlannak megjelölt kapcsolatok száma egyenlő-e a házasságok
# tábla sorainak számával?
sum(!E(halozat)$iranyitott) == nrow(hazassagok)
## [1] TRUE

Mindezek után még egy dolgot érdemes megtenni. A létrehozott hálózat csomópontjai a mögöttük álló egyének ID-jeivel vannak azonosítva. Ezen nyilván nem akarunk változtatni, azonban a könnyebb tájékozódás érdekében jó lenne felcímkézni a csomópontokat az illetők nevével és születési-halálozási évével. Az alábbi kódblokk erre kínál megoldást.

# Egy új mező létrehozása az egyének táblában a címke szövegével.
egyenek$label <- paste0(egyenek$nemzNev, " ", egyenek$kerNevRovid, " (", egyenek$szulEv, "-", egyenek$halEv, ")")

# A címke hozzáadása a hálózat csomópontjaihoz.
V(halozat)$label <- egyenek[match(as.numeric(V(halozat)$name), egyenek$ID),"label"]

Az elkészült hálózatos adatstruktúra

Ezzel készen is vagyunk a hálózatos adatstruktúrával. Ahogy a bevezetőben említettem, a történeti hálózatok kutatásában ez a műveletsor az adatgyűjtés és az adatok elemzése, vizualizációja között elhelyezkedő lépcsőfoknak tekinthető.

Van már tehát egy “láthatatlan” hálózatunk, de lényeg csak ezután jön majd. A következő posztban a most elkészített hálózatra fogok támaszkodni, ezért egy RDATA fájlba kimentem (save(halozat, file = "halozat.RData")) és letölthetővé teszem itt: halozat.RData. Ezt a későbbiekben egyszerűen vissza lehet tölteni az R-be.

comments powered by Disqus