Similarity Measures

Functions measuring similarity using graph edit distance.

The graph edit distance is the number of edge/node changes needed to make two graphs isomorphic.

The default algorithm/implementation is sub-optimal for some graphs. The problem of finding the exact Graph Edit Distance (GED) is NP-hard so it is often slow. If the simple interface graph_edit_distance takes too long for your graph, try optimize_graph_edit_distance and/or optimize_edit_paths.

At the same time, I encourage capable people to investigate alternative GED algorithms, in order to improve the choices available.

graph_edit_distance(G1, G2[, node_match, …])

Returns GED (graph edit distance) between graphs G1 and G2.

optimal_edit_paths(G1, G2[, node_match, …])

Returns all minimum-cost edit paths transforming G1 to G2.

optimize_graph_edit_distance(G1, G2[, …])

Returns consecutive approximations of GED (graph edit distance) between graphs G1 and G2.

optimize_edit_paths(G1, G2[, node_match, …])

GED (graph edit distance) calculation: advanced interface.

simrank_similarity(G[, source, target, …])

Returns the SimRank similarity of nodes in the graph G.

simrank_similarity_numpy(G[, source, …])

Calculate SimRank of nodes in G using matrices with numpy.

panther_similarity(G, source[, k, …])

Returns the Panther similarity of nodes in the graph G to node v.

generate_random_paths(G, sample_size[, …])

Randomly generate sample_size paths of length path_length.