Magyar Tudomány, 2006/11 1319. o.

Hálózatok

Csoportosulások szociológiai, technológiai

és biológiai hálózatokban

A valóságban megfigyelhető hálózatok többsége inhomogén szerkezetű, ennek a legárulkodóbb jele az, hogy a hálózatban csomósodások találhatók. Ezek a csomósodások (vagy más néven csoportosulások, klaszterek, modulok, community-k) a hálózatnak olyan „sűrű” részgráfjai, amelyeken belül az elemek (csúcsok) gyakrabban kapcsolódnak egymáshoz, mint a hálózat többi részéhez. A hálózatok funkciója, illetve dinamikája szempontjából minden bizonnyal meghatározó szerepük van a csoportosulásoknak. Gondoljunk például az emberi kapcsolatok hálózatára, ahol a járványok és a hírek egy-egy csoportosuláson belül nagyon gyorsan terjednek, hiszen olyan emberekről van szó, akik közül nagyon sokan személyesen ismerik egymást, a csoportosulások között viszont lassabb lehet a terjedés. A világháló oldalainak hálózatában megtalált sűrű csoportosulások olyan weboldalak, amelyek között sok mutató utal egymásra. Ezek gyakran azonos témájú vagy földrajzilag egymáshoz közel található oldalak, és a megtalálásuk a keresőprogramok számára jelentős segítséget nyújthat. Szintén számos érdekes felismerést és gyakorlati hasznosítási lehetőséget rejtenek azok a csoportosulások, amelyeket sejtjeink molekulái alkotnak. Ha felismerünk egy csoportot, amely néhány vagy akár néhány tucatnyi molekulatípust tartalmaz, és ezek a molekulák sokféle kölcsönhatásra képesek egymás között, de kevesebbre másokkal, akkor gyakran előfordul, hogy ennek a csoportnak jól leírható önálló funkciója, feladata van a sejtben. Nagy és komplex hálózatokban a csoportosulások azonosítása nem könnyű, de még csak nem is jól definiált feladat. Jelentősége miatt azonban erre a célra az elmúlt évtizedekben számos módszert dolgoztak ki, amelyek közül néhány fontosabbat tekintünk át a következőkben.

Klaszterezés a hálózat felosztásával

Természetesen egy hálózatban minden kapcsolatnak (élnek) lehet iránya, erőssége (súlya) és több más jellemzője, akárcsak a csúcsoknak. A következőkben viszont csak ún. egyszerű gráfokat vizsgálunk, amelyekben minden él irányítatlan és azonos erősségű, valamint a csúcsoknak sincsenek további tulajdonságaik. Egyszerű gráfok esetén a klaszterezés legelterjedtebb módja a gráf felosztása: ennek során a gráf minden egyes csúcsát besoroljuk valahány csoport egyikébe (Kernighan – Lin, 1970). Ezt sokféleképpen tehetjük meg. Számos módszer alapszik például a szomszédsági mátrix sajátértékeinek és sajátvektorainak meghatározásán. Ebben a mátrixban az i. sor j. oszlopában 1 vagy 0 szerepel aszerint, hogy a hálózat i. és j. csúcsa között van-e kapcsolat.

Nagyon szemléletes megközelítés az, amikor a gráf éleit elkezdjük egyesével eltávolítani valamilyen szabály alapján, majd egy ponton megállva a megmaradt élek által összetartott komponenseket feleltetjük meg a hálózat csoportosulásainak. Eltávolítandó élnek érdemes mindig a leggyengébb láncszemet választani, vagyis azt a kapcsolatot, amely a legnagyobb terhelésnek van kitéve, ha például az éleket drótoknak képzeljük, és véletlenszerűen választott pontpárok között elektromos áramot folyatunk át a rendszeren. A terhelés ugyanis várhatóan a sűrű tartományok között futó éleken lesz a legnagyobb, így ezek eltávolítása során a sűrű tartományok többnyire érintetlenül maradnak. Kérdés azonban, hogy az élek eltávolításával mikor érdemes megállni. Szeretnénk azt az állapotot megtalálni, amikor az eredeti gráfban meglévő sűrű tartományok közé eső néhány él már eltűnt, de maguk a sűrű tartományok még nem kezdtek el szétesni. Ennek a problémának a megoldására vezette be Michelle Girvan és Mark E. J. Newman a modularitás fogalmát (Girvan – Newman, 2002). Ez a mennyiség jellemzi, hogy a gráf pillanatnyi felosztása mellett hogy viszonyul egymáshoz a csoportosulásokon belül, illetve között futó élek száma az eredeti gráfban. A megállás pillanatát ezek után a modularitás maximumának elérésével határozhatjuk meg.

