Zoeken naar 2 clubs

Geplaatst op 09-08-2012 door Maarten Marx | research, resultaten | tags: | comment image Geen reacties »

Netwerken bevatten behalve individuen ook groepjes die interresant kunnen zijn. Zo heb je klieks, deelgroepjes waarin iedereen met iedereen verbonden is. Echter die komen niet zo veel voor. Naast klieks bestaan er ook clubs en clans, begrippen geintroduceerd door Rob Mokken, een van Nederderlands nestors op het gebied van het analyseren van netwerken.

Een 2-club binnen een netwerk is een maximaal deel van dat netwerk waarin iedereen of direct met elkaar verbonden is (als in een kliek), of minstens 1 gemeenschappelijke “vriend” heeft.

Het vinden van de grootste 2-club binnen een netwerk is een NP-volledig probleem. Dit zijn problemen die we met de huidige kennis in het algemeen niet snel kunnen oplossen.
Het gebied van de kunstmatige intelligentie (AI) houdt zich precies bezig met het toch proberen op te lossen van dit soort hele moeilijke problemen. Steven Laan, een derde jaars student AI heeft zijn Bacehelor scriptie over dit onderwerp geschereven.

De scriptie is hieronder beschikbaar, samen met een aantal data sets en de 2-clubs die daar inzitten.

Niet Wilders, maar Cohen krijgt de meeste aandacht

Geplaatst op 23-02-2011 door Maarten Marx | parliament | tags: | comment image Geen reacties »

We hebben een aantal malen over interruptienetwerken geschreven. Een interruptiegraaf is een graphische weergave van een debat als een sociaal netwerk, waarin de deelnemers aan het debat de knopen zijn en er een pijl gaat van A naar B als A persoon B interrumpeerd. Onderaan deze post staat een voorbeeld van zo’n netwerk.

Net als hyperlinks tussen webpaginas kan je een interruptie zien als het geven van aandacht.
Binnen zo’n graaf kan je dan kijken wie er het meeste aandacht krijgt. Dat is op verschillende manieren te meten. We noemen er drie:

  • tel het aantal inkomende pijlen (de indegree)
  • weeg het aantal inkomende pijlen op een bepaalde manier:
    • gebruik de dikte van de pijl (het aantal interrupties, dus de intensiteit van de aandacht)
    • weeg een inkomende pijl met de belangrijkheid van de gever van de aandacht.

Het laatste idee zit achter Google’s fameuze PageRank wat weer een variant is van het begrip eigenvector centraliteit, dat veel in sociale netwerk analyse gebruikt. wordt.

We leggen het idee in een versimpelde versie uit. Voor meer, zie Wikipedia over PageRank.
Het idee is dat de aandacht die een persoon kan “weggeven” gelijk is aan zijn belangrijkheid. Als iemand zijn aandacht aan meerdere mensen geeft (hij interrumpeert meerdere personen), dan verdeelt hij zijn aandacht over die personen. De belangrijkheid van iemand is dan de som van alle aandacht die hij ontvangt.
In een formula gaat dat dan als volgt: de belangrijkheid van een persoon a in een netwerk, notatie B(a) , is

B(a) = de som van B(b)/outdegree(b) voor alle b met een pijl naar a

De outdegree(b) is het aantal pijlen dat vanuit b vertrekt.
We geven hieronder de sterk gerelateerde eigenvector centraliteit voor de deelnemers aan het debat over de regeringsverklaring op 26 Oktober 2010. Onderaan deze post staat een tekening van de interruptiegraaf. De interruptiegraaf staat nog mooier afgedrukt in een artikel in NRC Next. In dat artikel staan de deelnemers ook gerangschikt op het aantal ontvangen interrupties.
De volgorde aan de top is Blok, Wilders, Buma en dan Cohen. Cohen heeft minder dan een kwart van de interrupties die Blok heeft gekregen.

Gaan we de eigenvector centraliteit berekenen, dan komt er een heel ander beeld naar voren. Nu krijgt Cohen de meeste aandacht, gevolgd door, wie had ook anders verwacht, Wilders. Blok en Buma krijgen nu vrijwel evenveel aandacht, maar flink minder dan Cohen en Wilders. De rest krijgt slechts marginaal aandacht.

Cohen 1
Wilders .85
Blok .6
Buma .58
Van der Staaij .11
Pechtold .09
Halsema .09
Roemer 0
Rouvoet 0
Thieme 0

Voor iedereen die zelf wil gaan rekenen met deze graaf hebben we hem beschikbaar gemaakt in graphml formaat.