Hálózatok dinamikája Klasztervizsgálat, keresés hálózatokban 3.3. projekt Lukács András
[email protected]
Eötvös Loránd Tudományegyetem Számítógéptudományi Tanszék
econet.hu Informatikai Nyrt.
nagy és heterogén hálózatok = komplex információ
Témák és vezető kutatók Hálózati kódolás Információáramlás és fogyasztás vizsgálata Lovász László
Szociális hálózatok Nagyméretű hálózatokat leíró és klaszterező algoritmusok kutatása és fejlesztése
Kapcsolati adattárházak Benczúr A. András
Keresés nagyméretű hálózatokban
Lukács András
Hálózati kódolás Lehet-e és hogyan növelni egy hálózat áteresztőképességét, ha az információtovábbításnál a köztes csomópontok kódolást is végezhetünk - változik az információ/adatformátum? A lehetséges üzeneteket, információcsomagokat számokkal, vektorokkal kódoljuk. a2
…
Lineáris műveletek:
a1
ak
Σλiai
Hálózati kódolás Lehet-e és hogyan növelni egy hálózat áteresztőképességét, ha az információtovábbításnál a köztes csomópontok kódolást is végezhetünk - változik az információ/adatformátum? Li – Li sejtés: irányítatlan hálózatokon, több forrás – több cél esetében hálózati kódolás nem tud javítani a maximálisan elérhető információáramláson. Mennyiben általánosítható az elmélet matroid címkézésű folyamok esetén? Milyen matroid-osztályok esetén segít a hálózati kódolás?
Szociális hálózatok Alapok • humán közösségek típusai: család/kreatív (5-8), …, szociális (25-150), politikai (1000-) • a p2p telekommunikációs eszközök használata a szociálisnál nem nagyobb közösségek „kurkászásához” járul hozzá Módszer • több mint 2 millió felhasználó 8 hónapnyi telefonálási naplóadatából hálózatot/gráfot építünk • a kialakított hálózatból klikkperkolációs módszerrel (Palla at al. 2005) kinyerjük a közösségeket
Humán közösségek méretei 100000
gyakoriság
10000
1000
100
10
1 0.5
1
1.5
2
2.5
klaszterméret logaritmusa Dunbar-határ, szociális közösségek maximális mérete (Dunbar 1993): ~150
3
3.5
4
Szociális hálózatok Alapok • humán közösségek típusai: család/kreatív (5-8), …, szociális (25-150), politikai (1000-) • a p2p telekommunikációs eszközök használata a szociálisnál nem nagyobb közösségek „kurkászásához” járul hozzá Itt veszthetjük/veszítjük a legtöbb információt!!
Módszer • több mint 2 millió felhasználó 8 hónapnyi telefonálási naplóadatából hálózatot/gráfot építünk • a kialakított hálózatból klikkperkolációs módszerrel (Palla at al. 2005) kinyerjük a közösségeket
Hogyan kell kapcsolati naplókból valódi szociális információkat tartalmazó hálózatot építeni?
Közösségek kinyerése • Három különböző hálózaton, de ugyanazon módszerrel (klikkperkoláció) végzett klaszterezés minőségén keresztül mutatom be a nyers hálózat átsúlyozásának fontosságát. • A kapcsolatok új súlyaihoz a nyers környezetek kölcsönös viszonyait mérjük, majd a gyenge kapcsolatokat elvetjük. klikk méret: 5 felhasználók: 2,1 millió kapcsolatok száma (millió)
irányítatlan átsúlyozott, átsúlyozott, átsúlyozott, alapgráf küszöb: 0,03 küszöb: 0,05 küszöb: 0,1 30
26,4
18,3
10,5
klaszterezett felh. aránya
33%
75%
66%
47%
maximális klaszter méret
6721
13482
486
164
1,7
2,4
1,9
1,4
átlagos klaszterszám @felh.
+ hatékonyabb algoritmus a klikkperkolációs feladatra
Humán közösségek méretei 100000 Eredeti hálózat Átsúlyozással, küszöb: 0.03
10000
gyakoriság
Átsúlyozással, küszöb: 0.05 Átsúlyozással, küszöb: 0.10
1000
100
10
1 0.5
1
1.5
2
2.5
klaszterméret logaritmusa Dunbar-határ, szociális közösségek maximális mérete (Dunbar 1993): ~150
3
3.5
4
Kapcsolati adattárházak Célok • céges/intézményes adatvagyon újszerű felhasználása: az üzleti logika hű leképezése egy kapcsolati hálózatba • a kapcsolati adattárház akár heterogén adattáblákból történő (közel) automatikus felépítése • felhasználóbarát keresés és böngészés a hálózatban • hasonló entitások, ill. hálózati mintázatok felismerése Előképek • World Wide Web ☺ • közösségi webportálok (iWiW, Orkut, Flickr stb.) • Analyst’s Notebook (bűnüldözési szoftver) Kapcsolodó projektek • ASTOR (Működési kockázatok csökkentése) • i-TRACS (Counter-Terrorism identification and tracking system)
Kliens-szerver architektúra GUI
Java RMI / távoli metódus hívás
kliensoldali absztrakt adatelérési inteface
ssh tunnel / port forwarding
DataProvider.java
java - C++ konverter
NativeServer.java
JNI
szerver oldali adatelérési inteface dataprovider.c++
kapcsolati adatbázis és motor
Kapcsolati adatbázis és motor kereséseket kiszolgáló motor
adatbázis (csv fájlok és indexek)
indexelés kialakítása (Berkeley DB)
entitás kinyerés id kiosztás tábla gyártás gráf gyártás
üzleti logika/ konfigurációs adatok (XML)
heterogén adattáblák
Adatmodell, adatleképezés feszítő fa rekord
Irodalom R. Ahlswede, N. Cai, S. R. Li, and R. W. Yeung (2000) Network information flow, IEEE Transactions on Information Theory 46, 1204-1216. Z. Li and B. Li. (2004) Network coding in undirected networks, in Proc. CISS 2004. R.I.M. Dunbar (1993) Coevolution of Neocortical Size, Group Size and Language in Humans, Behavioural and Brain Sciences 16, 681–735. G. Palla, I. Derényi, I. Farkas, and T. Vicsek (2005) Uncovering the overlapping community structure of complex networks in nature and society, Nature 435, 814-818.
Hasznosítás, termékesítés
