(toiminnot)

hwechtla-tl: Satunnaisten verkkojen klusteroituminen

Kierre.png

Mikä on WikiWiki?
nettipäiväkirja
koko wiki (etsi)
viime muutokset


(nettipäiväkirja 26.02.2018) Luin populaaritiedeteoksesta Linked (Barabási 2002), jonka tiedot sinänsä ovat vanhentuneita, että n solmun satunnaisesti muodostettuun verkkoon on yleensä muodostunut yksi iso yhdistetty klusteri, mikäli linkkejä on vähintään saman verran kuin solmuja. Olisi kiva verifioida tämä itse.

Tiettyä tulkinnanvaraisuutta on tietysti siinä, milloin meillä on vain "yksi klusteri". Satunnaisesti muodostetussa verkossa muutama solmu pystyy helposti välttelemään yhdistetyksi tulemista, ja olemme oikeastaan enemmän kiinnostuneita siitä, missä tilanteessa klustereita ei ole enää monta kuin missä tilanteessa jokainen solmu kuuluu klusteriin. Eli ehkäpä voisi laittaa ehdoksi sen, että suurin klusteri on kooltaan vaikkapa 9/10 koko verkon koosta, tjsp.

Mutta nykyiset ohjelmointikielet tekevät superhelpoksi kokeilla tällaista. Esimerkiksi clojuressa on mukavat joukot, joilla voi helposti pitää muistissa yhdistettyjä verkon komponentteja (verkon "ekvivalenssiluokkia" linkkien suhteen). Ohjelma näyttää tältä:

(use 'clojure.set)

(defn nodes [n] (set (range n)))

(defn node-map [nodes] (into {} (map #(vector % #{%}) nodes)))

(defn connect-nodes [node-map x y]
  (let [eqclass (union (get node-map x) (get node-map y))]
    (into node-map (map #(vector % eqclass) eqclass))))

(defn connect-random [node-map n]
  (connect-nodes node-map (rand-int n) (rand-int n)))

(defn state-seq [n]
  (iterate #(connect-random % n) (node-map (nodes n))))

(defn clustered? [node-map threshold]
  (> (apply max (map count (vals node-map)))
     (* threshold (count node-map))))

(defn clustering-point [n threshold]
  (count (take-while #(not (clustered? % threshold))
                     (state-seq n))))

Tulokset eivät kylläkään vastaa kunnolla kirjan väitettä.

user=> (load-file "connected.clj")
#'user/clustering-point
user=> (clustering-point 100 0.9)
138
user=> (clustering-point 100 0.9)
130
user=> (clustering-point 100 0.9)
151
user=> (clustering-point 100 0.9)
133

Jos yhden suuren klusterin pitää kattaa vain puolet verkosta, tulos on ihan eri. Satunneisesti muodostuneissa verkoissa suuren klusterin muodostumisessa aika menee siis satunnaisten erakkosolmujen haalimiseen osaksi verkkoa, ei klustereiden yhdistämiseen:

user=> (clustering-point 100 0.5)
66
user=> (clustering-point 100 0.5)
74
user=> (clustering-point 100 0.5)
72
user=> (clustering-point 100 0.5)
70

Siinä missä tulokset riippuvat "yhdeksi yhtymisen" tulkinnasta, ne eivät riipu verkon koosta, mikä on yhtäpitävää kirjan väitteen kanssa:

user=> (clustering-point 1000 0.9)
1302
user=> (clustering-point 1000 0.9)
1306
user=> (clustering-point 1000 0.9)
1262
user=> (clustering-point 1000 0.9)
1246
user=> (clustering-point 1000 0.5)
702
user=> (clustering-point 1000 0.5)
693
user=> (clustering-point 1000 0.5)
698
user=> (clustering-point 1000 0.5)
680

Joka tapauksessa kirjassa väitettiin, että on olemassa maaginen piste, jossa yhden klusterin muodostuminen tapahtuu. Se on, mutta riippuu siitä, kuinka suuren klusterin haluamme. Tämä lienee lähinnä satunnaisesti muodostettujen verkkojen ominaisuus? Satunnaisia verkkoja ei oikeastaan esiinny luonnossa, eivätkä nämä tulokset kertone paljon mitään verkoista, lähinnä satunnaisuuden luonteesta. Mutta jos mittakaavattomissa verkoissa on sama juttu, niin sitten pitää kyllä sanoa, että klusteroitumiselle _ei_ ole yhtä selkeää rajaa.


kommentoi (viimeksi muutettu 26.02.2018 17:26)