A hálózat bontása helyett az optimális felosztást megpróbálhatjuk elérni építkezéssel is. Ehhez induljunk ki abból a gráfból, amely a csúcsokon kívül egyetlen élt sem tartalmaz, majd helyezzük be az éleket egyesével. Kézenfekvő megoldás lehet, hogy minden pillanatban azt az élt választjuk, amely a legnagyobb mértékben növeli meg a modularitás értékét, és akkor állunk meg az építkezéssel, amikor a modularitás eléri a maximumát.

A különböző csoportosuláskereső módszerek tesztelésére és összehasonlítására néhány jól definiált hálózatot szokás használni. Az egyik leggyakrabban előforduló példa (Zachary, 1977) egy 34 tagú sportklub a 70-es évekből. A klub két részre szakadása előtt – a jövőt nem sejtve – szociológusok feltérképezték a klubon belüli személyes kapcsolatokat. A módszerek tesztelésekor az eredeti sportklub ismeretségi hálózatában kiszámított két csoportosulást a klub szakadása után létrejött két csoporttal hasonlítják össze. Egy másik gyakran használt teszthálózat 64 (vagy 128) pontból áll, és minden alkalommal véletlenszerűen elkészítik úgy, hogy négy egyenlő méretű részén belül sok él fusson, míg a részek között kevesebb. Szintén gyakran használt tesztgráf az Egyesült Államok egyetemi futballcsapatai közötti találkozók hálózata. Mivel a csapatok a legtöbb mérkőzésüket a földrajzi hely szerint szerveződő csoportokban játsszák, ezért egy klaszterező módszernek jó ellenőrzése lehet, hogy ebben a hálózatban megtalálja-e az egyes területi csoportokat.

Átfedő csoportosulások keresése lokális kapcsolatsűrűség segítségével

A gráfok különálló részekre való felosztásával szükségszerűen olyan klaszterezést kapunk, amelyben a hálózat minden csúcsa legfeljebb egy csoportosuláshoz tartozhat, tehát a csoportok között nincsen átfedés. A valódi hálózatokban azonban igen gyakoriak a csoportosulások közötti átfedések. Másképpen fogalmazva: egy elem több sűrűn összekapcsolt csoportnak is tagja lehet. Az egyik legismertebb példa erre az ismeretségi kapcsolatok hálózata. Ebben a hálózatban mindannyian több, egymástól eltérő szerepű csoportosulásnak is tagjai vagyunk. Példaként említhető családunk, iskolatársaink köre, baráti körünk vagy munkatársaink. A többszörös átfedések is gyakoriak, például a baráti körünkben számos iskolatárs is lehet. Szintén érdekes átfedő csoportosulásokat tartalmaz egy nyelv szavainak asszociációs hálózata (1. ábra). Ebben a hálózatban minden csúcs az adott nyelv egy-egy szavát jelöli, és két csúcs össze van kötve, ha az általuk jelölt két szót a vizsgálatokban megkérdezett személyek társítják egymáshoz.

