ra_index_soundarajan_hopcroft#

Compute the resource allocation index of all node pairs in ebunch using community information.

For two nodes \(u\) and \(v\), this function computes the resource allocation index considering only common neighbors belonging to the same community as \(u\) and \(v\). Mathematically,

\[\sum_{w \in \Gamma(u) \cap \Gamma(v)} \frac{f(w)}{|\Gamma(w)|}\]

where \(f(w)\) equals 1 if \(w\) belongs to the same community as \(u\) and \(v\) or 0 otherwise and \(\Gamma(u)\) denotes the set of neighbors of \(u\).

Parameters:
Ggraph

A NetworkX undirected graph.

ebunchiterable of node pairs, optional (default = None)

The score will be computed for each pair of nodes given in the iterable. The pairs must be given as 2-tuples (u, v) where u and v are nodes in the graph. If ebunch is None then all nonexistent edges in the graph will be used. Default value: None.

communitystring, optional (default = ‘community’)

Nodes attribute name containing the community information. G[u][community] identifies which community u belongs to. Each node belongs to at most one community. Default value: ‘community’.

Returns:
piteriterator

An iterator of 3-tuples in the form (u, v, p) where (u, v) is a pair of nodes and p is their score.

Raises:
NetworkXNotImplemented

If G is a DiGraph, a Multigraph or a MultiDiGraph.

NetworkXAlgorithmError

If no community information is available for a node in ebunch or in G (if ebunch is None).

NodeNotFound

If ebunch has a node that is not in G.

References

[1]

Sucheta Soundarajan and John Hopcroft. Using community information to improve the precision of link prediction methods. In Proceedings of the 21st international conference companion on World Wide Web (WWW ‘12 Companion). ACM, New York, NY, USA, 607-608. http://doi.acm.org/10.1145/2187980.2188150

Examples

>>> G = nx.Graph()
>>> G.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 3)])
>>> G.nodes[0]["community"] = 0
>>> G.nodes[1]["community"] = 0
>>> G.nodes[2]["community"] = 1
>>> G.nodes[3]["community"] = 0
>>> preds = nx.ra_index_soundarajan_hopcroft(G, [(0, 3)])
>>> for u, v, p in preds:
...     print(f"({u}, {v}) -> {p:.8f}")
(0, 3) -> 0.50000000
----

Additional backends implement this function

parallelA networkx backend that uses joblib to run graph algorithms in parallel. Find the nx-parallel’s configuration guide here

The edge pairs are chunked into pairs_chunks and then the resource allocation index for all pairs_chunks is computed in parallel, using the community information, over n_jobs number of CPU cores.

Additional parameters:
get_chunksstr, function (default = “chunks”)

A function that takes in a list of all the edges (or ebunch) as input and returns an iterable pairs_chunks. The default chunking is done by slicing ebunch into n_jobs number of chunks.

[Source]