Generating Experiments with Random Graphs in Clojure

In this Post we will look at generating experiments in random graphs. We consider basic uniform random graph generation, and consider other models such as rich-get-richer and geographic models. We will look at experiments in graph connectivity, the evolution of giant components, and other structures.

Here is an associated Powerpoint Presentation.

Generating Graph Data Structures in Clojure

Adjacency Lists/Maps/Sets

(def G {
   :a #{:b :c},
   :b #{:d},
   :c #{:d},
   :d #{}})

(defn is-node [g x]
    (contains? g x))
(defn is-edge [g x y]
  (contains? (g x) y))

(is-node G :a) ;; => true.
(is-edge G :a :b) ;; => true
(is-edge G :a :e) ;;=> false

Generating Random Graphs

We generate a random graph by generating an n-vector of random sets. We will use
Clojure’s conj[oin] or assoc[iate] functions, which will add new data to sets, maps and vectors.

(def nodes (range n))

(defn empty-graph [n]
 (vec (repeat n #{})))

(defn add-directed-edge [g n1 n2]
 (let [n1-neighbors (g n1)]
   (assoc g n1 (conj n1-neighbors n2))))

(defn add-edge [g [n1 n2]]
 (-> g
     (add-directed-edge n1 n2)
     (add-directed-edge n2 n1)))

;The random generation is easy:
(defn random-edge [n]
  (vector (rand-int n) (rand-int n)))

;(add-edge (empty-graph 5) (random-edge 5))
;;=> [#{} #{} #{4} #{} #{2}]

(defn add-rand-edge [g]
    (add-edge g (random-edge (count g))))
; A lazy sequence of an
; evolving random graph:
(take 5 (iterate add-rand-edge (empty-graph 5)))
;([#{} #{} #{} #{} #{}   [#{} #{} #{} #{4} #{3}]
; [#{0} #{} #{} #{4} #{3}]  [#{0} #{} #{4} #{4} #{2 3}]
; [#{0} #{} #{4} #{4} #{2 3}])

(defn random-graph-a [n e] 
     (last (take e (iterate add-rand-edge (empty-graph n)))))

(random-graph-a 10 15)
; [#{4 6 8} #{2 9 8} #{7 1 2} #{7} #{0} #{9} #{0 8} #{3 2 8} #{0 7 1 6} #{1 5}]

An alternative implementation uses reduce, which takes a binary function/operation and a list and applies the function to running (sum) operation scanning each successive element.

(defn random-graph-b [n e] 
    (reduce add-edge (empty-graph n)
       (for [i (range e)] (random-edge n))))

(random-graph-b 5 6)
;=>[#{3 4} #{4} #{3 4} #{0 2 4} #{0 1 2 3}]

Random Regular Graphs
Regular graphs have the same degree d at each vertex. I think the simplest and most efficient way to simulate the random connection process in a functional manner is to start by generating a shuffled list of d copies of each vertices (this represents the d legs for each vertex), and then pair them up using partition. At this point you have a list of all the undirected edges, so you just add them to your graph. This process should work with any graph representation.

So if your vertices are numbered 0 through 3, and you want 3 edges coming out from each vertex, you begin by shuffling the list:
[0 1 2 3 0 1 2 3 0 1 2 3]
into something like:
[2 1 3 0 3 0 2 2 0 3 1 1]
Then partition this into:
[[2 1] [3 0] [3 0] [2 2] [0 3] [1 1]]
These are your 6 undirected edges which you store in your graph however you like.

For demonstration purposes, consider a graph representation where an undirected edge is stored as two directed edges, vertex ids are numbers in (range number-of-nodes), and the graph is just a vector that associates vertex ids with vectors of ids you can get to via outgoing directed edges.

(defn random-regular-graph [n d] 
   (reduce add-edge (empty-graph n)     
      (partition 2
          (shuffle (take (* n d)  
              (cycle (range n)))))))

;(random-regular-graph 20 4)
;[#{1 10 16 18} #{0 3 11 12} #{4 9 12 13} #{1 8 16} #{2 5 11 18} #{4 10 13 15} #{13 14 17}
; #{8 9 11 14} #{3 7 10} #{2 7 16 19} #{0 5 8 12} #{1 4 7 15} #{1 2 10 17} #{2 5 6} #{6 7 16 18}
; #{5 11 17 19} #{0 3 9 14} #{6 12 15 18} #{0 4 14 17} #{9 15 19}]

Testing Connectivity in Random Graphs

Our simple data structure to test random graphs for connectivity will be a parent map-or pmap for short. A pmap will use all nodes for keys and their parent as the values. The value will be the label of the smallest node they are connected to. All nodes that point to the same parent are in the same connected component, and these connected components form disjoint sets. This data structure is analogous to that used in classic Union-Find algorithm.

;; In our initial parent-map, every node is pointing to itself, and represents n disjoint sets with nothing joined.

(defn initial-parent-map [n]  (apply hash-map (mapcat (fn[x][x x]) (range n))))

;; (def initial-pmap (initial-parent-map 10))
;; initial-pmap => {0 0, 7 7, 1 1, 4 4, 6 6, 3 3, 2 2, 9 9, 5 5, 8 8}

;;Given a random edge [a b], we join the 2 nodes in parent-map by comparing their parents.
;;Every node connected to the larger labelled parent will be reset to point to the smaller labeled parent.

(defn join [parent-map [a b]]
   (let [parent-of-a (parent-map a)
         parent-of-b (parent-map b)
         larger-parent (if (< parent-of-a parent-of-b) parent-of-b parent-of-a)
         smaller-parent(if (< parent-of-a parent-of-b) parent-of-a parent-of-b)  ]
           (into {}
                (map (fn[[n1 n1parent]]
                       (if (= n1parent larger-parent) [n1 smaller-parent] [n1 n1parent]))
                 parent-map))))

;; (join initial-pmap [1 2]) => {0 0, 7 7, 1 1, 4 4, 6 6, 3 3, 2 1, 9 9, 5 5, 8 8}
;; (reduce join initial-pmap [[ 1 2] [2 3] [3 4]]) => {0 0, 7 7, 1 1, 4 1, 6 6, 3 1, 2 1, 9 9, 5 5, 8 8}

(defn nodes-joined? [parent-map a b]
    (= (parent-map a)(parent-map b)))

;; To test connectivity we simply see if all parents are 0
(defn pmap-allconnected? [pmap]
  (= 0 (reduce + (map pmap (range (count pmap))))))

(defn add-rand-edge-pmap [pmap] (join pmap (random-edge (count pmap))))

;; An experiment generates the connected components of a random graph
;; with specified num-nodes and num-edges and is true if graph is connected, false otherwise.

(defn connectexperiment [num-nodes num-edges]
  (pmap-allconnected?  (last (take num-edges
                   (iterate add-rand-edge-pmap (initial-parent-map num-nodes))))))

;;(connectexperiment 10 23) => true
;;(connectexperiment 10 23) => false
;;(connectexperiment 100 460) => false
;;(connectexperiment 100 460) => true

The model of adding random edges to an evolving graph is call  Erdos-Renyi model and there are several associated theorems that can be give insight into the structural properties given a certain ratio of p of nodes to edges. One result on connectivity shows there is a critical threshold ratio between num-nodes and num-edges. If E >> N*log(N) then random graph is almost surely connected. And if E << N*log(N) then random graph is almost surely disconnected.

GIANT COMPONENTS in Uniform Random Graphs
In an evolving random graph a giant component is formed when > 50% of vertices are connected to each other.

Erdös-Renyi show that as N becomes large:
– If p 1/N, probability of a giant component goes to 1
• Note: at edge density p, expected/average degree is p(N-1) ~ pN
• So at p ~ 1/N, average degree is ~ 1: sparse
• So model “explains” giant components in certain real networks

For our experiments we will consider the canonical parent-map, where each node is mapped to its smallest labeled neighbor. We will simply look at the histogram, or in clojure apply the frequencies function, and identify the largest component using max-key function.

(defn giantexp [num-nodes num-edges]
  (vals  (last (take num-edges
                     (iterate add-rand-edge-pmap (initial-parent-map num-nodes))))))

(giantexp 10 10) ; => (0 0 0 0 0 3 0 0 0 0)
; a giant component with 9/10 nodes connected

(frequencies (giantexp 20 20)); {0 13, 1 4, 17 1, 3 1, 14 1}
; there are 5 components with largest size 13, which is 65% > 50% so it is a giant.

; Lets look at larger experiments:
(apply max-key  val (frequencies (giantexp 1000 1000))) ;=> [1 802]
(apply max-key  val (frequencies (giantexp 10000 10000))) ; => [0 7943]

So our experiments suggest that giant components of 80% of all nodes evolve when #edges = #nodes.