Module: RandomGraph::RandomGenerators

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

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)



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

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

   possible_edges = n * (n - 1) / 2

   fail ArgumentError.new('too many edges') if m > possible_edges

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

   # for every edge
   (0...m).each do |i|
     valid_edge = false
     from = 0
     to = 0
     begin
      # select a random number, representing on of the possible edges
      from = rand(0...n)
      to = rand(0...n)
      valid_edge = !g.edge?(from, to) && (from != to)
    end until valid_edge == true
     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



40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
# File 'lib/random_graph/random_generators.rb', line 40

def erdos_renyi_gnp(n, p)
  fail ArgumentError.new('must have positive number of nodes') if n < 0
  fail ArgumentError.new('need positive probability') if p < 0
  fail ArgumentError.new('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 



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

def preferential_attachment(size)
  fail ArgumentError.new('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 



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



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
90
91
92
 
# File 'lib/random_graph/random_generators.rb', line 57

def watts_strogatz(n, k, b)
  fail ArgumentError.new('must have positive number of nodes') if n < 0
  fail ArgumentError.new('invalid beta parameter') if b < 0 || b > 1
  fail ArgumentError.new('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