Západočeská univerzita v Plzni Fakulta aplikovaných věd Katedra informatiky a výpočetní techniky

Za´padoˇceska´ univerzita v Plzni Fakulta aplikovanyćh vˇed Katedra informatiky a vy´poˇcetn´ı techniky

Bakal´ aˇ rsk´ a pr´ ace Anal´ yza soci´ aln´ı s´ıtˇ e pˇ r´ atel

Plzeˇ n 2013

Marek Naggy

Origin´ aln´ı zad´ an´ı M´ısto této stránky bude vloˇzeno origináln´ı zadán´ı BP.

i

Prohl´ aˇ sen´ı Prohlaˇsuji, ˇze jsem bakaláˇrskou práci vypracoval samostatnˇe a v´ yhradnˇe s pouˇzit´ım citovan´ ych pramen˚ u.

V Plzni dne 2. kvˇetna 2013 Marek Naggy

ii

Podˇ ekov´ an´ı Na tomto m´ıstˇe bych rád podˇekoval Ing. Michalu Nyklovi za ochotné veden´ı práce, cenné rady a ˇcas, kter´ y mi vˇenoval pˇri konzultac´ıch.

iii

Abstract Analysis of social network of friends This thesis introduces the opportunities that social network analysis offers by analyzing online large-scale social network of friendship. Thus, you will find here a design of the web crawler, which has successfully crawled more than a million web pages located on the online social network called Lidé.cz. In the thesis you will also find statistics which show socio-demographics of this server. It is also stated what kind of information you can obtain through the analysis of online social network content. The above mentioned social network is then verified against the theoretical models. Furthermore, there are rankings which contain the most important users of this network. These rankings were created by using basic Centrality measures methods (such as Degree, Closeness and Betweenness centrality). In addition the small-world theory is verified. Key words: social network analysis, Centrality measures, web crawler, small-world theory, scale free networks, Lidé.cz

Anal´ yza soci´ aln´ı s´ıtˇ e pˇ r´ atel Práce se pomoc´ı anal´ yzy rozsáhlé online sociáln´ı s´ıtˇe pˇra´telstv´ı zamˇeˇruje na pˇribl´ıˇzen´ı moˇznost´ı, které anal´ yza sociáln´ıch s´ıt´ı nab´ız´ı. Naleznete zde návrh webového robota, kter´ y proˇsel v´ıce neˇz milion webov´ ych stránek nacházej´ıc´ıch se na online sociáln´ı s´ıti Lidé.cz. Jsou zde uvedeny statistiky zab´ yvaj´ıc´ı se sociodemografi´ı tohoto serveru a je zde uvedeno, jaké informace pomoc´ı anal´ yzy obsahu sociáln´ıch s´ıt´ı lze z´ıskat. Z´ıskaná s´ıt’ je poté verifikována oproti teoretick´ ym model˚ um. Téˇz jsou zde pomoc´ı nˇekolika základn´ıch metod Centrality measures (Degree, Closeness a Betweenness centrality) urˇceny nejv´ yznamnˇejˇs´ı uˇzivatelé nacházej´ıc´ı se v této s´ıti. Práce se téˇz zab´ yvá ovˇeˇren´ım hypotézy malého svˇeta. Kl´ıˇcová slova: anal´ yza sociáln´ıch s´ıt´ı, Centrality measures, webov´ y robot, teorie malého svˇeta, bezˇskálové s´ıtˇe, Lidé.cz

iv

Obsah ´ 1 Uvod

1

2 Soci´ aln´ı s´ıtˇ e a jejich anal´ yza 2.1 Polomˇer, hustota a dalˇs´ı pojmy z teorie graf˚ u 2.2 Modely a vlastnosti komplexn´ıch s´ıt´ı . . . . . 2.2.1 Bezˇskálové s´ıtˇe a mocninn´ y zákon . . . 2.3 Small-world experiment . . . . . . . . . . . . . 2.4 Centrality measures . . . . . . . . . . . . . . . 2.4.1 Degree centrality . . . . . . . . . . . . 2.4.2 Closeness centrality . . . . . . . . . . . 2.4.3 Betweenness centrality . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

2 3 5 6 7 8 8 9 9

3 Online soci´ aln´ı s´ıt’ Lid´ e.cz 3.1 Smluvn´ı podm´ınky a autorsk´ y zákon 3.2 Pˇredpokládaná velikost . . . . . . . . 3.3 Omezen´ı stahován´ı . . . . . . . . . . 3.4 Které webové stránky procházet? . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

11 11 11 12 13

4 Z´ısk´ an´ı dat 4.1 V´ ybˇer vhodného webového robota . . . . . . . . . . . 4.2 Tvorba webového robota . . . . . . . . . . . . . . . . 4.2.1 Ukládán´ı dat a návrh databázové struktury . 4.2.2 Architektura, algoritmy a pouˇzité technologie 4.2.3 Implementaˇcn´ı poznámky . . . . . . . . . . . 4.3 Z´ıskaná data . . . . . . . . . . . . . . . . . . . . . . . 4.4 Známé problémy . . . . . . . . . . . . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

15 15 16 16 17 19 21 22

. . . . . .

24 24 25 27 28 30 30

. . . .

. . . .

. . . .

. . . .

. . . .

5 Statistick´ e v´ ystupy a jejich porovn´ an´ı s dostupn´ ymi daty 5.1 Jaké informace zjiˇst’ovat a z jakého d˚ uvodu? . . . . . . . . . 5.2 Obyvatelstvo . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Ciz´ı jazyky a vzdˇelán´ı . . . . . . . . . . . . . . . . . . . . . 5.4 Mladistv´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Obl´ıbené sporty a hudba . . . . . . . . . . . . . . . . . . . . 5.6 Shrnut´ı kapitoly . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

6 Anal´ yza z´ıskan´ e s´ıtˇ e 6.1 V´ ybˇer vhodného frameworku . . . . . . . . . . . . . . . . . . . . . . . 6.2 Základn´ı informace o s´ıti . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 V´ ysledky Centrality measures a jejich porovnán´ı . . . . . . . . . . . .

31 31 32 35

7 Z´ avˇ er 39 7.1 Budouc´ı práce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 A Uˇ zivatelsk´ e pˇ r´ıruˇ cky 47 A.1 Webov´ y robot SNABot . . . . . . . . . . . . . . . . . . . . . . . . . . 47 A.2 Framework SNAP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 A.3 SNABot-nastroje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 B Form´ aty soubor˚ u

50

C Rozˇ s´ıˇ ren´ı statistik

51

D Porovn´ an´ı v´ ysledk˚ u aproximace s pˇ resn´ ym v´ ypoˇ ctem

52

E V´ ysledky Centrality measures pro orientovanou s´ıt’ a aproximace 54 F J´ adro s´ıtˇ e

57

´ 1 Uvod S rozvojem online sociáln´ıch s´ıt´ı (online social network – OSN), odehrávaj´ıc´ı se v posledn´ıch letech, se otv´ırá nová moˇznost, jak zkoumat strukturu lidské spoleˇcnosti a jejich vztah˚ u. Touto moˇznost´ı je anal´ yza sociáln´ıch s´ıt´ı (social network analysis – SNA). Tento analytick´ y nástroj je pouˇz´ıván napˇr. v marketingu, sociologii ˇci kriminalistice. Práce se zab´ yvá anal´ yzou sociáln´ı s´ıtˇe pˇra´tel, která byla z´ıskána z OSN Lidé.cz. Obecnˇe se vˇsak OSN nemus´ıme omezovat. Tyto metody lze uplatnit v mnoha dalˇs´ıch sociáln´ıch s´ıt´ıch od spolupráce mezi herci, telefonn´ımi hovory aˇz po krimináln´ı s´ıt’. C´ılem práce nen´ı komplexn´ı anal´ yza zvolené OSN (nenaleznete zde napˇr. anal´ yzu komunit ˇci dynamiky), ale pˇribl´ıˇzit ˇctenáˇri moˇznosti, které SNA nab´ız´ı a ukázat, proˇc jsou jej´ı metody vyuˇz´ıvány napˇr. FBI [25] ˇci armádn´ımi zpravodajci [26]. Po prvn´ıch dvou kapitolách, vˇenuj´ıc´ıch se zejména pojm˚ um z teorie graf˚ u, pˇredstaven´ı a anal´ yze zvolené OSN, následuje kapitola zab´ yvaj´ıc´ı se automatick´ ym sbˇerem dat pro dalˇs´ı anal´ yzu. Vzhledem k tomu, ˇze pro naˇsi anal´ yzu byla zvolena OSN, je v této kapitole popsán postup návrhu webového robota, kter´ y umoˇzn´ı jej´ı automatické z´ıskán´ı. Pátá kapitola si klade za c´ıl motivovat napˇr. zamˇestnance marketingov´ ych ˇci reklamn´ıch agentur a ukázat, jaké informace lze z dat uchovan´ ych v OSN z´ıskat. V´ ysledky jsou pr˚ ubˇeˇznˇe porovnávány s podobn´ ymi pr˚ uzkumy, jeˇz jsou provádˇeny klasickou“ ” dotazn´ıkovou formou. Tento krok se snaˇz´ı urˇcit, do jaké m´ıry lze povaˇzovat data, která uˇzivatelé uvádˇej´ı, za spolehlivá. Posledn´ı kapitola se zab´ yvá samotnou anal´ yzou z´ıskané s´ıtˇe. Naleznete zde nˇekteré základn´ı vlastnosti této s´ıtˇe a porovnán´ı, na kolik odpov´ıdá teoretick´ ym model˚ um, které jsou uvedeny v druhé kapitole. Dalˇs´ı ˇca´st´ı této kapitoly jsou ˇzebˇr´ıˇcky sestavené dle metod, které umoˇzn ˇuj´ı v s´ıti identifikovat kl´ıˇcové osoby, diskuse z´ıskan´ ych v´ ysledk˚ u a jejich porovnán´ı s podobn´ ymi pracemi. V z´ıskané s´ıti se téˇz snaˇz´ım ovˇeˇrit teorii malého svˇeta, zaloˇzenou S. Milgramem roku 1967 [29]. Ta inspirovala divadeln´ı hru a následnˇe televizn´ı film, kter´ y tuto hypotézu ˇ proslavil tvrzen´ım: Kaˇzd´ y na této planetˇe je oddˇelen jen ˇsesti jin´ ymi lidmi. Sest ” krok˚ u od sebe. Mezi námi a k´ ymkoli jin´ ym na této planetˇe. Prezident Spojen´ ych stát˚ u. Benátsk´ y gondoliér... “ [10]. Práce je inspirována v´ yzkumem A.L. Barabásiho [5, 10] zkoumaj´ıc´ım r˚ uzné typy komplexn´ıch s´ıt´ı a pˇredstavuj´ıc´ı jejich tzv. bezˇskálov´ y model. Dále pracemi, které zkoumaj´ı jiné OSN (napˇr. Facebook.com, Flickr.com aj.) [18, 30, 6]. Za ˇceské jmenujme [21] analyzuj´ıc´ı OSN CouchSurfing.com ˇci [24] zkoumaj´ıc´ı sociáln´ı s´ıt’ organizátor˚ u záˇzitkov´ ych akc´ı. 1

2 Sociáln´ı s´ıtˇe a jejich analýza Pojem sociáln´ı s´ıt’ pocház´ı ze sociologie a je formulován jako skupina sociáln´ıch vztah˚ u nebo vazeb mezi aktéry, které vzájemnˇe propojuj´ı [14, 23]. Tyto vazby mohou b´ yt kladné ˇci záporné, m´ıt stejnou nebo rozd´ılnou váhu a orientaci. Sociáln´ı s´ıt’ lze reprezentovat grafem (viz ˇcást 2.1) nebo matic´ı sousednosti [23, 26]. Graf, kter´ y reprezentuje sociáln´ı s´ıt’ se naz´ yvá sociogramem [14, 23]. V sociogramu jsou aktéˇri zobrazeni jako vrcholy (body) a jejich vztahy jako hrany (vazby, které vrcholy spojuj´ı). Jeho ukázku m˚ uˇzete vidˇet na obr. 2.1 (pro vizualizaci byla pouˇzita data z [12] a program Gephi [11]). V tomto obr. je velikost a barva vrcholu dána jeho oblibou“ mezi ostatn´ımi vrcholy (jedná se o orientovanou vazbu – povaˇzuji ho za ” ” pˇr´ıtele“). V´ ypoˇcet je zaloˇzen na metrice Betweenness centrality (viz kapitola 2.4.3).

Robin Walt Ben

Steve

Alex Gary

Earl Ev

Bob

Pat

Mel

Jack

Dale Jim

Chris

Dan

Rick

Ovid

Nan

Irv

Ken

Carl

Upton

Hugh

Gerry

Tom

Hal

Vic

Zoe

Len

Fred Abe

Ivo

Obr. 2.1: Ukázka sociogramu. Online sociáln´ı s´ıt’ (Online social network – OSN) je v [17] definována jako webová sluˇzba, která uˇzivatel˚ um umoˇzn ˇuje vytvoˇrit si vlastn´ı profil1 , navazovat s dalˇs´ımi uˇzivateli spojen´ı a prohl´ıˇzet si jejich profily nebo jejich spojen´ı. OSN se tak snaˇz´ı pˇrenést ˇca´sti reáln´ ych sociáln´ıch s´ıt´ı do virtuáln´ıho prostˇred´ı. 1

Vlastn´ı webovou str´ anku, kter´ a obsahuje informace o uˇzivateli.

2

Sociáln´ı s´ıtˇe a jejich analýza

Polomˇer, hustota a dalˇs´ı pojmy z teorie graf˚ u

Za prvn´ı OSN je povaˇzována SixDegrees.com, spuˇstˇená v roce 1997 a ukonˇcena v roce 2000 [17]. Mezi dneˇsn´ı nejznámˇejˇs´ı OSN patˇr´ı Facebook2 , Twitter3 nebo Google+4 . Za ˇceské jmenujme Lidé.cz5 nebo Spoluˇzaći.cz6 . Analýzou sociáln´ı s´ıtˇe (jak reálné, tak virtuáln´ı) rozum´ıme zkoumán´ı, detekován´ı a interpretován´ı vzor˚ u, které tvoˇr´ı sociáln´ı vazby mezi aktéry [16]. Oblasti vyuˇzit´ı této anal´ yzy jsou ˇsiroké, od vyuˇzit´ı v marketingu, modelován´ı pˇrenos˚ u nemoc´ı, zkoumán´ı moˇzného napojen´ı na krimináln´ı organizace, aˇz po anal´ yzu politického hlasován´ı [10, 26, 27].

2.1

Polomˇ er, hustota a dalˇ s´ı pojmy z teorie graf˚ u

V této ˇca´sti naleznete nˇekolik pojm˚ u z teorie graf˚ u, které budou v textu dále pouˇz´ıvány a jejich aplikaci na sociáln´ı s´ıt’, která bude dále zkoumána. Jako zdroje byly pouˇzity [4, 18, 23]. Graf, jeho orientace a v´ ahy hran Jako graf G oznaˇcujeme dvojici G = (V, E), kde V je koneˇcná neprázdná mnoˇzina vrchol˚ u a E je koneˇcná mnoˇzina hran, které mezi sebou propojuj´ı dvojice vrchol˚ u z mnoˇziny V . Poˇcet vrchol˚ u V budeme znaˇcit jako n a poˇcet hran E jako m. Pokud budou vrcholy spojeny hranou, bude v textu dále znaˇceno, ˇze vrchol vi má kontakt na vrchol vj a hrana bude znaˇcena jako {vi , vj }. V naˇsem pˇr´ıpadˇe, budou vrcholy pˇredstavovat uˇzivatele OSN a hrany jejich virtuáln´ı pˇrátelstv´ı. Jako orientovaný graf uvaˇzujeme takov´ y graf, u kterého rozliˇsujeme smˇer odkud (z v´ ychoz´ıho vrcholu) kam (do c´ılového vrcholu) hrana vede tzn. hrana {x, y} = 6 {y, x}. U neorientovaného grafu tento smˇer neuvaˇzujeme tzn. hrana {x, y} = {y, x}. Graf oznaˇc´ıme jako neváˇzený, pokud jeho hrany nejsou ohodnoceny váhou7 , pˇr´ıpadnˇe pokud plat´ı ω(e) = 1; ∀e ∈ E, kde ω je funkc´ı urˇcuj´ıc´ı váhu hrany. Váˇzeným grafem naopak oznaˇc´ıme graf, u kterého rozliˇsujeme váhy jednotliv´ ych hran. 2

http://www.facebook.com http://www.twitter.com 4 http://plus.google.com 5 http://www.lide.cz 6 http://www.spoluzaci.cz 7 V´ aha m˚ uˇze pˇredstavovat napˇr. cenu, vzdálenost, kapacitu apod. 3

3


Polomˇer, hustota a dalˇs´ı pojmy z teorie graf˚ u

Stupeˇ n vrcholu Jako stupeˇ n vrcholu v dG (v) oznaˇcujeme poˇcet hran z mnoˇziny E, pro které plat´ı {v, x} ˇci {x, v}. Pokud mluv´ıme o neorientovaném grafu, nezáleˇz´ı, zda bude uzel v c´ılov´ y nebo poˇcáteˇcn´ı. U orientovaného grafu oznaˇcujeme jako d+ cet v´ ystupG (v) poˇ n´ıch hran z vrcholu v. Pro poˇcet vstupn´ıch hran pouˇz´ıváme znaˇcen´ı d− (v). V pˇ r´ıpadˇe G váˇzeného grafu poˇc´ıtáme nejen s poˇctem hran, ale i s jejich váhou. V naˇsem pˇr´ıpadˇe stupeˇ n vrcholu v vyjadˇruje, kolik má uˇzivatel v virtuáln´ıch pˇra´tel (v´ ystupn´ıch hran) a kolik uˇzivatel˚ u ho za pˇr´ıtele povaˇzuje (vstupn´ı hrany). V ˇca´sti 2.4.1 naleznete metriku, která pracuje v´ yhradnˇe s touto informac´ı. Cesta a nejkratˇ s´ı cesta Cestou v grafu G oznaˇcujeme libovolnou posloupnost pˇrechod˚ u mezi vrcholy va a vz za pomoci hran {va , vb },{vb , vc } ... {vy , vz }, ve které se kaˇzd´ y vrchol vi objevuje pouze jednou. Nejkratˇs´ı cestou mezi dvˇema vrcholy rozum´ıme cestu, jej´ıˇz ohodnocen´ı je ze vˇsech existuj´ıc´ıch cest minimáln´ı. Pokud graf obsahuje v´ıce komponent (Ki , Kj viz dále), délka nejkratˇs´ı cesty z vrcholu va ∈ Ki do vrcholu vz ∈ Kj je nekoneˇcná. V naˇsem pˇr´ıpadˇe cesta znamená posloupnost uˇzivatel˚ u, která je zapotˇreb´ı pro komunikaci mezi uˇzivateli va a vz . Tuto komunikaci je moˇzné zprostˇredkovat pomoc´ı pˇra´tel. Komponenta Komponentou Ki v grafu G oznaˇc´ıme podgraf (podmnoˇzina vrchol˚ u a hran p˚ uvodn´ıho grafu), neexistuje-li cesta z vrcholu vi ∈ Ki do vrcholu vj ∈ Kj , pˇriˇcemˇz plat´ı Ki ∩ Kj = ∅. Jin´ ymi slovy – ˇza´dn´ y vrchol z Ki nen´ı spojen hranou s vrcholem patˇr´ıc´ı do Kj . Pokud z kaˇzdého vrcholu v existuje koneˇcná cesta do vˇsech vrchol˚ u, má graf jednu komponentu. Pokud by v grafu bylo v´ıce komponent, znamená to, ˇze uˇzivatelé z komponenty Ki , nemohou za pomoci sv´ ych kontakt˚ u, komunikovat s uˇzivateli z komponenty Kj . Hustota grafu Hustota grafu je dána jako pomˇer hran existuj´ıc´ıch a hran vˇsech moˇzn´ ych. Pro m 2m y pak ∆ = n(n−1) . Kde m je neorientovan´ y graf tedy ∆ = n(n−1) , pro graf orientovan´ poˇcet hran a n poˇcet vrchol˚ u. Jej´ı hodnota se pohybuje v intervalu < 0, 1 >. V reáln´ ych rozsáhl´ ych s´ıt´ıch tato hodnota vˇetˇsinou nab´ yvá mal´ ych hodnot [16].

4


Modely a vlastnosti komplexn´ıch s´ıt´ı

