Repository: networkx/networkx

Issue:
Personalization in PageRank
In https://github.com/networkx/networkx/blob/master/networkx/algorithms/link_analysis/pagerank_alg.py in all algorithms, the personalization dict accepted needs a value for every node. In my personal application, most values are 0. I suspect that in a lot of applications, including the default, most nodes will have the same probability.
Furthermore, for all but the PageRank algorithm, the docstring suggests that each of these values needs to be non-zero. As far as I know, there is no code-technical or mathematical basis for this and it should be "at least one non-zero value".

My proposal:

- Add a parameter specifying a default value for personalization.
- Do not force presence of all keys in personalization, instead use default value for non-existant values.
- Rewrite docstrings to specify "at least one non-zero value"

I'll be happy to implement this. Feedback appreciated. :)

Discussion:

Patch:
diff --git a/networkx/algorithms/components/biconnected.py b/networkx/algorithms/components/biconnected.py
index 3cc4d0b5c..9605d2515 100644
--- a/networkx/algorithms/components/biconnected.py
+++ b/networkx/algorithms/components/biconnected.py
@@ -351,7 +351,7 @@ def biconnected_component_subgraphs(G, copy=True):
 
 @not_implemented_for('directed')
 def articulation_points(G):
-    """Return a generator of articulation points, or cut vertices, of a graph.
+    """Yield the articulation points, or cut vertices, of a graph.
 
     An articulation point or cut vertex is any node whose removal (along with
     all its incident edges) increases the number of connected components of
@@ -366,10 +366,10 @@ def articulation_points(G):
     G : NetworkX Graph
         An undirected graph.
 
-    Returns
-    -------
-    articulation points : generator
-        generator of nodes
+    Yields
+    ------
+    node
+        An articulation point in the graph.
 
     Raises
     ------
