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
 
# 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}
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

#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



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

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

    adj[edge[0]] << edge[1]
    if not directed
      adj[edge[1]] << edge[0]
    end
  end
  adj
end

Instance Method Details

#build_graph_from_comms ⇒ Object 



138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
 
# File 'lib/louvian/graph.rb', line 138

def build_graph_from_comms

  comm_edges = []

  count = @communities.count
  if not directed # iterate only on one half of communities
    count % 2 == 0 ?  count : count + 1
    count /=2
  end

  @communities[0,count].each do |comm|
    comm.nodes_ids.each do |node|
      @adj_list[node].each do |linked_node|
        if not comm.nodes_ids.include? linked_node
          comm_edges << [comm.id, @n2c[linked_node]]
        end
      end
    end
  end
  return Louvian::Graph.new comm_edges, directed, @level+1
end

#display_communities ⇒ Object

This method outputs information about communities



115
116
117
118
119
120
 
# File 'lib/louvian/graph.rb', line 115

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

#garbage_collect(community) ⇒ Object 



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

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

#get_community(node) ⇒ Object 



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

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

#get_neighbour_comms(node) ⇒ Object 



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

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 



49
50
51
 
# File 'lib/louvian/graph.rb', line 49

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



68
69
70
71
72
73
74
75
76
 
# File 'lib/louvian/graph.rb', line 68

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

#get_number_of_links(from_node, to_comm) ⇒ Object

OPTIMIZE



79
80
81
 
# File 'lib/louvian/graph.rb', line 79

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 



122
123
124
125
 
# File 'lib/louvian/graph.rb', line 122

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

#modularity ⇒ Object

This method calcualtes the current modularity of the communities



85
86
87
88
89
90
91
92
93
 
# File 'lib/louvian/graph.rb', line 85

def modularity
  q = 0.0
  m2 = @total_weight

  @communities.each do |m_node|
    q += m_node.in.to_f/m2 - (m_node.tot.to_f/m2 * m_node.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



100
101
102
103
104
105
106
107
108
109
110
111
112
 
# File 'lib/louvian/graph.rb', line 100

def modularity_gain node, community
  nb_links_to_comm = get_number_of_links node, community
  tot = community.tot
  deg = @adj_list[node].count
  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 



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

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