Polomˇ er grafu Polomˇer grafu D je roven ohodnocen´ı nejdelˇs´ı z nejkratˇs´ıch cest vˇsech dvojic vrchol˚ u grafu G. V pˇr´ıpadˇe, ˇze je graf rozdˇelen´ y na v´ıce komponent, plat´ı D = ∞. V tom pˇr´ıpadˇe má smysl uvaˇzovat polomˇer nejvˇetˇs´ı komponenty. Pr˚ umˇ ern´ a d´ elka nejkratˇ s´ı cesty Pr˚ umˇerná délka nejkratˇs´ı cesty (Average shortest path length – ASPL) l v grafu G, je definována jako aritmetick´ y pr˚ umˇer délek nejkratˇs´ıch cest mezi vˇsemi moˇzn´ ymi dvojicemi vrchol˚ u v grafu G (viz (1) a [15]).

l=

X 1 g(vi , vj ) n(n − 1) i6=j

(1)

Kde n je poˇcet vrchol˚ u a g(vi , vj ) je délka nejkratˇs´ı cesty mezi vrcholy vi a vj . Pokud graf obsahuje v´ıce komponent, urˇcujeme ASPL v nejvˇetˇs´ı komponentˇe. Tuto hodnotu lze odhadnout jako l ∼ ln(n)/ ln ln(n). Jak v lidské spoleˇcnosti (ve smyslu propojen´ı pomoc´ı pˇra´tel), tak v dalˇs´ıch s´ıt´ıch, jako napˇr. spolupráce herc˚ u v Holywoodu, citaˇcn´ıch s´ıt´ı aj. (viz [10]) je tato hodnota relativnˇe malá – ASPL mezi obˇcany USA je uvádˇena jako 6,5 (viz kapitola 2.3).

2.2


Text v této ˇca´sti vycház´ı ze zdroj˚ u [10, 15, 5]. Pro modelován´ı komplexn´ıch s´ıt´ı se v souˇcasnosti pouˇz´ıvaj´ı tˇri hlavn´ı paradigmata: teorie náhodn´ ych graf˚ u, WattsStrogatz˚ uv model a model bezˇskálov´ ych s´ıt´ı. Model náhodných s´ıt´ı (1959) [10]. pˇredpokládá, ˇze kaˇzdá dvojice vrchol˚ u je spojena hranou s pravdˇepodobnost´ı p. Pokud bychom tedy uvaˇzovali p = 0, ˇza´dné vrcholy spojeny nebudou, naopak, pokud p = 1 budou spolu spojeny vˇsechny vrcholy. Takto vytvoˇrené s´ıtˇe, maj´ı relativnˇe mal´ y polomˇer, ale jejich dalˇs´ı vlastnosti neodpov´ıdaj´ı empirick´ ym v´ ysledk˚ um z´ıskan´ ym z reáln´ ych s´ıt´ı8 . Zejména kv˚ uli absenci vrchol˚ u s nˇekolikanásobnˇe vˇetˇs´ım stupnˇem neˇz je stupeˇ n pr˚ umˇern´ y, které se v reáln´ ych s´ıt´ıch bˇeˇznˇe vyskytuj´ı. Dále kv˚ uli malému koeficientu shlukován´ı, ve kterém se odráˇz´ı neschopnost podobn´ ych vrchol˚ u vytváˇret tzv. shluky, ve kter´ ych je vˇetˇsina vrchol˚ u vzájemnˇe propojena. 8

Ty m˚ uˇzete nalézt v [5], jedn´ a se napˇr. o s´ıt’ webov´ ych stránek, spolupráce herc˚ u aj.

5



Model, kter´ y problém s mal´ ym koeficientem shlukován´ı odstraˇ nuje, se naz´ yvá WattStrogatz˚ uv model (1998) [10]. Ten pouˇz´ıvá vrcholy uspoˇrádané do kruhu, jenˇz jsou propojeny se sv´ ymi K sousedy, kde K urˇcuje poˇcet propojen´ ych soused˚ u (K/2 na kaˇzdé stranˇe). Poté jsou nˇekteré vrcholy propojeny jako v modelu pˇredchoz´ım – tento krok vytváˇr´ı tzv. slabé vazby9 zmenˇsuj´ıc´ı polomˇer s´ıtˇe. Tento model vˇsak stále nevyˇreˇsil existenci vrchol˚ u s vysok´ ym stupnˇem. Ten ˇreˇs´ı aˇz model bezˇskálových s´ıt´ı (2001) [5].

2.2.1

Bezˇ sk´ alov´ e s´ıtˇ e a mocninn´ y z´ akon

Pˇri zkoumán´ı reáln´ ych s´ıt´ı, at’ jiˇz rozvoden elektˇriny, spolupráce herc˚ u v Holywoodu nebo zkoumán´ı struktury internetu, se ukázalo, ˇze nˇekteré vrcholy maj´ı oproti jin´ ym nˇekolikanásobnˇe vˇetˇs´ı stupeˇ n. Takovéto vrcholy budeme dále oznaˇcovat jako centra. V pˇredchoz´ıch modelech je nepˇr´ıtomnost center dána Poissonov´ ym rozdˇelen´ım pravdˇepodobnosti, kter´ ym se u vrchol˚ u ˇr´ıd´ı rozdˇelen´ı jejich stupnˇe. Pro vysvˇetlen´ı vzniku center je tˇreba vz´ıt v u ´vahu, ˇze vrcholy jsou do s´ıtˇe pˇridávány postupnˇe a neexistuj´ı v s´ıti od jej´ıho poˇcátku, jak uvaˇzovaly modely pˇredchoz´ı. Starˇs´ı vrcholy tak maj´ı v´ıce ˇcasu na z´ıskán´ı v´ıce kontakt˚ u. Dle [10] tento samotn´ y fakt pro vznik center nestaˇc´ı. Dalˇs´ım pravidlem pro pˇripojován´ı vrchol˚ u je tzv. preferenˇcn´ı pˇripojován´ı. To ˇr´ıká, ˇze pravdˇepodobnost pˇripojen´ı nového vrcholu k vrchol˚ um stávaj´ıc´ım je u ´mˇerná jejich ˇ stupni a atraktivitˇe“ pro nové vrcholy. C´ım vˇetˇs´ı stupeˇ n tedy vrchol má a ˇc´ım je ” pro nové vrcholy atraktivnˇejˇs´ı“, t´ım je pravdˇepodobnˇejˇs´ı, ˇze z´ıská dalˇs´ı kontakty. ” Na obr. 2.2 m˚ uˇzete vidˇet v´ yvoj bezˇskálové s´ıtˇe, kde kaˇzd´ y obrázek pˇredstavuje pˇridán´ı nového vrcholu (znázornˇen´ y prázdn´ ym krouˇzkem), pˇriˇcemˇz se kaˇzd´ y nov´ y vrchol m˚ uˇze pˇripojit právˇe ke dvˇema vrchol˚ um. Nové vrcholy se ˇr´ıd´ı preferenˇcn´ım pˇripojován´ım (pouze podle stupnˇe) a jak je z obrázku vidˇet, vznikaj´ı tak centra s vysok´ ym stupnˇem. Tyto dva faktory odstraˇ nuj´ı v´ yˇse zmiˇ nované Poissnovo rozdˇelen´ı a nahrazuj´ı ho tzv. mocninným zákonem. Tento zákon se ˇr´ıd´ı vzorcem (2), N (k) = k −γ

(2)

kde N (k) znaˇc´ı ˇcetnost v´ yskytu vrchol˚ u stupnˇe k. Jako γ je oznaˇcen exponent konektivity. Tento exponent má v reáln´ ych s´ıt´ıch nejˇcastˇeji hodnotu 2 ≤ γ ≤ 3 [10]. S´ıtˇe, ˇr´ıd´ıc´ı se mocninn´ ym zákonem maj´ı nˇekolik spoleˇcn´ ych vlastnost´ı. D´ıky centr˚ um maj´ı relativnˇe mal´ y polomˇer a jsou odolné proti náhodn´ ym v´ ypadk˚ um. V s´ıt´ıch, ve kter´ ych plat´ı γ ≤ 3, pak lze náhodnˇe odebrat témˇeˇr vˇsechny vrcholy a s´ıt’ se stále 9

V [10, 14] se uv´ ad´ı, ˇze pr´ avˇe slabé vazby hraj´ı v sociáln´ı interakci d˚ uleˇzitou roli napˇr. pˇri hled´ an´ı zamˇestn´ an´ı nebo pˇri rozˇsiˇrován´ı fám.

6


Small-world experiment

Obr. 2.2: V´ yvoj bezˇskálové s´ıtˇe – obrázek byl pˇrevzat z [10]. nerozpadne na v´ıce komponent [10]. Na druhou stranu, pro bezˇskálové s´ıtˇe plat´ı, ˇze pokud bychom vrcholy odeb´ırali c´ılenˇe, staˇc´ı jich odebrat pouze nˇekolik a s´ıt’ se rozpadne – v tomto pˇr´ıpadˇe bychom volili právˇe centra.

2.3

Small-world experiment

Roku 1967 provedl S. Milgram experiment [29], kter´ y mˇel ovˇeˇrit kolik prostˇredn´ık˚ u je zapotˇreb´ı pro spojen´ı dvou náhodn´ ych lid´ı v USA. Pˇri tomto experimentu rozeslal v´ıce neˇz sto sloˇzek r˚ uzn´ ym lidem v Nebrasce, kteˇr´ı mˇeli za u ´kol pˇreposlat tyto sloˇzky 10 c´ılovému ˇclovˇeku v Massachusetts a dodrˇzet pravidlo, ˇze je sloˇzku moˇzné pˇreposlat pouze osobˇe, kterou osobnˇe znaj´ı. C´ılem bylo zjistit, na kolik je lidská spoleˇcnost propojená (formou znám´ ych a pˇrátel). V´ ysledky ukázaly, ˇze tyto sloˇzky dorazily k c´ılovému ˇclovˇeku za pouˇzit´ı dvou aˇz deseti prostˇredn´ık˚ u, pˇriˇcemˇz jejich pr˚ umˇern´ y poˇcet byl 5,5. Je nutné podotknout, ˇze v´ ysledek m˚ uˇze b´ yt ponˇekud zavádˇej´ıc´ı. Délka tˇechto cest byla dána nejlepˇs´ım odhadem lid´ı, kteˇr´ı topologii této s´ıtˇe neznali. Na zkreslen´ı v´ ysledku se taktéˇz mohlo projevit to, ˇze z p˚ uvodn´ıch 160 sloˇzek jich k c´ıli dorazilo pouze 27,5%, tj. jen 44. Po pr˚ uzkumu ˇretˇezc˚ u Milgram nalezl nˇekolik dalˇs´ıch zaj´ımavost´ı. C´ılové osobˇe dorazilo 48% sloˇzek pˇres cesty, kde se jako posledn´ı zprostˇredkovatelé vyskytovali pouze tˇri r˚ uzné osoby. To m˚ uˇze naznaˇcovat, ˇze nˇekteré cesty jsou vyuˇz´ıvány v´ıce neˇz ostatn´ı. U podobného experimentu (oznaˇcovaného jako Kansask´ y) zjistil, ˇze jak ˇzeny, tak muˇzi pˇrepos´ılali sloˇzky stejnému pohlav´ı ˇcastˇeji – pˇribliˇznˇe o 78%. ˇ Tento experiment inspiroval divadeln´ı hru s názvem Sest stupˇ n˚ u odlouˇcen´ı, která byla pozdˇeji zfilmována. V té se mylnˇe uvád´ı, ˇze fenomén ˇsesti krok˚ u plat´ı pro cel´ y svˇet [10]. Posledn´ı studie, viz [6], zkoumaj´ıc´ı v´ıce neˇz 720 milión˚ u uˇzivatel˚ u OSN 10

Vzd´ alen´ y z v´ ychoz´ıho bodu pˇribliˇznˇe 2 300 km.

7


Centrality measures

Facebook.com z nˇekolika zem´ı vˇsak ukazuje, ˇze tato hodnota je jeˇstˇe menˇs´ı. Jako ASPL uvád´ı 4,74 – tedy pouze“11 3,74 stupnˇe odlouˇcen´ı. ”

2.4

Centrality measures

Centrality measures (CM) jsou kolekc´ı metod, umoˇzn ˇuj´ıc´ıch mˇeˇren´ı tzv. centrality jednotliv´ ych vrchol˚ u, která urˇcuje jejich v´ yznamnost v s´ıti [18, 23, 26]. Vrcholy s vysokou centralitou maj´ı v s´ıti v´ yhodnˇejˇs´ı pozici, napˇr. ve smyslu moˇznosti kontroly toku informac´ı nebo moˇznosti ovlivˇ novat vrcholy ostatn´ı. Mezi tˇri hlavn´ı metody, které umoˇzn ˇuj´ı centralitu mˇeˇrit, patˇr´ı Degree centrality (CD ), Closeness centrality (CC ) a Betweenness centrality (CB ) [23, 26]. V dalˇs´ım textu budou popsány základn´ı pˇr´ıstupy k tˇemto metodám, nejˇcastˇeji oznaˇcované jako Freemanovy12 . Pro kaˇzdou z tˇechto metod existuje nˇekolik dalˇs´ıch variant (napˇr. Bonachiho pˇr´ıstup pro CD , Eigenvector vycházej´ıc´ı z CC aj.), které tyto základn´ı pˇr´ıstupy rozˇsiˇruj´ı (viz [23]). V´ ysledky vˇsech metod lze normalizovat, coˇz umoˇzn ˇuje vzájemné porovnán´ı mezi podobn´ ymi s´ıtˇemi.

2.4.1

Degree centrality

Degree centrality je nejjednoduˇsˇs´ı metoda, kdy je centralita urˇcena stupnˇem uzlu13 (viz ˇca´st 2.1). U orientované s´ıtˇe se m˚ uˇze jednat o stupeˇ n v´ ystupn´ı, vstupn´ı nebo kombinaci obou. Vrchol s vˇetˇs´ım stupnˇem je zv´ yhodnˇen t´ım, ˇze má v´ıce moˇznost´ı, jak v s´ıti komunikovat. T´ım se stává ménˇe závisl´ ym na vrcholech dalˇs´ıch. Zároveˇ n m˚ uˇze jin´ ym vrchol˚ um slouˇzit jako prostˇredn´ık pˇri komunikaci a z této sluˇzby tˇeˇzit. V orientované s´ıti jsou vrcholy s vysok´ ym vstupn´ım stupnˇem oznaˇcovány jako prominentn´ı nebo prestiˇzn´ı, vrcholy s vysok´ ym v´ ystupn´ım stupnˇem pak jako vrcholy vlivné [23]. Normalizovaná verze této metriky viz vzorec (3) a [18], CD (vi ) =

d(vi ) n−1

(3)

kde d(vi ) je stupeˇ n vrcholu vi a n celkov´ y poˇcet vrchol˚ u v s´ıti. 11

Zde je moˇzné se na problém d´ıvat ze dvou stran. Z jedné strany se skuteˇcnˇe jedná o malé ˇc´ıslo. Na druhou stranu se jedn´ a o nˇekolik okruh˚ u znám´ ych, coˇz m˚ uˇze b´ yt velká psychologick´ a ” vzd´ alenost“ [29]. 12 Jejich autorem je sociolog Linton C. Freeman, viz [20]. 13 U v´ aˇzené s´ıtˇe m˚ uˇzeme pouˇz´ıt tzv. Weighed degree centrality, která pro v´ ypoˇcet pouˇz´ıvá nejen poˇcet hran, ale i jejich v´ ahu.

8


Centrality measures

Nev´ yhodou této metody je, ˇze vrcholy s vysokou hodnotou CD nemus´ı b´ yt ty s nejvˇetˇs´ı centralitu nebo mohou b´ yt centráln´ı pouze lokálnˇe [23]. Naopak v´ yhodou této metody je n´ızká v´ ypoˇcetn´ı sloˇzitost.

2.4.2

Closeness centrality

Closeness centrality – pˇresnˇejˇs´ı metoda, která analyzuje, jak je vrchol bl´ızko k dalˇ ım je bl´ıˇze, t´ım efektivnˇeji dokáˇze s dalˇs´ımi vrcholy komunikovat. ˇs´ım vrchol˚ um. C´ Taktéˇz t´ım vzr˚ ustá ˇsance, ˇze komunikace bude u ´spˇeˇsná (zpráva nebude jin´ ymi uzly zam´ıtnuta apod.). Dalˇs´ı v´ yhodou vrcholu s vysokou hodnotou CC je, ˇze se jej pravdˇepodobnˇe budou ostatn´ı vrcholy snaˇzit vyuˇz´ıt pˇri komunikaci, ˇc´ımˇz tento vrchol z´ıskává na d˚ uleˇzitosti [23]. V´ ypoˇcet této metriky je dán jako pˇrevrácená hodnota souˇctu délek nejkratˇs´ıch cest s´ıtˇe. Normalizovaná verze viz vzorec (4) a [18], −1



n 1 X g(vi , vj ) CC (vi ) =  n − 1 j6=i

(4)

kde vi je v´ ychoz´ı vrchol, vj vrchol c´ılov´ y, n poˇcet vrchol˚ u v s´ıti a g(vi , vj ) je délka nejkratˇs´ı cesty z vrcholu vi do vrcholu vj . Tato metoda narozd´ıl od CD dokáˇze odhalit i vrcholy menˇs´ıho stupnˇe, které jsou vˇsak na základˇe své polohy“ v s´ıti v´ yznamné [23, 26]. Nev´ yhodou je jej´ı v´ ypoˇcetn´ı ” 3 2 sloˇzitost, která je pro váˇzené s´ıtˇe O(nm + n ) a pro neváˇzené O(nm + n ), viz [8].

2.4.3

Betweenness centrality

Betweenness centrality je komplexn´ı metoda, která analyzuje, jak ˇcasto vrchol leˇz´ı na nejkratˇs´ı cestˇe pˇri komunikaci mezi vrcholy dalˇs´ımi [18, 23]. Vrcholy s vysokou hodnotou CB jsou d˚ uleˇzité, protoˇze napˇr. umoˇzn ˇuj´ı efektivn´ı komunikaci mezi r˚ uzn´ ymi komunitami. Svého postaven´ı tak mohou vyuˇz´ıvat a vyb´ırat servisn´ı poplatky“, rozhodnout se blokovat neˇza´douc´ı zprávy nebo izolovat nˇekteré ” vrcholy. T´ımto mohou do znaˇcné m´ıry kontrolovat dˇen´ı v s´ıti [23, 26]. V´ ypoˇcet CB se pro vrchol vi vypoˇc´ıtá jako:

CB (vi ) =

X vs 6=vi 6=vt

9

σst (vi ) σst

(5)


Centrality measures

kde σst je poˇcet nejkratˇs´ıch cest mezi vrcholy vs a vt (pokud maj´ı stejné ohodnocen´ı, m˚ uˇze jich b´ yt v´ıce) a σst (vi ) je poˇcet nejkratˇs´ıch cest mezi vrcholy vs a vt , které procházej´ı vrcholem vi [18]. Normalizace této metriky se provede vydˇelen´ım CB (vi ) s (n − 1)(n − 2) pro s´ıt’ orientovanou a (n−1)(n−2) pro s´ıt’ neorientovanou [32]. Kde n je poˇcet vrchol˚ u v s´ıti. 2 V´ yhodou CB je nalezen´ı vrchol˚ u, které jsou v s´ıti nejv´ıce vyuˇz´ıvány pˇri pˇredáván´ı zpráv, za pˇredpokladu vyuˇz´ıván´ı nejkratˇs´ıch cest. Jej´ı nev´ yhodou je jej´ı v´ ypoˇcetn´ı sloˇzitost, která je uvádˇena jako O(mn + n2 log n) pro váˇzené s´ıtˇe, pro neváˇzené pak O(mn), viz [8]. To plat´ı pˇri pouˇzit´ı algoritmu uvádˇeného v [13] jinak je pro váˇzené i neváˇzené O(n3 ).

10

3 Online sociáln´ı s´ıt’ Lidé.cz Sociáln´ı s´ıt’ Lidé.cz je nejvˇetˇs´ı ˇceskou OSN1 , kterou provozuje firma Seznam.cz, a.s. V dobˇe svého vzniku (1997) slouˇzila k vyhledáván´ı e-mailov´ ych adres2 . Pozdˇeji se transformovala do dneˇsn´ı podoby, umoˇzn ˇuj´ıc´ı uˇzivatel˚ um mezi sebou komunikovat, seznamovat se, vzájemnˇe si prohl´ıˇzet profily apod.

