Ruby implementation of the algorithm described by Jia & Barabasi to obtain a score on how "driver" is a node of a graph

algorithm.rb

# This set of classes implement the algorithm described in
# > Jia, T., & Barabási, A. L. (2013).
# > Control capacity and a random sampling method in exploring controllability of complex networks.
# > Scientific reports, 3.
#
# This algorithm obtains a score for each node of a network telling how 'driver' it is
# i.e. What is the chance this node is in a set of nodes that can control the whole network
#
# Look at the test files to see how to run this algorithm
#
# Requirements: Ruby 2.1.2 or higher. No gem has been used.
require 'set'

class MMS
  attr_accessor :nodes, :edges

  def initialize nodes = [], edges = []
    self.nodes = nodes
    self.edges = edges
  end

  def dup
    MMS.new self.nodes.dup, self.edges.dup
  end

  def inspect
    "{ Nodes: #{self.nodes.inspect}, Edges: #{self.edges.inspect} }"
  end

  def eql? other_mms
    return false unless other_mms.is_a? MMS
    (other_mms.nodes == self.nodes) && (other_mms.edges == self.edges)
  end

  def hash
    self.nodes.hash + self.edges.hash
  end

end

class ControllabilityScoreAlgorithm

  # Algorithm to get a maximum match set
  def mms graph
    mms = MMS.new
    # for each node on the "out" side we get the ins that are not already matched
    # and get one
    graph.each do |out, ins|
      newly_matched = (ins - mms.nodes).sample
      unless newly_matched.nil?
        mms.nodes << newly_matched
        mms.edges << [out, newly_matched]
      end
    end
    mms
  end


  def alternative_mms graph, current_mms, removal_node
    # We get the out node matching the removal node
    out, _ = current_mms.edges.detect{|_, in_node| in_node == removal_node }
    # We remove the removal node from the MMS
    current_mms.nodes.delete removal_node
    current_mms.edges.reject!{|_, in_node| in_node == removal_node }

    # We remove every incoming edge to our removal node
    # We don't remove the node or any outgoing edge as we will need it later
    graph.each do |_, ins|
      ins.delete removal_node
    end

    # We randomize the targets from the out node on the graph
    graph[out].shuffle.each do |target|
      # and search a new mms with augmenting path from out to the target
      new_mms = augmenting_path graph, current_mms, out, target, [removal_node]
      # if we have a new mms, then we return it
      return new_mms unless new_mms.nil?
    end

    # If no mms has been returned, there's no alternative
    nil

  end

  def augmenting_path graph, current_mms, source, target, path
    # If target was not matched, then we're done
    if !current_mms.nodes.include? target
      current_mms.nodes << target
      current_mms.edges << [source, target]
      return current_mms
    # If target is matched, then we must search if there's an augmenting path
    else
      # We get the out node that matches the target
      out, _ = current_mms.edges.detect{|_, in_node| in_node == target }
      # we remove the edge
      current_mms.edges.reject!{|_, in_node| in_node == target }
      # we add the edge from source to target
      current_mms.edges << [source, target]

      path << target


       # We randomize the targets from the out node on the graph
      ( graph[out].shuffle - path). # and remove all targets that has been already traversed
      each do |new_target|
        # and search a new mms with augmenting path from out to its new target
        new_mms = augmenting_path graph, current_mms, out, new_target, path

        # if we have a new mms, then we return it
        return new_mms unless new_mms.nil?
      end

      # If no new mms has been returned there's no augmenting path
      return nil

    end
  end

  def all_alternative_mms graph, current_mms, removal_node

    alternatives =  []

    until current_mms.nil?
      current_mms = alternative_mms graph, current_mms, removal_node
      unless current_mms.nil?
        alternatives << current_mms.dup
        removal_node =  current_mms.nodes.sample
      end

    end

    alternatives
  end

  def controlability_score graph, mmss
    scores = {}
    mmss_count = mmss.to_a.length

    graph.keys.each do |node|
      mmss_with_node = mmss.select{|mms| mms.nodes.include? node}
      scores[node] = 1 - (mmss_with_node.length.to_f / mmss_count)
    end

    scores
  end

  def run graph

    puts "#{Time.now}: First MMS"

    current_mms = mms graph

    puts current_mms.nodes.count

    mmss = Set.new
    mmss << current_mms
    number_nodes = graph.keys.length
    # We repeat N * ln(N) so the algorithm converges
    (number_nodes*Math.log(number_nodes)).ceil.times do |i|
      puts "#{Time.now}: #{i}th repeat"
      # First, we get a node from the matched ones and it's the removal one
      removal_node = current_mms.nodes.sample
      alternative = all_alternative_mms(Marshal.load(Marshal.dump(graph)), current_mms.dup, removal_node).sample
      mmss << alternative unless alternative.nil?
    end

    controlability_score(graph, mmss)
  end

end

hash_sample.rb

# This hash represents the full graph:
#
# (1) -> (2)
#  |   /  |
#  |  /   |
#  V <    V
# (3) -> (4)
#
# Using keys and values we also have the bipartite graph, being the "in" side the values and the "out" side the keys
graph = {
  1 => [2,3],
  2 => [3,4],
  3 => [4],
  4 => []
}

require_relative './algorithm'

puts ControllabilityScoreAlgorithm.new.run(graph).inspect

tsv_file_sample.rb

require_relative './algorithm'

graph = {}
number_edges = 0
# We read the graph hrom a TSV file (just the two first columns)
File.new("./graph.tsv").each do |edge|
  mentioning, mentioned = edge.split("\t").first(2)
  graph[mentioned] ||= []
  graph[mentioned] << mentioning
  number_edges += 1
end

number_nodes = graph.keys.length

puts "#{number_nodes} mentioned users"
puts "#{number_edges} edges"
puts "Using #{(number_nodes*Math.log(number_nodes)).ceil} repeats"

# Store the scores
scores = ControllabilityScoreAlgorithm.new.run(graph).inspect

File.open("./scores.csv", "w") do |csv|
  scores.each do |node, score|
    csv << "#{node}, #{score}\n"
  end
end