Deeltentamen 1 sociale netwerk analyse Voor dit tentamen krijg je maximaal 2 uur. Als je eerder klaar bent, ga dan stil weg en lever je antwoordenvel, kladpapier en tentamenvragen bij de examinator in. Je mag kladpapier gebruiken, geen rekenmachine, computer, tablet of telefoon. Lees alle vragen eerst goed door. Beantwoord de vragen door de letter voor het antwoord te omcirkelen. Mocht je een antwoord later willen verbeteren streep dan de omcirkelde letter voor het antwoord door en schrijf de letter van het nieuwe antwoord naast de vraag. Elke vraag heeft slechts 1 correct antwoord. Er zijn 18 vragen en iedere vraag geeft 5 punten, je krijgt er 10 kado, voor een totaal van 100 punten. Mocht je vast komen te zitten ga dan door naar de volgende vraag. Collegekaartnummer: Naam: Datum: 1 E&K Ch.2: graphs Beschouw de volgende simpele, ongerichte graaf F: F = (V,E) V = {1, 2, 3, 4, 5, 6} E = {<1,2>, <2,3>, <2,4>, <3,4>, <3,5>, <4,5>, <5,6>} Hint: begin het tekenen van de graaf met een vierkant met knopen 2,3,4,5. 1. Hoeveel local gatekeepers heeft F? A. 0 B. 2 C. 4 D. 6 E. Geen van bovenstaande antwoorden. 2. Wat is de diameter van graaf F? A. 1 B. 2 C. 3 D. 4 E. Geen van bovenstaande antwoorden. 3. Stel je een netwerk voor van Wikipedia, waarbij Wikipedia artikelen de vertices zijn, en hyperlinks tussen paginas als de edges weergegeven worden bijvoorbeeld als het Wikipedia artikel van Johan Cruijff1 verwijst naar het artikel Betondorp2 . Hoe heet dit type netwerk? A. Technological network B. Collaboration graph C. Information linkage graph D. Bipartite graph E. Geen van bovenstaande antwoorden. 1 2 http://nl.wikipedia.org/wiki/Johan_Cruijff http://nl.wikipedia.org/wiki/Betondorp Page 2 NetworkX vragen De vragen gaan over de volgende graaf: >> >> >> >> >> >> import networkx as nx E = {(1, 2), (1, 5), (1, 7), (2, 3), (2, 4), (2, 6), (3, 5)} G = nx.Graph() G.add_edges_from(E) 1. Je genereert de adjacency matrix van graaf G: >> adj_matrix_G = nx.adjacency_matrix(G) Welke van onderstaande code snippets geeft antwoord op de vraag of graaf G simple is? A. 1 in adj_matrix_G B. 2 in adj_matrix_G C. len(adj_matrix_G) / float(2) 2. Met het commando nx.shortest_path_length(G) kun je de kortste paden berekenen in graaf G. Je krijgt een nested dictionary terug die er als volgt uit ziet: { vertex1: { vertex1: shortest_path_length, vertex2: shortest_path_length, ... vertex_n: shortest_path_length }, vertex2: { vertex1: shortest_path_length, vertex2: shortest_path_length, ... vertex_n: shortest_path_length }, ... vertex_n: { vertex1: shortest_path_length, vertex2: shortest_path_length, ... vertex_n: shortest_path_length } } Tip: Met d.keys() krijg je een list met keys uit dictionary d : [key1, key2, ..., key_n]. Page 3 met d.values() een list met values uit d : [value1, value2, ..., value_n] Met d.items() een list met (key, value)-tuples uit d : [(key1, value1), (key2, value2), ..., (key_n, value_n)] Hoe bereken je de eccentricity van node 2? >> path_dict = nx.shortest_path_length(G) A. 1 / float(path_dict[2]) B. path_dict[2].keys() C. max(path_dict[2].values()) D. min(path_dict[2].values()) 3. Hoe bereken je de radius van graaf G met path_dict? >> buffer = [] >> for paths in path_dict.values(): >> ... (I) >> >> ... (II) Welke code snippets moeten op plek (I) en (II)? A. (I): buffer.append(max(paths.values())) (II): min(buffer) B. (I): buffer.append(sum(paths.values())) (II): max(buffer) C. (I): buffer.append(min(paths.values())) (II): min(buffer) D. (I): buffer.append(max(paths.values())) (II): max(buffer) Page 4 Set notatie en operaties Deze vragen gaan over set notatie en operaties op sets (verzamelingen). In deze vragen gebruiken we de volgende sets: • W = {1,2,3} • X = {4,5,6} • Y = {4,5} • Z = {W,X,Y} Welke set is het resultaat van de volgende operaties? 1. S V ∈Z V A. {1,2,3,4,4,5,5,6} B. {1,2,3,4,5,6} C. {W,X,Y} D. {1,2,3,4,5,6,W,X,Y} E. Geen van bovenstaande antwoorden. 2. (W S X)\Y A. {1,2,3,4,5,6} B. {4,5} C. {1,2,3,4,5} D. {1,2,3,6} E. Geen van bovenstaande antwoorden. Page 5 Gerichte, gewogen, en gekleurde grafen Let op in de volgende vragen zullen we een aantal grafen cree¨eren op basis van de graaf in figuur 1. Sommige van de grafen in de volgende opgaven bouwen voort op elkaar andere niet. Lees iedere vraag dus goed en teken voor jezelf bij iedere vraag de aangepaste graaf. Figure 1 1. We beginnen met de graaf uit figuur 1. Welke van de volgende edges moet aan de graaf in figuur 1 worden toegevoegd om deze strongly connected te maken? −−−−−−−→ A. < v3, v4 > −−−−−−−→ B. < v4, v3 > −−−−−−−→ C. < v1, v3 > −−−−−−−→ D. < v4, v1 > E. Geen van bovenstaande antwoorden, de graaf is al strongly connected. 2. We beginnen met de graaf uit figuur 1. Verander voor ieder van de arcs in figuur 1 de orientation (orientatie). Wat is de set van reachable nodes (knopen) vanuit node (knoop) v4? A. {v1,v2,v3,v4} B. {v2,v3,v4} C. {v3,v4} D. {v4} E. Geen van bovenstaande antwoorden. Page 6 3. We beginnen met de graaf uit figuur 1. We kennen aan iedere edge (verbinding) in figuur 1 een gewicht toe als volgt: a1 a2 a3 a4 a5 a6 a7 = = = = = = = 1 1 3 1 1 2 1 Wat is de (geodesic) distance van het kortste pad van knoop v4 naar knoop v1. A. 2 B. 3 C. 4 D. 5 E. Geen van bovenstaande antwoorden. 4. We werken nog steeds met de gewogen graaf uit de vorige opgave, maar nu kijken we naar de underlying graph (onderliggende graaf). Wat is de (geodesic) distance van het kortste pad van knoop v4 naar node (knoop) v1. A. 2 B. 3 C. 4 D. 5 E. Geen van bovenstaande antwoorden. 5. Teken een bipartite graph, wat is de chromatic number van deze graaf? A. 1 B. 2 C. 3 D. 4 E. Geen van bovenstaande antwoorden. Page 7 Netwerk analyse De volgende vraag gaat over graaf H gedefineerd als volgt: H:({v1,v2,v3,v4,v5},{<v1,v2>,<v2,v3>,<v3,v4>,<v4,v5>}) Hint: teken deze graaf als een lijn. 1. Wat is de (ongenormaliseerde) betweenness centrality van knoop (node) v3? A. 0 B. 1 C. 2 D. 3 E. Geen van bovenstaande antwoorden. E&K Ch.3: strong and weak ties Beschouw de volgende simple graph I: I = (V,E) V = {1, 2, 3, 4, 5, 6} E = {<2,4>, <3,4>, <4,5>, <2,5>, <1,3>, <1,5>, <2,6>, <3,6>} Hint: teken deze graaf als een rechthoek, met knoop 4 in het midden. 1. We voegen S en W-labels toe aan de edges, om aan te geven of het gaat om strong of weak ties: <1,3> <1,5> <2,4> <2,5> <2,6> <3,4> <3,6> <4,5> = = = = = = = = S S S W W W S S Welke vertice(s) in I schend(en) de Strong Triadic Closure eigenschap? A. {4} B. {1, 3, 5} C. {1} D. {1, 2, 3, 5, 6} E. Geen van bovenstaande antwoorden. Page 8 2. Stel we weten de sterkte van alle ties (verbindingen) in een sociaal netwerk. Stel dat we de verbindingen geordend hebben op sterkte (tie strength). Nu gaan we een voor een de verbindingen verbreken en we beginnen met de sterkste verbinding, dan de een na sterkste, en zo voorts. Welke van de volgende figuren geeft de beste weergave van de relatie tussen het op deze manier verwijderen van verbindingen en het aantal componenten in dit netwerk? (Het gaat hier niet om de absolute getallen maar om de vorm van de grafiek.) A B C D Page 9 E&K Ch.5: structural balance 1. Stel je de volgende vriendengroep voor: Gerrit is vrienden met Iris, Marije is een vriendin van Iris, Henk is bevriend met Paul en Henk heeft ruzie met Gerrit. Wat kun je doen om deze graaf in balans te krijgen, zonder dat je de onderlinge (gegeven) relaties moet veranderen? A. Alle ontbrekende relaties negatief (vijanden) te maken. B. Marije vrienden te maken met Paul, Gerrit vrienden laten worden met Marije, en verder negatieve relaties toe te voegen. C. Alle ontbrekende relaties positief (vrienden) te maken. D. Paul ruzie laten maken met Marije, Gerrit vrienden te laten worden met Marije, en verder negatieve relaties toe te voegen. E. Geen van bovenstaande antwoorden. 2. Zie het netwerk in Figuur 2. Welke uitspraak over deze graaf klopt? B + - A C + D E Figure 2 A. De graaf is structurally balanced te maken zonder edges van symbool te veranderen (+ naar - of andersom). B. We moeten op z’n minst van 1 edge het symbool veranderen zodat we de graaf structurally balanced kunnen maken. C. We moeten op z’n minst van 2 edges het symbool veranderen zodat we de graaf structurally balanced kunnen maken. D. We moeten op z’n minst van 3 edges het symbool veranderen zodat we de graaf structurally balanced kunnen maken. E. Geen van bovenstaande antwoorden. Page 10