3.1

Smluvn´ı podm´ınky a autorsk´ y z´ akon

Pát´ y bod tˇret´ı ˇca´sti smluvn´ıch podm´ınek Lidé.cz (viz [36]) ˇr´ıká, ˇze uveden´ım osobn´ıch informac´ı o své osobˇe, uˇzivatel souhlas´ı s jejich zveˇrejnˇen´ım pˇredem neomezenému okruhu osob. Z toho plyne, ˇze pˇri zpracován´ı informac´ı z´ıskan´ ych z této OSN by nemˇel b´ yt poruˇsen zákon o ochranˇe osobn´ıch u ´daj˚ u. Autorský zákon takovéto vytˇeˇzován´ı databáze – zejména pro komerˇcn´ı u ´ˇcely – zakazuje. Zároveˇ n ho vˇsak dle §92 povoluje a) pro osobn´ı potˇrebu, b) pro u ´ˇcely vˇedecké nebo vyuˇcovac´ı, c) pro u ´ˇcely veˇrejné bezpeˇcnosti nebo správn´ıho ˇci soudn´ıho ˇr´ızen´ı [1].

3.2

Pˇ redpokl´ adan´ a velikost

Oficiáln´ı informace o aktuáln´ı velikosti této OSN nejsou uvádˇeny. Poˇcet online uˇzivatel˚ u se pohybuje v rozmez´ı 20 - 30 tis´ıc. Tisková zpráva z konce bˇrezna 2007, zveˇrejnˇená prostˇrednictv´ım serveru Lupa.cz3 , se zmiˇ nuje o pˇrekonán´ı hranice milionu uˇzivatel˚ u s vlastn´ım profilem. Spoleˇcnost Netmonitor ve veˇrejn´ ych v´ ystupech z prosince 2012 uvád´ı, ˇze pˇribliˇzn´ y poˇcet unikátn´ıch mˇes´ıˇcn´ıch pˇr´ıstup˚ u (RUM ) na subdoménˇe http://profil.lide.cz byl 610 tis´ıc. Zde je pro srovnán´ı nˇekolik u ´daj˚ u z pˇredeˇsl´ ych obdob´ı (hodnoty uvedeny v poˇctu RUM ): ˇ Cerven 2007 – 1,1 milionu; Leden 2010 – 1,5 milionu (maximum v obr. 3.1); Prosinec 2011 – 830 tis´ıc; Kvˇeten 2012 – 710 tis´ıc. 1

Dle spoleˇcnosti NetMonitor (http://www.netmonitor.cz). http://onas.seznam.cz/cz/o-firme/historie-firmy/1997 3 http://www.lupa.cz 2

11

Online sociáln´ı s´ıt’ Lidé.cz

Omezen´ı stahován´ı

Obr. 3.1 zobrazuje relativn´ı objem vyhledáván´ı této OSN pomoc´ı vyhledávaˇce Google.com. Z obrázku je vidˇet postupn´ y u ´tlum, kter´ y je pravdˇepodobnˇe zp˚ usoben vstupem zahraniˇcn´ıch OSN (napˇr. Facebook.com) na ˇcesk´ y trh.

Obr. 3.1: Relativn´ı objem vyhledáván´ı OSN Lidé.cz dle aplikace Google Trends4 . Jelikoˇz pr˚ umˇern´ y dennˇe stráven´ y ˇcas návˇstˇevn´ıka na této OSN je relativnˇe vysok´ y (cca 35 min), pˇredpokládám, ˇze se jedná o stálé návˇstˇevn´ıky“. Souˇcasn´ y poˇcet ” aktivn´ıch profil˚ u5 se tak dle mého názoru bl´ıˇz´ı pr˚ umˇernému poˇctu RUM za posledn´ı rok. Tedy 600 aˇz 800 tis´ıc˚ um. Pˇriˇcemˇz z obr. 3.1 usuzuji, ˇze tento poˇcet stagnuje ˇci pozvolna klesá.

3.3

Omezen´ı stahov´ an´ı

Po prozkoumán´ı podm´ınek pouˇz´ıván´ı [35] a smluvn´ıch ujednán´ı [36] Lidé.cz zjist´ıme, ˇze se provozovatel o automatickém procházen´ı nezmiˇ nuje (oproti tomu napˇr. pˇri automatickém procházen´ı OSN Facebook.com je nutné ˇza´dat o povolen´ı6 ). Soubor robots.txt7 na adrese http://lide.cz/robots.txt, obsahuje pouze ˇra´dky: User-Agent: * Disallow: Ty robot˚ um povoluj´ı následovat veˇskeré odkazy [2]. Automatické procházen´ı nen´ı omezeno ani HTML metatagem: <meta name="robots"content="noindex, nofollow"> Stále je vˇsak moˇzné, ˇze si provozovatel nebude pˇra´t, aby tato OSN byla procházena neznám´ ymi roboty (napˇr. kv˚ uli omezen´ı zátˇeˇze serveru) a bude se proti tomu bránit. 4

http://www.google.com/trends Neaktivn´ım uˇzivatel˚ um, kteˇr´ı se v´ıce neˇz 6 mˇes´ıc˚ u nepˇrihlás´ı, je jejich u ´ˇcet smazán [36]. 6 http://www.facebook.com/apps/site_scraping_tos.php 7 Soubor, kter´ y povoluje robot˚ um procházet urˇcité ˇcásti webové prezentace. 5

12


Které webové stránky procházet?

Jako pˇr´ıklad uved’me blokaci IP adres s vysok´ ym poˇctem poˇzadavk˚ u, nebo pouˇzit´ı 8 CAPTCHA kód˚ u. V takovém pˇr´ıpadˇe by pro naˇse u ´ˇcely bylo vhodné zváˇzit zmˇenu OSN. Dalˇs´ı moˇznost´ı by mohlo b´ yt z´ıskán´ı dat z webov´ ych archiv˚ u, jako napˇr. http://www.archive.org. Ty ale nejsou pˇr´ıliˇs aktuáln´ı a obsahuj´ı pouze zlomek poˇzadovan´ ych webov´ ych stránek. Alternativn´ı moˇznost´ı by bylo z´ıskat data z webové cache Google.com, coˇz je m´ısto, kde Google.com uchovává kopie webov´ ych stránek, které proˇsel jejich robot [28]. Do této cache se dá dostat napˇr. pˇres adresu: http://webcache.googleusercontent.com/search?q=cache:adresa Pˇr´ıpadnˇe ve vyhledávaˇci Google.com vyhledat cache:adresa. Tato cache vˇsak téˇz neobsahuje veˇskeré poˇzadované stránky a poˇcet pˇr´ıstup˚ u do n´ı m˚ uˇze b´ yt omezen.

3.4

Kter´ e webov´ e str´ anky proch´ azet?

Kaˇzd´ y uˇzivatel, kter´ y si na OSN Lidé.cz zaloˇz´ı u ´ˇcet, dostane pˇridˇelen´ y profil, na unikátn´ı adrese http://profil.lide.cz/Jm´ enoUˇ zivatele/profil. Tato u ´vodn´ı stránka obsahuje struˇcné informace o uˇzivateli, nˇekolik jeho pˇrátel a nástˇenku (slouˇz´ıc´ı jako vzkazn´ık, kde spolu uˇzivatelé mohou veˇrejnˇe komunikovat). Dalˇs´ımi stránkami jsou: • o-mne • moji-pratele • maji-me-v-pratelich • fotogalerie • videa Stránka o-mne obsahuje veˇskeré informace, které o sobˇe uˇzivatel uvedl, jako napˇr. jeho záliby, vˇek, bydliˇstˇe aj. Stránka moji pˇ ra ´tel´ e je rozdˇelena na dvˇe ˇca´sti. Prvn´ı ˇca´st moji-pratele obsahuje seznam uˇzivatel˚ u, které majitel profilu povaˇzuje za své pˇra´tele. Druhá ˇcást, majime-v-pratelich je seznam uˇzivatel˚ u, kteˇr´ı povaˇzuj´ı majitele profilu za svého pˇr´ıtele. Tyto dva seznamy se pˇri nepovinné autorizaci (ˇzádosti o navázán´ı pˇra´telstv´ı nen´ı tˇreba potvrzovat), na rozd´ıl od nˇekter´ ych jin´ ych OSN, nemus´ı shodovat. V tom pˇr´ıpadˇe se jedná o orientovaná spojen´ı. 8

Completely Automated Public Turing test to Tell Computers and Humans Apart.

13


Které webové stránky procházet?

Pokud vezmeme v u ´vahu v´ yˇse uvedené, je vhodné z´ıskávat data pouze ze stránek o-mne a moji pˇra´telé. Z ˇcasov´ ych d˚ uvod˚ u – pˇredpokládám staˇzen´ı aˇz 800 tis´ıc profil˚ u (viz ˇca´st 3.2) – jsem se rozhodl stahovat pouze u ´daje ze stránek moji-pratele a o-mne. Z dat, z´ıskan´ ych ze stránek moji-pratele, bude vytvoˇrena a dále analyzována s´ıt’ pˇra´telstv´ı uˇzivatel˚ u této OSN. Data ze stránek o-mne budou pouˇzita pro statistické u ´ˇcely, jejichˇz v´ ysledky budou porovnány s dostupn´ ymi u ´daji.

14

4 Z´ıskán´ı dat V této kapitole naleznete algoritmy a poˇzadavky na webového robota (dále jen robota), nˇekolik poznámek k implementaci a zp˚ usob, jak´ ym budou data ukládána. Na konci kapitoly jsou uvedeny známé problémy a nˇekolik statistik, které jsem pˇri pr˚ uchodu OSN shromáˇzdil. Uˇzivatelskou pˇr´ıruˇcku pro práci s roboty naleznete v pˇr´ıloze A.1.

4.1

V´ ybˇ er vhodn´ eho webov´ eho robota

Pˇri v´ ybˇeru vhodného robota jsem vycházel z nˇekolika jiˇz implementovan´ ych ˇreˇsen´ı 1 2 3 4 (Web-Harvest 2.0 , JSpider 0.5 , JoBo 1.4 , crawler4j aj.). Základn´ı podm´ınkou v´ ybˇeru byla obstojná dokumentace a splnˇen´ı co nejvˇetˇs´ıho poˇctu tˇechto, mnou poˇzadovan´ ych, vlastnost´ı: • Moˇznost ukládat data do databáze, CSV ˇci XML souboru. • Moˇznost pˇreruˇsit stahován´ı a moˇznost pokraˇcovat tam, kde robot naposledy skonˇcil. • Logován´ı akc´ı robota. • Generován´ı základn´ıch statistik stahován´ı. • Nastaven´ı robota vlastn´ım zdrojov´ ym kódem ˇci pomoc´ı XML souboru. • Pˇr´ıtomnost DOM5 parseru, nebo jiné moˇznosti v´ ybˇeru ˇca´sti HTML stránky, která bude ukládána. • Nastaven´ı doby prodlevy mezi stahován´ım jednotliv´ ych stránek. • Moˇznost zpracován´ı nevalidn´ıho HTML. Vˇsechny tyto poˇzadavky splˇ nuje Scrapy [3]. Webov´ y robot, napsan´ y v Pythonu, kterého je moˇzné pomoc´ı vlastn´ıho zdrojového kódu libovolnˇe upravit. 1

http://web-harvest.sourceforge.net http://j-spider.sourceforge.net 3 http://www.matuschek.net/jobo-menu 4 http://code.google.com/p/crawler4j 5 Document Object Model – umoˇzn ˇuje pˇristupovat k dat˚ um uloˇzen´ ym v XML nebo HTML souborech pomoc´ı stromové struktury, viz http://www.w3.org/DOM. 2

15

Z´ıskán´ı dat

4.2

Tvorba webového robota

Tvorba webov´ eho robota

Jako základ, pro tvorbu webového robota, jsem pouˇzil framework Scrapy (v. 0.14) [3]. Framework je moˇzné pouˇz´ıvat i na slabˇs´ıch stroj´ıch (pˇri bˇehu vyuˇz´ıvá cca 50 MB pamˇeti).

4.2.1

Ukl´ ad´ an´ı dat a n´ avrh datab´ azov´ e struktury

Pro dalˇs´ı práci, jsem se rozhodl ukládat data v relaˇcn´ı databázi z následuj´ıc´ıch d˚ uvod˚ u: a) poskytuje dostateˇcnou rychlost; b) oproti XML souboru bude objem dat menˇs´ı; c) data jsou ukládána postupnˇe a nehroz´ı tak jejich ztráta; d) potˇrebná data lze snadno a rychle vyhledávat; e) oproti grafov´ ym databáz´ım mám s jejich pouˇz´ıván´ım zkuˇsenosti. To umoˇzn´ı rychlejˇs´ı v´ yvoj a zbude tak v´ıce ˇcasu na z´ıskán´ı a anal´ yzu dat. Jako c´ılovou relaˇcn´ı databázi jsem vybral MySQL6 Community Server (v. 5.5.25a), provozovanou na lokáln´ım stroji. Toto ˇreˇsen´ı nab´ız´ı dostateˇcnou v´ ykonnost, je ˇs´ıˇreno pod GPL7 licenc´ı, je pˇrenositelné a s vyuˇzit´ım nástroje phpMyAdmin8 nab´ız´ı pˇr´ıjemné uˇzivatelské rozhran´ı. Robot byl na databázi napojen pomoc´ı knihovny MySQLdb9 . Na obr. 4.1 m˚ uˇzete vidˇet strukturu navrˇzené databáze. Mezi tabulkami profil, hrany a uzivatel jsem zvolil kardinalitu 1:1. To, v pˇr´ıpadˇe potˇreby omezen´ı datového objemu, umoˇzn´ı pracovat pouze s ˇca´st´ı databáze. V pˇr´ıpadˇe odpojen´ı se téˇz omez´ı poˇcet poloprázdn´ ych“ záznam˚ u, které by vznikly pˇri pouˇzit´ı jedné tabulky. ” U tabulky hrany jsem pro atribut pratele zvolil kompaktnˇejˇs´ı zp˚ usob uchováván´ı dat. Tento atribut je uchováván jako textov´ y seznam. Hlavn´ım d˚ uvodem pro pouˇzit´ı této konstrukce, byl pˇredpoklad relativnˇe velkého pr˚ umˇerného poˇctu pˇrátel jednotliv´ ych uˇzivatel˚ u – dle vizuáln´ı kontroly cca 30 - 50. Testy ukázaly, ˇze tento zp˚ usob uloˇzen´ı m˚ uˇze uˇsetˇrit pˇri pˇredpokládaném poˇctu 40 milion˚ u hran aˇz 400 MB. Stejn´ y formát pak lze pouˇz´ıt i pro reprezentaci s´ıtˇe v programech, které s n´ı dále pracuj´ı (jako napˇr. Pajek XXL, Gephi aj., viz ˇcást 6.1). 6

http://www.mysql.com GNU General Public License – licence pro svobodn´ y software (viz http://www.gnu.org). 8 http://www.phpmyadmin.net 9 http://sourceforge.net/projects/mysql-python 7

16

Z´ıskán´ı dat


Obr. 4.1: Struktura pouˇzité databáze.

4.2.2

Architektura, algoritmy a pouˇ zit´ e technologie

Minimalizace rizika odpojen´ı Pˇri návrhu robota jsem vycházel z potenciáln´ıho hroz´ıc´ıho odpojen´ı robota od OSN. V prvn´ı ˇradˇe jsem se proto rozhodl pro z´ıskán´ı s´ıtˇe pˇrátelstv´ı, která bude dále analyzována (viz kapitola 6). Data pro statistické u ´ˇcely pak stahovat paralelnˇe z webové cache spoleˇcnosti Google.com (viz ˇcást 3.3), ˇci je stahovat, po z´ıskán´ı s´ıtˇe pˇra´telstv´ı, pˇr´ımo z OSN Lidé.cz. Takto rozloˇzené zat´ıˇzen´ı by mˇelo stahován´ı urychlit a zmenˇsit riziko odpojen´ı. Jako prodleva mezi stahován´ım jednotliv´ ych stránek byla zvolena jedna vteˇrina. To by mˇelo zv´ yˇsit pravdˇepodobnost, ˇze robot nebude odpojen, pˇr´ıpadnˇe bude odpojen aˇz po z´ıskán´ı vˇetˇs´ıho mnoˇzstv´ı dat. Robota je moˇzné v libovolnou chv´ıli pozastavit a pˇri dalˇs´ım spuˇstˇen´ı pokraˇcovat tam, kde naposledy pˇrestal. Tato vlastnost by také mˇela zmenˇsit riziko odpojen´ı. Z´ısk´ an´ı potˇ rebn´ ych dat Jelikoˇz veˇskeré profily, maj´ı stejnou strukturu (liˇs´ı se pouze vzhledem10 ) a jedná se o relativnˇe mal´ y HTML dokument, je pro z´ıskán´ı dat vhodné pouˇz´ıt DOM parser 10

Uˇzivatelé si mohou vybrat z nˇekolika tzv. skin˚ u, které pomoc´ı r˚ uzn´ ych kaskádov´ ych styl˚ u mˇen´ı vzhled jejich profilu.

17

Z´ıskán´ı dat


a potˇrebná data z´ıskat pomoc´ı XPath11 cest. Pˇri zmˇenˇe struktury z´ıskávan´ ych dokument˚ u je vˇsak nutné aktualizovat zastaralou XPath cestu. Protoˇze zdrojov´ y kód zpracovávan´ ych HTML soubor˚ u je tvoˇren v´ıce neˇz tis´ıcem ˇrádk˚ u, vyuˇzil jsem pro urˇcen´ı XPath cest nástroj˚ u jako XPath Helper ˇci FireBug. Strategie proch´ azen´ı Flickr

LiveJournal

Jako v´ ychoz´ı body, ze kter´ robot zaˇcne OSN procházet, jsem urˇcil1,846,198 pseudonáhodné5,284,457 Number ofych users of user population crawled uˇzivatele s pˇrihléEstimated dnut´ım nafraction geografickou rozmanitost jejich bydliˇstˇe26.9% a poˇctu jejich 95.4% Dates of crawl Jan 9, 2007 Dec 9 - 11, 2006 O pˇra´tel. Number of friend links 22,613,981 77,402,652 Average number of friends per user 12 12.24 16.97 Pro procházen´ı OSN jsem pouˇzsymmetric il algoritmus DFS (ve frameworku Scrapy reali- 73.5% Fraction of links 62.0% zovan´ y zásobn´ıkem), kter´ by, na rozd´ıl od BFS13 , mˇel i pˇri odpojen´ ı poskytnout7,489,073 Number ofy user groups 103,648 Average number of groups memberships per user 4.62 pˇresnˇejˇs´ı u ´daje napˇr. o exponentu konektivity nebo o pr˚ umˇerné délce nejkratˇs´ıch 21.25

