The generation of adjacency matrix

Usage
1

I want to acquire a adjacency matrix from a graph, but my code raised an error like:

MemoryError: Error at src/core/vector.c:146: Cannot initialize vector. -- Out of memory

How can I cope with this? I have 1,084,310 nodes and 2,613,136 edges.

Thanks for your help!

2

With about 1,000,000 nodes, I expect an adjacency matrix to be at least 4,000,000,000,000 bytes, so that’s quite some memory. Did you try get_adjacency_sparse()? Since you don’t have that many edges it should help.

2 Likes
3

Hi GroteGnoom,

Thanks so much for your suggestion. Actually, I want to calculate many metrics (e.g., betweenness, closeness, etc.) by igraph, but it works too slowly. Is there any way to speed up the igraph (e.g., GPU)? I can request the support from internal server with GPU or CPU.

Thanks

4

No, you can’t just switch to GPU.

Can you be more specific? Which metrics take too much time, and how much time is that?

5

Hi GroteGnoom,

Closeness. I have calculated that for over 3 hours but still could not got the answer.

And next I will cnoduct a research with over 17 miliion nodes and about 1 billion edges directed graph. Could you please give me some suggestion about this?

6

Computing the exact closeness for all vertices requires performing a graph traversal from each vertex, meaning that the complexity is O(V E) where V and E are the vertex and edge counts. Considering that in practical scenarios E > V, this is effectively quadratic in the number of vertices. So yes, it will be slow for a large graph and there’s no way around this.

If you were to compute the related harmonic centrality, you could get an approximation to the result by only considering paths shorter than a threshold (cutoff parameter). There is also a cutoff version for closeness, but this can’t be considered an approximation of exact closeness.

1 Like
7

Dear Szhorvat,

Thanks so much for your helpful suggestion.

In fact, I would like to calculate the eigenvector_centrality, eccentricity, hub score, closeness, and page rank possibility on this dataset. Is there any feasible method to speed up my calculation.

As per my understanding, it seems impossible to get the closeness metric. :joy:

Thanks

8

These are all very different metrics, and their calculations have different complexities.

Some of them are related and could be computed in tandem. E.g. once you have the distance from a vertex to all other vertices, you can compute closeness, harmonic centrality and eccentricity.

Before you start these calculations, make sure that these metrics are meaningful for your problem / dataset. You say you want to compute both the eigenvector centrality and the hub score, but you don’t mention the authority score. This makes little sense. Eigenvector centrality is designed for undirected graphs. The pair of hub and authority scores, which need to be interpreted together, are an extension of the concept to directed graphs. You would use one or the other depending on whether your graph is undirected or directed.

For closeness, you can try to get an estimate of how long it would take, then decide whether it’s worth your time. Start calculating it for 100, then 1000, then 10000 randomly chosen vertices. Then extrapolate how long the calculation would take for the entire graph.

9

Dear Szhorvat,

Thanks so much for you kind reply.

I will take your suggesiton into account seriously. But I am afraid I have to calculate all available metrics LOL. Is there another tool can handle my problem well? I do look forward to your constructive reply, which is quite important for my research.

Thanks so much!