Érdekes megvizsgálni, mi történik az ismeretségi hálózattal, ha felosztással próbálunk benne csoportosulásokat keresni, tehát átfedéseket nem engedünk meg. Tudjuk, hogy a legtöbb ember több csoportosuláshoz tartozik egyszerre, ezért akármilyen módon jelölünk ki a hálózatban számára egyetlen, a többivel nem átfedő klasztert, akkor abban az adott résztvevő több csoportosulásának töredékei együtt lesznek jelen. Például ha az ismeretségi hálózatban a jelen cikk valamelyik szerzője számára egyetlen klasztert jelölnénk ki, akkor ebbe nagy valószínűséggel családtagok, iskola- és munkatársak egyaránt belekerülnének. Ez a megoldás két fontos hibalehetőséget rejt: a kijelölt egyetlen csoportosulásba belekerülnének olyanok is, akik nem ismerik egymást, pl. a vizsgált ember valamelyik családtagja és munkatársa (téves pozitív); sok családtag viszont különböző klaszterbe kerülne (téves negatív).

Az ismeretségi hálózaton kívül több más esetben is köztudott, hogy az egyes elemek gyakran több csoportosuláshoz tartoznak. A molekuláris biológiai hálózatok közül egy igen részletesen vizsgált példa a sarjadzó élesztő (S. cerevisiae) nevű egysejtű élőlény fehérjéinek kölcsönhatási hálózata (Salwinski et al., 2004). Ebben az élőlényben a jelenlegi kísérleti eszközökkel már megvan a lehetőség arra, hogy bizonyos típusú csoportosulásokat (a fehérjekomplexeket) mérési módszerekkel azonosítsunk (Rigaut et al., 1999). Az így megtalált csoportosulásokban összesen 2750 fehérje vesz részt (Guldener et al., 2005), ám a csoportosulások méreteinek összege 8932, tehát egy fehérjét átlagosan háromnál több csoportosulás tartalmaz. Az angol nyelv leggyakrabban használt szavainak hálózatával kapcsolatos eredmény hasonló: a hálózattól függetlenül megállapított 238 szócsoport összesen 3369 különböző szóalakot tartalmaz (Roget’s, 1995), ám ennél jóval nagyobb a csoportok méreteinek összege (5248), tehát a szavak jelentős része több csoportnak is tagja.

A klikk-perkolációs módszer

A hálózatokban található átfedő csoportosulások keresésére egy lehetséges eljárás a 2. ábrán mutatott klikk-perkolációs módszer (Clique Percolation Method – CPM). Ez a módszer k darab csúcsból álló, teljesen összekötött részgráfokat (k-klikkeket) használ a csoportosulások felépítéséhez (Derényi et al., 2005; Palla et al., 2005). Két k-klikket akkor mondunk szomszédosnak, ha csak egyetlen csúcsban különböznek egymástól, azaz k-1 csúcsuk közös. Egy CPM segítségével kapott csoportosulás olyan k-klikkekből épül fel, melyek közül bármelyikből eljuthatunk bármely másikba szomszédos k-klikkeken keresztül. Ez a megközelítés nagyon közel áll a csoportosulások eredeti megfogalmazásához: a csoportosulásokon belül sok kapcsolatot szeretnénk, a csoportosulások között viszont keveset, hiszen k darab csúcs akkor van a lehető legsűrűbben összekötve, ha egy k-klikket hoznak létre. A bevezetett k-klikk szomszédság segítségével definiálhatjuk a k-klikkek hálózatát is, ahol az egyes csúcsok az eredeti hálózat k-klikkjeinek felelnek meg, és két csúcs között akkor van él, ha a megfelelő k-klikkek szomszédosak. A csoportosulások ebben a képben a k-klikk hálózat összefüggő komponenseinek felelnek meg. Ezeket a statisztikus fizikában perkolációs klasztereknek szokás nevezni, innen a módszer elnevezése. Az eredeti hálózatban egy csúcs egyszerre több k-klikk perkolációs klaszternek (csoportosulásnak) is tagja lehet, így a CPM természetes módon engedi meg a csoportosulások átfedéseit.

A csoportosulások közötti átfedések lehetővé tétele mellett a CPM módszer másik fő előnye a gráffelosztási módszerekkel szemben az, hogy lokális. Egy él betételének, illetve kivételének csak azokra a csoportosulásokra lehet hatása, amelyek az él valamelyik végpontját tartalmazzák, ám már egyetlen él megváltoztatása is hatással van a felosztási módszereknél használt globális tulajdonságokra (szomszédsági mátrix sajátvektoraira, áramok eloszlásaira, modularitásra stb.), ami a felosztást alapvetően átrendezheti.

