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 nodev
.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, fork = 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 inG
.
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)