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.
* [merkintä: 2018-02] * [atehwa] * [kategoria:
päiväkirjamerkintä] * [kategoria: sosiaalisuus] * [kategoria:
ohjelmointi] [pariohjelmoinnin ajankulutus]