Message Boards Message Boards

0
|
7103 Views
|
3 Replies
|
0 Total Likes
View groups...
Share
Share this post:

Graph Measures & Metrics for Weighted and Directed Networks

Posted 9 years ago

Hello all:

Does Mathematica have software to calculate Graph Measures & Metrics for Weighted and Directed Networks? Where could I find it?

thanks!

WP

POSTED BY: Wilson Perez
3 Replies

Bad news :-(

Mathematica also gives incorrect results for the betweenness centrality of large graphs, most likely due to integer overflow. (Update: Fixed in recent versions.) How do I know that Mathematica is wrong?

Well, here it is:

Let's make a grid graph, which has lots and lots of shortest paths of the same length, and is thus a good stress test.

In[36]:= g = GridGraph[{30, 30}];

In[37]:= Max@BetweennessCentrality[g] - Max@IGBetweenness[g, "UseBigInt" -> False]
Out[37]= 0.

igraph and Mathematica agree perfectly. Good. Now let's make a bigger grid graph.

In[33]:= g = GridGraph[{40, 40}];

In[34]:= Max@BetweennessCentrality[g] - Max@IGBetweenness[g, "UseBigInt" -> False]
Out[34]= -46909.

That's a huge difference. So someone is wrong. But who? igraph is documented to have integer overflows with the "UseBigInt" -> False option (although it's very fast with it). Let's use bigints to avoid the overflow.

In[40]:= Max@BetweennessCentrality[g] - Max@IGBetweenness[g, "UseBigInt" -> True]
Out[40]= -14441.

They still disagree. So let's try a third package, networkx:

In [16]: g=nx.grid_2d_graph(40,40);

In [17]: bc=nx.betweenness_centrality(g, normalized=False);

In [18]: max(bc.values())
Out[18]: 45701.730220604535

Comparing Mathematica and igraph:

In[42]:= {Max@BetweennessCentrality[g], Max@IGBetweenness[g, "UseBigInt" -> True]}
Out[42]= {31260.7, 45701.7}

So networkx and igraph agree. Mathematica must be wrong.

Sean, could you please bring this to the attention of the developers?

POSTED BY: Szabolcs Horvát

Hello Wilson,

Mathematica has builtin functions for many graph measures. There are many types of graphs: directed, undirected, edge-weighted, vertex-weighted, multi-edge graphs, graphs with self loops, mixed directed/undirected, and all sort of combinations of these. Most graph functions that Mathematica provides don't work with all of them, or don't even make sense for all of them. The Details section of each documentation page will usually have a sentence mentioning what works and what doesn't. For example,

  • BetweennessCentrality works with undirected graphs, directed graphs, multigraphs, and mixed graphs.

Notice this particular one doesn't support weighted graphs. Many other functions, like EdgeBetweennessCentrality, do.

The IGraphM package I made tries to provide an interface to some of igraph's functionality, especially those things that are not yet present in Mathematica. It does have a betweenness function for weighted graphs, but unlike Mathematica's, it doesn't work with mixed graphs. It doesn't give accurate results for very large graphs either due to integer overflows (will be fixed soon). So as you can see, neither is perfect, and they're meant to complement each other.

When using IGraphM be very cautious as the package is still under development and may have problems. (Update: The package is now mature.) Let me know if you find any. One of the motivations behind it was to have something to verify Mathematica with: if they agree, then you can be confident in the result.


Update:

Recent versions of IGraph/M can compute several different centrality measures taking weights into account, for which the built-in functions of Mathematica only give unweighted answers. There are also multiple utility functions take make the handling of weighted graphs easier.

POSTED BY: Szabolcs Horvát

Here is the documentation on these in Mathematica: https://reference.wolfram.com/language/guide/GraphMeasures.html.

If I understand correctly, many of these functions aren't supported for the specific kinds of graphs you are looking for.

I would take a look at IGraphM and igraph:

https://github.com/szhorvat/IGraphM

http://szhorvat.net/pelican/using-igraph-from-mathematica.html

POSTED BY: Sean Clarke
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract