Class: Louvian::Graph

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

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(edges_list, directed, level) ⇒ Graph

Returns a new instance of Graph.



4
5
6
7
8
9
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
 
# File 'lib/louvian/graph.rb', line 4

def initialize edges_list, directed, level
  # Adjacency list
  @adj_list = Louvian::Graph.make_adj edges_list, directed

  # List of all nodes
  # TODO remove sort
  @nodes = @adj_list.keys.sort

  # List of all communities (meta_nodes)
  @communities = []

  # whether the graph is diercted or not
  @directed = false

  # node_id => community_id
  @n2c = {}

  @level = level
  # TODO remove sort
  @adj_list.sort.each do |k, v|
    @communities << Louvian::Community.new({k => v}, @level)
    @n2c[k] = @communities.last.id
  end

  # Sum of all links half edges (double the number of edges)
  #@total_weight = @adj_list.inject(0) {|r,(k,v)| r+v.count}
  @total_weight = 0
  @adj_list.each do |node, links|
    @total_weight += links.values.inject(0, :+)
  end
end

Instance Attribute Details

#adj_list ⇒ Object

Returns the value of attribute adj_list.



3
4
5
 
# File 'lib/louvian/graph.rb', line 3

def adj_list
  @adj_list
end

#communities ⇒ Object

Returns the value of attribute communities.



3
4
5
 
# File 'lib/louvian/graph.rb', line 3

def communities
  @communities
end

#directed ⇒ Object

Returns the value of attribute directed.



3
4
5
 
# File 'lib/louvian/graph.rb', line 3

def directed
  @directed
end

#level ⇒ Object

Returns the value of attribute level.



3
4
5
 
# File 'lib/louvian/graph.rb', line 3

def level
  @level
end

#n2c ⇒ Object

Returns the value of attribute n2c.



3
4
5
 
# File 'lib/louvian/graph.rb', line 3

def n2c
  @n2c
end

#nodes ⇒ Object

Returns the value of attribute nodes.



3
4
5
 
# File 'lib/louvian/graph.rb', line 3

def nodes
  @nodes
end

#total_weight ⇒ Object

Returns the value of attribute total_weight.



3
4
5
 
# File 'lib/louvian/graph.rb', line 3

def total_weight
  @total_weight
end

Class Method Details

.make_adj(edges_list, directed) ⇒ Object

This method builds the adjacency list from list of edges

Parameters:

  • list (Array) —

    in the form of [src dest] (edge per cell)

  • directed, —

    whether the edge list is directed or not

Returns:

  • hash of hashes => {dest1 => weight1, dest1 => weight1}



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

def self.make_adj edges_list, directed
  adj = {}
  edges_list.each do |edge|
    adj[edge[0]] ||= {}

    adj[edge[1]] ||= {}

    adj[edge[0]][edge[1]] = (adj[edge[0]][edge[1]] || 0 ) + (edge[2] || 1)
    if not directed
      adj[edge[1]][edge[0]]  = (adj[edge[1]][edge[0]] || 0 ) + (edge[2] || 1)
    end
  end
  adj
end

Instance Method Details

#build_graph_from_comms ⇒ Object 



157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
 
# File 'lib/louvian/graph.rb', line 157

def build_graph_from_comms
  comm_edges = []

  @communities.each do |comm|
    comm.nodes_ids.each do |node|
      @adj_list[node].each do |linked_node, weight|
        if not comm.nodes_ids.include? linked_node
          #comm_edges << [comm.id, @n2c[linked_node]] * weight
          comm_edges << [comm.id, @n2c[linked_node], weight]
        end
      end
    end
    comm_edges << [comm.id, comm.id, comm.in]
  end
  return Louvian::Graph.new comm_edges, true, @level+1
end

#display_communities ⇒ Object

This method outputs information about communities



125
126
127
128
129
130
 
# File 'lib/louvian/graph.rb', line 125

def display_communities
  @communities.each do |m|
    puts "#{m.id} => #{m.nodes_ids} in=#{m.in} tot=#{m.tot}"
  end
  nil
end

#expand!(lower_graph) ⇒ Object 



174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
 
# File 'lib/louvian/graph.rb', line 174

def expand! lower_graph
  comm_2_nodes = lower_graph.communities.inject({}) {|r,comm| r[comm.id]= comm.nodes_ids;r}
  new_graph_nodes = []
  @communities.each do |comm|
    new_comm_nodes = []
    comm.nodes_ids.each do |node|
      new_comm_nodes += comm_2_nodes[node]
      comm_2_nodes[node].each do |low_node|
        @n2c[low_node] = comm.id
      end
    end
    comm.nodes_ids = new_comm_nodes
    new_graph_nodes += new_comm_nodes
  end
  @nodes = new_graph_nodes
