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.