panther_similarity#

panther_similarity(G, source, k=5, path_length=5, c=0.5, delta=0.1, eps=None, weight='weight')[source]#

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

Panther is a similarity metric that says “two objects are considered to be similar if they frequently appear on the same paths.” [1].

Parameters:

GNetworkX graph: A NetworkX graph
sourcenode: Source node for which to find the top k similar other nodes
kint (default = 5): The number of most similar nodes to return.
path_lengthint (default = 5): How long the randomly generated paths should be (T in [1])
cfloat (default = 0.5): A universal positive constant used to scale the number of sample random paths to generate.
deltafloat (default = 0.1): The probability that the similarity \(S\) is not an epsilon-approximation to (R, phi), where \(R\) is the number of random paths and \(\phi\) is the probability that an element sampled from a set \(A \subseteq D\), where \(D\) is the domain.
epsfloat or None (default = None): The error bound. Per [1], a good value is sqrt(1/|E|). Therefore, if no value is provided, the recommended computed value will be used.
weightstring or None, optional (default=”weight”): The name of an edge attribute that holds the numerical value used as a weight. If None then each edge has weight 1.

Returns:

similaritydictionary: Dictionary of nodes to similarity scores (as floats). Note: the self-similarity (i.e., v) will not be included in the returned dictionary. So, for k = 5, a dictionary of top 4 nodes and their similarity scores will be returned.

Raises:

NetworkXUnfeasible: If source is an isolated node.
NodeNotFound: If source is not in G.

Notes

The isolated nodes in G are ignored.

References

[1] (1,2,3)

Zhang, J., Tang, J., Ma, C., Tong, H., Jing, Y., & Li, J. Panther: Fast top-k similarity search on large networks. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (Vol. 2015-August, pp. 1445–1454). Association for Computing Machinery. https://doi.org/10.1145/2783258.2783267.

Examples

>>> G = nx.star_graph(10)
>>> sim = nx.panther_similarity(G, 0)