Az elmúlt tíz évben ismereteink jelentősen bővültek a szociális hálózatok tulajdonságainak, a kapcsolatok kialakulásának és változásainak és a hálózati résztvevők osztályozásának területein, amelyek kiemelt fontosságúak a telefontulajdonosok szegmentációja, a marketing célcsoportok kiválasztása, az információterjedés vagy egyéb viselkedés előrejelzése céljából is. A szakirodalomban több összefoglaló munkát találhatunk, amelyek közül kiemeljük Barabási Albert-László (2002) magyarul is megjelent művét.
Tanulmányunkban, amely a (Kurucz et al., 2008) cikk válogatott kivonata, a szociális hálózatok modellezésének és vizsgálatának legújabb eredményeit alkalmazva bemutatjuk a hazai vezetékes telefonhívások által megrajzolt kapcsolati hálózat elhelyezkedését az ország területén belül. Egyedülálló adathalmazunk több millió anonimizált telefontulajdonos hosszú időszakon keresztül történő összesített viselkedését tartalmazza. Eredményeink alapján intuíciót nyerhetünk a szociális kapcsolatok térbeliségéről. Három fő területet vizsgálunk: a kapcsolatok távolságának eloszlását és ezen keresztül az ún. „kis világ” létrejöttét; az egymással szorosabb kapcsolatban álló csoportok települések szerinti hierarchikus tagozódását; végül pedig a hálózati kapcsolatok alkalmazhatóságát a résztvevők tulajdonságainak modellezésében és előrejelzésében.

Legfontosabb megfigyeléseink között említhető a közösségek hierarchiájának erőteljes, felülről lefelé történő szerveződése, amelyben a nagyvárosok egyetlen, nehezen továbbosztható csoportként jelennek meg. A hívások hálózatának fő jellemzői, hogy a kapcsolatok száma hatványeloszlást követ, aminek következtében a közösségek a sok kapcsolattal rendelkező központok köré csoportosulnak. A hálózat résztvevőinek jelentős része ugyanakkor a központokból induló hosszú nyúlványokban helyezkedik el. A nagyléptékű struktúra ugyanakkor csak a sűrű magok és a nyúlványok mint lokális jelenségek tisztítása és előfeldolgozása után ismerhetők meg, ez önálló kutatási eredményünk.

Az adathalmaz

Az általunk vizsgált, több mint kétmillió telefontulajdonosból előálló hálózat követi a szociális hálózatok általános viselkedését. A kapcsolatok száma hatványeloszlást követ (Barabási et al., 2000), azaz a k darab kapcsolattal rendelkezők száma k-γ-val arányos, ami azt is jelenti, hogy meglepően sok nagy kapcsolati számmal rendelkező telefontulajdonost találunk. A hálózat átmérője kicsi (Watts – Strogatz, 1998; Albert et al., 1999), azaz tetszőleges két személy között általában néhány lépésen keresztül kapcsolatot tudunk teremteni. Végezetül a résztvevők kisszámú kivételtől eltekintve egyetlen hatalmas összefüggő hálózat részét képezik. A bemutatásra kerülő mérések egy kisebb és egy nagyobb hálózaton történnek, amelynek adatait és a települések méret szerinti eloszlását az 1. ábra tartalmazza. Az eloszlás a kiugróan magas, majdnem 600 ezer telefonvonallal rendelkező Budapest elhagyása után közel lognormális.

Navigáció a kis világban

Az ún. „kis világ” jelenséget elsőként Stanley Milgram (1967) mutatta be híres kísérletében, amelyben az Egyesült Államok polgárai közötti kapcsolati távolságok átlagos értékeként nem egészen hat lépés adódott. A kicsi átmérő tulajdonságot azóta több hálózat, így például a World Wide Web esetében is megfigyelték (Albert, 1999), és az általunk vizsgált hálózatnak is sajátja. Néhány híresebb modell (Watts − Strogatz, 1998) között számunkra kiemelkedő fontosságú Jon Kleinbergé (2000), amely a kis átmérő mellett Milgram kísérletének egy további kulcsmozzanatát is modellezi. A tetszőleges két személy közötti hat lépéses távolság ugyanis nemcsak elméletben létezik, hanem a kísérlet résztvevői képesek is azt pusztán lokális kapcsolati információjuk segítségével megtalálni. Valójában Milgram kísérletében néhány nem lokális információ is adott volt, például a célszemély lakhelye vagy foglalkozása. Kleinberg modelljében a navigáció a lakhelyen, azaz egészen pontosan a célszemély földrajzi koordinátáin alapul, s az útvonal minden lépésben a földrajzilag legközelebb vivő kapcsolatokon keresztül halad.

