Sociale Netwerkanalyse van Gebruikersprofielen

Faculteit Wetenschappen Vakgroep Toegepaste Wiskunde en Informatica Voorzitter: Prof. Dr. G. VANDEN BERGHE

Sociale Netwerkanalyse van Gebruikersprofielen door Bert VERSLYPPE

Promotor: Dr. C. CORNELIS Scriptiebegeleider: P. VICTOR

Scriptie ingediend tot het behalen van de academische graad van licentiaat in de informatica, optie: informatie- en communicatietechnologie

Academiejaar 2006–2007

Voorwoord Met deze scriptie zet ik een punt achter mijn vier jaar durende studie. Hoewel het voor veel mensen logisch leek dat ik informatica ging studeren, was het voor mij niet zo evident deze keuze te maken. Vier jaar later moet ik echter met spijt in het hart vaststellen dat ik op het einde van deze periode beland ben. Het is een zeer boeiende tijd geworden. Ik wil hiervoor een aantal mensen bedanken. Ik heb in de eerste plaats veel te danken aan mijn ouders. Ze hebben me immers opgevoed, me hierbij veel kansen geboden, en — misschien voor een informaticus het allerbelangrijkste — ge¨ınvesteerd in computerhardware. Mijn zussen, mijn familie en mijn vrienden bedank ik voor de muziek, gezelligheid en kleur die ze aan mijn leven toevoegen. Zij hebben me gemaakt wie ik ben. Liesbeth, je steun en geduld hebben me geholpen om dit werk tot een goed einde te brengen. Ik wil mijn doopmeter, tante Maria, en nonkel Guido danken voor de vele vakanties die ik bij hun doorgebracht heb. Het is tijdens één van die “TM-kampen” dat mijn interesse en talent voor informatica ontdekt werd. Ik kreeg er de kans om verschillende vaardigheden te ontwikkelen. Mijn neef Bart wil ik bedanken voor alle uitleg, de “depannages” die in mijn beginjaren na experimenten soms nodig waren en het voorbeeld dat hij geweest is. Mijn promotor, Chris Cornelis, en mijn begeleidster, Patricia Victor, wil ik bedanken voor hun enthousiasme. Dat enthousiasme heeft mijn interesse voor dit scriptieonderwerp gewekt en heeft me over de streep getrokken om dit onderwerp te kiezen. Ik wil ze danken voor de kansen die ze me geboden hebben. Hun opbouwende kritiek en feedback maken van deze scriptie wat ze geworden is. Ik wil ook alle andere mensen bedanken die, direct of indirect, tot deze scriptie bijgedragen hebben. In het bijzonder wil ik Peter Mika bedanken voor zijn advies en antwoord op mijn vragen. Michel Klein wil ik danken voor zijn hulp bij het aanpassen van zijn bib2rdf-script.

Bert Verslyppe, mei 2007

i

Toestemming tot bruikleen “De auteur geeft de toelating deze scriptie voor consultatie beschikbaar te stellen en delen van de scriptie te kopiëren voor persoonlijk gebruik. Elk ander gebruik valt onder de beperkingen van het auteursrecht, in het bijzonder met betrekking tot de verplichting de bron uitdrukkelijk te vermelden bij het aanhalen van resultaten uit deze scriptie.”

Bert Verslyppe, mei 2007

ii

Overzicht Sociale Netwerkanalyse van Gebruikersprofielen door Bert VERSLYPPE Scriptie ingediend tot het behalen van de academische graad van licentiaat in de informatica, optie: informatie- en communicatietechnologie Academiejaar 2006–2007 Promotor: Dr. C. CORNELIS Scriptiebegeleider: P. VICTOR Faculteit Wetenschappen Universiteit Gent Vakgroep Toegepaste Wiskunde en Informatica Voorzitter: Prof. Dr. G. VANDEN BERGHE

Samenvatting In de sociale netwerkanalyse (SNA) wordt de sociale structuur die mensen vormen, bestudeerd. Ontstaan in de jaren ’60, kreeg de SNA door de opkomst van Web 2.0 en het Semantisch Web hernieuwde aandacht. Het doel van deze scriptie is het analyseren van de “Fuzzy Sets and Systems” onderzoeksgemeenschap door gebruik te maken van de technieken uit de SNA. Sociale netwerken en hun kadering in de nieuwe technologieën worden besproken in Deel I. Daarna staat in Deel II de analyse van de “Fuzzy Sets and Systems” onderzoeksgemeenschap centraal. In een eerste luik onderzoeken we het co-auteursnetwerk (dit is het sociaal netwerk dat onstaat door co-auteursrelaties). Gebruik makend van de sociale netwerkanalyse kunnen we belangrijke onderzoekers bepalen: verschillende rangschikkingen van onderzoekers worden opgesteld. Verder breiden we de analyse uit door het toevoegen van profielinformatie. Deze informatie gebruiken we om inhoudelijk verwante onderzoekers te bepalen. Hoewel de verzamelde dataset relatief ijl blijkt te zijn, geeft deze techniek reeds veelbelovende resultaten.

Trefwoorden Sociale netwerkanalyse (SNA), Folksonomieën, Co-auteursnetwerken, Gebruikersprofielen, Vaagverzamelingen

iii

Social Network Analysis of User Profiles [email protected] Supervisors: Dr. Chris Cornelis, Patricia Victor Abstract—In this thesis we build a social network and user profiles based on research papers. First, we build a social network of researchers in the “Fuzzy Sets and Systems” community based on coauthor relations found in a set of crawled “Fuzzy Sets and Systems” related articles. By using different social network analysis measures such as the degree, betweenness and closeness centralities, important researchers can be identified. In a second part, we extend the analysis by adding profile information. The information is handled using a method based on folksonomies. The profiles consisting of keywords are modelled using fuzzy set theory. Several fuzzy set operations can be used and we are able to identify related researchers. Keywords—Social network analysis, SNA Measures, Folksonomies, User Profiles, Fuzzy Sets

I. I NTRODUCTION

S

OCIAL network analysis (SNA) has been successfully used to identify important members in communities. The goal of this M.Sc. thesis is to examine the “Fuzzy Sets and Systems” research community. We want to identify important researchers based on coauthorship relations. Further on, we want to add profile information and find related authors. We give a short overview of social network analysis measures and we continue by introducing folksonomies. We build a social network based on coauthor relations and determine its properties in Section II. Then, we add profile information and calculate related authors (Section III). A. Social Networks A social network is a social structure of people, related (directly or indirectly) to each other through a common relation or interest. Social network analysis is the study of social networks to understand their structure and behaviour. Social networks are represented using graphs. An example is shown in Figure 1. Several measures can be used to analyse social networks. We distinguish two main categories: ego-centric measures and global measures. Ego-centric measures calculate an individual value for each actor, whereas global measures calculate one value for the complete network. For details, we refer to [1], which is a recent and widely cited handbook. Three classic ego-centric measures originating from social science are most widely known. The degree centrality of an actor is the degree of the vertex. The betweenness centrality for a node k is the number of shortest paths between two other nodes that go through k. The closeness centrality for a node

B A

J I

C

L

D E

G

H

is the average (shortest) path length between that node and all other vertices reachable from it. Centralities try to express the importance of the actors in the network. A more recent measure is the clusteringcoefficient, defined by Watts en Strogatz, and is defined as the number of edges between the neighbours of an actor divided by the maximum number of possible edges. Other measures like HITS and PageRank were developed in the context of ranking queryresults of search engines. Kleinberg proposed the “Hypertext Induced Topic Selection” (HITS) algorithm. This algorithm calculates two values called the “hubness” and “authority” for each vertex. A good authority is pointed to by a lot of good hubs, and a good hub is pointing to good authorities. PageRank was invented by Page and Brin and is the base of Google’s ranking system. In short, the PageRank of a page is the sum of the (distributed) PageRank of all pages pointing to that page. Global measures include global clusteringcoefficient (i.e. the average of all local clusteringcoefficients), average path length and diameter (i.e. the length of the longest shortest path in the network). B. Folksonomies In short, a folksonomy is a simple multi-user system for categorizing random items. All items are public and every user can add his own items to the folksonomy. Every item is tagged: tags are randomly chosen words, there are no explicitly defined relations between the tags. All users of the system thus cooperate by making their items (and the corresponding tags) public. Users tend to use the same tags to categorise different items: typically, for each tag there is a page containing all items described at least once by the tag. Popular examples of folksonomies include Flickr and Delicious1 . Several features are interesting for this work. The most important one is that it is possible to calculate related items, tags and users. Secondly, it can be shown that stable tag distributions for items emerge. We refer to [2] for a thorough discussion. Folksonomies gave us inspiration for the profile representation in which researchers will be tagged with keywords. II. C OAUTHORNETWORKS A coauthornetwork is a social network where the edges represent coauthorship in research papers. Before we can build the network, we have to define the community and collect information about it. A researcher is part of the “Fuzzy Sets and Systems” community if he/she has at least one publication in one of four given journals/conferences2 . The source of information is bibliographic data crawled from DBLP3 .

K

F

Fig. 1. A social network with twelve actors. Actors can be people, companies, researchers, etc. We can see two communities with actor H in between, acting as a connector.

1 http://www.flickr.com

and http://del.icio.us the journals “Fuzzy Sets and Systems” and “International Journal of Approximate Reasoning”, and the conferences “International Fuzzy Systems Association” and “IEEE International Conference on Fuzzy Systems”. 3 DBLP is a completely public bibliographic database and indexes journals and conferences in the domain of computer science. http://www. informatik.uni-trier.de/∼ley/db/ 2 namely

rank name 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Witold Pedrycz Didier Dubois Miguel Delgado Lluis Godo Henri Prade Ronald R. Yager Bernard De Baets Vladik Kreinovich Francisco Herrera Kaoru Hirota Antonio di Nola Philippe Smets Janos C. Fodor Serafin Moral Hung T. Nguyen Simon Parsons Rudolf Kruse Etienne E. Kerre Salvatore Sessa Michel Grabisch Radko Mesiar Isabelle Bloch Abraham Kandel Maria Amparo Vila Miranda Sankar K. Pal

degree 47 52 32 33 47 27 35 31 33 19 25 26 18 33 20 18 31 28 18 23 20 20 19 22 13

ego-centric SNA measures degree betweenness closeness average betweenness closeness clust.coef. rank rank rank rank 2 302897,09 1 4,2624 1 0,0444 1,33 1 152353,52 5 4,2908 2 0,1395 2,67 8 182475,10 2 4,3955 6 0,1935 5,33 5 123590,40 8 4,3159 4 0,2008 5,67 3 87874,36 16 4,3595 5 0,1591 8,00 12 129214,43 7 4,4037 8 0,0427 9,00 4 119350,28 10 4,5717 17 0,0706 10,33 9 102878,68 12 4,4997 12 0,0753 11,00 6 108955,92 11 4,6159 19 0,1515 12,00 30 163370,35 3 4,3972 7 0,0819 13,33 14 93375,11 13 4,5085 13 0,1167 13,33 13 80867,56 19 4,4506 10 0,3508 14,00 34 133619,12 6 4,3033 3 0,1569 14,33 7 81098,87 18 4,6345 21 0,2405 15,33 24 81152,19 17 4,4659 11 0,1158 17,33 35 121456,29 9 4,5456 14 0,3856 19,33 10 54155,22 32 4,5848 18 0,2688 20,00 11 90975,36 15 4,9193 45 0,1005 23,67 36 59909,93 26 4,4294 9 0,1961 23,67 17 35104,51 55 4,6803 24 0,3004 32,00 25 59725,53 27 4,9405 49 0,0947 33,67 27 45525,17 40 4,8249 37 0,3684 34,67 31 66274,33 23 4,9918 60 0,1345 38,00 20 37386,38 51 4,9253 46 0,2857 39,00 57 77765,04 20 4,8783 41 0,1282 39,33

Fig. 2. Ranking based on classic ego-centric SNA measures. The global ranking is derived from the average of the subrankings for each centrality.

After downloading all information of the given journals/conferences and extending the data by downloading all information of all authors encountered, we obtain a dataset containing 35006 publications, 29475 unique authors and 3598 original authors being part of the investigated community. From this dataset, we create two social networks: first, we build a simple network, and later we extend the analysis by building a network that incorporates weights and asymmetric links (called the DirectedWeighted network). A. Analysis of the Simple Network The Simple network is built by creating a vertex for each author and by drawing edges between two authors if they coauthored least one publication (see for example Figure 1). We start the analysis by determining the components of the graph. One big component contains about fifty percent of all researchers, while most other researchers are isolated or in small components containing two, three or four researchers. Most researchers have a degree between one and five. It can be shown that the degree is related to the components. We also calculate the clusteringcoefficients and find a correlation between the degree and clusteringcoefficients. To calculate closeness (or other path based measures) in a meaningful way, the graph needs to be connected. This is why we only consider the big component for calculating a global ranking. We compare the results of global measures with the ones for the complete network: we see that both networks are more or less equally structured. Using the classic SNA centralities (degree, betweenness and closeness), we build a table of most important researchers in the big component: this table is given in Figure 2. We see that there is a strong correlation between the different centralities.

network, but are interesting because they also take into account the importance of the neighbours of the researchers. Some researchers take advantage of this and climb in the ranking. HITS has a somewhat unclear interpretation regarding the difference between the authority and hubness of a node (as each node is both due to the returning arrow). The performance of HITS can be improved by removing the the edge with the smallest weight in each pair of edges. III. P ROFILES OF RESEARCHERS We want to extend the analysis with profile information. First we extend the dataset by adding keyword information. Using the electronic edition link, the keywords and abstract of each publication located on ScienceDirect4 are downloaded: 5492 publications and 21362 keywords (of which 13567 distinct) are found. We will call these keywords tags. This information is modelled using a graph that is built as follows. We start with one of the already discussed social networks and add a “new layer” of vertices representing each unique tag. For each use of a tag by an author, we draw an arrow from that author to the keyword. After this process, we remove tags that are used in less than three publications: these are artifacts or to “unique” keywords. In this representation we calculate some properties like tag use, most used tags, etc. To find related authors, we define a profile of an author as a fuzzy set over all unique tags. The degree of membership of a tag is defined as the number of times the author is tagged with that tag normalized by the maximum tag count of that author. The richness of the profile can be expressed using the sigma count (i.e. the sum of all degrees of membership) of the fuzzy set and the number of positive degrees of membership. Using these measures, we see that most profiles are relatively sparse. For each author, we calculate the ten most related profiles by comparing the sigma count of the (fuzzy) intersection with other profiles. Although we expected that coauthors yield related profiles, we can also identify related profiles of researchers that did not coauthor. IV. C ONCLUSIONS It is possible to identify important researchers using only the structure of the coauthor network. The Simple network already yields good results, while the DirectedWeighted analysis adds the influence of the neighbourhood of the researchers. Although the dataset is relatively sparse, we are able to show that the suggested technique for calculating related profiles already works. There probably is a lot of potential when a denser dataset is used, so more work has to be done to extend and improve the dataset. Research needs to be done to find a suitable definition of the richness of a profile and useful fuzzy set operations. Afterwards, we can examine the correlation between the coauthornetwork and the related profiles. ACKNOWLEDGEMENTS

B. Analysis of the DirectedWeighted network We extend the Simple network by adding weights and directed edges: every edge is replaced by two directed edges and the (outgoing) edge weight is set to the number of coauthored publications, normalised by the total number of publications of the author. The information obtained from path based centralities does not change as we did not change the structure of the network. After calculating HITS and PageRank it becomes clear that the results are closely related to the results from the Simple

The author would like to thank his supervisors for their support and feedback. R EFERENCES [1] J. Scott, Social Network Analysis: A Handbook, Sage Publications, 2000. [2] S.A. Golder and B.A. Huberman, “Usage patterns of collaborative tagging systems,” Journal of Information Science, vol. 32, no. 2, pp. 198–208, 2006.

4 http://www.sciencedirect.com

Inhoudsopgave Voorwoord

i

Toestemming tot bruikleen

ii

Overzicht

iii

1 Inleiding

3

I

6

State of the art: literatuurstudie

2 Sociale Netwerken 2.1 Wat zijn sociale netwerken? . . . . 2.2 Kadering uit de sociale psychologie 2.3 Grafentheorie . . . . . . . . . . . . 2.4 Extractie van sociale netwerken . . 2.5 Sociale netwerkanalyse . . . . . . . 2.6 Concrete toepassingen . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

3 Folksonomie¨ en 3.1 Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Omschrijving . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Concrete voorbeelden . . . . . . . . . . . . . . . . . . . . . 3.4 Sterktes en zwaktes t.o.v. traditionele classificatiesystemen 3.5 Eigenschappen . . . . . . . . . . . . . . . . . . . . . . . . .

II

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

. . . . .

. . . . . .

7 7 8 10 12 15 21

. . . . .

28 28 29 30 33 34

Analyse van de Fuzzy Sets and Systems netwerken

38

4 Co-auteursnetwerken 4.1 Extractie . . . . . . . . . . . . . . . . . . . 4.2 Analyse van het basisnetwerk . . . . . . . . 4.3 Analyse van het gerichte, gewogen netwerk 4.4 Besluit . . . . . . . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

39 39 41 44 47

5 Onderzoekersprofielen 5.1 Uitbreiding van de dataset . . . . . . . . 5.2 Representatie van de gebruikersprofielen 5.3 Bepalen van verwante profielen . . . . . 5.4 Besluit . . . . . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

56 56 57 60 62

1

. . . .

. . . .

INHOUDSOPGAVE

2

6 Besluit

65

III

68

Appendices: technisch

A Het Semantisch Web A.1 Bouwstenen voor het Semantisch Web . . . . . . . . . . . . . . . . . . . . . . . . A.2 Sesame RDF Repository . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69 69 71

B CookieMonster voor eindgebruikers B.1 Werkomgeving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.2 Gebruik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.3 Ontwikkeling van eigen taken . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

72 72 73 75

C CookieMonster onder de motorkap C.1 Situering . . . . . . . . . . . . . . . C.2 Ontwerp . . . . . . . . . . . . . . . C.3 Implementatie . . . . . . . . . . . . C.4 Mogelijke verbeteringen . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

76 76 76 77 81

D Bespreking CookieMonster taken D.1 Beheer van Sesame Repositories . . . . . . . . . D.2 Vullen van de dataset: crawlen en importeren . D.3 Opbouw van co-auteursnetwerken . . . . . . . . D.4 Sociale netwerkanalyse van co-auteursnetwerken D.5 Profielen . . . . . . . . . . . . . . . . . . . . . . D.6 Varia . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

82 82 83 86 88 89 92

E Takenlijsten E.1 Co-auteursnetwerken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E.2 Profielnetwerken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

94 94 97

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

Hoofdstuk 1

Inleiding Het valt niet te ontkennen dat het Web de laatste jaren een sterke evolutie heeft doorgemaakt. Er is (nog steeds) een verschuiving aan de gang zodat websites nu eerder van i.p.v. voor de gebruikers worden. Dit fenomeen wordt omschreven als het “Web 2.0”, hoewel de preciese betekenis van de term tot op heden vaag blijft. De term is in het jaar 2003 ontstaan en gaat over een nieuwe “generatie” van webtoepassingen die gebaseerd is op een ander gebruikersmodel enerzijds, en een verbeterde technologie anderzijds. In Figuur 1.1 wordt een overzicht van het Web 2.0 gegeven: het is een “mindmap” van nieuwe begrippen en technologieën die men beschouwt als deel uitmakend van Web 2.0. Wat de figuur interessant maakt, is dat haar opbouw typisch Web 2.0 is: in Web 2.0 termen zou men dit een tag cloud kunnen noemen. Op de figuur worden enkele pijlers van het Web 2.0 uitgewerkt. De voor deze scriptie belangrijkste pijler is “Participation”. De inhoud van het Web wordt nu door de gebruikers zelf gecreëerd. Zeer populaire voorbeelden hiervan zijn blogs, waar gebruikers in dagboekstijl hun gedachten met de wereld delen, en wiki’s, wat in feite webpagina’s met een editeerknop zijn (en die dus door de bezoeker direct en zonder technische kennis aangepast kunnen worden). Blogs zijn zeer invloedrijk en wijd verspreid. Een zeer bekend voorbeeld van het begrip wiki, is Wikipedia. Het doel van Wikipedia is om in elke taal een complete en vrije (zoals in vrijheid) encyclopedie op het Web te creëren. De artikels kunnen door elke bezoeker bewerkt worden, m.a.w. men vertrouwt erop dat de gemeenschap voor de correctheid van de artikels instaat. Wikipedia dient hierdoor evenwel kritisch wat betreft de juistheid en neutraliteit van de informatie bekeken te worden1 . Er zijn ook veel plaatsen waar gebruikers op een minder uitgesproken manier informatie aan het web toevoegen, zoals bijvoorbeeld bij folksonomieën (Eng. folksonomies) of aanbevelingssystemen (Eng. recommender systems). Samengevat zijn folksonomieën eenvoudige multi-user systemen voor het categoriseren van arbitraire items. Het categoriseren ontstaat doordat de gebruikers items voorzien van “tags”: dit zijn willekeurig gekozen woorden. Gebruikers werken samen door het delen van hun items én de corresponderende meta-informatie (tags). Verschillende eigenschappen kunnen vastgesteld worden: de belangrijkste is dat het mogelijk is om verwante items, tags en gebruikers te bepalen en dat er daarnaast stabiele tagverdelingen voor items verschijnen. Folksonomieën worden besproken in Hoofdstuk 3. In aanbevelingssystemen gaan gebruikers een waarde of een aanbeveling uitspreken over verschillende dingen, gaande van bijvoorbeeld films, boeken, muziek, tot zelfs andere gebruikers. In dat laatste geval spreken we 1

Gezien de sterk stijgende populariteit en diens gevolgen zoals bijvoorbeeld de hoge rangschikking in zoekresultaten, wordt er in deze scriptie een aantal keer gerefereerd aan Wikipedia. Deze kan evenwel niet instaan als vervanging voor peer-reviewde tijdschriften maar kan beschouwd worden als een, meestal zeer toegankelijk en uitgebreid, startpunt bij het verkennen van een bepaald domein. We willen de lezer dan ook aanmoedigen om deze referenties met een kritische houding te bekijken.

3

HOOFDSTUK 1. INLEIDING

4

Figuur 1.1: Web 2.0 mindmap. Figuur overgenomen van http://kosmar.de/archives/2005/ 11/11/the-huge-cloud-lens-bubble-map-web20 dan eerder over “vertrouwen” (zie Sectie 2.6.2). Bewust of onbewust werken gebruikers dus samen. Bij dit proces van samenwerking worden virtuele gemeenschappen gevormd. Deze gemeenschappen onstaan door sociale interactie zoals bijvoorbeeld in de blogwereld of op wiki’s. Sociale netwerkdiensten gaan hier nog een stap verder in. Met behulp van zo’n dienst kunnen gebruikers hun contacten beheren: iedere gebruiker kan een persoonlijk profiel opstellen en men kan andere gebruikers aan zijn lijst van vrienden of contacten toevoegen. Door te browsen of te zoeken in het systeem kunnen interessante gebruikers gevonden worden. In deze diensten wordt er dus expliciet een virtueel netwerk gebouwd van mensen die elkaar (zij het in levende lijve of enkel virtueel) kennen. Deze netwerken zijn precies wat we in deze scriptie bestuderen. Een sociaal netwerk is een sociale structuur van personen, direct of indirect verwant door een gemeenschappelijke relatie of interesse. Sociale netwerken worden voorgesteld met behulp van grafen en kunnen aan de hand van maten uit de sociale netwerkanalyse (SNA) bestudeerd worden. We geven een literatuuroverzicht van sociale netwerken en hun analyse in Hoofdstuk 2. Zelf bestuderen we het co-auteursnetwerk voor de “Fuzzy Sets and Systems” onderzoeksgemeenschap in Hoofdstuk 4. Voor we dit netwerk kunnen opbouwen, dienen we eerst de gemeenschap te definiëren en de gepaste informatie te verzamelen. Als informatiebron gebruiken we DBLP, een publiek beschikbare, on-line toegankelijke bibliografiedatabank die tijdschriften en conferenties in het domein van de computerwetenschappen indexeert. Uit deze dataset leiden we twee netwerken af: een eenvoudig en een uitgebreid, gericht en gewogen, netwerk. Beide netwerken worden geanalyseerd met behulp van de maten besproken in Hoofdstuk 2. Er worden verschillende rangschikkingen opgesteld en we vinden ook enkele verbanden tussen de SNA maten. We breiden in Hoofdstuk 5 de analyse uit met het toevoegen van profielinformatie. De inspiratie voor de “inhoudelijke” profielen van de onderzoekers werd gevonden bij folksonomieën: we taggen de onderzoekers met kernwoorden gevonden in hun publicaties. Onderzoekers zullen meer getagd worden met kernwoorden die ze vaker gebruiken dan andere: op deze manier zullen de belangrijkste tags een samenvatting van hun profiel voorstellen. We beschouwen twee

HOOFDSTUK 1. INLEIDING

5

verschillende modelleringen: een netwerkgebaseerde en een vaagverzamelinggebaseerde. De netwerkgebaseerde voorstelling gebruiken we om enkele gegevens over de tags te verzamelen en een filtering van de tags in te voeren. De vaagverzamelinggebaseerde voorstelling wordt afgeleid uit de netwerkgebaseerde voorstelling en gebruiken we om gerelateerde onderzoekers te vinden. We bepalen hiervoor de (vage) doorsnede van de twee profielen en gebruiken de (vage) kardinaliteit van de doorsnede om het verwantschap te bepalen. We gebruiken Semantisch Web-technologie als database back-end voor het opslaan van onze dataset. Het Semantisch Web wordt kort ge¨ıntroduceerd in Appendix A. Het Semantisch Web ontketende een hernieuwde interesse in sociale netwerken omdat deze netwerken nu expliciet gegeven kunnen worden maar dit wordt in deze scriptie niet verder uitgediept. Om de verschillende experimenten uit te voeren, ontwikkelden we CookieMonster. Dit is een applicatie waarmee taken in een lijst geordend kunnen worden, waarna deze takenlijsten uitgevoerd kunnen worden. Deze applicatie is generiek geschreven en kan ook voor andere doeleinden gebruikt worden. Het voordeel van zo’n applicatie is dat de resultaten zeer eenvoudig herhaald kunnen worden. Ook is het mogelijk om, met een minimum aan werk voor de onderzoeker, andere deeldomeinen te onderzoeken. CookieMonster wordt uitgebreid besproken in Appendix B, C en D.

Deel I

State of the art: literatuurstudie

6

Hoofdstuk 2

Sociale Netwerken Iedereen kan zich wel een beeld vormen van wie deel uitmaakt van zijn of haar kennissenkring; typisch zijn dat familieleden, vrienden en kennissen. Deze mensen hebben uiteraard op hun beurt allemaal opnieuw een kennissenkring (terug bestaande uit familie, vrienden of kennissen). De kans is echter groot dat er tussen deze nieuwe kennissenkringen gemeenschappelijke contacten voorkomen en we krijgen dus al snel een wirwar van mensen en relaties tussen deze mensen. We kunnen deze kennissenkringen gaan analyseren en deze uittekenen als een netwerk. Een wiskundige structuur die zich daar uitstekend voor leent, is een graaf. De graaf die dit netwerk beschrijft, noemen we een sociaal netwerk. Dit hoofdstuk introduceert sociale netwerken en de analyse hiervan. Omdat we ook relaties tussen tussen andere entiteiten (bv. bedrijven) kunnen gaan beschouwen, gebruiken we in deze tekst de term actor. Het is immers mogelijk om technieken en ideeën uit wat je “echte” sociale netwerken (personen en relaties tussen personen) zou kunnen noemen, ook in andere contexten toe te passen. Verloop van dit hoofstuk We gaan eerst nog wat dieper in op sociaal netwerken, waarin we een historische kadering uit de humane wetenschappen geven. We herhalen enkele begrippen uit de grafentheorie en geven een definitie voor het begrip sociaal netwerk. Verder onderzoeken we hoe we een sociaal netwerk kunnen opstellen en analyseren. We eindigen met enkele toepassingen.

2.1

Wat zijn sociale netwerken?

Een sociaal netwerk is een sociale structuur van personen, direct of indirect verwant door een gemeenschappelijke relatie of interesse. Sociale netwerkanalyse (SNA) is de studie van sociale netwerken om hun structuur en gedrag te begrijpen. Een formele definitie in de context van grafentheorie wordt gegeven in Sectie 2.3. We verwijzen de lezer naar [1] waarin een compact maar breed overzicht van de beschikbare literatuur omtrent sociale netwerken en hun analyse wordt gegeven. Afgaande op twee kenmerken, worden er vier soorten netwerken onderscheiden, nl. sociale, kennis-, cognitieve sociale en cognitieve kennisnetwerken [1]. Deze vier netwerken worden (deels overlappend) door verschillende sociale wetenschappen bestudeerd. Sociale vs. kennisnetwerken Wie kent wie of wie kent wat? Kennisnetwerken zijn bijvoorbeeld belangrijk in de bedrijfswereld. In een bedrijf is er vaak veel know-how aanwezig die niet ten volle wordt aangewend omdat de werknemers specifieke “experten” moeilijk of helemaal niet

7

HOOFDSTUK 2. SOCIALE NETWERKEN

8

vinden. Oorzaken hiervan zijn bijvoorbeeld verschillende vestigingen, internationalisatie, etc. Ook binnen een vestiging kunnen werknemers een moeizamer contact hebben met andere afdelingen. Op deze manier zijn werknemers soms niet in staat om van de in het bedrijf aanwezige know-how gebruik te maken. Met behulp van kennisnetwerken kunnen toepassingen worden ontwikkeld die voor een gegeven probleem een geschikte “expert” binnen het bedrijf vinden. Gewone vs. cognitieve netwerken Een cognitief netwerk is een verstandelijk (cognitief) netwerk dat de mensen omvat. Het gaat dus over de perceptie van het werkelijke sociaal netwerk. De gewone netwerken gaan uit van de werkelijke (meetbare) verwantschappen. Cognitieve netwerken komen bijvoorbeeld voor wanneer in een enquête gevraagd wordt naar de vrienden van de bevraagde. In tegenstelling tot bijvoorbeeld broer-zus of werknemer-baas relaties is het zeer moeilijk om de gegeven verwantschappen objectief vast te stellen of te meten. In de enquête zal de bevraagde zijn eigen perceptie van de relatie weergeven. Bij de bevraging van de relatie in de andere richting zou men tot een totaal verschillend resultaat kunnen komen wanneer bijvoorbeeld één partij de onderlinge relatie totaal verkeerd inschat. (Zie 2.2.2) In deze scriptie spreken we over gewone sociale netwerken. Sociaal omdat de actoren die we zullen bestuderen personen zijn, en gewoon omdat we de werkelijke relaties tussen de personen zullen in kaart brengen. In deel II zullen we een sociaal netwerk opbouwen aan de hand van tastbare informatie, het is dus duidelijk dat dit geen cognitief netwerk is.

2.2

Kadering uit de sociale psychologie

De moderne sociale netwerkanalyse stamt uit de sociale psychologie. Eén van de belangrijkste historische resultaten is wellicht dat van het small world phenomenon dat voor het eerst door Stanley Milgram experimenteel bevestigd werd. Eenvoudig gesteld, vraagt het small world problem hoe groot de kans is dat twee willekeurige mensen op de wereld elkaar kennen. We kunnen dit probleem veralgemenen door ook tussenpersonen toe te laten; algemeen zouden we ons dan kunnen afvragen hoeveel mensen we gemiddeld nodig hebben om deze twee personen te verbinden (als dit u ¨berhaupt al mogelijk is).

2.2.1

Small World Phenomenon

Men zou kunnen stellen dat Milgrams1 small world experiment [2] de basis legde voor de moderne sociale netwerkanalyse. In het experiment werd elke deelnemer gevraagd om een boodschap naar een bepaalde persoon (het doel) te brengen. Hij mocht hiervoor enkel gebruik maken van familie, vrienden of kennissen waarvan hij dacht dat er een grote kans bestaat dat deze de doelpersoon kenden (of iemand die de doelpersoon kende). De boodschap kon alleen maar naar mensen worden gestuurd die hij persoonlijk kende en dus bij de voornaam kon aanprekenaangesproken. In het eerste experiment werden twee startplaatsen gekozen (Wichita, Kansas en Omaha, Nebraska) met als respectievelijke eindpunten de vrouw van een theologiestudent aan Cambridge, Massachusetts en een effectenmakelaar die werkte in Boston en leefde in Sharon, Massachusetts. Elk startpunt (de deelnemers werden gekozen na het sturen van uitnodigingsbrieven) kreeg een omslag die een document met volgende informatie bevatte: 1 Stanley Milgram (15 augustus 1933 - 20 december 1984) is ook bekend van zijn gehoorzaamheidsexperiment in 1963 waarbij een proefpersoon vragen moest stellen aan een tweede proefpersoon in een andere kamer. Bij een fout antwoord moest de eerste proefpersoon een straf in de vorm van een elektroshock geven. De tweede proefpersoon was in werkelijkheid een acteur die de reacties simuleerde. Het resultaat was choquerend: ongeveer 80% van de deelnemers gaf electroshocks van dodelijke sterkte.


9

• De naam van de doelpersoon. • De regels die gevolgd dienden te worden bij het doorgeven van de omslag. De belangrijkste regel was hier wellicht dat de omslag enkel aan de doelpersoon mag gegeven worden als je deze persoonlijk kent (en je deze persoon dus niet direct mag contacteren). • Een tabel waarin elke deelnemer zijn naam schreef. De ontvanger kon zo zien van wie hij de omslag gekregen heeft en op deze manier konden lussen vermeden worden. De omslag bevatte ook nog 15 traceerkaarten die bij het ontvangen terug naar de onderzoeker moesten gestuurd worden. Op de vraag of het experiment zou werken kwam al zeer vlug een antwoord: na vier dagen werd de eerste omslag afgeleverd. Er werden slechts twee tussenpersonen gebruikt om de omslag op zijn bestemming te brengen. Na afloop van het experiment bleek het aantal tussenpersonen tussen twee en tien, met een mediaan van vijf te liggen. Het dient vermeld te worden (dit is trouwens één van de kritieken) dat slechts iets meer dan een vierde van de omslagen hun doel bereike. Voor een bespreking van de eigenschappen van de paden verwijzen we naar Milgrams artikel [2]. Het experiment werd later met verschillende variaties uitgevoerd, waaruit bleek dat er gemiddeld 5.5 tussenpersonen nodig waren. Dit is de oorsprong van de term “Six Degrees of Separation”. Moderne technieken stellen ons in staat om dit fenomeen gemakkelijk vast te stellen. Mika doet dit bijvoorbeeld voor zijn dataset van Semantisch Web onderzoekers (zie Sectie 2.6.1). Ook in ons eigen werk kunnen we dit (weliswaar maar in zekere mate) vaststellen (zie Sectie 4.2.4). Er zijn verschillende mathematische modellen die dit fenomeen proberen te verklaren. Omdat deze niet essentieel zijn voor wat verder volgt, worden ze niet verder beschreven, de ge¨ınteresseerde lezer verwijzen we naar [3]. We geven echter wel een inleiding tot de grafentheorie in Sectie 2.3 want we zullen deze wiskundige theorie gebruiken om sociale netwerken voor te stellen en kwantitatieve maten te berekenen.

