Class: Louvian

Inherits:
Object
  • Object
show all
Defined in:
lib/louvian.rb

Defined Under Namespace

Classes: Community, Graph

Constant Summary collapse

MIN_INCREASE = 
0.000001

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(tuples, directed) ⇒ Louvian

This method sets up the whole environemnt for calculations

Parameters:

  • string (String) —

    in the form of src dest (one edge per line)



12
13
14
15
16
 
# File 'lib/louvian.rb', line 12

def initialize tuples, directed
  #list = string.split("\n").map {|line| line.split.map{|n| n.to_i}}
  @graph = Graph.new tuples, directed, 0
  @levels = [] # List of Graphs
end

Class Method Details

.example(s = nil) ⇒ Object 



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

def self.example s=nil
  s ||='0 1 1
  0 8 1
  1 3 1
  1 4 1
  1 8 1
  2 3 1
  2 5 1
  2 7 1
  3 8 1
  4 7 1
  5 6 1
  5 7 1'
  list = self.make_list_from_string s

  l = Louvian.new(list, false)
  #l.one_level
  #ng = l.graph.build_graph_from_comms
  #l.levels << l.graph
  #l.graph = ng
  l.run
  return l
end

.make_list_from_string(s) ⇒ Object 



141
142
143
 
# File 'lib/louvian.rb', line 141

def self.make_list_from_string s
  list = (s.split("\n").map {|line| line.split.map{|n| n.to_i}})
end

Instance Method Details

#display_hierarchy ⇒ Object 



57
58
59
60
61
62
 
# File 'lib/louvian.rb', line 57

def display_hierarchy
  @levels.each do |graph|
    puts "level #{graph.level}: Nodes #{graph.communities.count}"
  end
  nil
end

#graph ⇒ Object 



18
19
20
 
# File 'lib/louvian.rb', line 18

def graph
  @graph
end

#graph=(value) ⇒ Object 



22
23
24
 
# File 'lib/louvian.rb', line 22

def graph= value
  @graph = value
end

#levels ⇒ Object 



26
27
28
 
# File 'lib/louvian.rb', line 26

def levels
  @levels
end

#levels=(value) ⇒ Object 



30
31
32
 
# File 'lib/louvian.rb', line 30

def levels= value
  @levels = value
end

#one_level ⇒ Object

This method iterates over the graph to optimze the modularity. Iterations stops when there are no possible moves anymore.



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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
 
# File 'lib/louvian.rb', line 67

def one_level
  improvement = false
  nb_passes = 0
  cur_mod = @graph.modularity
  new_mod = cur_mod
  begin
    #puts "Iterating"
    #puts "modularity is #{@graph.modularity}"
    cur_mod = new_mod
    nb_moves = 0
    nb_passes += 1
    @graph.nodes.shuffle.each do |node|
      #puts "\t#{@graph.n2c}"
      #puts "\tconsidering node #{node}"
      orig_community = @graph.get_community node

      neighbour_communities = @graph.get_neighbour_comms node

      #puts "\tneihbours#{neighbour_communities.map {|i| i.id}} origin #{orig_community.id}"
      @graph.remove_node node, orig_community


      best_community = orig_community
      max_gain = 0.0

      neighbour_communities.each do |comm|
        mod_gain = @graph.modularity_gain node, comm
        #puts "\t\tfor comm #{comm.id} mod increase is #{mod_gain}"
        if mod_gain > max_gain
          max_gain = mod_gain
          best_community = comm
        end
      end
      if best_community != orig_community
        nb_moves += 1
        improvement = true
        #puts "\t\tbest comm #{best_community.id}"
      end

      @graph.insert_node node, best_community

      @graph.garbage_collect orig_community

    end
    new_mod = @graph.modularity
    #puts "modularity was #{cur_mod} and now #{new_mod}, moves #{nb_moves}"
  end while  nb_moves > 0 and new_mod - cur_mod >= MIN_INCREASE
  return improvement
end

#run(verbose = false) ⇒ Object 



34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
# File 'lib/louvian.rb', line 34

def run verbose=false
  l = 0
  puts "Level #{l}: Comms #{@graph.communities.size}" if verbose
  l +=1

  while self.one_level
    puts "Level #{l}: Comms #{@graph.communities.size}" if verbose
    @levels << @graph
    @graph = @graph.build_graph_from_comms

    l+=1
  end
  self
end

#unfold_levels! ⇒ Object 



49
50
51
52
53
54
55
 
# File 'lib/louvian.rb', line 49

def unfold_levels!
  return false if @levels.size < 2
  @levels[(1..-1)].each_with_index do |graph, i|
    graph.expand! @levels[i]
  end
  true
end