@@ -417,7 +417,11 @@ def articulation_points(G):
            Communications of the ACM 16: 372–378. doi:10.1145/362248.362272
 
     """
-    return _biconnected_dfs(G, components=False)
+    seen = set()
+    for articulation in _biconnected_dfs(G, components=False):
+        if articulation not in seen:
+            seen.add(articulation)
+            yield articulation
 
 
 @not_implemented_for('directed')
diff --git a/networkx/algorithms/link_analysis/pagerank_alg.py b/networkx/algorithms/link_analysis/pagerank_alg.py
index a105f8f28..889215487 100644
--- a/networkx/algorithms/link_analysis/pagerank_alg.py
+++ b/networkx/algorithms/link_analysis/pagerank_alg.py
@@ -35,8 +35,9 @@ def pagerank(G, alpha=0.85, personalization=None,
 
     personalization: dict, optional
       The "personalization vector" consisting of a dictionary with a
-      key for every graph node and personalization value for each node.
+      key some subset of graph nodes and personalization value each of those.
       At least one personalization value must be non-zero.
+      If not specfiied, a nodes personalization value will be zero.
       By default, a uniform distribution is used.
 
     max_iter : integer, optional
@@ -129,11 +130,6 @@ def pagerank(G, alpha=0.85, personalization=None,
         # Assign uniform personalization vector if not given
         p = dict.fromkeys(W, 1.0 / N)
     else:
-        missing = set(G) - set(personalization)
-        if missing:
-            raise NetworkXError('Personalization dictionary '
-                                'must have a value for every node. '
-                                'Missing nodes %s' % missing)
         s = float(sum(personalization.values()))
         p = dict((k, v / s) for k, v in personalization.items())
 
@@ -141,11 +137,6 @@ def pagerank(G, alpha=0.85, personalization=None,
         # Use personalization vector if dangling vector not specified
         dangling_weights = p
     else:
-        missing = set(G) - set(dangling)
-        if missing:
-            raise NetworkXError('Dangling node dictionary '
-                                'must have a value for every node. '
-                                'Missing nodes %s' % missing)
         s = float(sum(dangling.values()))
         dangling_weights = dict((k, v/s) for k, v in dangling.items())
     dangling_nodes = [n for n in W if W.out_degree(n, weight=weight) == 0.0]
@@ -160,7 +151,7 @@ def pagerank(G, alpha=0.85, personalization=None,
             # doing a left multiply x^T=xlast^T*W
             for nbr in W[n]:
                 x[nbr] += alpha * xlast[n] * W[n][nbr][weight]
-            x[n] += danglesum * dangling_weights[n] + (1.0 - alpha) * p[n]
+            x[n] += danglesum * dangling_weights.get(n,0) + (1.0 - alpha) * p.get(n,0)
         # check convergence, l1 norm
         err = sum([abs(x[n] - xlast[n]) for n in x])
         if err < N*tol:
@@ -183,7 +174,9 @@ def google_matrix(G, alpha=0.85, personalization=None,
 
     personalization: dict, optional
       The "personalization vector" consisting of a dictionary with a
-      key for every graph node and nonzero personalization value for each node.
+      key some subset of graph nodes and personalization value each of those.
+      At least one personalization value must be non-zero.
+      If not specfiied, a nodes personalization value will be zero.
       By default, a uniform distribution is used.
 
     nodelist : list, optional
@@ -238,25 +231,15 @@ def google_matrix(G, alpha=0.85, personalization=None,
     if personalization is None:
         p = np.repeat(1.0 / N, N)
     else:
-        missing = set(nodelist) - set(personalization)
-        if missing:
-            raise NetworkXError('Personalization vector dictionary '
-                                'must have a value for every node. '
-                                'Missing nodes %s' % missing)
-        p = np.array([personalization[n] for n in nodelist], dtype=float)
+        p = np.array([personalization.get(n, 0) for n in nodelist], dtype=float)
         p /= p.sum()
 
     # Dangling nodes
     if dangling is None:
         dangling_weights = p
     else:
-        missing = set(nodelist) - set(dangling)
-        if missing:
-            raise NetworkXError('Dangling node dictionary '
-                                'must have a value for every node. '
-                                'Missing nodes %s' % missing)
         # Convert the dangling dictionary into an array in nodelist order
-        dangling_weights = np.array([dangling[n] for n in nodelist],
+        dangling_weights = np.array([dangling.get(n, 0) for n in nodelist],
                                     dtype=float)
         dangling_weights /= dangling_weights.sum()
     dangling_nodes = np.where(M.sum(axis=1) == 0)[0]
@@ -288,9 +271,11 @@ def pagerank_numpy(G, alpha=0.85, personalization=None, weight='weight',
       Damping parameter for PageRank, default=0.85.
 
     personalization: dict, optional
-       The "personalization vector" consisting of a dictionary with a
-       key for every graph node and nonzero personalization value for each
-       node. By default, a uniform distribution is used.
+      The "personalization vector" consisting of a dictionary with a
+      key some subset of graph nodes and personalization value each of those.
+      At least one personalization value must be non-zero.
+      If not specfiied, a nodes personalization value will be zero.
+      By default, a uniform distribution is used.
 
     weight : key, optional
       Edge data key to use as weight.  If None weights are set to 1.
@@ -370,9 +355,11 @@ def pagerank_scipy(G, alpha=0.85, personalization=None,
       Damping parameter for PageRank, default=0.85.
 
     personalization: dict, optional
-       The "personalization vector" consisting of a dictionary with a
-       key for every graph node and nonzero personalization value for each
-       node. By default, a uniform distribution is used.
+      The "personalization vector" consisting of a dictionary with a
+      key some subset of graph nodes and personalization value each of those.
+      At least one personalization value must be non-zero.
+      If not specfiied, a nodes personalization value will be zero.
+      By default, a uniform distribution is used.
 
     max_iter : integer, optional
       Maximum number of iterations in power method eigenvalue solver.
@@ -452,26 +439,15 @@ def pagerank_scipy(G, alpha=0.85, personalization=None,
     if personalization is None:
         p = scipy.repeat(1.0 / N, N)
     else:
-        missing = set(nodelist) - set(personalization)
-        if missing:
-            raise NetworkXError('Personalization vector dictionary '
-                                'must have a value for every node. '
-                                'Missing nodes %s' % missing)
-        p = scipy.array([personalization[n] for n in nodelist],
-                        dtype=float)
+        p = scipy.array([personalization.get(n, 0) for n in nodelist], dtype=float)
         p = p / p.sum()
 
     # Dangling nodes
     if dangling is None:
         dangling_weights = p
     else:
-        missing = set(nodelist) - set(dangling)
-        if missing:
-            raise NetworkXError('Dangling node dictionary '
-                                'must have a value for every node. '
-                                'Missing nodes %s' % missing)
         # Convert the dangling dictionary into an array in nodelist order
-        dangling_weights = scipy.array([dangling[n] for n in nodelist],
+        dangling_weights = scipy.array([dangling.get(n, 0) for n in nodelist],
                                        dtype=float)
         dangling_weights /= dangling_weights.sum()
     is_dangling = scipy.where(S == 0)[0]
diff --git a/networkx/generators/geometric.py b/networkx/generators/geometric.py
index 08675c6b3..b22de623a 100644
--- a/networkx/generators/geometric.py
+++ b/networkx/generators/geometric.py
@@ -9,6 +9,7 @@
 # Authors: Aric Hagberg (hagberg@lanl.gov)
 #          Dan Schult (dschult@colgate.edu)
 #          Ben Edwards (BJEdwards@gmail.com)
+#          Arya McCarthy (admccarthy@smu.edu)
 """Generators for geometric graphs.
 """
 from __future__ import division
@@ -20,6 +21,12 @@ from math import sqrt
 import math
 import random
 from random import uniform
+try:
+    from scipy.spatial import cKDTree as KDTree
+except ImportError:
+    _is_scipy_available = False
+else:
+    _is_scipy_available = True
 
 import networkx as nx
 from networkx.utils import nodes_or_number
@@ -38,14 +45,41 @@ def euclidean(x, y):
     return sqrt(sum((a - b) ** 2 for a, b in zip(x, y)))
 
 
+def _fast_construct_edges(G, radius, p):
+    """Construct edges for random geometric graph.
+
+    Requires scipy to be installed.
+    """
+    pos = nx.get_node_attributes(G, 'pos')
+    nodes, coords = list(zip(*pos.items()))
+    kdtree = KDTree(coords)  # Cannot provide generator.
+    edge_indexes = kdtree.query_pairs(radius, p)
+    edges = ((nodes[u], nodes[v]) for u, v in edge_indexes)
+    G.add_edges_from(edges)
+
+
+def _slow_construct_edges(G, radius, p):
+    """Construct edges for random geometric graph.
+
+    Works without scipy, but in `O(n^2)` time.
+    """
+    # TODO This can be parallelized.
+    for (u, pu), (v, pv) in combinations(G.nodes(data='pos'), 2):
+        if sum(abs(a - b) ** p for a, b in zip(pu, pv)) <= radius ** p:
+            G.add_edge(u, v)
+
+
 @nodes_or_number(0)
-def random_geometric_graph(n, radius, dim=2, pos=None, metric=None):
+def random_geometric_graph(n, radius, dim=2, pos=None, p=2):
     """Returns a random geometric graph in the unit cube.
 
     The random geometric graph model places `n` nodes uniformly at
     random in the unit cube. Two nodes are joined by an edge if the
     distance between the nodes is at most `radius`.
 