2.2.2

Verschuiving van synthese naar analyse

Vanaf 1970 is het aantal publicaties (ge¨ındexeerd door Sociological Abstracts2 ) die “social network” in de titel of abstract bevatten, exponentieel beginnen groeien (zie Figuur 2.1). Hoewel sociale netwerken historisch gezien reeds door de sociale wetenschappen zeer breed onderzocht werden, is er vanaf de jaren 1990 een explosie in het aantal studies van sociale netwerken. Dit onderzoek wordt gestimuleerd door de beschikbaarheid van grote hoeveelheden data. We spreken daarom van een verschuiving van synthese naar analyse. De klassieke aanpak legt de klemtoon op synthese: het “samenvatten” van de eigenschappen van het netwerk zoals vastgesteld wordt aan de hand van enquêtes. Er zijn echter een aantal problemen. Er is een zekere vertekening van de resultaten; de perceptie van de mensen kan verkeerd zijn (cfr. cognitieve netwerken). Manueel uitgevoerde enquêtes hebben een hoge kost en de toenemende internationalisering van de sociale netwerken (bijvoorbeeld in de bedrijfswereld) brengt logistieke problemen met zich mee. Door het beschikbaar zijn van elektronisch communicatieverkeer (bv. onder de vorm van e-mail) kan men deze netwerken nu met een vrij fijne granulariteit en vrijwel zonder vertekening vastleggen. Hierdoor kan men de klemtoon verschuiven en zich eerder bezighouden met de analyse van de verschillende netwerken. 2

http://www.csa.com/factsheets/socioabs-set-c.php/ (bezocht op 17 mei 2007)


10

Figuur 2.1: Groei van het aantal publicaties (ge¨ındexeerd door Sociological Abstracts) die “social network” in de titel of abstract bevatten. Figuur overgenomen uit [4].

2.3

Grafentheorie

De grafentheorie is een wiskundige discipline die zeer bruikbaar is voor het modelleren van sociale netwerken. In deze sectie geven we een kort overzicht van de grafentheorie met enkele belangrijke begrippen die we verder zullen gebruiken. Voor een uitgebreider overzicht verwijzen we de lezer naar [5] waar onderstaande definities op gebaseerd zijn. Definitie 1 Een graaf G is een koppel G = (V (G), E(G)) bestaande uit een eindige verzameling V (G) van objecten (toppen) en een verzameling E(G) van paren van elementen uit V (G) (bogen). De verzamelingen V (G) en E(G) worden respectievelijk de toppenverzameling en de bogenverzameling genoemd. De orde van een graaf is het aantal toppen dat de graaf bevat. Enkele voorbeelden worden gegeven in Figuur 2.2. Hoewel grafen een eenvoudige structuur lijken te zijn, hebben ze veel meer mogelijkheden dan dat men op het eerste zicht zouden kunnen verwachten. We kunnen grafen uitbreiden met extra mogelijkheden die ons zullen helpen in onze sociale netwerkanalyse, nl. de notie richting en gewichten. Definitie 2 Een gerichte graaf is een graaf waarvan alle bogen gericht zijn. Een gerichte boog is een boog waarvan één van de eindpunten als kop aangeduid wordt, terwijl het andere eindpunt als staart aangeduid wordt. Een gerichte boog is gericht van zijn kop naar zijn staart. Definitie 3 Een gewogen graaf is een graaf waarbij met elke boog een getal, dat het gewicht van de boog genoemd wordt, geassocieerd wordt.


11

Figuur 2.2: Enkele voorbeelden van grafen. Men noemt de punten toppen en de lijnen die de punten verbinden bogen. Merk voor de meest rechtse graaf op dat we geen extra bogen meer kunnen tekenen. Deze graaf noemen we daarom de complete graaf van orde vijf en noteren we als C5 . Grafen met relatief weinig bogen noemen we ijle grafen. Het is mogelijk dat een graaf zowel gewogen als gericht is. Om gemakkelijker kwantitatief over grafen te kunnen spreken, voeren we het begrip buur in. Definitie 4 Adjacente toppen zijn toppen die verbonden zijn door een boog. De verzameling van de toppen die adjacent zijn met een top v noemen we de de burenverzameling van v. De graad grd(v) van een top v is het aantal buren van die top, m.a.w. het aantal toppen dat adjacent is met met v. Wanneer we vertrekken vanuit een top v kunnen we ons via zijn bogen verplaatsen naar adjacente toppen. Op deze manier kunnen we door de graaf “wandelen”, ons verplaatsend van top tot top. Definitie 5 Een pad is een opeenvolging van toppen zodanig dat elke top v bereikbaar is vanaf zijn voorganger u (m.a.w. v is een element van de burenverzameling van u) en dat er geen toppen herhaald worden. Het is mogelijk dat grafen bestaan uit onderling niet met elkaar verbonden “stukken” (deelgrafen). Het is dus niet mogelijk om een pad van het ene stuk naar het andere te vinden. Deze stukken noemen we componenten en we zeggen dat de graaf niet samenhangend is. Definitie 6 Een graaf G is samenhangend als er voor elk paar toppen u en v een pad van u naar v is. Definitie 7 Een graaf H is een deelgraaf van een graaf G als V (H) ⊆ V (G) en E(H) ⊆ E(G). Een component van een graaf G is een (maximale) samenhangende deelgraaf van G. Dit stelt ons in staat om een sociaal netwerk als een graaf te definiëren, wat ons toelaat om de terminologie, eigenschappen en algoritmes uit de grafentheorie te gebruiken. Definitie 8 Een sociaal netwerk is een graaf waarbij de toppen actoren voorstellen en de bogen relaties tussen deze actoren.


2.4

12

Extractie van sociale netwerken

Voor we sociale netwerken kunnen analyseren moeten we uiteraard over het netwerk (in de voorstelling van een graaf) beschikken. Met de extractie van een sociaal netwerk bedoelen we het reconstrueren (opbouwen) van dat netwerk aan de hand van beschikbare informatie. Deze informatie kan uit verschillende informatiebronnen geaggregeerd worden en kan van veranderlijke kwaliteit zijn. Het resultaat is een graaf waarbij de toppen actoren (personen) zijn, en de bogen sociale relaties (bv. “kent”, “is familie van”, “werkt samen met”,...) aangeven. Deze bogen kunnen gewogen zijn. We kunnen drie deelproblemen onderscheiden: (1) welke bronnen kunnen we gebruiken om het sociaal netwerk uit af te leiden (zie Sectie 2.4.1), (2) welk startpunt moeten we gebruiken en (3) wie behoort tot het netwerk dat we willen bestuderen, m.a.w. waar leggen we de grens. De laatste twee deelproblemen staan in verband met elkaar en worden besproken in Sectie 2.4.2.

2.4.1

Mogelijke bronnen

In deze sectie willen we de lezer een overzicht geven van de verschillende mogelijke informatiebronnen en het onderzoek dat er naar gedaan wordt. Deze lijst wil enkel een overzicht geven van wat mogelijk is en is dus (met opzet) niet volledig. E-mail De verzameling e-mails van een doelpersoon bevat een schat aan sociale netwerkinformatie zoals de correspondenten, de inhoud van de e-mails en de adresboeken van de gebruikers. De correspondenten zijn af te leiden uit het FROM, TO en CC veld van de e-mails. We beschikken over een e-mailadres (dat een gebruiker uniek identificeert) en meestal de bijhorende naam. Ook de inhoud van de e-mails bevatinformatie: we kunnen hieruit namelijk kernwoorden afleiden die bij bepaalde gebruikers horen. Verder bevat het adresboek gegevens die met de hand werden ingevuld. Een voorbeeld van hoe deze informatie wordt aangewend, is te vinden in [6]. Omdat veel e-mail niet publiek beschikbaar is3 , is het moeilijk om hierop onderzoek te doen. Hoewel men kunstmatig e-mail kan genereren, geeft dit niet de situatie zoals in de echte wereld weer. De Enron e-mail dataset is in die zin uniek omdat hij wellicht de enige aanzienlijke publieke verzameling real-world e-mail is: hij ontstond door het publiek maken van de e-mailverzameling van het management in de nasleep van het faillisement van Enron Corp4 . De dataset wordt nu verdeeld door William Cohen en bevat 517431 berichten van 150 gebruikers [7]. World Wide Web Het World Wide Web kan op verschillende manieren aangewend worden: we kunnen het web bijvoorbeeld gebruiken om persoonlijke webpagina’s terug te vinden of om bepaalde kwantitatieve waarden te bepalen. In [6] worden bijvoorbeeld persoonlijke webpagina’s verkregen door het creëren van een Google query met een bijhorende domeinterm (om in het geval van naamambigu¨ıteit irrelevante personen weg te filteren). De resultaten worden dan gefilterd gebruik makend van de eigenschappen van de URL en de inhoud van de pagina. Een pagina op het domein (of een ouderdomein) van het e-mailadres geeft bijvoorbeeld een sterke indicatie van de correctheid van de gevonden homepagina. Ook is het zo dat bij zeer veel URL’s van homepagina’s één of andere vorm van de naam voorkomt. Verder kan ook een taalmodel gebruikt worden om te bepalen of de inhoud van de pagina’s overeenstemt met wat verwacht kan worden. Eenmaal in het bezit van de persoonlijke webpagina van een persoon kunnen we 3

Merk op dat e-maillijsten hier soms een uitzondering op vormen Voor een overzicht verwijzen we de lezer naar http://en.wikipedia.org/wiki/Enron/ (bezocht op 17 mei 2007) 4


13

deze gebruiken om sociale verbanden met andere personen te vinden of om het profiel van de persoon te verrijken. Het ligt voor de hand hiervoor kernwoorden te gebruiken. Het bepalen van kernwoorden kan bijvoorbeeld gebeuren aan de hand van de T F × IDF (Term Frequency, Inverse Document Frequency) techniek [8]. Hoewel er verschillende varianten van de formule bestaan, geven we de variant zoals gegeven in [9]: T F × IDF = log(T F + 1) · log(|D|/DF )

(2.1)

De formule bestaat uit twee componenten: de T F (woordfrequentie) en IDF (omgekeerde documentfrequentie). Het belang van een woord T voor een document D is proportioneel met het voorkomen (de frequentie) van dat woord in het document en omgekeerd evenredig met het aantal documenten waar dat woord in voorkomt. Dit wordt weerspiegeld in de formule: T F is de woordfrequentie in een document en |D|/DF is het omgekeerde van de fractie van documenten waar het kernwoord in voorkomt. (|D| duidt op het aantal documenten in de beschouwde documentenverzameling, DF op het aantal documenten waar de term in voorkomt.) Varianten laten logaritmes weg of normalizeren de woordfrequentie op het aantal woorden in het document. Algemeen wordt een hoog T F × IDF gewicht bekomen door een hoge woordfrequentie en een lage fractie van documenten waar het woord in voorkomt. Op deze manier kan men met behulp van dit gewicht dus algemene termen (en stopwoorden) uitfilteren en woorden die een pagina karakteriseren bepalen. Mika gebruikt het aantal zoekresultaten van Google om de sterkte van de verbinding tussen twee actoren te bepalen [10, 11]. Eerst wordt het aantal zoekresultaten waar beide actoren in voorkomen bepaald. Daarna wordt dit resultaat genormaliseerd met het aantal zoekresultaten voor elke individuele actor. Links zijn dus niet symmetrisch: de sterkte van de link is afhankelijk van de richting. Op een vergelijkbare manier wordt de zogenaamde Google Mindshare5 bepaald. Merk op dat het gebruik van zoekmachines ook een zekere fout introduceert: het zoeken naar het voorkomen van namen op pagina’s wordt immers op een syntactisch niveau gedaan. Mensen die verschillende varianten van hun naam gebruiken of namen met internationale tekens kunnen op deze manier gemist worden. In het specifieke geval van Google kan ook het fenomeen Google Dance [12] de resultaten be¨ınvloeden. Google Dance komt voor wanneer Google zijn indices updatet. Dit gebeurt ruwweg eenmaal per maand. Google gebruikt DNS om “load balancing” te implementeren: dat maakt het mogelijk dat een query wordt uitgevoerd op een server waar de nieuwe index reeds aanwezig is, terwijl een tweede query wordt uitgevoerd op een server waar de oude index nog wordt gebruikt. Nieuwsgroepen Door hun publieke aard kunnen nieuwsgroepen ook bestudeerd worden. Elk bericht heeft velden zoals afzender, onderwerp en datum net zoals bij e-mail. Zeer belangrijk is het referentiesveld: hieruit kan men afleiden op welke post de post een reactie is. Op deze manier kunnen gesprekken (“threads”) afgeleid kunnen worden. Opnieuw kan de inhoud van de posts bestudeerd worden. Een voorbeeld van de analyse van een nieuwsgroep wordt gegeven in [9]. Hier worden verschillende soorten deelnemers zoals leiders, motivators en babbelaars (“chatters”) ge¨ıdentificeerd. Sociale netwerkdiensten en blogs Een “social network service” is een dienst speciaal gericht op het bouwen en onderhouden van een persoonlijk sociaal netwerk. De mogelijkheden hangen af van de gebruikte dienst en diens doelpubliek. Algemeen kan de gebruiker een persoonlijk profiel opmaken, typisch vergezeld van één of meer foto’s. Het is mogelijk om andere 5 De Google Mindshare van een persoon tot een bepaald concept is het aantal pagina’s waar zowel de persoon als het onderwerp in voorkomen gedeeld door het aantal pagina’s over die persoon.


14

gebruikers als “vrienden” te declareren, meestal is hiervoor een goedkeuring nodig van beide gebruikers vooraleer ze gelinkt worden. Er is doorgaans privacycontrole mogelijk door bijvoorbeeld (delen van) het profiel enkel zichtbaar te maken voor vrienden of te bepalen wie de gebruiker kan contacteren. Veel diensten bieden ook de mogelijkheid om groepen met een gemeenschappelijke interesse of verwantschap te creëren, foto’s of video’s te posten of deel te nemen in discussieforums. Er bestaan honderden verschillende diensten, al dan niet toegespitst op een specifieke gemeenschap of domein; enkele bekende voorbeelden zijn Orkut6 , LinkedIn7 , Friendster8 , MySpace9 , Yahoo groups10 en Windows Live Spaces11 . Een uitgebreide lijst van noemenswaardige sociale netwerkdiensten is te vinden op [13]. Een blog12 is een persoonlijke website waar in dagboekstijl toevoegingen aan worden gedaan. Deze toevoegingen worden in omgekeerd chronologische volgorde weergegeven. Blogs geven commentaar of nieuws over een bepaald onderwerp zoals politiek, fotografie of het persoonlijk leven van de auteurs. Een typische blog bevat geschreven tekst, foto’s en links naar verwante blogs of andere media. Blogs worden gelezen door miljoenen mensen en hebben een impact op de maatschappij. Veel sociale netwerkdiensten stellen ook bloginfrastructuur ter beschikking. Sommige van deze diensten bieden de informatie in de profielen ook in FOAF-formaat aan, zij het publiek of enkel voor leden. Onderzoek toont aan dat deze websites instaan voor een grote fractie van de beschikbare FOAF-documenten [14, 15]. Bij analyse van het gebruik van FOAF dient hiermee rekening gehouden te worden. Semantisch Web FOAF werd reeds eerder bespoken en is bijna per definitie geschikt om er sociale netwerken uit af te leiden. De publieke en gedistribueerde natuur van de documenten maakt het voor iedereen mogelijk om een persoonlijk FOAF-profiel beschikbaar te stellen. De mogelijkheid om links of verwijzingen naar vrienden toe te voegen, zorgen ervoor dat we kunnen spreken van een netwerk van FOAF-documenten. Er is veel literatuur beschikbaar over het gebruik en de analyse van FOAF data. Een voorbeeld voor de opbouw van een sociaal netwerk aan de hand van FOAF documenten is te vinden in [16] waarin drie stappen onderscheiden worden: 1. Instanties van foaf:Person vinden. Een typische manier om dit te doen is te vertrekken van een zoekmachine (bv. Swoogle [17, 18]) en het volgen van de links in de gevonden RDF documenten (rdfs:seeAlso). 2. De informatie van unieke individuen samenvoegen. Het kan voorkomen dat we in twee verschillende documenten informatie vinden over dezelfde persoon. We moeten dan deze informatie met elkaar in verband brengen en met elkaar samenvoegen. Dit wordt FOAF merging of FOAF smushing genoemd. Eigenschappen zoals bijvoorbeeld het e-mailadres van een actor kan deze actor uniek onderscheiden van alle andere. Wanneer we twee actoren met hetzelfde e-mailadres hebben, kunnen we (ervan uit gaand dat dit twee keer dezelfde actor is) deze actoren samenvoegen. 6

http://www.orkut.com/ (bezocht op 17 mei 2007) http://www.linkedin.com/ (bezocht op 17 mei 2007) 8 http://www.friendster.com/ (bezocht op 17 mei 2007) 9 http://www.myspace.com/ (bezocht op 17 mei 2007) 10 http://groups.yahoo.com/ (bezocht op 17 mei 2007) 11 http://spaces.live.com/ (bezocht op 17 mei 2007) 12 De term “weblog” werd door Jorn Barger voor het eerst gebruikt op 17 december 1997. De kortere vorm “blog” werd ge¨ıntroduceerd door Peter Merholz die al grappend het woord opsplitste in “we blog”. De term werd snel overgenomen en is bruikbaar zowel als werkwoord en als zelfstandig naamwoord. (“Bloggen” betekent het schrijven van blogs) 7


15

Eigenschappen die hun onderwerp op een unieke manier identificeren, noemen we inversfunctioneel (of injectief). In de context van FOAF kunnen we dus eigenschappen zoals foaf:mbox, foaf:mbox_sha1sum en foaf:homepage gebruiken om unieke individuen te identificeren. Eigenschappen zoals foaf:name en foaf:nick zijn niet strikt inversfunctioneel maar wel bruikbaar in combinatie met andere eigenschappen13 . 3. De persoon met behulp van sociale relatie-eigenschappen zoals foaf:knows verbinden. Deze links kunnen reeds in de documenten gegeven zijn. Men kan zich ook op andere informatie baseren om een relatie te veronderstellen.

2.4.2

Startpunt en grenzen

Voor we kunnen starten met het verzamelen van informatie over het sociaal netwerk moeten we definiëren welke actoren deel uitmaken van het netwerk. Men kan dit zeer eenvoudig oplossen door het geven van bijvoorbeeld een namenlijst, een organisatie waar de actoren lid moeten van zijn of een ander duidelijk gedefinieerd predikaat. Dit gegeven is zeer belangrijk voor de concrete implementatie aangezien het ons een criterium geeft waarop we de waarde van informatie kunnen beoordelen. De overmaat aan beschikbare informatie verplicht ons om deze beperking op te leggen. (Zonder filter verliezen we het overzicht en zien we m.a.w. door de bomen het bos niet meer). Hoe we precies starten met het verzamelen van informatie hangt af van de gekozen informatiebronnen. Zo kunnen we bijvoorbeeld voor het traditioneel en semantisch web gebruik maken van zoekmachines. In het geval van e-mail zullen we zelf moeten beschikken over de verzameling e-mail. Merk op dat dit enkel het begin is; de gevonden informatie kan ons pointers naar andere verwante bronnen geven (bv. links in de context van webpagina’s). Door het gebruiken van de nieuwe informatie kunnen we onze kennis stap na stap uitbreiden. Zoals later wordt uitgelegd is het zeer belangrijk om de grenzen van het netwerk te bepalen. Het wel of niet in rekening brengen van een actor kan immers een grote invloed hebben tijdens de analyse. Ironisch genoeg is het startpunt meestal ook de grens: men kan beslissen om alleen informatie van actoren in het gekozen startpunt te verzamelen (en dus geen verdere uitbreidingsstappen uit te voeren). Hierbij worden dan enkel verwijzingen binnen het gedefinieerde netwerk gevolgd. Indien men wel de verwijzingen volgt (men kan dit bijvoorbeeld doen tot op een bepaalde diepte), krijgen we een groter gedeelte in het sociaal netwerk dat zich aan de “buitenkant” of “waziggebied” bevindt. Dit stelt ons in staat om onverwachte relaties en structuren te ontdekken, maar kan ons afleiden van de beoogde gemeenschap.

2.5

Sociale netwerkanalyse

Na het opstellen van het sociaal netwerk kunnen we een analyse maken. Dit gebeurt aan de hand van metrieken of maten die voor de graaf (het sociaal netwerk) berekend worden. We onderscheiden twee grote klassen van maten, namelijk egogebaseerde maten en globale maten. De onderstaande lijst wil enkel een beperkt overzicht geven van enkele bekende metrieken (en kan dus helemaal niet als volledig beschouwd worden). De ge¨ınteresseerde lezer verwijzen we naar het recente en veel geciteerde handboek van Scott [19]. 13 De kans op naamambigu¨ıteit is groot, zeker in een internationale context. Ook moet men rekening houden met de verschillende varianten van een naam. Namen kunnen verschillen in “opmaak” (bv. het gebruik van initialen) of schrijfwijze (bv. accenten en andere lettertekens), tot zelfs in het gebruik van verschillende voornamen)


16

B A

J I

C

L

D E

G

H

K

F

Figuur 2.3: Een sociaal netwerk bestaande uit twaalf actoren. We kunnen twee deelgemeenschappen onderscheiden waarbij actor H optreedt als een bruggenbouwer. Actor D speelt een centrale rol in de linker deelgemeenschap.

2.5.1

Egogebaseerde maten

Egogebaseerde maten vertrekken uit de actoren. Hun resultaat is afhankelijk van de actor die als startpunt genomen wordt. Een groot deel van deze maten zijn zogenaamde “centraliteiten”. Centraliteiten proberen het belang van een actor uit te drukken en volgens deze waarden kan men de actoren dan gaan rangschikken. We beschrijven deze maten eerst voor een ongewogen, ongerichte graaf. Voor elk van deze maten bestaan er (uiteraard) gewogen en gerichte varianten, en indien relevant worden deze daarna beschreven. In wat volgt, noemen we de centrale of startactor het ego. Het begrip padlengte verwijst telkens naar de lengte van het kortste pad tussen het ego en een andere top. Graadcentraliteit De graadcentraliteit (Eng. degree centrality) is het aantal buren dat het ego heeft en is dus een maat voor het aantal contacten van de actor. Definitie 9 De graadcentraliteit van een actor is de graad van de actor. In een gerichte graaf kunnen we de in-graad (Eng. in-degree) en de uit-graad (Eng. out-degree) onderscheiden. In het voorbeeldnetwerk van Figuur 2.3 heeft actor D de grootste graad en dat maakt hem één van de centrale figuren van het netwerk. Hoewel men op het eerste zicht zou kunnen stellen “hoe meer contacten, hoe beter” is dit niet zo. Belangrijk is wie verbonden wordt, en hoe de anders onverbonden actoren verbonden worden. Het aantal is hierbij niet zozeer belangrijk; men kan bijvoorbeeld twee onverbonden “klieken” (deelgemeenschappen) of alle actoren binnen eenzelfde kliek verbinden. Spilcentraliteit Het spreekt voor zich dat een actor die twee anders onverbonden klieken verbindt in zekere zin belangrijker is dan een actor die reeds verbonden actoren opnieuw verbindt. Dit wordt uitgedrukt met de spilcentraliteit (Eng. betweenness centrality). Deze geeft een indicatie over het aantal kortste paden tussen andere actoren die langs het ego gaan. Definitie 10 Gegegeven een graaf G = (V, E) en drie toppen s, t, v ∈ V . We definiëren σst als het aantal kortste paden van s naar t en σst (v) als het aantal kortste paden van s naar t die


17

door v gaan. We nemen bij conventie aan dat σss = 1. De spilcentraliteit van een top v ∈ V van een graaf wordt dan gedefinieerd als CB (v) =

X s6=v6=t∈V

σst (v) σst

(2.2)

Een actor met een grote spilcentraliteit heeft een grote invloed op de doorstroom in het netwerk. De spilcentraliteit berekent in hoeverre actoren via het ego moeten gaan om andere actoren te bereiken. Het wegnemen van de actor kan ervoor zorgen dat actoren die anders verbonden waren, onverbonden worden. In het voorbeeld van Figuur 2.3 is H zo’n bruggenbouwer die de anders onverbonden linker- en rechterdeelgemeenschap verbindt. Het dient opgemerkt te worden dat de berekening voor deze kortste-pad-gebaseerde centraliteit niet zo evident is. Tot voor enkele jaren was het onmogelijk om deze berekening exact uit te voeren wegens de combinatorische explosie van het aantal mogelijke paden. Een algoritme met O(|V | + |E|) ruitme en O(|V | · |E|) tijd (dit wordt O(|V | · |E| + |V |2 log(|V |)) voor gewogen grafen) wordt gegeven in [20]. Nabijheidcentraliteit De nabijheidcentraliteit (Eng. closeness centrality) heeft te maken met lengte van de paden van het ego naar alle andere actoren in het netwerk. In zijn eenvoudigste vorm wordt de nabijheidcentraliteit berekend door hiervan het gemiddelde te nemen. Definitie 11 Gegeven een graaf G = (V, E). Stel dG (v, t) de lengte van het kortste pad tussen de toppen v en t. De nabijheidcentraliteit van een top v wordt dan gegeven door: P dG (v, t) CC 0 (v) = t∈V (2.3) |V | De nabijheid karakteriseert de bereikbaarheid van het ego vanuit alle actoren in het netwerk. Het kan dus gezien worden als een maat voor hoe lang het zal duren vooraleer informatie verspreid zal worden over het netwerk. Actoren met een lage nabijheid hebben een uitstekende positie om toezicht te houden op de informatiestroom in het netwerk; ze hebben immers het beste zicht op wat er gebeurt in het (volledige) netwerk. In Figuur 2.3 heeft actor G de laagste nabijheid (1,83). Actor D en actor H delen de tweede plaats met een nabijheid van 2,0: actor D profiteert van de vele rechtstreekse verbindingen en actor H maakt gebruik van zijn positie tussen de twee deelgemeenschappen. Merk op dat sommigen echter de definitie van Sabidussi [21] gebruiken die in essentie het omgekeerde van formule 2.3 is. De informatie is dezelfde, maar in plaats van de duurtijd spreekt men nu over propagatiesnelheid in het netwerk. Op deze manier wordt de nabijheidcentraliteit gegeven door: CC (v) = P

t∈V

1 dG (v, t)

(2.4)

Clusteringco¨ effici¨ ent De clusteringcoëfficiënt van een actor is een maat die bepaalt hoe goed de buren van die actor ge¨ınterconnecteerd zijn. Hij werd gedefinieerd door Watts en Strogatz [3] als het het aantal bogen tussen de buren van de actor gedeeld door het maximaal aantal mogelijke bogen14 . 14 Dit is in het geval dat de buren compleet met elkaar verbonden zijn. Als kv de graad van de actor v is, dan wordt dit aantal bogen gegeven door kv · (kv − 1)/2.


18

Definitie 12 Gegeven een graaf G en een top v. Stel kv = grd(v) en n het aantal bogen tussen de buren van v. De clusteringco¨ effici¨ ent van de top v wordt dan gegeven door: C(v) =

2n kv (kv − 1)

(2.5)

In het voorbeeld heeft actor H een clusteringcoëfficiënt van nul, en actor A een coëfficiënt van 2 3 . Het is duidelijk dat het netwerk in de buurt van actor A veel dichter verweven is dan in de buurt van actor H. Hubs en autoriteiten Kleinberg beschrijft in [22] een nieuwe techniek voor het selecteren van belangrijke webpagina’s als antwoord op een (zoek)query. In tegenstelling tot het gebruik van de inhoud (tekst) van webpagina’s om er eigenschappen uit af te leiden, bestudeert Kleinberg de structuur van de links. Met de tot dan toe gangbare technieken (het gebruik van de tekstinhoud) konden relevante pagina’s moeilijk onderscheiden worden van andere omdat deze pagina’s de zoekterm meestal zeer weinig gebruiken15 . Kleinberg stelt dat het creëren van een link op het WWW een concrete indicatie geeft dat de linkende pagina de gelinkte pagina beschouwt als een zekere autoriteit. We zouden autoriteiten kunnnen beschouwen als pagina’s met een grote in-graad. Dit is echter niet voldoende: op deze manier zullen niet alleen de thematisch relevante maar ook universeel populaire pagina’s als autoriteiten beschouwd worden. Relevante pagina’s moeten dus niet alleen een grote in-graad hebben, maar er moet ook een noemenswaardige overlap zijn in de verzamelingen van linkende pagina’s. Dus moeten we, naast de autoriteiten ook nog hubs invoeren. Dit zijn pagina’s die links hebben naar verschillende relevante autoriteiten. Een goede hub is een pagina die naar goede autoriteiten linkt, en een goede autoriteit is een pagina die door veel goede hubs gelinkt wordt. Kleinberg geeft het “Hypertext Induced Topic Selection” (HITS) algoritme [22] waarmee de hub- en autoriteitswaarde berekenend kunnen worden. Het algoritme bestaat uit twee operaties die we I en O noemen. In de I-stap wordt het autoriteitsgewicht van een pagina bepaald als de som van de hubgewichten van alle pagina’s die verwijzen naar die pagina. Daarna wordt in de O-stap het hubgewicht van een pagina bepaald als de som van de autoriteitsgewichten waar naar verwezen wordt. De autoriteits- en hubgewichten worden genormaliseerd zodat de som van hun kwadraten één is. We kunnen starten met willekeurige waarde hub- en autoriteitswaarden. Wanneer we nu verschillende keren over deze stappen itereren, dan zullen de waarden convergeren. Dit wordt formeel bewezen. PageRank PageRank [23] werd door Page16 ontworpen om, net zoals bij het HITS algoritme, relevante pagina’s te identificeren. Opnieuw wordt er gebruik gemaakt van de structuur van de links om belangrijke pagina’s te identificeren, maar er zijn enkele belangrijke verschillen. Er wordt maar één, globale, waarde berekend, en dit gebeurt reeds tijdens het indexeren (in tegenstelling tot HITS waar twee waarden, enkel voor het deeldomein en tijdens het verwerken van de query, berekend worden). Hoe dit past in het ontwerp van een zoekmachine wordt gegeven in de originele Google paper [24]. 15

Merk op dat we spreken over het pre-Google tijdperk. Google maakt gebruik van het PageRank algoritme om zijn zoekresultaten te ordenen en zal op deze manier goede resultaten teruggeven. Dit algoritme baseert zich ook op de verbindingen tussen de pagina’s en wordt later besproken. 16 De naam PageRank is afkomstig van de naam Page, en niet van het woord pagina zoals soms gedacht wordt.


19

Figuur 2.4: Een voorbeeld van het PageRank (vereenvoudigde versie) algoritme in evenwicht op een web van zeven pagina’s. Merk op hoe de rank gelijkmatig over de verschillende gelinkte pagina’s verdeeld wordt. Figuur overgenomen uit [25]. Intu¨ıtief kunnen we PageRank als volgt omschrijven: een pagina heeft een hoge rang (Eng. rank) als de som van de rangen van de linkende pagina’s hoog is. Merk op dat dit meer is dan rangschikken op in-graad: een pagina krijgt een hoge rangschikking als hij gelinkt wordt door veel pagina’s, maar ook als hij gelinkt wordt door enkele pagina’s met een hoge rangschikking. Een voorbeeld van PageRank in evenwicht wordt getoond in Figuur 2.4. Men ziet gemakkelijk dat de PageRank van een pagina de som van de gewichten van de inkomende bogen is, en dat de som van de uitgaande bogen van een pagina gelijk is aan de rang van die pagina. Meer formeel kunnen we (een vereenvoudigde versie) van PageRank definiëren als volgt. Stel Bu de verzameling van pagina’s die linken naar u. Stel grd+ (u) de uitgraad van top u en c een normalisatiefactor zodat de som van de rang van alle pagina’s constant is. De rang R van een pagina u wordt nu gegeven door R(u) = c

X v∈Bu

R(v) grd+ (v)

(2.6)

De rang wordt dus gelijkmatig verdeeld over de gelinkte pagina’s om bij te dragen tot hun rang17 . De formule is recursief maar zal vertrekkend van willekeurige startwaardes na verschillende iteraties convergeren. Er is wel een probleem met deze eenvoudige vorm: stel dat er twee 17

Het is ook mogelijk om de rang te verdelen volgens een willekeurige i.p.v. een uniforme verdeling. Links die bijvoorbeeld een grotere kans hebben om op geklikt te worden, kunnen een grotere fractie van de rang van de linkende pagina doorgeven.


20

pagina’s zijn die enkel naar elkaar linken, en een derde die naar één van die twee pagina’s linkt. Tijdens het itereren zal de rang van de pagina’s cummuleren, maar nooit verder verdeeld worden omdat er geen pijlen zijn die ontsnappen aan deze lus. Dit is een soort van val die Page een “rank sink” noemt. Om dit probleem op te lossen introduceert hij een extra vector E(u) (die hij de “source of rank” noemt) en die tijdens de berekening bij de rang wordt opgeteld. Voor een uitgebreide bespreking verwijzen we de lezer naar het artikel [23]. Opmerking Merk op dat niet in kaart gebrachte verbindingen een grote invloed op de resultaten van bovenstaande maten kunnen hebben! Beschouw bijvoorbeeld een actor met veel contacten die de onderzochte gemeenschap verbindt met een andere gemeenschap. Als in de analyse de contacten met de andere gemeenschap niet beschouwd worden, vermindert de graad- en spilcentraliteit van deze actor. Op deze manier kan hij veel minder belangrijk lijken dan hij in werkelijkheid is. De grens van het netwerk dient dus met zorg gekozen te worden en de resultaten van actoren op die grens moeten kritisch ge¨ınterpreteerd worden.

2.5.2

Globale maten

Globale maten berekenen één globale waarde. Ze geven informatie over de structuur van het netwerk zelf. Globale Clusteringco¨ effici¨ ent De globale clusteringcoëfficiënt is een maat die aanduidt hoe geclusterd het volledig netwerk is. Hij wordt gedefinieerd als het gemiddelde van de lokale clusteringcoëfficiënten. Definitie 13 Gegeven een graaf G = (V, E) met |V | toppen v ∈ V . De globale clusteringco¨ effici¨ ent wordt gedefinieerd als 1 X C= C(v) (2.7) |V | v∈V

Gemiddelde verwijdering Definitie 14 De gemiddelde verwijdering (Eng. average path length) is de gemiddelde (kortste) padlengte tussen alle paren van actoren. Het belang van de gemiddelde verwijdering is dat het een maat is voor de efficiëntie van de informatiedoorstroom in het netwerk. In netwerken met een grote gemiddelde verwijdering zal het immers langer duren vooraleer informatie volledig is doorgestroomd. Hoewel er een sterke correlatie is, dient de gemiddelde verwijdering niet verward te worden met de nabijheidcentraliteit (die een egogebaseerde maat is) en de diameter van het netwerk. Definitie 15 De diameter van een netwerk is de lengte van het langste kortste pad in het netwerk. Met andere woorden: als men alle (kortste) paden tussen alle paren van toppen beschouwt, dan is de diameter de lengte van het pad met de grootste lengte. De diameter van het voorbeeld is 7: een voorbeeld van zo’n langste pad is A, D, G, H, I, J, L. Merk op dat de route via de actoren B en C (A, B, C, G, H, I, J, L) geen geldig pad vormt omdat dit niet het kortste pad tussen A en L is.