end

#garbage_collect(community) ⇒ Object 



151
152
153
154
155
 
# File 'lib/louvian/graph.rb', line 151

def garbage_collect community
  if  community.nodes_ids.empty?
    @communities.delete community
  end
end

#get_community(node) ⇒ Object 



65
66
67
 
# File 'lib/louvian/graph.rb', line 65

def get_community node
  @communities.find {|comm| comm.id == @n2c[node]}
end

#get_links_from_comm_to_node(community, node) ⇒ Object 



132
133
134
135
136
137
138
139
 
# File 'lib/louvian/graph.rb', line 132

def get_links_from_comm_to_node community, node
  links = 0
  nodes = community.nodes_ids - [node]
  nodes.each do |n|
    links+=@adj_list[n].select {|adj| adj == node}.values.inject(0,:+)
  end
  links
end

#get_neighbour_comms(node) ⇒ Object 



59
60
61
62
63
 
# File 'lib/louvian/graph.rb', line 59

def get_neighbour_comms node
  node_to_comms_links = get_node_to_comms_links node

  neighbour_communities = @communities.find_all {|comm| node_to_comms_links.include? comm.id}
end

#get_neighbour_nodes(node) ⇒ Object 



55
56
57
 
# File 'lib/louvian/graph.rb', line 55

def get_neighbour_nodes node
  neighbours = adj_list[node]
end

#get_node_to_comms_links(node) ⇒ Object

This method gets all neighbour communities and the number of links from node to all neighbou communities to community}

Parameters:

  • node —

    to be considered



74
75
76
77
78
79
80
81
82
 
# File 'lib/louvian/graph.rb', line 74

def get_node_to_comms_links node
  neighbour_nodes = get_neighbour_nodes node
  node_to_comms_links = {}
  neighbour_nodes.each do |n, weight|
    node_to_comms_links[@n2c[n]] = (node_to_comms_links[@n2c[n]] || 0) + weight
  end
  node_to_comms_links[@n2c[node]] ||= 0
  return node_to_comms_links
end

#get_number_of_links(from_node, to_comm) ⇒ Object

OPTIMIZE



85
86
87
 
# File 'lib/louvian/graph.rb', line 85

def get_number_of_links from_node, to_comm
  get_node_to_comms_links(from_node)[to_comm.id]
end

#insert_node(node, comm) ⇒ Object 



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

def insert_node node, comm
  comm.insert node, @adj_list[node], (get_links_from_comm_to_node comm, node)
  @n2c[node] = comm.id
end

#modularity(verbose = false) ⇒ Object

This method calcualtes the current modularity of the communities



91
92
93
94
95
96
97
98
99
100
 
# File 'lib/louvian/graph.rb', line 91

def modularity verbose=false
  q = 0.0
  m2 = @total_weight
  puts "m2 #{m2},  comms #{@communities.count}" if verbose
  @communities.each do |comm|
    puts " in #{comm.in}, tot #{comm.tot}"  if verbose
    q += comm.in.to_f/m2 - (comm.tot.to_f/m2 * comm.tot.to_f/m2)
  end
  q
end

#modularity_gain(node, community) ⇒ Object

This method calcualtes the modularity gain for moving node to community

Parameters:

  • node —

    this is the node to be moved

  • community —

    this is the destination community

  • nb_links_to_comm —

    is the number of links from node to community



107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
 
# File 'lib/louvian/graph.rb', line 107

def modularity_gain node, community
  nb_links_to_comm = (get_number_of_links node, community) || 0
  #puts "node #{node}, comm #{community.id}"
  #puts "####################{nb_links_to_comm}"

  tot = community.tot
  deg = @adj_list[node].values.inject(0,:+)
  m2 = @total_weight

  #puts "\t\t\tcomm #{community.id} #{[tot, deg, m2, nb_links_to_comm]}"
  # what makes sense
  #return (nb_links_to_comm.to_f/m2) - (tot * deg.to_f/m2**2/2)

  # copied from the cpp code
  return nb_links_to_comm.to_f - tot*deg.to_f/m2
end

#remove_node(node, comm) ⇒ Object 



146
147
148
149
 
# File 'lib/louvian/graph.rb', line 146

def remove_node node, comm
  comm.remove node, @adj_list[node], (get_links_from_comm_to_node comm, node)
  @n2c[node] = -1
end