# Long running time in cluster\_edge\_betweenness function

**URL:** <https://igraph.discourse.group/t/long-running-time-in-cluster-edge-betweenness-function/1333>\
**Category:** Usage\
**Tags:** R\
**Created:** [21 August 2022 09:43 UTC](https://igraph.discourse.group/t/long-running-time-in-cluster-edge-betweenness-function/1333 "2022-08-21T09:43:05Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![Ilhom\_Sadriddinov](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/ilhom_sadriddinov/32/720_2.png) [@Ilhom\_Sadriddinov](https://igraph.discourse.group/u/Ilhom_Sadriddinov)\
**Post date:** [21 August 2022 09:43 UTC](https://igraph.discourse.group/t/long-running-time-in-cluster-edge-betweenness-function/1333/1 "2022-08-21T09:43:05Z")

</div>

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:

```auto
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](https://igraph.discourse.group/uploads/short-url/qJtJXEYrGAmyImRIEg73uIKA5ev.csv) (1.0 MB)

---

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\
**Post date:** [21 August 2022 09:59 UTC](https://igraph.discourse.group/t/long-running-time-in-cluster-edge-betweenness-function/1333/2 "2022-08-21T09:59:23Z")

</div>

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](https://igraph.org/c/html/latest/igraph-Community.html#igraph_community_edge_betweenness), 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.