2.5.3

21

Deelgemeenschappen vinden

Ervaring leert dat grote gemeenschappen zich vaak in kleine groepen van sterk verweven individuen opsplitsen. Deze kleine groepen interageren occasioneel met elkaar maar zijn onderling veel minder met elkaar verweven. Het is interessant om deze deelgemeenschappen in het netwerk te kunnen identificeren. We onderscheiden twee fundamentele werkwijzen, namelijk het gebruik van clusteringalgoritmes en het gebruik van extra attributen. Het nadeel van het gebruik van clusteringalgoritmes is dat het oordeel van de onderzoeker meestal nodig is om uit te maken wat het beste resultaat van het algoritme is omdat deze algoritmes meestal iteratief werken. Het meest eenvoudige clusteringalgoritme kijkt enkel naar de verschillende componenten van het netwerk. Indien het netwerk niet volledig verbonden is, bestaan er verschillende disjuncte componenten. We kunnen deze componenten dan beschouwen als deelgemeenschappen. Merk op dat deze techniek voor veel netwerken niet gebruikt kan worden (omdat ze volledig verbonden zijn). Andere clusteringalgoritmes werken door het iteratief verwijderen van bogen tot de gewenste deelgemeenschappen ontstaan. De onderzoeker moet dan zelf bepalen wanneer het gewenste resultaat bereikt is (omdat het aantal te verwijderen bogen afhangt van de structuur van het netwerk). We hebben dus ook een criterium voor het selecteren van te verwijderen bogen nodig; daarvoor kan bijvoorbeeld de spilcentraliteit gebruikt worden, maar dan voor bogen i.p.v. toppen18 . De resulterende informatie kunnen we dan gebruiken om te bepalen welke bogen we gaan verwijderen, nl. deze met de hoogste spilcentraliteit. Het algoritme werkt dus door iteratief eerst de spilcentraliteit van de bogen in de resulterende graaf te berekenen en daarna de boog (of een geparametriseerd aantal bogen) te verwijderen met de grootste spilcentraliteit. In elke iteratie wordt dus de spilcentraliteit opnieuw berekend. We kunnen ook van extra data (attributen of informatie van de actoren) gebruikmaken. Attributen zoals bijvoorbeeld de vakgroep of de universiteit (in het geval van onderzoekers) kunnen gebruikt worden om onderzoekers in verschillende groepen te verdelen. De mogelijkheden hangen af van de kwaliteit (betrouwbaarheid) en kwantiteit (beschikbaarheid voor elke actor) van de meta-informatie. Ook het soort meta-informatie is belangrijk; het is bijvoorbeeld duidelijk dat de naam van de vakgroep van een onderzoeker in dit opzicht interessanter is dan het aantal citaties.

2.6

Concrete toepassingen

We illustreren het gebruik van sociale netwerken aan de hand van enkele concrete voorbeelden. De eerst besproken toepassing (Flink) analyseert het sociaal netwerk van Semantisch Web onderzoekers en maakt daarbij gebruik van de hierboven beschreven maten. Flink is in essentie een website die de resultaten van de analyse voor de gemeenschap van Semantisch Web onderzoekers presenteert en werd ontworpen door mijn begeleider Peter Mika. Flink was een inspiratiebron voor wat volgt in deel II. De tweede toepassing kan men zien als een uitbreiding op sociale netwerken; hier wordt het vertrouwen tussen verschillende actoren gemodelleerd in een vertrouwensnetwerk. Het vertrouwen kan dan bijvoorbeeld gebruikt worden om voorspellingen te doen over de belangrijkheidsgraad van een bepaalde e-mail, of een verbeterde (in feite gepersonaliseerde) voorspelling over de waardering van films geven. 18

De spilcentraliteit voor een boog e ∈ E in een graaf G = (V, E) wordt gedefinieerd als CB (e) =

X σst (e) σst

s6=t∈V


2.6.1

22

Flink

Flink [11] is een voorstelling van het werk en de sociale verbanden van Semantisch Web onderzoekers waarmee de ontwerper (Peter Mika) de “Semantic Web Challenge Award 2004 for best application of Semantic Web technology” won. Hij definieert de Semantisch Web gemeenschap als alle onderzoekers die publicaties hebben voorgesteld op, of die deel uitmaakten van de organisatie van de International Semantic Web Conferences (ISWC). In Flink wordt deze gemeenschap bestudeerd vertrekkende vanuit het sociaal netwerk. Wanneer de gebruiker een startpunt heeft gekozen, geeft het systeem een overzichtspagina die profielinformatie van de geselecteerde onderzoeker en links naar andere onderzoekers teruggeeft. De omgeving van de onderzoeker wordt ook grafisch (als een netwerk) weergegeven. Een voorbeeld van zo’n pagina is te vinden in Figuur 2.5. De architectuur wordt voorgesteld in Figuur 2.6. We onderscheiden drie lagen: verwerving (extractie) van meta-informatie, opslag en visualisatie. Verwerving gebruikt:

Voor de verwerving van informatie worden er vier verschillende kennisbronnen

• Webpagina’s. Dit onderdeel gebruikt Google om het aantal zoekresultaten van paarsgewijs samengenomen namen te bepalen. De sterkte van de relatie tussen twee individuen wordt dan bepaald door dit resultaat te normaliseren met het aantal zoekresultaten voor het individu. Op een vergelijkbare manier worden de relevante onderzoeksonderwerpen voor de onderzoekers bepaald met behulp van de Google Mindshare. • FOAF profielen verkregen van het semantisch web. Dit gebeurt in twee stappen. Eerst zal een RDF crawler profielen uit het FOAF-web verzamelen. De crawler beweegt in het netwerk door het volgen van links in FOAF documenten (rdfs:seeAlso). Er wordt voor gezorgd dat er enkel potentieel interessante triples worden gedownload door bijvoorbeeld te lange documenten of grote FOAF producenten zoals blogwebsites te negeren. In een tweede stap worden de door de crawler gevonden individuen gematcht tegen de profielen van de doelgemeenschap, om zo enkel de relevante profielen te weerhouden. • E-mail wordt gedownload van een POP3 of IMAP server en de headerinformatie wordt in RDF formaat vastgelegd. FOAF wordt gebruikt voor het voorstellen van de zenders en ontvangers van de berichten. Opnieuw wordt enkel de relevante informatie weerhouden. • Bibliografische data wordt verkregen door gebruik te maken van Google Scholar. Er wordt op naam gezocht samen met een extra term om naamambigu¨ıteit te vermijden. De titel, de locatie, het jaar van publicatie en het aantal citaties wordt voorgesteld in SWRC formaat. Opslag De geaggregeerde verzameling van RDF data wordt bewaard in een Sesame RDF repository (zie Sectie A.2). Omdat het datamodel een uitbreiding van FOAF is, is het mogelijk om deze informatie te gebruiken met andere FOAF-compatibele software. Mika geeft als voorbeeld de “ESRI Place Finder Sample Web Service” die de geografische locaties (coördinaten) van meer dan drie miljoen plaatsnamen wereldwijd teruggeeft. Op dit niveau wordt er ook aan inferentie gedaan. Met behulp van regels kunnen mappings en metakennis uitgedrukt worden. Co-auteurs van publicaties of zenders en ontvangers van mail kennen elkaar bijvoorbeeld ook in de FOAF betekenis van het woord. Ook worden regels gebruikt om “smushing” te doen. Smushing is het bepalen van verschillende instanties van dezelfde persoon in de RDF data. Hiervoor wordt gebruik gemaakt van invers-functionele eigenschappen zoals het e-mailadres of de homepagina.


23

Figuur 2.5: Deel van de Flink-overzichtspagina van Peter Mika. Bovenaan zien we het sociaal netwerk met daarnaast enkele SNA maten en een ranking. Daaronder volgt een lijst van alle gevonden informatie. Niet weergegeven is de lijst van contacten, interesses, publicaties en emails. Flink is beschikbaar op http://flink.semanticweb.org/.


24

Figuur 2.6: De architectuur van Flink vertrekkende vanaf de verwerving (bovenste laag) tot de gebruikersinterface (onderste laag). Figuur overgenomen uit [11]. De naam van de onderzoeker kan ook gebruikt worden, zij het in beperkte mate (er is naamambigu¨ıteit mogelijk en de naam wordt niet altijd op dezelfde manier geschreven door bijvoorbeeld het weglaten of afkorten van de voornaam). Met behulp van de owl:sameAs relatie worden twee verschillende instanties “samengevoegd”. Visualisatie en analyse De profielinformatie en het sociaal netwerk is gebaseerd op de analyse van webpagina’s, e-mails, publicaties en (door de onderzoekers zelfgemaakte) FOAF-profielen. Komen we even terug op Figuur 2.5. De getoonde pagina bevat bovenaan een grafische voorstelling van het netwerk (in de vorm van een graaf). Daarnaast worden de waarden van enkele bekende SNA-maten samen met de plaats op de globale rangschikking weergegeven. Verder wordt alle gevonden informatie (dit omvat de naam, e-mail, homepagina, geografische informatie, interesses, deelname aan verwante conferenties, e-mails verzonden naar publieke mailinglijsten en publicaties) gegeven. Navigatie kan gebeuren door op één van de co-auteurs of geadresseerden te klikken. In dat geval wordt er een pagina getoond met het bewijs dat het bestaan van de relatie aantoont. Verder is er een pagina die een overzicht geeft van de statistieken van het systeem. Er wordt een rangschikking van de onderzoekers gegeven volgens de in-graad, nabijheid, spilcentraliteit, publicaties en impact. Op een andere pagina wordt het volledige sociaal netwerk getoond en is het mogelijk om dit netwerk te clusteren. Hiervoor wordt er een java-applet gestart dat de gebruiker de kans geeft om via een regelaar in te stellen hoeveel bogen verwijderd moeten worden. De informatie over de interesses van de onderzoekers wordt ook gebruikt om een ontologie van onderzoeksonderwerpen van de Semantisch Web gemeenschap te creëen. De sterkte van het verband tussen twee onderwerpen wordt bepaald door het aantal onderzoekers die een interesse in het gegeven paar onderzoeksonderwerpen hebben. Er is een pagina waar deze informatie gevisualiseerd wordt aan de hand van een graaf.


2.6.2

25

Vertrouwensnetwerken

Eén van de grote doelen van het Semantisch Web is het zogenaamde “Web of Trust”. Veel onderzoek is reeds gedaan naar de authenticatie van bronnen, digitale handtekeningen en publieke sleutels. Het vertrouwen in de oorsprong (bijvoorbeeld een bron of auteur) van een document is belangrijk, maar is in zekere zin onvolledig: de bevestiging van de echtheid van een bron betekent immers niet dat een gebruiker deze bron vertrouwt, aanvaardt of voor waar aanneemt. Jennifer Golbeck werkt rond dit soort vertrouwen (zie b.v. [26]). Golbecks bijdrage tot het “Web of Trust” is dat ze het sociaal netwerk als invalshoek neemt. We kunnen vertrouwen op verschillende manieren bepalen. Men kan bijvoorbeeld stellen dat vertrouwen een verband heeft met het onderliggend sociaal netwerk omdat het kennen van individuen een basis kan zijn voor het vertrouwen in deze individuen. Vertrouwen is echter meer dan dat; het vertrouwen is nl. gericht (het is niet omdat A B vertrouwt, dat B A vertrouwt) en gewogen (vertrouwen is gradueel i.p.v. binair). In het model kunnen kunnen gebruikers andere gebruikers vertrouwen geven op een schaal van één tot tien. Tien drukt hierbij volledig vertrouwen uit, één volledig wantrouwen en vijf neutraal vertrouwen. Dit vertrouwen kan algemeen, of beperkt tot een specifiek onderwerp gegeven worden. Ze creëert hiervoor een trust ontologie [26] die de foaf::Person klasse uitbreidt door er extra vertrouwenseigenschappen aan toe te voegen. Het is ook mogelijk om vertrouwen uit te drukken voor specifieke domeinen; hiervoor wordt de TrustRegarding klasse gedefinieerd die de eigenschappen trustsPerson en trustsOnSubject bevat. Op deze laatste wordt er geen enkele beperking gelegd; de gebruiker is volledig vrij om elk mogelijk onderwerp uit elke mogelijke ontologie te specificeren. Deze data is, net zoals bij gewone FOAF documenten, gedistribueerd. Propagatie van vertrouwen Een belangrijk probleem in vertrouwensnetwerken is het inschatten van het gewicht van een niet bestaande boog in het netwerk. Hiervoor werden er propagatiealgoritmes ontworpen die, bovenop het vertrouwen bepaald door de directe links tussen individuen, het vertrouwen voorspellen tussen niet direct verbonden individuen door de ontbrekende link te berekenen. We kunnen deze algoritmen indelen in lokale en globale metrieken. Lokale metrieken berekenen een waardering voor een welbepaalde entiteit in het netwerk. Deze waardering is afhankelijk van de entiteit die het startpunt (bron) van de berekening is. Deze metrieken zijn beter geschikt in situaties waar de mening van verschillende gebruikers over hetzelfde onderwerp kan verschillen, zoals we later bijvoorbeeld bij Golbecks toepassingen zullen bespreken. Daarin wordt gebruik bemaakt van een eenvoudige, lokale metriek [26]. Deze heeft een aantal problemen waarvan de meest belangrijke is dat er geen afname is van vertrouwen voor langere padlengten; daarom wordt in [27] een verbeterde versie voorgesteld, nl. het TidalTrust algoritme19 . De verbetering zit in het gebruik van een drempelwaarde max die voorkomt dat buren met een lage trustwaarde worden meegenomen in de berekening. Deze drempelwaarde wordt gedefineerd als de grootste vertrouwenswaarde die, als we deze gebruiken als een minimale drempelwaarde, nog steeds aanleiding geeft tot een pad van de bron naar het doel. We beschouwen dus enkel bogen met een waarde groter of gelijk aan de drempelwaarde. Globale metrieken berekenen één waarde voor elke entiteit in het netwerk. Deze metrieken zijn geschikt in situaties waar de verwachtingen van de gebruikers gelijkaardig zijn. Dit komt bijvoorbeeld voor in peer-to-peer netwerken waar de geschiktheid van een peer afhangt van technische kenmerken (zoals bijvoorbeeld de bandbreedte). EigenTrust [28] is een variatie op 19

De naam van dit algoritme is afgeleid van de beweging die de berekening maakt: eerst van de bron naar het doel toe en dan terug (getijde, Eng. tidal).


26

PageRank [24]. EigenTrust is bedoeld voor peer-to-peer networks; vertrouwen is hier eerder een maat voor prestatie. Dit is een globale metriek; in deze formulering is de betekenis van vertrouwen niet zozeer afhankelijk van de source peer. Prototypes en concrete toepassingen Aan de hand van TidalTrust creëerde Golbeck een aantal toepassingen, waaronder TrustMail en FilmTrust. Het feedbacksysteem dat door eBay gebruikt wordt, is een globale metriek. TrustMail We kunnen het vertrouwensnetwerk gebruiken om e-mails te rangschikken en zelfs om spam te bestrijden. Een prototype wordt beschreven in [26]. Golbeck maakt hiervoor gebruik van de Mozilla e-mail client met een extra uitbreiding: in de lijst van berichten wordt er een kolom toegevoegd die de vertrouwenswaarde voor de afzender weergeeft. De waarde wordt berekend aan de hand van een onderliggende (generieke) webservice die de vertrouwenswaarde tussen twee e-mailadressen weergeeft. De service gebruikt de hierboven beschreven vertrouwensontologie om een generiek vertrouwensnetwerk op te bouwen. Indien mogelijk zal bij het berekenen het vertrouwen met betrekking tot het onderwerp van de e-mail gebruikt worden. Als dit niet mogelijk is, wordt de waarde voor e-mail (op zich) of anders de algemene waarde gebruikt. In latere artikels [29, 27] beschrijft Golbeck een nieuwe implementatie in Java. Hier wordt vertrokken vanuit een eigen opgebouwd sociaal netwerk (aan de hand van de lokaal beschikbare mail) uitgebreid met een gedistribueerd, webgebaseerd vertrouwensnetwerk. Het kan dat er een te hoge (of te lage) vertrouwenswaarde die niet overeenstemt met de verwachting van de gebruiker wordt berekend. In dat geval kan men een lagere (resp. hogere), directe waarde aan het systeem toevoegen. Merk op dat dit enkel invloed heeft op vertrouwenswaarden waar men een tussenliggende actor is. Het belang van dit systeem zit in het ordenen en het identificeren van potentieel belangrijke e-mail. FilmTrust FilmTrust wordt door Golbeck beschreven in [27]. FilmTrust is een website die gebruik maakt van vertrouwenswaarden in een sociaal netwerk om voor de gebruiker gepersonaliseerde aanbevelingen van films te doen. Het systeem bestaat uit twee componenten. In de eerste component moeten gebruikers voor elke persoon die ze toevoegen als vriend een vertrouwenswaarde ingeven. Deze waarde drukt uit hoeveel ze hun vriend vertrouwen op het vlak van films en wordt gebruikt om het sociaal netwerk op te bouwen. In de tweede component kunnen gebruikers films bespreken en een waardering (van een halve tot vier sterren) uitdrukken. De twee componenten worden ge¨ıntegreerd met de “Recommended Rating” functie. Met het TidalTrust algoritme worden zeer vertrouwde gebruikers geselecteerd die een waardering voor een bepaalde film hebben ingegeven. Het eindresultaat is dan het gemiddelde van de waarderingen gewogen met de vertrouwenswaarde van de gebruikers. Het voordeel in vergelijking met een gewone rating (die eigenlijk een globaal gemiddelde is) is dat wanneer het globale gemiddelde slecht presteert, de “Recommended Rating” het veel beter doet. Dit komt bijvoorbeeld vaak voor bij controversiële films, waar veel mensen ofwel voor, ofwel tegen zijn. De waardering van de gebruiker ligt in dat geval ver van de globale (gemiddelde) waardering, maar dichter bij de waardering van mensen die men een grote trust rating gegeven heeft. Men kan verwachten dat mensen die een groot vertrouwen in elkaar hebben een gelijkaardige smaak hebben.


27

eBay Een toepassing die gebruik maakt van een globale metriek is eBay20 . Het feedbacksysteem dat door eBay gebruikt wordt, zou men kunnen zien als een vertrouwensnetwerk. Zowel koper als verkoper geven (na het voltooien van een transactie) een individuele feedback op de verkoper of koper. Het is mogelijk om deze feedback te browsen. In tegenstelling tot Golbeck doet eBay evenwel geen netwerkgebaseerde voorspelling over de betrouwbaarheid van de verkoper; het globale percentage van positieve feedback wordt enkel gegeven.

20

http://www.ebay.com/ (bezocht op 17 mei 2007)

Hoofdstuk 3

Folksonomie¨ en 3.1

Inleiding

Folksonomieën (Eng. folksonomies) vinden we terug in de context van het ordenen van informatie. Bij het ordenen van items — zij het boeken, artikels, documenten, foto’s, muziek, of andere media — wordt informatie toegevoegd die het mogelijk maakt om deze items te organiseren en toegankelijk te maken. Deze informatie noemen we meta-informatie (Eng. metadata). Het is in feite informatie over informatie(bronnen). Meta-informatie We kunnen stellen dat er drie brede categorieën meta-informatie bestaan: administratieve, structurele en beschrijvende meta-informatie [30]. In dit hoofstuk spreken we vooral over inhoudsbeschrijvende meta-informatie. Deze meta-informatie kan door verschillende soorten mensen gecreëerd worden: • Experts: stellen meta-informatie op. De meta-informatie heeft dan een hoge kwaliteit, maar is duur (zowel in tijd als in werk). Deze aanpak is weinig schaalbaar, beschouw bijvoorbeeld de informatiestroom van het World Wide Web. • Auteurs: kunnen zelf ook meta-informatie leveren. Op deze manier kunnen we schaalbaarheidsproblemen oplossen. Auteurs kunnen bijvoorbeeld zelf Dublin Core velden invullen (zie Sectie A.1). • Gebruikers: zij zijn de gebruikers van meta-informatie. De belangen van de auteurs en experten staan in feite los van de effectieve informatiegebruikers. Door de gebruikers zelf de meta-informatie te laten leveren, geven we de gebruikers de mogelijkheid om een op eigen maat gesneden systeem te ontwikkelen. Traditionele systemen gebruiken ontologieën of taxonomieën die door experts worden vastgelegd. In dit hoofdstuk wordt de metadata gecreëerd door (gemeenschappen van) gewone gebruikers. De gebruikers zullen in folksonomieën vooral de inhoud van de items beschrijven. Verder verloop van dit hoofdstuk In de eerstvolgende sectie beginnen we met een algemene beschrijving en een definitie. Om deze definitie te verduidelijken geven we in de daaropvolgende sectie een beschrijving van concrete voorbeelden. Daarna volgt een bespreking van verschillende vastgestelde eigenschappen. We beslisten deze materie een eigen hoofdstuk te geven omdat folksonomieën eerder een Web 2.0 dan een Semantisch Web applicatie zijn. Verder hebben folksonomieën sociale aspecten: gebruikers worden met elkaar gelinkt door het gebruik van dezelfde tags of items. Dit maakt

28

¨ HOOFDSTUK 3. FOLKSONOMIEEN

29

dat folksonomieën een op zich staande technologie zijn, met voldoende eigenschappen om er een hoofdstuk aan te wijden. Dit hoofstuk is belangrijk omdat we een aantal eigenschappen van folksonomieën willen gebruiken in hoofstuk 5. Daar zullen auteurs met kernwoorden getagd worden en kan er op deze manier een profiel opgesteld worden. Folksonomieën waren een inspiratiebron voor deze werkwijze. We hopen een aantal gelijkaardige eigenschappen vast te kunnen stellen. We willen tevens opmerken dat de blogwereld een grote invloed heeft op het ontstaan en de ontwikkeling van folksonomieën; dit wordt bijvoorbeeld weerspiegeld in de referenties. De academische interesse is pas nadien gegroeid wanneer bleek dat folksonomieën meer waren dan alleen een mooie Web 2.0 applicatie. De resultaten uit sectie 3.5 zijn academisch werk.

3.2

Omschrijving

De term folksonomy werd het eerst gebruikt door Thomas Vander Wal, op een informatiearchitectuur mailinglist in een discussie over het systeem dat Delicious (zie Sectie 3.3.1) en Flickr (zie Sectie 3.3.2) gebruiken. Folksonomy ontstaat door het samenbrengen van de woorden folk en taxonomy [31]. Er is discussie over de correctheid van deze naam. Merholz [32, 33] gebruikt bijvoorbeeld de term ethnoclassification. Hij argumenteert dat een taxonomie meer neigt naar hiërarchie en controle, en dat dus bij uitbreiding folksonomy een incorrecte term is. Ook zijn term zouden we als niet correct kunnen zien omdat een folksonomie eerder categoriseert i.p.v. classificeert1 . In [34] wordt de term collaborative tagging voorgesteld. Hoewel we zouden kunnen stellen dat er een zekere (brede) consensus is over wat valt onder het begrip folksonomie, is het moeilijk om een strikte of algemeen aanvaarde definitie te vinden. Google rapporteert bijvoorbeeld ongeveer 10.300.000 zoekresultaten voor “folksonomy”2 . Uiteraard geeft niet elke pagina een nieuwe definitie, maar veel auteurs geven wel een eigen interpretatie. We stellen dan ook voor om de door Vander Wal in [31] geformuleerde definitie te volgen: “Folksonomy is the result of personal free tagging of information and objects (anything with a URL) for one’s own retrieval. The tagging is done in a social environment (usually shared and open to others). Folksonomy is created from the act of tagging by the person consuming the information.” Een folksonomie is in essentie een eenvoudig multi-user systeem voor het categoriseren van willekeurige items. Alle items zijn publiek en elke gebruiker kan eigen items aan de folksonomie toevoegen. Alle gebruikers van een folksonomie werken dus samen door hun items en de corresponderende meta-informatie openbaar te maken. Elk item wordt getagd door de gebruikers. Tags zijn willekeurig gekozen woorden en liggen allemaal in dezelfde namespace. Er zijn geen expliciet gedefinieerde verbanden tussen de tags. Het groeperen van tags is echter wel mogelijk omdat de gebruikers dezelfde tags gebruiken om verschillende items te beschrijven. Typisch bestaat er bijvoorbeeld voor elke tag een pagina die alle items bevat die tenminste één keer door deze tag werden beschreven. Het is ook mogelijk om items te groeperen omdat gebruikers individueel en (tenminste in zekere mate) onafhankelijk van elkaar meta-informatie over dezelfde items genereren. Op deze manier zal men typisch ook een pagina opstellen die voor een bepaald item alle verschillende 1

Men kan algemeen stellen dat classificeren exclusiever is dan categoriseren. Een item kan tot verschillende categorieën behoren, terwijl classificatiemethodes streven naar het onderbrengen van een item in één klasse. Categorisatie is dus in zekere zin minder rigoureus en vager dan classificatie. 2 http://www.google.com/search?hl=en&q=folksonomy&btnG=Google+Search op 12 mei 2007


30

tags en het aantal keer dat deze tags door de verschillende gebruikers gebruikt worden weergeeft. Het totaal aantal tags dat gebruikers toekennen kan dan worden gezien als een maat voor de populariteit van het item. Omdat elke gebruiker vrij is om tags naar eigen goeddunken te gebruiken, verschilt deze categorisatiemanier van traditionele systemen. Het is niet nodig een consensus te bereiken over hoe het item precies moet worden gecategoriseerd (m.a.w. welke tags gebruikt dienen te worden). De tags die het meest worden gebruikt geven de mening van de meerderheid. Tags die een item goed categoriseren worden dus veel gebruikt. De bruikbaarheid van een folksonomie is dus recht evenredig met het aantal gebruikers en de geproduceerde metadata.

3.3

Concrete voorbeelden

Vooraleer we de eigenschappen van folksonomieën bespreken, stellen we eerst enkele voorbeelden voor. Deze eigenschappen (die besproken worden in Sectie 3.5) werden telkens geobserveerd in één van onderstaande voorbeelden. Deze lijst is in zekere zin arbitrair maar probeert bekende (pionier) websites met een verschillend onderwerp of doel voor te stellen.

3.3.1

Del.icio.us

Del.icio.us3 (kortweg Delicious) werd in 2003 opgericht door Joshua Schachter. In 2005 werd er een officieel bedrijf onder de naam del.icio.us, Inc. opgericht dat reeds in december van dat jaar werd overgenomen door Yahoo!4 . Schachter noemt Delicious een “social bookmarks manager”: een website ontworpen voor het bewaren en delen van bookmarks op het web (in tegenstelling tot in de browser). Schachter ziet hier drie voordelen in. Ten eerste is het mogelijk om overal toegang tot je bookmarks te verkrijgen (bijvoorbeeld thuis, op het werk, in de bibliotheek of op de computer van een vriend). Ten tweede kan je je bookmarks delen met vrienden, collega’s en andere mensen. Ten derde kan je andere personen vinden die interessante bookmarks hebben en is het mogelijk om die links aan je eigen collectie toe te voegen. Met een speciale bookmark (“bookmarklet”) of extra browser buttons (als browser extension of plug-in ge¨ınstalleerd) kunnen gebruikers links toevoegen. Na het klikken komt de gebruiker terecht op een pagina waar hij extra informatie zoals een beschrijving, extra nota’s en tags kan invullen. Aangeraden tags worden op deze pagina getoond. Door het klikken van de saveknop wordt de bookmark aan het systeem toegevoegd. De bookmark is standaard publiek zichtbaar. Delicious is volgens [30] echter niet nieuw of uniek in zijn rol als “bookmarks manager”. Het vernieuwende aan Delicious is de nadruk op door de gebruiker toegevoegde tags. Gebruikers kunnen op deze manier informatie ordenen en beschrijven met een vocabularium dat ze zelf kiezen. In Figuur 3.3.1 is de frontpagina van http://del.icio.us5 te zien.

3.3.2

Flickr

Flickr6 is een dienst om foto’s op te slaan en uit te wisselen en is eigendom van Yahoo!. De frontpagina is te zien op Figuur 3.3.2. Foto’s worden ingedeeld in verzamelingen (Eng. sets). 3

http://del.icio.us (bezocht op 12 mei 2007) http://info.yahoo.com/ (bezocht op 12 mei 2007) 5 De speciale vorm van de URL wordt een domain hack genoemd. Een domain hack onstaat door het op een onconventionele manier gebruikken van domeinnamen. Delicious is wellicht het meest bekende voorbeeld dat dit doet. Andere voorbeelden zijn http://blo.gs en http://cr.yp.to. Een informele introductie tot dit fenomeen is te vinden op http://en.wikipedia.org/wiki/Domain_hack 6 http://www.flickr.com/ (bezocht op 12 mei 2007) 4


31

Figuur 3.1: Frontpagina Del.icio.us. Merk de verschillende soorten tags op; rechts zien we bv. de tag toread (dit is een tag die alleen betekenis heeft voor de individuele gebruiker), music en photos (die het soort medium aanduiden). Veel gebookmarkte websites zijn technologiegerelateerd.


32

Figuur 3.2: Frontpagina Flickr. De foto op de frontpagina is een geselecteerde foto van een echte gebruiker. De gekleurde woorden in het citaat zijn tags waarop kan worden gezocht. Flickr wordt veel gebruikt in combinatie met blogs. Hoewel het mogelijk is om foto’s van andere gebruikers te taggen, taggen gebruikers vooral hun eigen foto’s. Meestal zijn de tags dus enkel afkomstig van de fotograaf, in tegenstelling tot bijvoorbeeld Delicious waar gebruikers veel dezelfde bookmarks aan het systeem toevoegen. Omdat elke foto uniek is (en dus in de praktijk maar één keer aan het systeem toegevoegd wordt), heeft het in deze folksomomie geen zin om te groeperen op items. Andere gebruikers kunnen commentaar geven op de foto’s. Het is zelfs mogelijk om zones op de foto’s te selecteren en enkel deze zone te annoteren. De annotaties worden weergegeven wanneer er over de foto wordt bewogen met het muispijltje. Toegangsrechten worden geregeld aan de hand van (zowel publieke als private) groepen, familie en vrienden. Foto’s kunnen dan publiek of enkel als lid van een bepaalde groep zichtbaar zijn. Het becommentariëren van foto’s kan op deze manier ook beperkt worden.

3.3.3

Andere voorbeelden