+    Edges are determined using a KDTree when SciPy is available.
+    This reduces the time complexity from :math:`O(n^2)` to :math:`O(n)`.
+
     Parameters
     ----------
     n : int or iterable
@@ -56,23 +90,15 @@ def random_geometric_graph(n, radius, dim=2, pos=None, metric=None):
         Dimension of graph
     pos : dict, optional
         A dictionary keyed by node with node positions as values.
-    metric : function
-        A metric on vectors of numbers (represented as lists or
-        tuples). This must be a function that accepts two lists (or
-        tuples) as input and yields a number as output. The function
-        must also satisfy the four requirements of a `metric`_.
-        Specifically, if *d* is the function and *x*, *y*,
-        and *z* are vectors in the graph, then *d* must satisfy
-
-        1. *d*(*x*, *y*) ≥ 0,
-        2. *d*(*x*, *y*) = 0 if and only if *x* = *y*,
-        3. *d*(*x*, *y*) = *d*(*y*, *x*),
-        4. *d*(*x*, *z*) ≤ *d*(*x*, *y*) + *d*(*y*, *z*).
+    p : float
+        Which Minkowski distance metric to use.  `p` has to meet the condition
+        ``1 <= p <= infinity``.
 
-        If this argument is not specified, the Euclidean distance metric is
-        used.
+        If this argument is not specified, the :math:`L^2` metric (the Euclidean
+        distance metric) is used.
 