cest (ASPL), viz [30]. Dalˇs´ı algoritmus, pomoc´ı kterého lze OSN procházet, m˚ uˇzete Table 1: High-level statistics of our social networking sit nalézt v [18]. Jedná se o tzv. Uniform Sampling. Ten je zaloˇzen na procházen´ı náhodn´ ych adres profil˚ u, coˇz umoˇzn ˇuje nalezen´ı profil˚ u z v´ıce komponent. Vzhledem 4.1.2 only ı,forward k pˇredem neomezen´ emu Using poˇctu variac´ tvoˇr´ıc´ıchlinks uˇzivatelské jméno, ale nen´ı pro4.2.1 naˇse Flickr Flickr w ( ww.flickr.com u ´ˇcely vhodn´ y. Crawling directed graphs, as opposed to undirected graphs, presents additional challenges. In particular, many sgraph

a social network. Th

only by d˚ following links proch´ in theaforward direcfrom a crawl of th Jak bylo dˇr´ıve can zm´ınˇ eno,bez crawled ˇcasov´ ych uvod˚ u jsem zel pouze stránku is moji9th, and contain tion (i.e., one cannot easily determine the set of nodes h whic pratele (obsahuj´ıc´ı v´ ystupn´ı hrany). To mohlo zp˚ usobit nekompletn´ı zpracová2007, n´ı links. Flickr exports a point into a given node). Using only forward links does not komponenty, viz obr. 4.2. Z obrázku je vidˇet, ˇze pˇri tomto pˇr´ıstupu se mohou vywe used this API to necessarily crawl an entire WCC; instead, it explores the skytovat uˇzivatel´ e, patˇr´ıc´ı do stejné komponenty, kteˇr´ı nebudou nalezeni, pokud na group membership in connected component reachable from the set of seed users. nˇe nesmˇeˇruje ˇza´This dná limitation vstupn´ı hrana. Lze sak pˇredpokl´ adat,online ˇze pro s´ıt’ only allows us Flickr is typical forvˇ studies that crawl netzkoumanou nebudou pˇr´ıliˇs v´ y znamn´ ı. we were unable to cra works, including measurement studies of the Web [12].

the fraction of users w our crawl, we perform SLEDOVÁNÍ the fact that the vast m VÝSTUPNÍCH the form of [randoml HRAN generated 100,000 ra a possible pool of 90 of these were assigne a random sample of F Among these 6,902 START discovered during ou SLEDOVÁNÍ notpreviously discove VSTUPNÍCH A starting at each user t VÝSTUPNÍCH HRAN reach our set of previo 250 (5.0%) of the mis Figure 1: Users reached by crawling different link Obr. 4.2:types. Ukázka nalezen´ ych vrchol˚ u pˇrused, i následov´ an´ı reach v´ ystupn´ıch hran and were definitively i If only forward links are we can orientovan´ s´ıti. Pˇrevzato [30]. both sively say that the rem only the vinner cloud e(shaded cloud); z using not attached to the W forward and reverse links crawls the entire WCC 11 who points to them a Viz http://www.w3schools.com/xpath. (dashed cloud). 12 Depth-first search – prohled´ av´ an´ı do hloubky. of these have no forw 13 Breadth-first search – prohled´ aván´ı do ˇs´ıˇrky. connected at all. Figure 1 shows an example of a directed graph crawl. The Finally, to explore h users reached by following only forward links are shown in connected, we crawled the shaded cloud, and those reached using both forward and users as seeds, and reverse links are shown in the dashed cloud. Using both forcrawl. We found only ward and reverse links allows 18 us to crawl the entire WCC, the connected compo while using only forward links results in a subset of the in the original crawl. WCC. were singleton nodes had one link, 620 (5.4 4.2 Crawling social networks (20.3%) had four or We now discuss our methodology for crawling each of the

Z´ıskán´ı dat


Rozdˇ elen´ı program˚ u a popis algoritm˚ u Pro procházen´ı OSN Lidé.cz vznikli celkem tˇri roboti. SNABot – pro procházen´ı s´ıtˇe pˇra´telstv´ı. SNABot-Profily – pro procházen´ı profil˚ u a SNABot-Centra – pro procházen´ı center (viz popis problému s centry v ˇcásti 4.4). Algoritmus nejd˚ uleˇzitˇejˇs´ıch akc´ı robota SNABot: 1) Projdi v´ ychoz´ı stránku/y a uloˇz do zásobn´ıku ˇza´dané odkazy14 . 2) Vyjmi ze zásobn´ıku odkaz a odeˇsli poˇzadavek na server. Pokud je zásobn´ık prázdn´ y a nejsou naplánovány dalˇs´ı poˇzadavky, pˇrejdi na 7). 3) Ze z´ıskané odpovˇedi z´ıskej seznam pˇra´tel. 4) Uloˇz do databáze aktuáln´ıho uˇzivatele a jeho pˇrátele (tabulka uzivatele) a v´ ystupn´ı hrany uˇzivatele (tabulka hrany). Pokud bude pˇrátel v´ıce neˇz 500, nastav záznamu v hrany.znovu pˇr´ıznak na 1. 5) Pˇridej do zásobn´ıku odkazy na uˇzivatelovi pˇra´tele. 6) Pokud je zásobn´ık prázdn´ y a neexistuj´ı dalˇs´ı poˇzadavky, pˇrejdi na 7), jinak opakuj 2). 7) Ukonˇci program. Dalˇs´ı roboti pracuj´ı obdobnˇe. Robot zpracovávaj´ıc´ı profily, procház´ı iteraˇcnˇe databázi a v kaˇzdé iteraci naplánuje nˇekolik odkaz˚ u, které budou dále procházeny. Robot pro extrakci kontakt˚ u center, ˇreˇs´ıc´ı problém s centry (viz ˇca´st 4.4 – problém s centry), procház´ı iteraˇcnˇe záznamy, které byly oznaˇceny ve ˇctvrtém kroku robotem SNABot. Procház´ı vˇsak mobiln´ı verzi této OSN um´ıstˇenou na http://m.lide.cz15 , generuje a zpracovává pˇredem známé odkazy (z´ıskané z uˇzivatelsk´ ych jmen). T´ım v´ yˇse uveden´ y problém ˇreˇs´ı. Architekturu robot˚ u, zaloˇzen´ ych na frameworku Scrapy, m˚ uˇzete vidˇet na obr. 4.3.

4.2.3

Implementaˇ cn´ı pozn´ amky

V této ˇca´sti je struˇcnˇe uvedeno pouˇzit´ı nˇekter´ ych specifick´ ych konstrukc´ı frameworku Scrapy. Dalˇs´ı implementaˇcn´ı podrobnosti naleznete v oficiáln´ı dokumentaci projektu, viz [3]. 14

Odkazy, na které lze aplikovat pravidla dána regulárn´ımi v´ yrazy, viz ˇcást 4.2.3 Na té existuje str´ ankov´ an´ı, které umoˇzn ˇuje seznamem pˇrátel listovat. Je ovˇsem omezeno pouze stranami 1 aˇz 100. Tzn. maxim´ alnˇe 1200 pˇráteli. Toto stránkován´ı vˇsak lze oklamat“ pomoc´ı ” editace URL adresy. V té je moˇzné nastavit offset a pomoc´ı nˇej proj´ıt veˇskeré pˇrátele. 15

19

Z´ıskán´ı dat


Plánovač Internet Požadavky

Požadavky

Scrapy Engine

Databáze

Downloader

Odpovědi

Položky

Roboti

Obr. 4.3: Ukázka architektury webov´ ych robot˚ u, zaloˇzen´ ych na frameworku Scrapy. Obrázek byl pˇrevzat z [3]. Robotovi je moˇzné nastavit pravidla, které pˇriˇrazuj´ı stránkám r˚ uzné akce a lze s jejich pomoc´ı obsah stránek zpracovávat. Toho lze doc´ılit kódem: rules = ( Rule(SgmlLinkExtractor(allow = "profil.lide.cz/(.+)/moji-pratele/"), callback ="pratele_parse"), Rule(SgmlLinkExtractor(allow = "profil.lide.cz/(.+)/o-mne/"), callback = "profil_parse") )

Kde ˇretˇezec pˇriˇrazen´ y allow je regulárn´ı v´ yraz. Pokud odkaz bude odpov´ıdat alespoˇ n jednomu regulárn´ımu v´ yrazu, uplatn´ı se na nˇej metoda maj´ıc´ı stejn´ y název, jako ˇretˇezec pˇriˇrazen´ y promˇenné Callback. Pokud robot nalezne odkazy, na které ˇza´dná pravidla uplatnit nelze, budou ignorovány. V´ ychoz´ı adresy se urˇcuj´ı jako start_urls = ["www.prvni.cz", ... ]. Na v´ ychoz´ı adresy nejsou uplatˇ nována pravidla – tzn. v´ ychoz´ı adresy nebudou zpracovány! Proto doporuˇcuji v´ ychoz´ı adresy napˇr. podstrˇcit“ v lokáln´ım souboru jako start_urls ” = ["file:start.html"]. Adresy obsaˇzené v souboru jiˇz budou standardnˇe zpracovány. V z´ıskaném HTML dokumentu lze pomoc´ı XPath cest vyb´ırat data následovnˇe: xpath = HtmlXPathSelector(response) xpath.select("//div[@id=’profileTitle’]/h2/text()").extract()[0]

20

Z´ıskán´ı dat

Z´ıskaná data

Kde response je z´ıskan´ y HTML dokument a ˇretˇezec v metodˇe select XPath cesta, pomoc´ı n´ıˇz lze v dokumentu vybrat poˇzadovaná data. Metoda extract vrac´ı unicódov´ y ˇretˇezec vybran´ y pomoc´ı XPath cesty. ˇ Casovou prodlevu mezi stahován´ım jednotliv´ ych stránek lze mˇenit pomoc´ı promˇenné download_delay. V aktuáln´ım nastaven´ı roboti zapisuj´ı veˇskeré informace do soubor˚ u log-rrrr-mm-dd.txt. Stupeˇ n v´ ypis˚ u lze zm´ırnit napˇr. pouze na chybové hláˇsky zmˇenou hodnoty LOG_LEVEL na ERROR v souboru settings.py. Dalˇs´ı zmˇenu nastaven´ı je moˇzné provést v témˇze souboru.

4.3

Z´ıskan´ a data

Tisíce

Počet nalezených profilů

Sbˇer dat pro vytvoˇren´ı s´ıtˇe pˇrátelstv´ı (tzn. stránek moji-pratele) neprob´ıhal kontinuálnˇe, robot byl nˇekolikrát pozastaven (nejˇcastˇeji po 12 hodinách bˇehu). Sbˇer dat trval pˇribliˇznˇe mˇes´ıc, pˇriˇcemˇz robot nebyl od OSN odpojen. Pˇri pr˚ uchodu OSN Lidé.cz bylo celkem nalezeno 589 374 uˇzivatel˚ u (vˇcetnˇe duplicit, viz ˇcást 4.4). Z obr. 4.4 m˚ uˇzete vidˇet, ˇze pro nalezen´ y poˇcet uˇzivatel˚ u témˇeˇr plat´ı Paretovo pravidlo [10] (pravidlo 80/20), v následuj´ıc´ım kontextu: Po pr˚ uchodu a zpracován´ı prvn´ıch 20% ” uˇzivatel˚ u, nalezneme 80% uˇzivatel˚ u z celkového poˇctu“. 700 600 500 400 300

200 100 0 0

100

200

300

400

500

600 Tisíce

Počet prošlých profilů

Obr. 4.4: Poˇcet nalezen´ ych uˇzivatel˚ u. Celkov´ y poˇcet u ´spˇeˇsnˇe proˇsl´ ych stránek moji-pratele je 574 988. Po odeˇcten´ı duplicitn´ıch uˇzivatel˚ u (cca 10 tis´ıc), zjist´ıme, ˇze za mˇes´ıc bylo smazáno pˇribliˇznˇe 4,5 tis´ıce profil˚ u. Pˇri stahován´ı profil˚ u z webové cache spoleˇcnosti Google.com byl robot odpojen (viz 4.4 – Odpojen´ı od cache Google.com). Mimo to se ukázalo, ˇze tato cache obsahuje pouze cca 58% poˇzadovan´ ych stránek. Data ze stránek o-mne proto byla z´ıskána pˇr´ımo z c´ılové OSN, po z´ıskán´ı s´ıtˇe pˇrátelstv´ı. Stahován´ı trvalo cca 40 dn´ı, pˇriˇcemˇz 21

Z´ıskán´ı dat

Známé problémy

opˇet neprob´ıhalo nepˇretrˇzitˇe. Dalˇs´ı zaj´ımavost´ı je, ˇze pˇri posledn´ıch iterac´ıch stahován´ı – cca o tˇri mˇes´ıce pozdˇeji po zahájen´ı stahován´ı stránek moji-pratele – byl pomˇer neexistuj´ıc´ıch stránek (smazan´ ych profil˚ u) k poˇctu nalezen´ ych profil˚ u 1,6 : 23,5. Tzn., ˇze za tˇri mˇes´ıce bylo smazáno cca 7% uˇzivatelských u ´ˇct˚ u. To, dle mého názoru, m˚ uˇze b´ yt jednak d˚ usledkem vysoké dynamiky OSN nebo to m˚ uˇze ukazovat na postupn´ y odliv“ uˇzivatel˚ u (viz ˇcást 3.2). ” Robot procházej´ıc´ı mobiln´ı verzi OSN, proˇsel za cca 2,5 hodiny vˇsechny oznaˇcené záznamy tvoˇrené 58 centry s v´ıce neˇz 500 pˇráteli. Ze 7 tis´ıc z´ıskan´ ych stránek tak 16 mohl z´ıskat aˇz 27 tis´ıc nov´ ych hran . Roboti proˇsli v´ıce neˇz 1,1 milionu webových stránek. Pr˚ umˇern´ y poˇcet staˇzen´ ych stránek za minutu se pohyboval v intervalu 50-55 stránek/min. Pˇri stahován´ı bylo odesláno na server cca 380 MB poˇzadavk˚ u a staˇzeno cca 4,75 GB dat. Z tˇechto dat vznikla databáze maj´ıc´ı pˇribliˇznˇe 9,6 milionu ˇra´dk˚ u o velikosti 370 MB. SQL Dump této databáze naleznete na pˇriloˇzeném DVD.

4.4

Zn´ am´ e probl´ emy

Pˇri z´ıskáván´ı dat se vyskytlo nˇekolik problém˚ u, které budou dále popsány. Probl´ em s centry Ukázalo se, ˇze poˇcet zobrazovan´ ych pˇrátel na stránce moji-pratele je omezen horn´ı hranic´ı 500 pˇra´tel (ˇrazeno abecednˇe). Tento problém se podaˇrilo odstranit dodateˇcn´ ym robotem, kter´ y centra znovu projde (viz ˇcást 5.2.2 – robot pro extrakci kontakt˚ u center). Probl´ em s diakritikou v n´ azvech profil˚ u Pˇri stahován´ı dat bylo zjiˇstˇeno, ˇze existuje minoritn´ı mnoˇzstv´ı uˇzivatel˚ u, kteˇr´ı si v minulosti vytvoˇrili profil se jménem, obsahuj´ıc´ı diakritiku. To v souˇcasnosti nen´ı moˇzné. Tyto profily jsou pak spojeny s profily bez diakritiky (napˇr. uˇzivatel = uzivatel). Tvar zobrazovaného jména v seznamech pˇrátel nen´ı normalizován. Tato skuteˇcnost vytváˇr´ı v databázi duplicitn´ı záznamy, mezi které jsou vstupn´ı hrany rozdˇeleny. Pˇred samotnou anal´ yzou OSN je nutné tyto duplicity odstranit. Tento problém ˇreˇs´ı aplikace SNABot-Nastroje, která umoˇzn ˇuje profily sjednotit a pˇresmˇerovat chybné vstupn´ı hrany duplicit. Pro budouc´ı práci doporuˇcuji robota upravit tak, aby zpracovával pouze u ´ˇcty bez diakritiky. Nebude tak tˇreba u ´ˇcty sjednocovat a dle namˇeˇren´ ych u ´daj˚ u, se projde cca o 10 tis´ıc stránek ménˇe. 16

Kaˇzdé centrum mˇelo 500 hran, tzn. 29 tis´ıc jich jiˇz existovalo. Z kaˇzdé stránky, vyjma posledn´ıch, bylo z´ısk´ ano 8 hran.

22

Z´ıskán´ı dat

Známé problémy

Odpojen´ı od cache Google.com Dalˇs´ım problémem se ukázalo paraleln´ı stahován´ı dat z cache Google.com. Jiˇz pˇri testován´ı byl robot odpojen pˇribliˇznˇe po zaslán´ı sta poˇzadavk˚ u. Nepomohlo ani zv´ yˇsen´ı ˇcasové prodlevy mezi stahován´ım jednotliv´ ych stránek. V [22] autor, kter´ y z´ıskával data z Google Scholar17 , uvád´ı cituji: Experimentálnˇe bylo zjiˇstˇeno, ˇze ide” a´ln´ı je pozastavit program na jednu hodinu po kaˇzd´ ych 150 uskuteˇcnˇen´ ych dotazech. Je ovˇsem moˇzné, ˇze po vˇetˇs´ım poˇctu pˇr´ıstup˚ u z jedné IP adresy, bude nutné limity zpˇr´ısnit.“ Kv˚ uli neefektivitˇe (150 z´ıskan´ ych stránek za hodinu oproti 3600), jsem od paraleln´ıho stahován´ı dat z této cache upustil a rozhodl se toto ˇreˇsen´ı vyuˇz´ıt pouze v pˇr´ıpadˇe, pokud bude robot SNABot z OSN Lidé.cz odpojen. Nepˇ retrˇ zit´ a zmˇ ena dat Posledn´ım problémem, kter´ y byl pˇredem znám, ale nebyl oˇcekáván v takovém rozsahu, je neustálá zmˇena OSN. Jejich velikost a neustálá zmˇena znemoˇzn ˇuje z´ıskán´ı vˇsech poˇzadovan´ ych informac´ı ve stejném ˇcase. V naˇsem pˇr´ıpadˇe to napˇr. zp˚ usobuje existenci uˇzivatel˚ u, které nˇekdo povaˇzuje za pˇra´tele, ale neˇz se robot dostal k jejich zpracován´ı, jejich u ´ˇcet byl smazán. Nebylo tak moˇzné z´ıskat jejich pˇrátele a profily.

17

http://scholar.google.com

23