Kísérletünkben megvizsgáltuk Kleinberg (2000) útvonalkereső módszerének lépésszámát és az általa adott modell paramétereinek érvényességét a hazai telefonhívások által rajzolt kapcsolati hálózaton. Összességében megállapítottuk, hogy ha Budapest torzító hatását kiszűrjük, akkor a modell kellően jól illeszkedik a hazai kapcsolati hálóra, ám Budapesttel együtt ugyanez már kevéssé mondható el. Valójában Budapesten belül már az adatok hiányossága miatt sem tudtuk az útvonalkereső algoritmust alkalmazni, mivel utca- és házszámszintű földrajzi pozíció nem állt rendelkezésünkre. Ezért általánosságban is megelégedtünk azzal, hogy a céltelepülést elérjük, azaz például két budapesti (vagy azonos településen lakó) személy között azonnal, nulla lépésben véget ér az útvonalkeresés.
A mérési eredményeket a 2. és a 3. ábrákon mutatjuk be. Az első a települések elhelyezkedését ábrázolja (Budapest tehát egyetlen pont), illetve Budapest hatását kiszűrendő kiemeli a kiválasztott nyugati országrészt. A 2. ábrán az adott távolságra levő kapcsolatok számát láthatjuk. Ez Kleinberg modellje szerint a távolság -d hatványával arányosan csökken, ahol d a földrajzi tér dimenziószáma – normál esetben tehát kettő. Miközben a teljes ország területén az illeszkedés meglehetősen zajos, és a -1 hatvány grafikonja közelebb áll az egyeneshez, mint a -2 hatványé, a nyugati országrészben már a modell által jósolt -2 hatvány illeszkedést látjuk. A teljes ország talán egy torz, Budapesttől mért egydimenziós távolságú képet mutat, azonban Budapestet kihagyva már egészséges kétdimenziós kapcsolati mozgást látunk. A 3. ábrán azt is megfigyelhetjük, hogy egymillió véletlen telefontulajdonos-pár között a nagy kapcsolati távolságok exponenciális sebességgel tűnnek el, és a tíz lépésen belül nem elérhető párok száma százas nagyságrendű marad. Ne felejtsük azonban el, hogy az útvonal keresése a települést elérve megáll, ami jogos lehet egy falu esetében, de értelmetlen egy nagyvárost, vagy Budapestet tekintve. (4. ábra)

Klaszteranalízis

A klaszterezés vagy csoportosítás, (felügyelet nélküli) osztályozás célja az ügyfelek értelmezhető, fontos információkat bemutató, a teljes állomány áttekintését megkönnyítő felosztása. Telefontulajdonosok esetében így az ügyfeleket szegmentálhatjuk, kívánatos vagy elkerülendő csoportokat határozhatunk meg, amelyekben például nagy a hajlandóság valamely új szolgáltatás kipróbálására – vagy éppen lemondására, fizetési késedelemre.

Telefonhívás-hálózatok klaszterezése esetén azzal a nehézséggel szembesülünk, hogy a kis világ tulajdonság (Milgram, 1967; Watts–Strogatz, 1998) következtében az egyes közösségek környezete erősen keveredő, átfedő. A kapcsolatok számának hatványeloszlása (Barabási et al., 2000) következtében pedig sok olyan csomópontot találunk, amelyek nagyon sok szomszéddal rendelkeznek, és így sok közösséget kapcsolnak össze. A résztvevők jelentős része ugyanakkor távolabb van a központi magtól és hosszas nyúlványokban kötődik azokhoz. A sűrű közösségi magok és a hosszú nyúlványok jelenlétét az 5. ábrán két valós példán mutatjuk be.

Ebben a fejezetben két önkényesen választott klaszterező algoritmust mutatunk be, a klikk perkolációt (Derényi et al., 2005) és a saját heurisztikáinkat (Kurucz et al. 2008) alkalmazó hierarchikus spektrál módszereit. Megvizsgáljuk a fellelt közösségek az algoritmus paramétereitől való függőségét és a kapcsolatok súlyozásainak lehetőségeit. Megmutatjuk, hogy a sűrű közösségek és hosszú nyúlványok léte mennyire megnehezíti a klaszterezés feladatát, és a spektrál esetben olyan heurisztikákat mutatunk, amelyek megszüntetik ezek torzító hatását.

Klikk perkoláció: egy friss klaszterező algoritmus

A klikk perkoláció (Derényi et al., 2005) alapötlete az olyan k résztvevős csoportok, ún. k-klikkek vizsgálata, amelyekben minden részt vevő pár között előfordul hívás. Ezek a magok az elképzelhető legsűrűbben összekapcsolt kis közösségek. A módszer az ilyen k-klikkekből növeszt lépésről lépésre növekvő közösségeket úgy, hogy minden lépésben valamelyik k-klikk egyik