-        .. _metric: https://en.wikipedia.org/wiki/Metric_%28mathematics%29
+        This should not be confused with the `p` of an Erdős-Rényi random
+        graph, which represents probability.
 
     Returns
     -------
@@ -90,20 +116,9 @@ def random_geometric_graph(n, radius, dim=2, pos=None, metric=None):
 
     >>> G = nx.random_geometric_graph(20, 0.1)
 
-    Specify an alternate distance metric using the ``metric`` keyword
-    argument. For example, to use the "`taxicab metric`_" instead of the
-    default `Euclidean metric`_::
-
-        >>> dist = lambda x, y: sum(abs(a - b) for a, b in zip(x, y))
-        >>> G = nx.random_geometric_graph(10, 0.1, metric=dist)
-
-    .. _taxicab metric: https://en.wikipedia.org/wiki/Taxicab_geometry
-    .. _Euclidean metric: https://en.wikipedia.org/wiki/Euclidean_distance
-
     Notes
     -----
-    This uses an `O(n^2)` algorithm to build the graph.  A faster algorithm
-    is possible using k-d trees.
+    This uses a *k*-d tree to build the graph.
 
     The `pos` keyword argument can be used to specify node positions so you
     can create an arbitrary distribution and domain for positions.
@@ -139,23 +154,12 @@ def random_geometric_graph(n, radius, dim=2, pos=None, metric=None):
     if pos is None:
         pos = {v: [random.random() for i in range(dim)] for v in nodes}
     nx.set_node_attributes(G, 'pos', pos)
-    # If no distance metric is provided, use Euclidean distance.
-    if metric is None:
-        metric = euclidean
 
-    def should_join(pair):
-        u, v = pair
-        u_pos, v_pos = pos[u], pos[v]
-        return metric(u_pos, v_pos) <= radius
+    if _is_scipy_available:
+        _fast_construct_edges(G, radius, p)
+    else:
+        _slow_construct_edges(G, radius, p)
 
-    # Join each pair of nodes whose distance is at most `radius`. (We
-    # know each node has a data attribute ``'pos'`` because we created
-    # such an attribute for each node above.)
-    #
-    # TODO This is an O(n^2) algorithm, a k-d tree could be used
-    # instead.
-    nodes = G.nodes(data='pos')
-    G.add_edges_from(filter(should_join, combinations(G, 2)))
     return G
 
 


Test patch:
diff --git a/networkx/algorithms/community/tests/test_asyn_lpa.py b/networkx/algorithms/community/tests/test_asyn_lpa.py
index a830bbb2d..519014e0f 100644
--- a/networkx/algorithms/community/tests/test_asyn_lpa.py
+++ b/networkx/algorithms/community/tests/test_asyn_lpa.py
@@ -1,4 +1,4 @@
-from nose.tools import assert_equal
+from nose.tools import assert_equal, assert_in
 from networkx import asyn_lpa, Graph
 
 
