Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Využití grafů při analýze sociálních sítí Michail Tsikerdekis Grafy a sítě podzim 2011 Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie 0 čem bude dnešní přednáška Motivace Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Shrnutí Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie K čemu je analýza sociálních sítí? Člověk žije ve společenství, vytváří si různé vazby a vztahy s ostatními lidmi, které se zpravidla mění v čase Obvykle jsou sociální sítě vícevrstvé a lze se na ně dívat z různého úhlu pohledu a v různých kontextech Studium sociálních sítí využívá poznatků několika vědních oborů: psychologie, antropologie, sociologie a diskrétní matematiky (teorie grafů) Šest stupňů odloučení - teorie, která předpokládá, že každý člověk je spojený s libovolným jiným člověkem na Zemi prostřednictvím řetězce šesti sobě navzájem známých lidí sce Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie S Historie J Leonhard Euler - položil základy teorie grafů . Jacob Mořeno (sociometrie) - kvantitativní metodologie pro zkoumání sociálních vazeb . Formální definice klik v teorii grafů . Elizabeth Bott, John Barnes (antropologie) -Manchesterská škola, zasloužili se o rozvoj výzkumu v oblasti sociálních sítích . James C. Mitchel (antropologie) - studium sociálních systémů, formální popis příbuzenských vztahů pomocí algebry . Vzestup sociologie - Sociál Networks Journal, Stanley Milgram (experiment Malý svět, 6 stupňů odloučení), Mark Granovetter (slabé a silné vazby) . Rozvoj výpočetní techniky, postupné rozšiřování počítačových sítí I Masivní rozvoj počítačových sítí, především Internetu, vznik programů pro analýzu sociálních sítí Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Uplatnění analýzy sociálních sítí Pop-kultura: hry, TV, noviny, magazíny, ... Obchodní sféra: nové nástroje pro konzultanty, znalostní management, ... Akademické prostředí: mnoho různých oborů (lingvistika, politologie, sociologie, .. .) otivace Teorie grafů a sociální sítě Analýza sociálních sítí Co je sociální síť? Ukázková studie Formální definice: Množina uzlů a hran, kde: uzly jsou dvojího typu: '-v. jednotlivci a skupiny, r^* / hrany jsou binární relace mezi JMy jednotlivými uzly. Sociální síť je sociální struktura tvořená jednotlivci (nebo organizacemi) zvané „uzly", které jsou provázány (propojeny) jedním nebo více typy vzájemných závislostí, jakými jsou přátelství, příbuzenské vztahy, společné zájmy, finanční transakce, nenávist, sexuální vztahy, vyznání, znalosti nebo prestiž. Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Uzly v sociálních sítích Dva druhy: Jednotlivci: osoby, zvířata • Skupiny: organizace, oddělení, týmy, země, města, druhy Atributy uzlu - popisují vlastnosti postoje, názory a chování, mohou se měnit v čase (např. příjem, vzdělání, zaměstnání) Analýza atributů - soubor metod, pomocí kterých lze určit a popsat jednotlivé atributy Motivace Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Relace mezi uzly é je matkou, je ženou lí je šéfem, je učitelem, je přítelem ií ví že, je si vědom Pocitové má rád, věří í radí, mluvíš, bojuje proti í patří do stejného klubu, je součástí Každá kategorie relací má vlastní strukturu a dopady na členy sociální sítě. Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková stud Základní pojmy (které byste měli znát) Komponenta souvislosti grafu Cesta v grafu Topologie grafu Stupeň vrcholu (vstupní/výstupní stupeň) Teorie grafů a sociální sítě Analýza sociálních sítí Klika v grafu Klika - největší úplný podgraf grafu, jehož vrcholy jsou spojeny hranou se všemi zbylými Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie N-klika Definice kliky je pro některé případy příliš silná (skupina, kde nejsou všichni přátelé všech) N-klika je podgrafem grafu, ve kterém cesta mezi dvěma uzly není větší než N (pro N = 2: přátelé mých přátel) 1-klika = klika Pro sociology výzkum klik, kde N > 2 skýtá mnoho zásadních výzev Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Problémy N-klik » Překryvy: {a,b,c,f,e} a {b,c,d,f,e} jsou obě 2-kliky » Příslušnost do kliky je splnitelná pro nečleny I 2-kliky mohou být nekompaktní (cesta přes uzly mimo kliku): červené vrcholy patří do stejné 2-kliky, ačkoliv spolu nesousedí Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie N-klan Podobné N-klice, cesta však nesmí vést přes uzly, které nejsou součástí N-klanu Příslušnost uzlů do N-klanu je dána cestami dlouhými nejvýše N hran bez použití uzlů mimo N-klan Vznikají tak více kompaktní podgrafy než v případě N-klik Problémy N-klanů: Je {a,b,c,f} 2-klan? Ukažte všechny 2-klany. • Jejich mnohem méně a nemusí tak zcela reflektovat realitu. Různé N-klany se mohou překrývat. Motivace Teorie grafů a sociální sítě Analýza sociálních sítí 2-klany - příklad Ukázková studie Shrnutí 4: HOLLY PAULINE GERY 10: PAM PAT MICHAEL JOHN Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie K-plex Množina uzlů, ve které všechny uzly sousedí s ostatními s výjimkou nejvýše K uzlů 1-plex = 1-klika Je-li K = 2, všechny uzly v 2-plexu jsou spojeny s alespoň N — 2 dalšími uzly K-plexu je zpravidla velmi mnoho a překrývají se Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie K-plex - příklad ls {a,b,á,e}a 2-plex? Is {a:b,c,d,e} a 2-plex? Is {a,b,d} a 2-plex? Is the graph as a whole a 2-plex? s it a 3-plex? Motivace Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Základní pojmy analýzy sociálních sítí I. • Zabývá se zkoumáním vztahů a vzorů chování v rámci komunity • Vztahy jsou spletité a obvykle mají více rovin (viz kategorie relací) • Zaměřuje se primárně na analýzu relací mezi aktéry, nikoliv na aktéry samotné Motivace Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Základní pojmy analýzy sociálních sítí II. a - kontakty, vazby na ostatní, informace o skupinách aktérů, které definují spojení (relaci) mezi dvěma aktéry. Relační data nemohou být omezeny pouze na vlastnosti jednotlivce (atributy). ě - soubor metod, které se používají pro zkoumání a popis relací mezi jednotlivými uživateli Motivace Teorie grafů a sociální sítě Analýza sociálních sítí Příklady sítí I. Ukázková studie Shrnutí Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Získávání dat pro analýzu » Dříve se data zapisovala ručně do tabulek, které byly více či méně efektivně organizovány, dnes se používají relační databáze • Atributy - data uložena v matici dat, osoba = řádek, ve sloupcích jsou atributy » Relace - data uložena v matici spojení popisujících spojení mezi uzly Standard Data Matrix Variables Transposed Data Matrix Cases a b c Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Metody získávání dat Style of research Source o! evidence Survey research Ethnographic research Documentary research Questionnaires, mlervlows QbServatirtns Texts Type of dala AUfůule 4- / 1 ■ —•* Ktealional ^— ňelaiionai Type of ana Variable rli-lflljfTi.il Typological analysis i--:--,.--. anatysis Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Sběr dat dnes Kolekce dat z webu & automatické zpracování: • snazší jak pro respondenty, tak pro zpracovatele. Pasivní sběr elektronických dat: • záznamy telefonních rozhovorů • zpracování znalostí, jež je těžké předat (znalost jazyků) • web cookies Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Sociocentrický vs. egocentrický pohled na síť Sociocentrický pohled se zaměřuje na vlastnosti sociální sítě jako celku. Pozice jednotlivých aktérů je charakterizována relativně vůči ostatním. Egocentrický pohled se zaměřuje na jednotlivé aktéry. Zkoumá privátní sítě jednotlivců, jejich vazby na okolí a jejich strukturu. Motivace Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Shrnutí Tabulka pohledů a aktérů Sociocentrický pohled Egocentrický pohled 1 typ aktérů Vazby mezi všemi aktéry stejného typu Vazby mezi množinou aktérů, kteří jsou přímo spojeni s jedním konkrétní osobou 2 typy aktérů Vazby mezi všemi aktéry dvou různých typů Vazby mezi dvěma různými množinami aktérů, kteří jsou přímo spojeni s konkrétní osobou Motivace Teorie grafů a sociální sítě 1 typ aktérů Analýza sociálních sítí Ukázková studie - egocentrický pohled Shrnutí Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie 2 typy aktérů - sociocentrický pohled CHARLOTTE Data compiled from newspaper society pages by Davis, Gardner & Gardner Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie 2 typy aktérů - egocentrický pohled Dr. Jones Web MD Bil PDR Merck manual Jane Mom Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Shrnutí Kompletnost a hustota grafu Kompletnost grafu = ( -) / Př.: Graf o 20 vrcholech s 5 izolovanými uzly má kompletnost = 0.75 Čím více je graf kompletní, tím vyšší je jeho hustota • Sociocentrická hustota grafu o 91 uzlech, kde pouze 16 je propojeno hranami je 18 % • Egocentrická hustota se liší pro každé dva vrcholy Hustotaíneorient.) =-;-— v ' n*(n-l)/ H ustotaí orient.) =-—^-- n * (n — 1) Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Centralita I. Lokální centralita • definována, jako stupeň vrcholu grafu (počet hran vedoucích z daného uzlu (neorient. graf), resp. počet vstupních/výstupních hran (orient, graf)) • Lokální centralita nemůže být kritériem pro srovnávání dvou různě velkých grafů Relativní lokální centralita • poměr skutečného počtu hran ku maximálnímu počtu hran • Př.: uzel stupně 25 v grafu o 100 vrcholech má relativní lokální centralitu 0,25; uzel stejného stupně v grafu o 30 vrcholech má relativní lokální centralitu 0,86. • lze ji použít i pro srovnání různě velkých grafů, nelze ji použít pro grafy různých kategorií relací Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Centralita II. Globální centralita (blízkost) Freeman (1979, 1990) navrhl metodu měření globální centrality založenou na pojmu „blízkosti" uzlů • Globální centralita je vyjádřena jako vzdálenost (délka cesty) mezi různými vrcholy grafu. • Vrchol je globálně centrální, je-li suma délek všech jeho cest k většině ostatních uzlů nejmenší (má nejkratší cesty k většině ostatních uzlů) Užitečnost globální centrality • udává očekávaný čas doručení libovolné informace přenášené po síti (např. Síť drbů - centrální aktér slyší drby jako první) Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Stupeň centrality Udává míru vystavení informací procházející grafem (např. Síť drbů - centrální aktér bude mít vždy přesnější informace než aktéři na odlehlých koncích grafu) Může být interpretován jako příležitost k ovlivňování &i přímá ovlivnitelnost Předpovídá různé situace: např. šíření nemocí, uspokojení z práce Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Globální centralita a stupeň centrality Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Dosah centrality Množina vrcholů, které jsou vzájemně dosažitelné v nejvýše k krocích. Pro k = 1 = stupeň centrality. 2krokový dosah říká analytikovi, jaký je poměr lidí v síti, kteří mohou být dosaženi libovolným jiným člověkem přímo, nebo prostřednictvím jednoho prostředníka (přátelé mých přátel) Jedná se o dobrý ukazatel schopnosti člověka získat nějaké zdroje nebo informace od ostatních Motivace Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Shrnutí Centralizace • Hustota popisuje obecnou úroveň koheze v grafu • Centralizace udává rozsah koheze, která je soustředěna kolem jednoho či více ohnisek • Definice: Rozdíl mezi lokální centralitou každého uzlu a globálně centrálním uzlem Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Obecné hypotézy Příslušníci stejné skupiny mají podobné výstupy: názory, chování, postoje, ... (atributy) Příslušnost ke skupině tak může predikovat některé atributy jedince Díky komunikaci mezi členy skupiny dochází k jejich vzájemnému ovlivňování Motivace Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Základní informace » Mapování sociálních vztahů mezi učiteli a zaměstnanci školy • Výzkum probíhal na střední škole v Albertě v Kanadě (556 studentů) Cíle studie • identifikovat klíčové aktéry sociálních vztahů • systematicky zmapovat sociální vazby a následně je analyzovat • nalézt metodu vhodnou pro zachycení sociální struktury učitelů a dalších zaměstnanců na střední škole Penelope Hawe and Laura Ghali Use of social network analysis to map the social relationships of staff and teachers at school Health Educ. Res. (2008) 23(1): 62-69 first published online February 7, 2007 doi:10.1093/her/cyll6 Motivace Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Shrnutí Sběr dat » Mapováno pět kategorií relací, které byly zvoleny na základě počáteční diskuse a pilotního testu: • Znám dotyčného/dotyčnou jménem • Znám dotyčného/dotyčnou osobně • Pravidelně s dotyčným/dotyčnou hovořím • Ptám se dotyčného/dotyčné na záležitosti týkající se školy • Setkávám se s dotyčným/dotyčnou i mimo školu • Použit dotazník rozdaný respondentům • Otázky zaměřené na běžné operace a rutinní vztahy • Zúčastnilo se 50 osob (94 %), 28 žen, 22 mužů • 30 učitelů, 18 dalších zaměstnanců, ředitel a jeho zástupce Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Vstupní předpoklady Výzkum byl navržen tak, aby byly jasně vymezeny jednotlivé grafy Ne všechny vztahy jsou symetrické (např. učitel A může znát učitele B jménem, ale naopak to platit nemusí) Za symetrické byly považovány: „setkávání mimo školu" a „pravidelné konverzace" V ostatních případech byly relace symetrické pouze pokud to obě účastnické strany deklarovaly explicitně Každá z pěti kategorií tvoří vlastní síť Motivace Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Shrnutí Metody analýzy • Zjištění stupně centralizace sítě Míra 2krokové dosažitelnosti (schopnost získat informace nebo zdroje přímo a pomocí prostředníka) • Pozice jednotlivců v rámci sítě • Vliv pracovního zařazení: učitelé, administrativní pracovníci, ostatní personál Vliv pohlaví Motivace Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Shrnutí Velikost egocentrické sítě a 2kroková dosažitelnost Velikost egocentrické 2kroková dosažitelnost sítě (%) Setkávání mimo školu Ředitel / Zástupce 2/10 27 / 47 Žádost o radu Ředitel / Zástupce 37 / 35 85 / 83 Pravidelné konverzace Ředitel / Zástupce 29 / 27 75 / 73 Osobně se zná s Ředitel / Zástupce 33 / 35 98 / 98 Zná jej/ji jménem Ředitel / Zástupce 43 / 42 100 / 100 Motivace Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Shrnutí Závěry • Ve všech pěti kategoriích je podpůrný personál na okraji sítě, v centru jsou učitelé • Většina žen z podpůrného personálů byla na samém okraji sítě • Hustota sítě korelovala s intenzitou vzájemných vazeb • Hustota byla vyšší pro více povrchní vazby (znám dotyčnou osobu jménem) než pro ty společenské • Hustota kategorie „znám dotyčnou osobu jménem" byla nižší (65 %), než se předpokládalo • Nikdo nebyl izolovaný, a to včetně 10 nových zaměstnanců (všichni měli vazbu alespoň na jednu osobu) • Centrem sítě „dotazů" byl ředitel a jeho zástupce, zároveň 7 osob bylo zcela mimo tuto síť Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Shrnutí I. Analýza sociálních sítí je vhodná pro zkoumání: příbuzenských vztahů, strukturu skupiny lidí, řídících formálních a neformálních procesů Využívá se informací o uzlech a relacích mezi nimi Různé druhy relačních vztahů produkují unikátní vrstvy sítě. Sociální sítě lze zkoumat z různých pohledů: sociocentrický, egocentrický, 1-mode, 2-mode. Hustota je poměr počtu hran mezi uzly ku maximálnímu počtu hran v (úplném) grafu. Pokud se všichni znají navzájem, hustota je 100 %. Motivace Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Shrnutí Shrnutí II. • Centralizace sítě udává míru dominance jednoho či více aktérů na síti. Může tak ukázat na klíčové osoby v síti. Kliky, N-kliky a N-klany jsou užitečné pro identifikaci skupin v síti • Existuje velké množství metod pro analýzu sociálních sítí. Konkrétní volba závisí na záměru konkrétního výzkumu • SW nástroje pro analýzu sociálních sítí (např. UCINET, Pájek) jsou nezbytné pro automatizovanou kolekci především u velkých datových sad Teorie grafů a sociální sítě Analýza sociálních sítí Shrnutí III. Ukázková studie Další příklady uplatnění analýzy sociálních sítí: • Hledání klik nebo spojitých komponent podgrafu, volba závisí na cílech a účelu, které jsou stanoveny • Identifikace osob se strategickým významem, identifikace přirozených vůdců a pomocníků v dané komunitě Teorie grafů a sociální sítě Analýza sociálních sítí Ukázková studie Doporučená literatura John P. Scott. Social Network Analysis: A Handbook. Sage Publications Ltd; 2nd edition (March 2000) John P Scott (Editor), Peter Carrington (Editor). The SAGE Handbook of Social Network Analysis. Sage Publications Ltd (May 25, 2011) Penelope Hawe and Laura Ghali Use of social network analysis to map the social relationships of staff and teachers at school Health Educ. Res. (2008) 23(1): 62-69. 2007.