Merge pull request #1163 from kemskems/link-prediction

Link prediction algorithms #2

3 files changed, 733 insertions, 234 deletions

diff --git a/doc/source/reference/algorithms.link_prediction.rst b/doc/source/reference/algorithms.link_prediction.rst
index 6d1c7da2..a95caee9 100644
--- a/doc/source/reference/algorithms.link_prediction.rst
+++ b/doc/source/reference/algorithms.link_prediction.rst
@@ -7,6 +7,9 @@ Link Prediction
    :toctree: generated/
 
    resource_allocation_index
+   jaccard_coefficient
+   adamic_adar_index
+   preferential_attachment
    cn_soundarajan_hopcroft
    ra_index_soundarajan_hopcroft
    within_inter_cluster
diff --git a/networkx/algorithms/link_prediction.py b/networkx/algorithms/link_prediction.py
index 8458464b..c54ae64b 100644
--- a/networkx/algorithms/link_prediction.py
+++ b/networkx/algorithms/link_prediction.py
@@ -4,11 +4,15 @@ Link prediction algorithms.
 
 from __future__ import division
 
+import math
+
 import networkx as nx
-from networkx.exception import *
 from networkx.utils.decorators import *
 
 __all__ = ['resource_allocation_index',
+           'jaccard_coefficient',
+           'adamic_adar_index',
+           'preferential_attachment',
            'cn_soundarajan_hopcroft',
            'ra_index_soundarajan_hopcroft',
            'within_inter_cluster']