Alkalmazások: a csoportosulások fejlődése és a csoportosulások hálózata

A klikk-perkolációs módszer két jelentős előnye, hogy lokális módszer, és megengedi az átfedő csoportosulásokat. A CPM önmagában azonban csak egyetlen hálózatot vizsgál, annak ellenére, hogy sok gyakorlati esetben a csoportosulások fejlődése is igen érdekes kérdés lehet. Az emberi ismeretségek hálózatában gyakran fontos a klaszterek fejlődése: szolgáltatók (munkáltatók) számára az ügyfeleik (alkalmazottaik) kapcsolataiban, biztonsági szolgálatok számára a figyelt személyek között, de akár egy-egy tudományterület fejlődése is nyomon követhető az adott területen aktív kutatói csoportosulások alakulásán keresztül. A csoportosulások fejlődésének vizsgálatára egy egyszerű módszer a következő. Végezzük el a klaszterezést a CPM-mel a hálózat összes állapotára, majd az időben egymás után következő állapotokat hasonlítsuk össze, és keressük meg az egyes időlépésekben eltűnő, születő, megmaradó, összeolvadó, illetve felhasadó csoportosulásokat. Nagy hálózatok esetén az elemzést és az áttekinthetőséget elősegítő érdekes további lehetőség a csoportosulások hálózatának kiszámítása. Az eredeti hálózat minden egyes csoportosulását ábrázoljuk egyetlen ponttal, és két pontot kössünk össze, ha az általuk jelölt két csoportosulás között van átfedés.

A szerzők honlapjáról, a http://angel.elte.hu/cfinder címről szabadon letölthető a CFinder (Clique and Community Finder) program, amely a klikk-perkolációs módszer használatával csoportosulásokat keres, és – több más elemzéssel együtt – a talált csoportosulások hálózatát bemutatja. A program tudományterülettől függetlenül alkalmazható minden olyan adatrendszer elemzésére, amely hálózatként ábrázolható. A felhasznált bemenő adatfájl a hálózat éleit sorolja fel, minden sorban a hálózat két, egymással összekötött csúcsának a nevét kell megadni. A program Windows-, Linux- és Macintosh-alapú számítógépeken egyaránt használható.

A CFinder segítségével végzett vizsgálataink szerint a kutatói együttműködési csoportosulások hálózata az eredeti együttműködési hálózathoz hasonló szabályok szerint növekszik (Pollner et al., 2006). Az eredeti szerzőtársi hálózatban egy új szerző (például egy diák) a már aktív kutatók közül nagyobb valószínűséggel lesz olyan kutatónak szerzőtársa, akinek az adott pillanatban több, már meglévő szerzőtársi kapcsolata van. Az együttműködési csoportosulások hálózatában egy újonnan létrejött csoport nagyobb valószínűséggel fog közös szerzőt tartalmazni olyan csoporttal, amelynek nagyszámú közös eleme van már más csoportokkal is. Néhány további érdekes alkalmazás, amely a CFinder felhasználásával született: a sarjadzó élesztő fehérje-fehérje kölcsönhatási hálózatában korábban nem ismert csoportok és új fehérjefunkciók azonosítása (Adamcsek et al., 2006), majmok agyának látókérgében az ott található idegsejtkapcsolatok hálózata alapján az egyes területek szerepének elemzése (Négyessy et al., 2006), könnyűzenei előadók csoportosulásainak vizsgálata és szociológiai értelmezése (Smith, 2006), valamint daganatos elváltozásokban a sejt megváltozott működéséért felelős fehérjék keresése (Jonsson et al., 2006).

A szerzők kutatásait az OTKA D048422, F047203 és T049674 jelű pályázatai támogatják.

Kulcsszavak: átfedés, csoportosulás, klaszter, klikk, perkoláció

