Long running time in cluster_edge_betweenness function

Usage
1

I have been trying to implement a cluster_edge_betweenness() function to find communities. My graph contains 732 vertices and 245786 edges. Moreover, it is a little bit dense. After converting to igraph object I passed this to the cluster_edge_betweenness() function to get the communities. However, I could not get the result(I have waited for 12 hours and my computer/CPU is not very bad). What is the problem, I did not make any mistake but the time is strangely long for this kind of graph.
Here is my code and adjacency matrix:

train_network <- graph_from_adjacency_matrix(adj_mat_users,
                                             mode = "undirected",  
                                             diag = FALSE)

train_community_edge <- cluster_edge_betweenness(train_network)

adj_mat_users.csv (1.0 MB)

2

This algorithm has quadratic complexity in the number of edges so it’s no surprise that it’s slow with this graph. Time complexities are indicated in the C/igraph documentation, but in this case it’s relatively easy to see what’s going on: betweenness values need to be recalculated from scratch after the removal of each edge.

It is an interesting question whether there are efficient (sub-linear in edges) algorithms for updating betweenness after edge removals.