résztvevőjét megpróbálja egy, a már feltárt közösségen kívüli, de a maradék k-1 résztvevővel újra k-klikket alkotó elemmel lecserélni. A már tovább nem bővíthető, esetlegesen egymással átfedő közösségek képezik a végeredményt.

A következőkben a fent vázolt módszer a 6. ábra nagy hálózatán, illetve általában olyan nagyméretű hálózatokon való viselkedését mutatjuk be, amelyekben sok sűrű kis közösséget hosszú nyúlványok kötnek össze. A 6. ábra felső táblázatában láthatjuk, hogy a klikkek száma rendkívül magas, és az ezeket kezelő algoritmus megvalósítása így nem egyszerű. A legnagyobb közösség mérete 3-klikkek esetében szintén a klikkek nagy száma miatt óriási. Ugyanakkor a közösségek száma áttekinthetetlenül nagy – ez még 5-klikkek esetén is igaz. Ahogy k növekszik, ugyanakkor csökken a felhasználható klikkek száma, és egyre kevesebb résztvevőt választunk bele egyáltalán valamelyik közösségbe. A nyúlványokba tartozó, sűrű magoktól távolabb eső elemekkel nem tudunk igazán mit kezdeni. Az ábra alsó részén láthatjuk, hogy a közösségek túlnyomó többsége rendkívül kicsi, azaz nagyon sok a nagyon sűrű kis csoport.

Spektrál klaszterezés

A spektrál klaszterezés olyan heurisztikák gyűjtőneve, melyek a hálózat elemeit az első főirányokra vetítik, és a kapott alacsony dimenziós térben sűrűségalapon keresnek csoportokat. A legjobban működő módszerek, amint azt a szakirodalom részletesebb elemzésével és kísérletekkel megmutattuk (Kurucz et al., 2008), egy viszonylag magas, pár tízdimenziós térbe vetíti a hálózat résztvevőit, és utána tíz körüli darab csoportot próbál képezni. Siker esetén a kapott csoportokon a módszer megismételhető, így egy klaszterhierarchia áll elő.

A spektrál klaszterezés is érzékeny a sűrű magok és hosszú nyúlványok problémájára. Igen gyakran kimenetként a tagok sűrű magokba, illetve nyúlványokba tartozás szerinti kettéosztását kapjuk. A sűrű magok legalább összefüggő csoportot alkotnak, a másik oldal azonban egymástól izolált apró nyúlványokra bomlik. Ráadásul ezek a darabkák nagyon erősen kötődnek a másik oldal bizonyos részeihez, egy utófeldolgozási lépésben tehát ezeket egyenként áthelyezhetjük a túloldalra, amíg végül visszakapjuk az eredeti teljes adathalmazt mint egyetlen klasztert.

Az általunk javasolt módszer lényege, hogy a vetítési dimenziók számát mindaddig növeljük, amíg a nem összefüggő részek szétosztása után kapott legkisebb és legnagyobb össze­függő klaszter méreteinek aránya egy küszöb alá nem kerül. Nagyon nehezen bontható hálózatok esetében a sűrű részek és a nyúlványok összevonását is alkalmazhatjuk, például Budapest sűrű szociális kapcsolatrendszerét ilyen módon lehet szétbogozni. Megjegyezzük, hogy a dimenziók számának növelése nagyon megnöveli a számításigényt, tehát gondos egyensúlyra kell törekednünk a paraméterek megválasztásakor.

A 7. ábrán láthatók a spektrál particioná­lással kapott eredményeink. Megfigyelhető, hogy a küszöb szigorításával egyre nagyobbá válik a legnagyobb, tovább nem bontható kö­zösség mérete. Ez a nagy közösség azonban a kapcsolatokkal túl sűrűn ellátott főváros következménye, és Budapestet elhagyva már jól kezelhető méreteket látunk. Az ábra alsó részén a kisebb közösségek darabszámának eloszlását is láthatjuk, amelyre rávetítettük az 1. ábra településméret-eloszlását is. Itt a 2 és 6 közötti küszöbértékek választása a településméretekhez nagyon hasonló közösség-méreteket eredményez.

Lemorzsolódás
és hálózaton alapuló kategorizáció

Utolsó alkalmazásunkban megmutatjuk, hogyan aknázható ki a hálózati kapcsolatokban rejlő információ a churn, azaz az előfizetés lemondásának előrejelzésében. Kísérletünket a kis adathalmazon folytatjuk olyan módon, hogy nyolc hónap tanító időszak után négy hónappal előre, a 12. hónapra adjuk az előrejelzést. Hipotézisünk szerint, amelyet méréseink igazolnak, az egymással kapcsolatban álló előfizetők befolyásolják egymás véle­ményét, és csoportokban együtt jutnak elhatározásra, hogy előfizetésüket lemondják.