@@ -16,30 +20,45 @@ __all__ = ['resource_allocation_index',
 
 @not_implemented_for('directed')
 @not_implemented_for('multigraph')
-def resource_allocation_index(G, u, v):
-    """Compute the resource allocation index of u and v.
+def resource_allocation_index(G, ebunch=None):
+    r"""Compute the resource allocation index of all node pairs in ebunch.
+
+    Resource allocation index of `u` and `v` is defined as
+
+    .. math::
+
+        \sum_{w \in \Gamma(u) \cap \Gamma(v)} \frac{1}{|\Gamma(w)|}
 
-    Resource allocation index of nodes u and v is defined as the sum of
-    reciprocals of the degree of all the common neighbors w of u and v.
+    where :math:`\Gamma(u)` denotes the set of neighbors of `u`.
 
     Parameters
     ----------
     G : graph
         A NetworkX undirected graph.
 
-    u, v : nodes
-        Nodes in the graph.
+    ebunch : iterable of node pairs, optional (default = None)
+        Resource allocation index 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 non-existent edges in the graph will be used.
+        Default value: None.
 
     Returns
     -------
-    value : float
-        The resource allocation index of u and v.
+    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 resource allocation index.
 
     Examples
     --------
+    >>> import networkx as nx
     >>> G = nx.complete_graph(5)
-    >>> nx.resource_allocation_index(G, 0, 1)
-    0.75
+    >>> preds = nx.resource_allocation_index(G, [(0, 1), (2, 3)])
+    >>> for u, v, p in preds:
+    ...     '(%d, %d) -> %.8f' % (u, v, p)
+    ...
+    '(0, 1) -> 0.75000000'
+    '(2, 3) -> 0.75000000'
 
     References
     ----------
@@ -48,36 +67,229 @@ def resource_allocation_index(G, u, v):
        Eur. Phys. J. B 71 (2009) 623.
        http://arxiv.org/pdf/0901.0553.pdf
     """
-    return sum(1 / G.degree(w) for w in nx.common_neighbors(G, u, v))
+    if ebunch is None:
+        ebunch = nx.non_edges(G)
+
+    def predict(u, v):
+        return sum(1 / G.degree(w) for w in nx.common_neighbors(G, u, v))
+
+    return ((u, v, predict(u, v)) for u, v in ebunch)
 
 
 @not_implemented_for('directed')
 @not_implemented_for('multigraph')
-def cn_soundarajan_hopcroft(G, u, v):
-    """Count the number of common neighbors using community information.
+def jaccard_coefficient(G, ebunch=None):
+    r"""Compute the Jaccard coefficient of all node pairs in ebunch.
 
-    One is added to the count for each common neighbor that belongs
-    to the same community as u and v.
+    Jaccard coefficient of nodes `u` and `v` is defined as
+
+    .. math::
+
+        \frac{|\Gamma(u) \cap \Gamma(v)|}{|\Gamma(u) \cup \Gamma(v)|}
+
+    where :math:`\Gamma(u)` denotes the set of neighbors of `u`.
 
     Parameters
     ----------
     G : graph
         A NetworkX undirected graph.
 
-    u, v : nodes
-        Nodes in the graph.
+    ebunch : iterable of node pairs, optional (default = None)
+        Jaccard coefficient 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 non-existent edges in the graph will be used.
+        Default value: None.
+
+    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 Jaccard coefficient.
+
+    Examples
+    --------
+    >>> import networkx as nx
+    >>> G = nx.complete_graph(5)
+    >>> preds = nx.jaccard_coefficient(G, [(0, 1), (2, 3)])
+    >>> for u, v, p in preds:
+    ...     '(%d, %d) -> %.8f' % (u, v, p)
+    ...
+    '(0, 1) -> 0.60000000'
+    '(2, 3) -> 0.60000000'
+
+    References
+    ----------
+    .. [1] D. Liben-Nowell, J. Kleinberg.
+           The Link Prediction Problem for Social Networks (2004).
+           http://www.cs.cornell.edu/home/kleinber/link-pred.pdf
+    """
+    if ebunch is None:
+        ebunch = nx.non_edges(G)
+
+    def predict(u, v):
+        cnbors = list(nx.common_neighbors(G, u, v))
+        union_size = len(set(G[u]) | set(G[v]))
+        if union_size == 0:
+            return 0
+        else:
+            return len(cnbors) / union_size
+
+    return ((u, v, predict(u, v)) for u, v in ebunch)
+
+
+@not_implemented_for('directed')
+@not_implemented_for('multigraph')
+def adamic_adar_index(G, ebunch=None):
+    r"""Compute the Adamic-Adar index of all node pairs in ebunch.
+
+    Adamic-Adar index of `u` and `v` is defined as
+
+    .. math::
+
+        \sum_{w \in \Gamma(u) \cap \Gamma(v)} \frac{1}{\log |\Gamma(w)|}
+
+    where :math:`\Gamma(u)` denotes the set of neighbors of `u`.
+
+    Parameters
+    ----------
+    G : graph
+        NetworkX undirected graph.
+
+    ebunch : iterable of node pairs, optional (default = None)
+        Adamic-Adar index 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
+        non-existent edges in the graph will be used.
+        Default value: None.
+
+    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 Adamic-Adar index.
+
+    Examples
+    --------
+    >>> import networkx as nx
+    >>> G = nx.complete_graph(5)
+    >>> preds = nx.adamic_adar_index(G, [(0, 1), (2, 3)])
+    >>> for u, v, p in preds:
+    ...     '(%d, %d) -> %.8f' % (u, v, p)
+    ...
+    '(0, 1) -> 2.16404256'
+    '(2, 3) -> 2.16404256'
+
+    References
+    ----------
+    .. [1] D. Liben-Nowell, J. Kleinberg.
+           The Link Prediction Problem for Social Networks (2004).
+           http://www.cs.cornell.edu/home/kleinber/link-pred.pdf
+    """
+    if ebunch is None:
+        ebunch = nx.non_edges(G)
+
+    def predict(u, v):
+        return sum(1 / math.log(G.degree(w))
+                   for w in nx.common_neighbors(G, u, v))
+
+    return ((u, v, predict(u, v)) for u, v in ebunch)
+
+
+@not_implemented_for('directed')
+@not_implemented_for('multigraph')
+def preferential_attachment(G, ebunch=None):
+    r"""Compute the preferential attachment score of all node pairs in ebunch.
+
+    Preferential attachment score of `u` and `v` is defined as
+
+    .. math::
+
+        |\Gamma(u)| |\Gamma(v)|
+
+    where :math:`\Gamma(u)` denotes the set of neighbors of `u`.
+
+    Parameters
+    ----------
+    G : graph
+        NetworkX undirected graph.
+
+    ebunch : iterable of node pairs, optional (default = None)
+        Preferential attachment 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 non-existent edges in the graph will be used.
+        Default value: None.
 
     Returns
     -------
-    value : int
-        The number of common neighbors between u and v plus bonus for
-        each common neighbor belonging to the same community as u and v.
+    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 preferential attachment score.
+
+    Examples
+    --------
+    >>> import networkx as nx
+    >>> G = nx.complete_graph(5)
+    >>> preds = nx.preferential_attachment(G, [(0, 1), (2, 3)])
+    >>> for u, v, p in preds:
+    ...     '(%d, %d) -> %d' % (u, v, p)
+    ...
+    '(0, 1) -> 16'
+    '(2, 3) -> 16'
+
+    References
+    ----------
+    .. [1] D. Liben-Nowell, J. Kleinberg.
+           The Link Prediction Problem for Social Networks (2004).
+           http://www.cs.cornell.edu/home/kleinber/link-pred.pdf
+    """
+    if ebunch is None:
+        ebunch = nx.non_edges(G)
+
+    return ((u, v, G.degree(u) * G.degree(v)) for u, v in ebunch)
+
+
+@not_implemented_for('directed')
+@not_implemented_for('multigraph')
+def cn_soundarajan_hopcroft(G, ebunch=None, community='community'):
+    r"""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,
+
+    .. math::
 
-    Notes
-    -----
-    The community information is defined as the information of which
-    community each node belongs to. This information should be stored
-    as the nodes attribute with 'community' as the name.
+        |\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 :math:`\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
+        non-existent 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.
 
     Examples
     --------
@@ -86,120 +298,162 @@ def cn_soundarajan_hopcroft(G, u, v):
     >>> G.node[0]['community'] = 0
     >>> G.node[1]['community'] = 0
     >>> G.node[2]['community'] = 0
-    >>> nx.cn_soundarajan_hopcroft(G, 0, 2)
-    2
+    >>> preds = nx.cn_soundarajan_hopcroft(G, [(0, 2)])
+    >>> for u, v, p in preds:
+    ...     '(%d, %d) -> %d' % (u, v, p)
+    ...
+    '(0, 2) -> 2'
 
     References
     ----------
     .. [1] Sucheta Soundarajan and John Hopcroft.
-       Using community information to improve the precision of link prediction methods.
+       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
     """
-    Cu = _community(G, u)
-    Cv = _community(G, v)
-    cnbors = list(nx.common_neighbors(G, u, v))
-    if Cu == Cv:
-        return len(cnbors) + sum(_community(G, w) == Cu for w in cnbors)
-    else:
-        return len(cnbors)
+    if ebunch is None:
+        ebunch = nx.non_edges(G)
+
+    def predict(u, v):
+        Cu = _community(G, u, community)
+        Cv = _community(G, v, community)
+        cnbors = list(nx.common_neighbors(G, u, v))
+        if Cu == Cv:
+            return len(cnbors) + sum(_community(G, w, community) == Cu
+                                     for w in cnbors)
+        else:
+            return len(cnbors)
+
+    return ((u, v, predict(u, v)) for u, v in ebunch)
 
 
 @not_implemented_for('directed')
 @not_implemented_for('multigraph')
-def ra_index_soundarajan_hopcroft(G, u, v):
-    """Compute the resource allocation index of u and v using community information.
+def ra_index_soundarajan_hopcroft(G, ebunch=None, community='community'):
+    r"""Compute the resource allocation index of all node pairs in
+    ebunch using community information.
 
-    Resource allocation index of two nodes is defined as the sum of
-    reciprocals of the degree of all their common neighbors. However,
-    this function only considers common neighbors belonging to the same
-    community as u and v.
+    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,
+
+    .. math::
+
+        \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 :math:`\Gamma(u)` denotes the set of
+    neighbors of `u`.
 
     Parameters
     ----------
     G : graph
         A NetworkX undirected graph.
 
-    u, v : nodes
-        Nodes in the 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
+        non-existent 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
     -------
-    value : float
-        The resource allocation index of u and v considering only
-        common neighbors that belong to the same community as u and v.
-
-    Notes
-    -----
-    The community information is defined as the information of which
-    community each node belongs to. This information should be stored
-    as the nodes attribute with 'community' as the name.
+    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.
 
     Examples
     --------
+    >>> import networkx as nx
     >>> G = nx.Graph()
     >>> G.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 3)])
     >>> G.node[0]['community'] = 0
     >>> G.node[1]['community'] = 0
     >>> G.node[2]['community'] = 1
     >>> G.node[3]['community'] = 0
