relaxed_spanning_tree

relaxed_spanning_tree(graph: TGraph, maximise=False, gamma=1)[source]

compute relaxed minimum or maximum spanning tree

This implements the relaxed minimum spanning tree algorithm of

M. Beguerisse-Díaz, B. Vangelov, and M. Barahona. “Finding role communities in directed networks using Role-Based Similarity, Markov Stability and the Relaxed Minimum Spanning Tree”. In: 2013 IEEE Global Conference on Signal and Information Processing (GlobalSIP). IEEE, 2013, pp. 937–940. isbn: 978-1-4799-0248-4.

Parameters:

graph – input graph
maximise – if True start with maximum spanning tree
gamma – \(\gamma\) value for adding edges