5 Statistické výstupy a jejich porovnán´ı s dostupn´ ymi daty V této kapitole naleznete nˇekolik statistik, které jsou následnˇe porovnány s daty ˇ eho statistického u ˇ U) ´ ˇci jin´ Cesk´ ´ˇradu (CS ymi zdroji. Tyto informace lze pouˇz´ıt napˇr. pro urˇcen´ı nejvˇetˇs´ı c´ılové skupiny. Pokud se potvrd´ı, ˇze vˇetˇsina dat souhlas´ı s jiˇz proveden´ ymi mˇeˇren´ımi, mohou b´ yt pˇr´ınosná i pro sociology (viz dále). Následuj´ıc´ı informace byly z´ıskány z databáze profil˚ u, obsahuj´ıc´ı v´ıce neˇz 550 tis´ıc profil˚ u, kterou se podaˇrilo vytvoˇrit robotem SNABot-Profily (viz kapitola 4). Tvorba graf˚ u a v´ ysledk˚ u je z ˇcásti zautomatizována. Aplikace SNABot-Nastroje umoˇzn ˇuje vytvoˇrit CSV soubory (viz pˇr´ıloha A.3) s poˇzadovan´ ymi daty a z tˇech pak pomoc´ı R1 skript˚ u (nacházej´ıc´ıch se na pˇriloˇzeném DVD) vygenerovat dále uvedené grafy. Pˇri aktualizaci dat je tak moˇzné následuj´ıc´ı statistiky pomˇernˇe snadno aktualizovat.

5.1

Jak´ e informace zjiˇ st’ovat a z jak´ eho d˚ uvodu?

C´ılem této ˇca´sti je vytvoˇrit ukázkovou mnoˇzinu otázek, t´ ykaj´ıc´ı se dat z´ıskan´ ych z c´ılové OSN, které budou dále zkoumány. Na základˇe v´ ysledk˚ u pak z´ıskat pˇredstavu, nakolik jsou data udávaná uˇzivateli shodná s u ´daji uvádˇen´ ymi jin´ ymi zdroji a zjistit tak jejich relevantnost. V pˇr´ıpadˇe jejich shody by stálo za zváˇzen´ı, zda neprovádˇet nˇekteré kvantitativn´ı sociologické pr˚ uzkumy anal´ yzou dat z´ıskan´ ych ze sociáln´ıch s´ıt´ı. Tato alternativa by oproti dotazn´ıkové formˇe poskytla vˇetˇs´ı poˇcet respondent˚ u a uˇsetˇrila by náklady spojené s distribuc´ı a následn´ ym ruˇcn´ım vyhodnocován´ım dotazn´ık˚ u. Jako ukázkovou mnoˇzinu jsem zvolil následuj´ıc´ı otázky: Populace zkouman´ e OSN • Jaké je vˇekové sloˇzen´ı uˇzivatel˚ u? • Jak jsou uˇzivatelé rozm´ıstˇeni dle jednotliv´ ych kraj˚ u? • Plat´ı Milgramem pozorovan´ yu ´kaz z ˇca´sti 2.3 – stejné pohlav´ı se kontaktuje (v naˇsem pˇr´ıpadˇe pˇra´tel´ı) ˇcastˇeji? 1

Jedn´ a se o software umoˇznuj´ıc´ı, pomoc´ı jazyka R, statistické v´ ypoˇcty a tvorbu graf˚ u. Viz http://www.r-project.org.

24

Statistické výstupy

Obyvatelstvo

Ciz´ı jazyky a vzdˇ el´ an´ı • Jaké je sloˇzen´ı uˇzivatel˚ u dle nejvyˇsˇs´ıho dosaˇzeného vzdˇelán´ı? • Kolika ciz´ımi jazyky uˇzivatelé hovoˇr´ı? • Bude nejv´ıce uvádˇen´ ym ciz´ım jazykem angliˇctina2 následována nˇemˇcinou? • Souvis´ı poˇcet ciz´ıch jazyk˚ u, kter´ ymi uˇzivatel hovoˇr´ı, s dosaˇzen´ ym vzdˇelán´ım? Mladistv´ı • Kolik procent mladistv´ ych kouˇr´ı a/nebo konzumuje alkohol? • Kouˇr´ı a konzumuj´ı alkohol v´ıce chlapci, nebo d´ıvky? Obl´ıben´ e sporty a hudba • Jaké jsou nejpopulárnˇejˇs´ı sporty a hudebn´ı ˇzańry?

5.2

Obyvatelstvo

Z obr. 5.1 je vypl´ yvá, ˇze nejv´ıce zastoupenou skupinou v této OSN jsou lidé ve vˇeku 15 - 29 let. Pr˚ umˇern´ y vˇek je 26 let. 55,8% uˇzivatel˚ u sv˚ uj vˇek neuvád´ı. V populaci ve vˇeku 15 - 19 jasnˇe pˇrevládaj´ı ˇzeny, dalˇs´ı vˇekové skupiny jsou pomˇernˇe vyrovnané. Celkové zastoupen´ı uˇzivatel˚ u tvoˇr´ı 45,5% muˇz˚ u a 54,5% ˇzen. ˇ U ´ Vˇekové sloˇzen´ı uˇzivatel˚ u ani sloˇzen´ı pohlav´ı neodpov´ıdaj´ı u ´daj˚ um uvádˇen´ ymi CS (50,9% ˇzen a 49,1% muˇz˚ u, viz soubor csu-kr-obyvatele.xls na pˇriloˇzeném DVD). Neshoduj´ı se ani s oficiáln´ımi u ´daji uvádˇen´ ych na OSN3 a to sice: 53% muˇz˚ u a 47% ˇzen. Ty vycházej´ı z mˇeˇren´ı spoleˇcnosti Netmonitor.cz (jako vzorek bylo pouˇzito 2 889 respondent˚ u). Je vˇsak tˇreba vz´ıt v u ´vahu odliˇsnou metodologii tˇechto mˇeˇren´ı. Oficiáln´ı statistiky vycház´ı z u ´daj˚ u poskytnut´ ych návˇstˇevn´ıky této OSN nikoliv ze sloˇzen´ı profil˚ u. Z obr. 5.2 vypl´ yvá, ˇze sloˇzen´ı uˇzivatel˚ u této OSN procentuálnˇe odpov´ıdá sloˇzen´ı ˇ obyvatelstva v CR dle kraj˚ u (s toleranc´ı 2 - 3% u jednotliv´ ych kraj˚ u). V´ yraznou anomálii tvoˇr´ı pouze uˇzivatelé z Plzeˇ nského kraje. V tomto kraji je zkoumaná OSN velmi populárn´ı, zejména v Plzni. 72,3% uˇzivatel˚ u z Plzeˇ nského kraje uvád´ı ve svém ˇ ´ profilu mˇesto Plzeˇ n. Data z CSU uvád´ı, ˇze pouze 56,4% obyvatel z Plzeˇ nského kraje se nacház´ı v okresech Plzeˇ n-mˇesto, Plzeˇ n-jih a Plzeˇ n-sever (ˇci pouze 32,3% Plzeˇ nmˇesto). 19,4% uˇzivatel˚ u kraj neuvedlo. 2 3

Slovenˇstina zde nen´ı zahrnuta, jelikoˇz na zkoumané OSN ji nen´ı moˇzné vybrat. Viz http://onas.seznam.cz/cz/lide-cz.html.

25


Obyvatelstvo

20

Pohlaví Muži Ženy

Počet (%)

15

10

5

60-64

55-59

50-54

45-49

40-44

35-39

30-34

25-29

20-24

15-19

10-14

5-9

0

Věková skupina (dle ČSU)

Obr. 5.1: Vˇekové sloˇzen´ı uˇzivatel˚ u OSN Lidé.cz dle pˇetilet´ ych vˇekov´ ych skupin a pohlav´ı.

20

Zdroj Lidé.cz ČSU

Počet (%)

15

10

5

0 Jh

Jm Ka

Kr

Li

Mo

Ol

Pa

Pl

Pr

St

Ús

Vy

Zl

Kraj

ˇ dle kraj˚ Obr. 5.2: Porovnané sloˇzen´ı uˇzivatel˚ u OSN Lidé.cz s obyvateli CR u. 26


Ciz´ı jazyky a vzdˇelán´ı

´ Ukaz, pozorovan´ y Milgramem, o ˇcastˇejˇs´ım vyuˇz´ıván´ı kontakt˚ u stejného pohlav´ı se neprokázal. Naopak pouze 12,5% ze vˇsech pˇrátelstv´ı tvoˇr´ı pˇrátelstv´ı mezi muˇzi a 30,1% mezi ˇzenami.

5.3

Ciz´ı jazyky a vzdˇ el´ an´ı

Informace o nejvyˇsˇs´ım dosaˇzeném vzdˇelán´ı byly zjiˇst’ovány u uˇzivatel˚ u ve vˇeku 15 let a starˇs´ıch. Nejv´ıce je v této OSN zastoupena skupina uˇzivatel˚ u s maturitou – 34,7%, stˇredn´ım vzdˇelán´ım bez maturity – 33,5% a základn´ım vzdˇelán´ım – 23,7%. Vysokoˇskolské vzdˇelán´ı je zde zastoupeno cca 8%. Své vzdˇelán´ı uvád´ı 59,4% uˇzivatel˚ u. ˇ U ´ uvád´ı tyto u CS ´daje4 : základn´ı vzdˇelán´ı 18%, stˇredn´ı vzdˇelán´ı bez maturity 33%, stˇredn´ı vzdˇelán´ı s maturitou 34% a vysokoˇskolské vzdˇelán´ı 15%. Z toho vypl´ yvá, ˇze tuto OSN vyuˇz´ıvá vˇetˇs´ı procentuáln´ı ˇca´st lid´ı se základn´ım vzdˇelán´ım, neˇzli je ˇ Naopak zde nejsou pˇr´ıliˇs zastoupeni lidé vysokoˇskolsky vzdˇelan´ı. pr˚ umˇer v CR. Poˇcet ciz´ıch jazyk˚ u, kter´ ymi uˇzivatelé u ´dajnˇe hovoˇr´ı, naleznete na obr. 5.3b. Procentuáln´ı zastoupen´ı jednotliv´ ych ciz´ıch jazyk˚ u na obr. 5.3a. Tyto v´ ysledky jsou podobné tˇem, které jsou uvádˇeny v [33] (jedná se o pr˚ uzkum mezi obˇcany ve vˇeku 18–69 let, zkoumáno bylo 9 500 domácnost´ı). V tomto v´ yzkumu uvád´ı 40% respondent˚ u znalost jednoho jazyka, 24% dvou a 7% tˇr´ı a v´ıce. 30% dotazovan´ ych nemluv´ı ˇzádn´ ym ciz´ım jazykem. Jazyk angličtina němčina jiný ruština francouzština španělština italština

Počet cizích jazyků žádný jeden dva tři a více

41.3% 37.5%

19.7%

2.1% 3% 4.6%

28.4%

12.2%

9.6% 30.5%

11.1%

(a) Pomˇer v´ yskytu jednotliv´ ych ciz´ıch jazyk˚ u.

(b) Pomˇer poˇctu ciz´ıch jazyk˚ u, kolika u ´dajnˇe uˇzivatelé hovoˇr´ı.

Obr. 5.3: Znalosti ciz´ıch jazyk˚ u. 4

Viz prezentace O. N´ yvlta na pˇriloˇzeném DVD.

27


Mladistv´ı

Nejˇcastˇeji uvádˇen´ ymi ciz´ımi jazyky (dle [33]) jsou: angliˇctina – 45%, nˇemˇcina – 26% a ruˇstina – 23%. V´ yzkum [34] (z roku 2002, kde bylo dotázáno 900 respondent˚ u) uvád´ı, ˇze ruˇstina je zastoupena v nejvˇetˇs´ı m´ıˇre u starˇs´ıch generac´ı. Vzhledem k malému zastoupen´ı, které ve zkoumané OSN tvoˇr´ı, to bude pravdˇepodobnˇe d˚ uvod, proˇc nen´ı uvádˇena ˇcastˇeji.

100

Na obr. 5.4 naleznete grafické znázornˇen´ı závislosti poˇctu jazyk˚ u, které uˇzivatelé této OSN uvádˇej´ı, na jejich dosaˇzeném vzdˇelán´ı. [34] uvád´ı, ˇze nejˇcastˇejˇs´ı forma v´ yuky ciz´ıch jazyk˚ u (u lid´ı ve vˇeku 15 - 30 let, bylo moˇzné vybrat v´ıce moˇznost´ı) je: ˇ ˇ 42% a VS ˇ 21%. Za zaj´ımav´ v´ yuka na SS 60,5%, ZS y fakt tak povaˇzuji to, ˇze lidé se základn´ım vzdˇelán´ım uvádˇej´ı znalost v´ıce jazyk˚ u neˇzli vyuˇcen´ı lidé a velmi podobnou znalost lidem se stˇredn´ım vzdˇelán´ım s maturitou. U vysokoˇskolsky vzdˇelan´ ych lid´ı je v´ yrazn´ y nár˚ ust znalosti tˇr´ı a v´ıce jazyk˚ u. U tˇechto skupin tvoˇr´ı témˇeˇr 25% a v´ıce.

Cizích jazyků:

60 40 0

20

Počet (%) v kat.

80

0 1 2 3 a více

zák

vyu

stř

mat

bak

vys

mag

dok

jin

Vzdělání

Obr. 5.4: Závislost znalosti poˇctu ciz´ıch jazyk˚ u na dosaˇzeném vzdˇelán´ım.

5.4

Mladistv´ı

V s´ıti existuje 27 048 uˇzivatel˚ u mladˇs´ıch 18 let (tj. 11% z uˇzivatel˚ u uvádˇej´ıc´ıch sv˚ uj vˇek). Z toho jich 43,3% uvád´ı, ˇze alespoˇ n pˇr´ıleˇzitostnˇe kouˇr´ı (cca 17,7%) nebo konzumuj´ı alkohol (cca 41,1%). Pouze 16,8% uˇzivatel˚ u mladˇs´ıch 18 let uvád´ı, ˇze 28


Mladistv´ı

nekouˇr´ı ani nekonzumuj´ı alkohol. 25% jich o sobˇe tyto u ´daje neuvád´ı a 17,8% uvád´ı pouze jeden u ´daj. V následuj´ıc´ım textu jsou vynechány osoby, které o sobˇe neuvedly obˇe informace (tj. 42,8% mladistv´ ych). Nejv´ıce (23,9%) je zastoupena skupina mladistv´ ych konzumuj´ıc´ıch alkohol, která uvedla, ˇze nekouˇr´ı. Naopak kuˇrák˚ u nekonzumuj´ıc´ıch alkohol je velmi málo (1,4%). Kuˇra´k˚ u konzumuj´ıc´ıch alkohol je 16,5%. Zdá se tak, ˇze vˇetˇsina mladistv´ ych má prvotn´ı zkuˇsenost s alkoholem a ˇca´st z nich poté zaˇcne b´ yt i kuˇra´ky. Podrobnˇejˇs´ı u ´daje naleznete v pˇr´ıloze C.

60 40

Počet (%)

20

Zl

Vy

St

Ús

Pl

Pr

Ol

Pa

Li

Mo

Kr

Ka

Jh

Kraj

Jm

0 Zl

Vy

St

Ús

Pl

Pr

Ol

Pa

Li

Mo

Kr

Ka

Jh

Jm

0

20

10

Počet (%)

30

80

40

100

Porovnán´ı mladistv´ ych kuˇrák˚ u (obr. 5.5a) a konzument˚ u alkoholu (obr. 5.5b) dle kraj˚ u naleznete na obr. 5.5 (vynecháni mladistv´ı bez vyplnˇen´ ych informac´ı). Z tˇechto graf˚ u vypl´ yvá, ˇze nejv´ıce mladistv´ ych kuˇra´k˚ u je v Praze, nejménˇe pak v Plzeˇ nském, Zl´ınském a Moravskoslezském kraji. Nejménˇe mladistv´ ych konzument˚ u alkoholu je opˇet v Moravskoslezském kraji.

Kraj

(a) Porovn´ an´ı mladistv´ ych kuˇráku dle jednotliv´ ych kraj˚ u.

(b) Porovnán´ı mladistv´ ych konzument˚ u alkoholu dle jednotliv´ ych kraj˚ u.

Obr. 5.5: Porovnán´ı mladistv´ ych kuˇrák˚ u a konzument˚ u alkoholu dle kraj˚ u. V [31] (studie omezená na 16 leté studenty) je uvedeno, ˇze mezi mladistv´ ymi se vyskytuje 25,7% kuˇrák˚ u (27,1% chlapc˚ u a 24,2% d´ıvek) a pˇribliˇznˇe 79% mladistv´ ych, kteˇr´ı v posledn´ıch 30 dnech pily alkohol. Pr˚ uzkum byl proveden v roce 2011 a t´ ykal se 3 913 student˚ u. V pˇr´ıpadˇe omezen´ı na mladistvé ve vˇeku 16 let, jich ve zkoumané OSN 74,4 % uvád´ı konzumaci alkoholu a 26,5%, ˇze jsou kuˇráci (vzorek tvoˇrily cca 4 tis´ıce uˇzivatel˚ u a nebyli bráni v u ´vahu mladistv´ı bez vyplnˇené informace). Dále se ze z´ıskan´ ych dat podaˇrilo zjistit (viz tab. 5.1, která bere v u ´vahu mladistvé ve vˇeku 16 let uvádˇej´ıc´ı oba u ´daje), ˇze mezi kuˇra´ky je vˇetˇs´ı procentuáln´ı zastoupen´ı d´ıvek (34,4% oproti 27,8% chlapc˚ u). Konzumace alkoholu je pomˇernˇe vyrovnaná (78,8% d´ıvek oproti 76,9% chlapc˚ u). 29


Obl´ıbené sporty a hudba

Tab. 5.1: Kouˇren´ı a konzumace alkoholu dle pohlav´ı. Pohlav´ı Celkem Alkohol Kouˇren´ı Chlapci D´ıvky

5.5

1430 2536

1127 1951

398 872

Obl´ıben´ e sporty a hudba

Nejˇcastˇeji uvádˇen´ y hudebn´ı ˇzánr je rock. Ten uvád´ı 40,8% uˇzivatel˚ u. Dále pop – 34,8% a hip-hop – 26,3%. Nejménˇe uvádˇen´ ymi ˇzańry jsou opera a opereta 1,4% a swing 1,7%. Práce [19] (bylo dotazováno 440 respondent˚ u) na prvn´ıch dvou m´ıstech uvád´ı téˇz rock a pop (neuvaˇzujeme-li soundtrack). Mezi nejˇcastˇeji uvádˇené sporty v OSN Lidé.cz patˇr´ı kolektivn´ı hry s m´ıˇcem – 33,5%, cyklistika – 29,3% a zimn´ı sporty – 25,6%. Naopak nejménˇe uvádˇen´ ymi sporty jsou parasporty (paraˇsutismus apod.) – 1,7% a jogging – 2%. Zaj´ımavou infografiku o obl´ıbenosti sport˚ u uvád´ı [37]. Zde se na prvn´ım m´ıstˇe um´ıstil fotbal, na druhém cyklistika a na tˇret´ım hokej. Jako nejˇcastˇeji provozovan´ y sport se uvád´ı cyklistika.

5.6

Shrnut´ı kapitoly

V této kapitole bylo uvedeno nˇekolik statistik, které byly porovnány s v´ ysledky z jin´ ych zdroj˚ u. Vˇetˇsina z nich odpov´ıdala v´ ysledk˚ um z jin´ ych zdroj˚ u s pomˇernˇe malou toleranc´ı. Lze tak doporuˇcit pouˇz´ıvat anal´ yzu obsahu OSN jako alternativn´ı formu k z´ıskáván´ı kvantitativn´ıch informac´ı. Jej´ı hlavn´ı v´ yhodou je snadné shromáˇzdˇen´ı velkého objemu dat, které, jak bylo v této kapitole naznaˇceno, jsou dostateˇcnˇe relevantn´ı. Tuto alternativu je vˇsak nutné pouˇz´ıvat s rozmyslem a uvˇedomit si, ˇze nˇekterá data mohou b´ yt, zejména proto, ˇze si uˇzivatelé uvˇedomuj´ı jejich dostupnost, ˇca´steˇcnˇe zkreslená. ´ Udaje uvedené v této kapitole lze napˇr. vyuˇz´ıt k urˇcen´ı, jak velkou c´ılovou skupinu m˚ uˇze oslovit reklamn´ı sdˇelen´ı. Napˇr. reklama s v´ ybavou pro rybáˇre nebo s bˇeˇzeck´ ymi potˇrebami nenalezne pˇr´ıliˇs potencionáln´ıch zájemc˚ u. Naopak reklama napˇr. s v´ ybavou cyklistickou, lyˇzaˇrkou ˇci se vstupenkami na koncert obl´ıbeného rockového zpˇeváka by jich mohla oslovit aˇz nˇekolik des´ıtek, ne-li stovek, tis´ıc.

30

6 Analýza z´ıskané s´ıtˇe V této kapitole naleznete informace o z´ıskané s´ıti, ovˇeˇren´ı, zda odpov´ıdá bezˇskálové topologii (viz 2.2.1), a ˇzebˇr´ıˇcky uˇzivatel˚ u sestavené dle metod Centrality measures (CM), které jsou následnˇe porovnány. Poˇcátek kapitoly tvoˇr´ı struˇcné pˇredstaven´ı pouˇzit´ ych program˚ u a framework˚ u. Obr. 6.1 zobrazuje proces, jak´ ym byla data z´ıskána a zpracována. Transformace (pomocí SNABot-nastroje)

SNABot

.gr

astroje

SNABot-n

Lidé.cz SNABot-profily

DB

SN

AB o

t-n

AB SN

SNABot-centra

as

tro j

e

ot-

Scrapy

SNAP

Pajek

oje

str

na

.net

R

Grafické a statistické výstupy

.csv

Gephi

Obr. 6.1: Proces pouˇzit´ y pro z´ıskán´ı informac´ı z c´ılové OSN.

6.1

V´ ybˇ er vhodn´ eho frameworku

ˇ asteˇcn´ C´ y seznam nástroj˚ u, umoˇzn ˇuj´ıc´ıch anal´ yzu s´ıt´ı, naleznete napˇr. v [7]. Nˇekter´ ym z nich se vˇsak z´ıskanou s´ıt’, kv˚ uli jej´ı velikosti, nepodaˇrilo ani naˇc´ıst. U dalˇs´ıch, vzhledem k neparaleln´ı implementaci a kvadratické ˇci vyˇsˇs´ı asymptotické sloˇzitosti, nebylo moˇzné hodnoty centralit (CB a CC ) v reálném ˇcase vypoˇc´ıtat. Pomoc´ı programu Pajek XXL jsem zjistil, ˇze pˇresn´ y neparaleln´ı v´ ypoˇcet (jedné z centralit) by na stroji s procesorem AMD Phentom II X4 955 3,20 GHz trval pˇribliˇznˇe mˇes´ıc. Small-world Network Analysis and Partitioning (SNAP) Pro v´ ypoˇcet centralit jsem zvolil framework Small-world Network Analysis and Partitioning (SNAP) [9, 7]. Ten, jako jeden z mála (dalˇs´ı viz [7]) umoˇzn ˇuje paraleln´ı bˇeh. Je implementován v jazyce C, vyuˇz´ıvá POSIX vlákna a primitiva OpenMP. Je ˇs´ıˇren jako open-source. Framework se mi podaˇrilo zprovoznit pouze na systémech zaloˇzen´ ych na OS Linux (konkrétnˇe na Ubuntu 12.10 64bit a Debian 3.2.0). 31

Analýza z´ıskané s´ıtˇe

Základn´ı informace o s´ıti

V [7] je uvedeno, ˇze oproti existuj´ıc´ım ˇreˇsen´ım je SNAP ˇcasto 10-100 rychlejˇs´ı a m˚ uˇze 9 pracovat se s´ıtˇemi maj´ıc´ımi ˇrádovˇe aˇz 10 vrchol˚ u. Téˇz zde naleznete algoritmy, v tomto frameworku pouˇzité (napˇr. paraleln´ı verze algoritmu BFS aj.). SNAP mj. umoˇzn ˇuje identifikaci komunit, v´ ypoˇcet CB a centralit hran. V´ ypoˇcet CC bylo nutné doimplementovat. Taktéˇz jsem doimplementoval v´ ypoˇcet polomˇeru s´ıtˇe a ASPL. V´ ypoˇcty vˇsech v´ yˇse uveden´ ych hodnot prob´ıhaj´ı v jednom pr˚ uchodu – na rozd´ıl od nˇekter´ ych jin´ ych program˚ u, kde je v jednom pr˚ uchodu moˇzné vypoˇc´ıtat pouze jednu metriku. SNAP téˇz umoˇzn ˇuje hodnoty centralit aproximovat, coˇz povaˇzuji za velmi pˇr´ınosné (viz dále). V [9] je uvedeno, ˇze pˇri 5% aproximaci se pr˚ umˇerná chyba u nejcentrálnˇejˇs´ıch vrchol˚ u (nejvyˇsˇs´ıho 1%) pohybuje pod hranic´ı 20%. Veˇskeré v´ ypoˇcty jsou procesorovˇe nároˇcné a nen´ı-li SNAP omezen, vyuˇz´ıvá 100% procesorového ˇcasu. Pajek XXL a Gephi Dalˇs´ım programem, kter´ y jsem vyuˇzil pro ˇcasovˇe nenároˇcné v´ ypoˇcty (napˇr. DC , poˇcet komponent apod.), byl Pajek XXL [32]. Ten téˇz umoˇzn ˇuje práci s rozsáhl´ ymi s´ıtˇemi, nicménˇe neumoˇzn ˇuje paraleln´ı bˇeh. U programu Gephi (viz [11]) oceˇ nuji velmi kvalitn´ı vizualizaci s´ıtˇe, se kterou je moˇzné r˚ uznˇe manipulovat (napˇr. dle r˚ uzn´ ych metrik zvˇetˇsovat a obarvovat vrcholy). Kv˚ uli vizualizaci vˇsak nen´ı moˇzné pracovat s rozsáhl´ ymi s´ıtˇemi (jako maximum se uvád´ı 50 tis´ıc vrchol˚ u – tuto hodnotu se mi vˇsak podaˇrilo pˇrekonat). Gephi téˇz neumoˇzn ˇuje paraleln´ı bˇeh. Program je nav´ıc velmi pamˇet’ovˇe nároˇcn´ y a pˇr´ıleˇzitostnˇe se chová nestabilnˇe. Lze ho vˇsak doporuˇcit pro anal´ yzu menˇs´ıch s´ıt´ı.

6.2

Z´ akladn´ı informace o s´ıti

S pouˇzit´ım program˚ u, popsan´ ych v pˇredeˇslé ˇcásti, jsem z´ıskal pro neorientovanou 1 s´ıt’ následuj´ıc´ı informace: Tab. 6.1: Informace o neorientované s´ıti. Poˇc. vrchol˚ u

Poˇc. hran

∼ 578 tis´ıc

∼ 6 788 tis´ıc

Vrch. v nej. komp. Poˇc. komp. Pˇredpokl. % OSN 99,99 %

53

Polomˇer ASPL Hustota Pr˚ um. dG 15

4,87

4,06E-5

23,48

72-96%

Max. dG

γ

5254

3,5

Z tabulky 6.1 vypl´ yvá, ˇze mimo hlavn´ı komponentu se v s´ıti nacház´ı dalˇs´ıch 52 komponent (kaˇzdou tvoˇr´ı jeden vrchol). To je pravdˇepodobnˇe zp˚ usobeno existenc´ı dupli1

Vzhledem ke stahov´ an´ı pouze v´ ystupn´ıch hran, velmi rychlou zmˇenou OSN a moˇznost´ı vypnut´ı/zapnut´ı autorizace pˇr´ atel, nen´ı snadné rozhodnout, kter´ y model je vhodnˇejˇs´ı. Proto jsou d´ ale uvedeny oba modely.

32



citn´ıch profil˚ u (viz ˇca´st 4.4) a rychlou zmˇenou dat v OSN. Vzhledem k jej´ı velikosti nemá tato skuteˇcnost na v´ ysledná data vliv. Jelikoˇz je hodnota ASP L ≤ 6, 5, podaˇrilo se pro neorientovanou s´ıt’ potvrdit hypotézu ˇsesti krok˚ u (pr˚ umˇern´ y poˇcet prostˇredn´ık˚ u = ASP L − 1, nebot’ ASP L = 1 je pˇr´ım´ y kontakt, viz ˇca´st 2.3 a [29]). Zjiˇstˇená hodnota ASPL je velmi podobná (4,87 oproti 4,74) hodnotˇe, zveˇrejnˇené v práci [6], popisuj´ıc´ı strukturu OSN Facebook.com. Kaˇzdého uˇzivatele ve zkoumané s´ıti je tak moˇzné pr˚ umˇernˇe kontaktovat pomoc´ı 4 prostˇredn´ık˚ u. Délka nejdelˇs´ıho ˇretˇezce je pak 14 prostˇredn´ık˚ u (v experimentu provádˇeném Milgramem jich bylo 10, viz 2.3). Téˇz se potvrdilo, ˇze hodnota ASPL m˚ uˇze b´ yt odhadnuta jako: ln(n)/ ln ln(n). V naˇsem pˇr´ıpadˇe tedy 5,13. ASPL v dalˇs´ıch OSN jsou taktéˇz podobné a to sice v intervalu 4,25 - 5,88, viz [30]. Tab. 6.2 uvád´ı informace z´ıskané z orientované s´ıtˇe2 . Tab. 6.2: Informace o orientované s´ıti. + Polomˇer ASPL Hustota Pr˚ um. d− G , dG

17

5,07

2,03E-5

Max. d+ G

Max. d− G

5254

590

11,74

γ vstup. γ v´ ystup. Vzájemn´ ych hran 3,5

3,5

31,5%

Oproti OSN Orkut, ˇci jin´ ym, je pr˚ umˇern´ y poˇcet hran (pr˚ um. dG ) témˇeˇr 10x menˇs´ı (viz [30]). Za zaj´ımav´ y fakt povaˇzuji to, ˇze pouze jedno ze tˇr´ı pˇrátelstv´ı je vzájemné. To je v porovnán´ı s jin´ ymi OSN velmi málo. Napˇr. Flickr má u ´dajnˇe tuto hodnotu 62%, LiveJournal 73,5% a YouTube 79,1% [30]. To m˚ uˇze naznaˇcovat, ˇze se ve zkoumané s´ıti vyskytuje pomˇernˇe velké mnoˇzstv´ı slab´ ych vazeb nebo to, ˇze se ve skuteˇcnosti nˇekteˇr´ı uˇzivatelé navzájem neznaj´ı. Maximáln´ı v´ ystupn´ı stupeˇ n je témˇeˇr desetkrát vˇetˇs´ı neˇz maximáln´ı vstupn´ı stupeˇ n. Z toho vyvozuji, ˇze se v s´ıti nenacház´ı extrémnˇe populárn´ı ˇci prestiˇzn´ı osoby ( pouze“ 50 krát ˇcastˇeji vyhledávané neˇzli je pr˚ umˇer). Naopak zde existuje nˇekolik ” osob shromaˇzd’uj´ıc´ıch velk´ y poˇcet kontakt˚ u (jejich poˇcet kontakt˚ u pˇresahuje aˇz 500 krát pr˚ umˇer). Vysok´ y exponent konektivity3 pravdˇepodobnˇe umoˇzn ˇuje existenci kritického prahu [10]. Pokud bychom náhodnˇe odeb´ırali vrcholy, s´ıt’ by se nejsp´ıˇse rozpadla na v´ıce komponent. Ztrác´ı se tak jedna z v´ yhod bezˇskálov´ ych s´ıt´ı. 2

ASPL a polomˇer byly z´ısk´ any 20% aproximac´ı, viz dále. Vypoˇcten pomoc´ı n´ astroje dostupného na http://tuvalu.santafe.edu/∼aaronc/powerlaws metodou maxim´ aln´ı vˇerohodnosti s hodnotou Kolmogorov–Smirnova testu rovné 0,0297. Tato mal´ a hodnota naznaˇcuje pomˇernˇe pˇresnou aproximaci [30]. 3

33



Četnost % (log) 1e-03 1e-01 1e+01 1

2

1e-05

1e-05

Četnost % (log) 1e-03 1e-01 1e+01

Na obr. 6.2 naleznete ˇcetnosti vstupn´ıho (obr. 6.2a) a v´ ystupn´ıho stupnˇe (obr. 6.2b).

5 20 50 200 Vstupní stupeň (log)

1

(a) vstupn´ı – d− G

5 50 500 Výstupní stupeň (log)

5000

(b) v´ ystupn´ı – d+ G

ˇ Obr. 6.2: Cetnosti vstupn´ıho a v´ ystupn´ıho stupnˇe.

0.0

0.0

0.2

0.5

Četnost (%) 0.4 0.6

Četnost (%) 1.0 1.5

0.8

2.0

Na obr. 6.3 naleznete v´ yskyt ˇcetnost´ı hodnot CC (obr. 6.3b) a ASPL (obr. 6.3a). I kdyˇz se rozdˇelen´ı stupnˇe vrchol˚ u neˇr´ıd´ı normáln´ım rozdˇelen´ım pravdˇepodobnosti tyto dvˇe témˇeˇr ano.

0.05

0.15

0.25 CC

0.35

2

(a) CC

4

6 8 ASPL

10

12

(b) ASPL

ˇ Obr. 6.3: Cetnosti hodnot CC a ASPL. Z obr. 6.44 vypl´ yvá, ˇze i pˇres pomˇernˇe dobrou aproximaci koeficientu konektivity (γ), je v této s´ıti tlumen´ı poˇctu hran (zejména u vrchol˚ u s menˇs´ım stupnˇem) menˇs´ı neˇz 4

CCDF – doplˇ nkov´ a kumulativn´ı distribuˇcn´ı funkce, vypoˇctena jako 1 − F (x), kde F (x) je distribuˇcn´ı funkce.

34


Výsledky Centrality measures a jejich porovnán´ı

je pro bezˇskálové s´ıtˇe obvyklé. Jako EXP 0,075 je oznaˇceno CCDF exponenciáln´ıho rozdˇelen´ı s parametrem λ = 0.075. Jako SF 2 a SF 3,5 jsou oznaˇceny CCDF standardn´ıch bezˇskálov´ ych s´ıt´ı s pˇr´ısluˇsn´ ym koeficientem konektivity. Tvar CCDF OSN + Lidé.cz (zejména dG ) pˇripom´ıná CCDF vytvoˇrenou ze s´ıtˇe spolupráce herc˚ u z´ıskanou z IMDb5 [5]. U té téˇz nastupuje mocninn´ y zákon aˇz po urˇcitém stupni vrchol˚ u. Domn´ıvám se tak, ˇze v této s´ıti je vˇetˇsina uˇzivatel˚ u schopna z poˇca´tku sesb´ırat“ ” 6 nˇekolik kontakt˚ u pomˇernˇe snadno . Tato jejich schopnost se s pˇrib´ yvaj´ıc´ım stupnˇem sniˇzuje a nastupuje mocninn´ y zákon, kter´ y umoˇzn´ı dosáhnout velkého stupnˇe pouze nˇekolika vrchol˚ um.

Obr. 6.4: Porovnán´ı nˇekolika r˚ uzn´ ych CCDF.

6.3

V´ ysledky Centrality measures a jejich porovn´ an´ı

Kv˚ uli v´ ypoˇcetn´ı sloˇzitosti (viz ˇca´st 2.4) a ˇcasové nároˇcnosti byly v´ ypoˇcty centralit provádˇeny na serveru students.kiv.zcu.cz. Na tom se nacház´ı: 8x Intel(R) Xeon(TM) 3.0 GHz (dvou jádrové, tedy celkem 16x CPU) a 32GB RAM. Z ˇcasov´ ych d˚ uvod˚ u (viz dále) jsem pro neorientovanou s´ıt’ provedl 5% aproximaci a pˇresn´ y v´ ypoˇcet. Pro orientovanou s´ıt’ pak 5% a 20% aproximaci. V´ ypoˇcet 5% aproximace trval cca 5,5 hodiny, 20% aproximace pˇribliˇznˇe jeden den a pˇresn´ y v´ ypoˇcet cca 4,5 dne. 5 6

http://www.imdb.com Coˇz vzhledem k tomu, ˇze ˇclovˇek má u ´dajnˇe 200-5000 sociáln´ıch vazeb [10, 29] nen´ı pˇrekvapivé.

35



V´ ysledky hodnot orientované i neorientované s´ıtˇe, jsou si v naˇsem pˇr´ıpadˇe velmi podobné (viz tab. v pˇr´ıloze E a tab. 6.3). Aproximace téˇz dosahuj´ı velmi podobn´ ych v´ ysledk˚ u. Vzhledem k malému r˚ ustu ASPL v neorientované s´ıti (cca 2% pˇri 15% rozˇs´ıˇren´ı vrchol˚ u, viz tab. D.1) lze pˇredpokládat, ˇze je hypotéza ˇsesti krok˚ u splnˇena i pro orientovanou s´ıt’ a to i pˇres to, ˇze je pouze 31,5% pˇra´telstv´ıch vzájemn´ ych. Pˇredpokládám tedy, ˇze je s´ıt’ dobˇre propojena, zejména mezi v´ yznamn´ ymi vrcholy, které tvoˇr´ı tzv. jádro s´ıtˇe (viz pˇr´ıloha F). V tab. 6.3 naleznete ˇzebˇr´ıˇcky uˇzivatel˚ u, kteˇr´ı se dle základn´ıch metrik CM (tj. CC , ˇ r´ıˇcky byly sestaveny pro pˇresné CB a CD ) um´ıstili na prvn´ıch dvaceti m´ıstech. Zebˇ hodnoty CM pro neorientovanou s´ıt’. Uˇzivatelé, vyskytuj´ıc´ı se v prvn´ı des´ıtce, maj´ı napˇr´ıˇc ˇzebˇr´ıˇcky pˇriˇrazenou jednotnou barvu pro snadnˇejˇs´ı identifikaci. Vˇsimnˇete si, ˇze i pˇres r˚ uzné zp˚ usoby v´ ypoˇct˚ u tˇechto metod se v prvn´ı des´ıtce témˇeˇr vˇsechna jména opakuj´ı a jsou na podobn´ ych pozic´ıch. Tab. 6.3: Uˇzivatelé OSN seˇrazeni dle dosaˇzeného m´ısta pro jednotlivé metriky CM – pˇresn´ y v´ ypoˇcet neorientované s´ıtˇe. #

CB

CC

CD

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

honzek098 sochurek.j r.hasek melly.19 ashraf.shafeek martinoof [email protected] vvladimirvanek flamez10 durdil.d nezkrotny.dablicek.lucie.xd topol.d zasova1991 rocker.k ajik-1 vivi.elien.186 kapradorosty martin.karatista kubasvitak citronek.zx

honzek098 sochurek.j r.hasek nezkrotny.dablicek.lucie.xd melly.19 flamez10 [email protected] martinoof vivi.elien.186 kapradorosty durdil.d marcela-marsi nikollka22 topol.d ashraf.shafeek ajik-1 s.e.x.o.n.t.h.e.b.e.a.c.h rocker.k zasova1991 beruska.no1

honzek98 sochurek.j r.hasek martinoof melly.19 flamez10 vvladimirvanek ashraf.shafeek [email protected] durdil.d vivi.elien.186 topol.d zasova1991 kapradorosty ajik-1 martin.karatista rocker.k citronek.zx avoldies petrlupik

Na obr. E.1 naleznete tytéˇz ˇzebˇr´ıˇcky pro 5% aproximaci s´ıtˇe (aproximace vycház´ı z toho, ˇze nás zaj´ımaj´ı pouze vrcholy s nejvyˇsˇs´ı hodnotou – tj. centra). Jiˇz po 5% aproximaci, která je 20 krát rychlejˇs´ı neˇz pˇresn´ y v´ ypoˇcet, metody CB i CC (DC nen´ı v´ ypoˇcetnˇe nároˇcná, nemá ji tedy smysl aproximovat) pomˇernˇe pˇresnˇe centra odhal´ı. 36



Obr. D.2 zobrazuje grafické porovnán´ı aproximovan´ ych hodnot s hodnotami pˇresn´ ymi. Z obr. D.2b a D.1b, zobrazuj´ıc´ı pouze nejvyˇsˇs´ı hodnoty, vypl´ yvá, ˇze vˇetˇsina center je um´ıstˇena na správném m´ıstˇe (body tvoˇr´ı témˇeˇr pˇr´ımku). Aproximace ve frameworku SNAP byla optimalizována pro metodu CB (viz. [9]), proto je jej´ı aproximace pˇresnˇejˇs´ı. Aproximace CC ve frameworku SNAP p˚ uvodnˇe implementována nebyla, pˇresto vysoké hodnoty aproximuje pomˇernˇe dobˇre. V tab. E.2 a E.3 naleznete tytéˇz ˇzebˇr´ıˇcky pro s´ıt’ orientovanou. Aby bylo moˇzné v´ ypoˇcty vˇsech metrik provést v jednom bˇehu, byla nam´ısto metriky CC pouˇzita metrika CC− (bl´ızkost dle vstupn´ıch hran) – tzn., jak snadno se k vrcholu dostanou vrcholy ostatn´ı [32]. Z toho d˚ uvodu ve v´ yˇse uveden´ ych tabulkách naleznete metriku − CD a ˇzebˇr´ıˇcek se od dˇr´ıve uveden´ ych ponˇekud liˇs´ı. CB je opˇet aproximována dobˇre. − CC jiˇz pˇr´ıliˇs ne z d˚ uvodu, kter´ y byl uveden dˇr´ıve. Obr. 6.5 zobrazuje závislosti mezi hodnotami CM ve zkoumané s´ıti. Z obr. 6.5a a 6.5b vypl´ yvá, ˇze v této s´ıti jsou hodnoty CB a CC u ´mˇerné hodnotˇe CD . Tzn. ˇc´ım vˇetˇs´ı je stupeˇ n vrcholu, t´ım má vˇetˇs´ı hodnoty CB a CC (patrné zejména u vysok´ ych hodnot).

(a) CB x CD

(b) CC x CD

Obr. 6.5: Vzájemné závislosti centralit ve zkoumané s´ıti pro pˇresn´ y v´ ypoˇcet neorientované s´ıtˇe. Obecnˇe tomu tak b´ yt nemus´ı. Pokud by napˇr. s´ıt’ byla tvoˇrena v´ıce rozsáhl´ ymi komunitami, které by spojovalo pouze nˇekolik vrchol˚ u, hodnota CB tˇechto vrchol˚ u by byla vysoká, nehledˇe na jejich stupeˇ n. Jelikoˇz se zde takové vrcholy nevyskytuj´ı, lze vylouˇcit, ˇze je s´ıt’ rozdˇelena do velk´ ych komunit (napˇr. dle kraj˚ u, generac´ı apod.), které jsou spojeny pouze nˇekolika vrcholy. S´ıt’ je naopak dobˇre propojená a pˇri komunikaci, vyuˇz´ıvaj´ıc´ı nejkratˇs´ıch cest, j´ı vˇetˇsina informac´ı putuje pˇres jádro s´ıtˇe (viz pˇr´ıloha F – pods´ıt’ vytvoˇrená z uˇzivatel˚ u maj´ıc´ı v´ıce neˇz 500 hran). 37



Obr. 6.6a ukazuje, ˇze v s´ıti existuje nˇekolik vrchol˚ u maj´ıc´ıch malou hodnotu CC , ale relativnˇe velkou hodnotu CB . Z toho usuzuji, ˇze v s´ıti existuj´ı vrcholy (ˇci malé komunity), které jsou na okraji“ s´ıtˇe a k jej´ımu zbytku jsou pˇripojeny napˇr. pouze ” prostˇrednictv´ım jednoho ˇci dvou vrchol˚ u, které jsou od ostatn´ıch vrchol˚ u vzdálené“. ” Lze oˇcekávat, ˇze k tˇemto vrchol˚ um se dostanou informace ze s´ıtˇe mezi posledn´ımi pˇr´ıpadnˇe v˚ ubec. Obr. 6.6b znázorˇ nuje nezávislost vstupn´ıho a v´ ystupn´ıho stupnˇe. V této s´ıti tak existuj´ı vrcholy, které jsou populárn´ı (vyhledávané s vysok´ ym vstupn´ım stupnˇem), ale nejsou pˇr´ıliˇs vlivné (nemaj´ı vysok´ y v´ ystupn´ı stupeˇ n) a naopak.

+ − x CD (b) CD

(a) CB x CC

Obr. 6.6: Vzájemné závislosti centralit ve zkoumané s´ıti pro pˇresn´ y v´ ypoˇcet neorientované s´ıtˇe. Vzhledem k tomu, ˇze je tato s´ıt’ dobˇre propojená, lze pro urˇcován´ı v´ yznamnosti vrchol˚ u doporuˇcit metriku CD , která nen´ı pˇr´ıliˇs v´ ypoˇcetnˇe nároˇcná. Pˇr´ıpadnˇe pouˇz´ıvat 5% aproximaci metrik CB a CC , které jsou pro odhalen´ı nejv´ yznamnˇejˇs´ıch vrchol˚ u (zejména u neorientované s´ıtˇe) dostateˇcnˇe pˇresné.

38

7 Závˇer Práce si kladla za u ´kol seznámit ˇctenáˇre s nˇekter´ ymi metodami, které anal´ yza sociáln´ıch s´ıt´ı nab´ız´ı. Za t´ımto u ´ˇcelem byla analyzována rozsáhlá sociáln´ı s´ıt’ pˇra´tel, kterou se podaˇrilo z´ıskat z online sociáln´ı s´ıtˇe (Online social network – OSN) Lidé.cz. Ukázalo se, ˇze provozovatel této OSN se automatickému procházen´ı nebrán´ı a podaˇrilo se tak proj´ıt v´ıce neˇz milion webov´ ych stránek. Z tˇechto stránek byla vytvoˇrena databáze, obsahuj´ıc´ı pˇra´telstv´ı mezi uˇzivateli a informace o uˇzivatel´ıch. Odhaduji, ˇze tato databáze v dobˇe, kdy byla aktuáln´ı, obsahovala 72-96% uˇzivatel˚ u, kteˇr´ı se v této OSN nacházeli. V teoretické ˇcásti byl pˇredstaven model bezˇskálové s´ıtˇe, kter´ ym se dle Barabásiho (viz [10]) ˇr´ıd´ı vˇetˇsina reáln´ ych komplexn´ıch s´ıt´ı. Z´ıskanou s´ıt’ (ta byla tvoˇrena témˇeˇr 600 tis´ıci vrcholy a 7 miliony hran) jsem se oproti tomuto modelu pokusil verifikovat. Ukázalo se, ˇze se dle tohoto modelu ˇr´ıd´ı“ pouze ˇca´steˇcnˇe. Dále bylo zjiˇstˇeno, ˇze se ” jej´ı topologie podobá sociáln´ı s´ıti spolupráce mezi herci. Byly pˇredstaveny základn´ı metody, které jsou schopné odhalit uˇzivatele, maj´ıc´ı ve zkoumané s´ıti kl´ıˇcovou roli. Podle tˇechto metod byly sestaveny ˇzebˇr´ıˇcky kl´ıˇcov´ ych uˇzivatel˚ u v s´ıti, které jsou mezi sebou porovnány. Toto porovnán´ı odhalilo, ˇze v s´ıti nejsou lidé rozdˇeleni do velk´ ych komunit (napˇr. dle generac´ı, pohlav´ı, bydliˇstˇe apod.), které by spojovalo pouze nˇekolik uˇzivatel˚ u. Naopak je s´ıt’ velmi dobˇre propojená a nejv´ıce vyuˇz´ıvan´ ymi cestami jsou ty mezi centry. Jelikoˇz jsou si z´ıskané ˇzebˇr´ıˇcky velmi podobné, lze pro identifikaci center v této s´ıti doporuˇcit nejrychlejˇs´ı, i kdyˇz obecnˇe nejménˇe pˇresnou, metodu – Freemanovu degree centrality. Jej´ı v´ yhodou je okamˇzit´ y v´ ypoˇcet. Pˇresn´ y v´ ypoˇcet dalˇs´ıch metrik, vzhledem k jejich v´ ypoˇcetn´ı nároˇcnosti a velikosti s´ıtˇe, zabral 4,5 dne. Obecnˇe tak lze doporuˇcit 5% aproximaci dalˇs´ıch metrik (Closeness a Betweenness centrality). Jak bylo ukázáno, v´ ysledky tˇechto aproximac´ı jsou dostateˇcnˇe pˇresné. D´ıky dobˇre propojenému jádru má s´ıt’ velmi malou pr˚ umˇernou délku nejkratˇs´ı cesty a to sice 4,87. Pro orientovan´ y model je tato hodnota o nˇekolik procent vyˇsˇs´ı. Stále je vˇsak menˇs´ı, neˇz hodnota uvádˇená Milgramem (tj. 6,5). Pro tuto sociáln´ı s´ıt’ pˇrátel se tak podaˇrilo ovˇeˇrit hypotézu ˇsesti krok˚ u. Z´ıskaná hodnota je nav´ıc velmi podobná hodnotám, které jsou uvádˇené v podobn´ ych v´ yzkumech, zkoumaj´ıc´ıch jiné OSN. Práce se téˇz zab´ yvala anal´ yzu dat v OSN uloˇzen´ ych. Z tˇech byly vytvoˇreny statistické v´ ystupy, které byly porovnány s podobn´ ymi pr˚ uzkumy, aby bylo moˇzné posoudit jejich relevantnost. Z tˇechto informac´ı je moˇzné napˇr. zjistit, jak velkou potencionáln´ı skupinu m˚ uˇze reklamn´ı sdˇelen´ı oslovit a mohou tak b´ yt pouˇzity reklamn´ımi ˇci marketingov´ ymi agenturami. Téˇz poskytuj´ı jasnˇejˇs´ı informace o sociodemografii této OSN (oficiáln´ı u ´daje, uvádˇené na OSN Lidé.cz, jsou tvoˇreny ze vzorku tvoˇr´ıc´ıho cca 0,5% mnou analyzovan´ ych dat). V OSN Lidé.cz jsou konkrétnˇe nejv´ıce zastoupenou 39

Závˇer

Budouc´ı práce

skupinou lidé ve vˇeku 15-29 let, se zájmy o sport (zejména cyklistiku a kolektivn´ı m´ıˇcové hry) a o hudbu (zejména rock a pop). Nejpopulárnˇejˇs´ı je tato OSN u uˇzivatel˚ u v Plzeˇ nském kraji. Dalˇs´ımi zkouman´ ymi vlastnostmi byla vzdˇelanost, znalost ciz´ıch jazyk˚ u a problematika konzumace alkoholu a kouˇren´ı u mladistv´ ych. Z´ıskané u ´daje se, s pomˇernˇe malou toleranc´ı, shoduj´ı s u ´daji uvádˇen´ ymi v jin´ ych zdroj´ıch. Mohou tak b´ yt povaˇzovány za relevantn´ı a anal´ yzu obsahu OSN lze doporuˇcit jako alternativn´ı formu k formˇe dotazn´ıkové“ a uˇsetˇrit tak náklady, které jsou s n´ı spojené. ”

7.1

Budouc´ı pr´ ace

Jako moˇzné rozˇs´ıˇren´ı se nab´ız´ı anal´ yza komunit, která zkoumá a identifikuje komunity, ve kter´ ych se vˇetˇsina uˇzivatel˚ u navzájem zná. Téˇz by bylo moˇzné analyzovat dynamiku s´ıtˇe. S drobn´ ymi u ´pravami databáze a webov´ ych robot˚ u by bylo moˇzné uchovávat r˚ uzné verze s´ıtˇe a zkoumat, jak se ˇcasem mˇenila. V´ ysledky této anal´ yzy by mohli napˇr. odhalit vzory, jak se virtuáln´ı pˇra´telstv´ı navazuj´ı, mˇen´ı ˇci ruˇs´ı. Dále by bylo moˇzné z´ıskat v´ıce informac´ı vycházej´ıc´ıch z dat v OSN obsaˇzen´ ych. Napˇr. je moˇzné zkoumat r˚ uzné závislosti mezi bydliˇstˇem a zálibami uˇzivatel˚ u. Tyto otázky, zamˇeˇrené na lokalitu, by mohli b´ yt pˇr´ınosné napˇr. pro lokáln´ı obchodn´ıky, kina ˇci organizátory sportovn´ıch akc´ı. Zaj´ımavou moˇznost´ı by téˇz bylo porovnán´ı v´ ysledk˚ u z´ıskan´ ych pomoc´ı základn´ıch (tj. Freemanov´ ych) metod Centrality measures s metodami dalˇs´ımi (napˇr. s metodami PageRank, Bonachii degree ˇci HITS). V této práci jsem pro zjednoduˇsen´ı, urychlen´ı v´ ypoˇctu a urychlen´ı z´ıskán´ı dat, povaˇzoval vˇsechny hrany za stejnˇe v´ yznamné. Ve skuteˇcnosti tomu tak b´ yt nemus´ı. Hranám lze pˇriˇradit r˚ uzné váhy. Ty mohou b´ yt z´ıskány napˇr. pomoc´ı kombinace geografické vzdálenosti uˇzivatel˚ u, jejich spoleˇcn´ ymi zájmy, poˇctu a obsahu zpráv, které si p´ıˇs´ı na nástˇenku“, jak´ y komentáˇr uvádˇej´ı u popisu pˇrátelstv´ı a je-li pˇrátelstv´ı ” vzájemné. Poté m˚ uˇze b´ yt zaj´ımavé pozorovat, zda a jak se prvn´ı m´ısta v ˇzebˇr´ıˇcc´ıch zmˇen´ı. Posledn´ım návrhem na budouc´ı práci je moˇzn´ y pr˚ uzkum, z jakého d˚ uvodu jsou centra, ˇci konkrétn´ı uˇzivatelé, centry. Maj´ı nˇejaké spoleˇcné zájmy ˇci vlastnosti? Znaj´ı stejné uˇzivatele? Jak by asi vypadal a jaké by mˇel m´ıt vlastnosti ideáln´ı“ uˇzivatel, ” proto aby se mohl stát populárn´ım centrem a z této pozice profitovat?

40

Literatura [1] Zákon ˇc. 121/2000 Sb., o právu autorském, o právech souvisej´ıc´ıch s právem autorsk´ ym a o zmˇenˇe nˇekter´ ych zákon˚ u (autorsk´ y zákon). [2] The Web Robots Pages [online]. http://www.robotstxt.org.

[cit.

28.4.2013].

Dostupné

z:

[3] Scrapy [online]. [cit. 28.4.2013]. Dostupné z: http://scrapy.org. ˇ ´ CEK, ˇ [4] CADA, R. – RYJA Z. – KAISER, T. Diskrétn´ı matematika. Západoˇceská univerzita, 2004. ´ [5] ALBERT, R. – BARABASI, A.-L. Statistical mechanics of complex networks. Reviews of modern physics. 2002, 74, 1, s. 47. [6] BACKSTROM, L. et al. Xiv:1111.4570. 2011.

Four degrees of separation.

arXiv preprint ar-

[7] BADER, D. A. Parallel Programming for Graph Analysis [online]. [cit. 28.4.2013]. Dostupné z: http://www.cc.gatech.edu/∼bader/papers/ PPoPP12. [8] BADER, D. A. – MADDURI, K. Parallel algorithms for evaluating centrality indices in real-world networks. In Parallel Processing, 2006. ICPP 2006. International Conference on, s. 539–550. IEEE, 2006. [9] BADER, D. A. – MADDURI, K. SNAP, Small-world Network Analysis and Partitioning: an open-source parallel graph framework for the exploration of large-scale networks. In Parallel and Distributed Processing, 2008. IPDPS 2008. IEEE International Symposium on, s. 1–12. IEEE, 2008. ´ [10] BARABASI, A.-L. V pavuˇcinˇe s´ıt´ı. Paseka, 2005. ISBN 80-7185-751-3. [11] BASTIAN, M. – HEYMANN, S. – JACOMY, M. Gephi: An Open Source Software for Exploring and Manipulating Networks. International AAAI Conference on Weblogs and Social Media. 2009. Dostupné z: http://gephi.org. [12] BATAGELJ, V. Friendship and unionization in a hi-tech firm. [online]. [cit. 28.4.2013]. Dostupné z: http://vlado.fmf.uni-lj.si/pub/networks/ data/esna/hiTech.htm. 41

LITERATURA

LITERATURA

[13] BRANDES, U. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology. 2001, 25, 2, s. 163–177. ˇ ÍKOVA, ´ L. Anal´ [14] BUST yza sociáln´ıch s´ıt´ı. Sociologický ˇcasopis. 1999, 35, 2, s. 193–206. [15] CATANESE, S. et al. Extraction and analysis of facebook friendship relations. Computational Social Networks. 2012, s. 291–324. [16] DE NOOY, W. – MRVAR, A. – BATAGELJ, V. Exploratory social network analysis with Pajek. Cambridge University Press, 2011. ISBN 9780521602624. [17] ELLISON, N. B. et al. Social network sites: Definition, history, and scholarship. Journal of Computer-Mediated Communication. 2007, 13, 1, s. 210–230. [18] FERRARA, E. – FIUMARA, G. Mining and Analysis of Online Social Networks. University of Messina, 2012. ˇ ˇÍK, P. [19] FRANEK, M. – MUZ Hudebn´ı preference a jej´ı souvislost s nˇekterými osobnostn´ımi rysy [online]. [cit. 28.4.2013]. Dostupné z: http://acta.musicologica.cz/06-03/0603s02.html. [20] FREEMAN, L. C. A set of measures of centrality based on betweenness. Sociometry. 1977, s. 35–41. ˇ T. Extrakce informac´ı ze sociáln´ıch médi´ı. Masarykova Uni[21] GREGOROVIC, verzita, 2010. [22] HANKE, T. Import dat ze sluˇzby Google Scholar do formátu XML. Západoˇceská univerzita, 2012. [23] HANNEMAN, R. A. – RIDDLE, M. Introduction to social network methods. University of California Riverside, 2005. ˇ [24] JARUSEK, P. Analýza sociáln´ı s´ıtˇe organizátor˚ u záˇzitkových akc´ı. Masarykova Univerzita, 2008. [25] JOHNSON, J. A. et al. Social Network Analysis: A Systematic Approach for Investigating [online]. [cit. 28.4.2013]. Dostupné z: http://www.fbi.gov/ stats-services/publications/law-enforcement-bulletin/2013/March/ social-network-analysis. ˇ [26] SLERKA, J. Social network analysis pro zaˇcáteˇcn´ıky [online]. [cit. 28.4.2013]. Dostupné z: http://www.lupa.cz/clanky/social-network-analysis-prozacatecniky. [27] LESKOVEC, J. Social media analytics: tracking, modeling and predicting the flow of information through networks. In Proceedings of the 20th international conference companion on World wide web, s. 277–278. ACM, 2011. 42

LITERATURA

LITERATURA

[28] LONG, J. Google Hacking. Zoner Press, 2005. ISBN 80-86815-31-5. [29] MILGRAM, S. The small world problem. Psychology today. 1967, 2, 1, s. 60–67. [30] MISLOVE, A. et al. Measurement and analysis of online social networks. In Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, s. 29–42. ACM, 2007. ˇ ÍK, V. Evropská ˇskoln´ı studie o alkoholu a jin´ [31] MRAVC ych drogách (ESPAD). ´ ˇ In Zaostˇreno na drogy 1/2012. Uˇrad vlády CR, 2012. [32] MRVAR, A. Network Analysis using Pajek [online]. [cit. 28.4.2013]. Dostupné z: http://mrvar.fdv.uni-lj.si/sola/info4. ´ [33] NOSAL, P. Vzdˇeláván´ı dospˇelých [online]. [cit. 28.4.2013]. Dostupné z: http://www.czso.cz/csu/tz.nsf/i/prezentace_z_tiskove_konference _vzdelavani_dospelych/$File/csu_tk_vzdelavani_prezentace.pdf. [34] SAK, P. Stav a vývoj znalost´ı ciz´ıch jazyk˚ u ˇceské populace [online]. [cit. 28.4.2013]. Dostupné z: http://www.insoma.cz/index.php?id=1&n=1 &d_1=paper&d_2=jazyky_cz. [35] SEZNAM.CZ. Lidé.cz – Nevhodné chován´ı a zakázané aktivity [online]. [cit. 28.4.2013]. Dostupné z: http://napoveda.seznam.cz/cz/nevhodnechovani-a-zakazane-aktivity.html. [36] SEZNAM.CZ. Smluvn´ı ujednán´ı - Seznam u ´ˇcet [online]. [cit. 28.4.2013]. Dostupné z: http://registrace.seznam.cz/licenceScreen. [37] STERLY, R. Výsledky ankety Sport roku 2012 – nap´ınavý souboj mezi cyklistikou a fotbalem [online]. [cit. 28.4.2013]. Dostupné z: http://info.sportcentral.cz/blog/vysledky-ankety-sport-roku-2012souboj-mezi-cyklistikou-a-fotbalem.

43

Slovn´ık pojm˚ u a zkratek ASPL BFS CCDF

Pr˚ umˇerná délka nejkratˇs´ı cesty (Average shortest path length) Prohledáván´ı do ˇs´ıˇrky (Breadth-first search) Doplˇ nková kumulativn´ı distribuˇcn´ı funkce (Complementary cumulative distribution function) CM Centrality measures CSV Comma-separated values ˇ U ´ ˇ y statistick´ CS Cesk´ yu ´ˇrad DFS Prohledáván´ı do hloubky (Depth-first search) DOM Document Object Model GPL General Public License HTML HyperText Markup Language IBMd Internet Movie Database OS Operaˇcn´ı systém OSN Online sociáln´ı s´ıt’ (Online social network) RUM Mˇes´ıˇcn´ıch unikátn´ıch pˇr´ıstup˚ u SNAP Small-world Network Analysis and Partitioning URL Uniform resource locator XML Extensible Markup Language XPath XML Path Language

Znaky pouˇ zit´ e ve vzorc´ıch ∆ γ CB CC CC− CD + CD − CD D dG

Hustota grafu Exponent konektivity Betweenness centrality Closeness centrality Closeness centrality dle vstupn´ıch hran Degree centrality Degree centrality dle v´ ystupn´ıch hran Degree centrality dle vstupn´ıch hran Polomˇer grafu Stupeˇ n vrcholu

44

Obsah DVD Na pˇriloˇzeném DVD naleznete následuj´ıc´ı sloˇzky a soubory: • Data – lide-sit.net – s´ıt’ ve formátu .net (viz pˇr´ıloha B) – lide-sit.gr – s´ıt’ ve formátu .gr (viz pˇr´ıloha B) – lide-sit.sql – SQL Dump databáze se z´ıskan´ ymi daty – lide-struktura.sql – SQL Dump struktury databáze (viz ˇcást 4.2.1) – vypocty – sloˇzka obsahuj´ıc´ı vypoˇctené hodnoty CM • Roboti – SNABot-sit – robot pro pr˚ uchod a zpracován´ı s´ıtˇe pˇra´telstv´ı – SNABot-profily – robot pro pr˚ uchod a zpracován´ı profil˚ u – SNABot-centra – robot pro pr˚ uchod a zpracován´ı center – Scrapy.pdf a Scrapy-0.14.4.tar.gz – manuál a knihovna Scrapy • Analyza – SNAP – rozˇs´ıˇren´ y framework SNAP ˇ U ´ – statistiky – tabulky a prezentace uvádˇené CS • R – csv – CSV soubory slouˇz´ıc´ı k tvorbˇe graf˚ u – skripty – R skripty – pdf – PDF soubory s grafy vygenerované pomoc´ı R skript˚ u • SNABot-nastroje.jar – program umoˇzn ˇuj´ıc´ı generován´ı CSV soubor˚ u pro tvorbu statistik a generován´ı souboru se s´ıt´ı • BP-Marek-Naggy.pdf – elektronická verze BP • BP-Marek-Naggy.rar – zdrojové dokumenty elektronické verze BP 45

Pˇ r´ılohy

46

A Uˇzivatelské pˇr´ıruˇcky A.1

Webov´ y robot SNABot

Pro spuˇstˇen´ı webového robota je tˇreba m´ıt nainstalovan´ y Python verzi 2.6 nebo 2.7 a knihovnu Scrapy. Tu m˚ uˇzete nalézt v [3] (pr˚ ubˇeh instalace je popsán v oficiáln´ı dokumentaci v ˇcásti Installation guide). Dále je nutné vytvoˇrit databázi s pˇredepsanou strukturou (viz ˇca´st 4.2.1 ˇci SQL Dump na pˇriloˇzeném DVD). Roboti byli vyv´ıjeni a testováni na OS Windows 7. Vzhledem k tomu, ˇze vˇsechny pouˇzité ˇca´sti jsou platformˇe nezávislé, mˇelo by b´ yt moˇzné roboty spustit i na jin´ ych OS. Pˇred spuˇstˇen´ım je tˇreba v souboru scrapy.bat nastavit cestu, ve které je Python nainstalován. Pro zahájen´ı stahován´ı spust’te pˇr´ıkazov´ y ˇrádek a pˇrepnˇete se do sloˇzky, ve které se robot nacház´ı. Toho následnˇe spust´ıte pˇr´ıkazem: scrapy crawl jmeno -s JOBDIR=adresar Kde jmeno je jméno webového robota. Tˇemi jsou: SNABot-profily – pro pr˚ uchod profil˚ u, jejichˇz jména je nutné z´ıskat pomoc´ı robota SNABot-sit –, SNABot-centra – pro pr˚ uchod center, jejichˇz jména je nutné z´ıskat pomoc´ı robota SNABot-sit – a SNABotsit – pro pr˚ uchod stránek moji-pratele, obsahuj´ıc´ı pˇra´tele uˇzivatele. Parametr adresar je adresáˇr, do kterého budou ukládána data, d´ıky kter´ ym bude moˇzné robota pozastavit a pˇri dalˇs´ım spuˇstˇen´ı na toto stahován´ı navázat. Nedoporuˇcuji spouˇstˇet v´ıce robot˚ u najednou. Jinak m˚ uˇze doj´ıt k jejich odpojen´ı ˇci nesprávné funkˇcnosti. Pro pˇreruˇsen´ı stahován´ı stisknˇete v pˇr´ıkazové ˇra´dce kombinaci kláves ctrl + c. Robot bude po krátké dobˇe ukonˇcen. Pˇr´ıpadnˇe lze ukonˇcen´ı vynutit dvojit´ ym stisknut´ım této kombinace. Poté vˇsak nen´ı zaruˇceno, ˇze budou zpracovány vˇsechny stránky korektnˇe. Pro navázán´ı na pˇreruˇsené stahován´ı opˇet zadejte v´ yˇse uveden´ y pˇr´ıkaz. Roboti loguj´ı své akce do soubor˚ u log-rrrr-mm-dd.txt. V tˇech je moˇzné odhalit pˇr´ıpadné problémy. Téˇz jsou v nich uvedeny základn´ı statistiky o stahován´ı, jako je jeho rychlost, velikost pˇrenesen´ ych dat apod.

47

Uˇzivatelské pˇr´ıruˇcky

A.2

Framework SNAP

Framework SNAP

Framework SNAP se mi podaˇrilo spustit pouze na systémech zaloˇzen´ ych na OS Linux. Pˇred samotn´ ym spuˇstˇen´ım je tˇreba framework nakonfigurovat. Toho doc´ıl´ıte pˇr´ıkazem ./configure --enable-openmp. Bez zadán´ı parametru -openmp nebude umoˇznˇen paraleln´ı v´ ypoˇcet! Po konfiguraci zadejte pˇr´ıkaz make, kter´ y zdrojové soubory pˇreloˇz´ı (pˇreklad m˚ uˇze trvat i nˇekolik minut). Pro spuˇstˇen´ı v´ ypoˇctu centralit pˇrejdˇete do sloˇzky test. V terminálu poté zadejte následuj´ıc´ı pˇr´ıkaz: ./eval_vertex_betweenness -infile vstup.gr -outfile vystup.txt [-approx X] Kde vstup.gr je soubor se s´ıt´ı, která má b´ yt analyzována, ve formátu .gr (viz pˇr´ıloha B). vystup.txt je soubor, do kterého budou v´ ysledky uloˇzeny. Pomoc´ı volitelného parametru -approx je moˇzné v´ ysledky aproximovat (viz ˇca´st 6.3) a v´ ypoˇcet tak znaˇcnˇe urychlit. X znaˇc´ı kolika procentn´ı aproximac´ı bude v´ ypoˇcet proveden (nejˇcastˇeji se uvád´ı 5%). Pˇresn´ y v´ ypoˇcet m˚ uˇze b´ yt ˇcasovˇe velmi nároˇcn´ y. Pˇri cca 580 tis´ıc´ıch vrcholech trval na 16 jádrovém procesoru cca 4,5 dne. Pokud nen´ı program omezen, vyuˇz´ıvá po ˇcas v´ ypoˇctu 100% procesorového ˇcasu.

A.3

SNABot-nastroje

Tento nástroj slouˇz´ı k odstranˇen´ı duplicit, které vznikly z d˚ uvodu uvedeném v ˇca´sti 4.4. Dále umoˇzn ˇuje vygenerován´ı souboru, obsahuj´ıc´ıho sociáln´ı s´ıt’ a generován´ı CSV soubor˚ u, které umoˇzn ˇuj´ı automatickou aktualizaci graf˚ u uveden´ ych v kapitole 5. Pro správnou funkˇcnost je tˇreba, aby data byla uloˇzena v databázi maj´ıc´ı dˇr´ıve uvedenou strukturu (viz ˇca´st 4.2.1 ˇci SQL Dump na pˇriloˇzeném DVD). Soubory obsahuj´ıc´ı s´ıt’ je moˇzné vygenerovat ve dvou formátech (viz pˇr´ıloha B). Pro odstranˇen´ı duplicit a vygenerován´ı souboru se s´ıt´ı zadejte do pˇr´ıkazové ˇra´dky následuj´ıc´ı pˇr´ıkaz: java -jar SNABot-nastroje.jar -d/n -format [-csv] Kde -d je pˇr´ıznak pro odstranˇen´ı duplicit (tˇech se v databázi nacház´ı cca 10 tis´ıc). Pˇri zadán´ı tohoto pˇr´ıznaku m˚ uˇze zpracován´ı trvat nˇekolik minut. Z d˚ uvodu zpˇetné 48

Uˇzivatelské pˇr´ıruˇcky

SNABot-nastroje

kompatibility nebyly duplicity odstranˇeny pˇr´ımo v databázi. Pˇri zadán´ı pˇr´ıznaku n duplicity odstranˇeny nebudou a soubory jsou vygenerovány témˇeˇr ihned. Parametr -format urˇcuje, v jakém formátu bude s´ıt’ uloˇzena. Na v´ ybˇer jsou tˇri moˇznosti: -net – s´ıt’ bude moˇzné analyzovat pomoc´ı vˇetˇsiny program˚ u (jako jsou napˇr. Pajek XXL, Gephi atd.), -gr – s´ıt’ bude moˇzné analyzovat pomoc´ı frameworku SNAP, kter´ y umoˇzn ˇuje paraleln´ı v´ ypoˇcet metrik CC a CB , -oba – budou vytvoˇreny oba soubory s v´ yˇse uveden´ ymi formáty. Pokud bude zadán voliteln´ y parametr -csv, z databáze budou vygenerovány CSV soubory, které umoˇzn ˇuj´ı automatickou tvorbu graf˚ u pomoc´ı statistického nástroje R (R skripty naleznete na pˇriloˇzeném DVD ve sloˇzce R).

49

B Formáty soubor˚ u S´ıt’ lze uloˇzit do dvou r˚ uzn´ ych formát˚ u, které budou dále popsány. Form´ at .gr Soubor s pˇr´ıponou .gr je pouˇz´ıván frameworkem SNAP pˇri v´ ypoˇctu centralit CC a CB . Reprezentace s´ıtˇe má následuj´ıc´ı formát: p 578119 6788208 u u 1 1 1211 ...... 578119 22513 Prvn´ı ˇrádka definuje model, se kter´ ym se bude dále pracovat, ostatn´ı ˇrádky tvoˇr´ı jednotlivé hrany. p definuje prvn´ı ˇrádku, ˇc´ıslo za n´ım urˇcuje poˇcet vrchol˚ u. Druhé ˇc´ıslo urˇcuje poˇcet hran. Následuj´ıc´ı p´ısmeno znaˇc´ı: u – s´ıt’ je neorientovaná, d – s´ıt’ je orientovaná. Tˇret´ı p´ısmeno urˇcuje zda je s´ıt’ váˇzená – w, ˇci neváˇzená – u. Váhy je moˇzné pˇridat na konec ˇra´dek tvoˇr´ıc´ı hrany napˇr. takto: 1 1211 5. Posledn´ı ˇc´ıslo znaˇc´ı, zda je prvn´ı vrchol ˇc´ıslován od jedniˇcky, ˇci od nuly. Dle toho je toto ˇc´ıslo nutné nastavit. U ˇrádk˚ u, urˇcuj´ıc´ıch hrany, je nutné dbát na to, aby se v nich nevyskytovali nepatˇriˇcné mezery (napˇr. na konci ˇra´dek). Form´ at .net Tento formát je pouˇz´ıván programy Gephi, Pajek XXL a nˇekter´ ymi dalˇs´ımi programy. Soubor má následuj´ıc´ı formát: *Vertices 578119 1 "jmeno" ......... 578119 "jmeno" *Edgeslist 1 1211 1212 1213 1214 ......... 578118 278044 ˇ ıslo za znaˇckou *Vertices udává poˇcet vrchol˚ C´ u. Vrcholy jsou ˇc´ıslovány od 1 a je moˇzné je r˚ uznˇe oznaˇcit. V naˇsem pˇr´ıpadˇe jménem. Znaˇcka *Edgelist ˇr´ıká, ˇze se jedná o neorientované hrany. V pˇr´ıpadˇe hran orientovan´ ych pouˇzijeme znaˇcku *Arcslist. Téˇz je moˇzné pouˇz´ıt znaˇcky *Edges a *Arcs. V tom pˇr´ıpadˇe je vˇsak nutné, aby se na jedné ˇrádce nacházela pouze jedna hrana. Hranám je téˇz moˇzné pˇriˇradit váhu pˇridán´ım jej´ı hodnoty na konec ˇra´dky (napˇr. 1 1211 5). 50

C Rozˇs´ıˇren´ı statistik V této pˇr´ıloze naleznete tabulku s detailn´ım rozdˇelen´ım mladistv´ ych do skupin podle toho, jak ˇcasto u ´dajnˇe konzumuj´ı alkohol a kouˇr´ı. Tabulka se vztahuje k ˇca´sti 5.4. Tab. C.1: Skupiny kuˇrák˚ u a konzument˚ u alkoholu u uˇzivatel˚ u mladˇs´ıch 18 let. Konzumace alkoholu Kouˇren´ı Mladistv´ ych Neuvád´ı Neuvád´ı Neuvád´ı Neuvád´ı Neuvád´ı Abstinent Abstinent Abstinent Abstinent Abstinent Dennˇe Dennˇe Dennˇe Dennˇe Dennˇe I bez m´ıry I bez m´ıry I bez m´ıry I bez m´ıry I bez m´ıry Poˇra´d Poˇra´d Poˇra´d Poˇra´d Poˇra´d S m´ırou S m´ırou S m´ırou S m´ırou S m´ırou

Neuvád´ı Hodnˇe Ne Obˇcas Poˇra´d Neuvád´ı Hodnˇe Ne Obˇcas Poˇra´d Neuvád´ı Hodnˇe Ne Obˇcas Poˇra´d Neuvád´ı Hodnˇe Ne Obˇcas Poˇra´d Neuvád´ı Hodnˇe Ne Obˇcas Poˇrád Neuvád´ı Hodnˇe Ne Obˇcas Poˇra´d

6755 58 3859 216 42 95 66 4539 243 67 7 99 51 31 13 115 448 794 572 91 3 448 794 572 91 424 610 5544 1860 282

Celkem

27048

51

D Porovnán´ı výsledk˚ u aproximace s pˇ resn´ ym v´ ypoˇ ctem V této pˇr´ıloze, která se váˇze k ˇcásti 6.2, naleznete porovnán´ı hodnot CM, polomˇeru s´ıtˇe a ASPL. Téˇz jsou zde porovnány pˇresné v´ ysledky a v´ ysledky z´ıskané pomoc´ı aproximace. V tabulce D.1 naleznete hodnoty polomˇeru s´ıtˇe a ASPL pro r˚ uzné typy v´ ypoˇct˚ u. Na obrázc´ıch naleznete porovnán´ı nakolik jsou aproximované hodnoty (resp. um´ıstˇen´ı jednotliv´ ych vrchol˚ u) shodné s pˇresn´ ym v´ ysledkem. V idea´ln´ım pˇr´ıpadˇe by se mˇelo jednat o pˇr´ımku. Je zde uvedeno porovnán´ı 5% aproximace a pˇresného v´ ypoˇctu neorientované s´ıtˇe. Obr. D.2 zobrazuje celkové porovnán´ı. Na ˇ tˇech, následuj´ıc´ı stránce naleznete detail tohoto porovnán´ı pro vysoké hodnoty. Cili které nás vˇetˇsinou zaj´ımaj´ı. Tab. D.1: Porovnan´ı ASPL a polomˇeru s´ıtˇe pro r˚ uzné typy v´ ypoˇct˚ u. Typ s´ıtˇe Neorientovaná Neorientovaná Orientovaná Orientovaná

Aproximace 5% 100% 5% 20%

(a) CC – vˇsechny hodnoty

ASPL Polomˇer 4,39 4,86 4,97 5,07

12 15 15 17

(b) CB – vˇsechny hodnoty

Obr. D.1: Porovnán´ı 5% aproximace a pˇresného v´ ypoˇctu pro neorientovanou s´ıt’.

52

Porovnán´ı výsledk˚ u aproximace s pˇresným výpoˇctem

(a) CB – detail vysok´ ych hodnot

(b) CC – detail vysok´ ych hodnot

Obr. D.2: Porovnán´ı 5% aproximace a pˇresného v´ ypoˇctu pro neorientovanou s´ıt’.

53

E Výsledky Centrality measures pro orientovanou s´ıt’ a aproximace V této pˇr´ıloze naleznete ˇzebˇr´ıˇcky uˇzivatel˚ u, kteˇr´ı se um´ıstily na prvn´ıch 20 m´ıstech, dle základn´ıch metrik Centrality measures1 . Uˇzivatelé, vyskytuj´ıc´ı se na prvn´ıch 10 m´ıstech v ˇzebˇr´ıˇcku uvedeném v ˇcásti 6.3, maj´ı pro snadnˇejˇs´ı identifikaci napˇr´ıˇc ˇzebˇr´ıˇcky pˇriˇrazenou jednotnou barvu. Jsou zde uvedeny ˇzebˇr´ıˇcky pro s´ıt’ orientovanou i neorientovanou a jejich 5% a 20% aproximace. Pˇresn´ y v´ ypoˇcet pro neorientovanou s´ıt’ naleznete v tabulce 6.3. Tab. E.1: Uˇzivatelé OSN seˇrazeni dle dosaˇzeného m´ısta pro jednotlivé metriky CM – 5% aproximace neorientované s´ıtˇe. # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

CB

CC

honzek098 honzek098 r.hasek r.hasek sochurek.j sochurek.j melly.19 melly.19 flamez10 flamez10 martinoof martinoof [email protected] vivi.elien.186 nezkrotny.dablicek.lucie.xd nezkrotny.dablicek.lucie.xd ashraf.shafeek [email protected] durdil.d kapradorosty vvladimirvanek durdil.d vivi.elien.186 janmukarovsky topol.d ajik-1 kapradorosty topol.d rocker.k nikollka22 ajik-1 marcela-marsi zasova1991 martin.karatista [email protected] lusie44 [email protected] karollecka martin.karatista s.e.x.o.n.t.h.e.b.e.a.c.h

CD honzek098 sochurek.j r.hasek martinoof melly.19 flamez10 vvladimirvanek ashraf.shafeek [email protected] durdil.d vivi.elien.186 topol.d zasova1991 kapradorosty ajik-1 martin.karatista rocker.k citronek.zx avoldies petrlupik

− – Closeness Legenda k tabulk´ am: CB – Betweenness centrality, CC – Closeness centraltity, CC − centrality dle vstupn´ıch hran, CD – Degree centrality, CD – Degree centrality dle vstupn´ıch hran). 1