-    >>> nx.ra_index_soundarajan_hopcroft(G, 0, 3)
-    0.5
+    >>> preds = nx.ra_index_soundarajan_hopcroft(G, [(0, 3)])
+    >>> for u, v, p in preds:
+    ...     '(%d, %d) -> %.8f' % (u, v, p)
+    ...
+    '(0, 3) -> 0.50000000'
 
     References
     ----------
     .. [1] Sucheta Soundarajan and John Hopcroft.
-       Using community information to improve the precision of link prediction methods.
+       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
     """
-    Cu = _community(G, u)
-    Cv = _community(G, v)
-    if Cu == Cv:
-        cnbors = nx.common_neighbors(G, u, v)
-        return sum(1 / G.degree(w) for w in cnbors if _community(G, w) == Cu)
-    else:
-        return 0
+    if ebunch is None:
+        ebunch = nx.non_edges(G)
+
+    def predict(u, v):
+        Cu = _community(G, u, community)
+        Cv = _community(G, v, community)
+        if Cu == Cv:
+            cnbors = nx.common_neighbors(G, u, v)
+            return sum(1 / G.degree(w) for w in cnbors
+                       if _community(G, w, community) == Cu)
+        else:
+            return 0
+
+    return ((u, v, predict(u, v)) for u, v in ebunch)
 
 
 @not_implemented_for('directed')
 @not_implemented_for('multigraph')
-def within_inter_cluster(G, u, v, delta=0.001):
-    """Compute the ratio of within- and inter-cluster common neighbor.
+def within_inter_cluster(G, ebunch=None, delta=0.001, community='community'):
+    """Compute the ratio of within- and inter-cluster common neighbors
+    of all node pairs in ebunch.
 
-    If a common neighbor w belongs to the same community with u and v,
-    w is considered as within-cluster common neighbor of u and v.
-    Otherwise, it is considered as inter-cluster common neighbor of u
-    and v. The ratio between the size of the set of within- and
-    inter-cluster common neighbors is defined as the WIC measure. [1]_
+    For two nodes `u` and `v`, if a common neighbor `w` belongs to the
+    same community as them, `w` is considered as within-cluster common
+    neighbor of `u` and `v`. Otherwise, it is considered as
+    inter-cluster common neighbor of `u` and `v`. The ratio between the
+    size of the set of within- and inter-cluster common neighbors is
+    defined as the WIC measure. [1]_
 
     Parameters
     ----------
     G : graph
         A NetworkX undirected graph.
 
-    u, v : nodes
-        Nodes in the graph.
+    ebunch : iterable of node pairs, optional (default = None)
+        The WIC measure 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
+        non-existent edges in the graph will be used.
+        Default value: None.
+
+    delta : float, optional (default = 0.001)
+        Value to prevent division by zero in case there is no
+        inter-cluster common neighbor between two nodes. See [1]_ for
+        details. Default value: 0.001.
 
-    delta : float, optional
-        Value to prevent division by zero in case there is no inter-cluster
-        common neighbor of u and v. See [1]_ for details.
+    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
     -------
-    value : float
-        The WIC measure of u and v.
-
-    Notes
-    -----
-    The community information is defined as the information of which
-    community each node belongs to. This information should be stored
-    as the nodes attribute with 'community' as the name.
+    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 WIC measure.
 
     Examples
     --------
+    >>> import networkx as nx
     >>> G = nx.Graph()
     >>> G.add_edges_from([(0, 1), (0, 2), (0, 3), (1, 4), (2, 4), (3, 4)])
     >>> G.node[0]['community'] = 0
@@ -207,10 +461,16 @@ def within_inter_cluster(G, u, v, delta=0.001):
     >>> G.node[2]['community'] = 0
     >>> G.node[3]['community'] = 0
     >>> G.node[4]['community'] = 0
-    >>> nx.within_inter_cluster(G, 0, 4)
-    1.9980019980019983
-    >>> nx.within_inter_cluster(G, 0, 4, delta=0.5)
-    1.3333333333333333
+    >>> preds = nx.within_inter_cluster(G, [(0, 4)])
+    >>> for u, v, p in preds:
+    ...     '(%d, %d) -> %.8f' % (u, v, p)
+    ...
+    '(0, 4) -> 1.99800200'
+    >>> preds = nx.within_inter_cluster(G, [(0, 4)], delta=0.5)
+    >>> for u, v, p in preds:
+    ...     '(%d, %d) -> %.8f' % (u, v, p)
+    ...
+    '(0, 4) -> 1.33333333'
 
     References
     ----------
@@ -221,22 +481,30 @@ def within_inter_cluster(G, u, v, delta=0.001):
        http://dx.doi.org/10.1007/978-3-642-34459-6_10
     """
     if delta <= 0:
-        raise NetworkXAlgorithmError('Delta must be greater than zero')
+        raise nx.NetworkXAlgorithmError('Delta must be greater than zero')
+
+    if ebunch is None:
+        ebunch = nx.non_edges(G)
+
+    def predict(u, v):
+        Cu = _community(G, u, community)
+        Cv = _community(G, v, community)
+        if Cu == Cv:
+            cnbors = set(nx.common_neighbors(G, u, v))
+            within = set(w for w in cnbors
+                         if _community(G, w, community) == Cu)
+            inter = cnbors - within
+            return len(within) / (len(inter) + delta)
+        else:
+            return 0
 
-    Cu = _community(G, u)
-    Cv = _community(G, v)
-    if Cu == Cv:
-        cnbors = set(nx.common_neighbors(G, u, v))
-        within = set(w for w in cnbors if _community(G, w) == Cu)
-        inter = cnbors - within
-        return len(within) / (len(inter) + delta)
-    else:
-        return 0
+    return ((u, v, predict(u, v)) for u, v in ebunch)
 
 
-def _community(G, u):
+def _community(G, u, community):
     """Get the community of the given node."""