@@ -106,4 +106,5 @@ def test_two_communities():
 
     communities = asyn_lpa.asyn_lpa_communities(test)
     result = {frozenset(c) for c in communities}
-    assert_equal(result, ground_truth)
+    # probabilitistic result could be all nodes in one community. So test result is either.
+    assert_in(result, [ground_truth, {frozenset(range(16))}])
diff --git a/networkx/algorithms/components/tests/test_biconnected.py b/networkx/algorithms/components/tests/test_biconnected.py
index 19f02c3f6..faf216f4c 100644
--- a/networkx/algorithms/components/tests/test_biconnected.py
+++ b/networkx/algorithms/components/tests/test_biconnected.py
@@ -42,6 +42,11 @@ def test_barbell():
     pts = set(nx.articulation_points(G))
     assert_equal(pts, {7, 20, 21, 22})
 
+def test_articulation_points_repetitions():
+    G = nx.Graph()
+    G.add_edges_from([(0, 1), (1, 2), (1, 3)])
+    assert_equal(list(nx.articulation_points(G)), [1])
+
 def test_articulation_points_cycle():
     G=nx.cycle_graph(3)
     nx.add_cycle(G, [1, 3, 4])
diff --git a/networkx/algorithms/link_analysis/tests/test_pagerank.py b/networkx/algorithms/link_analysis/tests/test_pagerank.py
index a64899d5f..663f08815 100644
--- a/networkx/algorithms/link_analysis/tests/test_pagerank.py
+++ b/networkx/algorithms/link_analysis/tests/test_pagerank.py
@@ -71,13 +71,7 @@ class TestPageRank(object):
         p = numpy.array(ev[:, 0] / ev[:, 0].sum())[:, 0]
         for (a, b) in zip(p, self.G.pagerank.values()):
             assert_almost_equal(a, b)
-
-        personalize = dict((n, random.random()) for n in G)
-        M = networkx.google_matrix(G, alpha=0.9, personalization=personalize)
-        personalize.pop(1)
-        assert_raises(networkx.NetworkXError, networkx.google_matrix, G,
-                      personalization=personalize)
-
+        
     def test_personalization(self):
         G = networkx.complete_graph(4)
         personalize = {0: 1, 1: 1, 2: 4, 3: 4}
@@ -85,9 +79,6 @@ class TestPageRank(object):
         p = networkx.pagerank(G, alpha=0.85, personalization=personalize)
         for n in G:
             assert_almost_equal(p[n], answer[n], places=4)
-        personalize.pop(0)
-        assert_raises(networkx.NetworkXError, networkx.pagerank, G,
-                      personalization=personalize)
 
     def test_zero_personalization_vector(self):
         G = networkx.complete_graph(4)
@@ -102,7 +93,15 @@ class TestPageRank(object):
         p = networkx.pagerank(G, alpha=0.85, personalization=personalize)
         for n in G:
             assert_almost_equal(p[n], answer[n], places=4)
-
+            
+    def test_incomplete_personalization(self):
+        G = networkx.complete_graph(4)
+        personalize = {3: 1}
+        answer = {0: 0.22077931820379187, 1: 0.22077931820379187, 2: 0.22077931820379187, 3: 0.3376620453886241}
+        p = networkx.pagerank(G, alpha=0.85, personalization=personalize)
+        for n in G:
+            assert_almost_equal(p[n], answer[n], places=4)
+       
     def test_dangling_matrix(self):
         """
         Tests that the google_matrix doesn't change except for the dangling
diff --git a/networkx/classes/tests/test_graph.py b/networkx/classes/tests/test_graph.py
index a0fc425d1..644517380 100644
--- a/networkx/classes/tests/test_graph.py
+++ b/networkx/classes/tests/test_graph.py
@@ -94,13 +94,11 @@ class BaseGraphTester(object):
 
     @raises(networkx.NetworkXError)
     def test_nbunch_iter_node_format_raise(self):
-        """Tests that a node that would have failed string formatting
-        doesn't cause an error when attempting to raise a
-        :exc:`networkx.NetworkXError`.
+        #Tests that a node that would have failed string formatting
+        #doesn't cause an error when attempting to raise a
+        #:exc:`networkx.NetworkXError`.
 
