cliq.r

library(igraph)

gamma = 0.7
edge_list = as.matrix(read.csv('ueb06-daten.csv'))
graph = graph_from_edgelist(edge_list, directed = FALSE)

print("Loaded graph.")

find_clique_component <- function() {
  components = decompose.graph(graph)
  sprintf("Component count: %d", length(components))
  for (component in components) {
    degrees = degree(graph)
    degrees_enough = degrees >= gamma * (length(V(graph)) - 1)
    if (all(degrees_enough)) {
      return(component)
    }
  }
  return(NULL)
}


while (length(V(graph)) > 0) {
  print("Trying to find clique component...")
  clique_component = find_clique_component()
  print("Done.")
  if (is.null(clique_component)) {
    print("Nothing found. Finding edge...")
    betw = edge.betweenness.estimate(graph, cutoff = 0)
    max_betw_index = which.max(betw)
    graph = delete_edges(graph, c(max_betw_index))
    print(sprintf("Deleted edge. Edge count: %d", length(E(graph))))
  } else {
    print("Found component, removing it from graph: ")
    print(clique_component)
    graph = delete_edges(graph, E(clique_component))
  }  
}