Skip to main content
`Ctrl`+`K`

# cn_soundarajan_hopcroft

cn_soundarajan_hopcroft(G, ebunch=None, community='community')
  Count the number of common neighbors of all node pairs in ebunch

    using community information.

  For two nodes \(u\) and \(v\), this function computes the number of common neighbors and bonus one for each common neighbor belonging to the same community as \(u\) and \(v\). Mathematically,

  \[|\Gamma(u) \cap \Gamma(v)| + \sum_{w \in \Gamma(u) \cap \Gamma(v)} f(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:
    G graph

      A NetworkX undirected graph.

    ebunch iterable 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.

    community string, 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:
    piter iterator

      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.path_graph(3)
      >>> G.nodes[0]["community"] = 0
      >>> G.nodes[1]["community"] = 0
      >>> G.nodes[2]["community"] = 0
      >>> preds = nx.cn_soundarajan_hopcroft(G, [(0, 2)])
      >>> for u, v, p in preds:
      ...     print(f"({u}, {v}) -> {p}")
      (0, 2) -> 2