+    node_u = G.node[u]
     try:
-        return G.node[u]['community']
+        return node_u[community]
     except KeyError:
-        raise NetworkXAlgorithmError('No community information')
+        raise nx.NetworkXAlgorithmError('No community information')
diff --git a/networkx/algorithms/tests/test_link_prediction.py b/networkx/algorithms/tests/test_link_prediction.py
index 96049897..875d7dca 100644
--- a/networkx/algorithms/tests/test_link_prediction.py
+++ b/networkx/algorithms/tests/test_link_prediction.py
@@ -1,67 +1,252 @@
+import math
+
 from nose.tools import *
 
 import networkx as nx
-from networkx.exception import *
-import networkx.algorithms.link_prediction as lp
 
 
 class TestResourceAllocationIndex():
     def setUp(self):
-        self.func = lp.resource_allocation_index
-        def test_func(G, u, v, expected):
-            tol = 1e-7
-            result = self.func(G, u, v)
-            assert_true(abs(result - expected) < tol)
+        self.func = nx.resource_allocation_index
+
+        def test_func(G, ebunch, expected):
+            result = self.func(G, ebunch)
+            for res, exp in zip(result, expected):
+                assert_true(isinstance(res, tuple))
+                assert_equal(3, len(res))
+                assert_equal(res[0], exp[0])
+                assert_equal(res[1], exp[1])
+                assert_almost_equal(res[2], exp[2])
+        self.test = test_func
+
+    def test_K5(self):
+        G = nx.complete_graph(5)
+        self.test(G, [(0, 1)], [(0, 1, 0.75)])
+
+    def test_P3(self):
+        G = nx.path_graph(3)
+        self.test(G, [(0, 2)], [(0, 2, 0.5)])
+
+    def test_S4(self):
+        G = nx.star_graph(4)
+        self.test(G, [(1, 2)], [(1, 2, 0.25)])
+
+    @raises(nx.NetworkXNotImplemented)
+    def test_digraph(self):
+        G = nx.DiGraph()
+        G.add_edges_from([(0, 1), (1, 2)])
+        self.func(G, [(0, 2)])
+
+    @raises(nx.NetworkXNotImplemented)
+    def test_multigraph(self):
+        G = nx.MultiGraph()
+        G.add_edges_from([(0, 1), (1, 2)])
+        self.func(G, [(0, 2)])
+
+    @raises(nx.NetworkXNotImplemented)
+    def test_multidigraph(self):
+        G = nx.MultiDiGraph()
+        G.add_edges_from([(0, 1), (1, 2)])
+        self.func(G, [(0, 2)])
+
+    def test_no_common_neighbor(self):
+        G = nx.Graph()
+        G.add_nodes_from([0, 1])
+        self.test(G, [(0, 1)], [(0, 1, 0)])
+
+    def test_equal_nodes(self):
+        G = nx.complete_graph(4)
+        self.test(G, [(0, 0)], [(0, 0, 1)])
+
+    def test_all_nonexistent_edges(self):
+        G = nx.Graph()
+        G.add_edges_from([(0, 1), (0, 2), (2, 3)])
+        self.test(G, None, [(0, 3, 0.5), (1, 2, 0.5), (1, 3, 0)])
+
+
+class TestJaccardCoefficient():
+    def setUp(self):
+        self.func = nx.jaccard_coefficient
+
+        def test_func(G, ebunch, expected):
+            result = self.func(G, ebunch)
+            for res, exp in zip(result, expected):
+                assert_true(isinstance(res, tuple))
+                assert_equal(3, len(res))
+                assert_equal(res[0], exp[0])
+                assert_equal(res[1], exp[1])
+                assert_almost_equal(res[2], exp[2])
+        self.test = test_func
+
+    def test_K5(self):
+        G = nx.complete_graph(5)
+        self.test(G, [(0, 1)], [(0, 1, 0.6)])
+
+    def test_P4(self):
+        G = nx.path_graph(4)
+        self.test(G, [(0, 2)], [(0, 2, 0.5)])
+
+    @raises(nx.NetworkXNotImplemented)
+    def test_digraph(self):
+        G = nx.DiGraph()
+        G.add_edges_from([(0, 1), (1, 2)])
+        self.func(G, [(0, 2)])
+
+    @raises(nx.NetworkXNotImplemented)
+    def test_multigraph(self):
+        G = nx.MultiGraph()
+        G.add_edges_from([(0, 1), (1, 2)])
+        self.func(G, [(0, 2)])
+
+    @raises(nx.NetworkXNotImplemented)
+    def test_multidigraph(self):
+        G = nx.MultiDiGraph()
+        G.add_edges_from([(0, 1), (1, 2)])
+        self.func(G, [(0, 2)])
+
+    def test_no_common_neighbor(self):
+        G = nx.Graph()
+        G.add_edges_from([(0, 1), (2, 3)])
+        self.test(G, [(0, 2)], [(0, 2, 0)])
+
+    def test_isolated_nodes(self):
+        G = nx.Graph()
+        G.add_nodes_from([0, 1])
+        self.test(G, [(0, 1)], [(0, 1, 0)])
+
+    def test_all_nonexistent_edges(self):
+        G = nx.Graph()
+        G.add_edges_from([(0, 1), (0, 2), (2, 3)])
+        self.test(G, None, [(0, 3, 0.5), (1, 2, 0.5), (1, 3, 0)])
+
+
+class TestAdamicAdarIndex():
+    def setUp(self):
+        self.func = nx.adamic_adar_index
+
+        def test_func(G, ebunch, expected):
+            result = self.func(G, ebunch)
+            for res, exp in zip(result, expected):
+                assert_true(isinstance(res, tuple))
+                assert_equal(3, len(res))
+                assert_equal(res[0], exp[0])
+                assert_equal(res[1], exp[1])
+                assert_almost_equal(res[2], exp[2])
         self.test = test_func
 
     def test_K5(self):
         G = nx.complete_graph(5)
-        self.test(G, 0, 1, 0.75)
+        self.test(G, [(0, 1)], [(0, 1, 3 / math.log(4))])
 
     def test_P3(self):
         G = nx.path_graph(3)
