A közösségi hálózatok számítógépes feldogozása során alapvető fontosságú a gráfelmélet. A matematikának ez az ága halmazok egymással kapcsolatban álló elemeivel, illetve az általuk alkotott hálózatokkal foglalkozik. Például a Facebookon a barátok közösségei gráfokat alkotnak, vagy egy Google-keresés során is egy gráfalgoritmus kimenetét használja fel a keresőmotor. Számos feladat, amelyet egy átlagos internetező naponta elvégez modellezhető gráf-problémaként.

Az World Wide Web lényegéből fakadóan maga is egy óriási gráf: amíg egy weblap nem kapcsolódik linkeken keresztül más oldalakhoz, addig gyakorlatilag nem létezik, hiszen senki sem talál rá. Ugyanez elmondható a web kisebb szegleteiről, például a magyar blogokról vagy a Twitter-felhasználókról. És míg az egész webbel kapcsolatban értelmezhetetlen az a kérdés, hogy melyik a „legfontosabb” vagy a „legközpontibb” oldal (már csak mérete és differenciáltsága miatt is), kisebb hálózatoknál ezek nagyon is fontos kérdések. Például a magyar blogoszférával kapcsolatban az effajta kérdések feltevése és megválaszolása már indokolt, hiszen az itt megjelenő tartalmaknak akár komoly PR és marketing-vonzata is lehet (gondoljunk csak a például fogyasztóvédelmi vagy a sokak által olvasott politikai blogokra). A legnépszerűbb blog megtalálásakor először azt kell tisztáznunk, hogy pontosan mit is keresünk. Azt az oldalt, amelyet a legtöbben olvasnak? Vagy talán azt, amelyre a legtöbben hivatkoznak? Esetleg azt a bloggert, akinek a véleménye fontos, egy véleményvezért? Vagy a blogoszféra központi blogjait? 

Az oldal az ajánló után folytatódik...

A véleményvezérek a blogoszférában azok a blogok, blogbejegyzések, amelyeket sokat átvesznek (hivatkoznak). Ez nem is jelenti feltétlenül azt, hogy a véleményvezérek írásait sokan olvassák – úgy is lehet egy blogger fontos tagja a blogszférának, hogy az ő blogját csak olyan bloggerek olvassák és hivatkozzák, akiket azonban már nagy tömegek követnek (feltételezve persze, hogy az  bloggerek nem össze-vissza linkelnek, hanem az adott íráshoz kapcsolódó tartalmakat linkelnek). Pontosan ugyanezen az elven működik a Google PageRank algoritmusa.

Oldalak súlyozása rájuk mutató linkek száma szerint
(Forrás: wikimedia commons / 345Kai)

A fenti ábra egy 11 oldalból álló hálózat. Minden oldal „fontosságát” a benne szereplő érték mutatja. Figyeljük meg a C oldalt –  annak ellenére a második legfontosabb, hogy csak egy hivatkozás mutat rá. Ezt a hivatkozást azonban a legnépszerűbb oldaltól kapja). Kicsit más problémával állunk szemben, ha egy hálózat  „legközpontibb” oldalát keressük. Egy ilyen oldal egymástól tematikusan távol álló blogokat köt össze, „hídként” funkcionál. Ugyanilyen hídként funkcionálnak az olyan felhasználók a közösségi hálózatokban, akiknek kiterjedt, sokféle embert tartalmazó baráti köre van. Egy gráfban azok az elemek ezek, amelyekből a legkevesebb lépéssel elérhető az összes másik elem. A Facebookon ezek azok az ismerőseink, akiknél mindig meglepődünk: “Jé, hát ez mindenkit ismer!”

Hálózatok központi elemei különböző algoritmusok alapján meghatározva
(Forrás: wikimedia commons / CC BY-SA 3.0)

Ismét más jellegű probléma az olyan tartalmak (vagy éppen felhasználók) megtalálása, amelyek egymással szoros kapcsolatban vannak. Például a borászattal foglalkozó blogok sokkal gyakran hivatkoznak egymásra, mint kutyatenyésztéssel foglalkozó blogokra. Ezt a jelenséget csomósodásnak hívjuk, és egy egyszerű képlettel kiszámolhatjuk egy gráf tetszőleges pontjáról, hogy mennyire zárt az őt körülvevő hálózat. Ezen értékek segítségével az is meghatározható, hogy mely blogok (vagy éppen felhasználók) saját hálózataik központi elemei.

A lenti ábrán a magyarországi blogszféra egy borászattal foglalkozó szegmensének gráf-reprezentációját látjuk. Megfigyelhető, hogy a borász-blogok egymásra gyakran hivatkoznak, és vannak olyan központi blogok is, amelyekre szinte mindenki linkel. Ezeknél az elemeknél a legmagasabb az úgynevezett csomósodási-együttható (ez az érték mutatja a gráf adott elemének a beágyazottságát.

Forrás: Tempfli Péter

A fenti ábra a magyar blogoszféra egy kis szeletét ábrázolja egy adott időpontban. A nyilak az egyes oldalakról illetve az azokra mutató linkeket jelzik. A színezett ellipszisek központok, és a köréjük szerveződő linkek is hasonló színűek. Látható, hogy a hálózat egy adott eleme egyszerre több belső hálózatnak is tagja, vagyis a „csomók” közt átfedések vannak. A fenti ábra a graphviz programcsomaggal készült, amely egy python nyelven íródott program kimenetét dolgozta fel. A python nyelvű program végigpásztázta a blog.hu blogszolgáltató blogjainak egy bizonyos részét és rögzítette az oldalak közt található viszonyokat. Az így megkapott adatokból kirajzolódik a blogoszféra (egy nagyon kis részének) gráfként való reprezentációja.  Ugyanilyen módon az is ki lehet számolni, hogy egy Facebook-felhasználó baráti köre mennyire zárt, azaz hogy az adott felhasználó ismerősei mekkora eséllyel ismerik egymást. A csomósodási együtthatót kiszámolhatjuk akár teljes gráfokra, és így megállapíthatjuk, hogy különböző tartalmak vagy közösségi hálók mennyire alkotnak összefüggő közösségeket.A gráfelmélet a közösségi hálók modellezésén túl számos más téren is kulcsfontosságú (például a térképészetben vagy a tudáshalmazok gépi reprezentálásában). Akit mélyebben érdekel a téma, annak bátran ajánlható az Udacity online szabadegyetem Algoritmusok kurzusa.