Bouwen en Analyseren van Sociale Netwerken Project Sandra van Bockhooven 6081304
[email protected] Wendy G¨ unther 6052088
[email protected] December 11, 2011
1
1
Inleiding
Voor dit project was het de bedoeling om data van internet te verzamelen en hier een graaf van te maken, gebruikmakend van een bashscript. De graaf moest vervolgens geanalyseerd worden met behulp van een programma wat grafen kan visualiseren en analyseren, genaamd gephi. De nodes in de graaf zijn de medewerkers van ILPS(research staff en support staff), weergegeven met een aangepaste weergave van hun DBLPnaam. Er bevind zich een edge tussen twee personen wanneer ze samen een artikel geschreven hebben. De co-authors van de ILPS-medewerkers zijn te vinden op de DBLP website.
2
Data collection
Het verzamelen van de data hebben we opgedeeld in meerdere stappen. De graaf maken we bovendien zelf aan in het script, we hebben geen gebruik gemaakt van saxon. Voordat de volgende stappen worden uitgevoerd, wordt een mogelijk reeds bestaande graphml file opgeruimd. 1. Met behulp van de ILPS website de namen van researcg staff en support staff opslaan 2. De search urls van DBLP aanmaken met behulp van de voorafgaand opgeslagen namen. 3. Deze search urls uitvoeren op het internet waardoor je weer een nieuwe url krijgt. Deze worden opgeslagen als DBLP urls. 4. Vanuit deze DBLP urls kunnen de namen van de medewerkers worden opgeslagen zoals ze bij DBLP bekend zijn. 5. Nu kunnen de nodes worden aangemaakt die in de graphml file worden geplaatst. De nodes gebruiken de namen van DBLP. 6. De edges aanmaken door middel van de co-authors. Merk op dat nu ook edges zijn aangemaakt voor medewerkers buiten ILPS. Dus deze edges worden eruit gefilterd door gebruik te maken van de opgeslagen DBLP namen. Nu zijn er nog dubbele edges, want het is een ongerichte graaf, dus deze worden er ook uitgefilterd. 7. Nu heb je alle edges en nodes dus is de laatste stap om de werkelijke graphml file te maken. Doe dit door een bestand te vullen met de header van graphml, de nodes, de edges en als laatste de header af sluiten. Nadat deze stappen zijn uitgevoerd, worden de tijdelijke bestanden verwijderd. Zie appendix A voor de code van ons script.
3
Plots
Wanneer je de GraphML file inlaadt in Gephi kun je er een aantal dingen mee doen. Je kunt namelijk de nodes weergeven met een bepaalde grootte en kleur gebaseerd op hun degree, of bijvoorbeeld op het component waarbij ze horen. Ten eerste willen wij de nodes analyseren op basis van hun degree. Bijvoorbeeld, welk persoon heeft met de meeste andere verschillende personen samengewerkt? Dit zegt overigens nog niet gelijk iets over het aantal publicaties wat deze persoon heeft. Degene kan namelijk met meerdere personen slechts ´e´en keer hebben samengewerkt, en een andere persoon kan met ´e´en iemand heel veel hebben samengewerkt. De graaf die je krijgt wanneer je de Nodes groter laat zijn bij een hogere degree, en bovendien let op kleuren ziet er uit als in figuur 1. Je ziet bovendien dat wanneer de nodes een lage degree hebben en zeer klein zijn, dit voor de labels ook geldt. De kleuren die we hebben gebruikt voor de nodes zijn: Rood (voor een lage degree), Oranje(Voor een degree op de mediaan) en Groen (voor een hoge degree).Ook is te zien dat de edges een verschillende kleur hebben. Dit is op basis van het aantal publicaties waarbij de personen hebben samengewerkt. De bijbehorende tabel met de kleur en het bijbehorende aantal publicaties is te zien in figuur 2. Ook willen we kunnen zien in hoeverre de graaf bestaat uit verschillende componenten. De graaf die je krijgt wanneer je de Nodes dezelfde kleur geeft wanneer ze bij een zelfde component horen ziet er uit als in figuur 3.
4
Analyse graaf en nodes
In figuur 1 kun je duidelijk zien dat de persoon die met het grootste aantal verschillende personen heeft samengewerkt Maarten de Rijke is. Als we in de bijbehorende degree tabel (figuur 4) kijken die we hebben gekregen klopt deze conclusie ook: Maarten stijgt met zijn degree van 10 boven de rest uit. Bovendien kunnen we aan de kleur van de edges zien dat hij niet alleen veel heeft samengewerkt met andere mensen, maar dat hij met deze mensen ook nog eens een groot aantal publicaties op zijn naam heeft. Ook zien we dat een aantal mensen een degree van 0 heeft. Dat betekent niet gelijk dat deze personen nooit iets gepubliceerd hebben, echter het betekent wel dat ze nooit iets gepubliceerd hebben met iemand uit ILPS als co-author. Deze personen zullen we in het vervolg dan ook buiten beschouwing laten, omdat ze op zichzelf een te klein component vormen. Met dit in gedachte gaan we ons bovendien storten op de analyse per component. Je ziet in de graaf namelijk duidelijk ´e´en groot component en ´e´en kleiner component met een knopenaantal van 3. Om deze conclusie te bewijzen kijken we naar
2
Figure 1: Graaf gebaseerd op de degree
3
Figure 2: Kleur met bijbehorende aantal publicaties
4
Figure 3: Graaf gebaseerd op de components
5
Figure 4: Tabel gebaseerd op de degree
6
figuur 3 waarin we de knopen een kleur hebben gegeven per component. De bijbehorende tabel is te zien in figuur 5. In deze tabel zie je dat elk component een nummer heeft gekregen en dat inderdaad er twee componenten zijn wanneer we de nodes die op zichzelf staan buiten beschouwing laten.
4.1
Giant component
We zullen nu de analyse uitvoeren per component, beginnend met het grote component, ookwel genoemd ”the giant component”. De verdeling van de degrees binnen dit giant component blijft natuurlijk hetzelfde als bij de totale graaf, immers: geen van de nodes binnen dit component had een verbinding met een node uit een ander component, anders zou die andere node en zijn component wel onderdeel zijn geweest van de giant component.
4.1.1
Eccentricity
Wat ten eerste interessant is om te weten is wat de eccentricity is binnen dit connected component. Gephi kan daar heel makkelijk achter komen door een ”average path length” algoritme, waarbij de eccentricity, de betweenness centrality en de closeness centrality van de graaf in een tabel worden gezet. Laten we eerst eccentricity definiren: (wikipedia):”The eccentricity of a vertex v is the greatest geodesic distance between v and any other vertex. It can be thought of as how far a node is from the node most distant from it in the graph”. De eccentricity tabel die we hebben verkregen met Gephi is te zien in figuur 6. Zoals je kunt zien kan Maarten de Rijke binnen twee stappen iedereen binnen het component bereiken. Logisch is dan ook dat bijvoorbeeld Maria-Hendrike Peetz een maximale padlengte van 4 heeft. Namelijk: Binnen twee stappen kan zij Maarten de Rijke bereiken en van daaruit met maximaal 2 stappen weer ieder ander binnen het component. Wat we bovendien kunnen afleiden uit deze eccentricity-tabel zijn de radius en de diameter van dit giant component. Namelijk, de radius is gelijk aan de minimale eccentricity en de diameter is gelijk aan de maximale eccentricity. De radius is dus gelijk aan 2 en de diameter is gelijk aan 4. Gephi leert ons daarnaast dat de gemiddelde padlengte gelijk is aan 1.8461538461538463 voor dit component en dat er maar liefst 156 kortste paden bestaan. 4.1.2
Betweenness Centrality
(wikipedia):”Betweenness centrality is a measure of a node’s centrality in a network equal to the number of shortest paths from all vertices to all others that pass through that node”. De formule voor de Betweenness Centrality 7
Figure 5: Tabel gebaseerd op het component waar men bij hoort
8
Figure 6: Eccentricity binnen het giant component (v) luidt als volgt: g(v) = s6=v6=t σst σst , waarbij σst het totale aantal kortste paden is van node s naar node t en σst )(v) het aantal van die paden dat door node v gaat. De betweenness-centrality tabel die we hebben verkregen met Gephi is te zien in figuur 7. Wederom blijkt dat Maarten de Rijke een zeer grote rol heeft binnen dit component. Zijn betweenness centrality stijgt namelijk ver boven die van de rest uit. Dat betekent dus dat Maarten de Rijke op de meeste kortste paden ligt van elke node naar elke andere node binnen de graaf. De op een na grootste betweenness centrality geldt voor Christof Monz. Dit is ook wel logisch aangezien de enige manier waarop mensen naar Simon Carter kunnen, via hem is.
P
4.1.3
Closeness centrality
4.1.4
Clustering coefficient
De gemiddelde clustering coefficient per node is te zien in figuur 8. De clustering coefficient is een indicatie voor de mate waarin de buren van de node ook met elkaar verbonden zijn. Dit is dus het aantal verbindingen dat er daadwerkelijk bestaat tussen de buren gedeeld door het aantal verbindingen wat er mogelijk is.Zoals je in de figuur kunt zien is de clustering coefficient niet overal 1, wat inhoudt dat niet iedere buur met iedere andere buur ver9
Figure 7: Betweenness centrality binnen het giant component bonden is en het giant component dus ook duidelijk niet compleet is (wat we overigens ook al in de grafische weergave van de graaf konden zien). 4.1.5
Speciale nodes
Binnen de graaftheorie kunnen we spreken van ”speciale nodes”. Bijvoorbeeld, een node kan pivotal zijn voor een node X en Y, wanneer deze node op elk kortste pad tussen X en Y ligt. Ook kan een node een gatekeeper zijn, wanneer de graaf uit elkaar zou vallen als deze node wegvalt, of een local gatekeeper wanneer twee buren van de node geen verbinding met elkaar hebben. Zoals we net bij de betweenness centrality hebben gezien moet iedere node door Christof Monz heen om bij Simon Carter te komen. Dat betekent dat Christof Monz een gatekeeper is, en bovendien pivotel voor het paar Simon Carter met elke andere node. We zijn er ook al achter gekomen dat Maarten de Rijke duidelijk een zeer belangrijk persoon is en bovendien ook pivotal is voor meerdere paren nodes met Maarten Marx, Maria-Hendrike Peetz en Anne schuth. Wanneer Maarten de Rijke zou wegvallen zou het giant component uiteenvallen in twee components. Ook zien we dat bijvoorbeeld Edgar Meij een local gatekeeper is, aangezien deze wel verbonden is met Manos Tsagkias en Richard Berendsen, maar dezen niet met elkaar verbonden zijn.
10
Figure 8: Average clustering coefficient binnen het giant component 4.1.6
Speciale edges
De edge die loopt van Christof Monz tot Simon Carter is een bridge. Wanneer deze wegvalt, valt het giant component uiteen in twee components.
4.2
Small component
Het kleinere component bestaat eigenlijk maar uit 3 nodes: Lynda Hardman, Frank Nack en Anders Bouwer. Binnen dit component heeft Frank Nack de grootste degree en is bovendien een pivotal node voor de andere twee. Dat maakt hem ook gelijk een (local) gatekeeper en degene met de grootste betweenness centrality. Alle edges in dit component zijn bridges.
5
Problemen
Een probleem waar we tegen aangelopen zijn is dat sommige personen meerdere namen hebben. Zoals bijvoorbeeld Anders Bouwer heeft ook nog de naam Anders J Bouwer. De websites van deze twee zijn wel verschillend. Waarschijnlijk is de naam van deze persoon op een gegeven moment in zijn carriere veranderd en is de oude data van deze persoon niet bij zijn nieuwe website gevoegd. Wat we in de graaf duidelijk kunnen zien is ´e´en van de twee namen voor de personen voor wie het geldt een component op zichzelf 11
Figure 9: WordCloud gebaseerd op degree is en geen verbinding heeft met een van de andere auteurs. Aangezien we de enkele componenten toch buiten beschouwing laten bij onze graaf-analyse maakt de aanwezigheid van deze dubbele namen niets uit, anders dan het aantal componenten binnen de graaf als geheel.
6
Word Cloud
Tot slot hebben we een word cloud van de degree van de personen binnen ILPS gemaakt (figuur 9).
12
A
Code
#!/bin/sh #Cleanup the graphml before you begin. rm -r ’files/graph.graphml’ #Step 1: Get the names of the research staff and support staff from ILPS curl http://ilps.science.uva.nl/people | sed -n ’/
research staff<\/h2>/,/support staff<\/h2>/p’| grep ’View user profile’ | sed ’s/<[^>]*>//g’| sort >> files/namesILPS.txt #Step 2: Get search urls on DBLP while read LINE; do sed "s%^%http://dblp.uni-trier.de/search/author?author=%" | sed "s/ /+/g" >> files/searchurl.txt done < "files/namesILPS.txt"
#Step 3: Get the real urls. Problem: Some people have two names. while read LINE; do curl $LINE| grep -o ’http://dblp.uni-trier.de/db/indices/a-tree/./[^"]*.html’>> files/urlsDBLP.t done < "files/searchurl.txt" #Step 4: Get the names of the authors as they are on DBLP. while read LINE;do sed ’s%http://dblp.uni-trier.de/db/indices/a-tree/%% ; s%/xc%%’| sed ’s/.html//g’>> files/namesDBLP.txt done < "files/urlsDBLP.txt" #Step 5: Create all nodes using the DBLP names. while read LINE; do echo "<node id=\"$LINE\">\n \"$LINE\"\n eventuele andere info\n " | sed " ; s%[a-z]/%% ; s%[a-z]/%%" | sed ’s/:/ /g’>> files/nodes.xml done < "files/namesDBLP.txt" #Step 6.1: Create all edges by putting the DBLP names in a link. These edges # still have names outside ILPS in it, and double edges. 13
while read LINE; do curl http://dblp.uni-trier.de/rec/pers/$LINE/xc | grep ’%" | sed "s%\">[ ]*[A-Z].*%%" >>files/wrongedges.xml done <"files/namesDBLP.txt" #Step 6.2: Filter out the names that are not in ILPS and rename names # from b/Bouwer:Anders to Bouwer Anders rightnames=‘cat files/namesDBLP.txt | tr ’\n’ ’|’ |sed ’s/^/(/; s/|$/)/’‘ cat files/wrongedges.xml |grep -P "target=\"$rightnames\"" | sed " ; s%[a-z]/%% ; s%[a-z]/%%" | sed ’s/:/ /g’ >> files/wrong2edges.xml #Step 6.3: Filter out the dubbel edges like A-B is the same as B-A. while read LINE; do source=‘echo $LINE | grep -o ’source="[^"]*’ | sed ’s/source=\"//g’‘ target=‘echo $LINE | grep -o ’target="[^"]*’ | sed ’s/target=\"//g’‘ if [ "$source" \< "$target" ] then echo $LINE >> "files/edges.xml" fi done < "files/wrong2edges.xml" #Step 7: Final step, make the graphml file
#Step 7.1: Fill the header of the graphml file. echo " <desc> <meta debatetitle=\"Coauthors\"/> #Step 7.2: Fill the graphml file with the nodes. cat files/nodes.xml >> files/graph.graphml #Step 7.3: Fill the graphml file with the edges. 14
cat files/edges.xml >> files/graph.graphml #Step 7.4: Ending the graphml file. echo "\n" >> files/graph.graphml #remove all tempory files. rm -r ’files/edges.xml’ rm -r ’files/graph.graphml’ rm -r ’files/nodes.xml’ rm -r ’files/wrongedges.xml’ rm -r ’files/searchurl.txt’ rm -r ’files/namesDBLP.txt’ rm -r ’files/namesILPS.txt’ rm -r ’files/wrong2edges.xml’ rm -r ’files/urlsDBLP.txt’
15