-        self.test(G, 0, 2, 0.5)
+        self.test(G, [(0, 2)], [(0, 2, 1 / math.log(2))])
 
     def test_S4(self):
         G = nx.star_graph(4)
-        self.test(G, 1, 2, 0.25)
+        self.test(G, [(1, 2)], [(1, 2, 1 / math.log(4))])
 
-    @raises(NetworkXNotImplemented)
+    @raises(nx.NetworkXNotImplemented)
     def test_digraph(self):
         G = nx.DiGraph()
         G.add_edges_from([(0, 1), (1, 2)])
-        self.func(G, 0, 2)
+        self.func(G, [(0, 2)])
 
-    @raises(NetworkXNotImplemented)
+    @raises(nx.NetworkXNotImplemented)
     def test_multigraph(self):
         G = nx.MultiGraph()
         G.add_edges_from([(0, 1), (1, 2)])
-        self.func(G, 0, 2)
+        self.func(G, [(0, 2)])
 
-    @raises(NetworkXNotImplemented)
+    @raises(nx.NetworkXNotImplemented)
     def test_multidigraph(self):
         G = nx.MultiDiGraph()
         G.add_edges_from([(0, 1), (1, 2)])
-        self.func(G, 0, 2)
+        self.func(G, [(0, 2)])
 
-    def test_custom1(self):
-        """Case of no common neighbors."""
+    def test_no_common_neighbor(self):
         G = nx.Graph()
         G.add_nodes_from([0, 1])
-        self.test(G, 0, 1, 0)
+        self.test(G, [(0, 1)], [(0, 1, 0)])
 
-    def test_custom2(self):
-        """Case of equal nodes."""
+    def test_equal_nodes(self):
         G = nx.complete_graph(4)
-        self.test(G, 0, 0, 1)
+        self.test(G, [(0, 0)], [(0, 0, 3 / math.log(3))])
+
+    def test_all_nonexistent_edges(self):
+        G = nx.Graph()
+        G.add_edges_from([(0, 1), (0, 2), (2, 3)])
+        self.test(G, None, [(0, 3, 1 / math.log(2)), (1, 2, 1 / math.log(2)),
+                  (1, 3, 0)])
+
+
+class TestPreferentialAttachment():
+    def setUp(self):
+        self.func = nx.preferential_attachment
+
+        def test_func(G, ebunch, expected):
+            result = self.func(G, ebunch)
+            for res, exp in zip(result, expected):
+                assert_true(isinstance(res, tuple))
+                assert_equal(3, len(res))
+                assert_equal(res[0], exp[0])
+                assert_equal(res[1], exp[1])
+                assert_equal(res[2], exp[2])
+        self.test = test_func
+
+    def test_K5(self):
+        G = nx.complete_graph(5)
+        self.test(G, [(0, 1)], [(0, 1, 16)])
+
+    def test_P3(self):
+        G = nx.path_graph(3)
+        self.test(G, [(0, 1)], [(0, 1, 2)])
+
+    def test_S4(self):
+        G = nx.star_graph(4)
+        self.test(G, [(0, 2)], [(0, 2, 4)])
+
+    @raises(nx.NetworkXNotImplemented)
+    def test_digraph(self):
+        G = nx.DiGraph()
+        G.add_edges_from([(0, 1), (1, 2)])
+        self.func(G, [(0, 2)])
+
+    @raises(nx.NetworkXNotImplemented)
+    def test_multigraph(self):
+        G = nx.MultiGraph()
+        G.add_edges_from([(0, 1), (1, 2)])
+        self.func(G, [(0, 2)])
+
+    @raises(nx.NetworkXNotImplemented)
+    def test_multidigraph(self):
+        G = nx.MultiDiGraph()
+        G.add_edges_from([(0, 1), (1, 2)])
+        self.func(G, [(0, 2)])
+
+    def test_zero_degrees(self):
+        G = nx.Graph()
+        G.add_nodes_from([0, 1])
+        self.test(G, [(0, 1)], [(0, 1, 0)])
+
+    def test_all_nonexistent_edges(self):
+        G = nx.Graph()
+        G.add_edges_from([(0, 1), (0, 2), (2, 3)])
+        self.test(G, None, [(0, 3, 2), (1, 2, 2), (1, 3, 1)])
 
 
 class TestCNSoundarajanHopcroft():
     def setUp(self):
-        self.func = lp.cn_soundarajan_hopcroft
-        def test_func(G, u, v, expected):
-            result = self.func(G, u, v)
-            assert_equal(result, expected)
+        self.func = nx.cn_soundarajan_hopcroft
+
+        def test_func(G, ebunch, expected, community='community'):
+            result = self.func(G, ebunch, community)
+            for res, exp in zip(result, expected):
+                assert_true(isinstance(res, tuple))
+                assert_equal(3, len(res))
+                assert_equal(res[0], exp[0])
+                assert_equal(res[1], exp[1])
+                assert_equal(res[2], exp[2])
         self.test = test_func
 
     def test_K5(self):
@@ -71,14 +256,14 @@ class TestCNSoundarajanHopcroft():
         G.node[2]['community'] = 0
         G.node[3]['community'] = 0
         G.node[4]['community'] = 1
-        self.test(G, 0, 1, 5)
+        self.test(G, [(0, 1)], [(0, 1, 5)])
 
     def test_P3(self):
         G = nx.path_graph(3)
         G.node[0]['community'] = 0
         G.node[1]['community'] = 1
         G.node[2]['community'] = 0
-        self.test(G, 0, 2, 1)
+        self.test(G, [(0, 2)], [(0, 2, 1)])
 
     def test_S4(self):
         G = nx.star_graph(4)
@@ -87,95 +272,112 @@ class TestCNSoundarajanHopcroft():
         G.node[2]['community'] = 1
         G.node[3]['community'] = 0
         G.node[4]['community'] = 0
-        self.test(G, 1, 2, 2)
+        self.test(G, [(1, 2)], [(1, 2, 2)])
 
-    @raises(NetworkXNotImplemented)
+    @raises(nx.NetworkXNotImplemented)
     def test_digraph(self):
         G = nx.DiGraph()
         G.add_edges_from([(0, 1), (1, 2)])
         G.node[0]['community'] = 0
         G.node[1]['community'] = 0
         G.node[2]['community'] = 0