54

Výsledky Centrality measures pro orientovanou s´ıt’ a aproximace

Tab. E.2: Uˇzivatelé OSN seˇrazeni dle dosaˇzeného m´ısta pro jednotlivé metriky CM – 5% aproximace orientované s´ıtˇe. #

CB

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

honzek098 r.hasek melly.19 sochurek.j nezkrotny.dablicek.lucie.xd durdil.d flamez10 vivi.elien.186 [email protected] martinoof vvladimirvanek avoldies ashraf.shafeek zlatovlaska111 rompears [email protected] 01pitrisek martin.karatista [email protected] italfllexo

CC−

− CD

r.hasek [email protected] vivi.elien.186 avoldies honzek098 splichalpeta melly.19 vivi.elien.186 x.x.radushka.princess.x.x beruska.no1 [email protected] denny.hebdova lusie44 karollecka karollecka italfllexo durdil.d honzek098 rompears jitka.pabyskova lucixxcka-lucik lucixxcka-lucik nezkrotny.dablicek.lucie.xd domi-stara flamez10 myska122 xxxluciiinkaxxx r.hasek nikollka22 zpewanda bacio333 durdil.d adrika75 marcela-marsi asuss jahodka444 jahodka444 petra.dark elvislu rompears

55

Výsledky Centrality measures pro orientovanou s´ıt’ a aproximace

