Generating Barabasi-Albert Model Random Graphs in Clojure

Generating an Evolving Class of Random Graphs Obtained by Preferential Attachment

The Barabási–Albert (BA) random graph model is an algorithm for generating random scale-free networks using a preferential attachment mechanism. To implement preferential attachment we will need to turn the distribution of the degree of nodes into a probabilty. This is done via normailization.

(defn normalize  [freq]
  (let [sum (apply + (vals freq))]
    (into {} (for [[k v] freq]
                  [k (/ v sum)]))))

(defn normal [coll]
  (normalize (frequencies coll)))

(def dice-pair
(normal '(2 3 3 4 4 4 5 5 5 5 6 6 6 6 6 7 7 7 7 7 7 8 8 8 8 8 9 9 9 9 10 10 10 11 11 12)))

dice-pair
; => {2 1/36, 3 1/18, 4 1/12, 5 1/9, 6 5/36, 7 1/6, 8 5/36, 9 1/9, 10 1/12, 11 1/18, 12 1/36}

We want to turn a uniform random number into a selection (of a node in a graph) from a non-uniform distribution. To wit, we select an item at random based on the cumulative distribution of the distribution we are given. The cumulative distribution is just all initial sums of the individual densities, and is computed via a sum reductions (or sum scan). Then, in a two step process, of first choosing a uniform random number y in interval [0,1), and second using y to index the cumulative sums, we determine the selected element. This is a special case of what we will call a scan. Scans (called reductions in clojure (poorly chosen)) are highly useful functional primitives, and particularly useful in parallel computing. Here is sample usage.

;(reductions f coll)
;(reductions f init coll)
;;Returns a lazy seq of the intermediate values of the reduction (reduce) of coll by binary func f.

(reductions + '( 1 2 3 4 5)) ; => (1 3 6 10 15)
(reductions max '( 1 3 5 2 4 6 8)) ; => (1 3 5 5 5 6 8)

We will generate random graphs iteratively by adding one node at a time and then add edges to that new node by applying the select function, where the probability of selecting any particular edge is proportional to the degree of the attaching node.

The Barabasi-Albert BA model starts with a small complete graph, then repeatedly adds new nodes with each new node initializing a connection to k neighbors via the weighted random selection described now in detail.

Details of Weighted Selection (the select function):
1. do a scan on the normalized probabilities to get a cumulative probability distribution.
2. choose random number y in the interval [0,1)
3. find the position of first scan value that is greater than y by counting ct the number of scans-values less than y
4. use that (less-than y) count as index into vector of keys to select the random element

(defn select [prob]
  (let [keys  (vec (for [[k v] prob] k))
        vals  (for [[k v] prob] v)
        scan  (reductions + vals)
        y     (rand)
        tlist (map (fn[x] (< x y)) scan)
        indxfn (fn ct [lst] (cond (empty? lst) 0
                                    (= (first lst) false) 0
                                    :else (inc (ct (rest lst)))))
        indx (indxfn tlist)]

        (keys indx)))

; we can define a dice roll function by simply selecting from the dice-pair normalized distribution. 

(defn roll []  (select pair-dice))

(into (sorted-map)
      (normal (for [i (range 1000)] (roll))))

; Validation 

(defn roll [] (select dice-pair))
(for [i (range 10)] (roll))  ;=>  (11 9 3 2 6 6 5 12 4 7)

(frequencies (for [i (range 3600)] (roll))))
;=>{2 86, 3 218, 4 289, 5 392, 6 531, 7 584, 8 468, 9 432, 10 323, 11 178, 12 99}

(into (sorted-map)
(normal (for [i (range 1000)] (roll))))
;=> {2 21/500, 3 53/1000, 4 37/500, 5 53/500, 6 141/1000, 7 93/500, 8 137/1000, 9 99/1000, 10 77/1000, 11 53/1000, 12 4/125}

Let’s use these ideas to generate a class of “rich-get-richer” graphs with preferential attachment by using the function select above to select a random edge in Barabasi-Albert sense of using the normalized degree distribution. We call the function “select-Social-rand-edge”. As an experiment in preferential attachment models, we contrast the Barabasi-Albert random graph with the “poor-get-richer” graph in which attachment probability is inversely proportional to the degree of a node. We define a function “select-AntiSocial-rand-edge” that selects edges at random with this inverted probability distribution. We consider the variance of these two random graph models.

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

; generating edge lists for a complete graph
; (for [i (range 4)  j (range 4) :when (not= i j)] [i j]) =>
; ([0 1] [0 2] [0 3] [1 0] [1 2] [1 3] [2 0] [2 1] [2 3] [3 0] [3 1] [3 2])

(defn complete-graph [n]
  ( let [edge-list  (for [i (range n)  j (range n) :when (not= i j)] [i j])]
    (reduce add-edge (empty-graph n) edge-list)))

;(complete-graph 4); =>[#{1 3 2} #{0 3 2} #{0 1 3} #{0 1 2}]

(defn degree-dist [g]
  (zipmap (range (count g)) (map  count g) ))

;(degree-dist (random-graph-a 10 15) ) ;=> {0 3, 7 1, 1 4, 4 2, 6 1, 3 1, 2 3, 9 1, 5 2, 8 5}

;selecting edges for preferential attachment

(defn select-Social-rand-edge [g]
  (let [choice (select (normalize (degree-dist g )))]
    (vector  (count g) choice) ))

(defn select-AntiSocial-rand-edge [g]
  (let [ invprob (fn[p] (into {} (for [[k v] p] [k (/ 1 v)])))
        choice (select (normalize (invprob (degree-dist g ))))]
    (vector  (count g) choice) ))

(defn random-Social-graph [n k]
   (cond
    (= n k)  (complete-graph k)
    :else
      (let [ g (random-Social-graph (dec n) k)
            edge-list (for [i (range k)] (select-Social-rand-edge g ))]
      (reduce add-edge  (assoc g (count g) #{}) edge-list))))

(defn random-AntiSocial-graph [n k]
   (cond
    (= n k)  (complete-graph k)
    :else
      (let [ g (random-AntiSocial-graph (dec n) k)
            edge-list (for [i (range k)] (select-AntiSocial-rand-edge g ))]
      (reduce add-edge  (assoc g (count g) #{}) edge-list))))

(defn sorted-dd [dd]
    (into (sorted-map-by (fn [key1 key2]
                           (compare [(get dd key2) key2]
                                    [(get dd key1) key1])))  dd))

;(sorted-dd dd)=>  {2 51, 10 41, 0 36, 5 35, 8 27, 6 27, 4 26, 11 24, 1 24, 7 21, 30 20, ...

(defn avg-deg [dd] (/ (reduce + (vals dd)) (count dd)))

(defn variance [dd]
 (let [ mean (avg-deg dd) ]
    (/  (reduce +   (map (fn[v] (*  (- mean v) (- mean v))) (vals dd))) (count dd)))) 


(float  (variance (degree-dist (random-Social-graph 200 3)))) ;=> 45.907
(float  (variance (degree-dist (random-Social-graph 1000 3)))) ;=> 48.057
(float  (variance (degree-dist (random-AntiSocial-graph 200 3)))) ;=> 4.9639
(float  (variance (degree-dist (random-AntiSocial-graph 1000 3)))) ;=> 5.9955
(float  (variance (degree-dist (random-Social-graph 1000 10))));=>
275.61063
(float  (variance (degree-dist (random-AntiSocial-graph 1000 10))));=> 49.900845

Homework Project: Another popular model of generating random social networks is the Watts-Strogatz model:
http://en.wikipedia.org/wiki/Watts_and_Strogatz_model
In this project you will implement a “rich-get-richer” variant of the Watts-Strogatz model in which the random attachment edges are selected with a non-uniform distribution preferring attachment to nodes with higher degree. You should implement a function
(defn random-Watts-Strogatz-Social-graph [n k] ...)
that returns a random graph with n nodes and average degree k that accurately reflects the Watts-Strogatz model.

A Python Implementation
For the benefit of readers I have included below the python code available at the networkx.lanl.gov website.

def barabasi_albert_graph(n, m, seed=None):
    """Return random graph using Barabási-Albert preferential attachment model.
        
    A graph of n nodes is grown by attaching new nodes each with m
    edges that are preferentially attached to existing nodes with high
    degree.
    
    Parameters
    ----------
    n : int
        Number of nodes
    m : int
        Number of edges to attach from a new node to existing nodes
    seed : int, optional
        Seed for random number generator (default=None).   

    Returns
    -------
    G : Graph
        
    Notes
    -----
    The initialization is a graph with with m nodes and no edges.

    References
    ----------
    .. [1] A. L. Barabási and R. Albert "Emergence of scaling in
       random networks", Science 286, pp 509-512, 1999.
    """
        
    if m < 1 or  m >=n:
        raise nx.NetworkXError(\
              "Barabási-Albert network must have m>=1 and m<n, m=%d,n=%d"%(m,n))
    if seed is not None:
        random.seed(seed)    

    # Add m initial nodes (m0 in barabasi-speak) 
    G=empty_graph(m)
    G.name="barabasi_albert_graph(%s,%s)"%(n,m)
    # Target nodes for new edges
    targets=list(range(m))
    # List of existing nodes, with nodes repeated once for each adjacent edge 
    repeated_nodes=[]     
    # Start adding the other n-m nodes. The first node is m.
    source=m 
    while source<n: 
        # Add edges to m nodes from the source.
        G.add_edges_from(zip(*m,targets)) 
        # Add one node to the list for each new edge just created.
        repeated_nodes.extend(targets)
        # And the new node "source" has m edges to add to the list.
        repeated_nodes.extend(*m) 
        # Now choose m unique nodes from the existing nodes 
        # Pick uniformly from repeated_nodes (preferential attachement) 
        targets = _random_subset(repeated_nodes,m)
        source += 1
    return G