Module: RandomGraph::RandomGenerators

Included in:
Graph
Defined in:
lib/random_graph/random_generators.rb

Overview

implements random graph generators

Instance Method Summary collapse

Instance Method Details

#erdos_renyi_gnm(n, m) ⇒ Object

Select a graph randomly, where all graphs with n nodes and m edges are equally likely to be selected. O(n^2) expected worst-case rumtime, assuming random numbers generated in constant time. Number of random edges probed before adding edge k is (n^2 - n)/(n^2 - n - 2k). Total expected number of probes can be express as a summation, which is upper bounded by O(n^2)



11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
# File 'lib/random_graph/random_generators.rb', line 11

def erdos_renyi_gnm(n, m)
  fail ArgumentError, 'must have positive number of nodes' if n < 0
  fail ArgumentError, 'must have positive number of edges' if m < 0

  possible_edges = n * (n - 1) / 2

  fail ArgumentError, 'too many edges' if m > possible_edges

  # create empty graph
  g = Graph.new(n)

  # for every edge
  (0...m).each do |_i|
    loop do
      # select a random number, representing on of the possible edges
      from = rand(0...n)
      to = rand(0...n)
      break if !g.edge?(from, to) && (from != to)
    end
    g.add_edge(from, to)
  end
  g
end

#erdos_renyi_gnp(n, p) ⇒ Object

Create a graph with n nodes, where all edges have a probability p of existing



37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
# File 'lib/random_graph/random_generators.rb', line 37

def erdos_renyi_gnp(n, p)
  fail ArgumentError, 'must have positive number of nodes' if n < 0
  fail ArgumentError, 'need positive probability' if p < 0
  fail ArgumentError, 'probability cannot be greater than 1!' if p > 1

  # create empty graph
  g = Graph.new(n)
  (0...n**2).each do |i|
    from = i / n
    to = i % n
    g.add_edge(from, to) if rand <= p && to > from
  end
  g
end

#preferential_attachment(size) ⇒ Object

preferential attachement model enforces power law degree distribution



92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
 
# File 'lib/random_graph/random_generators.rb', line 92

def preferential_attachment(size)
  fail ArgumentError, 'invalid number of nodes' if size < 2
  g = Graph.new(2)
  g.add_edge(0, 1)
  total_degree = 2

  (2...size).each do |i|
    g.add_node
    r = rand(1..total_degree)
    j = 0

    loop do
      r -= g.degree(j)
      break if r <= 0
      j += 1
    end
    g.add_edge(i, j)
    total_degree += 2
  end
  g
end

#random_grid(n, p) ⇒ Object

n x n grid, with vertices isolated with probability p



116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
 
# File 'lib/random_graph/random_generators.rb', line 116

def random_grid(n, p)
  fail ArgumentError, 'invalid probability' if p > 1 || p < 0
  g = Graph.new(n**2)
  (0...n**2).each do |i|
    bottom = (i + n) % n**2
    right = (i + 1)
    right -= n if right % n == 0
    g.add_edge(i, bottom)
    g.add_edge(i, right)
  end
  (0...n**2).each do |i|
    next if rand > p
    top = i - n
    top += n**2 if top < 0
    bottom = (i + n) % n**2
    right = i + 1
    right -= n if right % n == 0
    left = i - 1
    left += n if left == -1 || left % n == n - 1
    g.remove_edge(i, top)
    g.remove_edge(i, bottom)
    g.remove_edge(i, left)
    g.remove_edge(i, right)
  end
  g
end

#watts_strogatz(n, k, b) ⇒ Object

creates a watts-strogatz random graph. n represents the number of nodes, k is the mean degree, and b is the beta parameter



54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
 
# File 'lib/random_graph/random_generators.rb', line 54

def watts_strogatz(n, k, b)
  fail ArgumentError, 'must have positive number of nodes' if n < 0
  fail ArgumentError, 'invalid beta parameter' if b < 0 || b > 1
  fail ArgumentError, 'invalid mean degree if' if k > n || k < Math.log10(n)

  # construction of regular ring lattice
  g = Graph.new(n)
  (0...n).each do |i|
    (0...n).each do |j|
      ab = (i - j).abs
      modded = n - 1 - (k / 2)
      checker = ab % modded
      g.add_edge(i, j) if 0 < checker && checker <= (k / 2)
    end
  end

  # rewiring under beta parameter
  (0...n).each do |i|
    (i...n).each do |j|
      # skip non-existent edges
      next unless g.edge?(i, j)
      # rewire from uniform distribution
      if rand < b && g.degree(i) != n - 1
        # skip is node is completely wired
        target = 0
        loop do
          target = rand(0...n)
          break if target != i && !g.edge?(i, target)
        end
        g.remove_edge(i, j)
        g.add_edge(i, target)
      end
    end
  end
  g
end