-        self.func(G, 0, 2)
+        self.func(G, [(0, 2)])
 
-    @raises(NetworkXNotImplemented)
+    @raises(nx.NetworkXNotImplemented)
     def test_multigraph(self):
         G = nx.MultiGraph()
         G.add_edges_from([(0, 1), (1, 2)])
         G.node[0]['community'] = 0
         G.node[1]['community'] = 0
         G.node[2]['community'] = 0
-        self.func(G, 0, 2)
+        self.func(G, [(0, 2)])
 
-    @raises(NetworkXNotImplemented)
+    @raises(nx.NetworkXNotImplemented)
     def test_multidigraph(self):
         G = nx.MultiDiGraph()
         G.add_edges_from([(0, 1), (1, 2)])
         G.node[0]['community'] = 0
         G.node[1]['community'] = 0
         G.node[2]['community'] = 0
-        self.func(G, 0, 2)
+        self.func(G, [(0, 2)])
 
-    def test_custom1(self):
-        """Case of no common neighbors."""
+    def test_no_common_neighbor(self):
         G = nx.Graph()
         G.add_nodes_from([0, 1])
         G.node[0]['community'] = 0
         G.node[1]['community'] = 0
-        self.test(G, 0, 1, 0)
+        self.test(G, [(0, 1)], [(0, 1, 0)])
 
-    def test_custom2(self):
-        """Case of equal nodes."""
+    def test_equal_nodes(self):
         G = nx.complete_graph(3)
         G.node[0]['community'] = 0
         G.node[1]['community'] = 0
         G.node[2]['community'] = 0
-        self.test(G, 0, 0, 4)
+        self.test(G, [(0, 0)], [(0, 0, 4)])
 
-    def test_custom3(self):
-        """Case of different community."""
+    def test_different_community(self):
         G = nx.Graph()
         G.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 3)])
         G.node[0]['community'] = 0
         G.node[1]['community'] = 0
         G.node[2]['community'] = 0
         G.node[3]['community'] = 1
-        self.test(G, 0, 3, 2)
+        self.test(G, [(0, 3)], [(0, 3, 2)])
 
-    @raises(NetworkXAlgorithmError)
-    def test_custom4(self):
-        """Case of no community information."""
+    @raises(nx.NetworkXAlgorithmError)
+    def test_no_community_information(self):
         G = nx.complete_graph(5)
-        self.func(G, 0, 1)
+        list(self.func(G, [(0, 1)]))
 
-    @raises(NetworkXAlgorithmError)
-    def test_custom5(self):
-        """Case of insufficient community information."""
+    @raises(nx.NetworkXAlgorithmError)
+    def test_insufficient_community_information(self):
         G = nx.Graph()
         G.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 3)])
         G.node[0]['community'] = 0
         G.node[1]['community'] = 0
         G.node[3]['community'] = 0
-        self.func(G, 0, 3)
+        list(self.func(G, [(0, 3)]))
 
-    def test_custom6(self):
-        """Case of sufficient community information."""
+    def test_sufficient_community_information(self):
         G = nx.Graph()
         G.add_edges_from([(0, 1), (1, 2), (1, 3), (2, 4), (3, 4), (4, 5)])
         G.node[1]['community'] = 0
         G.node[2]['community'] = 0
         G.node[3]['community'] = 0
         G.node[4]['community'] = 0
-        self.test(G, 1, 4, 4)
+        self.test(G, [(1, 4)], [(1, 4, 4)])
+
+    def test_custom_community_attribute_name(self):
+        G = nx.Graph()
+        G.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 3)])
+        G.node[0]['cmty'] = 0
+        G.node[1]['cmty'] = 0
+        G.node[2]['cmty'] = 0
+        G.node[3]['cmty'] = 1
+        self.test(G, [(0, 3)], [(0, 3, 2)], community='cmty')
+
+    def test_all_nonexistent_edges(self):
+        G = nx.Graph()
+        G.add_edges_from([(0, 1), (0, 2), (2, 3)])
+        G.node[0]['community'] = 0
+        G.node[1]['community'] = 1
+        G.node[2]['community'] = 0
+        G.node[3]['community'] = 0
+        self.test(G, None, [(0, 3, 2), (1, 2, 1), (1, 3, 0)])
 
 
 class TestRAIndexSoundarajanHopcroft():
     def setUp(self):
-        self.func = lp.ra_index_soundarajan_hopcroft
-        def test_func(G, u, v, expected):
-            tol = 1e-7
-            result = self.func(G, u, v)
-            assert_true(abs(result - expected) < tol)
+        self.func = nx.ra_index_soundarajan_hopcroft
+
+        def test_func(G, ebunch, expected, community='community'):
+            result = self.func(G, ebunch, community)
+            for res, exp in zip(result, expected):
+                assert_true(isinstance(res, tuple))
+                assert_equal(3, len(res))
+                assert_equal(res[0], exp[0])
+                assert_equal(res[1], exp[1])
+                assert_almost_equal(res[2], exp[2])
         self.test = test_func
 
     def test_K5(self):
@@ -185,14 +387,14 @@ class TestRAIndexSoundarajanHopcroft():
         G.node[2]['community'] = 0
         G.node[3]['community'] = 0
         G.node[4]['community'] = 1
-        self.test(G, 0, 1, 0.5)
+        self.test(G, [(0, 1)], [(0, 1, 0.5)])
 
     def test_P3(self):
         G = nx.path_graph(3)
         G.node[0]['community'] = 0
         G.node[1]['community'] = 1
         G.node[2]['community'] = 0
-        self.test(G, 0, 2, 0)
+        self.test(G, [(0, 2)], [(0, 2, 0)])
 
     def test_S4(self):
         G = nx.star_graph(4)
@@ -201,96 +403,114 @@ class TestRAIndexSoundarajanHopcroft():
         G.node[2]['community'] = 1
         G.node[3]['community'] = 0
         G.node[4]['community'] = 0
-        self.test(G, 1, 2, 0.25)
+        self.test(G, [(1, 2)], [(1, 2, 0.25)])
 
