satunnaisten verkkojen klusteroituminen

Mon, 26 Feb 2018 15:26:50 +0000

(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.

* [merkint�: 2018-02] * [atehwa] * [kategoria: p�iv�kirjamerkint�] * [kategoria: sosiaalisuus] * [kategoria: ohjelmointi]