Blogoszféra - a központok felkutatása

Az Udacity nevű online-egyetemen futó algoritmika kurzuson éppen a közösségi hálózatokról van szó, illetve a téma kapcsán a gráfokról -- isteni, csak ajánlani tudom!

A kurzuson bevezették a csomósodási együttható (clustering coefficient) fogalmát is, amely azt mutatja meg, hogy egy gráf adott csúcsa mennyire foglal el központi helyet a hálózatban. A kiszámításához két dolgot kell tudni:

• egy blogra hány oldalról mutat link (legyen LINK)
• a fenti oldalak között hány link van (legyen INTERLINK)

Az együttható kiszámítása a következő képlettel történik:

2*INTERLINK / (LINK*(LINK-1))

Minnél sűrűbb a hivatkozó oldalak közti linkhálózat, ez az érték annál nagyobb lesz.

A csomósodási együttható segítségével meg tudjuk mondani, mely blogok körül csomósodnak a linkek -- ezek az oldalak vélhetően hasonló témakörben publikálnak, hiszen különben nem linkelnének egymásra. Ezzel ellentétben, egy nagyon népszerű, sok befelé mutató linkkel rendelkező blognál ez az érték valószínűleg kisebb, hisz a hivatkozók egymásra ritkábban hivatkoznak.

A gyakorlatban több problémával is meg kell küzdeni: először is, az adatok rossz minősége itt már komoly probléma -- az index egymást körbehivatkozó foci-blogjai nagyon csúnyán eltorzítják az ábrát. Ezen kívül, komolyan el kell gondolkodni azon is, hogy mit számolunk: a befelé vagy a kifelé mutató linkeket, esetleg mind a kettőt? Végül, egy kicsi hálózatnak jellemzően nagyobb lesz a csomósodási együtthatója, ezért valamilyen határt is fel kell állítani -- az itt látható ábrákon 5 hivatkozásnál kevesebbel rendelkező blogok nem válhattak 'központokká'.

 

1. ábra

 

Az 1. ábrán kiválóan látható, hogy a boros blogok szépen kirajzolódó hálózatokba szerveződnek (a hálózat központja mindig színes hátterű, és az adott hálózat élei is ilyen színűek)

 Itt az látható, hogy a hálózatok átfedik egymást -- egy csúcs több hálózatnak is tagja lehet, hiszen bármely szomszédból lehet "központ", ha elég magas a csomósodási együtthatója.

Itt az index focis blogjai egymásra települt hálózatokat alkotnak, ezért a sok párhuzamos él. Értelmezhetetlen, de legalább szép:)

Blogoszféra: scatter plot

Szép a gráf, de áttekinthetetlen. Mennyivel szebb egy scatter plot (hogy van magyarul?), amelyen minden pont egy linket képvisel; az X koordináta az mondja meg, honnan, az Y pedig, hogy hová mutat (ez ugyanaz, mintha felírnánk a gráfot mátrix-alakban).

A tengelyek mentén a blogokra mutató linkek összessége (kékkel, az Y mentén), illetve a blogokon található hivatkozások száma (pirossal, X mentén) látható. A legnépszerűbb oldalakat fel is írtam az ábrára (kékkel), mint ahogy a legtöbb oldalra mutató blogok nevét is (pirossal). Ebből látszik, hogy a népszerű oldalak nem feltétlenül hivatkoznak sokat (itt persze közrejátszik az adatok minősége is, ugyanis teljes szöveget veszünk, olvasói kommentekkel is, amelyekben sok link lehet).

Érdekes kérdés, vajon ezek az adatok alapján csoportokba lehet-e rendezni a blogokat, és vajon ezek a csoportok kirajzolnak-e valamilyen értelmes mintát? (a gráfot nézegetve látható valamiféle mintázat, pl. a politikai blogok egymáshoz közel vannak). Ehhez valamilyen clustering-algoritmust kell alkalmazni, de mielőtt ezzel megpróbálkoznék, még át kell olvasnom egy-két dolgot;)