-    @raises(NetworkXNotImplemented)
+    @raises(nx.NetworkXNotImplemented)
     def test_digraph(self):
         G = nx.DiGraph()
         G.add_edges_from([(0, 1), (1, 2)])
         G.node[0]['community'] = 0
         G.node[1]['community'] = 0
         G.node[2]['community'] = 0
-        self.func(G, 0, 2)
+        self.func(G, [(0, 2)])
 
-    @raises(NetworkXNotImplemented)
+    @raises(nx.NetworkXNotImplemented)
     def test_multigraph(self):
         G = nx.MultiGraph()
         G.add_edges_from([(0, 1), (1, 2)])
         G.node[0]['community'] = 0
         G.node[1]['community'] = 0
         G.node[2]['community'] = 0
-        self.func(G, 0, 2)
+        self.func(G, [(0, 2)])
 
-    @raises(NetworkXNotImplemented)
+    @raises(nx.NetworkXNotImplemented)
     def test_multidigraph(self):
         G = nx.MultiDiGraph()
         G.add_edges_from([(0, 1), (1, 2)])
         G.node[0]['community'] = 0
         G.node[1]['community'] = 0
         G.node[2]['community'] = 0
-        self.func(G, 0, 2)
+        self.func(G, [(0, 2)])
 
-    def test_custom1(self):
-        """Case of no common neighbors."""
+    def test_no_common_neighbor(self):
         G = nx.Graph()
         G.add_nodes_from([0, 1])
         G.node[0]['community'] = 0
         G.node[1]['community'] = 0
-        self.test(G, 0, 1, 0)
+        self.test(G, [(0, 1)], [(0, 1, 0)])
 
-    def test_custom2(self):
-        """Case of equal nodes."""
+    def test_equal_nodes(self):
         G = nx.complete_graph(3)
         G.node[0]['community'] = 0
         G.node[1]['community'] = 0
         G.node[2]['community'] = 0
-        self.test(G, 0, 0, 1)
+        self.test(G, [(0, 0)], [(0, 0, 1)])
 
-    def test_custom3(self):
-        """Case of different community."""
+    def test_different_community(self):
         G = nx.Graph()
         G.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 3)])
         G.node[0]['community'] = 0
         G.node[1]['community'] = 0
         G.node[2]['community'] = 0
         G.node[3]['community'] = 1
-        self.test(G, 0, 3, 0)
+        self.test(G, [(0, 3)], [(0, 3, 0)])
 
-    @raises(NetworkXAlgorithmError)
-    def test_custom4(self):
-        """Case of no community information."""
+    @raises(nx.NetworkXAlgorithmError)
+    def test_no_community_information(self):
         G = nx.complete_graph(5)
-        self.func(G, 0, 1)
+        list(self.func(G, [(0, 1)]))
 
-    @raises(NetworkXAlgorithmError)
-    def test_custom5(self):
-        """Case of insufficient community information."""
+    @raises(nx.NetworkXAlgorithmError)
+    def test_insufficient_community_information(self):
         G = nx.Graph()
         G.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 3)])
         G.node[0]['community'] = 0
         G.node[1]['community'] = 0
         G.node[3]['community'] = 0
-        self.func(G, 0, 3)
+        list(self.func(G, [(0, 3)]))
 
-    def test_custom6(self):
-        """Case of sufficient community information."""
+    def test_sufficient_community_information(self):
         G = nx.Graph()
         G.add_edges_from([(0, 1), (1, 2), (1, 3), (2, 4), (3, 4), (4, 5)])
         G.node[1]['community'] = 0
         G.node[2]['community'] = 0
         G.node[3]['community'] = 0
         G.node[4]['community'] = 0
-        self.test(G, 1, 4, 1)
+        self.test(G, [(1, 4)], [(1, 4, 1)])
+
+    def test_custom_community_attribute_name(self):
+        G = nx.Graph()
+        G.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 3)])
+        G.node[0]['cmty'] = 0
+        G.node[1]['cmty'] = 0
+        G.node[2]['cmty'] = 0
+        G.node[3]['cmty'] = 1
+        self.test(G, [(0, 3)], [(0, 3, 0)], community='cmty')
+
+    def test_all_nonexistent_edges(self):
+        G = nx.Graph()
+        G.add_edges_from([(0, 1), (0, 2), (2, 3)])
+        G.node[0]['community'] = 0
+        G.node[1]['community'] = 1
+        G.node[2]['community'] = 0
+        G.node[3]['community'] = 0
+        self.test(G, None, [(0, 3, 0.5), (1, 2, 0), (1, 3, 0)])
 
 
 class TestWithinInterCluster():
     def setUp(self):
         self.delta = 0.001
-        self.func = lp.within_inter_cluster
-        def test_func(G, u, v, expected):
-            tol = 1e-7
-            result = self.func(G, u, v, self.delta)
-            assert_true(abs(result - expected) < tol)
+        self.func = nx.within_inter_cluster
+
+        def test_func(G, ebunch, expected, delta=self.delta,
+                      community='community'):
+            result = self.func(G, ebunch, delta, community)
+            for res, exp in zip(result, expected):
+                assert_true(isinstance(res, tuple))
+                assert_equal(3, len(res))
+                assert_equal(res[0], exp[0])
+                assert_equal(res[1], exp[1])
+                assert_almost_equal(res[2], exp[2])
         self.test = test_func
 
     def test_K5(self):
@@ -300,14 +520,14 @@ class TestWithinInterCluster():
         G.node[2]['community'] = 0
         G.node[3]['community'] = 0
         G.node[4]['community'] = 1
-        self.test(G, 0, 1, 2 / (1 + self.delta))
+        self.test(G, [(0, 1)], [(0, 1, 2 / (1 + self.delta))])
 
     def test_P3(self):
         G = nx.path_graph(3)
         G.node[0]['community'] = 0
         G.node[1]['community'] = 1
         G.node[2]['community'] = 0
-        self.test(G, 0, 2, 0)
+        self.test(G, [(0, 2)], [(0, 2, 0)])
 
     def test_S4(self):
         G = nx.star_graph(4)
@@ -316,110 +536,118 @@ class TestWithinInterCluster():
         G.node[2]['community'] = 1
         G.node[3]['community'] = 0
         G.node[4]['community'] = 0
