Class: MOSAIK::Algorithms::Louvain
- Inherits:
-
MOSAIK::Algorithm
- Object
- MOSAIK::Algorithm
- MOSAIK::Algorithms::Louvain
- Defined in:
- lib/mosaik/algorithms/louvain.rb
Overview
Louvain method for community detection (Blondel et al., 2008)
Constant Summary collapse
- EPSILON =
Threshold of modularity improvement
1e-6
Instance Attribute Summary
Attributes inherited from MOSAIK::Algorithm
Instance Method Summary collapse
Methods inherited from MOSAIK::Algorithm
Constructor Details
This class inherits a constructor from MOSAIK::Algorithm
Instance Method Details
#call ⇒ Object
14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 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 90 91 92 93 94 95 96 97 98 99 100 |
# File 'lib/mosaik/algorithms/louvain.rb', line 14 def call # Store the original graph original_graph = graph # Initialize modularity modularity = nil # Final mapping of vertices to communities mapping = graph .vertices .keys .index_with { |vertex_id| vertex_id } # Iterate until no further improvement in modularity 1.step do |i| # Assign initial set of communities (each vertex in its own community) graph.vertices.each_value do |vertex| graph .add_cluster(vertex.id) .add_vertex(vertex) end # Calculate and print initial modularity on first iteration if modularity.nil? modularity = modularity_for(graph) info "Initial modularity: #{modularity}" end debug "Iteration #{i}: start modularity=#{modularity}, vertices=#{graph.vertices.count}, communities=#{graph.clusters.count}" # Phase 1: reassign vertices to optimize modularity progress = ProgressBar.create( title: "Reassigning vertices", total: graph.vertices.size, length: 80, format: "%t%e [%b>%i] %p%%".cyan, output: [:debug] ? $stderr : File.open(File::NULL, "w"), ) graph.vertices.each_value do |vertex| progress.increment reassign_vertex(graph, vertex) end # Phase 2: reduce communities to a single node debug "Reducing graph" g, reduced_mapping = reduce_graph(graph) debug "Reduced #{graph.vertices.size} vertices to #{g.vertices.size} vertices" if [:visualize] MOSAIK::Graph::Visualizer .new(, g) .to_svg("louvain_#{i}") end # Merge the reduced mapping with the original mapping mapping = mapping.transform_values { |v| reduced_mapping[v] } # Calculate final modularity final_modularity = modularity_for(graph) debug "Iteration #{i}: end modularity=#{final_modularity}, vertices=#{graph.vertices.count}, communities=#{graph.clusters.count}" # Stop iterating if no further improvement in modularity break if final_modularity - modularity <= EPSILON # Update modularity modularity = final_modularity # Update the reduced graph @graph = g end info "Final modularity: #{modularity}" # Copy the final communities to the original graph original_graph.clusters.clear mapping.each do |vertex_id, community_id| original_graph .find_or_add_cluster(community_id) .add_vertex(original_graph.find_vertex(vertex_id)) end end |