1. ábra • A University of South Florida Free Association Norms angol nyelvű szóasszociációs hálózatban a gold (arany) szóhoz talált négy csoportosulás magyar nyelvű megfelelői. A körökkel jelölt csoportosulás fémekkel, a háromszögekkel jelölt csoportosulás olimpiai érmekkel kapcsolatos, míg a másik két csoportosulás a jólét, illetve az ékszerek köré rendeződik. A vastagított él és két csúcs több csoportosuláshoz tartozik, azaz csoportosulások átfedésében találhatóak. A pontozott vonalak csoportosulások közötti kapcsolatokat mutatnak.

2. ábra • A klikk-perkolációs módszer (CPM) bemutatása egy kis hálózaton k=4 méretű klikk esetén. A bal oldali ábrán látható, fekete színű élekkel jelölt klikknek (teljes részgráfnak) minden lépésben egyetlen csúcsát mozdítjuk el úgy, hogy a klikk a vizsgált hálózat csúcsain és élein „gördüljön”. Minden gördülési lépés során a korábbi és a későbbi, k=4 csúcsból álló klikk k-1=3 csúcsa közös. A gördülés során bejárt élek (a jobb oldali ábrán feketével jelölve) és az általuk összekötött csúcsok alkotják a hálózat egy csoportosulását.

IRODALOM

Adamcsek Balázs – Palla G. – Farkas I. J. – Derényi I. – Vicsek T. (2006): CFinder: Locating Cliques and Overlapping Modules in Biological Networks. Bioinformatics. 22, 1021–1023.

Derényi Imre – Palla G. – Vicsek T. (2005): Clique Percolation in Random Networks. Physical Review Letters. 94, 160202:1–4.

Girvan, Michelle – Newman, Mark E. J. (2002): Community Structure in Social and Biological Networks. Proceedings of the National Academy of Sciences of the USA. 99, 7821–-7826.

Guldener, U. et al. (2005): CYGD: the Comprehensive Yeast Genome Database. Nucleic Acids Research. 33, D364–D368.

Jonsson, P. F. – Cavanna, T. – Zicha, D. – Bates, P. A. (2006): Cluster Analysis of Networks Generated through Homology: Automatic Identification of Important Protein Communities Involved in Cancer Metastasis. BMC Bioinformatics. 7, 2.

Kernighan, Brian W. – Lin, Shen (1970): An Efficient Heuristic Procedure for Partitioning Graphs. Bell System Technical Journal. 49, 291–308.

Négyessy László – Nepusz T. – Kocsis L. – Bazsó F. (2006): Prediction of the Main Cortical Areas and Connections Involved in the Tactile Function of the Visual Cortex by Network Analysis. European Journal of Neuroscience. 23, 1919–1930.

Palla Gergely – Derényi I. – Farkas I. – Vicsek T. (2005): Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society. Nature. 435, 814–818.

Pollner Péter – Palla G. – Vicsek T. (2006): Preferential Attachment of Communities: The Same Principle, but a Higher Level. Europhysics Letters. 73, 478–484.

Rigaut, Guillaume – Shevchenko, A. – Rutz, B. – Wilm, M. – Mann, M. – Seraphin, B. (1999): A Generic Protein Purification Method for Protein Complex Characterization and Proteome Exploration. Nature Biotechnology. 17, 1030–1032.

Roget’s II: The New Thesaurus. 3. kiadás. (Boston, Houghton Mifflin, 1995) http://www.bartleby.com/62

Salwinski, Lukasz – Miller, C. S. – Smith, A. J. – Pettit, F. K. – Bowie, J. U. – Eisenberg, D. (2004): The Database of Interacting Proteins: 2004 Update. Nucleic Acids Research. 32, D449–D451.

Smith, Reginald D. (2006): The Network of Collaboration among Rappers and Its Community Structure. Journal of Statistical Mechanics – Theory and experiment. Art. No. P02006.

Zachary, Wayne W. (1977): An Information Flow Model for Conflict and Fission in Small Groups. Journal of Anthropological Research. 13, 452–473.

<-- Vissza a 2006/11 szám tartalomjegyzékére

<-- Vissza a Magyar Tudomány honlapra

[Információk] [Tartalom] [Akaprint Kft.]