A következőkben bemutatott módszer az ún. félig felügyelt osztályozás (Zhu, 2005) csoportjába tartozik, amelyben az ismeretlen, felcímkézetlen egyedek tulajdonságait is hasznosítjuk a modellépítés során. Ebben a csoportban található az általunk alkalmazott hálózati elemek osztályozása, amely iteratív tanulási folyamat. Kezdőlépésként a meglevő forgalmi, előfizetési és szociodemográfiai adatok alapján meghatározzuk minden résztvevő churn értékét. Ezután megnézzük minden előfizető esetén a vele kapcsolatban álló többi előfizető előrejelzett értékét és ezekből újabb jellemzőket gyártunk, amelyekkel kibővítve, akár több iterációban folytatjuk a modellépítést. Többféle jellemzőt állítunk elő, amely a szomszédok churn előrejelzésének c átlagán, illetve kapcsolati erősségekkel súlyozott c’ átlagán alapulnak. Ezek közül a c’ olyan változata bizonyul legjobbnak, amely a kevés kapcsolattal rendelkező csúcsokon „regularizációt” alkalmaz, azaz a semleges átlag felé tolja el a jellemző értékét.

A tulajdonságok hálózati kapcsolatokon keresztül történő továbbítása a churn előrejelzés mellett számos további alkalmazással bír, amelyek között megtalálható az internet dokumentumainak osztályozása és a bizalom vagy bizalmatlanság megerősítése. Talán a legfontosabb, a módszert egyik elsőként alkalmazó terület a web spamszűrés, azaz a kizárólag a keresőrendszerek találati rangsorának manipulálására létrehozott, értelmetlen vagy kifejezetten megtévesztő tartalmak fellelése (Benczúr, 2008). A web spam esetében a továbbítás például azon alapul, hogy becsületes tartalom elvétve hivatkozik spamre, míg a spam oldalakra azok egymást erősítő szándékai következtében mindig nagyon sok spam hivatkozik.
A klasszifikációt kísérletünkben a Weka ún. cost sensitive C4.5 módszerével végeztük a különböző típusú hívások (helyi, távolsági, csúcsidő, alternatív szolgáltatón keresztüli) összértékeivel mint jellemzőkkel. Az alap klasszifikátorhoz képest egy lépésben 25% javulást eredményezett a hálózati információk kihasználása, a második iteráció azonban már rontott a minőségen. Érdekességként megjegyezzük, hogy a c’ érték számításakor nem feltétlenül a hívások darabszámát vagy idejét érdemes használni, hanem két ügyfél kapcsolati erősségét inkább a közös hívottak számával, vagy két hívott csoport által meghatározott vektorok által bezárt szöggel érdemes súlyozni.
 

Kulcsszavak: szociális hálózatok, klaszteranalízis
 

IRODALOM

Albert Réka – Jeon, H. – Barabási A-L. (1999): Diameter of the World Wide Web. Nature. 401, 130–131.

Barabási Albert-László (2002): Linked. Perseus Publishing

Barabási Albert-László – Albert, R. – Jeong, H. (2000): Scalefree Characteristics of Random Networks: The Topology of the Word-Wide Web. Physica A. 281, 69–77.

Benczúr András A. – Siklósi D. – Szabó J. – Bíró I. – Fekete Z. – Kurucz M. –Pereszlényi A. – Rácz S. – Szabó A. (2008): Web Spam: A Survey with Vision for the Archivist. In: Proceedings of the International Web Archiving Workshop. WEBCÍM >

Derényi Imre – Palla G. – Vicsek T. (2005): Clique Percolation in Random Networks. Physical Review Letters. 94, 49–60. WEBCÍM >

Kleinberg, Jon (2000): Navigation in a Small World. Nature. 406, 845.

Kurucz M. – Siklósi D. – Lukács L. – Benczúr A. A. – Csalogány K. – Lukács A. (2008): Telephone Call Network Data Mining: A Survey with Experiments. In: Handbook of Large-Scale Random Networks. Springer Verlag in conjunction with the Bolyai Mathematical Society of Budapest

Milgram, Stanley (1967): The Small World Problem. Psychology Today. 2, 1, 60–67.

Watts, Duncan J. – Strogatz Steven H. (1998): Collective Dynamics of Small-World’ Networks. Nature. 393, 6684, 440–442.

Zhu, Xiaojin (2005): Semi-supervised Learning Literature Survey. Technical Report. 1530, Computer Sciences, University of Wisconsin-Madison WEBCÍM >

WebSpamChallenge: \texttt{http://webspam.lip6.fr/}

Weka nyílt forráskódú gépi tanulási eszköz: WEBCÍM >
 

* A TEXTREND NKFP-07-A2 és az OTKA NK 72845 támogatásával. <