1
$\begingroup$

I am working on a undirected, binary graph (derived from functional neuroimaging). I would like to alter this graph to change specific graph-characteristics (e.g. a specific value for the global clustering coefficient or the average minimal path length) while keeping all other graph-characteristics constant (or as many other as possible). There are some references how to alter a graph to have a specific clustering coefficient (e.g. this question suggests Wang or the block two-level Erdos-Renyi model). There are existing implementations for the clustering coefficient (here and here). Are there similar references with respect to average minimal path length?

$\endgroup$
1
$\begingroup$

You could the use the principle of the Watts-Strogatz model (Watts'98): in the article, they show empirically that randomly rewiring a very few links in a lattice allows largely decreasing the average distance while keeping a relatively high clustering coefficient.

In this model, a parameter p allows controlling the (expected) proportion of rewired links. For each rewired link, one randomly selects one of its end-points, then exchange it for a different (randomly drawn) node. You can find an implementation in igraph, see file igraph/src/games.c#igraph_watts_strogatz_game on their GitHub.

You could implement this simple mechanism, apply it to your own data, and study how playing with p affects the other topological proporties of interest. But intuitively, it seems hard to completely control one topological property without changing the others. For instance, in a previous work I studied how a different rewiring process (designed to produce a community structure) affects the average distance, degree correlation and average distance of a network, and the effects were very different, and sometimes very strong.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.