-        self.test(G, 1, 2, 1 / self.delta)
+        self.test(G, [(1, 2)], [(1, 2, 1 / self.delta)])
 
-    @raises(NetworkXNotImplemented)
+    @raises(nx.NetworkXNotImplemented)
     def test_digraph(self):
         G = nx.DiGraph()
         G.add_edges_from([(0, 1), (1, 2)])
         G.node[0]['community'] = 0
         G.node[1]['community'] = 0
         G.node[2]['community'] = 0
-        self.func(G, 0, 2, self.delta)
+        self.func(G, [(0, 2)])
 
-    @raises(NetworkXNotImplemented)
+    @raises(nx.NetworkXNotImplemented)
     def test_multigraph(self):
         G = nx.MultiGraph()
         G.add_edges_from([(0, 1), (1, 2)])
         G.node[0]['community'] = 0
         G.node[1]['community'] = 0
         G.node[2]['community'] = 0
-        self.func(G, 0, 2, self.delta)
+        self.func(G, [(0, 2)])
 
-    @raises(NetworkXNotImplemented)
+    @raises(nx.NetworkXNotImplemented)
     def test_multidigraph(self):
         G = nx.MultiDiGraph()
         G.add_edges_from([(0, 1), (1, 2)])
         G.node[0]['community'] = 0
         G.node[1]['community'] = 0
         G.node[2]['community'] = 0
-        self.func(G, 0, 2, self.delta)
+        self.func(G, [(0, 2)])
 
-    def test_custom1(self):
-        """Case of no common neighbors."""
+    def test_no_common_neighbor(self):
         G = nx.Graph()
         G.add_nodes_from([0, 1])
         G.node[0]['community'] = 0
         G.node[1]['community'] = 0
-        self.test(G, 0, 1, 0)
+        self.test(G, [(0, 1)], [(0, 1, 0)])
 
-    def test_custom2(self):
-        """Case of equal nodes."""
+    def test_equal_nodes(self):
         G = nx.complete_graph(3)
         G.node[0]['community'] = 0
         G.node[1]['community'] = 0
         G.node[2]['community'] = 0
-        self.test(G, 0, 0, 2 / self.delta)
+        self.test(G, [(0, 0)], [(0, 0, 2 / self.delta)])
 
-    def test_custom3(self):
-        """Case of different community."""
+    def test_different_community(self):
         G = nx.Graph()
         G.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 3)])
         G.node[0]['community'] = 0
         G.node[1]['community'] = 0
         G.node[2]['community'] = 0
         G.node[3]['community'] = 1
-        self.test(G, 0, 3, 0)
+        self.test(G, [(0, 3)], [(0, 3, 0)])
 
-    def test_custom4(self):
-        """Case of no inter-cluster neighbor."""
+    def test_no_inter_cluster_common_neighbor(self):
         G = nx.complete_graph(4)
         G.node[0]['community'] = 0
         G.node[1]['community'] = 0
         G.node[2]['community'] = 0
         G.node[3]['community'] = 0
-        self.test(G, 0, 3, 2 / self.delta)
+        self.test(G, [(0, 3)], [(0, 3, 2 / self.delta)])
 
-    @raises(NetworkXAlgorithmError)
-    def test_custom5(self):
-        """Case of no community information."""
+    @raises(nx.NetworkXAlgorithmError)
+    def test_no_community_information(self):
         G = nx.complete_graph(5)
-        self.func(G, 0, 1)
+        list(self.func(G, [(0, 1)]))
 
-    @raises(NetworkXAlgorithmError)
-    def test_custom6(self):
-        """Case of insufficient community information."""
+    @raises(nx.NetworkXAlgorithmError)
+    def test_insufficient_community_information(self):
         G = nx.Graph()
         G.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 3)])
         G.node[0]['community'] = 0
         G.node[1]['community'] = 0
         G.node[3]['community'] = 0
-        self.func(G, 0, 3)
+        list(self.func(G, [(0, 3)]))
 
-    def test_custom7(self):
-        """Case of sufficient community information."""
+    def test_sufficient_community_information(self):
         G = nx.Graph()
         G.add_edges_from([(0, 1), (1, 2), (1, 3), (2, 4), (3, 4), (4, 5)])
         G.node[1]['community'] = 0
         G.node[2]['community'] = 0
         G.node[3]['community'] = 0
         G.node[4]['community'] = 0
-        self.test(G, 1, 4, 2 / self.delta)
+        self.test(G, [(1, 4)], [(1, 4, 2 / self.delta)])
 
-    @raises(NetworkXAlgorithmError)
-    def test_custom8(self):
-        """Case of delta equals zero."""
+    @raises(nx.NetworkXAlgorithmError)
+    def test_zero_delta(self):
         G = nx.complete_graph(3)
         G.node[0]['community'] = 0
         G.node[1]['community'] = 0
         G.node[2]['community'] = 0
-        self.func(G, 0, 1, 0)
+        list(self.func(G, [(0, 1)], 0))
 
-    @raises(NetworkXAlgorithmError)
-    def test_custom9(self):
-        """Case of delta less than zero."""
+    @raises(nx.NetworkXAlgorithmError)
+    def test_negative_delta(self):
         G = nx.complete_graph(3)
         G.node[0]['community'] = 0
         G.node[1]['community'] = 0
         G.node[2]['community'] = 0
-        self.func(G, 0, 1, -0.5)
+        list(self.func(G, [(0, 1)], -0.5))
+
+    def test_custom_community_attribute_name(self):
+        G = nx.complete_graph(4)
+        G.node[0]['cmty'] = 0
+        G.node[1]['cmty'] = 0
+        G.node[2]['cmty'] = 0
+        G.node[3]['cmty'] = 0
+        self.test(G, [(0, 3)], [(0, 3, 2 / self.delta)], community='cmty')
+
+    def test_all_nonexistent_edges(self):
+        G = nx.Graph()
+        G.add_edges_from([(0, 1), (0, 2), (2, 3)])
+        G.node[0]['community'] = 0
+        G.node[1]['community'] = 1
+        G.node[2]['community'] = 0
+        G.node[3]['community'] = 0
+        self.test(G, None, [(0, 3, 1 / self.delta), (1, 2, 0), (1, 3, 0)])