Tab. E.3: Uˇzivatelé OSN seˇrazeni dle dosaˇzeného m´ısta pro jednotlivé metriky CM – 20% aproximace orientované s´ıtˇe. #

CB

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

honzek098 r.hasek melly.19 durdil.d sochurek.j flamez10 nezkrotny.dablicek.lucie.xd martinoof vivi.elien.186 [email protected] vvladimirvanek rompears ashraf.shafeek ashraf.shafeek avoldies martin.karatista [email protected] 01pitrisek zsidlo asuss italfllexo

CC−

− CD

r.hasek [email protected] vivi.elien.186 avoldies rompears splichalpeta melly.19 vivi.elien.186 durdil.d beruska.no1 x.x.radushka.princess.x.x denny.hebdova honzek098 karollecka lucixxcka-lucik italfllexo [email protected] honzek098 karollecka jitka.pabyskova lusie44 lucixxcka-lucik flamez10 domi-stara lucinnkaa16 myska122 nezkrotny.dablicek.lucie.xd r.hasek nikollka22 zpewanda bacio333 durdil.d xxxluciiinkaxxx marcela-marsi jjjjoenick jahodka444 asuss petra.dark horalka5 rompears

56

F Jádro s´ıtˇe V této pˇr´ıloze naleznete vizualizaci a nˇekolik informac´ı o jádru s´ıtˇe. To tvoˇr´ı uˇzivatelé, kteˇr´ı maj´ı v´ıce neˇz 500 pˇra´tel nebo je za pˇrátele povaˇzuje v´ıce neˇz 500 uˇzivatel˚ u. Pˇr´ıloha se váˇze ke kapitole 6. Pˇres toto jádro je v s´ıti pˇrenáˇseno nejv´ıce informac´ı. Je zaj´ımavé, ˇze témˇeˇr vˇsechny vrcholy tvoˇr´ı jednu komponentu (105 ze 123, tj. 85,4%). To ukazuje na velmi dobré propojen´ı mezi centry. ASPL v této pods´ıti (pro neorientovan´ y model) je 3 a polomˇer s´ıtˇe 8. Pro orientovanou s´ıt’ je pak ASPL 4 a polomˇer s´ıtˇe 10. Pr˚ umˇern´ y stupeˇ n vrcholu je 5,2. Hustota jádra je 4,3E-2 pro s´ıt’ neorientovanou a 2,1E-2 pro s´ıt’ orientovanou. Je tedy v´ yraznˇe hustˇs´ı neˇz s´ıt’ tvoˇrena vˇsemi uˇzivateli. Nejcentrálnˇejˇs´ım uˇzivatelem v jádˇre je dle vˇsech zkouman´ ych metrik CM (CD , CC a CB ) uˇzivatelka nezkrotny.dablicek.lucie.xd.

Obr. F.1: Nejvˇetˇs´ı komponenta jádra s´ıtˇe – vrcholy jsou obarveny a zvˇetˇseny dle metriky CD (vytvoˇreno pomoc´ı programu Gephi).

57

Západočeská univerzita v Plzni Fakulta aplikovaných věd Katedra informatiky a výpočetní techniky

Recommend Documents