Connotea, CiteULike (http://www.connotea.org/, http://www.citeulike.org/) Vergelijkbaar met Delicious, maar hier worden referenties gecategoriseerd. Technorati (http://technorati.com/) Technorati bestaat uit twee componenten, nl. het zoeken en organiseren van blogs. Er kan worden gezocht in de blogposts. Tijdens het opbouwen van de zoekindex worden links tussen blogs in kaart gebracht (bloggers hebben de neiging om naar elkaar te linken) en op deze manier kunnen belangrijke blogs ge¨ıdentificeerd worden. Het organiseren of categoriseren van blogs wordt uitgevoerd met behulp van tags. Op deze manier kan Technorati bijvoorbeeld gebruikt worden om blogs met een bepaalde tag extra in het oog te houden. Last.fm (http://www.last.fm) Last.fm gebruikt tags om gelijkaardige artisten terug te vinden. Elke track die een gebruiker afspeelt wordt “gescrobbled”, d.i. door een client toegevoegd aan de website. Deze client is stand-alone of als plugin voor bekende media-applicaties beschikbaar. Met deze informatie wordt dan een individueel gebruikersprofiel opgesteld. Doordat gebruikers songs


33

en artiesten kunnen taggen, wordt het mogelijk om op deze manier “buren” (gelijkaardige artiesten of andere gebruikers met gelijkaardige smaak) terug te vinden.

3.4

Sterktes en zwaktes t.o.v. traditionele classificatiesystemen

We bespreken de voor- en nadelen ten opzichte van traditionele classificatiesystemen.

3.4.1

Sterktes/voordelen

De eerste sterkte is “serendipity”, of in het Nederlands de “gave om toevallig waardevolle dingen te ontdekken”7 . Het browsen van het systeem en zijn gelinkte, verwante tags is verrassend om onverwachte items te vinden binnen een algemeen onderwerp. In het vinden van interessante inhoud verschilt browsen fundamenteel van direct zoeken. Zoeken zouden we bijvoorbeeld kunnen vergelijken met het kopen van een bepaald object in een specieke winkel, en verkennen met window shopping. Folksonomieën zijn beter geschikt voor verkennende taken. We kunnen dus moeilijk de performantie van folksonomieën vergelijken met gewone zoeksystemen omdat dan de verkennende kracht van een folksonomie wordt genegeerd. Wellicht is de belangrijkste kracht van folksonomieën dat ze onmiddellijk het vocabularium van de gebruikers uitdrukken. In dat opzicht kunnen volgens Peter Merholz folksonomieën nuttig zijn omdat ze het digitaal equivalent zijn van “desire lines” [33]. Desire lines zijn de paden die door voetstappen in het landschap ontstaan. In een folksonomie ontstaat er in feite op dezelfde manier een categorisatiesysteem dat de taal van de gebruikers spreekt. We kunnen deze eigenschap gebruiken om een “gecontroleerd vocabularium” op maat van de gebruikers te ontwikkelen: wanneer je een een folksonomie (als een voorbereidend systeem) in evenwicht hebt, kan je de meest gebruikte tags gebruiken om dit vocabularium op te stellen.

3.4.2

Beperkingen/nadelen

De beperkingen (t.o.v. traditionele classificatiesystemen) van folksonomieën zijn inherent aan het ongecontroleerde vocabularium dat gebruikt wordt. Omdat verschillende gebruikers verschillende termen op verschillende manieren gebruiken, onstaat er een dubbelzinnigheid in het gebruik van de tags. Veel woorden hebben verwante maar subtiel verschillende betekenissen. Zo kan het woord e-mailfilter gebruikt worden in verschillende betekenissen, bijvoorbeeld als een spamfilter of als zoekregel die je in sommige mail-clients ziet. Een verwant probleem is dat van homoniemen, maar dit probleem heeft een veel beperktere impact omdat door het toevoegen van extra tags de juiste betekenis van het woord duidelijk kan gemaakt worden. Ook is er geen synoniembeheer in het systeem. Verschillende woordvormen, bv. enkelvoud en meervoud, zijn vaak beide aanwezig. Soms willen gebruikers tags die bestaan uit verschillende woorden gebruiken. Sommige folksonomieën laten spaties toe, andere niet. Gebruikers gaan hier op een verschillende manier mee om: men kan de spaties vervangen door een teken (bv. samengevoegde_tag), men kan de woorden samenvoegen (bv. SamengevoegdeTag) of men kan alle woorden als aparte tags toevoegen. Opmerkelijk is dat gebruikers soms een hiërarchie in de tags proberen te creëren (bv. kleur/rood) Folkosonomieën zijn niet erg geschikt voor zoeken want de tags geven de inhoud van een item te beperkt weer. Zoeken in de inhoud van de items zelf kan, maar hangt af van het soort items 7

volgens het Van Dale groot woordenboek Engels-Nederlands


34

die worden gecategoriseerd. In heterogene folksonomieën (die algemene items, zonder restrictie op het type of formaat, categoriseren) heeft dit nog een grotere impact. Door hun publieke natuur kunnen folksonomieën gemakkelijk gespamd worden door bedrijven die hun items zo veel mogelijk verschillende tags kunnen geven. Op deze manier kunnen ze hun items linken aan zo veel mogelijk andere items.

3.5

Eigenschappen

In deze sectie geven we een overzicht van eigenschappen voor folksonomieën. De meeste eigenschappen werden door [34] voor Delicious geobserveerd, maar men kan verwachten dat deze ook algemeen een draagvlak hebbben.

3.5.1

Soorten tags

We kunnen de volgende soorten tags indentificeren: • Vastleggen over wat/wie het gaat. Bijvoorbeeld flower, car,... • Vastleggen wat soort item het is. Bijvoorbeeld een blog, article, photo. • Vastleggen wie de eigenaar is. Komt vooral voor in de blog-community waar de auteur van de inhoud belangrijk kan zijn. • Categorieën verfijnen. Sommige tags lijken niet alleen betekenis te hebben, maar ook een verfijning van andere tags te zijn. Een voorbeeld hiervan zijn jaartallen. • Vastleggen van kwaliteiten of karakteristieken. Adjectieven die de mening van de tagger over het item vastleggen. Bijvoorbeeld funny, scary,... • Zelfreferentie. Tags die my bevatten, identificeren inhoud die een relatie heeft met de tagger. • Organisatie van taken. Bijvoorbeeld toread of jobsearch.

3.5.2

Voorkomen van tags

Sommige tags worden gebruikt door een een grote groep van gebruikers, terwijl andere tags door een beperkter aantal gebruikers gebruikt worden. Gebruikers hebben een sterke neiging om algemene tags eerst te gebruiken. Dit wordt zeer mooi gedemonstreerd in [34] waar de (globale) rangorde berekend werd voor elke tag in Delicious. De rangorde van een tag is de positie van die tag in de volgorde van het ingeven van de tags. De globale rangorde wordt bepaald door de mediaan van alle rangordes te nemen. Bij het toevoegen van een nieuwe bookmark heeft de eerste tag de kleinste rangorde. Bij het toevoegen van extra tags zal de globale rangorde van de extra tags toenemen. Dit wordt ge¨ıllustreerd in Figuur 3.3. We kunnen op deze manier argumenteren dat de eerste tags de “basic levels” van de gecategoriseerde objecten uitdrukken. De basic level van een object kunnen we omschrijven als het standaardniveau van specificiteit dat mensen gebruiken bij het categoriseren. Veel mensen zullen bijvoorbeeld een labrador categoriseren als een hond, terwijl kenners onmiddelijk zullen verwijzen naar het ras. We zouden de labrador ook kunnen categoriseren als een dier, maar dit is te algemeen omdat we het onderscheid met andere diersoorten willen (kunnen) maken.


35

Figuur 3.3: Bij het toenemen van de positie (volgorde volgens het ingeven) van de tag zal de globale rangorde ook toenemen. Dit wordt hier getoond voor twee bookmarks. Figuur overgenomen uit [34].

3.5.3

Gebruikersactiviteit en aantal tags

Er blijkt geen uitgesproken verband te bestaan tussen het aantal Delicious-bookmarks dat de gebruiker heeft gecreëerd en het aantal tags dat hij gebruikt om deze bookmarks te categoriseren. Sommige gebruikers hebben dus een relatief grote verzameling tags, terwijl andere een relatief kleine verzameling gebruiken. De verzameling tags van een gebruiker neemt toe in tijd wanneer bij het ontdekken van nieuwe interesses nieuwe tags worden ge¨ıntroduceerd om deze te beschrijven en te categoriseren. Het kan ook een tijd duren vooraleer een bepaald onderscheid wordt opgemerkt. Pas vanaf dan kan dat onderscheid worden gebruikt om items verder te categoriseren en te beschrijven. Dit stelt wel problemen voor reeds gecategoriseerde informatie, de gebruiker moet nl. alle vorige items opnieuw bekijken om het onderscheid te maken. In Hoofdstuk 5 zal worden besproken dat sommige auteurs een grotere tagverzameling hebben, en andere een kleinere: beginnende onderzoekers zullen immers minder publicaties (en een beperkter onderzoeksdomein) hebben dan ervaren onderzoekers.

3.5.4

Stabiele tagverdelingen

De verzameling tags en hun corresponderende frequenties per item kunnen we zien als een voorstelling van de gecombineerde omschrijving van dat item door de gebruikers. Voor Delicious wordt geobserveerd dat de relatieve frequentie van de tags wanneer we alle tags van een item groeperen aanleiding geeft tot een stabiel patroon waarbij de verschillende fracties van voorkomen ongeveer vast zijn. Empirisch wordt vastgesteld dat dit reeds voorkomt vanaf ongeveer de eerste 100 bookmarks. Dit wordt ge¨ıllustreerd in Figuur 3.4. Er zijn twee redenen waarom deze stabilisatie kan voorkomen, nl. imitatie en gedeelde kennis. Bij imitatie nemen gebruikers het gedrag van andere gebruikers over. In Delicious gebeurt dit bijvoorbeeld doordat gebruikers bij het toevoegen van een bookmark de reeds door andere gebruikers gebruikte tags getoond worden. Gebruikers kunnen makkelijk deze tags selecteren


36

Figuur 3.4: De stabilisatie van de tagverdelingen wordt aangetoond voor twee populaire URL’s. De verticale as toont de relatieve frequentie en de horizontale geeft de tijd weer (in toevoegingen van de bookmark). Elke curve stelt een tag voor. Figuur overgenomen uit [34]. en dus de keuzes van vorige gebruikers imiteren. Omdat het stabiel patroon ook voorkomt voor weinig gebruikte tags is enkel imitatie niet voldoende om dit patroon te verklaren. Het is te verwachten dat Delicious-gebruikers een zekere achtergrond (zij het lingu¨ıstisch, cultureel, educatief,...) delen. In het geval van Delicious blijken de gebruikers een sterk technische achtergrond te bezitten; veel van de gebookmarkte URLs zijn technologiegerelateerd. (Zie bijvoorbeeld Figuur 3.3.1)

3.5.5

Verwante tags

Het is mogelijk om verwante tags te bepalen: als twee tags voor hetzelfde item gebruikt worden, drukt dit een zeker verband uit tussen die twee tags. Dit verband wordt sterker naarmate de twee tags meer samen voorkomen bij andere items. Er worden in de literatuur verschillende, analoge, technieken voorgesteld om verwante tags te berekenen. In [35] wordt “tagoverlapping” gedefinieerd als de verhouding van het aantal items waarvoor beide tags samen optreken over het aantal items waarvoor minstens één van de twee tags optreedt. Deze tagoverlapping wordt dan verder gebruikt om de tags in traditionele tagclouds8 te groeperen. In [36] wordt een algoritme voor het bepalen van verwante tags voorgesteld. Dit zou men kunnen zien als een uitbreide variant op tagoverlapping. Eerst wordt voor een bepaald item het aantal keer dat twee tags samen voorkomen geteld. Met behulp van een drempelwaarde wordt bepaald of dit samen voorkomen significant genoeg is om verder gebruikt te worden. De resultaten dan worden bewaard in een ijle vierkante matrix. Na het verwerken van de volledige tagverzameling, worden de absolute frequenties van de tagparen gebruikt om te bepalen welke paren een beduidend hogere frequentie hebben. Hiervoor wordt er gezocht naar een drempelwaarde waarboven de co-tags als sterk verwant beschouwd worden. In Figuur 3.5 wordt de typische verdeling van dergelijke frequenties weergegeven. We hebben enkele sterk verwante tags, waarna het verwantschap afneemt en we in een gebied van minder uitgesproken verwante tags komen. De drempelwaarde wordt gelegd op het knikpunt van de grafiek. In dit artikel wordt er ook nog een techniek voor het clusteren van tags aan de hand van dit algoritme gegeven. In [37] toont Mika dat er ook een verband is als we de gebruikers als een entiteit aanzien; hij beschouwt de hypergraaf van items-tags-gebruikers. Door het “samenvouwen” van deze graaf is het mogelijk om drie bipartite grafen (items-tags, items-gebruikers en tags-gebruikers) af te leiden. Aan de hand van de derde (“weggevouwde”) component wordt dan het gewicht op de 8

Een tagcloud is een lijst van tags (doorgaans alfabetisch gerangschikt) waarbij tags met een grotere frequentie een groter lettertype krijgen. Tagclouds worden vaak gebruikt om de verschillende tags voor een item of zelfs voor een volledige folksonomie te visualiseren.


37

Figuur 3.5: Typisch verloop van de frequenties voor gevonden verwante tags. De vertikale as geeft de absolute frequentie weer. De verwante tags worden volgens aflopende frequentie geordend. Figuur overgenomen uit [36]. bogen bepaald. Deze grafen kunnen we op hun beurt nog eens opnieuw combineren, zodat we verwante tags kunnen berekenen. Op deze manier wordt het ook mogelijk om verwante items en verwante gebruikers te berekenen.

Deel II

Analyse van de Fuzzy Sets and Systems netwerken

38

Hoofdstuk 4

Co-auteursnetwerken Als twee auteurs aan een publicatie samenwerken kunnen we stellen dat er er een sociale relatie tussen die twee auteurs bestaat. In tegenstelling tot informele contacten, kunnen we deze relatie wel objectief vaststellen. Beide namen worden namelijk vermeld op de publicatie die bovendien publiek toegankelijk is. We kunnen dus een sociaal netwerk opstellen waarbij bogen co-auteurschap voorstellen. Dit is precies wat we in dit hoofstuk doen: we verzamelen een groot aantal publicaties en leiden hieruit een sociaal netwerk af. Verloop van dit hoofstuk Eerst bekijken we hoe we informatie kunnen extraheren en omzetten naar een eenvoudig netwerk, waarna we het bekomen netwerk analyseren. Verder breiden we dit netwerk uit met gerichte bogen en specifiekere gewichten, maken we opnieuw een analyse, en vergelijken we dit nieuwe netwerk met het oorspronkelijke netwerk.

4.1

Extractie

Het spreekt voor zich dat het co-auteursnetwerk in zekere zin al vastligt: het is te vinden door aggregatie van de informatie van alle publicaties. Er is echter nog een hoop werk om tot een handelbare versie te komen: de publicaties moeten worden teruggevonden en de informatie moet er worden uitgehaald. Om deze taken gemakkelijk en herhaalbaar uit te kunnen voeren, ontwikkelden we CookieMonster. Dit is een applicatie die taken in een lijst kan ordenen en die deze takenlijsten op een sequentiële manier kan uitvoeren. De taken dienen door de gebruiker ge¨ımplementeerd te worden en kunnen met behulp van de GUI aan de lijst toegevoegd worden. Omdat taken configureerbaar zijn, kunnen deze gemakkelijk in andere situaties hergebruikt worden. Het voordeel van zo’n applicatie is dat het gemakkelijk is om de resultaten te produceren en te herhalen. Verder kan, met een minimum aan interactie met de onderzoeker, een ander onderzoeksdomein geanalyseerd worden. CookieMonster wordt verder uitvoerig besproken in de appendices: appendix B is een handleiding voor de eindgebruiker, appendix C bespreekt de implementatie en appendix D handelt over de ontwikkelde taken. Aangezien de functionaliteit van de taken meestal uit de context van de tekst duidelijk wordt, verwijzen we de lezer naar appendix D voor uitgebreide informatie. Startpunt We definiëren de “Fuzzy Sets and Systems”-gemeenschap als alle auteurs die meegewerkt hebben aan minstens één publicatie uit een van de tijdschriften of conferenties uit onderstaande lijst. Als informatiebron voor ons co-auteursnetwerk gebruikten we DBLP [38]. Deze bibliografiedatabank

39

HOOFDSTUK 4. CO-AUTEURSNETWERKEN

40

was eerst gefocust op databanksystemen en logisch programmeren (de naam DBLP komt van “DataBase Systems and Logic Programming”) maar werd uitgebreid tot het volledig domein van computerwetenschappen. Op het moment van dit schrijven1 bevat de databank meer dan 870000 records. DBLP heeft het voordeel dat het volledig publiek toegankelijk is en de belangrijke tijdschriften en conferenties in de computerwetenschappen indexeert. We startten het opbouwen van het netwerk door het definiëren van onze doelgemeenschap als iedereen die tenminste één keer in onderstaande tijdschrijften en conferenties heeft gepubliceerd. Onze basisinformatie werd dan bekomen door het downloaden van alle relevante informatie beschikbaar op DBLP. • Fuzzy Sets and Systems 2 . Merk op dat dit tijdschrift nog maar sinds volume 117 (2001) ge¨ındexeerd wordt. We gebruiken de zoekterm fuzzy sets and systems. • International Journal of Approximate Reasoning 3 . Dit tijdschrift is op DBLP te vinden als Int. J. Approx. Reasoning. • International Fuzzy Systems Association 4 , kortweg IFSA. We vinden deze conferentie met de zoekterm ifsa. • IEEE International Conference on Fuzzy Systems 5 . De gebruikte zoekterm is hier FUZZ-IEEE. Wanneer men een query naar een conferentie of tijdschrift op DBLP plaatst, krijgt men alle artikels in die conferentie of tijdschrift terug. DBLP geeft de volledige bibliografische data en een link naar een elektronische editie. Door deze link te volgen is het mogelijk om extra informatie of zelfs de volledige tekst van het artikel te verkrijgen. Dit zijn telkens pagina’s van uitgevers: de toegankelijke informatie hangt af van abonnementen en toegangsrechten op de gegeven websites. De elektronische editie zal later gebruikt worden om extra informatie omtrend de inhoud te verkrijgen. De taak die hiervoor ontwikkeld werd, is QueryDBLP. Deze downloadt en bewaart alle resultaten als BibTeX-records. We gebruikten de takenlijst crawl1_download.cm (zie Sectie E.1.1). Om deze data handig te kunnen gebruiken, importeren we ze in een Sesame repository. Hiervoor moeten we de BibTeX-records eerst converteren in RDF+XML formaat. Dit gebeurt met een aangepaste versie van het bib2rdf script van Michel Klein [39]. Het script zal ervoor zorgen dat voor elke auteur precies één instantie wordt gecreëerd. Op deze manier vermijden we de noodzaak aan een extra FOAF smushing stap. De uitvoer van dit script kan rechtstreeks in de repository ge¨ımporteerd worden. Dit gebeurt in de takenlijst crawl1_import.cm (zie E.1.2). Na het voltooien van deze eerste crawl beschikken we over 2859 publicaties van 3608 verschillende auteurs. Deze auteurs zijn het “kernnetwerk” dat we verder zullen bestuderen en worden daarom gemarkeerd (met behulp van de takenlijst crawl1_mark.cm, zie Sectie E.1.3). We zullen in wat volgt aan deze dataset refereren als crawl1 en aan de auteurs als de gemarkeerde auteurs. Aangezien de informatie over de auteurs in dit kernnetwerk zeer ijl is (veel auteurs zijn op basis van slechts één publicatie lid van het kernnetwerk) moeten we extra informatie over elke auteur downloaden. 1

eind maart 2007 http://www.elsevier.com/locate/fss (bezocht op 29 maart 2007) 3 http://www.elsevier.com/locate/ijar (bezocht op 29 maart 2007) 4 http://www.cmplx.cse.nagoya-u.ac.jp/~ifsa/ (bezocht op 29 maart 2007) 5 http://www.fuzzieee2007.org/ (bezocht op 29 maart 2007)

2


Publicaties Unieke auteurs Gemarkeerde auteurs Verschillende co-auteursrelaties Totaal aantal co-auteursrelaties

41

crawl1 2859 3608 3608 4088 5228

crawl2 35006 29475 3598 5414 15084

Tabel 4.1: Overzicht van de datasets. Merk op dat alleen co-auteursrelaties tussen gemarkeerde auteurs beschouwd worden; andere auteurs werden genegeerd. Verbreden Voor elke gemarkeerde auteur downloaden we nu alle publicaties die te vinden zijn op DBLP. Dit geeft een totaal van 35006 publicaties6 en 29475 unieke auteurs. Merk op dat voor elke publicatie die we downloaden er tenminste één gemarkeerde auteur is omdat we deze publicatie vonden bij een query op een gemarkeerde auteur. We zullen aan deze dataset refereren als crawl2. We maken gebruik van de QueryMarkedAuthorsOnDBLP-taak (zie Sectie D.2.5 die voor alle gemarkeerde auteurs een query op DBLP doet en alle BibTeX-records bewaart in een nieuw bestand. Dit proces is ingewikkelder dan het lijkt: DBLP zal een naamdisambiguatiepagina geven wanneer de gezochte naam niet exact teruggevonden werd of er gelijkaardige namen bestaan. Het bepalen van de correcte naam wordt gedaan door eerst de accenten en andere lettertekens van de zoekterm en de voorstelde namen te verwijderen en dan de link te volgen indien een exacte match gevonden wordt7 . Deze taak zorgt ook voor het verwijderen van dubbele records. Deze stap kreeg zijn eigen takenlijst (crawl2_download.cm, zie Sectie E.1.4) door zijn lange uitvoertijd (5u40). Terug moeten we het bestand met de BibTeX-records omzetten in het RDF+XML formaat voor we het kunnen importeren in Sesame. De uitvoer van het script blijkt enkele (syntactische) problemen te bevatten die met de hand werden weggewerkt. Door de omvang van de informatie dienen we ook over te schakelen op een ander soort repository (NativeStoreRepository). Deze repository bewaart de RDF-triples in een B+boom op de schijf. Door de verschillende indices en caching door het besturingssysteem geeft deze implementatie in vergelijking met de MemoryStoreRepository ook een goede performantie. Omdat het niet mogelijk is om informatie die al (partieel) in de repository zit, opnieuw te importeren, moeten we de markeringen kopiëren tussen de twee repositories. Dit gebeurt in de takenlijst crawl2_copymarks.cm+ (zie Sectie E.1.5). Bij dit proces verliezen we 10 auteurs uit het kernnetwerk doordat we (door bijvoorbeeld de doorverwijzingspagina’s) geen records vonden en we niet de origele informatie uit de crawl1 kopiëren. We bestuderen nu in totaal 3598 actoren. In Tabel 4.1 wordt een overzicht van beide datasets gegeven.

4.2

Analyse van het basisnetwerk

We kunnen de informatie in crawl2 nu gebruiken om een sociaal netwerk op te stellen. Een eerste voorstel is om het sociaal netwerk op te stellen door tussen twee auteurs een boog te plaatsen indien ze samen auteur zijn van minstens één publicatie. Een typevoorbeeld van zo’n graaf wordt gegeven in Figuur 4.1. Dit kan men uitvoeren met behulp van BuildSimpleCoauthorGraph (zie 6

Dit aantal is na het verwijderen van dubbels. In werkelijkheid werden 60880 publicaties gedownload. We krijgen 48 keer de melding dat DBLP de auteur niet teruggevonden heeft en we komen 490 keer op een naamdisambiguatiepagina. Na het selecteren van de correcte auteur en het volgen van de link stranden we 20 keer op een doorverwijzingspagina. We vinden dus voor 68 auteurs geen records. Voor belangrijke auteurs is dit geen probleem omdat we die publicaties ook nog via andere auteurs kunnen terugvinden. 7


42

D.3.1) die een ongerichte, ongewogen graaf oplevert met 3598 toppen en 5414 bogen. We starten de analyse van de structuur van het netwerk met het bepalen van de componenten. Merk op dat onderstaande analyse enkel het sociaal netwerk in beschouwing neemt, maar het belang van een onderzoeker is meer dan alleen zijn plaats in het sociaal netwerk: zowel de kwaliteit als de kwantiteit van de publicaties kunnen ook in beschouwing genomen worden. Hoewel dit in wezen een subjectieve maat is, kan de kwaliteit van een publicatie ook gemeten worden door bijvoorbeeld het aantal citaties te tellen of de kwaliteit van tijdschrift in rekening te brengen. We kunnen deze analyse zelfs aan de hand van “citatienetwerken” maken. In wat volgt kijken we enkel naar het belang van de auteur voor de structuur van het co-auteursnetwerk. Belangrijke auteurs zullen als een “bruggenbouwer” tussen verschillende deelgroepen optreden. In Tabel 4.2 wordt een overzicht gegeven van de meest “productieve” onderzoekers. Productiviteit wordt beloond in die zin dat dit de onderzoeker meer de kans geeft om met andere onderzoekers in contact te komen. Onderzoekers die minder deel uit maken van de “Fuzzy Sets and Systems”wereld zullen minder gemarkeerde co-auteurs hebben, en zullen minder “invloed” hebben op de structuur van het netwerk.

4.2.1

Componenten

Met behulp van de taak FindComponentClusters kunnen we de componenten bepalen. De resultaten worden samengevat in Figuur 4.2. We merken meteen op dat er één grote component bestaat die iets meer dan de helft van alle actoren verbindt. In wat volgt zullen we aan deze component refereren met de naam crawl2_trunk. Verder komen vooral zeer kleine componenten voor. Het groot aantal kleine componenten is te verklaren doordat veel publicaties door enkele onderzoekers samen wordt geschreven (typisch met twee, drie of vier). Als er dan (nog) geen contact is met andere onderzoekers, dan blijven deze onderzoekers afgescheiden van de rest van het netwerk. Merk op dat het aantal actoren in componenten met een grootte tussen 5 en 17 zeer klein is. Dit zal eerder te maken hebben met de onvolledigheid van onze gekozen informatiebron. Moesten we over meer informatiebronnen beschikken, dan zouden deze componenten wellicht verbonden kunnen worden met andere of zelfs de grootste component. Dit is echter moeilijk aan te tonen want men moet hiervoor extra informatiebronnen toevoegen en de evolutie van de clusters beschouwen. Door het ontbreken van samenhangendheid zouden we kunnen we stellen dat het “small world phenomenon” (zie Sectie 2.2.1) bij definitie niet geldt voor de “Fuzzy Sets and Systems” gemeenschap. Later zullen we onderzoeken of het geldt in crawl2_trunk.

4.2.2

Graad

De graad van een actor bepaalt het aantal verschillende andere actoren waarmee de actor samengewerkt heeft. Een overzicht van de verdeling in de crawl2 dataset wordt gegeven in Figuur 4.3. Terug valt op dat veel onderzoekers reeds met één, twee of drie andere onderzoekers hebben samengewerkt. Merk op dat de actoren met graad 0 dezelfde zijn als de ge¨ısoleerde actoren (de componenten met grootte 1). Ten tweede wordt meer dan de helft van de fractie actoren met graad 1 (886) bepaald door de actoren in componenten van grootte 2 (490).

4.2.3

Clusteringco¨ effici¨ ent

De formule voor de lokale clusteringcoëfficiënt wordt gegeven in Definitie 12 (zie Sectie 2.5.1). Deze betrekking is onbepaald voor actoren met één of geen buur. De implementatie in JUNG de-


43

finieert de clusteringcoëfficiënt als nul voor actoren met graad nul en één voor actoren met graad één. Voor alle andere actoren (met graad strikt groter dan één) wordt de clusteringcoëfficiënt gegeven door de betrekking (2.5). In Figuur 4.4 wordt een histogram van de verdeling van de clusteringcoëfficiënt gegeven. Het valt direct op dat de clusteringcoëffiënt zeer veel één is (bij 2240 actoren of 62,26% van het kernnetwerk). We moeten dit resultaat echter relativeren omdat voor de 886 (24,62%) actoren met graad één de clusterincoëfficiënt ook één is. We kunnen dus besluiten dat bij ongeveer 38% van de actoren de coëfficiënt één is waarbij de actor met een grotere component verbonden is. Dit betekent dat de buren van de actoren in veel gevallen dus ook buren zijn van elkaar. Dit fenomeen is zeer eenvoudig te verklaren: wanneer we één publicatie met drie auteurs beschouwen en we het sociaal netwerk opstellen krijgen we de complete graaf van orde drie. Bij definitie is de clusteringcoëfficiënt dan voor elke actor één. Een lagere coëfficiënt krijgen we pas wanneer een auteur een publicatie maakt met andere auteurs die niet samenwerkten met zijn eerste buren. Noemenswaardig is ook het aantal keer dat er een zeer lage clusteringcoëfficiënt gekregen wordt. Terug moeten we deze waarde relativeren aangezien het aantal ge¨ısoleerde actoren (actoren met graad nul) meer dan de helft van het aantal actoren met clusteringcoëfficiënt nul uitmaakt8 . De globale clusteringcoëfficiënt wordt gegeven door het gemiddelde van alle lokale waarden. We bekomen 0,734393832.

4.2.4

Resultaten voor de grootste deelcomponent

Omdat de diameter en de gemiddelde padlengte (zie Definitie 15 en 14) niet zinvol zijn in een niet-samenhangende graaf, berekenen we deze voor crawl2_trunk. De diameter is 17 (met vijf actoren waarvoor zo’n paden kunnen gevonden worden) en de gemiddelde padlengte wordt gegeven door 6,751343508. We zouden dus kunnen stellen dat het small world phenomenon voor deze component dus in zekere zin wel geldt. De globale clusteringcoëfficiënt is 0,676384951, wat iets lager ligt dan de coëfficiënt voor het volledige netwerk (crawl2). Dit betekent dat het volledig netwerk en de grootste component een vergelijkbare clustering hebben. Bestuderen we nu het verband tussen de clusteringcoëfficiënt en de graad. Wanneer we de waarden van de clusteringcoëfficiënt bij de verschillende graden vergelijken, wordt duidelijk dat de coëfficiënt daalt wanneer de graad groter wordt. Dit is te zien in Figuur 4.5. Aan de linkerkant (voor een graad tussen nul en vijf) zien we terug de verdeling van de clusteringcoëfficiënt zoals in Figuur 4.4 tevoorschijn komen. (We hebben dus een grote frequentie in de buurt van “gemakkelijke” breuken zoals 1/3, 2/3 en 1/2 bij lage graden). Wanneer de graad stijgt, komen er minder punten voor: dit zijn gevestigde onderzoekers met een uitgebreide ervaring en deze komen niet zo veel voor. Het dalen van de clusteringcoëfficiënt wordt wellicht veroorzaakt doordat de gevestigde onderzoekers hun expertise toepassen in verschillende onderzoeksdomeinen. Verder komen deze onderzoeksdomeinen niet of nauwelijks met elkaar in contact. We kunnen dit bijvoorbeeld waarnemen in de figuur van Sectie 4.2.6.

4.2.5

Rangschikking met behulp van centraliteiten

De nabijheid kan niet zinvol berekend worden in crawl2 omdat het netwerk niet samenhangend is (men zou kunnen stellen dat de nabijheid altijd oneindig is). Verder zal in de (kleine) componenten de graad- en spilcentraliteit van de actoren lager liggen omdat het aantal mogelijke buren 8 We hebben 228 ge¨ısoleerde actoren (6,34% van het kernnetwerk) en 415 actoren (11,53%) met clusteringcoëfficiënt nul


44

of paden kleiner is. Daarom berekenen we een rangschikking voor crawl2_trunk; de resultaten zijn te zien in Tabel 4.3. Voor elke centraliteit wordt een rangschikking opgesteld: de beste actoren hebben een grote graad- en spilcentraliteit en een kleine nabijheid. In plaats van voor elke centraliteit een eigen rangschikking te tonen, berekenen we om het geheel gemakkelijker voor te stellen de gemiddelde positie in deze drie ranschikkingen. Het is deze waarde die gebruikt werd bij het rangschikken van de auteurs. De subrangschikkingen vertonen een sterke correlatie, dat schijnbaar sterker wordt bij hoger gerangschikte onderzoekers (een flagrant voorbeeld is Witold Pedrycz).

4.2.6

Visualizatie van het netwerk

Omdat het netwerk veel te groot is om volledig te visualiseren, dienen we een kleinere deelgraaf te beschouwen. Dit doen we door te vertrekken van een door de gebruiker gekozen actor en enkel zijn co-auteurs te beschouwen (merk op dat ook de verbindingen tussen die auteurs worden getoond). We kunnen ook een niveau dieper gaan en alle auteurs met op afstand kleiner of gelijk aan twee beschouwen. Voor de visualisatie maken we gebruik van het ViewGraph applet. Dit applet is startbaar vanuit CookieMonster met behulp van het menu of automatisch via de ViewGraph taak. Uit een lijst kan de actor waaruit vertrokken wordt gekozen worden en de diepte kan worden ingesteld. Een voorbeeld wordt gegeven op Figuur 4.6.

4.3 4.3.1

Analyse van het gerichte, gewogen netwerk Uitbreiding van het netwerk

In de vorige sectie hebben we een zeer eenvoudige graaf uit onze informatie afgeleid. We kunnen meer informatie in ons sociaal netwerk brengen door de bogen in het netwerk te labellen met het aantal publicaties waar de twee auteurs samen aan werkten en de toppen te labellen met het aantal publicaties waar de auteur aan meewerkte. Op deze manier kunnen we belangrijke bogen en toppen onderscheiden van minder belangrijke. Er onstaat nu evenwel een onevenwicht tusen onderzoekers die reeds veel publicaties gemaakt hebben, en onderzoekers die nog maar enkele publicaties hebben. We lossen dit probleem op door de booggewichten te normaliseren op het totaal aantal publicaties van de onderzoekers. We ontbinden daarvoor elke boog in twee (tegengesteld) gerichte bogen met hetzelfde gewicht. Hierna normalizeren we de uitgaande bogen van een top met het aantal publicaties waaraan de auteur meewerkte. We bekomen dus een gerichte, gewogen graaf zoals bijvoorbeeld in Figuur 4.7. Dit proces wordt uitgevoerd door BuildDirectedWeightedGraph.

4.3.2

Analyse met behulp van klassieke maten

Hoewel we extra informatie aan het netwerk toevoegen, blijft de structuur van het netwerk hetzelfde. De componenten van de graaf veranderen niet; omdat we elke boog door twee nieuwe en tegengesteld gerichte bogen vervangen blijft elk pad bestaan9 . Door dit proces wordt de graad van elke actor verdubbeld; deze is de som van de in- en uitgraad. Men kan met een vergelijkbare argumentatie aantonen dat de spil- en nabijheidcentraliteit in hun vorm zoals besproken in hoofdstuk 2 terug een gelijkaardige waarde en rangschikking zullen geven. Deze maten brengen ons geen extra of betere informatie. 9

Merk op dat de componenten van een gerichte graaf aan de hand van de onderliggende ongerichte graaf gedefinieerd worden.


45

Een boog met een groot gewicht kunnen we interpreteren als een “trouwe” co-auteursrelatie. Beginnende onderzoekers zullen telkens met hun promotor als co-auteur publiceren, wat een pijl met een groot gewicht oplevert. Wanneer deze onderzoekers groeien en zelfstandiger worden, zullen deze gaan publiceren met andere onderzoekers waardoor de sterke link met de promotor zal vervagen. Wanneer we nu de som nemen van de gewichten van alle inkomende bogen, kunnen we ons een beeld vormen van de “trouwheid” van de co-auteurs t.o.v. een onderzoeker. Deze waarde drukt dus uit in welke mate de onderzoeker beschikt over “sterk gelinkte” of trouwe andere onderzoekers. De resultaten worden weergegeven in Tabel 4.4. Merk op dat het logischer kan lijken om het gemiddelde (i.p.v. de som) te beschouwen. Het gebruik van de som geeft voordeel aan onderzoekers met veel publicaties en co-auteurs maar wanneer twee onderzoekers met een groot aantal publicaties samenwerken, zal dit een minimale impact op de waarde hebben. Hoge waarden kunnen alleen maar bekomen worden door over veel “trouwe” co-auteurs te beschikken. Hoge gemiddelden worden vooral door zeer laag gerangschikte (beginnende) onderzoekers bekomen. Beschouw bijvoorbeeld de complete graaf van orde vier die onstaat wanneer vier onderzoekers samenwerken aan één publicatie: elke auteur zal een gemiddelde van één hebben. We kunnen deze analyse ook in de omgekeerde richting maken wanneer we de gewichten van de uitgaande bogen beschouwen. Een klein uitgaand gewicht betekent dat de auteur maar voor een beperkte fractie van zijn publicaties samenwerkte met de corresponderende auteur. Dit kan duiden op de “veelzijdigheid” van een onderzoeker, die met veel andere auteurs samenwerkte. De resultaten worden weergegeven in Tabel 4.4. In de rangschikking geeft een kleiner gewicht aanleiding tot een hogere rangschikking. Hier beschouwen we het gemiddeld uitgaand gewicht omdat anders auteurs met veel co-auteurs benadeeld worden t.o.v. auteurs met relatief weinig co-auteurs.

4.3.3

Analyse met behulp van PageRank en HITS

Door de introductie van richting en gewichten, kunnen we nu wel maten zoals PageRank en HITS zinvol berekenen (zie Sectie 2.5.1). De resultaten worden weergegeven in Tabel 4.5. De PageRank implementatie in JUNG maakt gebruik van de gewichten op de bogen om de overgangskansen te berekenen10 . De interpretatie is dan als volgt: omdat beginnende onderzoekers voor veel publicaties samenwerken met dezelfde persoon (bv. hun promotor) zal het gewicht op de boog naar die actor groot zijn. Dit betekent dat zo’n centrale “expert” dan een grote fractie van de PageRanks van die beginnende onderzoekers krijgt. In de omgekeerde richting zal het gewicht op de boog veel kleiner zijn omdat deze “experten” met veel verschillende (beginnnende) onderzoekers samenwerken. Deze onderzoekers krijgen dus maar een beperkte fractie van de PageRank terug en zullen zo veel lager geranschikt blijven. Indien experten samenwerken met elkaar, wordt hun (grote) PageRank verder gecummuleerd. Didier Dubois werkt bijvoorbeeld zeer veel samen met Henri Prade en Salem Benferhat (die opmerkelijk veel hoger gerankschikt werd), en had ook enkele publicaties met Lluis Godo, Rudolf Kruse, Seraf´ın Moral, Miguel Delgado, Francesc Esteva en Andrzej Skowron die vergelijkbare resultaten behalen, enkel Miguel Delgado maakt een grote beweging: een verlies van 17 plaatsen11 . Etienne Kerre werkte samen met Bernard De Baets die op zijn beurt publiceerde met Lluis Godo, Francesc Esteva en Miguel Delgado. Merk op dat het verschil in rangschikking in Tabel 4.5 voor de meeste actoren zeer klein is (maximaal verschil is 19). Bij de grote “winnaars” is de winst in rangschikking opmerkelijk groot: tenminste 47, maar meestal zelfs groter dan honderd. In Figuur 4.8 wordt de globale 10

De “kans” van een boog wordt dan berekend door het gewicht van de uitgaande boog te delen door de som van de gewichten van alle uitgaande bogen. 11 We beschouwen in deze Sectie enkel de auteurs met de dertig hoogste PageRanks.


46

verdeling gegeven. We zien dat voor de hoogst gerangschikten de nieuwe rangschikking niet zo veel verandert terwijl voor de “middelmatige” auteurs het verschil zeer groot kan zijn. We besluiten dat we globaal toch een zeker verband (dat aan de kop en aan de staart veel sterker is) tussen de twee verschillende rangschikkingen zien. De output van het HITS algoritme verschilt in vergelijking met PageRank voor de eerste dertig resultaten veel meer van de rangschikking op basis van centraliteiten. Wanneer we echter een grafiek analoog aan Figuur 4.8 tekenen (zie Figuur 4.9), blijkt dat de verdeling van HITS globaal gezien dichter bij de oude rangschikking ligt dan die van PageRank12 . In de implementatie in JUNG wordt geen gebruik gemaakt van de booggewichten (in feite is de berekening dus identiek aan die op een ongerichte graaf). Dit maakt het verschil tussen authoriteiten en hubs onduidelijk. Voor elke inkomende boog is er ook een uitgaande: een top met veel inkomende bogen (d.i. een authoriteit) is dus meteen ook een hub. Door het ontbreken van een duidelijke interpretatie is moeilijk de waarde van deze ranschikking te beoordelen. We kunnen de structuur van het netwerk wijzigen om het HITS algoritme meer bruikbaar te maken. We kunnen het gericht, gewogen netwerk gaan aanpassen of we kunnen meteen een ander soort netwerk opbouwen: • Een eenvoudig voorstel is om bij elk paar tegengesteld gerichte pijlen telkens de pijl met het kleinste gewicht te verwijderen. Dit heeft als gevolg dat een promotor veel inkomende bogen zal hebben, terwijl een beginnende onderzoeker eerder uitgaande bogen zal hebben. Dit wordt besproken in Sectie 4.3.4. • Een ander voorstel is de betekenis van de pijl te definiëren als “doet beroep op”. Hoewel op sommige publicaties de namen alfabetisch gerangschikt worden, geeft de volgorde van de namen doorgaans het belang van de auteurs weer. De hoofdauteur staat dan vooraan, en bijauteurs eerder achteraan de lijst. Men zou kunnen stellen dat de hoofdauteur een beroep doet op de ervaring van de bijauteurs. We kunnen daarom alleen maar bogen vanaf de hoofdauteur naar alle andere auteurs trekken. Op deze manier krijgen promotoren of begeleiders vooral inkomende bogen (vervullen ze dus de rol van autoriteiten) en zullen beginnende onderzoekers vooral uitgaande bogen bevatten (hubs). Het netwerk wordt een stuk ijler maar blijft op deze manier wel verbonden. Een belangrijke vraag is welke gewichten we dienen te gebruiken. Er worden in deze scriptie verder geen experimenten met dit soort netwerken gedaan.

4.3.4

Analyse voor het aangepast gericht, gewogen netwerk

We kunnen het gericht, gewogen netwerk aanpassen zodat het beter geschikt is voor algoritmes zoals HITS. We zouden dan graag bekomen dat gevestigde onderzoekers (promotors, begeleiders) beter de rol van autoriteit spelen, en beginnende onderzoekers (doctorandi) eerder de rol van hub op zich nemen. We stellen vast dat beginnende onderzoekers uitgaande bogen met eerder grote gewichten hebben, terwijl gevestigde onderzoekers uitgaande bogen met eerder kleinere gewichten hebben. Wanneer we een paar bogen tussen een promotor en een doctorandus beschouwen, zal de doctorandus een pijl met een groot gewicht naar zijn promotor hebben (omdat hij veel met zijn promotor publiceert). Omgekeerd zal de promotor ook een pijl naar de doctorandus hebben, zij het met een veel kleiner gewicht (de promotor kan bijvoorbeeld meerdere doctorandi begeleiden). 12

Voor HITS hebben we een gemiddeld verschil in rangschikking van 312,12 en voor PageRank hebben we een gemiddeld verschil in rangschikking van 374,78. Men kan dit op de figuur zien doordat bij HITS de punten dichter bij de diagonaal liggen als bij PageRank.


47

Wanneer we nu in het gericht, gewogen netwerk voor elk paar bogen telkens de boog met het kleinste gewicht verwijderen, zullen de promotoren vooral ingaande bogen hebben. We willen ook rekening houden met het feit dat promotoren ook met elkaar samenwerken. Aangezien voor elke auteur dan de fractie gedeelde publicaties betrekkelijk vergelijkbaar is, zullen de booggewichten in dit geval dicht bij elkaar liggen. Daarom zullen we de boog maar verwijderen als het verschil tussen de twee gewichten groter of gelijk aan een bepaalde waarde is. Deze waarde werd experimenteel voor crawl2 vastgelegd op 0, 05.13 . Een typevoorbeeld van zo’n netwerk is te vinden in Figuur 4.10 Berekenen we voor dit nieuwe netwerk opnieuw HITS en PageRank. De resultaten voor de grootste deelcomponent zijn te zien in Tabel 4.6. Hoewel het gemiddeld verschil tussen de rangschikking volgens HITS en de oude rangschikking globaal gezien groter is geworden (330,72) zien we voor de eerste dertig resultaten een kleine vermindering. Het valt direct op dat de resultaten gelijkaardig zijn, zo is bijvoorbeeld de top zes gelijk gebleven. We merken op dat voor de eerste helft van de tabel de autoriteitswaarden hoger liggen, de autoriteiten zijn dus met andere woorden meer uitgesproken autoriteit geworden. De resultaten (zie Tabel 4.6) voor PageRank wijken meer af van reeds bekomen resultaten. We hebben geen “feedbackboog”: promotoren zullen nu vooral PageRank gaan opnemen en niet meer verder in hun omgeving (bv. hun doctorandi) verdelen. Een beginnende onderzoeker zal dus niet kunnen meeprofiteren van de hoge PageRank van zijn promotor. Merk op dat dit op zijn beurt terug nadelig is voor de PageRank van die promotor.

4.4

Besluit

In dit hoofstuk bestudeerden we de “Fuzzy Sets and Systems”-wereld vanuit het oogpunt van samenwerkingsverbanden (co-auteurschap). We probeerden belangrijke actoren te identificeren aan de hand van de structuur van dit netwerk. Ongeveer de helft van het netwerk is samenhangend terwijl de andere helft versplinterd is in kleine componenten. Voor de grootste component maakten we verschillende rangschikkingen: één gebaseerd op klassieke centraliteitsmaten en twee gebaseerd op geavanceerde technieken uit de context van het Web (hyperlinknetwerken). Het is verrassend hoe voor de rangschikkingen gebaseerd op centraliteiten en andere algoritmes telkens dezelfde actoren naar voor komen. PageRank geeft wellicht de meest realistische resultaten omdat deze in plaats van enkel de positie in het netwerk ook het relatief belang van de omgeving meeneemt. De resultaten van HITS kunnen we iets verfijnen door de structuur van het netwerk aan te passen. Het is wenselijk om een evaluatie van de bekomen resultaten te maken door deze resultaten te vergelijken met “inhoudelijke” maten zoals het aantal citaties of de impact van de publicaties van de actoren in het netwerk. We zouden gebruik kunnen maken van meerdere informatiebronnen in de hoop een beter verbonden en meer gedetailleerd netwerk te krijgen. Verder kunnen we nieuwe algoritmen ontwerpen (voor opbouw en analyse van het netwerk) om beter in te spelen op klasses actoren zoals doctorandi en promotoren. 13

Deze waarde werd bepaald door het bestuderen van het aantal verwijderde bogen en het uitzicht van het netwerk in de buurt van Prof. Dr. Etienne Kerre.


48

B A

J I

C

L

D E

G

K

H

F

Figuur 4.1: Voorbeeld van een basis BuildSimpleCoauthorGraph (zie Sectie D.3.1.)

rang 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

publicaties naam aantal co-auteurs Wei Wang 292 17 Ming Li 275 6 Wei Li 266 10 Horst Bunke 235 6 Henri Prade 234 47 Witold Pedrycz 230 47 Didier Dubois 219 52 Tharam S. Dillon 214 6 Elke A. Rundensteiner 212 6 Nicholas R. Jennings 192 8 Edward A. Fox 189 5 Vladik Kreinovich 169 31 Ricardo A. Baeza-Yates 169 3 Hong Yan 167 6 Ronald R. Yager 164 27 Victor R. Lesser 163 4 Antonio Gonzalez 154 9 David E. Goldberg 151 7 Jan Treur 149 3 Manfred Glesner 143 3 Hui Zhang 140 7 Richard R. Muntz 139 6 Andrzej Skowron 134 15 Alan Bundy 133 2 Judea Pearl 131 3 Simon Parsons 125 18 Jian Zhang 124 6 Shusaku Tsumoto 122 7 Taghi M. Khoshgoftaar 122 2 Ajith Abraham 121 7

co-auteursnetwerk

rang 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

naam Hui Wang Xiaoou Tang Chengqi Zhang David A. Bell Sung-Bae Cho Sankar K. Pal Vijay V. Raghavan Paul R. Cohen Gerardo Canfora Tao Li Kaoru Hirota Lei Xu Michael P. Wellman Salem Benferhat Craig Boutilier Abraham Kandel C. Mohan Jun Li Xin He Antonio F. Gomez-Skarmeta Eric Horvitz Kwong-Sak Leung Wynne Hsu Etienne E. Kerre Li Chen Alberto Prieto Carles Sierra David Heckerman John Yen S. K. Michael Wong

zoals

gebouwd

door

aantal co-auteurs 120 8 120 4 119 7 119 8 116 3 115 13 114 5 113 11 110 1 107 1 106 19 105 1 104 5 102 21 102 3 99 19 99 1 97 10 97 6 95 14 93 7 93 12 92 2 90 28 89 7 88 18 87 6 87 9 85 7 85 4

Tabel 4.2: Overzicht van het aantal publicaties en het aantal verschillende co-auteurs van de meest “productieve” onderzoekers. Enkel gemarkeerde auteurs werden geteld, alle andere auteurs worden genegeerd. Een laag aantal co-auteurs betekent dus enkel dat de auteur met weinig gemarkeerde auteurs heeft samengewerkt: zo heeft bijvoorbeeld Wei Wang in totaal 472 verschillende co-auteurs.


49

componentgrootte 60%

50%

40%

30%

20%

10%

0%

1

2

3

4

5

6

7

8

9

10

11

12

14

17

1834

relatief aantal componenten (%) 31,98 34,36 16,41 7,57% 2,38% 3,37% 1,26% 0,56% 0,56% 0,42% 0,28% 0,42% 0,14% 0,14% 0,14% relatief aantal actoren (%) 6,34% 13,62 9,76% 6,00% 2,36% 4,00% 1,75% 0,89% 1,00% 0,83% 0,61% 1,00% 0,39% 0,47% 50,97

Figuur 4.2: Overzicht van de componenten in de crawl2 dataset. Op de horizontale as wordt de grootte van de componenten gegeven. “Relatief aantal actoren” betekent de fractie van de actoren die in een cluster met de gegeven grootte zitten.

graad 30%

relatieve frequentie

25%

20%

15%

10%

5%

0% 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 31 32 33 35 47 52

graad

Figuur 4.3: Relatieve verdeling van de graad. Waarden op de horizontale as met een nulfrequentie werden weggelaten.


50

histogram clusteringcoëfficiënt 70%

60%

relatieve frequentie

50%

40%

30%

20%

10%

0% 0 0,05 0,1 0,15 0,2 0,25 0,3 0,35 0,4 0,45 0,5 0,55 0,6 0,65 0,7 0,75 0,8 0,85 0,9 0,95 1 clusteringcoëfficiënt

Figuur 4.4: Histogram van de clusteringcoëfficient met interval 0, 05. Bij het interval is telkens de laagste waarde inclusief en de hoogste waarde exclusief. Merk op dat “eenvoudige” waarden (zoals 1/2, 1/3, 2/3) meer voorkomen.

verband tussen graad en clusteringcoëfficiënt 1 0,9 0,8

clusteringcoëffici:ent

0,7 0,6 0,5 0,4 0,3

0,2 0,1 0 0

5

10

15

20

25

30

35

40

45

50

55

60

graad

Figuur 4.5: Verband tussen de graad en de clusteringcoëfficiënt. Op de horzontale as toont de graad en de verticale as de clusteringcoëfficiënt. Hoe groter de cirkel, hoe meer graadclusteringcoëfficiëntparen voorkomen. Als de graad groter wordt, dan wordt de clusteringcoëfficiënt lager: dit wordt aangegeven met de curve.


rang naam 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Witold Pedrycz Didier Dubois Miguel Delgado Lluis Godo Henri Prade Ronald R. Yager Bernard De Baets Vladik Kreinovich Francisco Herrera Kaoru Hirota Antonio di Nola Philippe Smets Janos C. Fodor Serafin Moral Hung T. Nguyen Simon Parsons Rudolf Kruse Etienne E. Kerre Salvatore Sessa Michel Grabisch Radko Mesiar Isabelle Bloch Abraham Kandel Maria Amparo Vila Miranda Sankar K. Pal Fernando A. C. Gomide Daniel S. Yeung Andrzej Skowron Luis Martinez Masao Mukaidono

graad 47 52 32 33 47 27 35 31 33 19 25 26 18 33 20 18 31 28 18 23 20 20 19 22 13 11 14 15 12 15

51

graad spilcentraliteit nabijheid clustering- gemiddelde spilcentraliteit nabijheid maxdist rang rang rang coëfficiënt rang 2 302897,09 1 4,2624 1 10 0,0444 1,33 1 152353,52 5 4,2908 2 11 0,1395 2,67 8 182475,10 2 4,3955 6 11 0,1935 5,33 5 123590,40 8 4,3159 4 11 0,2008 5,67 3 87874,36 16 4,3595 5 11 0,1591 8,00 12 129214,43 7 4,4037 8 11 0,0427 9,00 4 119350,28 10 4,5717 17 11 0,0706 10,33 9 102878,68 12 4,4997 12 10 0,0753 11,00 6 108955,92 11 4,6159 19 11 0,1515 12,00 30 163370,35 3 4,3972 7 10 0,0819 13,33 14 93375,11 13 4,5085 13 10 0,1167 13,33 13 80867,56 19 4,4506 10 11 0,3508 14,00 34 133619,12 6 4,3033 3 10 0,1569 14,33 7 81098,87 18 4,6345 21 12 0,2405 15,33 24 81152,19 17 4,4659 11 10 0,1158 17,33 35 121456,29 9 4,5456 14 11 0,3856 19,33 10 54155,22 32 4,5848 18 11 0,2688 20,00 11 90975,36 15 4,9193 45 11 0,1005 23,67 36 59909,93 26 4,4294 9 10 0,1961 23,67 17 35104,51 55 4,6803 24 11 0,3004 32,00 25 59725,53 27 4,9405 49 12 0,0947 33,67 27 45525,17 40 4,8249 37 11 0,3684 34,67 31 66274,33 23 4,9918 60 10 0,1345 38,00 20 37386,38 51 4,9253 46 12 0,2857 39,00 57 77765,04 20 4,8783 41 10 0,1282 39,33 76 60520,49 24 4,6918 25 10 0,1455 41,67 49 59698,56 29 4,9558 53 11 0,2088 43,67 43 44635,93 41 4,9465 50 11 0,1619 44,67 64 39445,53 49 4,7310 26 11 0,3939 46,33 42 51615,36 36 5,0671 75 10 0,1238 51,00

Tabel 4.3: Overzicht van de resultaten voor de graad-, spil- en nabijheidcentraliteit. De eerste dertig resultaten worden gerangschikt op hun gemiddelde rang. Verder wordt ook nog de clusteringcoëfficiënt en de afstand tot de meest ver verwijderde auteur (maxdist) gegeven.

Figuur 4.6: Co-auteurs van Prof. Dr. Etienne Kerre. (Eén niveau diep.)


0,5

B

52

0,6

0,5

0,25

0,5 0,5 0,111 C A 0,222 0,111 0,5 0,25 0,5 0,125 D 0,333 0,5 0,5 0,666 0,6 0,222 0,444 E G 0,375 0,666 1 0,333 0,5 0,666 0,666 F

0,6

I 0,4 0,4

H

0,5 0,4

J 0,8

1

0,4

1

K

1

L

0,5

Figuur 4.7: Voorbeeld van een gericht, gewogen co-auteursnetwerk zoals gebouwd door BuildDirectedWeightedCoauthorGraph. (Zie Sectie D.3.2.)

rang 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

som gewicht inkomende bogen name som publicaties Bernard De Baets 16,911037 67 Etienne E. Kerre 14,484044 90 Francisco Herrera 14,437519 84 Oscar Cordon 11,853356 51 Witold Pedrycz 11,498508 230 Henri Prade 10,182765 234 Robert Babuska 10,095460 24 Didier Dubois 10,089387 219 I. Burhan Turksen 9,975320 40 Hector Pomares 9,705969 51 Ignacio Rojas 9,680693 73 Tsu-Tian Lee 9,360945 27 Vladik Kreinovich 8,636068 169 Jesus Gonzalez 8,353079 43 Abraham Kandel 8,196564 99 Hisao Ishibuchi 7,931533 82 Alberto Prieto 7,832651 88 Antonio F. Gomez-Skarmeta 7,629489 95 Rudolf Kruse 7,469952 75 Enrique Herrera-Viedma 7,259186 36 Hidetomo Ichihashi 7,094792 27 Daniel Sanchez 6,858531 28 Serafin Moral 6,654497 69 James M. Keller 6,500986 35 Lluis Godo 6,409719 65 Endre Pap 6,232906 22 Carlo Bertoluzza 6,174206 8 Antonio Gisolfi 6,174110 15 Jonathan Lee 6,038681 41 Thierry-Marie Guerra 6,000000 8

rang 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

gemiddeld gewicht uitgaande bogen naam gemiddelde publicaties Wei Wang 0,005641 292 Ming Li 0,008485 275 Tao Li 0,009346 107 Ajith Abraham 0,009445 121 Lei Xu 0,009524 105 Ronald R. Yager 0,009711 164 C. Mohan 0,010101 99 Hui Zhang 0,010204 140 Xin He 0,012027 97 Xiaoou Tang 0,012500 120 Wei Li 0,012782 266 Paul R. Cohen 0,014481 113 Hui Li 0,015152 66 Stefano Spaccapietra 0,015152 66 Judea Pearl 0,015267 131 Vladik Kreinovich 0,015270 169 Craig Boutilier 0,016340 102 Tao Wang 0,016667 70 Ricardo A. Baeza-Yates 0,017751 169 Lotfi A. Zadeh 0,018443 61 Jun Li 0,018557 97 Wei Xu 0,018868 53 Witold Pedrycz 0,018964 230 Simon Parsons 0,019111 125 Yueting Zhuang 0,019531 64 Antonio Gonzalez 0,020202 154 Marcel J. T. Reinders 0,020408 49 Wai Lam 0,020468 76 Claudio Moraga 0,020468 76 Taghi M. Khoshgoftaar 0,020492 122

Tabel 4.4: Resultaten voor de som van de gewichten van de inkomende bogen en het gemiddeld uitgaand gewicht.


rang 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

PageRank naam Didier Dubois Henri Prade Witold Pedrycz Francisco Herrera Etienne E. Kerre Bernard De Baets Vladik Kreinovich Lluis Godo Abraham Kandel Kaoru Hirota Oscar Cordon Salem Benferhat Rudolf Kruse Radko Mesiar Kwong-Sak Leung Serafin Moral Sankar K. Pal I. Burhan Turksen James M. Keller Miguel Delgado Hisao Ishibuchi Maria Amparo Vila Miranda Mark Last Francesc Esteva Ronald R. Yager Antonio di Nola Hung T. Nguyen Andrzej Skowron Tsu-Tian Lee Daniel S. Yeung

53

HITS PageRank oude rang 0,007249 2 0,007087 5 0,006137 1 0,004263 9 0,004123 18 0,003500 7 0,003463 8 0,003360 4 0,003180 23 0,003009 10 0,002966 48 0,002958 112 0,002806 17 0,002551 21 0,002548 147 0,002412 14 0,002389 25 0,002352 65 0,002276 116 0,002274 3 0,002266 360 0,002231 24 0,002170 195 0,002164 31 0,002147 6 0,002115 11 0,002108 15 0,002100 28 0,002078 78 0,001994 27

rang 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

naam Didier Dubois Henri Prade Rudolf Kruse Serafin Moral Philippe Smets Alessandro Saffiotti Jerôme Lang Lluis Godo Salem Benferhat Miguel Delgado Michel Grabisch Helène Fargier Nic Wilson Isabelle Bloch Claudio Sossai Alain Appriou Simon Parsons Hong Xu Francesc Esteva Regis Sabbadin Petr Hajek Pere Garcia Khaled Mellouli Salvatore Sessa Sylvain Lagrue Siegfried Gottwald Bernard De Baets Janos C. Fodor Marc Roubens Enrique H. Ruspini

HITS oude rang 0,036167 2 0,034602 5 0,026858 17 0,026631 14 0,026150 12 0,025959 39 0,025600 66 0,023013 4 0,022662 112 0,021085 3 0,020902 20 0,019821 183 0,019601 169 0,019385 22 0,018913 110 0,018836 132 0,018298 16 0,017548 227 0,009914 31 0,009395 271 0,008421 33 0,008293 133 0,008220 58 0,007991 19 0,007312 374 0,007129 42 0,007001 7 0,006933 13 0,006798 44 0,006508 159

Tabel 4.5: De resultaten voor PageRank en HITS op de gewogen, gerichte graaf bekomen zoals beschreven in 4.3.1. Telkens worden de eerste dertig auteurs weergegeven. De kolom “oude rang” geeft ter referentie de rangschikking met behulp van klassieke maten (zie Tabel 4.3). Het “gemiddeld verschil” wordt bekomen door het gemiddelde te nemen van de absolute waardes van het verschil in rangschikking, het drukt dus m.a.w. uit hoe groot het verschil is met het vorig overzicht.

verband tusen oude en PageRank rangschikking 2000 1800

rangschikking volgens PageRank

1600 1400 1200 1000 800 600 400 200

0 0

200

400

600

800

1000

1200

1400

1600

1800

2000

oude rangschikking

Figuur 4.8: Het verband tussen de rangschikking zoals in Tabel 4.3 (horizontale as) en de rangschikking volgens PageRank (verticale as).


54

verband tusen oude en HITS rangschikking 2000 1800

rangschikking volgens HITS

1600 1400 1200 1000 800 600 400 200

0 0

200

400

600

800

1000

1200

1400

1600

1800

2000

oude rangschikking

Figuur 4.9: Het verband tussen de rangschikking zoals in Tabel 4.3 (horizontale as) en de rangschikking volgens HITS (verticale as).

0,5

B 0,5

A 0,5 0,25 0,333 0,666

E

D 1

0,666

F

0,6

0,5 0,5 0,5 0,5 0,444

I

C 0,4 0,4

0,5

G

0,6

H

J

1

0,6 1 0,4

K

1

L

0,666

Figuur 4.10: Voorbeeld van een aangepast gericht, gewogen co-auteursnetwerk. Dit voorbeeld vertrekt van Figuur 4.7 waarbij voor elk paar bogen telkens de kleinste boog werd verwijderd indien het verschil groter dan of gelijk aan 0, 1 was.


rang 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

PageRank naam pagerank oude rang Henri Prade 0,018118 5 Miguel Delgado 0,011548 3 Witold Pedrycz 0,011483 1 Didier Dubois 0,010895 2 Hui Wang 0,010272 94 Serafin Moral 0,009869 14 Andrzej Skowron 0,009715 28 Francisco Herrera 0,008598 9 Vladik Kreinovich 0,008194 8 Sankar K. Pal 0,008111 25 Etienne E. Kerre 0,007926 18 Ronald R. Yager 0,007890 6 Maria Amparo Vila Miranda 0,007376 24 Lluis Godo 0,007193 4 David A. Bell 0,006901 180 Rudolf Kruse 0,006687 17 Bernard De Baets 0,006670 7 Simon Parsons 0,006253 16 Hui Zhang 0,006224 137 Yang Xu 0,006148 87 Wojciech Ziarko 0,006112 292 S. K. Michael Wong 0,005533 632 Ah Chung Tsoi 0,005193 332 Luis M. de Campos 0,005002 146 Philippe Smets 0,004894 12 Wei Wang 0,004859 35 Ming Li 0,004770 331 Robert Babuska 0,004705 123 Petr Hajek 0,004654 33 James F. Peters 0,004573 47 gemiddeld verschil in rang: 76,5

55

rang 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

HITS naam Didier Dubois Henri Prade Rudolf Kruse Serafin Moral Philippe Smets Alessandro Saffiotti Salem Benferhat Lluis Godo Miguel Delgado Isabelle Bloch Simon Parsons Nic Wilson Helène Fargier Michel Grabisch Jerôme Lang Hong Xu Bernard De Baets Petr Hajek Claudio Sossai Salvatore Sessa Regis Sabbadin Piero P. Bonissone Janos C. Fodor Antonio di Nola Siegfried Gottwald Carles Sierra Lotfi A. Zadeh Francisco Herrera Luis M. de Campos Enrique H. Ruspini gemiddeld verschil in rang:

HITS oude rang 0,066790 2 0,065506 5 0,045792 17 0,045437 14 0,040823 12 0,040040 39 0,034266 112 0,033849 4 0,033774 3 0,030410 22 0,029172 16 0,028574 169 0,027635 183 0,026897 20 0,025941 66 0,025041 227 0,013253 7 0,011487 33 0,010186 110 0,009421 19 0,009369 271 0,008487 72 0,008442 13 0,008142 11 0,007676 42 0,007351 283 0,007261 43 0,007244 9 0,006875 146 0,006461 159 59,67

Tabel 4.6: De resultaten voor PageRank en HITS op de gewogen, gerichte graaf waarbij bogen verwijdered werden zoals beschreven in Sectie 4.3.4. De kolom “oude rang” geeft ter referentie de rangschikking met behulp van klassieke maten weer (zie Tabel 4.3).

Hoofdstuk 5

Onderzoekersprofielen In het vorige hoofdstuk bestudeerden we de “Fuzzy Sets and Systems” onderzoeksgemeenschap door gebruik te maken van samenwerkingsverbanden tussen verschillende onderzoekers. Deze samenwerkingsverbanden ontstaan door het samen publiceren van wetenschappelijke artikels. We willen deze studie uitbreiden door naast sociale verwantschappen ook verbanden in het (geschreven) werk van de onderzoekers te zoeken. Hiervoor zullen we voor elke onderzoeker een “inhoudelijk” profiel opstellen en deze profielen later met elkaar vergelijken. De inspiratie voor de voorstelling van dergelijke profielen werd gevonden bij folksonomieën, die reeds in Hoofdstuk 3 besproken werden. We kunnen kernwoorden gebruiken om onderzoekers te “taggen”, waardoor we profielen bekomen die opgebouwd zijn uit kernwoorden. Kernwoorden die door een bepaalde auteur veel gebruikt worden, zullen aanleiding geven tot een tag met een grotere frequentie. Net als bij Delicious zullen de hoogst gerangschikte tags een groter belang hebben; men zou zelfs kunnen stellen dat die het onderzoeksonderwerp van de onderzoeker samenvatten. Verder verloop van dit hoofdstuk We starten met het verrijken van de dataset met extra inhoudelijke informatie. Deze data wordt eerst als een netwerk voorgesteld waarna we enkele gegevens bepalen. Daarna stellen we de profielen voor als een vaagverzameling en proberen we deze voorstelling te gebruiken om onderzoekers aan elkaar te linken op basis van hun profiel.

5.1

Uitbreiding van de dataset

Om onderzoekersprofielen op te kunnen stellen, dienen we te beschikken over extra, inhoudelijke, informatie. De publicaties waarvan we ons sociaal netwerk hebben afgeleid, zijn hiervoor de ideale bron. We kunnen meer informatie over de publicaties terugvinden door gebruik te maken van de link naar de elektronische editie (EE) die (indien beschikbaar) door DBLP gegeven wordt. Deze informatie werd bij het creëren van crawl2 ook in de Sesame Repository ge¨ımporteerd: in totaal bevat de repository 21650 verschillende URL’s. Deze URL’s verwijzen naar de webpagina’s van verschillende uitgevers. Analyse van de verschillende soorten URL’s toont aan dat sommige uitgevers duizenden publicaties hebben, terwijl andere slechts instaan voor enkele tientallen. Deze analyse wordt bemoeilijkt door het gebruik van het DOI-systeem1 omdat dan niet uit de URL kan afgeleid worden welke uitgever achter 1 DOI staat voor Digital Object Identifier. Het DOI-systeem is ontworpen om “contentobjecten” in een digitale omgeving te identificeren. Elk object krijgt een unieke DOI-naam die dan gebruikt kan worden als een permanente identificatie. De achterliggende informatie van het object (zoals bijvoorbeeld de locatie waar het te vinden is of andere meta-informatie) kan veranderen, maar de DOI-naam blijft vast. We verwijzen de lezer voor meer

56

HOOFDSTUK 5. ONDERZOEKERSPROFIELEN

57

een bepaalde DOI naam zit. We merken dat twee grote uitgevers (namelijk Elsevier en Springer) een relatief grote fractie van de URL’s bepalen (elk ongeveer één vierde). Verder hebben we verschillende kleine uitgevers die elk een tiental tot enkele honderden publicaties hebben. ScienceDirect2 , d.i. de portaalsite van Elsevier, biedt voor de meeste publicaties een abstract en (door de auteur opgegeven) kernwoorden. SpringerLink3 van Springer biedt in het beste geval enkel abstracts4 . Omdat de tijdschriften “Fuzzy Sets and Systems” en “International Journal of Approximate Reasoning” hun elektronische editie op ScienceDirect hebben, werd beslist om enkel op ScienceDirect te crawlen5 . Dit gebeurt met de takenlijst profiles_download.cm (zie Sectie E.2.1) die 5492 URL’s identificeert als zijnde van ScienceDirect (de 16158 andere worden dus niet herkend en verder genegeerd). Voor deze pagina’s vinden we 312 keer geen abstract, en 945 keer geen kernwoorden. De data wordt toevoegd aan crawl2. De abstracts worden verder niet meer gebruikt, maar werden wel verzameld omdat het weinig extra werk betekent wanneer de kernwoorden gedownload worden. Het aanwenden van deze deze data als gebruikersprofielinformatie werd ge¨ınspireerd door folksonomieën: elke auteur wordt getagd met de kernwoorden die we gevonden hebben. Sommige kernwoorden worden vaker gebruikt dan andere, wat zal gereflecteerd worden in hogere corresponderende gewichten. We hopen dat de stabiele tagverdelingen zoals bij folksonomieën ook hier voorkomen. We kunnen nu gebruik maken van de algoritmes die reeds voor folksonomieën bestaan om gerelateerde kernwoorden te gebruiken.

5.2

Representatie van de gebruikersprofielen

Hoewel deze informatie nu opgeslagen is in onze repository, is ze nog niet praktisch bruikbaar. Daarvoor moeten we namelijk eerst de informatie uit de repository halen en bundelen in een datamodel. We stellen twee datamodellen voor: een netwerkgebaseerd model dat een uitbreiding is op het sociaal netwerk en een model gebaseerd op vaagverzamelingen.

5.2.1

Netwerkgebaseerde representatie

We kunnen de sociale netwerken zoals besproken in Hoofdstuk 4 uitbreiden met profielinformatie. We vertrekken van een sociaal netwerk en voegen voor elke verschillende tag een top toe. Telkens een kernwoord in een publicatie van een auteur gebruikt wordt, wordt een gerichte boog van de auteur naar die tag (d.i. het kernwoord) aan de graaf toegevoegd. Deze pijlen drukken dus het profiel uit: een pijl betekent dat die auteur die tag tenminste éénmaal gebruikt heeft. Op de pijlen wordt een gewicht geplaatst dat weergeeft hoeveel keer dat de auteur het kernwoord gebruikt heeft6 . Voor de voorstelling van het profiel maakt het niet uit welk type onderliggend sociaal netwerk gekozen wordt. We kunnen ook vertrekken van de graaf die enkel de toppen van de auteurs (dus geen bogen) bevat. Een voorbeeld van een dergelijke profielgraaf is te vinden in Figuur 5.1. Merk op dat er kernwoorden zijn die in verschillende woordvormen voorkomen (bv. genetic algorithm en genetic algorithms) maar die naar hetzelfde verwijzen. Met behulp van “steminformatie naar http://www.doi.org/. 2 http://www.sciencedirect.com (bezocht op 12 mei 2007) 3 http://www.springerlink.com (bezocht op 12 mei 2007) 4 Het gebeurt wel dat er kernwoorden gegeven worden, maar dit gebeurt niet op een vaste manier. Soms worden de kernwoorden in de abstract gemarkeerd of soms maken ze deel uit van de laatste regel van de abstract. 5 Voor FUZZ-IEEE hebben we geen EE links en voor IFSA komen we terecht op een SpringerLink pagina. 6 Naar analogie met folksonomieën kunnen auteurs verschillende keren met dezelfde tag getagd worden. We kunnen stellen dat de auteurs corresponderen met de “items” en de publicaties met de “gebruikers” in de folksonomie.


T2

T4

T3

T6

58

T10

T8

T12

T9

T5

T1

T11

T13

T7

B

J I

C

A

L

D E

G

H

K

F

Figuur 5.1: Voorbeeld van een netwerkvoorstelling van een profiel. Als onderliggend sociaal netwerk werd het basis co-auteursnetwerk uit Sectie 4.2 gebruikt. De gewichten op de pijlen werden weggelaten om de figuur overzichtelijk te houden. Merk op dat de figuur onvolledig is in die zin dat niet voor elke publicatie een tag getekend werd, geen enkele publicatie meerdere tags bezit en tags niet door verschillende publicaties opnieuw gebruikt worden. ming” worden deze gelijkaardige tags ge¨ıdentificeerd en samengevoegd. Stemming is het proces waarbij de stam van een woord bepaald wordt. Dit gebeurt op een algoritmische manier, m.a.w. met behulp van heuristieken7 . De woorden fish, fishes en fished kunnen zo bijvoorbeeld gereduceerd worden naar fish. We maken gebruik van de Snowball English stemmer8 . Door dit proces kunnen we het aantal verschillende tags iets reduceren. Wanneer we zo’n profielgraaf opbouwen voor crawl2, levert dit ons een profielgraaf met 11735 tags op. Er zijn 32249 pijlen van de auteurs naar de tags en de totale som van de gewichten is 36023: zeer veel tags worden dus maar eenmaal door de auteurs gebruikt. Om de verzameling tags beter handelbaar te maken, zullen we uit de 11735 unieke tags de weinig relevante verwijderen. We weerhouden enkel die tags die in tenminste drie verschillende publicaties gebruikt werden. Op deze manier houden we enkel kwalitatieve, hergebruikte tags over en worden “downloadartefacten”9 verwijderd. Dit gebeurt met de FilterKeywords taak: na deze operatie hebben we nog 1213 unieke tags over. Een overzicht van de 60 meest gebruikte tags wordt gegeven in Tabel 5.1. Een aantal auteurs heeft geen publicaties waarvoor er kernwoorden beschikbaar waren. Deze worden dus niet getagd en hebben een “leeg profiel”. Na het verwijderen van de niet relevante kernwoorden is dit aantal 803. In Figuur 5.2 wordt het profiel van Etienne Kerre weergegeven. 7

Er bestaan ook woordenboekgebaseerde stemmers. Deze stemmer is ook bekend onder de naam Porter2. Zie http://snowball.tartarus.org/. 9 Door bijvoorbeeld het uitzonderlijk gebruik van andere scheidingstekens gaat het selecteren van de kernwoorden soms mis. Ook kernwoorden met syntactische fouten beschouwen we als downloadartefacten. 8


rang 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

tag (stam) genetic algorithm fuzzy set fuzzy control neural network fuzzy numb fuzzy log fuzzy clust data min fuzzy system bayesian network approximate reason pattern recognit fuzzy rel stabil uncertainti learn t-norm possibility theori cluster rough set membership funct expert system fuzzy measur optim classif fuzzy model choquet integr information retriev fuzzy system model triangular norm

voorkomen van tags auteurs gebruikt publicaties 256 377 180 251 325 174 255 316 132 206 269 160 177 251 133 194 228 120 133 185 90 104 156 80 124 140 49 79 128 61 111 122 61 96 119 71 102 119 65 86 119 53 98 116 64 99 115 52 66 106 52 81 104 55 75 103 65 62 102 55 81 91 45 80 91 59 63 85 44 68 82 48 72 81 49 74 81 33 50 79 34 62 79 39 72 79 31 52 77 40

rang 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

tag (stam) belief funct adaptive control decision mak fuzzy topolog fuzzy inference system linguistic model aggregation oper nonlinear system image process machine learn fuzzy integr probabilistic reason neuro-fuzzy system decision tre decision analysi robot analysi t-conorm non-classical log fuzzy random vari non-additive measur probabl evolutionary algorithm algorithm artificial neural network fuzzy c-mean fuzzy rul fuzzy mathematical program association rul random set

59

auteurs

gebruikt 45 56 57 43 57 53 34 50 49 50 50 37 51 47 50 42 39 26 33 29 25 39 33 35 38 23 37 38 28 33

73 66 66 63 61 60 58 57 56 56 56 55 54 53 50 49 48 48 48 48 47 47 46 45 44 44 44 43 43 42

publicaties 43 33 38 36 25 27 28 26 36 32 27 27 25 30 26 20 23 19 25 28 27 30 14 36 29 27 19 18 24 18

Tabel 5.1: Overzicht van de meest gebruikte kernwoorden, na stemming. De kolom “gebruikt” geeft aan hoeveel keer het kernwoord als tag gebruikt werd (m.a.w. de som van het gewicht op de inkomende bogen), de kolom “auteurs” hoeveel auteurs deze tag kregen en “publicaties” het aantal publicaties waar dit kernwoord in voorkwam.

Figuur 5.2: Tags van Etienne Kerre zoals voorgesteld door het ViewGraph applet. De tilde betekent dat de top een tag voorstelt. De gewichten worden niet getekend.


5.2.2

60

Vaagverzameling gebaseerde representatie

Hoewel relatief compact, is de netwerkgebaseerde representatie niet erg handig om verschillende profielen te vergelijken. We zullen deze voorstelling daarom vertalen naar een representatie als vaagverzameling. Door gebruik te maken van de netwerkgebaseerde voorstelling kunnen we gebruik maken van de reeds uitgevoerde bundeling en filtering van de data. Een profiel van een auteur kunnen we nu voorstellen als een vaagverzameling over het universum van tags. Dit betekent dat we met elke tag een waarde tussen nul en één associëren die uitdrukt hoe “goed” die tag tot het profiel behoort. Deze waarde bepalen we door het absuluut aantal keer dat de tag gebruikt werd te normalizeren met het maximaal aantal keer dat de auteur dezelfde tag gebruikte. Meer formeel kunnen we een profiel definiëren als volgt. Stel A de verzameling van alle auteurs ai en T de verzameling van alle (unieke) tags tj . We introduceren de functie Q die het gewicht op de boog van a naar t geeft. Indien er geen boog is, wordt er nul gegeven. Q:A×T →N (a, t) 7→ het aantal keer dat auteur a met t getagd is,

∀(a, t) ∈ A × T

Deze functie kunnen we nu gebruiken om het profiel van een auteur a voor te stellen als een vaagverzameling Pa over het universum T . Definitie 16 Het profiel Pa van een auteur a ∈ A wordt gegeven door Pa : T → [0, 1] Q(a, t) t 7→ , max Q(a, s)

∀t ∈ T

s∈T

We bewaren deze vaagverzameling als een rij van vlottende komma-getallen. De profielen van alle auteurs kunnen we nu in de (|A| × |T |) matrix (pij ) met pij = Pai (tj ) bewaren waar elke rij een profiel voorstelt en een kolom de lidmaatschapsgraden van een bepaalde tag. Om in de implementatie van deze matrix het profiel van een auteur of de waarheidswaarde van een tag te bepalen, hebben we een index van auteurs en van tags nodig. Deze worden opgebouwd door het alfabetisch rangschikken van de auteurs (resp. tags) en de positie van de auteur (resp. tag) in de martrix wordt dan bepaald door de positie in deze lijst. Deze twee lijsten worden samen met de profielmatrix gebundeld in het Profile object, dat in de ObjectStore bewaard wordt om door andere taken gebruikt te worden. We willen ook de beperkte schaalbaarheid van deze aanpak vermelden. Wanneer we geen tags wegfilteren en de tabel maken voor alle auteurs en de 11735 oorspronkelijke tags (we gebruiken dubbele precisie vlottende-komma precisie), bekomen we een tabel van meer dan 320 MiB. We maken daarom gebruik van enkelvoudige precisie en we beschouwen enkel de (1213) geselecteerde tags. Het gebruik van enkelvoudige precisie heeft het nadeel dat de foutmarge bij het vergelijken van de profielen verhoogt, maar halveert wel de tabelgrootte.

5.3

Bepalen van verwante profielen

Nu we beschikken over de representatie gebaseerd op vaagverzamelingen kunnen we technieken uit de vaagverzamelingenleer toepassen om verwante profielen te bepalen. Introduceren we eerst enkele begrippen. De kardinaliteit van een vaagverzameling in een eindig universum is de som van alle lidmaatschapsgraden van de tags. We definiëren de “profielbreedte” als het aantal tags


kwaliteit van de profielen profielkardinaliteit hergebruik breedte Witold Pedrycz 90 17,364 5,183 Hong Yan 57 21,000 2,714 Sankar K. Pal 45 12,000 3,750 Etienne E. Kerre 43 9,833 4,373 Ronald R. Yager 41 10,667 3,844 Isabelle Bloch 41 9,000 4,556 M. Narasimha Murty 38 12,400 3,065 Horst Bunke 37 10,800 3,426 James C. Bezdek 37 9,667 3,828 Didier Dubois 36 9,600 3,750 Nikhil R. Pal 35 14,333 2,442 Henri Prade 35 11,500 3,043 Lei Xu 35 8,125 4,308 Kaoru Hirota 33 9,800 3,367 Thierry Denoeux 33 7,714 4,278 I. Burhan Turksen 30 10,250 2,927 Francisco Herrera 30 5,300 5,660 Miguel Delgado 29 8,500 3,412 Sushmita Mitra 27 11,000 2,455 Pierre Hansen 27 9,600 2,813 Bernard De Baets 27 8,750 3,086 Kwong-Sak Leung 27 5,625 4,800 Da Ruan 23 14,500 1,586 Gwo-Hshiung Tzeng 23 11,667 1,971 Xiaobo Li 22 9,333 2,357 Rudolf Kruse 21 11,000 1,909 Abraham Kandel 21 7,667 2,739 Mark Last 21 7,667 2,739 Gert De Cooman 21 6,800 3,088 Mustafa Demirci 21 6,250 3,360

rang naam 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

rang naam 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

Radko Mesiar Oscar Cordon Maria Petrou Sung-Kwun Oh Zhi-Qiang Liu A. K. Ray Shu-Cherng Fang Serafin Moral Dug Hun Hong Alberto Prieto Marek Reformat Paul D. Gader Ying-Ming Wang Daijin Kim Nehad N. Morsi Zhenyuan Wang Adnan Darwiche Miin-Shen Yang Ze-Nian Li Sanghamitra Bandyopadhyay Ming Li Peter Walley Zong-Ben Xu Hisao Ishibuchi C. H. Chen Frederick E. Petry Ujjwal Maulik Daniel G. Schwartz Man Leung Wong Nicholas R. Jennings

61

profielkardinaliteit hergebruik breedte 21 5,444 3,857 21 4,625 4,541 20 12,000 1,667 20 11,000 1,818 20 10,500 1,905 20 7,250 2,759 19 8,667 2,192 19 7,000 2,714 19 5,500 3,455 18 18,000 1,000 18 10,000 1,800 18 10,000 1,800 18 9,333 1,929 18 7,600 2,368 18 6,600 2,727 18 6,200 2,903 18 6,000 3,000 18 6,000 3,000 18 6,000 3,000 18 5,500 3,273 18 4,600 3,913 17 11,000 1,545 17 10,000 1,700 17 9,500 1,789 17 9,000 1,889 17 9,000 1,889 17 6,750 2,519 17 6,667 2,550 17 5,000 3,400 17 5,000 3,400

Tabel 5.2: Overzicht van enkele maten die de “rijkheid” van de profielen weergeven. De resultaten werden geordend volgens aflopende profielbreedte. Merk de variatie in de hergebruikfactor op. waarvoor de lidmaatschapsgraad groter dan nul is, m.a.w. de kardinaliteit van de drager van de vaagverzameling. Met deze waarden kunnen we ons een idee vormen van de “kwaliteit” of de “rijkheid” van het profiel. Een grote profielbreedte geeft aan dat het profiel over veel verschillende kernwoorden is uitgesmeerd. De kardinaliteit geeft ons een idee over de “sterkte” of “uitgesprokenheid” van het profiel, maar heeft alleen maar zin samen met de profielbreedte. Wanneer een auteur tien verschillende tags één keer gebruikt, dan heeft deze auteur een profielbreedte en kardinaliteit van 10. Wanneer hij echter één tag twee keer gebruikt, en acht andere één keer, dan heeft hij een profielbreedte van 9 en een kardinaliteit van 5. De tweede verdeling bevat echter evenveel informatie en spreekt zelfs de voorkeur voor de hergebruikte tag uit. Deze waarden moeten dus met de nodige omzichtigheid vergeleken worden. Het “hergebruik” definiëren we als de profielbreedte gedeeld door de kardinaliteit10 . Het hergebruik is ook een maat voor de “rijkheid” van het profiel omdat dit hergebruik van tags en dus een betere gradatie van de lidmaatschap van de verschillende tags beloont. In Tabel 5.2 worden deze waarden weergegeven voor een deel van de auteurs uit crawl2. Wanneer we de doorsnede van twee profielen nemen, bepalen we in feite wat die twee profielen gemeen hebben. We vergelijken het verwantschap van profielen aan de hand van de kardinaliteit van de doorsnede van die profielen. Hoe groter de doorsnede, hoe dichter twee profielen bij elkaar liggen. We kunnen om het even welke t-norm gebruiken om de doorsnede te bepalen, maar gezien de ijlheid van de data kozen we voor de grootste t-norm, m.a.w. het minimum. Merk op dat door het gebruik van t-normen de doorsnede geen kardinaliteit zal hebben die 10

Voor onderzoekers met een nulprofiel kan deze waarde niet berekend worden en definiëren we ze als nul.


62

groter dan de kardinaliteit van de profielen is. Met behulp van CalculateProfileDistance (zie Sectie D.5.6) kunnen de meest verwante auteurs berekend worden. Een selectie van de resultaten wordt gegeven in Figuur 5.3. We bepaalden telkens de tien beste resultaten. Zinloze resultaten (d.i. wanneer de kardinaliteit van de doorsnede gelijk aan nul is11 ) werden weggelaten. Dit is bijvoorbeeld het geval bij Wilfried Philips. In de linkerkolom geven we een overzicht van onderzoekers aan de Universiteit Gent, de rechterkolom geeft enkele andere interessante onderzoekers (die meestal goed scoorden in de sociale netwerkanalyse). Als we bijvoorbeeld de resultaten van Etienne Kerre vergelijken met zijn sociaal netwerk ve(zie Figuur 4.6), zien we dat de best overeenkomende onderzoekers de onderzoekers zijn waarmee Etienne Kerre reeds samenwerkte (en die dus buren in het sociaal netwerk zijn). Dit is wat we verwachtten aangezien die onderzoekers ook getagd zijn met de tags die afkomstig zijn van de gedeelde publicaties. Het verrassende is echter dat de auteurs in de tweede helft van de tabel12 aan Etienne Kerre gelinkt worden zonder dat er een sociaal verband bestaat.

5.4

Besluit

Hoewel de resultaten soms verrassend goed bijken te kloppen (getuige bijvoorbeeld de linkerkolom van Tabel 4.6, is er nog veel ruimte voor verbetering. We kunnen twee deelproblemen onderscheiden, nl. het verbeteren van de kwaliteit van het profiel en het beter aanwenden van de verschillende mogelijke operaties op vaagverzamelingen. Naarmate de kardinaliteit van de bestudeerde profielen groter wordt, lijkt de hierboven beschreven techniek betere resultaten te geven. De kardinaliteit van de doorsnede kan niet groter zijn dan de kardinaliteit van de profielen waar de doorsnede van genomen wordt. In dat opzicht kunnen we stellen dat “brede” profielen gemakkelijker aanleiding zullen geven tot een verwantschap. De vraag is of dit een gewenst fenomeen is of gecorrigeerd dient te worden: op deze manier kunnen onderzoeksprofielen ontstaan die algemeen (voor arbitraire profielen) aanleiding zullen geven tot een sterk verwantschap. Verrijking van het profiel We willen het profiel zo rijk mogelijk proberen te maken. Een zeer belangrijke vraag hierbij is wat een rijk profiel precies is. De profielbreedte en de kardinaliteit geven een indicatie, maar vertellen ons niet alles. We kunnen ook maten zoals het hergebruik of het aantal tags waaruit het profiel bestaat gebruiken. Een “grillig” profiel is te verkiezen boven een “vlak” profiel omdat het verschillende gradaties van interesse uitdrukt, zodat de “grilligheid” een interessante maat kan zijn. Verder onderzoek moet uitmaken wat geschikte metrieken zijn. Een relatief eenvoudige en logische manier om het profiel te verrijken, is het toevoegen van extra uitgevers die door de ProcessElectronicEdition taak herkend worden. Dit zal het aantal kernwoorden in het systeem vergroten. Dit vraagt wel relatief veel werk van de onderzoeker omdat de resterende uitgevers relatief klein zijn, en is in zekere zin niet zo portabel naar andere onderzoeksdomeinen (met andere uitgevers en webpagina’s). We kunnen ook de inhoud van de abstracts gebruiken. Bij het crawlen voor de kernwoorden downloaden we een pagina waar de meestal ook de abstract op staat. Het is dan ook een kleine moeite om de abstract hieruit te selecteren. Met behulp van de T F × IDF -techniek (zie Sectie 2.4.1) kunnen we hieruit voor elke publicatie extra kernwoorden destilleren. Een mogelijk 11

Dit komt voor wanneer er tussen de profielen geen overlap is. Deze kans ligt hoger bij ijlere profilen. Door de beperkte precisie ontstaat er bij het berekenen van de kardinaliteit een fout en zal de waarde niet altijd precies nul zijn. De grens werd daarom op 0,001 gelegd. 12 Isabelle Bloch, Leen Kuijken, Mamoru Shimoda, Przemyslaw Grzegorzewski en Adolfo R. de Soto


Etienne E. Kerre profielbreedte: 43

1 2 3 4 5 6 7 8 9 10

Glad Deschrijver Martine De Cock Da Ruan Mike Nachtegael Isabelle Bloch Anna Maria Radzikowska Leen Kuijken Mamoru Shimoda Przemyslaw Grzegorzewski Adolfo R. de Soto

kardinaliteit

9,833 2,583 2,333 2,333 2,167 2,083 2,000 1,667 1,667 1,667 1,500

Chris Cornelis

kardinaliteit

profielbreedte: 5

5,000 2,000 2,000 2,000 2,000 2,000 2,000 2,000 2,000 1,500 1,333

1 2 3 4 5 6 7 8 9 10

Ada Lettieri Birgit Koppen-Seliger Daniel Sanchez Giangiacomo Gerla Nara-Amparo Vila Paul Flondor Paul M. Frank Paul Magrez Lorenzo Moreno Irina Perfilieva

Martine De Cock profielbreedte: 7

1 2 3 4 5 6 7 8 9 10

Etienne E. Kerre Adolfo R. de Soto Daniel J. Fonseca Gerald M. Knapp Ulrich Bodenhofer Brigitte Werners Cat-Ho Nguyen Dionis Boixader Jordi Recasens Lois Wright Hawkes

Stefan Schulte profielbreedte: 3

1 2 3 4 5 6 7 8 9 10

Dietrich Van der Weken Mike Nachtegael Valerie De Witte Francisco Gallego Lupia nez K. C. Chattopadhyay Pao-Ta Yu Rastislav Lukac Tzu-Chao Lin U. K. Mukherjee Bogdan Smolka

Wilfried Philips profielbreedte: 1

1 2 3 4 5

Ignace Lemahieu Lawrence O. Hall Olivier Colliot Etienne E. Kerre Isabelle Bloch

kardinaliteit

4,500 2,333 2,000 2,000 2,000 2,000 1,500 1,500 1,500 1,500 1,500

63

Witold Pedrycz profielbreedte: 90

1 2 3 4 5 6 7 8 9 10

Sung-Kwun Oh Sankar K. Pal Sushmita Mitra Marek Reformat Nicolino J. Pizzi M. Narasimha Murty Ho-Sung Park Kaoru Hirota Nikhil R. Pal James C. Bezdek

Henri Prade profielbreedte: 35

1 2 3 4 5 6 7 8 9 10

Didier Dubois Eyke Hullermeier Tod S. Levitt Salem Benferhat Ronald R. Yager Peter Walley George J. Klir Prakash P. Shenoy Gert De Cooman Da Ruan

Didier Dubois profielbreedte: 36

1 2 3 4 5 6 7 8 9 10

Henri Prade Eyke Hullermeier Salem Benferhat Tod S. Levitt Ronald R. Yager Peter Walley Gert De Cooman George J. Klir David Harmanec Frederic Comby

kardinaliteit

17,364 5,182 3,974 3,636 3,545 3,364 3,055 2,932 2,782 2,606 2,606 kardinaliteit

11,500 9,400 3,000 2,500 2,417 2,417 2,250 2,000 2,000 1,800 1,750 kardinaliteit

9,600 9,400 2,600 2,267 2,200 2,167 2,100 1,800 1,800 1,600 1,600

kardinaliteit

Isabelle Bloch

kardinaliteit

3,000 3,000 3,000 3,000 1,000 1,000 1,000 1,000 1,000 1,000 0,667

profielbreedte: 41

9,000 2,750 2,083 2,023 1,875 1,875 1,750 1,583 1,500 1,500 1,375

kardinaliteit

1,000 1,000 1,000 0,500 0,167 0,125

1 2 3 4 5 6 7 8 9 10

Olivier Colliot Etienne E. Kerre Witold Pedrycz Sankar K. Pal Mike Nachtegael Da Ruan Ronald R. Yager Jose L. Verdegay Manish Sarkar Biagio Turchiano

Miguel Delgado profielbreedte: 29

1 2 3 4 5 6 7 8 9 10

Armando Blanco Marial del Carmen Pegalajar Jimenez

Antonio F. Gomez-Skarmeta Maria Amparo Vila Miranda Juan Luis Castro Henri Prade Thomas Sudkamp Witold Pedrycz Didier Dubois Alexandre Evsukoff

kardinaliteit

8,500 2,750 2,750 2,250 2,250 1,750 1,500 1,500 1,455 1,350 1,250

Tabel 5.3: Overzicht van op basis van profielinformatie verwante onderzoekers. Telkens werden enkel de tien beste resultaten weerhouden. De rangschikking wordt bekomen door het ordenen volgens de kardinaliteit van de doorsnede van de profielen. Bij een gelijke kardinaliteit worden de onderzoekers alfabetisch gerangschikt (op voornaam). De verschillende deeltabellen werden gerangschikt volgens de kardinaliteit van het profiel.


64

probleem is dat T F ×IDF woorden gaat selecteren die “uniek” voor de gegeven abstracts zijn en die dus weinig of niet hergebruikt worden. Extra criteria zoals een minimum globale frequentie kunnen hier een oplossing voor zijn. Het stemmingproces verbetert het profiel doordat het tags die triviaal hetzelfde betekenen gaat proberen samenvoegen. We stellen dan ook voor om voor elk woord in de abstract de stam te berekenen, en dan pas T F × IDF toe te passen. Door gebruik te maken van publicaties als bron van kernwoorden krijgen we de facto een correlatie tussen het sociaal netwerk en de profielen van de onderzoekers. De kernwoorden worden immers gedeeld door de verschillende co-auteurs van een publicatie. Het zou interessant zijn deze gegeven correlatie te proberen uit te schakelen door op zoek te gaan in informatiebronnen die uniek zijn voor elke auteur, zoals bijvoorbeeld de persoonlijke webpagina. Dit is echter een zeer complexe en moeilijke opdracht, maar stelt ons wel in staat om te bepalen hoe groot de invloed is van de door co-auteurschap gedeelde kernwoorden op het verwantschap tussen de profielen. Deze verschillende verbeteringen voegen vooral extra tags aan het systeem toe en brengen terug de rijkheid van de profielen in het gedrang, m.a.w. maken de profielen terug ijler. We moeten ook opletten voor schaalbaarheidsproblemen bij grote gemeenschappen. Het is dus wenselijk om de profielbreedte enigzins binnen de perken te houden. Met behulp van de algoritmes voor het bepalen van verwante tags in folksonomieën (zie Sectie 3.5.5) kunnen we verwante tags berekenen. Sterk verwante tags kunnen samengevoegd worden om de profielbreedte te verkleinen. Het is wenselijk dat we vooral weinig voorkomende en tegelijkertijd sterk verwante tags samenvoegen. Operaties op profielen Indien we rijkere profielen hebben, kunnen we onze resultaten proberen te verbeteren door het gedrag van de verschillende operaties uit de vaagverzamelingenleer te bestuderen. Voor de doorsnede van profielen kunnen we ook andere t-normen gebruiken, zoals het product of de Lukasiewicz t-norm. Hoe we de “grootte” van die doorsnede bepalen heeft een invloed. We kunnen hiervoor bijvoorbeeld ook de hierboven gevraagde maat voor de rijkheid van het profiel gebruiken. We kunnen ook het verwantschap zien als een soort van afstand (in een n-dimensionele ruimte) en dit soort metrieken gebruiken. Onderzoek moet uitwijzen welke de beste resultaten geven. Ook unies of andere operaties behoren tot de mogelijkheden. Merk op dat we hierboven enkel “de meest verwante” onderzoekers bepaald hebben. We zouden ons echter ook kunnen afvragen welke profielen goed vergelijkbaar zijn, en welke niet. Door het gebruik van de kardinaliteit van de doorsnede kunnen we het berekende verwantschap enkel vergelijken met waarden die vertrekkende van hetzelfde profiel berekend werden. Er is dus nood aan een similariteitsmaat die twee profielen vergelijkt waarmee we de globaal gezien sterk gelijkende profielen kunnen identificeren.

Hoofdstuk 6

Besluit Sociale netwerkanalyse werd in het verleden succesvol gebruikt om sleutelfiguren in gemeenschappen te bepalen. Door de enorme hoeveelheid aan elektronische informatie en diensten is het nu ook mogelijk om zelf virtuele netwerken te bouwen en die te analyseren. In deze scriptie concentreerden we ons op de “Fuzzy Sets and Systems” onderzoeksgemeenschap. Op basis van co-auteursrelaties die we ontdekten op wetenschappelijke publicaties creëerden we een netwerk dat de “Fuzzy Sets and Systems” gemeenschap modelleert. Daarna breidden we deze analyse uit met onderzoekersprofielen. Zo’n “inhoudelijk” profiel werd opgesteld aan de hand van de kernwoorden die vermeld staan op de wetenschappelijke publicaties. Dit stelde ons ondermeer in staat om centrale figuren en verwante onderzoekers te bepalen. Co-auteursnetwerken In Hoofdstuk 4 bestudeerden we het sociaal netwerk dat gevormd wordt door co-auteursrelaties. Belangrijke egogebaseerde maten voor sociale netwerkanalyse zijn de graadcentraliteit, de spilcentraliteit, de nabijheid en de clusteringcoëfficiënt. We vonden dat de graad verwant is met de verschillende componentgroottes en de meeste onderzoekers een graad tussen één en vijf hebben. We berekenden de clusteringcoëfficiënt en vonden een correlatie tussen de graden en de clusteringcoëfficiënten. We stelden met behulp van klassieke centraliteitsmaten een rangschikking op die een weerspiegeling blijkt te zijn van de reële verwantschappen (zie Tabel 4.3). Door het introduceren van gerichte bogen en gewichten kon de analyse uitgebreid worden door gebruik te maken van maten zoals HITS of PageRank. We stelden voor elke maat een rangschikking op (zie Tabel 4.5) en de resultaten zijn in zekere zin vergelijkbaar met die reeds bekomen in de klassieke analyse. PageRank geeft wellicht de meest realistische resultaten omdat deze ook het relatief belang van de omgeving in de berekening meeneemt. Door de structuur van het netwerk aan te passen, kunnen we de resultaten van HITS iets verfijnen. Belangrijke autoriteiten krijgen een meer uitgesproken waarde. Uiteraard zijn ook de kwaliteit of het aantal citaties van de wetenschappelijke publicaties belangrijke karakteristieken om sleutelfiguren te bepalen, maar de analyse die alleen maar van het co-auteursnetwerk gebruik maakt blijkt al goede resultaten te geven. Uit de analyse komen enkele factoren naar voor die een positieve invloed hebben op de rangschikking van een onderzoeker. Het met veel verschillende onderzoekers in contact komen heeft een directe invloed op de graadcentraliteit. Een evidente factor is dus het met veel andere onderzoekers samen publiceren. Daarnaast is het belangrijk om zo veel mogelijk als een “bruggenbouwer” op te treden, m.a.w. zo veel mogelijk (deel)domeinen met elkaar in contact te brengen. Dit heeft een directe invloed op de spilcentraliteit van de onderzoeker, en zal ook een positieve invloed hebben op de nabijheid. Dit effect is sterker wanneer er een brug gebouwd

65

HOOFDSTUK 6. BESLUIT

66

wordt tussen voorheen niet in contact gekomen deelgroepen. Een derde factor is samenwerking met onderzoekers die reeds een “goede positie” in het netwerk hebben. In de gerichte, gewogen analyse zal hun hoge rangschikking een positieve invloed hebben op de rangschikking van de onderzoeker. Met een vergelijkbare argumentatie zullen trouwe medewerkers (bv. doctoraatsstudenten) een positieve invloed hebben: naarmate deze zelfstandiger worden, zullen ze hun positie in het netwerk verbeteren en zal de onderzoeker terug van hun (groeiende) positie kunnen meeprofiteren. Profielnetwerken In Hoofdstuk 5 bestudeerden we hoe we profielinformatie kunnen toevoegen. Deze profielinformatie stelden we op twee manieren voor: eerst, ge¨ınspireerd door folksonomieën, als een netwerk, en daarna als een vaagverzameling. De netwerkgebaseerde modellering helpt ons om de informatie te bundelen en kan ons reeds wat informatie over het gebruik van de tags (kernwoorden) geven. Uit deze voorstelling kunnen we een nieuwe modellering met behulp van vaagverzamelingen afleiden: een profiel wordt dan voorgesteld als een vaagverzameling over het universum van alle mogelijke tags. Het vinden van verwante profielen gebeurt dan door de (vage) doorsnede van twee profielen te nemen en de grootte (kardinaliteit) van de doorsnede te gebruiken als een maat voor verwantschap. Omdat de kernwoorden op de publicaties van co-auteurs dezelfde zijn, verwachtten we dat verwante profielen alleen maar voorkomen bij coauteurs. Verrassend genoeg is dit niet zo en vindt deze techniek ook onderzoekers die alleen maar een inhoudelijk verwantschap hebben. Hoewel de dataset relatief ijl blijkt te zijn, konden we tonen dat de voorgestelde techniek om de meest verwante onderzoekers te berekenen reeds werkt. Het gebruik van de vaagverzamelingenleer geeft ons nuttige tools die het mogelijk maken om op verschillende manieren verwantschappen tussen profielen te definiëren en verschillende operaties op de profielen uit te voeren. We gaven een uitgebreid overzicht van mogelijk toekomstig werk. Het belangrijkste is te starten met uitbreiden van de dataset, en vanaf dan kan onderzoek (gegrond) uitwijzen welke operaties op vaagverzamelingen het interessantst zijn om te gebruiken. Toekomstig werk Zowel in Hoofdstuk 4 als in Hoofdstuk 5 werd reeds aangegeven welke onderzoekspaden in de toekomst verder onderzocht kunnen worden. In deze sectie geven we enkele algemene beschouwingen die voor beide hoofdstukken van nut zijn. We kunnen dit werk in twee componenten splitsen, namelijk het uitbreiden van de dataset en het verbeteren van de analyse. Belangrijk (maar tijdsintensief) werk is het toevoegen van extra informatiebronnen. Naast DBLP zijn er nog andere citatiedatabanken, deze kunnen de onvolledigheid van DBLP wegwerken. Op deze manier zullen we nieuwe co-auteursrelaties ontdekken waardoor het netwerk beter verbonden zal worden. Het toevoegen van nieuwe informatiebronnen is nog meer van belang voor de onderzoekersprofielen die op dit moment zeer ijl blijken te zijn. Hier bestaat het werk erin om extra websites te crawlen (m.a.w. het toevoegen van extra uitgevers), en meer informatie uit elke pagina te halen (m.a.w. het selecteren van kernwoorden uit de abstracts of zelfs uit de volledige publicaties). Na het uitbreiden van de dataset zullen de resultaten van beide analyses sterker verfijnd worden en resultaten geven die dichter bij de echte wereld gaan aanleunen. Vanaf dan wordt het interessant om het co-auteursnetwerk te vergelijken met de verwante profielen. Onze techniek vond reeds inhoudelijk verwantschap bij onderzoekers die niet met elkaar samen publiceerden. In hoeverre is het co-auteursnetwerk verwant met de onderzoekersprofielen? Zullen onderzoekers die sterk verwante profielen hebben ook met elkaar samenwerken? In welke mate zijn de profielen van co-auteurs gecorreleerd aan elkaar? De vergelijking van het sociaal netwerk met

HOOFDSTUK 6. BESLUIT

67

de onderzoekersprofielen zal ons een idee geven van de “efficiëntie” van het onderzoeksdomein: wanneer er namelijk verschillende ge¨ısoleerde “eilandjes” van onderzoekers uit hetzelfde deeldomein bestaan, kan er energie verloren gaan door parallel aan hetzelfde probleem te werken. De efficiëntie kan dan eventueel verbeterd worden door verwante onderzoekers met elkaar in contact te brengen. Een uitbreiding op de gevoerde analyse is het bepalen van de invloed van de tijd. Naarmate tijd voorbij strijkt, zullen nieuwe onderzoekers op de voorgrond treden en zullen andere in invloed dalen. De onderzoeksdomeinen van de individuele onderzoekers en de “globale onderzoeksinteresse” zal evolueren naarmate de discipline zich ontwikkelt. Het in rekening brengen van tijd kan gebeuren door een filtering op de dataset uit te voeren en deze filtering iteratief aan te passen. We kunnen werken met een glijdend venster of het cumulatief toevoegen van extra “tijdsframes”. Zowel de onderzoekers in het co-auteursnetwerk als de onderzoekersprofielen kunnen we indelen in klassen. In het gericht, gewogen co-auteursnetwerk zal een ervaren onderzoeker (promotor) veel inkomende bogen met een hoog gewicht en veel uitgaande bogen met een laag gewicht hebben. Met behulp van vaagregelgebaseerde systemen kunnen we onderzoekers classificeren aan de hand van de vorm van het netwerk in hun buurt. Mogelijke klassen zijn dan bijvoorbeeld “beginnende onderzoeker”, “doctorandus”, “zelfstandige onderzoeker” en “ervaren onderzoeker”. Analoog kunnen we ook klassen van verwante profielen (m.a.w. onderzoeksdomeinen) bepalen. Een voorstel is om aan de hand van een similariteitsmaat de verzameling van alle onderzoekersprofielen te clusteren. We nemen dan telkens de twee meest verwante onderzoekersprofielen samen tot we een bevredigend aantal componenten hebben. Twee profielen kunnen samengenomen worden door bijvoorbeeld gebruik te maken van t-conormen uit de vaagverzamelingenleer.

Deel III

Appendices: technisch

68

Bijlage A

Het Semantisch Web Verwant met Web 2.0, en soms reeds het Web 3.0 genoemd, is het Semantisch Web [40]. In tegenstelling tot Web 2.0, waar de verbetering van de technologie niet een bepalende factor is, kan men het Semantisch Web zien als een “major upgrade” van de achterliggende technlogie. Het Semantisch Web werd door Berners-Lee voorgesteld als een een uitbreiding op het huidig Web die het machines (i.p.v. mensen) in staat moet stellen om de informatie op het Web te verwerken. In Berners-Lee’s visie wordt het Web dan een universeel medium voor data, informatie en uitwisseling van kennis. Het doel van het Semantisch Web is het in staat stellen van intelligente agents om informatie op het Web op een betekenisvolle manier te verwerken. In tegenstelling tot het traditioneel Web, dat een web van links is, is het Semantisch Web een web van data. De potentiële mogelijkheden zijn enorm. Het kan ons bijvoorbeeld toelaten om meer specifieke zoekmethodes te ontwikkelen die verder gaan dan enkel op kernwoorden zoeken (bv. “geef alle bekende schrijvers geboren tussen 1930 en 1980”). Het Semantisch Web laat toe om op een automatische manier nieuwe feiten uit een combinatie van informatie van verschillende bronnen af te leiden en de gebruiker bij te staan in het omgaan met de grote hoeveelheid informatie op het Web. Het Web wordt dan door de agents gebruikt als een grote “knowledge base”.

A.1

Bouwstenen voor het Semantisch Web

Het Semantisch Web is een web, m.a.w. gedistribueerd van aard. Data is verspreid over verschillende locaties en door middel van links wordt naar data op andere locaties verwezen. Om in staat te zijn om vrij informatie te delen en te hergebruiken, moeten we dezelfde taal spreken: een gestandardiseerde ontologietaal is de sleutel om de informatie van arbitraire bronnen te hergebruiken. Omdat we niet met een gesloten systeem te maken hebben (“closed world assumption”), moeten we evenwel een zekere flexibiliteit voorzien door het toelaten van ontbrekende, onvolledige of zelfs inconsistente informatie. De semantische data wordt vastgelegd aan de hand van ontologieën. Een ontologie is een formele, expliciete conceptualisatie van een domein. Formeel omdat het machine verwerkbaar moet zijn en expliciet omdat de concepten en hoe ze te gebruiken expliciet gedefinieerd zijn. Het specificeert de verschillende klassen van objecten die bestaan, de relaties tussen deze klassen, de mogelijke relaties tussen instanties van die klassen en voorwaarden bij die instanties. RDF (Resource Description Framework) [41], een W3C Recommendation, is een eenvoudige taal om computerbegrijpbare vocabularia te definiëren die zowel personen als programma’s kunnen gebruiken om dingen — gaande van webpagina’s, krantenartikels en e-mailberichten tot mensen en gebeurtenissen — te beschrijven. Het is een datamodel om metadata voor te stellen en om de

69

BIJLAGE A. HET SEMANTISCH WEB

70

semantiek van informatie op een machine toegankelijke manier te beschrijven. RDF statements beschrijven de eigenschappen van bronnen (Eng. resources), waarbij een bron elk mogelijk object is waarnaar verwezen kan worden met een URI (Uniform Resource Identifier)1 . Elk statement bevat drie componenten: het onderwerp (Eng. subject), het predikaat (Eng. predicate) en het object. RDF Schema (RDFS) RDF Schema [42] breidt RDF uit door het geven van een vocabularium om logische, objectgeoriënteerde schema’s, met een eenvoudig typesysteem, subklasses, subeigenschappen en overerving te ontwikkelen. Aan bepaalde RDF predicaten wordt een extra betekenis gehecht: de semantiek of hoe die bepaalde term zou moeten ge¨ınterpreteerd worden. De Web Ontology Language (OWL) ondersteunt meer geavanceerde mogelijkheden zoals logische inferentie en mapping tussen verschillende ontologieën. RDFS en OWL worden soms “metaontologietalen” genoemd. Friend-of-a-Friend (FOAF) Het FOAF (Friend-of-a-friend) vocabularium [43] bevat klassen en eigenschappen nuttig om personen te beschrijven. Het FOAF vocubularium is eenvoudig in gebruik en gemakkelijk uitbreidbaar, wat het geschikt maakt voor een breede waaier van toepassingen. Instanties van de klasse foaf:Person modelleren personen en met eigenschappen zoals foaf:name, foaf:interests, foaf:mbox kan informatie over die personen toegevoegd worden. Met behulp van de eigenschap foaf:knows kunnen eenvoudige sociale netwerken ontwikkeld worden door het linken van instanties van foaf:Person. Het publiek beschikbaar zijn van persoonlijke informatie kan leiden tot privacyproblemen. Een interessante eigenschap is foaf:mbox_sha1sum die de SHA1-hashwaarde van een e-mailadres weergeeft. Aan de hand van deze hash wordt het e-mailadres beschermd voor de buitenwereld, maar kan iemand die het kent het gebruiken om de persoon te identificeren. DC De Dublic Core Element Set (DC) [44] is een vocabularium om metadata voor een breed gamma van objecten te beschrijven. Het woord Core in de naam verwijst naar het feit dat de verzameling termen een fundamentele maar uitbreidbare lijst is. DC kan gebruikt worden bij het beschrijven van verschillende media zoals video, geluid, foto’s, tekstdocumenten en webpagina’s. SWRC Het voorstellen van kennis over onderzoekers, onderzoeksgemeenschappen, hun publicaties en activiteiten, en hun onderzoeksinteresses is een typisch gebruikscenario voor gedistribueerd en lokaal onderhouden, gelinkt en sterk gestructureerde informatie in de geest van het Sematisch Web. De SWRC ontologie (naam afkomstig van “Semantic Web Research Community Ontology”) modelleert op een generieke manier kernconcepten in een typische onderzoeksgemeenschap [45]. Het SWRC vocabularium bestaat uit zes basisconcepten, namelijk Person, Publication, Event, Organization, Topic en Project. De klasse Person modelleert een menselijk persoon en wordt ingedeeld in een aantal deelconcepten zoals student of werknemer. Een Event modelleert gebeurtenissen zoals lezingen of conferenties. De concepten Organization en Project modelleren meer abstracte begrippen zoals bijvoorbeeld vakgroep of departement. Het begrip Topic modelleert arbitraire onderzoeksonderwerpen, die onderling geordend kunnen worden met behulp van de subTopic relatie. 1 Eenvoudig gesteld zou men een URI kunnen zien als een veralgemening van het begrip URL. Met URL’s kunnen webpagina’s up een uniforme en unieke manier geadresseerd worden. Er bestaan echter ook andere schema’s die bepaalde objecten uniek kunnen identificeren: een bekend voorbeeld zijn de ISBN codes van boeken. Een ISBN code identificeert op een ondubbelzinnige manier een boek en kunnen we dus zien als een URI. Ook URL’s zijn URI’s.

BIJLAGE A. HET SEMANTISCH WEB

A.2

71

Sesame RDF Repository

Sesame2 [46] is een “databank” waarin men RDF triples kan opslaan en opvragen. De RDF statements worden bewaard in een zogenaamde “repository”. Sesame is volledig in java geschreven en kan zowel lokaal of als server (met behulp van Apache Tomcat) gebruikt worden. Met querytalen zoals SeQRL of SPARQL kunnen individuele statements tot zelfs volledige deelgrafen opgevraagd worden. Sesame wordt in deze scriptie gebruikt als databank waarin de data na het crawlen wordt opgeslagen. We gebruiken het SWRC vocabularium om wetenschappelijke publicaties en hun auteurs te beschrijven (er worden voor de auteurs ook extra FOAF termen toegevoegd).

2

http://www.openrdf.org (bezocht op 18 mei 2007)

Bijlage B

CookieMonster voor eindgebruikers CookieMonster is een applicatie om verschillende taken na elkaar uit te voeren. Deze taken worden in een lijst geordend en kunnen (indien relevant) elk individueel geconfigureerd worden. CookieMonster zorgt voor het beheer van deze taken en maakt het mogelijk om deze als een batch sequentieel uit te voeren. Takenlijsten (met de bijhorende configuraties) kunnen bewaard worden. Dit maakt het mogelijk om resultaten te herhalen. Deze appendix beschrijft het gebruik van CookieMonster voor eindgebruikers. Eerst worden de algemene ideeën uitgelegd, daarna het gebruik en verder wordt ingegaan op het implementeren van eigen taken. Voor een gedetailleerde bespreking van de implementatie verwijzen we naar appendix C. Extra uitleg over de reeds ge¨ımplementeerde taken is te vinden in appendix D. Appendices C en D zijn niet essentieel om CookieMonster te kunnen gebruiken.

B.1

Werkomgeving

De uitvoering van taken heeft pas zin als dit gebeurt in een bepaalde context. Deze context wordt bepaald door de objecten waarop de takenlijst inwerkt. Al die objecten worden opgeslagen in de Objectstore, een structuur die objecten beheert. Elk object heeft zijn eigen naam (sleutel) waarmee het object opgevraagd kan worden. Een overzicht wordt weergegeven in Figuur B.1. Elke taak beschikt over zijn eigen configuratie. Elke configuratie bestaat uit sleutel/waardeparen die vrij door de gebruiker ingevuld kunnen worden. Hoewel het in de praktijk weinig voorkomt, is het mogelijk dat een taak geen configuratie sleutel/waarde-paren gebruikt. CookieMonster legt hier geen beperkingen op. Bij het uitvoeren van de takenlijst worden de taken één voor één uitgevoerd in de opgegeven volgorde. Zeer belangrijk hierbij is de interactie met de context die in Figuur B.1 door de dubbele pijl wordt weergegeven. Elke taak kan objecten in de Objecstore creëren of manipuleren. Bij het starten van een nieuwe takenlijst is de Objectstore leeg. Typisch zullen er dus eerst taken die objecten in de Objectstore initialiseren, worden uitgevoerd, en later taken die deze objecten manipuleren. De toestand van de context wordt niet bewaard bij het bewaren van de takenlijst; bij het openen van een werkomgeving vertrekken we terug van een lege context. De context wordt wel niet gewist bij het heruitvoeren van een takenlijst om het stap-na-stap uitvoeren van losstaande taken mogelijk te maken. Merk op dat het mogelijk is om verschillende, van elkaar afgeschermde werkomgevingen simultaan te gebruiken. Elke werkomgeving heeft zijn eigen takenlijst en zijn eigen context. Deze contexten zijn strikt gescheiden (ook bij het gebruik van dezelfde sleutelwaarde in de Objectstore) en de uitvoering van deze takenlijsten gebeurt volledig onafhankelijk.

72

BIJLAGE B. COOKIEMONSTER VOOR EINDGEBRUIKERS

73

CookieMonster Workspace

Workspace

TaskList

Workspace CookieContext

Task 1

CookieConfiguration

Task 2

CookieConfiguration

Task 3

CookieConfiguration

Task 4

CookieConfiguration

Objectstore sleutel

ref

stdrep tmpfile graph

...

...

JUNG (Java Universal Network/Graph Framework)

Figuur B.1: Conceptueel overzicht van CookieMonster

B.2

Gebruik

Na het opstarten van CookieMonster starten wordt een leeg venster weergegeven. Met behulp van het menu Workspace kunnen we een lege of een bewaarde werkomgeving openen. In Figuur B.2 werd een nieuwe, lege werkomgeving gestart. Het venster van de werkomgeving bevat twee delen: bovenaan een veld waar een omschrijving kan worden ingevoerd en onderaan een gebied waarop de takenlijst wordt afgebeeld. Het staat de gebruiker vrij een omschrijving in te voeren. Deze omschrijving is er enkel voor de duidelijkheid; CookieMonster legt geen vereisten omtrent het gebruik op. De gebruiker kan de takenlijst vullen aan de hand van het menu Task. Dit wordt weergegeven in Figuur B.3. Taken worden telkens onderaan de lijst toegevoegd. De volgorde van de taken kan veranderd worden door gebruik te maken van het menu Task of (na het selecteren van de taak) van de toetsencombinaties + of +. Na het selecteren van de betreffende taak, kan deze geconfigureerd worden door menu Task, Config Selected... te kiezen of de F2-toets te drukken. Het uitvoeren van de takenlijst gebeurt door menu Run, Execute te kiezen of + te drukken. Bij uitvoering van de takenlijst krijgt de actieve taak een tandwiel pictogram. Na afwerking wordt het pictogram vervangen door een groen vinkje. Voor de beschrijving van de specifieke uitvoering en eigenschappen van de verschillende ge¨ımplementeerde taken verwijzen we naar appendix D. Taken staan zelf in voor het vangen van hun eigen Exceptions; bij het optreden van een fout zal een taak onmiddellijk eindigen en CookieMonster overgaan naar de volgende taak. Het menu Extra bevat enkele extra functies. Informatie over de objecten in de Objectstore kan verkregen worden met behulp van de functie Show Objectstore..., die de sleutels en types van de objecten aanwezig in de Objectstore toont. Deze informatie kan op elk moment


74

Figuur B.2: Een nieuwe, lege werkomgeving. Dit is het venster dat in het containervenster vervat zit. Bovenaan zien we het veld voor de beschrijving, daaronder de (op dit moment lege) takenlijst.

Figuur B.3: Creatie van een nieuwe taak. In de drop-down lijst worden de mogelijke taken getoond. Op de achtergrond is te zien dat er reeds enkele taken toegevoegd en geconfigureerd werden.


75

opgevraagd worden, zelfs als de takenlijst in uitvoering is. Met View graph... kunnen grafen in de Objectstore gevisualiseerd worden. Een tekstuele voorstelling van de takenlijst zoals in appendix E wordt verkregen met Output tasklist.

B.3

Ontwikkeling van eigen taken

Taken dienen ge¨ımplementeerd te worden als een uitbreiding van de interface Task. De interface Task wordt als als een implementatie van Runnable en Serializable gedefinieerd. Het “echte” werk van de Taak wordt in de methode public void run() ge¨ımplementeerd. De klasse is serialiseerbaar zodat de taak eenvoudig kan worden opgeslagen. Voor een bespreking van de verschillende methodes in de interface Task verwijzen we naar appendix C. De ontwikkelde taken moeten in de package cookiemonster.tasks geplaatst worden. Om het de ontwikkelaar eenvoudiger te maken, werd een AbstractTask ge¨ımplementeerd die een groot aantal methodes reeds implementeert met een default implementatie. Er wordt een abstracte methode public void doTask() gedeclareerd die de gebruiker moet implementeren met het specifieke werk van de taak. Bij het uitvoeren van de taak wordt er automatisch gecontroleerd of er een context werd ingesteld. AbstractTask zal automatisch de running toestand aanpassen en de afhankelijke klassen (listeners) hiervan op de hoogte brengen. Er mogen geen Exceptions gegooid worden. Wanneer een fout optreedt is het raadzaam dat de gebruiker deze afdrukt op System.err en de taak op een normale manier laat eindigen. Verder moet de gebruiker ook nog de methode public String toString() implementeren. De waarde die deze methode teruggeeft, wordt door de GUI gebruikt als de naam van de taak. Tijdens de uitvoering krijgt de gebruiker via het veld context toegang tot de context. Objecten kunnen uit de Objectstore opgevraagd worden met de methode public T getObject(String key,Class type). Het attribuut key is hierbij de sleutel van het object en type stelt de klasse van het object voor. Het Class-object kan verkregen worden gebruik te maken van de class literal1 . Op deze manier moet de gebruiker zelf geen cast-operatie meer doen2 . Met public Set<String> getKeySet() kan de verzameling van alle gebruikte sleutels opgevraagd worden. Met public void putObject(String key,Object o) kan er een object worden toegevoegd. Tijdens de constructie van de taak kan de ontwikkelaar configuratie-attributen creëren met behulp van putConfigurationEntry(String key, String value, String help). Hierbij is key de sleutelwaarde waarmee de waarde van het configuratie-attribuut opgevraagd kan worden, value een standaardaarde, en help de helpregel die weergegeven wordt in het configuratievenster. Tijdens de uitvoering kan via het config veld het configuratieobject worden opgevraagd. Met methoden zoals public int getAsInteger(String key) en public String get(String key) kunnen de configuratie-attributen tijdens de uitvoering opgevraagd worden.

1

Voor meer informatie verwijzen we de lezer naar de Java API (http://java.sun.com/j2se/1.5.0/docs/api/ java/lang/Class.html) 2 Hij moet uiteraard wel weten tot welk type het object behoort. Wanneer er een verkeerd type wordt opgegeven, zal er een ClassCastException gegenereerd worden.

Bijlage C

CookieMonster onder de motorkap Samengevat is CookieMonster een applicatie om verschillende taken sequentieel uit te voeren. CookieMonster werd reeds ge¨ıntroduceerd in appendix B. Dit hoofdstuk bouwt hierop verder en bespreekt de implementatie en technische details van het programma. Uitleg over de werking van de verschillende taken is te vinden in appendix D.

C.1

Situering

We ontworpen CookieMonster omdat we behoefte hadden aan een applicatie om op eenvoudige, generieke wijze verschillende taken na elkaar uit te voeren. Het moest gemakkelijk zijn om een lijst van taken op te stellen en uit te voeren. Het moest ook mogelijk zijn om resultaten te herhalen, en hiervoor moesten de taken (en hun specifieke configuratie) bewaard kunnen worden. Tenslotte moest het eenvoudig zijn nieuwe taken te programmeren. Vanwaar de naam CookieMonster? We waren reeds gestart met een prototype dat Sesame (zie Sectie A.2) en Elmo1 gebruikte. Hierin werden reeds primitieve varianten van de concepten taak en takenlijst gebruikt. Takenlijsten waren hardgecodeerd. We beslisten dit ontwerp te veralgemenen en te voorzien van een GUI. Werkomgevingen en takenlijsten moesten in de GUI opgesteld en bewaard kunnen worden. In lijn met de reeds gebruikte technologieën beslisten we het resultaat CookieMonster te noemen2 .

C.2

Ontwerp

Het centrale concept in CookieMonster is het concept taak. Een taak doet een concreet “werk”. Taken kunnen arbitrair in een lijst geordend worden en uitgevoerd worden. Voor de implementatie gebruikten we het command design pattern3 . Hierbij wordt een actie (in dit geval een taak) samen met zijn parameters in een object ingekapseld. Deze objecten kunnen nu in een lijst geordend worden of op andere manieren gemanipuleerd worden. Het programma kan de actie uitvoeren door een welbepaalde methode op het object op te roepen. 1

http://www.openrdf.org (bezocht op 18 mei 2007) Men zou kunnen stellen dat deze applicatie — net zoals bij het echte Cookiemonster uit Sesamstraat — alle taken sequentieel en gulzig “consumeert”. De initiële implementatie startte trouwens rond de verjaardag van het Cookiemonster, nl. 2 november. 3 Een design pattern is een architecturaal patroon dat gebruikt wordt in de softwareontwikkeling. Het is in feite een naam voor de “generieke structuur” van de oplossing van bepaalde typische softwareontwikkelingsproblemen. Andere voorbeelden zijn het observer/observable design pattern of het model-view-controller pattern. 2

76

BIJLAGE C. COOKIEMONSTER ONDER DE MOTORKAP

77

De interface Task definieert de abstracte voorstelling van een taak. Elke Task is onafhankelijk te configureren, hiervoor stelden we de interface CookieConfiguration op. In feite is een CookieConfiguration een Map van sleutel/waarde-paren. Een taak werkt natuurlijk in op een context. Deze context wordt voorgesteld door de CookieContext interface. Deze interface biedt via een sleutel toegang tot objecten . De Sesame Repository waar standaard op wordt gewerkt, krijgt bijvoorbeeld bij conventie de naam stdrep. Deze concepten worden gebundeld in een Workspace. Een Workspace bevat een TaskList en een CookieContext (in feite is het zelf die context). Workspaces werken volledig onafhankelijk van elkaar: elke werkomgeving heeft zijn eigen takenlijst en context. Er is geen communicatie tussen de contexten van verschillende werkomgevingen. Dit stelt CookieMonster in staat om verschillende takenlijsten parallel uit te voeren.

C.3

Implementatie

De applicatie (met GUI) werd ge¨ımplementeerd aan de hand van het model-view-controller (MVC) design pattern. In dit design pattern worden er drie concepten onderscheiden: het model, de view en de controller. Hoewel MVC ook nog in andere contexten gebruikt kan worden, wordt het vaak gebruikt bij het ontwikkelen van GUI applicaties. De view en de controller zijn dan componenten van de GUI, terwijl het model de inwendige voorstelling van de data in het programma is. De view is een (grafische) voorstelling van de inwendige toestand van het model. Wanneer het model van toestand verandert, zal de view zich automatisch aanpassen. Hiervoor zal het zich als een luisteraar bij het model registreren (cfr. het observer/observable design pattern). Het zijn enkel de controllercomponenten die het model zullen aanpassen. Een typisch voorbeeld hiervan is de gebruiker die op een knop klikt. De knop is hier de controller die bij het aanklikken een bepaalde wijziging op het model zal teweegbrengen. De view wordt automatisch aangepast als gevolg van het wijzigen van het model. Merk op dat de scheiding tussen view en controller soms zeer arbitrair is; sommige GUI-componenten kunnen tegelijkertijd view en controller zijn (bv. een checkbox).

C.3.1

Het model

In de package cookiemonster.model vinden we de basisklassen die het model uitmaken. CookieModel Deze klasse is de meest algemene voorstelling van het model; het bundelt de verschillende Workspaces en laat toe om Workspaces te creëren of te verwijderen. Deze klasse houdt ook (een Map van) Actions bij. Deze wordt gevuld en gebruikt door de GUI. Op deze manier wordt er voor gezorgd dat er voor elke GUI handeling maar één uniek Action object wordt bijgehouden (zie C.3.4). Klassen kunnen zich registreren bij deze klasse als een WorkspaceListener. Ze worden dan op op de hoogte gebracht wanneer er een Workspace wordt toegevoegd of verwijderd. Wijzigingen in de Workspace zelf worden genegeerd.


78

Workspace Een Workspace bevat een TaskList en kan bewaard/geladen worden door serialization4 . Hiervoor implementeert Workspace (en alle objecten die het bevat) de interface Serializable. De Workspace is zelf de context, daarom implementeert het de interface CookieContext. CookieContext De context wordt als volgt gedefinieerd: public interface CookieContext { public T getObject(String key, Class type); public void putObject(String key, Object o); public Set<String> getKeySet(); } De Objectstore wordt ge¨ımplementeerd als een Map. De werking van deze methodes is voor de hand liggend. Het tweede argument van de eerste methode zorgt voor een automatische cast. Op deze manier moet de taakontwikkelaar zelf geen cast meer doen. (Zie Sectie B.3.)

C.3.2

Het model voor taken

De package cookiemonster.model.task bevat de interfaces/klassen die abstracte taken voorstellen. De effectieve implementaties (door de gebruiker) horen in de package cookiemonster.tasks. Hier bespreken we enkel de interfaces/klassen die deel uit maken van het model. Meer uitleg over implementaties is te vinden in appendix D. Task De interface Task wordt als als een uitbreiding van Runnable en Serializable gedefinieerd. Het “echte” werk van de taak wordt in de methode public void run() ge¨ımplementeerd. De klasse is serialiseerbaar zodat de taak eenvoudig kan opgeslagen worden. We vinden de volgende methodes terug: • public void setContext(CookieContext context); Vooraleer een Task wordt uitgevoerd zal de context waarop de taak moet inwerken ingesteld worden. Over het tijdstip wanneer dit gebeurt, wordt niets gespecificeerd; dit kan vlak na constructie of vlak voor het oproepen van run() zijn. Die methode zal uiteraard wel moeten controleren of dit gebeurd is. Het instellen gebeurt niet bij constructie omdat dit de taak afhankelijk maakt van één bepaalde context (en dus minder goed “inwisselbaar” maakt). Dit maakt de serialisatie trouwens ook gemakkelijker. • public CookieConfiguration getConfiguration(); public Map<String,String> getConfigurationHelp(); 4

Informeel zouden we kunnen stellen dat serializatie “het bewaren van Java objecten” is. Meer specifiek is serializatie een proces waarbij de toestand van Java objecten omgezet wordt naar een bytestroom. Aan de hand van deze bytestroom kan het object later gereconstrueerd worden. Serializatie kan bijvoorbeeld gebruikt worden voor communicatie via sockets of persistentie (op schijf) van objecten. Een object is serialiseerbaar als het de Serializable interface implementeert. Voor verdere uitleg verwijzen we naar [47].


79

Deze methodes behandelen de configuratie van de taak. De laatste methode vraagt wat extra uitleg: om een Task in te kunnen stellen is extra informatie nodig over de in te stellen parameters en hun betekenis. Deze worden door de Task in een Map opgeslagen als sleutel/beschrijving-paren. De beschrijving is dus bedoeld voor gebruikers en wordt afgebeeld in de GUI. • public void addTaskListener(TaskChangeListener w); public boolean removeTaskListener(TaskChangeListener w); Deze methodes verzorgen de observer/observable structuur voor taken. Elke TaskListener wordt op de hoogte gebracht als de toestand van de taak verandert, bv. als deze running wordt (met andere woorden, als hij uitgevoerd wordt). • public boolean isRunning(); public String toString(); De eerste methode geeft aan of de taak op dit moment aan het uitvoeren is, de tweede een korte stringvoorstelling (de naam) van de taak. AbstractTask Om de implementatie voor de gebruiker makkelijker te maken, werd een AbstractTask ge¨ımplementeerd. Dit is een default implementatie van alle methodes van Task. Er wordt een abstracte methode public void doTask() gedeclareerd die de gebruiker moet implementeren om een volwaardige Task te schrijven. Bij het runnen van de Task zal er worden gecontroleerd of er een context en eventueel (indien nodig) een configuratie werd ingesteld. AbstractTask zal automatisch de running toestand aanpassen en de eventuele listeners hiervan op de hoogte brengen. TaskList Taken kunnen geordend worden in een lijst. TaskList bevat in essentie een List. Ik koos ervoor om TaskList een implementatie van Task te maken omdat het uitvoeren van een TaskList niets meer is dan het sequentieel uitvoeren van alle Taken die het bevat. Dit heeft twee voordelen: het maakt het implementeren van conditionele of “magic” taken (zie C.4) gemakkelijker en het configureerbaar zijn van een takenlijst biedt interessante mogelijkheden (we kunnen bijvoorbeeld meta-informatie in de configuratie opslaan). TaskList implementeert alle methodes van Task. Zo ondersteunt het dus ook listeners: luisterende objecten worden op de hoogte gebracht wanneer één van de Tasks die het bevat verandert. Dit maakt serializatie wel iets ingewikkelder. De omschrijving van de TaskList is (net zoals de titel van de werkomgeving) gewoon een configuratie-entry voor de takenlijst. Serializatie van Taken Bij het serialiseren van een object worden alle velden recursief geserialiseerd. Zoals reeds gezegd kunnen er zich bij Taken TaskChangeListeners registereren. Wanneer een object opnieuw wordt ingeladen, heeft het echter geen zin om bijvoorbeeld oude GUI-objecten terug te verwittigen. Listeners moeten dus niet bewaard worden bij serializatie. Door bij de declaratie van een veld het keyword transient te gebruiken, wordt dat veld bij serializatie niet bewaard. De listeners, de CookieContext en de running-toestand werden dan ook gedefinieerd als transient. Deze velden dienen wel hersteld te worden. In het geval van TaskList betekent dit dat de TaskList


80

zich terug bij elke Task moet registreren als TaskChangeListener. Hiervoor werd de methode private void readObject(ObjectInputStream in) overschreven.

C.3.3

Listeners: communicatie met de view

Listeners zijn objecten (bv. GUI componenten) die luisteren naar veranderingen van bepaalde objecten in het model. Hiervoor registreren ze zich bij die objecten. Deze houden in feite een lijst van listeners bij en zullen, wanneer de inwendige toestand verandert, een bepaalde methode op de listeners uitvoeren. Dit stelt de listeners in staat om te reageren op wijzigingen (cfr. het observer/observable design pattern). De listeners werden ondergebracht in de package cookiemonster.model.listener. • WorkpaceListChangeListeners worden op de hoogte gebracht wanneer er een nieuwe Workspace wordt gecreëerd of verwijderd in het CookieModel. Merk op dat er niets gebeurt bij een interne wijziging in van een Workspace (bv. het toevoegen van taken). Het containervenster zal zich bijvoorbeeld als een WorkpaceListChangeListener registreren om, wanneer er in het model een Workspace gecreëerd of verwijderd wordt, een nieuw intern venster te openen of het corresponderende venster te sluiten. • TaskChangeListeners luisteren naar veranderingen in de toestand van de Task waarbij ze geregistreerd zijn. In het geval van een TaskList betekent dit bij een wijziging van de TaskList zelf, of een van de onderliggende Tasks. De inwendige vensters zullen zich als TaskChangeListeners registreren om bij veranderingen in de takenlijst de weergave te vernieuwen.

C.3.4

De GUI: view en controller

CookieMonster gebruikt de Java Swing toolkit [48]. Voor de implementatie van de GUImogelijkheden wordt er gebruik gemaakt van Actions. Een Action is een object dat een bundeling is van een uit te voeren actie samen met extra informatie zoals een korte beschrijving, een tooltip, een pictogram en sneltoetsen. Swing voorziet ondersteuning om rechtstreeks GUI-componenten afgeleid van deze Actions te creëren. Op deze manier moet niet elke GUIcomponent met de hand ingesteld worden maar zal de informatie uit de actie (her)gebruikt worden. Dit zorgt voor een betere onderhoudbaarheid en uitbreidbaarheid van de code. Merk op dat dit terug een implementatie van het command design pattern is. Van elke Action wordt één instantie gecreëerd. Om deze instanties gemakkelijk terug te vinden worden ze bewaard in een ActionMap zodat ze via een sleutel teruggevonden kunnen worden5 . Er worden ActionMaps voorzien op twee niveaus: één globale (toegankelijk via het CookieModel) en één voor elke werkomgeving (bewaard in het WorkspaceInternalFrame, d.i. de klasse die de interne vensters voorstelt). De Actions in de ActionMap voor de werkomgeving zijn acties die in werken op een specifieke werkomgeving (bv. uitvoeren van de takenlijst of het verplaatsen van de geselecteerde taak). 5

Eigenlijk wordt er gebruik gemaakt van een eigen klasse ExtendedActionMap die ActionMap uitbreidt met ondersteuning voor “togglebare” acties (ToggleActions). Dit zijn acties met de speciale eigenschap dat ze geselecteerd kunnen zijn. Typisch worden ze gebruikt voor bijvoorbeeld checkboxes. Er wordt voor gezorgd dat alle andere GUI-componenten die gebaseerd zijn op de ToggleAction automatisch hun view aanpassen. Het voordeel van deze aanpak is dat GUI-componenten die zowel controller als view zijn veel eleganter gecreëerd kunnen worden. (De ontwikkelaar zou anders die componenten met de hand als luisteraar van het model moeten registereren en gepast laten reageren op wijzigingen.)


C.4

81

Mogelijke verbeteringen

Dit is een lijst van ideeën die me zinvol lijken, maar niet nodig zijn voor het gebruik in deze scriptie. Parallellisatie Sommige taken (bv. QueryDBLP en ProcessElectronicEdition) kunnen duidelijk intern geparallelliseerd worden. Veel tijd wordt bijvoorbeeld verloren bij het wachten op de response van de honderden HTML-pagina’s. We kunnen ook de Workspace parallelliseren door deze te laten bestaan uit meerdere TaskLists. Conditionele taken Het zou leuk zijn om klassieke lussen en for-each of conditionele taken in te voeren. Merk op dat dit vrij eenvoudig kan gebeuren omdat een TaskList een Task is; in feite moeten deze speciale conditionele taken enkel een Task object inbedden en uitvoeren naargelang een conditievoorwaarde. De uitdaging zit echter in het omgaan met de conditievoorwaarde en de implementatie van de GUI. De conditievoorwaarde kunnen we bijvoorbeeld implementeren als door de eindgebruiker geschreven objecten met een methode public boolean evaluate(). Het zou echter handiger zijn om een conditievoorwaarde via de configuratie in te kunnen geven, maar dit maakt de applicatie minder generiek. Magic tasks Deze klasse van taken doen zaken die eigenlijk tegen het ontwerp van de applicatie in gaan. Het zou bijvoorbeeld misschien interessant kunnen zijn om taken te schrijven die communicatie tussen twee concurrente Workspaces doet. Men kan dan bijvoorbeeld een object uit de Objectstore kopiëren naar een andere Workspace, die dan bv. hierop monitoring kan doen. Ook bariers of semaforen (voor parallellisme op Workspace-niveau) behoren tot de mogelijkheid. De vraag is of dit echt gewenst is aangezien concurrente toegang tot de Sesame Repository (wat wellicht de meest interessante mogelijkheid van zo’n taak zou zijn) ook kan verkregen worden door een remote Sesame server te gebruiken.

Bijlage D

Bespreking CookieMonster taken In deze appendix geven we een overzicht van de taken die we reeds voor CookieMonster ontwikkelden. Bij elke taak hoort een beknopte beschrijving en een overzicht van de verschillende configuratieattributen.

D.1 D.1.1

Beheer van Sesame Repositories OpenMemoryStoreRepository

Creëert een nieuwe Sesame Repository in het geheugen (MemoryStore). De repository wordt via de ObjectStore toegankelijk gemaakt. Configuratie • filename. Wanneer hier een bestandsnaam wordt ingevuld, zal de MemoryStore een persistente kopie in dit bestand op de schijf bijhouden. Als het bestand reeds bestaat, zal het bij het openen in de repository geladen worden. • repkey. Sleutel in de ObjectStore waarlangs de repository toegankelijk dient gemaakt te worden.

D.1.2

OpenNativeStoreRepository

Opent een Sesame Repository die de RDF-triples in een B+-boom op de schijf bewaart (MemoryStoreRepository). Elke toegang tot de repository gaat dus in principe altijd via de schijf, maar door de verschillende indices en caching in het besturingssysteem heeft deze implementatie ook een goede performantie. Configuratie • filename. Naam van de directory waar de repository wordt bewaard. Sesame zal verschillende bestanden in deze directory plaatsen. • repkey. Sleutel in de ObjectStore waarlangs de repository toegankelijk dient gemaakt te worden.

82

BIJLAGE D. BESPREKING COOKIEMONSTER TAKEN

D.1.3

83

ShutdownRepository

Sluit de repository af door de shutDown() methode op het Repository object op te roepen. Dit is de correcte manier om een Repository te sluiten; MemoryStore krijgt zo bv. nog de kans om eventuele wijzigingen naar de persistente kopie te schrijven. Na afsluiten wordt de repository uit de ObjectStore verwijderd. Configuratie • repkey. Sleutel in de ObjectStore van de af te sluiten repository.

D.1.4

DumpRepository

Drukt de volledige inhoud van een Sesame Repository in N-triples formaat af op de console. Configuratie • repkey. Sleutel in de ObjectStore van de te gebruiken repository.

D.1.5

DumpStatistics

Bepaalt het aantal personen (foaf:Person), publicaties (ow:Publication), kernwoorden en unieke kernwoorden (ow:keywords) in de repository en drukt dit af op de console. (Zie Sectie A.1.) Configuratie • repkey. Sleutel in de ObjectStore van de te gebruiken repository.

D.2 D.2.1

Vullen van de dataset: crawlen en importeren QueryDBLP

Deze taak verzamelt bibliografische data uit de DBLP databank [38]. QueryDBLP doet een query naar alle tijdschriften of conferenties die een bepaalde zoekterm bevatten en bewaart de BibTeX-entries van de gevonden publicaties in een bestand. Deze taak gaat als volgt te werk: 1. De op DBLP te plaatsen query wordt afgeleid uit de de waarde van de attributen journal, conference en maxresults en wordt aangeboden op de CGI-interface van de DBLP zoekfunctie. De resulterende HTML-file wordt volledig gedownload en in een String bewaard. Het attribuut maxresults bepaalt het maximaal aantal records dat DBLP teruggeeft, en dient dus voldoende hoog te worden gekozen. 2. Elke record bevat een URI zoals bv. [DBLP:journals/fss/CockK03a]. Deze worden met een reguliere expressie gezocht. 3. Voor elke URI wordt er een hiervan afgeleide URL gedownload, zoals bv. http://dblp.uni-trier.de/rec/bibtex/journals/fss/CockK03a. Deze HTML-pagina bevat de BibTeX-entry van de bijhorende publicatie. Met een reguliere expressie wordt de entry uit de HTML-file gehaald, en achteraan het uitvoerbestand geplaatst. Om het aantal aanvragen per seconde te beperken, wordt tussen het opvragen van twee BibTeX-entries een pauze van pauze ms gelaten.


84

Configuratie • journal. Te gebruiken zoekterm om te zoeken in tijdschriften. Spaties dienen vervangen te worden door “+”. Indien dit veld gebruikt wordt, dient het conference veld leeg gelaten te worden. • conference. Zoeken in conferenties, cfr. journal. Spaties dienen vervangen te worden door “+”. Indien dit veld gebruikt wordt, dient het journal veld leeg gelaten te worden. • maxresults. Maximum aantal records dat gedownload mag worden (standaardwaarde is “10000”). • pauze. Pauze tussen het downloaden van twee BibTeX-entries in milliseconden (standaardwaarde is “200”). • filekey. Sleutel van het File-object dat het bestand beschrijft waarnaar de resultaten zullen geschreven worden.

D.2.2

ImportBibtexEntries

Importeert een BibTeX-bestand in een repository. Vooraleer het BibTeX-bestand wordt ge¨ımporteerd, wordt het eerst omgezet in XML+RDF-formaat met behulp van het bib2rdf script van Michel Klein [39]. De locatie van het script is hardgecodeerd in de code: de code moet dus eerst aangepast worden vooraleer deze taak gebruikt kan worden. Configuratie • baseuri. Indien relatieve URI’s in het XML+RDF-bestand voorkomen, worden deze ten opzichte van deze URI ge¨ınterpreteerd. (standaardwaarde is “dblp:bibtexentry”) • filekey. Sleutel van het File-object dat het te importeren BibTeX-bestand beschrijft. • repkey. Sleutel in de ObjectStore van de te gebruiken repository.

D.2.3

ImportXML

Importeert een XML+RDF-bestand in een repository. Dit laat de gebruiker toe om eigen data in de repository te importeren. Merk op dat het niet mogelijk is om data die reeds in de repository aanwezig is, opnieuw te importeren. Configuratie • baseuri. Indien relatieve URI’s in het XML+RDF-bestand voorkomen, worden deze ten opzichte van deze URI ge¨ınterpreteerd. (standaardwaarde is “dblp:bibtexentry”) • filekey. Sleutel van het File-object dat het te importeren XML-bestand beschrijft. • repkey. Sleutel in de ObjectStore van de te gebruiken repository.

D.2.4

MarkAuthorsAsCoreAuthors

Markeert alle auteurs in een repository. Meer precies wordt voor elke foaf:Person een eigenschap rdf:type http://studwww.ugent.be/~bvrslypp/thesis/ont/CorePerson toegevoegd, m.a.w. elke gemarkeerde persoon wordt ook lid van de klasse http://studwww.ugent.be/~bvrslypp/thesis/ont/CorePerson.


85

Configuratie • repkey. Sleutel in de ObjectStore van de te gebruiken repository.

D.2.5

QueryMarkedAuthorsOnDBLP

Deze taak downloadt voor elke gemarkeerde auteur in een repository alle BibTeX-entries op DBLP en bewaart alle gevonden BibTeX-entries in een bestand. Wanneer DBLP een naamdisambiguatiepagina toont indien de gezochte naam niet exact teruggevonden werd of er gelijkaardige namen bestaan, wordt de te volgen link bepaald door eerst de accenten en andere lettertekens van de zoekterm en de voorgestelde namen te verwijderen en dan een link te volgen indien een exacte match gevonden wordt. Doorverwijspagina’s worden niet herkend. Dubbele BibTeX-entries worden verwijderd. Configuratie • filekey. Sleutel van het File-object dat het pad van de outputbestanden bevat. De bestandsnaam in dit object dient zonder extensie te zijn aangezien er twee bestanden gecreëerd worden: een logbestand (eindigend op “.log”) en het BibTeX-bestand (eindigend op “.bib”). • pauze. Pauze tussen het downloaden van twee BibTeX-entries (uitgedrukt in milliseconden). (standaardwaarde is “200”) • repkey. Sleutel in de ObjectStore van de repository waarin gezocht wordt naar de namen van gemarkeerde auteurs.

D.2.6

CopyMarksBetweenRepositories

CopyMarksBetweenRepositories kopieert de markeringen van een repository naar een andere. Dit gebeurt aan de hand van de namen van de personen. Eerst wordt er een lijst opgesteld van de namen van de gemarkeerde personen in de bronrepository. Daarna wordt elke naam op deze lijst gezocht in de doelrepository, en indien de naam (exact) teruggevonden wordt, wordt er een markering toegevoegd. Configuratie • fromrepkey. Sleutel in de ObjectStore van de te gebruiken bronrepository. • torepkey. Sleutel in de ObjectStore van de te gebruiken doelrepository.

D.2.7

ProcessElectronicEdition

Deze taak downloadt kernwoorden en abstracts van publicaties in de repository. Hiervoor worden de links naar de elektronische editie gebruikt. Alle links op gekende, geactiveerde uitgeversportals worden bezocht. Op dit moment wordt alleen ScienceDirect ondersteund.


86

B A

J I

C

L

D E

K

H

G

F

Figuur D.1: Voorbeeld van BuildSimpleCoauthorGraph.

een

basis

co-auteursnetwerk

zoals

gebouwd

door

Configuratie • download_sciencedirect. Activeer het downloaden op ScienceDirect. (standaardwaarde is “true”) • logoutputfile. Bestandsnaam van het logbestand (dit veld is verplicht). Er wordt zowel naar de console als naar het logbestand geschreven. • repkey. Sleutel in de ObjectStore van de te gebruiken Repository.

D.3 D.3.1

Opbouw van co-auteursnetwerken BuildSimpleCoauthorGraph

Bouwt een “basis co-auteursnetwerk” op aan de hand van de informatie in een repository. Elke gemarkeerde auteur wordt aan de graaf toegevoegd, alle andere (niet gemarkeerde) auteurs worden genegeerd. Tussen twee auteurs wordt een boog geplaatst indien ze samen auteur zijn van tenminste één publicatie. Een typevoorbeeld van een dergelijke graaf wordt gegeven in Figuur D.1. Configuratie • graphkey. Sleutel in de ObjectStore van de bekomen graaf. Dit object is van het type edu.uci.ics.jung.graph.UndirectedGraph. • repkey. Sleutel in de ObjectStore van de te gebruiken Repository.

D.3.2

BuildDirectedWeightedCoauthorGraph

Bouwt een “gewogen, gericht co-auteursnetwerk” op aan de hand van informatie in een repository. Enkel gemarkeerde auteurs worden beschouwd, andere worden genegeerd. Wanneer twee (gemarkeerde) auteurs samenwerkten aan een publicatie, worden twee tegengesteld gerichte pijlen tussen deze twee auteurs getrokken. De gewichten op de bogen geven het aantal gedeelde publicaties weer. Na het verwerken van alle publicaties, worden de gewichten genormaliseerd door de gewichten op de uitgaande bogen te delen door het aantal publicaties van de onderzoeker. Een typevoorbeeld van een dergelijke graaf wordt gegeven in Figuur D.2.


0,5

B

0,6

0,5

0,5 0,5 0,111 C 0,222 0,111 0,5 0,25 0,5 0,125 D 0,333 0,5 0,5 0,666 0,6 0,222 0,444 E G 0,375 0,666 1 0,333 0,5 0,666 0,666 F

A

87

0,25

0,6

I

0,5

0,4 0,4

0,4

J 0,8

1

1

1

K

H

0,4

L

0,5

Figuur D.2: Voorbeeld van een gericht, gewogen co-auteursnetwerk zoals gebouwd door BuildDirectedWeightedCoauthorGraph. 0,5

B 0,5

A 0,5 0,25 0,333 0,666

E

D 1

0,666

F

0,6

0,5 0,5 0,5 0,5 0,444

I

C 0,4 0,4

0,5

G

0,6

H

J

1

0,6 1 0,4

K

1

L

0,666

Figuur D.3: Voorbeeld van een aangepast gericht, gewogen co-auteursnetwerk zoals gebouwd door BuildAdvancedDirectedWeightedCoauthorGraph. Dit voorbeeld vertrekt van dezelfde dataset als Figuur D.2 en de difference werd ingesteld op 0.1. Configuratie • graphkey. Sleutel in de ObjectStore van de bekomen graaf. Dit object is van het type edu.uci.ics.jung.graph.DirectedGraph. • repkey. Sleutel in de ObjectStore van de te gebruiken Repository.

D.3.3

BuildAdvancedDirectedWeightedCoauthorGraph

Bouwt een “aangepast gewogen, gericht co-auteursnetwerk” op aan de hand van informatie in een repository. Vertrekkende van een gericht, gewogen co-auteursnetwerk, wordt er bij elk paar tegengesteld gerichte pijlen telkens de pijl met het laagste gewicht verwijderd. Wanneer het verschil (in absolute waarde) tussen de gewichten van een paar bogen strikt kleiner is dan de waarde van het attribuut difference, dan worden beide bogen bewaard. Een voorbeeld wordt gegeven in Figuur D.3. Configuratie • difference. Minimum verschil tussen de gewichten van de bogen dat aanleiding geeft tot het verwijderen van de boog met het kleinste gewicht. (standaardwaarde is “0.1”) • graphkey. Sleutel in de ObjectStore van de bekomen graaf. Dit object is van het type edu.uci.ics.jung.graph.DirectedGraph. • repkey. Sleutel in de ObjectStore van de te gebruiken Repository.


D.4 D.4.1

88

Sociale netwerkanalyse van co-auteursnetwerken FindComponentClusters

Deze taak bepaalt de componenten van een graaf. Eerst wordt de inhoud van elke component getoond, gevolgd door een frequentietabel van de componentgroottes. Het is mogelijk om de grootste component naar een nieuwe graaf te exporteren. Deze taak werkt zowel op gerichte als ongerichte grafen. Bij het exporteren worden het type van de graaf en de gewichten op de bogen bewaard. Configuratie • graphkey. Sleutel in de ObjectStore van de te analyseren graaf. • exportcomponent. Sleutel in de ObjectStore van de geëxporteerde component. Wanneer dit veld leeg gelaten wordt, wordt de exporteerstap overgeslagen. • outputfile. Uitvoer naar de console of naar een bestand. Wanneer de waarde van dit attribuut “console” is, wordt de uitvoer naar de console geschreven. In het andere geval wordt de waarde van het attribuut ge¨ınterpreteerd als een bestandsnaam.

D.4.2

CalculateSimpleLocalGraphMeasures

Berekent voor elke top eenvoudige egogebaseerde maten. De resultaten worden uitgeschreven als een tabel waarbij elke top beschreven wordt door de naam van de auteur die hij voorstelt. Bij grote datasets kunnen calc_averageDistances en calc_betweenness een lange rekentijd hebben. Configuratie • graphkey. Sleutel in de ObjectStore van de te analyseren graaf. Deze dient van het type edu.uci.ics.jung.graph.UndirectedGraph te zijn. • calc_degree. Berekent de graad van elke top. (standaardwaarde is “true”) • calc_betweenness. Berekent de spilcentraliteit van elke top. (standaardwaarde is “true”) • calc_clusteringCoefficients. Berekent de clusteringcoëfficiënt van elke top. (standaardwaarde is “true”) • calc_averageDistances. Berekent de nabijheid (d.i. de gemiddelde lengte naar alle andere bereikbare toppen) en de afstand tot de verst verwijderde top (“maxdist”). Het begrip padlengte verwijst hierbij telkens naar het kortste pad. (standaardwaarde is “true”.) • outputfile. Uitvoer naar de console of naar een bestand. Wanneer de waarde van dit attribuut “console” is, wordt de uitvoer naar de console geschreven. In het andere geval wordt de waarde van het attribuut ge¨ınterpreteerd als een bestandsnaam.

D.4.3

CalculateDirectedWeightedLocalGraphMeasures

Berekent enkele egogebaseerde maten op gerichte, gewogen grafen. De resultaten worden zoals bij CalculateSimpleLocalGraphMeasures uitgeschreven in tabelvorm.


89

Configuratie • graphkey. Sleutel in de ObjectStore van de te analyseren graaf. Deze dient van het type edu.uci.ics.jung.graph.DirectedGraph te zijn. • calc_degrees. Berekent de graad, de som van de gewichten van de inkomende bogen (“degreesum in”) en de som van de gewichten van de uitgaande bogen (“degreesum out”) van elke top. (standaardwaarde is “true”) • calc_hits. Berekent de autoriteitswaarden van het HITS algoritme voor elke top. (standaardwaarde is “true”) • calc_pagerank. Berekent de PageRank van elke top. (standaardwaarde is “true”) • calc_publications. Geeft het aantal publicaties van elke top. (standaardwaarde is “true”) • outputfile. Uitvoer naar de console of naar een bestand. Wanneer de waarde van dit attribuut “console” is, wordt de uitvoer naar de console geschreven. In het andere geval wordt de waarde van het attribuut ge¨ınterpreteerd als een bestandsnaam.

D.4.4

CalculateGlobalGraphStatistics

Berekent globale statistieken. Zowel gerichte als ongerichte grafen worden ondersteund. Op dit moment is enkel de berekening van de diameter ge¨ımplementeerd. Configuratie • graphkey. Sleutel in de ObjectStore van de te analyseren graaf. Deze dient van het type edu.uci.ics.jung.graph.Graph te zijn. • calc_diameter. Berekent de diameter van de graaf. (standaardwaarde is “true”) • outputfile. Uitvoer naar de console of naar een bestand. Wanneer de waarde van dit attribuut “console” is, wordt de uitvoer naar de console geschreven. In het andere geval wordt de waarde van het attribuut ge¨ınterpreteerd als een bestandsnaam.

D.5 D.5.1

Profielen BuildSimpleProfileGraph

Bouwt een profielgraaf aan de hand van informatie in een repository op. Eerst wordt elke voor elke auteur en elk uniek kernwoord (tag) een top aan de graaf toegevoegd. Daarna worden alle publicaties overlopen: als een kernwoord voorkomt in een publicatie, wordt een gerichte boog van de auteur(s) naar die tag aan de graaf toegevoegd. Op de pijlen wordt een gewicht geplaatst dat weergeeft hoeveel keer de auteur het kernwoord gebruikt heeft. Alle kernwoorden worden eerst getrimd (d.i. het verwijderen van overtollige witruimte), in kleine letters geplaatst en gestemd vooraleer ze met andere vergeleken worden; op deze manier worden sommige kernwoorden samengevoegd tot één tag. Een voorbeeld van een dergelijke graaf wordt gegeven in Figuur D.4.


T2

T4

T3

T6

90

T10

T8

T12

T9

T5

T1

T11

T13

T7

B

J I

C

A

L

D E

G

H

K

F

Figuur D.4: Voorbeeld van een profielgraaf zoals gebouwd door BuildSimpleProfileGraph. De letters A t.e.m. L stellen actoren voor en T1 t.e.m. T13 zijn tags. De gewichten op de bogen werden weggelaten. Configuratie • graphkey. Sleutel in de ObjectStore van de bekomen graaf. Dit object is van het type edu.uci.ics.jung.graph.DirectedGraph. • repkey. Sleutel in de ObjectStore van de te gebruiken Repository.

D.5.2

BuildSimpleFuzzyProfile

Bouwt voor elke auteur een profiel op. Alle profielen worden gebundeld in het Profile-object, dat de profielmatrix en enkele indices bevat zoals beschreven in Sectie 5.2.2. Configuratie • normalize. Geeft aan of het profiel genormaliseerd moet worden. Indien de waarde van dit attribuut “false” is, wordt voor elke tag het absoluut aantal keer dat de tag gebruikt werd gegeven. Anders worden alle frequenties gedeeld door de grootste waarde in het profiel van de auteur, zodat elk profiel uit waarden tusen nul en één bestaat (d.i. een vaagverzameling). (standaardwaarde is “true”) • graphkey. Sleutel in de ObjectStore van de profielgraaf waar de onderzoekersprofielen van afgeleid moeten worden. Dit object is van het type edu.uci.ics.jung.graph.DirectedGraph. • profilekey. Sleutel in de ObjectStore van het bekomen profiel. Dit object is van het type Profile.


D.5.3

91

FilterKeywords

Deze taak wijzigt een profielgraaf door tags te verwijderen die niet aan bepaalde voorwaarden voldoen. Deze voorwaarden zijn het aantal publicaties waar de tag op voorkomt, het aantal verschillende auteurs die de tag gebruikten en het totaal aantal keer dat de tag gebruikt werd. De verschillende criteria worden gecombineerd. Na uitvoering kan er eventueel een lijst van verwijderde tags getoond worden. Configuratie • graphkey. Sleutel in de ObjectStore van de profielgraaf die gefilterd dient te worden (en is dus van het type edu.uci.ics.jung.graph.DirectedGraph). Merk op dat het object aangepast wordt (en dus niet gekopieerd wordt). • min_publications. Weerhoudt tags die minstens op min_publications verschillende publicaties voorkomen. (standaardwaarde is “0”). • min_degree. Weerhoudt tags die minstens door min_degree verschillende auteurs gebruikt worden. (standaardwaarde is “0”). • min_degreesum. Weerhoudt tags die minstens min_degreesum keer gebruikt worden. (standaardwaarde is “0”). • show_removed. Schrijft alle tags die door de filter niet weerhouden werden, en dus verwijderd worden, naar de console uit. (standaardwaarde is “false”)

D.5.4

CalculateProfileKeywordInformation

Berekent voor elke tag in een profielgraaf enkele waarden over het gebruik. De resultaten worden uitgeschreven in tabelvorm (voor elke tag één record). Configuratie • graphkey. Sleutel in de ObjectStore van de te analyseren profielgraaf (is dus van het type edu.uci.ics.jung.graph.DirectedGraph). • calc_degree. Berekent voor elke tag het aantal verschillende auteurs, het aantal keer dat de tag gebruikt werd en het maximaal hergebruik door dezelfde auteur. (standaardwaarde is “true”) • calc_publications. Berekent voor elke tag het aantal verschillende publicaties waarin de tag gebruikt werd. (standaardwaarde is “true”) • outputfile. Uitvoer naar de console of naar een bestand. Wanneer de waarde van dit attribuut “console” is, wordt de uitvoer naar de console geschreven. In het andere geval wordt de waarde van het attribuut ge¨ınterpreteerd als een bestandsnaam.

D.5.5

CalculateProfileAuthorInformation

Berekent voor elke auteur in een profielgraaf enkele waarden over zijn gebruik van tags. De resultaten worden uitgeschreven in tabelvorm (voor elke auteur één record).


92

Configuratie • graphkey. Sleutel in de ObjectStore van de te analyseren profielgraaf (is dus van het type edu.uci.ics.jung.graph.DirectedGraph). • calc_degree. Berekent voor elke auteur het aantal unieke tags, het aantal keer dat de auteur getagd werd en het maximaal hergebruik van dezelfde tag. (standaardwaarde is “true”) • calc_publications. Berekent voor elke auteur het aantal publicaties. (standaardwaarde is “true”) • outputfile. Uitvoer naar de console of naar een bestand. Wanneer de waarde van dit attribuut “console” is, wordt de uitvoer naar de console geschreven. In het andere geval wordt de waarde van het attribuut ge¨ınterpreteerd als een bestandsnaam.

D.5.6

CalculateProfileDistance

Berekent voor elke auteur de meest verwante profielen. Deze worden in tabelvorm uitgeschreven waarbij elke auteur door één record beschreven wordt. Men kan de keuze maken uit twee verschillende metrieken: één gebaseerd op vaagverzamelingen en één gebaseerd op de afstand tussen de profielen (gebruik makend van de taximetriek). Zinloze resultaten (wanneer er geen verwantschap is) worden niet weergegeven. Configuratie • profilekey. Sleutel in de ObjectStore van de te analyseren profielen. Dit object is van het type Profile. • top. Aantal best verwante onderzoekers dat bepaald dient te worden. (standaardwaarde is “5”) • distance. Bepaalt welke techniek gebruikt moet worden om het verwantschap tussen twee profielen uit te drukken. Wanneer dit attribuut de waarde “intersection min” heeft, wordt de vage doorsnede (met behulp van het minumum) genomen, en de kardinaliteit van deze doorsnede wordt dan gebruikt als maat voor verwantschap. Als dit attribuut de waarde “distance” heeft, wordt het verwantschap bepaald door gebruik te maken van de taximetriek (d.i. de som van de absolute waarde van het componentsgewijs verschil van alle lidmaatschapsgraden). (standaardwaarde is “intersection min”)

D.6 D.6.1

Varia ViewGraph

Start het ViewGraph applet automatisch op voor een bepaalde graaf. Merk op dat het ViewGraphapplet ook via het menu kan opgestart worden. Er wordt dan een lijst getoond van grafen in de ObjectStore die gevisualiseerd kunnen worden. Dit applet werkt zowel met gerichte als ongerichte grafen. Gewichten worden genegeerd. Configuratie • graphkey. Sleutel in de ObjectStore van te visualiseren graaf.


D.6.2

93

Pause

Deze taak voert een pauze uit en geeft hierbij de processor vrij. Deze taak kan gebruikt worden om de onderzoeker de kans te geven de uitvoer van de vorige taak te bestuderen vooraleer de volgende start. Configuratie • pause. Lengte van de pauze, in milliseconden. (standaardwaarde is “10000”)

D.6.3

CreateFile

CreateFile creëert een File-object dat een bestandsnaam bevat. De bestandsnaam vervat in dit object kan dan door andere taken gebruikt worden om de resultaten naar te schrijven. Configuratie • path. Pad van het bestand. • key. Sleutel in de ObjectStore van het resulterend File-object.

D.6.4

CreateTempFile

Creëert een tijdelijk bestand waarvan het pad opgeslagen wordt in een File-object. Na het afsluiten van CookieMonster wordt het tijdelijk bestand verwijderd. Configuratie • key. Sleutel in de ObjectStore van het resulterend File-object.

Bijlage E

Takenlijsten In deze bijlage geven we een overzicht van de takenlijsten die besproken werden in Hoofdstuk 4 en Hoofdstuk 5. Het is de bedoeling de lezer duidelijk te maken hoe men de resultaten kan reproduceren en welke stappen men moet doorlopen bij het opbouwen van een nieuwe dataset (voor een ander onderzoeksdomein). In het kader deze scriptie werden er uiteraard ook andere takenlijsten gebruikt (in het bijzonder voor de analyse), maar omwille van hun triviaal karakter worden ze hier niet vermeld. De preciese werking van de verschillende taken werd reeds besproken in Bijlage D.

E.1 E.1.1

Co-auteursnetwerken crawl1-download.cm

---------------------------------------------------------------------- crawl1_download.cm ---------------------------------------------------------------------Bewaart het resultaat van verschillende DBLP queries in entries.bib ---------------------------------------------------------------------*** 1: CreateFile Configuration: - key = file - path = /home/bert/svnworkspace/thesis/dataset/entries.bib *** 2: QueryDBLP Configuration: - conference = - filekey = file - journal = fuzzy+sets+and+systems - maxresults = 10000 - pauze = 200 *** 3: Pause Configuration: - pause = 10000 *** 4: QueryDBLP Configuration: - conference = - filekey = file - journal = Int.+J.+Approx.+Reasoning

94

BIJLAGE E. TAKENLIJSTEN

95

- maxresults = 10000 - pauze = 200 *** 5: Pause Configuration: - pause = 10000 *** 6: QueryDBLP Configuration: - conference = ifsa - filekey = file - journal = - maxresults = 10000 - pauze = 200 *** 7: Pause Configuration: - pause = 10000 *** 8: QueryDBLP Configuration: - conference = FUZZ-IEEE - filekey = file - journal = - maxresults = 10000 - pauze = 200 ----------------------------------------------------------------------

De pauze tussen de taken dient om een synchronizatieprobleem in de (linux) native code van Java1 te vermijden. Indien we de pauzes weglaten, worden de laatste BibTeX-entries van de vorige taak overschreven of krijgen we een java.io.IOException.

E.1.2

crawl1-import.cm

---------------------------------------------------------------------- crawl1_import.cm ---------------------------------------------------------------------Voert de output van Michel Kleins script in de sesame repository. ---------------------------------------------------------------------*** 1: OpenMemoryStoreRepository Configuration: - filename = /home/bert/svnworkspace/thesis/dataset/sesame/rep-entries - repkey = stdrep *** 2: CreateFile Configuration: - key = file - path = /home/bert/svnworkspace/thesis/dataset/entries.bib *** 3: ImportBibtexEntries Configuration: - filekey = file 1

http://256.com/gray/docs/misc/java_bad_file_descriptor_close_bug.shtml (bezocht op 25 mei 2007)


- repkey = stdrep *** 4: DumpStatistics Configuration: - repkey = stdrep *** 5: ShutdownRepository Configuration: - repkey = stdrep ----------------------------------------------------------------------

E.1.3

crawl1-mark.cm

---------------------------------------------------------------------- crawl1_mark.cm ---------------------------------------------------------------------Markeert alle auteurs in de repository. ---------------------------------------------------------------------*** 1: OpenMemoryStoreRepository Configuration: - filename = /home/bert/svnworkspace/thesis/dataset/sesame/rep-entries - repkey = stdrep *** 2: MarkAuthorsAsCoreAuthors Configuration: - repkey = stdrep *** 3: ShutdownRepository Configuration: - repkey = stdrep ----------------------------------------------------------------------

E.1.4

crawl2-download.cm

---------------------------------------------------------------------- crawl2_download.cm ---------------------------------------------------------------------Downloadt de bibtex-entries voor alle gemarkeerde auteurs in de repository. ---------------------------------------------------------------------*** 1: OpenMemoryStoreRepository Configuration: - filename = /home/bert/svnworkspace/thesis/dataset/sesame/rep-entries - repkey = stdrep *** 2: CreateFile Configuration: - key = file - path = /home/bert/svnworkspace/thesis/dataset/entries_crawl2 *** 3: QueryMarkedAuthorsOnDBLP Configuration: - filekey = file - pause = 200

96


- repkey = stdrep *** 4: ShutdownRepository Configuration: - repkey = stdrep ----------------------------------------------------------------------

E.1.5

crawl2-copymarks.cm

---------------------------------------------------------------------- crawl2_copymarks.cm ---------------------------------------------------------------------Kopieert de marks van rep-entries (dataset crawl1) naar rep-crawl2 (dataset crawl2) ---------------------------------------------------------------------*** 1: OpenMemoryStoreRepository Configuration: - filename = /home/bert/svnworkspace/thesis/dataset/sesame/rep-entries - repkey = fromrep *** 2: OpenNativeStoreRepository Configuration: - filename = /home/bert/svnworkspace/thesis/dataset/sesame/rep-crawl2 - repkey = stdrep *** 3: CopyMarksBetweenRepositories Configuration: - fromrepkey = fromrep - torepkey = stdrep *** 4: ShutdownRepository Configuration: - repkey = fromrep *** 5: ShutdownRepository Configuration: - repkey = stdrep ----------------------------------------------------------------------

E.2 E.2.1

Profielnetwerken profiles-download.cm

---------------------------------------------------------------------- profiles_download.cm ---------------------------------------------------------------------Overloopt alle EEs in de repository, downloadt voor elke ScienceDirect publicatie de abstract en kernwoorden (indien beschikbaar) ---------------------------------------------------------------------*** 1: OpenNativeStoreRepository Configuration: - filename = /home/bert/svnworkspace/thesis/dataset/sesame/rep-crawl2

97


98

- repkey = stdrep *** 2: ProcessElectronicEdition Configuration: - download_sciencedirect = true - repkey = stdrep *** 3: ShutdownRepository Configuration: - repkey = stdrep ----------------------------------------------------------------------

E.2.2

profiles-info.cm

---------------------------------------------------------------------- profiles_info.cm ---------------------------------------------------------------------Bouwt een netwerkvoorstelling van de profielinformatie, verwijdert te unieke tags en berekent top-gebaseerde informatie voor de tags en auteurs. ---------------------------------------------------------------------*** 1: OpenNativeStoreRepository Configuration: - filename = /home/bert/svnworkspace/thesis/dataset/sesame/rep-crawl2 - repkey = stdrep *** 2: BuildSimpleProfileGraph Configuration: - graphkey = profilegraph - repkey = stdrep *** 3: FilterKeywords Configuration: - graphkey = profilegraph - min_degree = 0 - min_degreesum = 0 - min_publications = 3 - show_removed = false *** 4: CalculateProfileKeywordInformation Configuration: - calc_degree = true - calc_publications = true - graphkey = profilegraph - outputfile = /home/bert/svnworkspace/thesis/dataset/res/simpleprofile/info_keywords.csv *** 5: CalculateProfileAuthorInformation Configuration: - calc_degree = true - calc_publications = true - graphkey = profilegraph - outputfile = /home/bert/svnworkspace/thesis/dataset/res/simpleprofile/info_authors.csv *** 6: ShutdownRepository


Configuration: - repkey = stdrep ----------------------------------------------------------------------

99

Bibliografie [1] J. Srivastava, N. Pathak, S. Mane, and M.A. Ahmad. Data mining for social network analysis. In Proceedings of IEEE International Conference on Data Mining (ICDM), 2006. Slides van tutorial. [2] S. Milgram. The small world problem. Psychology Today, 2(1):60–67, 1967. [3] D. J. Watts and S.H. Strogatz. Collective dynamics of “small-world” networks. Nature, 393(6684):409–410, 1998. [4] S.P. Borgatti and P.C. Foster. The network paradigm in organizational research: A review and typology. Journal of Management, 29(6):991–1013, 2003. [5] V. Fack and H. Van Maldeghem. Cursusnota’s “Grafentheorie en Combinatorische Optimalisatie”, Universiteit Gent. 2006. [6] A. Culotta, R. Bekkerman, and A. McCallum. Extracting social networks and contact information from email and the Web. In Proceedings of the First Conference on Email and Anti-Spam (CEAS), July 2004. [7] W.W. Cohen. Enron E-mail Dataset. http://www.cs.cmu.edu/~enron/. Bezocht op 28 april 2007. [8] G. Salton and C. Buckley. Term-weighting approaches in automatic text retrieval. Information Processing and Management: an International Journal, 24(5):513–523, 1988. [9] R.D. Nolker and L. Zhou. Social computing and weighting to identify member roles in online communities. In Proceedings of IEEE/WIC/ACM International Conference on Web Intelligence (WI), 87–93, 2005. [10] P. Mika. Bootstrapping the FOAF-Web: An experiment in social network mining. In Proceedings of the First Workshop on Friend of a Friend, Social Networking and the Semantic Web, International Semantic Web Conference (ISWC), 2004. [11] P. Mika. Flink: Semantic Web technology for the extraction and analysis of social networks. Journal of Web Semantics, 3(2):211–223, 2005. [12] M. Sobek. Google Dance. http://dance.efactory.de/. Bezocht op 28 april 2007. [13] List of Social Networking Websites - Wikipedia, the free encyclopedia. http://en. wikipedia.org/wiki/List_of_social_networking_websites. Versie van 28 april 2007. [14] L. Ding, L. Zhou, T. Finin, and A. Joshi. How the Semantic Web is being used: An analysis of FOAF documents. Proceedings of the 38th International Conference on System Sciences, 1–10, 2005.

100

BIBLIOGRAFIE

101

[15] T. Finin, L. Ding, L. Zhou, and A. Joshi. Social networking on the Semantic Web. The Learning Organization, 12(5):418–435, 2005. [16] L. Ding, T. Finin, and A. Joshi. Analyzing social networks on the Semantic Web. IEEE Intelligent Systems (Trends & Controversies), 8(6), 2004. [17] Swoogle Semantic Web Search Engine. http://swoogle.umbc.edu/. Bezocht op 24 april 2007. [18] L. Ding, T. Finin, A. Joshi, R. Pan, R.S. Cost, Y. Peng, P. Reddivari, V. Doshi, and J. Sachs. Swoogle: a search and metadata engine for the Semantic Web. In Proceedings of ACM Conference on Information and Knowledge Management (CIKM), 652–659, 2004. [19] J. Scott. Social Network Analysis: A Handbook. Sage Publications, 2000. [20] U. Brandes. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2):163–177, 2001. [21] G. Sabidussi. The centrality index of a graph. Psychometrika, 31(4):581–603, 1966. [22] J.M. Kleinberg. Authoritative sources in a hyperlinked environment. Journal of the ACM (JACM), 46(5):604–632, 1999. [23] L. Page, S. Brin, R. Motwani, and T. Winograd. The Pagerank Citation Ranking: Bringing order to the Web. Technical report, Stanford Digital Library Technologies Project, 1998. [24] S. Brin and L. Page. The anatomy of a large-scale hypertextual Web search engine. WWW7 Computer Networks, 30(1-7):107–117, 1998. [25] PageRank - Wikipedia, the free encyclopedia. http://en.wikipedia.org/wiki/PageRank. Versie van 27 april 2007. [26] J. Golbeck, B. Parsia, and J. Hendler. Trust networks on the Semantic Web. In Proceedings of the 7th International Workshop Cooperative Intelligent Agents (CIA) 238–249. Springer, 2003. [27] J. Golbeck. Personalizing applications through integration of inferred trust values in Semantic Web-based social networks. In Proceedings of the Semantic Network Analysis Workshop at the 4th International Semantic Web Conference (ISWC), 2005. [28] S.D. Kamvar, M.T. Schlosser, and H. Garcia-Molina. The eigentrust algorithm for reputation management in P2P networks. In Proceedings of the 12th International Conference on World Wide Web, 640–651. ACM Press New York, NY, USA, 2003. [29] J. Golbeck and J. Hendler. Reputation network analysis for email filtering. In Proceedings of the First Conference on Email and Anti-Spam (CEAS), 30–31, 2004. [30] A. Mathes. Folksonomies - Cooperative Classification and Communication Through Shared Metadata. http://www.adammathes.com/academic/ computer-mediated-communication/folksonomies.html, December 2004. [31] T. Vander Wal. Folksonomy - Vanderwal.net. http://vanderwal.net/folksonomy.html. Bezocht op 12 mei 2007.

BIBLIOGRAFIE

102

[32] P. Merholz. Ethnoclassification and Vernacular Vocabularies. http://www.peterme.com/ archives/000387.html. Bezocht op 12 mei 2007. [33] P. Merholz. Adaptive Path - Metadata For The Masses. http://www.adaptivepath.com/ publications/essays/archives/000361.php. Bezocht op 12 mei 2007. [34] S.A. Golder and B.A. Huberman. Usage patterns of collaborative tagging systems. Journal of Information Science, 32(2):198–208, 2006. [35] Y. Hassan-Montero and V. Herrero-Solana. Improving Tag-Clouds as Visual Information Retrieval Interfaces. In Proceedings of the International Conference on Multidisciplinary Information Sciences and Technologies (InSciT), 2006. [36] G. Begelman, P. Keller, and F. Smadja. Automated Tag Clustering: Improving Search and Exploration in the Tag Space. WWW2006, 22–26, 2006. [37] P. Mika. Ontologies are us: A unified model of social networks and semantics. In Proceedings of the International Semantic Web Conference (ISWC), 2005. [38] M. Ley. DBLP Bibliography. http://www.informatik.uni-trier.de/~ley/db/. Bezocht op 29 april 2007. [39] M. Klein. Bibtex-2-rdf Translator. http://www.cs.vu.nl/~mcaklein/bib2rdf/. Bezocht op 29 april 2007. [40] T. Berners-Lee, J. Hendler, and O. Lassila. The Semantic Web. Scientific American Magazine, 284(5):34–43, 2001. [41] F. Manola, E. Miller, et al. RDF Primer. W3C Recommendation, 2004. [42] D. Brickley and R.V. Guha. RDF Vocabulary Description Language 1.0: RDF Schema. W3C Recommendation, 2004. [43] D. Brickley and L. Miller. FOAF Vocabulary Specification. http://xmlns.com/foaf/0.1/. Bezocht op 18 mei 2007. [44] D. Hillmann. Using Dublin Core. http://dublincore.org/documents/usageguide. Bezocht op 18 mei 2007. [45] Y. Sure, S. Bloehdorn, P. Haase, J. Hartmann, and D. Oberle. The SWRC OntologySemantic Web for Research Communities. In Proceedings of the 12th Portuguese Conference on Artificial Intelligence (EPIA), 218–231, 2005. [46] J. Broekstra, A. Kampman, and F. van Harmelen. Sesame: A generic architecture for storing and querying RDF and RDF Schema. In Proceedings of the First International Semantic Web Conference (ISWC), 54–68. Springer, 2002. [47] T. Greanier. Discover the secrets of the Java Serialization API. http://java.sun.com/ developer/technicalArticles/Programming/serialization/. Bezocht op 17 maart 2007. [48] K. Walrath, M. Campione, A. Huml, and S. Zakhour. The JFC Swing Tutorial: A Guide to Constructing GUIs, Second Edition. Prentice Hall PTR, 2004.

Sociale Netwerkanalyse van Gebruikersprofielen

Recommend Documents