Gráfok vizualizációja
Jeszenszky Péter
[email protected] Debreceni Egyetem, Informatikai Kar
Vizualizációs eszközök ●
●
Néhány eszköz: ●
Gephi http://gephi.org/
●
Graphviz http://www.graphviz.org/
●
NodeXL http://nodexl.codeplex.com/
●
SONIVIS http://sonivis.org/
●
Tulip http://tulip.labri.fr/
●
yEd http://www.yworks.com/yed/
●
…
Egy hasznos lista: Social network analysis software http://en.wikipedia.org/wiki/Social_network_analysis_software 2
Graphviz (1) ●
Története az 1980-as évek végéig nyúlik vissza vissza (AT&T Research Labs)
●
Megvalósítás: C (kb. 216 000 programsor)
●
Platform: Linux, Mac, Windows
●
2000 óta nyílt forrású
●
Licenc: Common Public License ●
●
Az IBM nem GNU GPL kompatibilis szabad szoftver licence
Állományformátum: DOT 3
Graphviz (2) ●
●
Eszközök: ●
Rajzolás: circo, dot, fdp, neato, twopi, sfdp
●
Generálás: gvgen
●
Előfeldolgozás: unflatten
●
Manipulálás: prune
●
…
Támogatott állományformátumok rajzolásnál: JPEG, PDF, PNG, PostScript, SVG, … 4
Graphviz: példa graph graph {{ Budapest[shape="diamond", Budapest[shape="diamond", style="rounded"]; style="rounded"]; Debrecen[shape="box",style="rounded"]; Debrecen[shape="box",style="rounded"]; Budapest--Cegléd Budapest--Cegléd [label="73km", [label="73km", color="red", color="red", style="bold,dashed"]; style="bold,dashed"]; Budapest--Hatvan Budapest--Hatvan [label="67km"]; [label="67km"]; Budapest--Újszász Budapest--Újszász [label="84km"]; [label="84km"]; Cegléd--Szolnok Cegléd--Szolnok [label="27km", [label="27km", color="red", color="red", style="bold,dashed"]; style="bold,dashed"]; Füzesabony--Eger Füzesabony--Eger [label="17km"]; [label="17km"]; Füzesabony--Tiszafüred Füzesabony--Tiszafüred [label="30km"]; [label="30km"]; Füzesabony--Miskolc Füzesabony--Miskolc [label="57km"]; [label="57km"]; Hatvan--Újszász Hatvan--Újszász [label="52km"]; [label="52km"]; Hatvan--Füzesabony Hatvan--Füzesabony [label="58km"]; [label="58km"]; Karcag--Debrecen Karcag--Debrecen [label="59km", [label="59km", color="red", color="red", style="bold,dashed"]; style="bold,dashed"]; Miskolc--Nyíregyháza Miskolc--Nyíregyháza [label="88km"]; [label="88km"]; Nyíregyháza--Debrecen Nyíregyháza--Debrecen [label="49km"]; [label="49km"]; Tiszafüred--Debrecen Tiszafüred--Debrecen [label="73km"]; [label="73km"]; Tiszafüred--Karcag [label="45km"]; Tiszafüred--Karcag [label="45km"]; Szolnok--Karcag Szolnok--Karcag [label="62km", [label="62km", color="red", color="red", style="bold,dashed"]; style="bold,dashed"]; Szolnok--Újszász [label="16km"]; Szolnok--Újszász [label="16km"]; }} 5
Graphviz: példa
6
Graphviz: példa
7
Néhány elterjedtebb formátum ●
DOT (Graphviz) http://www.graphviz.org/ ●
●
GEXF (Graph Exchange XML Format) http://gexf.net/ ●
●
XML formátum (RNC, RNG, XSD)
GraphML http://graphml.graphdrawing.org/ ●
●
Nem XML szöveges formátum
XML formátum (XSD)
Graph Modelling Language (GML) ●
Nem XML szöveges formátum 8
GEXF (Graph Exchange XML Format) ●
●
A Gephi projektben fejlesztett nyílt XML formátum gráfok ábrázolásához Fontosabb jellemzők: ●
●
Lehetővé teszi strukturált adatok tárolását a csúcsokhoz és élekhez
●
Hierarchikus gráfok ábrázolása
●
Dinamikus gráfok támogatása
●
Kiterjeszthetőség
XML sémák (RNC, RNG, XSD): http://gexf.net/format/schema.html (az akutális verzió az 1.2draft számú)
9
GEXF: támogatás ●
Kapcsolódó szabad és nyílt forrású szoftverek: ●
Gephi (szerkesztés, elemzés, vizualizáció) http://gephi.org/
●
LibGEXF (C++ programkönyvtár) http://gexf.net/lib/
●
gexf4j (Java programkönyvtár) http://gexf.net/gexf4j/
●
GEXF Explorer (SWF megjelenítő) http://gexf.net/explorer/
10
GEXF: Hello, világ! példa
version="1.2"> <meta <meta lastmodifieddate="2011-01-17"> lastmodifieddate="2011-01-17"> me me <description>Hello, <description>Hello, world! world! example example defaultedgetype="directed"> <nodes> <nodes> <node <node id="a" id="a" label="Hello"/> label="Hello"/> <node <node id="b" id="b" label="World"/> label="World"/> <edges> <edges> <edge <edge id="1" id="1" source="a" source="a" target="b"/> target="b"/>
11
GEXF: vegyes gráfok ●
Egy gráf tartalmazhat irányított, irányítatlan és kétirányú éleket is:
version="1.2"> <meta <meta lastmodifieddate="2011-01-17"> lastmodifieddate="2011-01-17"> me me <description>Mixed <description>Mixed graph graph example example <nodes> <nodes> <node <node id="a"/> id="a"/> <node id="b"/> <node id="b"/> <node <node id="c"/> id="c"/> <node <node id="d"/> id="d"/> <edges> <edges> <edge <edge id="1" id="1" source="a" source="a" target="b" target="b" type="directed"/> type="directed"/> <edge <edge id="2" id="2" source="a" source="a" target="c" target="c" type="undirected"/> type="undirected"/> <edge <edge id="3" id="3" source="a" source="a" target="d" target="d" type="mutual"/> type="mutual"/>
12
GEXF: attribútumok (1) ●
Adatok tárolása csúcsokhoz és élekhez:
version="1.2"> class="node"> type="boolean"> <default>true <default>true type="string"> low|medium|high low|medium|high <default>medium <default>medium class="edge"> type="double"/> …… 13
GEXF: attribútumok (2) ●
Adatok tárolása csúcsokhoz és élekhez (folytatás):
…… <nodes> <nodes> <node <node id="a"> id="a"> value="high"/> …… <edges> <edges> <edge <edge id="1" id="1" source="a" source="a" target="a"> target="a"> value="1E-5"/> …… 14
GEXF: VIZ modul (1) ●
Csúcsok és élek megjelenésének vezérlése (szín, pozíció, méret, alak, vonalvastagság):
version="1.2"> defaultedgetype="directed"> <nodes> <nodes> <node <node id="r" id="r" label="Red"> label="Red"> b="0"/> z="0"/> <node <node id="g" id="g" label="Green"> label="Green"> b="0"/> z="0"/> <node <node id="b" id="b" label="Blue"> label="Blue"> b="255"/> z="0"/> <node <node id="y" id="y" label="Yellow"> label="Yellow"> b="0"/> z="0"/>
15
GEXF: VIZ modul (2) ●
Csúcsok és élek megjelenésének vezérlése (szín, pozíció, méret, alak, vonalvastagság): …… <edges> <edges> <edge <edge id="1" id="1" source="r" source="r" target="g"> target="g"> value="2.0"/> <edge <edge id="2" id="2" source="g" source="g" target="b"/> target="b"/> <edge <edge id="3" id="3" source="b" source="b" target="y"/> target="y"/> <edge <edge id="4" id="4" source="y" source="y" target="r"> target="r"> value="dotted"/> b="255"/> 16
GEXF: dinamikus gráfok (1) ●
Időben változó topológia:
version="1.2"> start="2011-01-15"> <nodes> <nodes> <node <node id="a"/> id="a"/> <node <node id="b"/> id="b"/> <node <node id="c"/> id="c"/> <node <node id="d" id="d" start="2011-01-20"/> start="2011-01-20"/> <edges> <edges> <edge <edge id="1" id="1" source="a" source="a" target="b" target="b" start="2011-01-17"/> start="2011-01-17"/> <edge <edge id="2" id="2" source="b" source="b" target="c" target="c" start="2011-01-18"/> start="2011-01-18"/> <edge <edge id="3" id="3" source="c" source="c" target="a" target="a" start="2011-01-19"/> start="2011-01-19"/> <edge <edge id="4" id="4" source="a" source="a" target="d" target="d" start="2011-01-20"/> start="2011-01-20"/> <edge <edge id="5" id="5" source="b" source="b" target="d" target="d" start="2011-01-20"/> start="2011-01-20"/> <edge <edge id="6" id="6" source="c" source="c" target="d" target="d" start="2011-01-20"/> start="2011-01-20"/> 17
GEXF: dinamikus gráfok (2) ●
Időben változó topológia: több időintervallumban létező csúcsok és élek („spells”) <nodes> <nodes> …… <node <node id="f"> id="f"> <spells> <spells> <spell <spell start="2011-01-17" start="2011-01-17" end="2011-01-20"/> end="2011-01-20"/> <spell <spell start="2011-01-25" start="2011-01-25" end="2011-01-28"/> end="2011-01-28"/> <spell start="2011-02-01"/> <spell start="2011-02-01"/> <edges> <edges> …… <edge <edge id="10" id="10" source="f" source="f" target="g"> target="g"> <spells> <spells> <spell <spell start="2011-01-17" start="2011-01-17" end="2011-01-29"/> end="2011-01-29"/> <spell <spell start="2011-02-01"/> start="2011-02-01"/>
18
GEXF: dinamikus gráfok (3) ●
Időben változó adatok:
mode="dynamic"> type="string"> low|medium|high low|medium|high <default>medium <default>medium <nodes> <nodes> …… <node <node id="g"> id="g">
end="2011-01-18"/> start="2011-01-20"/>
19
Gephi (1) ●
Platform gráfok megjelenítéséhez és vizsgálatához ●
Mottó: „Photoshop™ for graphs”
●
Szabad és nyílt forrású (GNU AGPLv3)
●
Célplatform: Windows, Linux, Mac OS X
●
Megvalósítás: Java, NetBeans Platform
●
Rendszerkövetelmények: Java SE 6, OpenGL 1.2
●
Natív formátum: GEXF
●
Importálás: CSV, DOT, GML, GraphML, …
●
Ábra exportálása: PDF, SVG
20
Gephi (2) ●
●
Fejlesztés koordinálása: Gephi Consortium (nonprofit szervezet) Elismerés: 2010 Duke's Choice Awards (az Innovative Technical Data Visualization kategória győztese) http://www.java.com/dukeschoice/ ●
„The Duke's Choice Awards celebrate extreme innovation in the world of Java technology and are granted to the most innovative projects using the Java platform”
21
Gephi: jellemzők ●
●
●
●
Egyszerűen használható felhasználói felület Alkalmas nagyméretű gráfok kezeléséhez (akár 50 000 csúcs és 500 000 él) Számos beépített elrendezési algoritmus Statisztikák és metrikák számítása (PageRank, HITS, klaszterezési együttható, centralitási mérőszámok, …): felhasználható a megjelenés testreszabásához is
●
Beépített klaszterezési eljárások
●
Dinamikus és hierarchikus gráfok kezelése
●
Moduláris felépítés: bővítmények segítségével új funkciók adhatók a programhoz (jelenleg kb. 100 bővítmény elérhető)
22
Gráfok létrehozása ●
●
Facebook szociális háló: netvizz Facebook alkalmazás a szociális hálónk exportálásához http://apps.facebook.com/netvizz/ Levelezési kapcsolatok gráfja EML állományokból (SpigotEmail bővítmény)
●
Twitter követés gráfja (SpigotTwitter bővítmény)
●
Véletlen gráfok
●
●
Watts-Strogatz Small World
●
Gilbert modell: G(n,p)
WWW böngészés gráfja (HTTP Graph bővítmény)23
Facebook szociális háló exportálása (1) ●
A Facebook-ra bejelentkezés után keressük meg a netvizz alkalmazást
24
Facebook szociális háló exportálása (2) ●
A telepítés során engedélyezzük az alkalmazásnak a hozzáférést az adatlapunkhoz:
25
Facebook szociális háló exportálása (3) ●
Adjuk meg, hogy milyen adatok kerüljenek a profilokból exportálásra, majd kövessük a nyíllal megjelölt linket!
26
Facebook szociális háló exportálása (4) ●
Mentsük le a nyíllal megjelölt linkről az eredményül kapott GML állományt!
27
Facebook szociális háló vizsgálata (1) ●
Töltsük be a Gephi programba a netvizz által létrehozott GML állományt (File → Open…)! ●
A gráf típusaként (Graph Type) válasszunk irányítatlant (Undirected)
28
Facebook szociális háló vizsgálata (2) ●
Egy ilyen gráfot kapunk ●
Ennek megjelenését fogjuk szebbé tenni –
Célunk, hogy a csúcsok mérete legyen arányos a Betweenness centralitási mérőszámmal, a színek pedig jelezzék az ismerősök nemét
29
Facebook szociális háló vizsgálata (3) ●
Hívjuk elő a statisztikákat számoló panelt (Window Statistics), majd kattintsunk az Avarage Path Length mellett a Run gombra!
30
Facebook szociális háló vizsgálata (4) ●
A megjelenő panelen kérjük a centralitási mérőszámok normálását!
31
Facebook szociális háló vizsgálata (5) ●
Az eredmény (megtekintés után bezárható az ablak):
32
Facebook szociális háló vizsgálata (6) ●
Hívjuk elő a Ranking panelt (Window → Ranking), majd a Choose a rank parameter beállításnál válasszuk a Betweenness Centrality-t!
33
Facebook szociális háló vizsgálata (7) ●
A gyémánt ikonra kattintva érhetjük el, hogy a megjelenítésnél a csúcsok mérete a kiválasztott mérőszámmal legyen arányos A Max size mezőben írható elő a csúcsok maximálás mérete Válasszuk például az 50 értéket, majd kattintsunk az Apply gombra!
34
Facebook szociális háló vizsgálata (8) ●
Az eredmény:
35
Facebook szociális háló vizsgálata (9) ●
Következő lépésben el fogjuk érni, hogy különböző színek ábrázolják a nemeket, ehhez hívjuk elő a Partition panelt (Window → Partition) ●
Az ismerősök neme akkor áll rendelkezésre, ha az adatok exportálásánál kértük a nem (sex) tárolását
36
Facebook szociális háló vizsgálata (10) ●
Kattintsunk a zöld ikonra, majd a mellette megjelenő Choose a partition parameter alatt válasszuk ki a nemet (sex)!
37
Facebook szociális háló vizsgálata (11) ●
Az Apply gombra kattintva láthatjuk a nemek arányát Szokott módon null jelöli a hiányzó értéket
38
Facebook szociális háló vizsgálata (12) ●
Az eredmény:
39
Facebook szociális háló vizsgálata (13) ●
Alkalmazzunk egy Layout algoritmust a gráfra, amely át fogja rendezni a csúcsokat (Window → Layout)
A Choose a Layout alatt válasszuk a Force Atlas elrendezést!
40
Facebook szociális háló vizsgálata (14) ●
Adjuk meg a Layout algoritmus paramétereit! Módosítsuk a Repulsion Strenght paraméter értékét például 20 000-re, a többi paraméternél fogadjuk el az alapértelmezést A Run gombra kattintva elindul az algoritmus, ezután a Stop gombbal bármikor megszakítható a futás
41
Facebook szociális háló vizsgálata (15) ●
Az eredmény:
42
Facebook szociális háló vizsgálata (16) ●
Végül jelenítsük meg az ismerősök nevét is, ehhez a megjelölt T ikonra kell kattintani az ablak alján
43
44