-        For more information, see pull request #1813.
-
-        """
+        #For more information, see pull request #1813.
         G = self.Graph()
         nbunch = [('x', set())]
         list(G.nbunch_iter(nbunch))
diff --git a/networkx/generators/tests/test_geometric.py b/networkx/generators/tests/test_geometric.py
index f2ba80e54..e3692076a 100644
--- a/networkx/generators/tests/test_geometric.py
+++ b/networkx/generators/tests/test_geometric.py
@@ -7,6 +7,7 @@ from nose.tools import assert_true
 
 import networkx as nx
 
+
 class TestRandomGeometricGraph(object):
     """Unit tests for the :func:`~networkx.random_geometric_graph`
     function.
@@ -36,14 +37,32 @@ class TestRandomGeometricGraph(object):
             else:
                 assert_false(dist(G.node[u]['pos'], G.node[v]['pos']) <= 0.25)
 
-    def test_metric(self):
+    def test_p(self):
         """Tests for providing an alternate distance metric to the
         generator.
 
         """
         # Use the L1 metric.
         dist = lambda x, y: sum(abs(a - b) for a, b in zip(x, y))
-        G = nx.random_geometric_graph(50, 0.25, metric=dist)
+        G = nx.random_geometric_graph(50, 0.25, p=1)
+        for u, v in combinations(G, 2):
+            # Adjacent vertices must be within the given distance.
+            if v in G[u]:
+                assert_true(dist(G.node[u]['pos'], G.node[v]['pos']) <= 0.25)
+            # Nonadjacent vertices must be at greater distance.
+            else:
+                assert_false(dist(G.node[u]['pos'], G.node[v]['pos']) <= 0.25)
+
+    def test_node_names(self):
+        """Tests using values other than sequential numbers as node IDs.
+
+        """
+        import string
+        nodes = list(string.ascii_lowercase)
+        G = nx.random_geometric_graph(nodes, 0.25)
+        assert_equal(len(G), len(nodes))
+
+        dist = lambda x, y: sqrt(sum((a - b) ** 2 for a, b in zip(x, y)))
         for u, v in combinations(G, 2):
             # Adjacent vertices must be within the given distance.
             if v in G[u]:
@@ -145,14 +164,14 @@ class TestWaxmanGraph(object):
 class TestNavigableSmallWorldGraph(object):
 
     def test_navigable_small_world(self):
-        G = nx.navigable_small_world_graph(5,p=1,q=0)
-        gg = nx.grid_2d_graph(5,5).to_directed()
-        assert_true(nx.is_isomorphic(G,gg))
+        G = nx.navigable_small_world_graph(5, p=1, q=0)
+        gg = nx.grid_2d_graph(5, 5).to_directed()
+        assert_true(nx.is_isomorphic(G, gg))
 
-        G = nx.navigable_small_world_graph(5,p=1,q=0,dim=3)
-        gg = nx.grid_graph([5,5,5]).to_directed()
-        assert_true(nx.is_isomorphic(G,gg))
+        G = nx.navigable_small_world_graph(5, p=1, q=0, dim=3)
+        gg = nx.grid_graph([5, 5, 5]).to_directed()
+        assert_true(nx.is_isomorphic(G, gg))
 
-        G = nx.navigable_small_world_graph(5,p=1,q=0,dim=1)
+        G = nx.navigable_small_world_graph(5, p=1, q=0, dim=1)
         gg = nx.grid_graph([5]).to_directed()
-        assert_true(nx.is_isomorphic(G,gg))
+        assert_true(nx.is_isomorphic(G, gg))